CS50 wk4 課程筆記和作業心得

註：本課程筆記參考CS50官方課程和官方notes。

課程筆記：

1.image-RGB

圖片是怎麼存儲的呢？圖片是無數個小小的格子。像是電視的4k是3840×2160個格子，vcd畫面是352×240個格子。

每個格子由R(red)，G(green)，和B（blue）組成，不同的數值形成不同的顏色。

• white, with R: 255, G: 255, and B: 255, and #FFFFFF
• red, with R: 255, G: 0, and B: 0, and #FF0000
• green, with R: 0, G: 255, and B: 0, and #00FF00
• blue, with R: 0, G: 0, and B: 255, and #0000FF

2.hexadecimal

電腦的memory裡大部分都是使用十六進制，原因是：

1）16是2的4次方，所以一個十六進制的數字可以用四個二進制來表示。比如0為0000，f為1111。

2）提高可讀性，比如32 bites 的integer用十六進制的話可以縮減為8位。

3.pointer

pointer也是一種數據類型，可以把pointer看作是地址，pointer一般都是用十六進制的int表示。

int n = 50;
int *p = &n; //int *表示宣告p的類型是地址，地址是一串十六進制表示的數字。&n表示取得n的地址。
printf("%p\n", p);//%p是地址的format code，像%i一樣。
printf("%i\n", *p);//*p指的是到p這個地址取存在裡面的東西，因為p已經在int *p裡宣告過了是地址。

4.string

string是一串char的array，以nul結尾。array裡的每個char可以用s[0], s[1], s[2]等表示，每個char都有自己的地址&s[0]，&s[1]，&s[2]等。

string s = "HI!";
char *s = "HI!";

string s即是這一串字母裡面第一個字母的位置。

char *s = "HI!";
char *p = &s[0];
printf("%p\n", p);
printf("%p\n", s);
//p和s的地址一樣。

第二個字母的位置即是第一個字母的位置+1，第三個字母是第一個字母位置加2，以此類推。

#include <stdio.h>
int main(void)
{
    char *s = "HI!";
    printf("%p\n", s);
    printf("%p\n", &s[0]);
    printf("%p\n", &s[1]);
    printf("%p\n", &s[2]);
    printf("%p\n", &s[3]);
}
//結果：
$ make address
$ ./address
0x402004
0x402004
0x402005
0x402006
0x402007

5.Pointer arithmetic

地址是十六進制的int，在array裡每個元素的位置是連續排列的，所以可以用簡單的加法取得每個位置的值。第一個元素是+0,第二個元素是+1，第三個元素是加2，等等。此處不用考慮元素自己的bytes，因為complier知道把每個元素看成是一個單元。比如int是4個bytes，char是1個byte，但是取第二個元素的位置都是+1，而不考慮本身的元素大小。

下面這個例子並沒有事先宣告int *，而是直接用*去地址取值，是因為array本身是地址，而且是第一個元素的地址。

#include <stdio.h>
int main(void)
{
    int numbers[] = {4, 6, 8, 2, 7, 5, 0};
    printf("%i\n", *numbers);
    printf("%i\n", *(numbers + 1));
    printf("%i\n", *(numbers + 2));
    printf("%i\n", *(numbers + 3));
    printf("%i\n", *(numbers + 4));
    printf("%i\n", *(numbers + 5));
    printf("%i\n", *(numbers + 6));
}

6.string的比較

string不能像int和char一樣比較，是因為string是第一個元素的地址。即使兩個地址裡的內容一樣，地址也是不一樣的。

#include <cs50.h>
#include <stdio.h>
int main(void)
{
    char *s = get_string("s: ");
    char *t = get_string("t: ");
    printf("%p\n", s);
    printf("%p\n", t);
}

$ make compare
$ ./compare
s: HI!
t: HI!
0x19e06b0
0x19e06f0

在memory裡是這麼表示的。

7.string的copy

string是第一個元素的地址，所以下面的string t = s; 表示複製了s的地址，而不是地址裡的內容。

