Computer Science (哈佛CS50導讀)- 上

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