【程式學習】哈佛CS50x學習筆記_Week4：記憶體

 *本文是CS50x的中文學習筆記，是原課程的筆記補充，建議先上完課，看完原課程筆記，再閱讀本文。

這就是cs50，就是這麼難

我見到有人說哈佛大學CS50x課程其實不太適合初學者，我自己的經驗也是覺得爆難的。除了要自己補充很多相關知識，寫作業也常卡關。昨天卡了一個下午，只好上網查了作業的解答，畢竟有很多網友已經在網路上分享他們的學習心得，與本系列文一樣。

直接看別人的作業，基本上違反了這堂課的規定，如果你之前上傳過作業的話，應該會注意到，上傳前系統都會問你是不是誠實。但是我認為，一來我們不是哈佛大學的學生，是來學習不是來拿學分的，沒必要嚴格遵守課程規範；二來如果不是真的抄別人的作業，會試著自己寫過一次，已經有達到學習的目的了。畢竟CS50x真的挺困難的。

所以，CS50x到底適不適合初學者呢？教授David一再表示選本堂課的學生，有2/3的人過去從未學過任何一堂電腦課程。不過這些2/3的學生，完成課程的比例有高達8成嗎，我有點懷疑。但是要說CS50x是進階課程，也不太算，因為的確都是一些最基本的內容。其實CS50x的難，是因為他大量濃縮了基本知識，很多知識都只是帶過而已，絕對要自己去補充學習。

所以如果要看CS50x自學程式語言，建議要跟我以及眾網友一樣，把自己的心路歷程、學習心得、學習筆記，好好地整理一次。最好是放在網路上，也能嘉惠其他人，畢竟在網路上，中文的CS50學習筆記超級少。

16進位

在課程一開始，David介紹了16進位。

16進位的表示法，就是把10到15，替換成A、B、C、D、E、F。但是因為太容易跟10進位搞混，所以會前綴0x。例如0x0、0x1、0x2、0x3、0xA、0xB、0xC、0xD、0xE、0xF。

為什麼電腦工程師使用16進位呢，簡單來說，在早期IBM電腦公司在設計電腦時，是使用2進位的，也有用10進位的。用2進位來寫程式，位數過長。10進位固然方便，但是設計太複雜，電腦需要的硬體也比較多，不太划算。況且當時已經設計出編譯器，能夠自動轉換機器碼給電腦看。16進位符合當時的時代條件，與2進位轉換方便，跟硬體也相容，暫存器使用16進位，儲存的位數也比較少。因此IBM決定採用16進位。

然而，實際我們在寫程式時，除非是底層與硬體有關的設計，否則很少會用到16進位。在這裡談16進位，其實是為了介紹記憶體的位址。

指標Pointer

要談指標之前，得先談談String。

String在C語言是不存在的，它其實應該視為char的陣列，不過這也不是很正確的答案，更正確的說法是，string其實是指char陣列的第一個記憶體位址。CS50x團隊把一些概念簡化，將相關函式寫在cs50.h裡面，讓初學者不用一開始就接觸困難的概念。不過已經教了4堂課了，也該是時候學點困難的東西了。

假設你創一個變數如下：int a = 1;

這意思是你在記憶體取一個空間，取名叫a，然後你在裡面儲存整數1。這個空間有他的特殊位址，我們可以把記憶體位址想像成實際地址，例如是台北市中正區信義路一段1號，在這個地址有一個郵箱，a。

那麼指標是什麼意思呢，它是一種資料型態，可以設定變數，專門用來儲存記憶體位址。

假設我們今天，設了另一個郵箱，b。然後把b郵箱放在信義路一段50號，接著寫一張小紙條，裡頭是a郵箱的地址，放在b郵箱。然後告訴你，你想找a郵箱？先去b郵箱看看地址。這時你去b郵箱，就會找到a郵箱的地址。

在語法上怎麼操作呢，請見下方程式。