int main(void)
{
    string s = get_string("s: ");
    string t = s;
    t[0] = toupper(t[0]);
    printf("s: %s\n", s);
    printf("t: %s\n", t);
}

$ make copy
$ ./copy
s: hi!
s: Hi!
t: Hi!

8.memory allocation.

copy string三步驟：使用malloc分配地址；strcopy 或for loop 複製每個字母包括nul；free剛剛分配的地址 。

#include <cs50.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void)
{
    char *s = get_string("s: ");
    char *t = malloc(strlen(s) + 1);
//檢查RAM還夠不夠
    if (t == NULL)
    {
        return 1;
    }
    strcpy(t, s);
    if (strlen(t) > 0) 
    {
        t[0] = toupper(t[0]);
    }
    printf("s: %s\n", s);
    printf("t: %s\n", t);
    free(t);
}

9.valgrind

valgrind 是可以用檢查有關memory bug的命令行工具，這些錯誤用debugger檢查不出來。

10. garbage values

當宣告一個變數的時候，要同時給這個變數一個值，不然電腦就會從RAM裡亂找之前的數據（垃圾數據）。

11.swap

如果swap是在主程序（main）裡的話，是可以成功交換的。

#include <stdio.h>
void swap(int a, int b);
int main(void)
{
    int x = 1;
    int y = 2;
    printf("x is %i, y is %i\n", x, y);
    swap(x, y);
    printf("x is %i, y is %i\n", x, y);
}
void swap(int a, int b)
{
    printf("a is %i, b is %i\n", a, b);
    int tmp = a;
    a = b;
    b = tmp;
    printf("a is %i, b is %i\n", a, b);
}

如果swap在function裡，此function運行完成後會被清除，或者變成garbage value。（stack採取先進後出，此程式先是運行main，然後是運行swap，所以swap運行完後，stack存儲區會釋放。）

所以，正確的swap其實可以利用pointer來完成，swap地址，然後swap地址裡的取值。

#include <stdio.h>
void swap(int *a, int *b);
int main(void)
{
    int x = 1;
    int y = 2;
    printf("x is %i, y is %i\n", x, y);
    swap(&x, &y);
    printf("x is %i, y is %i\n", x, y);
}
void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

12.heap和stack，運行程式的時候RAM是怎麼分配的

1）machine code

machine code 是 程式compiled過產生的binary code。

2）global variable

接下來區塊是存儲globals variable。globals variable是程式裡不同的子程式需要多次使用的variable。確實需要多次用到才使用global variable，不然就浪費了這一部分的存儲空間。

當程式全部運行結束的時候，global variable會被自動清空。

3）heap

heap是預留的存儲區，給dynamic memory allocation專用，存儲空間比較不受限制，算是一個巨大容量的存儲池。

可以使用malloc來索取heap裡任意的存儲區，然後被索取的存儲區就會被預留。如果heap存儲區不夠的話，會返回NULL。當用完這個存儲區以後，需要使用free來把被預留的存儲區釋放。

heap存儲區是從上到下使用，如果malloc使用太多的heap的話，就會產生heap overflow的問題。

4）stack

stack是各種function（包括main）和各種local variable運行的時候使用的存儲區。如果有三個function A, B和C，A是main funtion會call B， B 會call C，這個時候stack的最底層存儲的是function A和裡面的local variable，然後往上存儲的function B和裡面的local variable，再往上是function C和裡面的local variable。當function C運行的時候，function A 和B是處於暫停狀態。當function C return後，返回值到function B，function C用完馬上自行釋放所佔用stack存儲區。然後換function B運行，return後自動釋放所佔用的stack，換function A運行，最後function A 運行完，返回結果，此程式佔用stack全部釋放。

stack由電腦事先預留的空間，通常比heap小很多。

當recursion不斷的循環，或者使用多重nested function，就有可能會產生stack overflow的問題。

詳細講解：Pointers and dynamic memory – stack vs heap

13.scanf

把輸入的值存到變數的地址。

#include <stdio.h>
int main(void)
{
    int x;
    printf("x: ");
    scanf("%i", &x);
    printf("x: %i\n", x);
}

