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是最容易放棄的時候,一方面是因為作業太難,另一方面是新鮮的感覺消失了。所以,即使作業卡關,也還是會提醒自己接著完成課程。

Leave a Comment

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *