Computer Science (哈佛CS50導讀)- 上

發表於 分類於 Disqus：

Computer Science50是哈佛大學的免費線上課程，沒有程式基礎的人也可以看完，網路有很多資源，就不詳細介紹了。

各種進位制

  • Binary
    世界上有1 0種人，一種是懂二進位的人，一種是不懂二進位的人。
  • Decimal
    0, 1, 2, 3, 4, 6, 7, 8, 9
  • Octal, Hex
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F

RGB

RGB一般稱為【色光三原色】，R（red）紅、G（green）綠、B（blue）藍，RGB的顏色階調為0-255
R, G, B 分別可以用兩位十六進位來表示:
⇒ #FFFFFF 表示白色，R（red）、G（green）、B（blue）都是最高色階255
⇒ #000000 表示黑色，R（red）、G（green）、B（blue）都是最低色階0
⇒ #FF0000 表示純紅色

Command line

Print Working Directory
List Segmant
Change Directory
MaKe DIRectory
ReMove
MoVe
CoPy
MANual

1
2
3
4
5
#include <stdio.h>
int main(viod) {
  printf("hello world!");
}

$ make hello
$ ./ helle

Compiler

  • Preprcessing
    處理#include
  • Compilier
    C code -> Assembly code
  • Assembling
    Assembly code -> Machine code
  • Linding
    把你的code跟系統的code連結起來

儲存型態

  • Binary 4bit
    0000 0001 …
  • 負數(Overflow)
    把所有bit反轉+1就是負數!
  • 32bit 最大元素是2^31 - 1
    2147483647

C++ |搜尋法

  • 線性搜尋
    一個一個搜

  • 二分搜尋法

必須是已經排序過的數列

1
2
3
4
5
6
7
8
9
10
11
12
bool seach(int values, int values[], int n) {
  while(L <= R) {
    M = (L+R)/2;
    if (values[M] == values) return true;
    if (values[M] > values) {
      R = M - 1;
    } else {
      L = M + 1;
    }
  }
  return false;
}

C++ |排序法

  • 選擇排序法
    不斷的找最小值

  • 泡沫排序法
    倆倆比較，順序錯了就交換上來

1
2
3
4
5
6
7
8
void sort(int values[], int n) {
  for(int i=0; i<n; i++) {
    if (values[j] > values[i]) {
      swap(&values[j], &values{j+1);
      }
    }
  }
}
  • 插入排序法

像撲克牌一樣