#include <stdio.h>
int main(void)
{
    char *s;
    printf("s: ");
    scanf("%s", s);
    printf("s: %s\n", s);
}
//此處不用存到string的地址，因為string本身就是第一個char的地址。

14.defining custom types

eg：typedef uint8_t BYTE;

15.files

// Saves names and numbers to a CSV file
  
#include <cs50.h>
#include <stdio.h>
#include <string.h>
  
int main(void)
{
    // Open CSV file
    FILE *file = fopen("phonebook.csv", "a");
    if (!file)
    {
        return 1;
    }
  
    // Get name and number
    string name = get_string("Name: ");
    string number = get_string("Number: ");
  
    // Print to file
    fprintf(file, "%s,%s\n", name, number);
  
    // Close file
    fclose(file);
}

作業心得：

1.filter-less

前三個function好寫，第四個用的笨辦法硬寫來解題，寫完後覺得自己的方法太笨，google了下其他人的思路，發現用nested for loop 加上 continue也可以解題。所以複習了下break和continue的用法，最後用4層loop和continue解題。

ps:發現sum和count在程式裡的不同位置也會影響結果。

比如下圖：把sum和count放在最前面沒被包在loop裡面是錯誤的。

比如下圖：只放在第一個i loop裡面也是錯誤的。

最後，放在i loop 後的 j loop裡面才是正確的。所以寫作業真的可以幫助釐清問題。

總共花費5個小時。

2.recover

作業是從頭開始寫一個程式用來找回照相機裡被誤刪除的照片。

這個作業跨度很大，感覺比tideman還難，剛開始一點頭緒也沒有。

把課程視頻和short重新看了一遍，又看了些關於file 教學的視頻，再看了好幾遍hint和walkthrough，勉強寫出程式，但是就是無法成功解決問題。

卡了四天，瀏覽FB群組裡別人問的問題和解答（不看code），發現自己也有如下的問題：

1）fread開了2次。

while的條件裡已經開過fread了，不需要再重新開第二次。

2)Segmentation fault (core dumped)

使用debug50找不出來問題， 用 valgrind ./recover結果顯示0 errors from 0 contexts。

最後發現問題在file的open和close上面。

3）不用walkthrough的步驟也可以解題

我用walkthrough的邏輯試了很多次，可以compile但是不可以運行。

最後還是解不開，我註冊了stackoverflow網站，準備把我的code PO上去問問題。突然又想重新按照自己的想法重寫一遍if/else，沒想到最後一次./recover card.raw 竟然成功了。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>
typedef uint8_t BYTE;
int main(int argc, char *argv[])
{
    ////accept exactly one command-line argument
    if(argc != 2)
    {
        printf("Usage: ./recover IMAGE\n");
        return 1;
    }
        FILE *f = fopen(argv[1],"r");
        if (!f)
        {
        return 1;
        }
    char filename[8];
    int counter=0;
    BYTE buffer[512];
    FILE *img=NULL;
    while (fread(buffer, 1, 512, f) == 512)
    {
        //if start of new JPEG
        if(buffer[0] == 0xff && buffer[1] == 0xd8 && buffer[2] == 0xff && (buffer[3] & 0xf0) == 0xe0)
        {
            sprintf(filename,"%03i.jpg",counter);
            img=fopen(filename,"w");
            fwrite(buffer,1,512, img);
            counter++;
            fclose(img);
        }
        else
        {if (counter>0)
            {
            img=fopen(filename,"a");
            fwrite(buffer,1,512, img);
            fclose(img);
            }
        }
    }
fclose(f);
return 0;
}

其他：

1.toggl

這週開始使用toggl這個免費時間追蹤軟體，把CS50當做一個大項目，每週的課程和每個pset和lab當作一個小項目，這樣可以清楚的知道時間去哪兒了，也可以幫助自己完成這個項目。

2.據說wk3/4/5是最容易放棄的時候，一方面是因為作業太難，另一方面是新鮮的感覺消失了。所以，即使作業卡關，也還是會提醒自己接著完成課程。