如果你執行下方的程式，a的記憶體位址，就會儲存在b，然後以16進位的數字顯示。我第一次執行時，記憶體位址顯示為0x7fff148cea98。每次執行時，因為記憶體都會被重新釋放，所以記憶體位址應該不會相同。

cs50x_w4_1.c

系統通常在設置一段記憶體區段時，會連續設置。而pointer也保存了陣列排序的特殊性，因此一個int陣列，arr[0]與arr[1]之間，也可以用*pointer、*(pointer+1)來表示它們之間的關係。這樣說很難理解，直接看下面例子。

*這個概念不太好理解，我原文是錯的，經臉書社團CS50中文討論區的網友指正後，已修改。

cs50x_w4_2.c

Pointer的功用

pointer的實際應用，就是它能夠在函式之間互相傳遞、修改資料。

假設你在主程式裡初始化變數 int a = 1;，然後另外寫一個函式，丟入a，函式會複製a的值，然後執行函式裡的程式，不會改變主程式內的變數a。如果我們使用pointer，它會直接指向該變數，函式就能直接更改它。講起來有點複雜，直接看看以下兩個例子。

在主程式外交換變數值

cs50x_w4_3.c

在函式間傳遞陣列

如果想要不使用指標，在函式間傳遞陣列，是做不到的，因為陣列不能直接複製。

cs50x_w4_4.c

使用指標時要小心的部分

如果你宣告指標如下：

int a, b, c; // 宣告a, b, c為int變數 

int* d, e, f; // 宣告d為int指標變數，e、f為int變數

很奇怪吧？照理說第二行，應該是要把d、e、f都宣告為int指標變數才是。但是C語言不是這麼認為的，它只會把d宣告為指標變數。

如果都要宣告成變數，請寫成下面這樣。

int* d, *e, *f;

另外，程式不允許你直接設一個pointer變數，但是卻沒有初始化，你如果一開始沒打算要初始化，最好先設為NULL。不然可能會產生不預期的行為。

int* a = NULL;

動態設定記憶體

malloc()會回傳指標，如果記憶體用完等理由，導致malloc()無法設定記憶體，會回傳NULL。

int* x = malloc(sizeof(int)); 

free(x); // 用完一定要記得釋放記憶體

開啟、讀取、寫入外部檔案

下列語法都在stdio.h裡。

fopen(檔案位置, 模式)，意思是file open。底下寫的ptr都是pointer的意思。

// r是read 

// a是appending，用於檔案內已經有內容，會在下方直接加上內容 

// w會覆寫上去 

FILE* ptr = fopen("file.txt", "r");

fclose(檔案指標)，意思是file close。

// 記得要關閉檔案

fclose(ptr);

fgetc(檔案指標)，意思是file get a character。另外還有一個類似的fgets()，可以讀取string。

cs50x_w4_5.c

fputc(要寫入的值, 檔案指標)，意思是file put a character；另外還有一個類似的fptts()，可以寫入string。至於fprintf()，可以用printf()寫入資料到檔案裡

cs50x_w4_6.c

fread(儲存區域指標, 尺寸, 數量, 檔案指標)，類似fgertc()，一次可以讀較多的資料。

// 一定要是在r模式 

// arr陣列丟入參數後，會自動轉成指標 

int arr[10]; fread(arr, sizeof(int), 10, ptr); 

//另一個例子 // 不一定要用陣列，用指標指向一個記憶體區域 

// arr2在這邊是指標 

double* arr2 = malloc(sizeof(double) * 80); 

fread(arr2, sizeof(double), 80, ptr); 

//第三個例子 

// c不是指標，所以要用&取址 

char c; fread(&c, sizeof(char), 1, ptr);

fwrite(儲存區域指標, 尺寸, 數量, 檔案指標)，是fread()的相反，一次寫入資料。

// 與fread()幾乎沒差別 int arr[10]; 

// 從ptr，寫入10個sizeof(int)大小的資料量，到arr裡 

fwrite(arr, sizeof(int), 10, ptr);

在本次作業裡有用到上述的某些函式，如果上面看不懂，沒關係，底下作業那邊會解釋。

程式如何在電腦內執行

我們的桌上型個人電腦、筆記型電腦等，都是由CPU、主機板、記憶體、硬碟組成。某些電腦會另外加裝顯示卡，以提高更好的畫面運算效果。所謂執行程式，意思是讀取硬碟的資料，放在記憶體裡，由CPU進行運算，連結這些硬體設備的則是主機板。今天的課程主要是談資料如何在被放在記憶體裡。

關於記憶體的知識，可見Lynn的DRAM、NAND Flash 最近貴到炸，你還搞不懂記憶體的差異嗎？

當stack與heap的資源被越佔越多，就會耗盡記憶體

上圖是記憶體儲存資料的結構，最上頭的位置會儲存C語言產生的二進位機器碼，你在終端機上輸入的./code_name，也是放在這裡。再來會有些全域變數，放這邊會增加程式執行的效率。

接著是heap，動態記憶體配置，例如我們在設定陣列時，通常都必須先給定記憶體容量，如int array[100];，意思是陣列含有100個int資料型別的記憶體區域。我們使用malloc()配置記憶體時，也是在這個區域，但是一定要記得手動釋放。底下為stack，它是靜態記憶體配置，例如我們在程式設定的區域變數，就會儲存在這裡。另外我們主程式int main()，以及各種函式，也都在這裡。

其他你在寫作業前最好知道的小撇步

二元運算子 bitwise operator

在你要寫「還原被刪除照片」的作業時，助教Brian會教你二元運算子。二元運算子的目的是用來計算二進位數。包含了：

• &：兩者為真即為真，因此兩者皆1則是1，兩者皆0則是0，有1有0也是0。
• |：兩者之一為真即為真，因此兩者皆1則是1，兩者皆0則是0，有1有0則是1。
• ^：一真一偽即為真，因此兩者皆1則是0，兩者皆0也是0，有1有0則是1。
• ~：取補數，將所有的位元 0 變 1，1 變 0。
• <<：左移，位元往左移。如0010變成0100。
• 右移，位元往右移。如0010變成0001。

在作業「還原被刪除照片」裡，會有一個邏輯運算如下，

(buffer[3] & 0xf0) == 0xe0

這句話的意思是：

在buffer陣列的第4個數值，與0xf0一起，轉成二進位數後，使用&二元運算子計算。只要buffer[3]介於0xe0~0xef之間，一律都會轉換成0xe0，如果buffer[3]不是介於0xe0~0xef之間，則會轉換成0x00~0xf0（只轉第二位數）。 轉換完成後，再與右邊的0xe0比較，如果相同，返回true，如果不同，返回false。

這裡先有一個概念，真就是1，偽就是0。

首先我們把16進位數轉成2進位數，如下：

0xe2 = 1110 0010 0xf0 = 1111 0000 0xe0 = 1110 0000

如果我們在程式裡表示(0xe2 & 0xf0)，&會把0xe2轉成0xe0。原理是在二進位模式下，&會把有1有0的位元都轉為0。兩者皆1則是1，兩者皆0則是0。然後你會很快地發現，從0xe0到0xef，一律都會轉為0xe0。

Magic!

作業

1. Filter

Filter這份作業挺簡單的，一部份原因也是因為我選簡單版本的關係啦。不過下載檔案後，會發現程式碼有點嚇人，一堆函式看不懂。不過不要緊張哦，慢慢地仔細看，有些不懂的跳過也沒關係，因為看不懂的部分應該都是在filter.c，而我們要寫的程式是在helpers.c，是在主程式以外的。

程式的目的是把照片轉成灰階、泛黃、鏡像、模糊，考驗的是操作陣列的技巧。

cs50x_w4_7.c

2. Recover

這份作業，我老實說不是我自己原創的。我看了網路上其他前輩的教學，然後試著自己寫一遍。大概有87%相似吧。

其實也不是難，而是我對於如何讀取檔案、儲存檔案，真的很不熟悉。這部分還需要多加強。

cs50x_w4_8.c

Happy coding!!!