1
2
3
4
5
6
7
8
9
10
11
viod insertion_sort(int values[], int n) {
  for(int i=1; i<n; i++) {
    int number = values[i];
    int position = i;
    while(position >=0 && values{position-1] > number) {{
      values[position] = values[position - 1]'
      position--;
    }
    values[position] = number;
  }
}
  • 合併排序法

左右兩邊排好之後再合併起來

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
void merge(int values[], int start, int middle, int end) {
  int temp[end - start + 1];
  int left = start;
  int right = middle + 1;
  int nowIndex = 0;

  while (left <= middle && right <= end) {
    if (values[left] <= values[right]) {
      temp[nowIndex] = values[left];
      left++;
    } else {
      temp[nowIndex] = values[right];
      right++;
    {
    nowIndex++;
  }
  while(left <= middle) {
    temp[nowIndex] = values[left];
    nowIndex++;
    left++;
  }
  while(right <= end) {
    temp[nowIndex] = values[right];
    nowIndex++;
    right++;
  }

  for(int i=start; i<=end; i++) {
    values[i] = temp[i-start];
  }
}

void merge_sort(int values[], int start, int end) {
  if (end > start) {
    int middle = (start + end) / 2;
    merge_sort(values, start, middle);
    merge_sort(values, middle+1, end);
    merge(values, start, middle, end);
  }
void sort(int values[], int n) {
  merge_sort(values, 0, n-1);
}
}

  • 快速排序法

找中值，左邊都比值小且右邊都比值大那值就在正確位子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int partition(int values[], int start, int end) {
  int splitIndex = start + 1;
  for(int i = start+1; i<=end; i++) {
    if (values[i] < pivot) {
      swap(&values[splitIndex], );
      splitIndex++;
    }
  }
  swap(&values[splitIndex - 1], &values[start]);
  return splitIndex - 1;
}

void quick_sort(int values[], inr start, int end) {
  if (end > start) {
    int middle = partition(values, start, end);
    quick_sort(values, start, end);
    quick_sort(values, middle + 1, end);
}

void sort(int values[], int n) {
  quick_sort(values, 0, n-1);

C++ | 指標(pointer)

  • 一種特殊的資料型態，存的是記憶體的位子。
1
2
3
4
5
6
7
8
9
10
int a = 20;
int* ptr = &a;
int** p = &ptr;

ptr -> 0x00 // address of a
*ptr -> 20 // values of a

p -> 0x04 // address of ptr
*p -> 0x00 // values of ptr, address of a
**p -> 20 // values of a

程式底層運作(Heap ane Steak)

  • Heap
    動態(malloc)取得的記憶體會在這裡

  • Steak
    儲存function, local, variable的地方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 因為記憶體位子不一樣，所以不會交換
viod swap(int a, int b){
  int temp = a;
  a = b;
  b = tenp;
}
int main() {
  int x = 10;
  int y = 5;
  swap(x, y);
  printf("%d %d\n", x, y);
}
// 第10行應該改成 -> swap(&x, &y)
```c

- Buffer overflow
沒有仔細檢查輸入，導致攻擊者可構出造"執行任意程式碼"的payload

## 結構(Structure)

拿來讀取 **有結構** 的東西

```c
typedef structure {
  string name;
  string dorm;
}student;

圖片解析

  • 負片效果
1
2
3
triple.rabtGreen = abs(255 - triple.rgbtGreen);
triple.rabtBlue = abs(255 - triple.rgbtBlue);
triple.rabtRed = abs(255 - triple.rgbtRed);
  • 黑白效果
1
2
3
4
int avg = (triple.rabtGreen + triple.rabtBlue + triple.rabtRed) / 3;
triple.rabtGreen = avg;
triple.rabtBlue = avg;
triple.rabtRed = avg;

鏈結串列(Linked list)

  • 優點：
    • 新增/刪除資料較Array簡單
    • 資料數量可以是動態的，不會有resize問題
  • 缺點：
    • 搜尋需要從頭開始找起，時間複雜度為O(N)
    • 需要額外記憶體來儲存pointer

佇列(Queue)

Queue是具有First-In-First-Out的特徵

  • 應用:
    CPU、應表機、網站等一次只能執行一個的需求，因此需要有Queue來安排

堆疊(Stack)

Stack 是具有 Last-In-First-Out 的資料結構

  • 應用:
    • 編輯器的undo
    • 遊覽器的上一頁

網路相關知識

  • IP位置
    每台可以上網的電腦，都會有一個IP位置，都是由4個數字組成範圍是0~255，例如:101.13.113.80，四個數字方法叫做IPv4，因應更多IP位置有了IPv6。
  • 域名(Domain)
    域名就是我們常用的網址，比起IP可讀且好記，像是Google.com，必須透過DNS(Domain Name System)才能知道確切位置。
  • Host
    域名必須跟域名供應商買，才能確保你連線時連到正確位置，但可以在自己電腦上調整設定檔，像是把127.0.0.1對到localhost這個網址，在自己電腦上建立DNS紀錄，只有在自己電腦上有效，這也是為什麼測試環境沒有設host就連不上的緣故。
  • VPN(Virtual Private Network)
    有些服務會鎖IP，只開放特定IP存取，為了提升安全性，讓一些系統只能從公司內部登入，像是大陸的”翻牆”軟體。
  • Status Code
    • 200 &rArr; OK
    • 404 &rArr; ont found
    • 500 &rArr; internet server error
  • 網頁(HTML)
    全名是 超文件標示語言(Hyper Text Markup Language)
    分成三部分:
內容與架構 HTML ⇒ 骨架
樣式 CSS ⇒ 外觀
程式碼 Javascript ⇒ 肌肉 
1
2
3
4
5
6
7
<html>
  <head>
  </head>
  <body>
    <p>Hello World!</p>
  </body>
</html>

登入機制

發給你一個識別證，你把識別證存起來，之後戴上就好，瀏覽器提供一個地方叫做”Cookie”，可以讓伺服器想要的資訊放這裡。
存識別證的地方 &rArr; Cookie
對照訪客名冊 &rArr; Session

Ref