# 鯊鯊的CS50筆記
# 課程來源及資訊
哈佛大學2023年CS50課程 made by FreeCodeCamp
https://youtu.be/LfaMVlDaQ24

講師:David J. Malan

# 時間軸與章節目錄
<!--
註記：
MD語法參考：
https://markdown.tw/
下列用法：
把常用的TAG設置類似於變數，使其可以重複使用，但設置時不會顯示於畫面
時分秒註記：
https://s4880069.pixnet.net/blog/post/37327802
善用FootNote來幫助整理來源連結，以及減少不必要資訊汙染原始碼畫面
https://hackmd.io/@hackmd/blog-tw/https%3A%2F%2Fhackmd.io%2F%40hackmd%2Ffootnote
記得務必拆分筆記，並善用超連結將筆記關聯，以免HackMD字數突破最大上限，以及導致畫面載入速度問題
-->

[回到目錄]: #時間軸與章節目錄
[Lecture 0 - Scratch]: #Lecture-0---Scratch
[Lecture 1 - C]: #Lecture-1---C
[Lecture 2 - Arrays]: #Lecture-2---Arrays
[Lecture 3 - Algorithms]: #Lecture-3---Algorithms
[Lecture 4 - Memory]: #Lecture-4---Memory
[Lecture 5 - Data Structures]: #Lecture-5---Data-Structures
[Lecture 6 - Python]: #Lecture-6---Python
[Lecture 7 - SQL]: #Lecture-7---SQL
[Lecture 8 - HTML, CSS, JavaScript]: #Lecture-8---HTML,-CSS,-JavaScript
[Lecture 9 - Flask]: #Lecture-9---Flask
[Lecture 10 - Emoji]: #Lecture-10---Emoji
[Cybersecurity]: #Cybersecurity

課程內容:
(00:00:00) [Lecture 0 - Scratch]
(02:05:47) [Lecture 1 - C]
(04:35:19) [Lecture 2 - Arrays]
(06:59:38) [Lecture 3 - Algorithms]
(09:01:13) [Lecture 4 - Memory]
(11:26:33) [Lecture 5 - Data Structures]
(13:42:44) [Lecture 6 - Python]
(15:58:02) [Lecture 7 - SQL]
(18:18:30) [Lecture 8 - HTML, CSS, JavaScript]
(20:58:14) [Lecture 9 - Flask]
(23:19:07) [Lecture 10 - Emoji]
(25:05:28) [Cybersecurity]

* 備忘列表
1. 筆記頁面拆分，按照章節，可之後做
* 目的：使整體筆記長度適中，並適度利用超連結
* 筆記太長了
* 筆記太長了
* 筆記太長了(因為真的很長所以講三次)
2. 跳轉功能：
* 運用`(顯示名稱)[跳轉章節名稱]`或tag(見第4點)撰寫MD語法以利於當頁跳轉
* 於各章節起點增加[回到目錄]超連結方便跳轉至起點
3. 章節階層拆更細：
* 將章節拆至更小的階層，使目錄井然有序，多利用`###`以下階層來標出小章節
4. 善用TAG:
* 多利用`[tag名稱]: "此處可為標題或超連結"`來作為跳轉捷徑
5. 標題簡化：
* 標題只留名稱，網址於內文中，使其不干擾閱讀與目錄閱覽，範例如[#二進制](#二進制)
6. Youtube超連結後面參數改使用`#`，採用時分秒
7. HackMD還有特有的MD用法，使用`:::`包起來的區域能強調，例如：

:::success
成功
:::

:::info
資訊區
:::

:::warning
警告區
:::

:::danger
危險區
:::

:::spoiler
這是劇透，艾斯變成甜甜圈了
:::

# Lecture 0 - Scratch

[回到目錄]

## [二進制](https://youtu.be/LfaMVlDaQ24?t=1162)

transistor電晶體:電腦裡控制01的小燈泡

unary:一元運算
binary:二進制

binary digit => bi(~~nary digi~~)t => bit:一個01開關稱為bit

decimal十進制


二進制

byte:八個bit
byte最小是00000000 代表 0
byte最大是11111111 代表 255

## [ASCII](https://youtu.be/LfaMVlDaQ24?t=2082)

電腦用65(01000001)來代表A、66代表B...

ASCII是一個字符跟數字(byte)的對應系統

電腦會根據使用情境 在需要解讀文字訊息時用這個對照表把01訊息轉換(interpret)成字符 在需要表示數字時(例如Excel) 會將01訊息解讀為數字 在需要表示顏色時(例如Photoshop) 則會將01訊息轉換成顏色

透過對照表 不同的系統/電腦之間得以溝通

ASCII只有使用一個byte(8 bit) 也就是只有0-255的256種變化 只夠英文字符使用而已 => 解決方法:Unicode

## [Unicode](https://youtu.be/LfaMVlDaQ24?t=2481)

Unicode使用了四個byte(32 bit) 可以包含各國語言的字符跟Emoji符號

01訊號

轉換成數字

轉換成Emoji

因為Emoji會被視為字符而不是圖片 所以不同系統或程式(例如ios/android)會因為使用的字體(font)不同 而使顯示的表情符號稍微不同 也可能會因為版本不同無法支援而導致顯示失敗

透過原先的表情符號加上特定的bit組合 可以顯示出同一個表情符號的不同膚色版本 甚至是組合出複雜的表情符號

## [RGB](https://youtu.be/LfaMVlDaQ24?t=3023)

圖片中的每一個像素pixel都需要3個bytes(24 bits)分別代表RGB來顯示出對應的顏色


透過快速切換圖片便可以得到影片 透過量化頻率、音量、時間長度...等資訊便可以得到聲音訊息

## [演算法](https://youtu.be/LfaMVlDaQ24?t=3370)

將輸入轉換為輸出是一個抽象化的過程
通過不同的標準/規範可以呈現不同的檔案類型

abstraction:抽象化
意思是將資料與程式 透過簡化的語意來代替底層的複雜實作細節 以減少程式的複雜度 使得程式設計師可以專注在處理程式表層的目標或過程 例如車子就是一種抽象化 我們不需要知道引擎是如何運作的 我們只要知道如何從A點開到B點就可以了

電腦使用的抽象化叫做演算法(algorithm)

演算法舉例:如何在電話簿中快速搜尋到人名?

第一種方法就是從第一頁開始一頁一頁找 正確但缺乏效率

第二種方法是從第一頁開始每兩頁找一次 如果發現超過了就回頭找跳掉的那一頁

第三種方法則是二分法 先從中間位置開始找 然後看目標在左邊還是右邊 再從剩下的中間位置找一次 重複這個動作直到找到目標

縱軸是解決問題的時間 橫軸是問題的大小
第一種方法是紅線 第二種方法是黃線 但都是直線 第三種方法是綠線

pseudocode:偽代碼
其中動詞就是程式中的函數function

if/else就是條件conditional

這些是布林表達式Boolean expression 指答案是"是/否"的問題

這些是迴圈loop

functions函數
arguments參數
return values回傳值
conditionals條件
Boolean expressions布林表達式
loops迴圈
variables變數

## [Scratch](https://youtu.be/LfaMVlDaQ24?t=4338)
雲端程式伺服器連結:https://scratch.mit.edu/

裡面有教學

block area 元素區域

code area 程式區域

sprite area 腳色區域

stage 舞台

scratch腳色存在於舞台這個二維空間內

綠色旗子代表執行 紅色八邊形代表停止
按下執行會觸發一個事件(event) 這個事件就是指say這個動作 而這個動作又通過白色的輸入框接收了"hello, world"這個參數(argument)

輸入 => 演算法 => 輸出

輸入(參數:"hello, world") => 演算法(函數:say) => 輸出(函數副作用:動畫)
函數副作用(side effect):通常指函數的視覺化結果

範例演示的部分很有趣 但對實際寫程式幫助不大 主要就是玩小遊戲跟解釋if/else之類的概念 建議自己看

# Lecture 1 - C

[回到目錄]

## [Source Code](https://youtu.be/LfaMVlDaQ24?t=7684)

Source Code:原始碼 就是我們寫的程式語言
Machine Code:機器碼 電腦理解的01二進制指令

原始碼 => 編譯器(Compiler) => 機器碼

好程式的三要素:正確性 設計 風格
=> 正確性:程式要可以正確執行
=> 設計:好的設計可以提高執行效率 增加易讀性跟可擴展性
=> 風格:好的風格有助於提高代碼的可讀性 方便其他人理解

課程使用線上版的VS Code 需要用GitHub帳號登入
code.cs50.io

Terminal:終端機 用來提供Commend Line Interface(CLI)命令行界面 <=> Graphical User Interface(GUI)圖形使用者界面

我們創造了原始碼檔案hello.c => `code hello.c`
呼叫編譯器把hello.c轉換成一個電腦可以理解的機器碼程式hello => `make hello`
最後讓電腦去執行hello => `./hello` (./代表在當前的資料夾裡面)

Syntax highlighting:語法突顯 指不同的元素用不同的顏色顯示以提高可讀性

類似Scratch的方塊顏色系統

如果原始碼錯了 編譯器無法將其轉換成機器碼 就會顯示錯誤

Escape Sequence逸出序列 \n告訴程式換下一行

沒有的話 會顯示在同一行

不在同一行會直接不能編譯

`#include <stdio.h>`:預處理指令 告訴編譯器在編譯過程中將header file(標頭文件)包含進來 這個stdio.h是一個程式庫(library) 其中包含了一些標準的輸入和輸出函數 例如printf

課程有專用的程式庫cs50.h 也有裡面所有函數的使用說明書
manual.cs50.io

透過`get_string()`可以取得取得使用者的輸入 並透過`answer =`來取得回傳值(return value) 而且需要用`string`來宣告answer的型別

這樣程式會直接印出hello, answer

%s代表要插入字串的佔位符


如果真的要印出"%" 就要打兩個%

## [conditional](https://youtu.be/LfaMVlDaQ24?t=10762)

if

if + else

if + else if + else

大小寫是有區別的 ""代表字串string ''代表字符char

||代表or

## [variables變數](https://youtu.be/LfaMVlDaQ24?t=12202)

## [loops迴圈](https://youtu.be/LfaMVlDaQ24?t=12392)

while

慣用用法是從0開始數到小於目標數字

for

forever loop
只有0是false 其他整數都是true 也可以直接輸入true

如果不小心執行了無限迴圈 可以按下 ctrl + c 來中斷

## [Linux](https://youtu.be/LfaMVlDaQ24?t=13347)

常見指令

ls:list 會列出所有的檔案

mv 把hello重新命名hello.c

cd 移到特定的資料夾內
必須先進入pset1資料夾 才能使用mario這個檔案

加上const之後可以保護變數被修改

檢查n是不是大於1

加上註解

函數化


C跟html一樣都是從上往下讀 如果沒有先在前面聲明函數 而是直接把函數寫在主程式下面的話 程式會找不到函數 (C#的編譯器採用兩階段編譯的方式 首先進行編譯 然後進行連接 這樣允許你在前面引用後面定義的函數)

## [計算機](https://youtu.be/LfaMVlDaQ24?t=15487)

"%i\n" 是格式化字串(format code) 它告訴printf在這個位置插入一個整數(%i)並在之後插入換行符(\n)

輸入大數字的時候會爆掉

原因:記憶體RAM裡面的空間有限

C語言中通常使用32bits來表示一個整數 理論上最小值是0 最大值是2的32次方減1 也就是4294967295

但現實中因為需要涵蓋正負數 第一個bit要被拿來表示正負號 所以實際上的最大值是2147483647 最小值是-2147483648 此時正數的範圍是0到2的31次方減1 而負數的範圍是-1到2的31次方 (因為正數範圍需要包含0 所以正數的最大值需要減一 而負數範圍不需要重複包含0 直接從-1開始就好 所以負數的最小值不需要減一)

超過整數大小限制時稱為integer overflow (整數溢出)

以3個bits舉例 正常情況下最多數到7

如果想要數到8 二進制應該要從111變成1000 但是你的電腦只能存3個bit 1000會被記成000 所以7+1後不會變成8 而是變回0

解決方法:把int改成long %i也要改成%li

long的最大值可以數到9223372036854775807

## [truncation](https://youtu.be/LfaMVlDaQ24?t=15922)

1除3在數學上應該得到0.333... 但整數int無法顯示出小數 結果會被截斷為整數部分 並丟棄小數部分 所以得到的結果是0 這種截斷狀況被稱為truncation (截斷)

應該改使用float浮點數 但這段程式中x跟y依然被視為整數 所以計算時就被截斷了 就算把結果轉換成浮點數也沒用

此時需要type casting (轉換型別) 把long轉換成float 才能保證計算結果不被截斷

## [floating-point imprecision](https://youtu.be/LfaMVlDaQ24?t=16165)

但此時又會出現新的問題 floating-point imprecision (浮點數不準確性)
跟整數的大小有上限一樣 浮點數的準確性也有上限

.20代表指定小數部分的位數為20位 此時結果又壞掉了 因為浮點數也是用有限的位元數來表示的 無法精確地表示所有的數值 尤其是無窮小數或無窮循環小數

改善方法:改用double (雙精度浮點數) double (通常64bits) 用了比float (通常32bits) 多一倍的bits來儲存資料 所以有更高的精度 但結果還是不完美

早期許多電腦由於容量跟成本問題 通常只用最後兩位來紀錄年份 所以從1999進入2000年時 因為電腦無法分辨2000跟1900 (對電腦來說都是00) 所以會錯把2000當成1900

事實上 在2038年1月19日也會遇到一樣的問題 因為現在的時間表示法是透過使用32bits的int來紀錄從1970年1月1日開始經過的秒數 但是在2038年1月19日這一天會用完32bits 並可能出現overflow把時間倒退回1901年12月13日

# Lecture 2 - Arrays

[回到目錄]

## [cipher text](https://youtu.be/LfaMVlDaQ24?t=16812)

經過加密 (encryption) 的文字稱為cipher text (密文)

這個`make hello`中的make其實不是真的編譯器 而是一個把呼叫編譯器的過程自動化的程式

編譯器有很多個 我們程式中使用的C語言編譯器叫做clang 還有另一個常見的C語言編譯器叫做GCC

如果直接呼叫clang (`clang hello.c`)
生成檔案的預設名稱都是a.out
所以必須另外將其重新命名為hello (`mv a.out hello`)

因為要兩個步驟很麻煩 所以這時就要使用command line arguments (命令列參數)

在`clang -o hello hello.c`中 -o代表要改變預設的輸出檔案名稱 hello是新的檔案名稱 合起來就是告訴編譯器要生成一個名為hello的可執行文件 這一行就是`make hello`的原型

雖然已經加入cs50.h了 但clang還是找不到cs50.h中的get_string()

使用命令列參數的話必須加上`-lcs50`指令才能正確引入程式庫 其中-l代表連結 (link) 指定的程式庫 如果使用`make hello`指令的話就會自動處理這些東西

實際上編譯的過程包括了四個步驟
Preprocessing 預處理
Compiling 編譯
Assembling 組合
Linking 連結

## [Preprocessing](https://youtu.be/LfaMVlDaQ24?t=17732)

用#開頭代表這些部分跟程式的其他內容不同 而這些部分需要預處理 也就是在初始化的時候就要被分析

這些標頭文件 (header file) 通常被存放在一個特定的資料夾中 (例如/usr/include) 當程式在編譯過程中遇到#include時 就會去資料夾中尋找對應的檔案 並且將檔案內容插入到#include的位置上

#include的部分會被取代為函數的原型
`printf(string format, ...)`中 ...代表不定數量個參數

## [Compiling](https://youtu.be/LfaMVlDaQ24?t=18046)

到這一步時 程式應該已經展開預處理的部分了

此時編譯器會把C語言編譯成這樣的組合語言 (Assembly language) 組合語言是一種低階的程式語言 接近機器碼的表達方式 但同時比機器碼更容易理解。

這些是呼叫的函數

這些是指令 (instructions) 負責告訴CPU如何執行資料的移動、加法、減法...

## [Assembling](https://youtu.be/LfaMVlDaQ24?t=18201)

到這一步時 編譯器會把之前看到的組合語言轉換成機器碼

## [Linking](https://youtu.be/LfaMVlDaQ24?t=18235)

此時這些機器碼只有我們寫的程式內容 所以需要結合被引用的檔案 並連結 (link) 到我們的程式中 也就是把我們程式的01機器碼加上cs50.h的01機器碼 再加上stdio.h的01機器碼

## [decompiling](https://youtu.be/LfaMVlDaQ24?t=18623)

反編譯就是把機器碼轉換回原始碼 可能被用來逆向工程竊取智慧財產權 但其實反編譯後其實無法回復到原始的原始碼 因為變數名稱並不會被儲存在機器碼裡面 也沒有辦法分辨原始碼中是使用哪一種迴圈 因為不同迴圈的效果對電腦來說都一樣 也就是說在編譯過程中訊息的丟失 限制了反編譯的準確性和可靠性

## [debugging](https://youtu.be/LfaMVlDaQ24?t=18820)

第一個bug真的是一隻導致錯誤的蟲蟲

第一個方法:printf
透過printf把值印出來檢查

第二個方法:debugger
先下中斷點 (break point) 然後在終端機輸入debug50 ./buggy0

程式執行到中斷點時會被暫停 所有變數的值會被顯示在左邊
step over (f10) 會跳過函數 step into (f11) 會進入函數

第三個方法:rubber duck
不要盯著程式 試著跟黃色小鴨說話 實際把程式唸出來 可能就會發現問題了

## [int](https://youtu.be/LfaMVlDaQ24?t=20328)

常見型別跟其佔用的空間大小

記憶體裡面可以儲存許多bytes

假設一個方塊代表一個byte

整數的準確性不夠高

改成用float 只要算式中有一個精度更高的數值型別 算式就會用這個型別計算

也可以用轉換型別的方式改成float

記憶體中需要4個bytes來儲存每一個數字

轉換成二進制就是這樣

但這樣不是一個好設計 當需要更多數值時 就要不斷新增變數 程式碼也會一直增加
解決方法:array (陣列)

改成陣列寫法

改成動態取得數值

還可以再改成迴圈

此時記憶體裡面是這樣 array可以很好的組織和處理多個相似的數據

## [magic number](https://youtu.be/LfaMVlDaQ24?t=21589)

3重複出現了兩次 因為陣列的大小不一定永遠是3 這樣直接寫死在程式裡的數值可能會因為改了一個忘記改另一個而導致問題 這種莫名其妙出現的數字就是魔法數字

改成宣告一個常數N就可以了

但此時average()裡面還有一個魔法數字

改成也使用常數N

但最好把average()變獨立 也就是不依賴外部的常數 所以把陣列的長度也改成要輸入的參數

## [char](https://youtu.be/LfaMVlDaQ24?t=22153)

char的長度是固定的 都是一個字符

記憶體裡面會長這樣

二進制長這樣

## [string](https://youtu.be/LfaMVlDaQ24?t=22244)

string的長度不固定

記憶體裡面應該會長這樣

其實字串就是字符的陣列

為了要知道這個陣列何時結束 也就是字串的長度 所以會再加上一個byte去表示陣列的結束 這個byte的值是\0 (\0是代表null的特殊表示法 不是單純的數字0 下面會提到)

整數的陣列也一樣

所以其實string在記憶體裡面是長這樣

這個"0"其實就是ASCII裡面的NUL

字符其實就是數字 所以這樣也可以印出數字

字串就是字符 所以這樣也可以印出字串

還可以把最後的0也印出來

可以先從字串的陣列中取出字串 再從字串中取出字符

記憶體裡面這樣呈現

也就是這樣

可以利用陣列最後是\0的特性來找到字串的長度

string.h是一個跟string相關的程式庫 可以在課程的程式庫說明書中找到相關資料

string.h裡面有一個取得字串長度的函數:strlen
使用時要記得include string.h

另一個跟字串相關的程式庫叫做ctype.h 課程的程式庫說明書裡面也有相關資料

大小寫之間永遠差32

可以利用字串就是字符 字符就是數字的特性進行大小寫轉換

include ctype.h之後 就可以使用toupper()這個函數

原本每一次迴圈都要呼叫strlen() 但如果在一開始把這個函數提出來賦值給n 這樣就只要呼叫一次就好

現在代表這個程式不接受command line arguments

改成接受參數
int argc代表參數數量 會包括"./greet"指令
string argv[] 代表參數 一樣會包括"./greet"指令 所以此時的argv[0]會抓到./greet

這樣就可以在輸入參數的同時取得資料

到目前為止 我們有兩種主程式形式 沒有參數的主程式

跟有參數的主程式

## [cowsay](https://youtu.be/LfaMVlDaQ24?t=24412)

cowsay是已經寫好並安裝在環境裡的應用程式 他需要至少一個參數

如果使用-f指定可選參數為duck 圖案就會變成鴨子

也可以指定為龍

## [exit status](https://youtu.be/LfaMVlDaQ24?t=24551)

exit status是指程式結束執行後返回給作業系統的數字 代表了程式的結束狀態 通常預設結果是0 所以0不會顯示出來 其他數字則被用來表示錯誤或例外

`echo $?` 可以獲取上一個命令的退出代碼

我們可以自己設定退出代碼

## [cryptography](https://youtu.be/LfaMVlDaQ24?t=24881)

plaintext:純文字
encryption:加密
ciphertext:密文

加密理論上是可以解密(decrypt)回原始內容的

key值:例如把每一個字母往前或往後移動n個位置 這個n就是key => 凱薩密碼

# Lecture 3 - Algorithms

[回到目錄]

## [searching](https://youtu.be/LfaMVlDaQ24?t=25409)

人類可以很輕鬆的綜觀全局 找到我們要找的數字

但電腦一次只能做一件事 所以對電腦來說 陣列是一排關著的櫃子 電腦每次只能查看一個數字

我們希望演算法告訴我們目標數字50有沒有在陣列裡面 所以回傳bool

linear search 線性搜尋法:櫃子裡的數字沒有經過排序
pseudo code (偽代碼) 版本:依序打開櫃子 => 有50就回傳true/沒有就繼續 => 全部都沒有回傳false

比較接近C語言的版本

binary search 二分搜尋法:櫃子裡的數字經過排序
pseudo code版本:如果沒有櫃子了就返回false 如果中間的門裡面有50就回傳true/小於50找左邊/大於50找右邊

比較接近C語言的版本

結論:資料量少的時候可以用線性搜尋 資料量多的時候就要用二分搜尋 但二分搜尋的前提是資料經過排序

斜體的大寫O (唸做big O) :用來描述算法在最糟情況下的執行次數 演算法執行所需時間的上限(Upper bound) 不是精確表示法 只是一種概括性的表示 表示當輸入資料規模增加時 算法執行時間的增長趨勢

上到下代表慢到快

omega:用來描述算法在最佳情況下的執行次數 演算法執行所需時間的下限(Lower bound) 一樣是一種概括性的表示
線性搜尋跟二分搜尋的omega都是Ω(1) 也就是第一次就找到50

Theta:是O和Ω的綜合體，表示算法的平均情況下的執行次數 代表演算法執行所需時間的上下限相同 比如說數出教室內人數的算法就是θ(n) 因為最佳情況跟最糟情況下都必須數完所有人

實際建立一個線性搜尋的程式

改成字串的搜尋 但是要注意因為字串其實是字符的陣列 而==並無法比較陣列的全部內容 所以這樣會出錯 (C#中 ==有多載 所以可以比較字串 但這邊是用C 所以不行)

C要引入string.h 並使用其中的strcmp() 這個函數等於0時代表輸入的兩個參數相同
strcmp()除了0以外 也有可能會傳回正數或負數 當需要按字母排序時可以利用回傳的0跟正負數來表示位置相同或在前或在後

當輸入不存在的字串時出現Segmentation fault錯誤 因為現在只有六個字串 但是for迴圈裡面的7沒有改到 所以當程式嘗試訪問記憶體中不存在的string[6]時就會發生錯誤

如果沒有return或break去中斷迴圈的話 程式就會繼續執行 導致同時印出Found跟Not found

## [data structures](https://youtu.be/LfaMVlDaQ24?t=28095)

新建立一個查詢電話簿的程式 但這個程式的問題是沒有把名字跟電話綁定的措施 當名字順序改變時 必須要一起更新電話順序 否則會亂掉 => 解決方法:自訂資料結構 (data structure)

我們可以建立一個"人"的型別 其中包含了名稱跟號碼 現在名字跟電話已經被綁定了

把下方的程式也一起改完

## [sorting](https://youtu.be/LfaMVlDaQ24?t=28732)

演算法的目標是把未排序的資料排序

selection sort 選擇排序:每次都找到未排序數字中的最小值 然後跟未排序數字的第一個交換位置 已排序數字的部分就可以不用看了

交換位置的方式可以保證數列大小不變 不然每次都要其他數字往右邊移一位來騰出空間會消耗很多效能

注意每次都必須經過全部的未排序數字 因為電腦的記憶體永遠只能儲存一個最小值 不像人類可以記憶所有數值 這段演示過程比較久 建議看影片

pseudo code
numbers[i]到numbers[n-1]代表每次都從第i個到看到最後一個 從第i個開始是為了跳過已排序的部分

bubble sort 泡沫排序:每次比較數列中相鄰的兩個數字 順序不對就交換 所以最大值會被慢慢推到數列右邊 稱為泡沫排序是因為比較大的數字會經由交換慢慢浮出到數列的頂端 這邊也建議看影片演示

如何判斷排序完成? => 每一輪的比較結束後 檢查是否發生了交換 如果沒有發生交換就代表排序完成

pseudo code

選擇排序中 如果一共有n的數字 要確定地一個數字的位置需要n-1次比較 (n-1因為不用跟自己比) 第二次因為還可以跳過已經排好的 所以需要n-2次 把每輪需要的步驟數相加可得以下結果 當n很大時 只要注意n平方的部分就好 所以可以寫成O(n^2)

最壞情況下是O(n^2)

但是在最佳情況下 程式因為一次只能記憶一個最小數字 所以程式依舊要跑完全程才能確定完成排序 所以一樣是Ω(n^2)

因為執行時間的上下限相同 也就是說 選擇排序的效率是θ(n^2) 該算法永遠需要相同步驟才能完成排序

接著看泡沫排序

0到n-2是因為每次會比較i跟i+1 所以只要到倒數第一位就會跟最後一位比較到了 如果到n-1的話 會變成最後一位跟沒有人比

另外該排序只要重複n-1輪就可以了 因為只要排完了其餘的數字 最後一個數字自然會在正確的位置

可以看到必須經過n-1輪 而且0到n-2代表每輪要經過n-1次

所以在最遭情況下執行步驟數是(n-1)x(n-1)也就是O(n^2)

但是在最佳情況下 也就是已經排好的情況下 只要跑過一次 發現沒有交換發生就會跳出了

交換次數是這兩種排序算法的一個區別 泡沫排序在每次比較後都進行交換 而選擇排序僅在找到最小值後才進行一次交換 因為通常交換的成本比比較的成本更高 因此選擇排序在這一點上稍微更有效率

動畫網站:https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

## [recursion](https://youtu.be/LfaMVlDaQ24?t=30431)

recursion 遞迴:指函數呼叫自己的能力 但每次處理的資料量必須越來越少 以確保最終會達到終止條件 (base case) 而終止條件是確保遞迴不會無限循環下去的關鍵

注意每次都會剩下一半 所以要處理的資料越來越少 然後終止條件是找到目標 或是全部沒有就放棄

iteration 迭代:重複執行一段程式碼 且每一次的結果會變成下一次的初始值 直到滿足終止條件

沒有終止條件 會變成無限循環

四層金字塔就是三層金字塔`draw(n-1)`加上第四層 然後三層金字塔又是二層金字塔加上第三層... 以此類推 最後終止條件是n小於等於0時停止

程式每次執行到第19行時就會重新呼叫自己 直到n小於等於0時會return結束本次遞迴並返回上一層被呼叫的地方 也就是draw(1)裡面的第19行 然後繼續往下執行21到25行 印出#後結束本次遞迴 然後再返回上一層被呼叫的地方 也就是draw(2)裡面的第19行 並繼續執行21到25行 印出##後結束本次遞迴 以此類推 最後畫出四層金字塔

## [merge sort](https://youtu.be/LfaMVlDaQ24?t=31435)

如果只有一個數字就返回 否則先排序右邊 再排序左邊 最後合起來


先不管左右怎麼排的 重點先放在如何merge合併兩個數列

首先比較兩邊的第一位

右邊的第一位比較小 把右邊的第一位取出放到新的第一位 然後左邊的第一位跟右邊的第二位再比

右邊的第二位比較小 把右邊的第二位取出放到新的第二位 然後左邊的第一位跟右邊的第三位再比

左邊的第一位比較小 把左邊的第一位取出放到新的第三位 然後左邊的第二位跟右邊的第三位再比

重複直到完成排序 注意合併排序不像選擇排序跟泡沫排序需要反覆進行迴圈 合併排序時兩邊的比較位置始終只往右移

另外由於合併過程中需要一個新的數列來把數字放進去 所以合併排序需要額外的記憶體空間

接下來注意排序左右邊的部分

首先執行第一行:排序左邊 => 取出原數列的左邊 因為要排序 所以進入下一層的排序左邊 於是再取出左邊的左邊 重複值到左邊只剩一個數字時停止 於是完成排序左邊 接著換排序右邊 但右邊也是只有一個數字 所以右邊排序也完成 於是進入合併環節

結束左邊的左邊合併排序後回到上一層 往下執行右邊排序 所以會像上面步驟一樣進入下一層進行拆分 拆到不能拆就合併

完成左邊的右邊合併排序後回到上一層 往下執行合併

合併完就完成了左邊的排序 於是返回上一層 往下執行右邊排序

右邊也排序完就會往下執行合併

最後就完成全部排序了!

第一行把1個int[8]拆成8個int[1] 進入終止情況(只有一個數字就返回)停止拆分並完成排序部分
第二行把每2個int[1]合併成1個int[2]
第三行把每2個int[2]合併成1個int[4]
第四行把2個int[4]合併成1個int[8]

在合併過程中 每一個數字都只會被比較跟移動一次 不會被反覆比較或移動 也就是說會進行log n輪 每輪比較n次 所以全部執行步驟的上限是n log n次

因為執行次數的下限也是n log n次 所以合併排序的效率是θ(n log n) 該算法永遠需要相同步驟才能完成排序

如果想要減少執行需要的時間 就必須付出一些東西 可能是要付出人類寫程式的時間 也可能是要付出額外的空間 例如合併排序需要額外的記憶體空間來存放合併後的新數列 所以早期在記憶體價格十分高昂時就可能不會採用合併排序

動畫播放時間點:https://youtu.be/LfaMVlDaQ24?t=32357

執行速度:合併排序>選擇排序>泡沫排序

# Lecture 4 - Memory

[回到目錄]

## [圖片](https://youtu.be/LfaMVlDaQ24?t=32601)

這是一張bits地圖

如果1是白色 0是黑色 就會形成一張笑臉圖片

自製像素圖片
cs50.ly/art

RGB都是0是黑色 RGB都是255是白色 注意下面的#FFFFFF 這種表示法叫做color code (顏色代碼)

color code採用十六進制 (Hexadecimal/base-16) 所以0到9後面還有a到f

第一個位置代表16的1次方 第二個位置代表16的0次方

這是0

這是9 接下來應該要變成10

因為是十六進制 所以10要寫成0A

這樣是15

這樣是16

最大就是255

為什麼要用十六進制? => 因為4個bits剛好可以從0數到15 對應了0到F 然後FF也就是8個bits 就是1個byte => FF就是11111111 00就是00000000

電腦科學中也常用十六進制來描述記憶體中byte的位置

但為了避免跟十進制搞混 一般前面會加上0x

當宣告一個變數時 系統將為該變數分配對應的記憶體空間 這邊因為是int型別 所以佔用4個bytes

假設這個變數儲存在記憶體中0x123的位置

&符號可以找到變數的記憶體地址
*符號可以訪問特定的記憶體地址的值

注意在印出記憶體地址時 佔位符要改成%p

## [pointers](https://youtu.be/LfaMVlDaQ24?t=33864)

C語言相對python之類的語言更接近底層 所以有一些比較特殊的功能 其中指標 (pointer) 是一個非常重要且強大的概念 它讓使用者能夠直接存取記憶體位置 這種直接性使得C語言在處理底層的系統細節、效能優化及資料結構的實現上非常靈活

簡而言之 pointer是一個儲存物件在記憶體中位置的變數 也可以說pointer就是物件的記憶體地址

p的型別是pointer 但不寫pointer而是寫int *是為了告訴程式這個p是一個指向int的pointer 這樣程式就知道目標位置上的資料應該解讀成int 所以當使用這個指標來存取記憶體位置上的資料時 程式就知道應該將這個資料視為整數

p會儲存n的位置 注意p佔用了8個bytes 因為現在的電腦記憶體很大 所以pointer也必須要夠大 (pointer的大小通常與該系統的位元架構相關 例如64位元的系統 那指標通常會佔用8個bytes)

p值不是固定的 因為它會指向n的位置 n的位置在哪裡 p的值就是多少 所以p本身的值跟位置並不重要

當宣告一個字串`string s = "HI!";`時 程式會在記憶體中為這個字串分配一段空間 同時在結尾加上\0

變數名稱s會被儲存在其他地方 而且s實際上是指向字串第一個字元的記憶體位置 也就是說變數名稱不需要存儲整個字串的全部位置 只需要存儲其起始位置即可 這樣的設計有助於節省記憶體

可以把s理解成一個pointer

所以其實string是char *

注意 在C語言中 string不是內建型別 而是char *的代名詞 表示以\0 (nul) 終止的字符陣列 這種表示方式需要開發者手動處理字串的大小和記憶體管理

(但是在C#中 string是內建的資料型別 因為為了簡化字串操作 所以語言內部已經幫我們處理了很多字串操作的底層細節 因此我們就不需要自己操作 直接使用string就好)

回顧一下上週的範例 我們定義了一個資料型別person 然後結構是下圖黃色的部分

我們之所以可以在教學環境中使用string 是因為cs50程式庫中幫我們定義了string

因為p儲存的是地址 所以用%p會印出地址

但如果用*p就會進入該地址取得實際值 因此就可以用%i印出數字

如果沒有include cs50.h 就不能使用string

沒有include cs50.h 就要使用char *了 可以看到一樣會印出位址

但如果改成%s 程式就會自動進入並印出所有字符直到遇見\0 所以不需要*s進入位址也可以印出字串

因為用*s進入只會找到第一個字符而已 但我們不是要一個字符 而是希望程式把全部的字都印出來

s跟&s[0]的位置相同 然後其他字符會跟在第一個字符後面

## [pointer arithmetic](https://youtu.be/LfaMVlDaQ24?t=35872)

Pointer arithmetic 指標算術:在程式語言中對指標執行的數學操作 這些操作應用於指標中存儲的記憶體地址

可以這樣印出每個字符的值

還可以這樣用地址的方式印出字符的值

但如果去到太遠的地方嘗試訪問系統沒有分配給程式的記憶體部分可能就會導致segmentation fault

要注意這種訪問程式中其他地址的技術可能會被駭客用來從記憶體內竊取資料

接著看下方範例中程式會從指定位置開始往後印出 直到遇見/0

另外在訪問數字字串時 一樣只要寫+1就可以訪問下一個數字了 不需要因為一個數字是4個bytes所以寫+4 程式會自動處理這部分

這就是為什麼string不能用==來比較 因為這樣會比較第一個字符的位置而不是實際的內容 而strcmp()就會知道要進去比較內容

記憶體裡面長這樣

結論:string很特別 它是一個由一個記憶體地址開始 並以\0結尾 除此之外其他內容都只是值而已

理論上可以這樣去比較每一個字符的值 但沒必要 還是用strcmp()就好了

s的第一個字也被改成大寫了 因為在複製`string t = s;`的時候 其實是將t的指向了與s相同的記憶體地址 所以改變t也會一起改變s

要記得加上檢查 不然如果使用者直接按下enter 程式嘗試訪問第一個字符時就會出現segmentation fault

`string t = s;`在記憶體中長這樣

## [複製字串](https://youtu.be/LfaMVlDaQ24?t=37483)

如何複製字串?

malloc:跟系統請求一定的記憶體空間 系統如果找到了可用的記憶體空間會回傳第一個byte的地址 但要注意malloc不像string會有/0結尾 所以使用者要自己記得請求了多少空間

free:完成操作後 透過free把記憶體地址傳給系統 告訴系統已經完成操作 把剛剛分配給程式的記憶體空間還給系統

如果一直不斷malloc 但沒有free 就會把記憶體空間用完 導致電腦當機

要記得先include stdlib.h才能用

要記得加上\0的位置

在迴圈的部分也要記得加1 把\0也算進去

如果沒有把\0加進去 程式會找不到結束的位置

malloc讓系統分配記憶體空間

迴圈把值填進去

改進一下迴圈的寫法

事實上原來的迴圈就是strcpy()

## [NULL](https://youtu.be/LfaMVlDaQ24?t=38170)

\0 nul 是一個特殊字符 是字元的一部分
null 是一個指標 指向的地址是0x0 也就是所謂的空指標 表示該指標不指向有效的記憶體位置

(C#中的null不一定指向0x0 而是指向一個表示沒有指向對象的特殊值)

get_string()跟malloc在發生錯誤時會返回NULL (例如輸入了太多文字或要求太多空間)

增加錯誤檢查 如果發生錯誤了就結束程式

最後記得要free記憶體 一般來說程式結束後就會自動釋放記憶體 所以這邊可以不需要手動釋放記憶體 但如果是要不斷執行的程式就要記得釋放記憶體 避免把記憶體用完 另外只有malloc才需要free 其他函數例如get_string()會自動釋放記憶體

## [valgrind](https://youtu.be/LfaMVlDaQ24?t=38601)

裡面有一些記憶體相關的錯誤 但程式仍然可以編譯 而且還可以執行

要先編譯過 然後下這行指令

write 寫入/改變 <=> read 讀取
Invalid write of size 4:有一個大小為4 bytes的無效寫入操作

memory lost = memory leak 記憶體洩漏:程式在執行過程中動態分配記憶體 但在結束時沒有正確釋放 這塊記憶體就像是在程式的執行期間洩漏出去 無法再被程式訪問或釋放

修改完的程式

沒問題的話會顯示這樣

下面的程式宣告了一個整數陣列 也就是分配了記憶體空間 但卻沒有設定任何數值

在C語言中 如果沒有初始化值 就會出現garbage values 也就是說程式會讀取到記憶體空間中之前的內容 這個範例因為是小程式 所以不太會有大問題 但是大程式中因為記憶體會不斷地被使用/釋放 所以就會有大量的垃圾值存在於記憶體中

C會在沒有遇到垃圾值的時候 變數會被自動初始化為0 但通常只有一開始才會這樣 所以可以看到有些是0 有些是垃圾值

結論:不要這樣 永遠要記得初始化值

\*y不像\*x有要求記憶體空間 所以y很有可能會讀取到垃圾值或是發生錯誤

現在把y的地址設定成跟x一樣 這樣就可以把x一開始設定的42改成13了

## [教學影片](https://youtu.be/LfaMVlDaQ24?t=39161)

pointer指向的東西叫pointee

Dereferencing是指使用指標來訪問或取得該指標指向的內存位置中的值 當你對指標進行dereference時(例如\*x) 你實際上是在取得指標所指向內存位置的值

## [變數交換](https://youtu.be/LfaMVlDaQ24?t=39403)

變數交換時一般需要一個暫時的容器

其實有辦法透過bits完成不需要暫時容器的交換方法

然而程式失敗了 因為C語言的函數在呼叫時是按值傳遞的 傳入函數的是變數的值 不是變數的地址 也就是將這個變數的值複製一份傳給函數 C語言沒辦法自己去地址中修改資料 因此這個函數只會在內部交換a和b的值 不會影響到原始變數

## [scope](https://youtu.be/LfaMVlDaQ24?t=39711)

scope 作用域:指變數或函數的可見性和有效性的範圍

不同東西會被放在記憶體中的不同地方
當我們執行程式時 程式的機器碼就會從硬碟被載入到記憶體的最前面
接著是全域變數
接著是heap 也就是一大堆程式運行時可以動態分配的記憶體 malloc就是從這裡取得記憶體的 要求越多記憶體 位置就會越來越往下 然後把空間填滿
最後是stack 跟heap相反 會越來越往上 是有參數跟變數的函數暫時儲存的地方

一直malloc會導致heap用太多 不斷呼叫函數或無限循環會導致stack用太多 兩者都有可能導致segmentation fault 所以寫程式的時候要確認malloc/get_string之類函數的回傳值是不是null 確保沒有把記憶體空間用完

呼叫main時 會在stack的底部被分配到一些記憶體叫做frame
之上是裡面呼叫的函數swap 當swap結束後 這些記憶體空間就被自動釋放了 但裡面的內容還在 在該記憶體區域讀取時就有可能會得到垃圾值

接下來一步一步看 首先是main函數中定義了x跟y 然後呼叫swap

因為函數在呼叫時是按值傳遞 所以x會被複製到a y被複製到b

接著執行swap 可以看到a跟b確實被交換了 但x跟y沒有被改變

之後swap執行完畢 又回到原來的狀況

回來看程式 邏輯上對 但實際上只會在該函數的作用域中交換

改成傳入地址

這次a、b會指向x、y

這樣就可以正確交換x、y了

除了改函數外 原型跟傳入的參數也要改

## [overtflow](https://youtu.be/LfaMVlDaQ24?t=40368)

因為記憶體空間的設計問題 heap跟stack都有可能用太多

用太多用到不該用的區域就會出現heap overflow跟stack overflow

而buffer overflow則是指在寫入緩衝區時超出其容量 可能發生在stack 也可能發生在heap 通常是由於沒有檢查輸入的大小而引起 出現時就代表程式中有邏輯錯誤

接下來就可以來看這些函數是如何實現的了 會使用這些函數是因為C語言中很難正確取得使用者輸入的資料 特別是當不知道使用者會輸入多少東西時很容易寫出有bug的程式 事實上要在不導致buffer overflow的前提下正確儲存使用者輸入的資料是有難度的

我們用`scanf("%i", &x)`來讀取使用這輸入的數字 並放到x的地址中
如果使用者不是輸入數字 就會被設置為0

取得int是相對簡單的 但要取得string就不一樣了
結果都是0 因為s始終指向NULL

這樣就可以了 因為我們用陣列分配了四個bytes給cat+\0 但這樣會把空間寫死 可是我們又不能每次都給一個很大的空間去儲存使用者輸入的資料 所以要不斷檢查使用者輸入的資料 如果不夠就再malloc 使用者每多輸入一個字符 就要重新malloc一個更大的空間

預告:訪問文件

# Lecture 5 - Data Structures

[回到目錄]

抽象資料型別 跟其他C語言中的型別類似 抽象資料型別中也有屬性 但是抽象資料型別的實作細節最終取決於使用者 也就是說抽象資料型別可以代表某個東西 也可以進行一些操作 但使用者可以決定如何完成這些操作
結論:ADT包含了資料和操作 但這些操作的具體實作是抽象的 使用者可以根據需要自行實現 這種設計模式使得程式碼更加模組化 因為使用者僅需關心操作的定義和如何使用它們 而不需深入了解實作的細節

queue是一種抽象資料型別 就像現實中的排隊一樣 queue也有first in first out屬性 也就是先來的人先處理

queue都會有兩種函數
enqueue:將一個新元素添加到queue的尾端 => 從最後面開始排隊
dequeue:從queue的前端移除一個元素 => 第一個結完帳的人離開

但有可能會遇到插隊 也就是說如果不堅持FIFO原則 queue就會有不公平的可能

另一種抽象資料型別是stack stack就像餐盤一樣 擺放的時候是由下往上堆疊 而使用者在取得的時候也是從最上面開始拿 這種屬性稱為LIFO 也就是last in first out 所以stack不在乎順序 但可能也會有一些很髒的餐盤在最下面從來沒被人拿過

我們的信箱內容就可以說是一種stack 新的信件會出現在最上面 舊的信件會被推到最下面

stack也會有兩種函數
push:把新元素放在stack的最上面
pop:從stack的最上面把元素拿走

接下來進入程式範例
首先我們自訂了一個類別stack stack中有一個person的陣列 陣列的大小是最大容量 還有一個標示陣列實際大小的整數size (CAPACITY是衣櫃的容量 size是實際有幾件衣服)

可以在外面定義CAPACITY 但此時有一個缺點 就是50可能會不夠用 但是又不能直接定義成5000 因為如果沒用那個多 那也會浪費很多記憶體空間

## [queue&stack比較影片](https://youtu.be/LfaMVlDaQ24?t=41897)

## [arrray](https://youtu.be/LfaMVlDaQ24?t=42040)

要往大小是3的陣列後面加新元素時 可能會遇到後面的記憶體已經有人用了的問題 所以我們需要移動整個陣列去有放得下4個元素空間的地方

我們要先把原來陣列的元素覆寫到垃圾值上 然後就可以丟掉舊陣列了 最後在把新元素加到新陣列的第4個位置上 但這種設計缺乏效率 因為每次都需要複製一遍原來的值

換一個思路 3後面放不下了 那我們可以直接把新元素放在其他地方 然後在原來的陣列後面加一個指示

在程式的範例中可以看到要改變陣列大小會需要改很多地方

先改成用malloc的方式動態分配記憶體

這樣需要增加元素時 就可以重新malloc 然後把舊元素複製到新空間上 再加上新元素 接著釋放舊的list空間 最後把list重新指向tmp的位置
注意 如果發生錯誤 要返回之前也要先free之前使用的list空間

程式結束要退出前也要記得free 注意這邊free了list兩次 但兩次釋放的是不同位置的記憶體空間 第一次是釋放舊的list 第二次是釋放新的list 因為現在list跟tmp都指向新的記憶體位置 所以只要free其中一個就好 不需要釋放兩次

## [realloc](https://youtu.be/LfaMVlDaQ24?t=43204)

realloc會先嘗試在原地擴展或縮小記憶體 如果不能在原地進行 它就會在其他地方分配新的空間 將舊內容複製到新的空間 並釋放舊的空間

struct用於建立自訂的資料型別
.用於訪問物件的屬性
*代表指標 也用於訪問指標指向的值

.跟*可以合起來變成->

## [linked list](https://youtu.be/LfaMVlDaQ24?t=43662)

linked list由一系列節點 (Node) 組成 每個節點包含數據 (data) 和一個指向下一個節點的指標 (pointer)

記憶體中就會長這樣 然後最後一個節點的指標指向NULL來標示結束

還要加上起點

簡化後就變成這樣
因為linked list是非連續且動態的資料結構 所以需要一個起點來標示從哪裡開始 但array是連續且固定大小的資料結構 所以不需要標示起點

想要訪問linked list中的元素時 需要從head開始按照指標的方向一步一步地移動到下一個節點 這種存取方式相對array更複雜 因為需要遍歷整個linked list 而不像array那樣可以通過索引直接訪問 但是linked list在插入和刪除元素方面更加靈活 因為它不需要移動大量的元素

node *代表指向下一個node的指標 但是要注意 在我們使用node型別之前 我們還沒完成定義node

所以要加上另一個關鍵字:struct

這樣代表我們先建立一個資料結構叫做struct node 這樣就可以在裡面使用struct node這個型別 最後用typedef把struct node重新命名成node

使用linked list的缺點:
1. 因為需要儲存指標 所以大致上需要比array更多的記憶體 而且因為現在的指標大多需要8的bytes 所以甚至可能出現指標比資料還要大的狀況 不過還好現在的記憶體比較便宜了
2. 因為linked list是不連續的 所以不能像array一樣直接用[index]來訪問元素 而是需要從頭開始遍歷
3. 因為linked list是不連續的 所以也不能用binary search了 因為binary search需要能夠直接訪問中間元素 但是在linked list這樣不連續的資料結構上是不可行的

我們先定義一個node的指標list 但沒有指向任何地址 所以現在裡面是垃圾值

如果指向NULL 代表這個linked list是空的 這樣就完成了一個大小是0的linked list

我們再定義一個暫時的node的指標n 這次他指向了系統分配給我們的記憶體地址 但我們只有要求記憶體空間 還沒有填值進去 所以裡面還是垃圾值

`(*n)`代表訪問n指向的內容 然後透過`.number`可以訪問這個n這個node裡面的number屬性 這邊我們把number設成1

`(*n).number`又可以寫成`n->number`

我們讓這個節點的指標指向NULL 代表結束這個linked list 這樣就完成了一個大小是1的linked list

然後我們把list也指向這個節點

現在我們就讓list的大小從0變成1了 然後n就可以不管它了

然後我們再定義一個暫時的node的指標n 這次他一樣指向了系統分配給我們的記憶體地址 但我們只有要求記憶體空間 還沒有填值進去 所以裡面還是垃圾值

接著我們透過`->`把這個節點的number設成2 next設成NULL

但這次就不能讓list也指向這個節點了 不然list原來的節點就不見了 此時就出現了memory leak記憶體洩漏 因為原來的節點還存在 但沒有任何東西指向它了 也就是說我們丟失了原來節點的記憶體空間

所以我們改成讓新節點的指標指向第1個節點

然後再讓list指向新節點 這樣就成功插入了一個新節點到list裡面

最後就變成了這樣 雖然感覺順序不對 但至少我們成功把list的大小從0變成2 而且沒有造成任何記憶體洩漏

新元素會被放在list的最前面 所以可以說這是一個stack的結構 這樣設計的好處是增加新節點時不需要歷遍到最後一個節點 然後再把最後一個節點的指標指向新節點 而是只要將新節點的指標指向原來的起點 然後再把list指向新節點就好了

當然因為順序是相反的 所以會變成降冪排序 如果需要升冪排序的話就要考慮一下

接著回到程式 這樣就完成一個空的linked list

接下來改成透過命令列參數插入新節點

迴圈是從1開始 因為argv[0]是執行程式的指令
然後因為輸入的是字串 所以要用stoi()轉成數字

要把linked list裡面的值印出來 我們需要一個暫時的pointer依序歷遍所有元素

建立一個指標ptr 一開始指向list 然後進入迴圈 把節點的number印出來 然後更新指標為節點的指標 直到指標指向NULL為止

最後記得要用上面迴圈的方法依序釋放每個節點的記憶體
重新把ptr指向list 然後先用next取得下一個節點 再釋放當前節點的記憶體 最後更新指標為下一個節點 然後不斷循環直到ptr指向NULL

這邊要先用next取得下一個節點是因為如果我們已經釋放掉當前節點的記憶體 我們就無法再取得當前節點的指標了

注意 在這裡還有一個潛在的bug可能導致記憶體洩漏 如果第一次呼叫的時候就失敗沒問題 但是如果是在第二次或之後才失敗 直接結束程式會導致前幾次malloc的記憶體沒有被釋放 所以應該要進行garbage collection垃圾回收 把之前分配的記憶體釋放掉

當然 把while loop改成for loop也是沒有問題的

因為不能用binary search 所以每次要搜尋都需要歷遍所有元素 所以linked list的搜尋執行時間是O(n)

因為新增元素時是從頭插入 (prepend) 每次新增所需的步驟相同 所以linked list的插入執行時間是O(1)

如果是採用這種從尾插入 (append) 的方式 搜尋執行時間一樣是O(n) 但插入執行時間變成O(n) 因為新增時需要先移動到最後一個

如果像要在新增不規則元素時排序 也就是根據新元素的資料來決定要prepend還是append的話 搜尋執行時間一樣是O(n) 而插入執行時間一樣是O(n) 也就是說執行時間跟append相同 但多了排序功能

## [tree](https://youtu.be/LfaMVlDaQ24?t=46698)

兼顧可以用binary search的速度 也想要linked list的動態變化能力 => 從一維變成二維

而tree其中的binary search tree就擁有binary search的屬性

linked list相較array的優勢是在新增時不需要複製跟移動原來的元素 而array相較linked list的優勢是可以用binary search

在這個數列中黃色是全部的中間元素 紅色是一半的中間元素 剩下元素是綠色的

如果把這個數列變成二維的就會變這樣

如果把每個元素變成節點 然後透過指標去連接其他節點 其中4又稱為root 代表這個binary search tree的起點

相較之前的linked list的節點只有一個指向下一個元素的指標 binary search tree的節點有兩個指標 分別指向右邊跟左邊 但這也是binary search tree的其中一個缺點 就是需要更多的記憶體空間 還好現在記憶體已經相對過去便宜很多了

兩個參數分別是指向tree的指標 又稱為root 也就是這個樹的起點 跟要找的數字

不過二分搜索樹還有其他潛在的問題 例如下面範例中 如果先新增2 再新增1跟3的話 結果沒什麼問題

但如果先新增1 再新增2跟3 甚至繼續新增4的時候就會出現左右不平衡的問題了 此時二分搜索樹就會變得像linked list一樣

也就是說 在運氣好 也就是二分搜索樹左右平衡的時候 搜索的執行時間是O(log n) 但是運氣不好時 二分搜索樹會變得像linked list一樣 於是搜索的執行時間就會變成O(n) 因此二分搜索樹往往需要一些方法來修正資料結構以保持平衡

## [dictionary](https://youtu.be/LfaMVlDaQ24?t=47573)

如果我們能找到一種資料結構的搜索執行時間是O(1) 也就是每次只需要相同步驟就能完成的話最好

就像真的字典有單字跟定義一樣 dictionary也有key跟value key用來找東西的媒介 value是最後找到的東西

在通訊錄中 名字就是key 電話號碼則是value

## [hashing](https://youtu.be/LfaMVlDaQ24?t=47769)

如何實現搜索時間是O(1)? => hashing
hashing是指傳入一個值 經過轉換後回傳一個簡化的版本

例如在排序撲克牌時 我們通常會先按照花色來分類 也就是把52張不同的撲克牌簡化成4種花色

hash function是實現這個想法的函數

hash table是集合了array跟linked list兩種資料結構的優點的應用 理想上可以達到或接近O(1)

例如在通訊錄中 我們可以先用array找到名字的開頭字母 再用linked list去連接相同開頭字母的名字

這樣會比linked list快 因為不需要歷遍所有名字 也會比array快 因為不需要進行binary search 理想情況下多數名字可以透過開頭字母來一步找到 也就是可以用恆定的步驟完成搜尋 但如果遇到有多個相同開頭字母的名字時會發生碰撞 (collision) 這樣就需要在這個開頭字母的linked list上歷遍所有名字 導致搜尋效率減慢 變得接近線性搜尋的時間複雜度

如何減少碰撞/解決相同開頭字母的名字接在一起? => 從用開頭字母分類變成用前兩個字母分類

但看起來還是有兩個名字會被分到同一區 => 用前三個字母分類

這樣就不會出現碰撞了 但是前面用來儲存前三個字母的array變的超大 這樣可能會浪費很多記憶體

我們一開始建立了person這個型別來儲存名字跟電話

但在這個哈希表中 我們會改成這樣來儲存名字、電話以及指向下一個名字的指標

而這個哈希表本身則是一個數列 其中代表每個字母的方格是指標 如果沒有這個字母開頭的名字 那這個字母就是空指標 (null pointer) 如果有名字就會指向名字的節點

就像撲克牌按照花色分類一樣 名字Albus會被分類到[0] 也就是A開頭

在最糟的情況下 哈希表的搜尋跟新增執行時間都是O(n) 比所有人的名字都是A開頭

但如果用聰明一點的方式分類 例如改成用前三個字母分類 平均情況下執行時間會變成O(n/k) k代表分類的數量 雖然這樣還是O(n) 但理論上每增加一個字母用來分類 分類數量會增加26倍 整體速度也會變快26倍

## [trie](https://youtu.be/LfaMVlDaQ24?t=48651)

trie (字典樹) 是一種特別的樹狀結構 它是retrieval的縮寫 但唸作try 這個樹狀結構的每個節點都是一個數列

這是trie的root

這樣可以儲存Hagrid 但是到d的時候 綠色代表某種終止信號 例如bool的true 用來表明這個名字在這邊結束

trie可以重複使用節點 通過共享相同的自首可以節省空間

trie搜尋的步驟數取決於名字的長度 因此如果假設最長的名字是50個字母 就代表50步以內一定會找到目標名字 50是一個常數 所以trie的搜尋執行時間是O(1) !!

但trie的卻點就是需要占用超多的記憶體空間 因為每個節點都需要儲存26個字母 => 執行效率的代價往往是記憶體空間 這是計算機科學中一個重要的權衡之一 被稱為時間與空間的權衡 (Time-Space Tradeoff) 有時甚至還需要考慮到人類的開發時間、成本、程式的可讀性...等因素

trie的每個節點都包含了一個數字 以及一個數列 這個數列中有26個指向下一個節點的指標

儲存trie的變數只需要一個指ㄜ向根節點的指標就好了

這個trie儲存了兩個名字 Daniel跟Danielle

一個節點中的字母既可以擁有終止信號 表示某個字串在這裡結束 同時也可以擁有指向下一個字母的指標 這樣的組織方式允許trie共享相同的前綴 同時保留每個字串的終止信息

trie的執行速度是O(1) 因為其執行速度取決於輸入值的長度 或稱為key的長度 而跟資料數量無關

圖片中的架子有key-value pair特性 所以類似一個字典結構 但也可以看成一個hash table => 資料結構無處不在!!

# Lecture 6 - Python

[回到目錄]

## [概論](https://youtu.be/LfaMVlDaQ24?t=49467)

python不像C語言需要經過手動編譯後才能執行 python可以透過python解釋器 (interpreter) 去解釋 (interpret) 程式 解釋器會逐行將原始碼轉換為適當的機器碼並執行

這是C版本的

這是python版本的 注意到最後的分號不見了 \n也不見了

以前C需要這樣引入標頭文件

python版本的寫法也被簡化了

建立code hello.py後 直接呼叫python程式去解釋原始碼就可以執行了
ㄨ

除了引入整個程式庫 也可以單獨引入程式庫中的某個函數

還可以這樣引入多的函數

這是C版本的

這是python版本的 注意到除了最後的分號不見了 現在也不需要宣告answer是string了 因為python是一種動態型別的語言 它會自動根據變數的內容自動推測型別 而且print()函數中不需要%s之類的佔位符 而是用+來連接 (concatenate) 字串

python也可以這樣寫 print一樣會連接兩個字串 並自動在中間加入空格

python還可以這樣寫 可以用{}插入變數 但要在""前面加上f 這種方式稱為格式化字串 (format string/F string)

## [types](https://youtu.be/LfaMVlDaQ24?t=50284)

這些是python中類似C語言的型別 因為python裡面的int跟float的大小可以動態調整 所以不必像C語言中需要另外指定long跟double型別

此外 由於python中的str已經足夠用來表示單個字元 因此也不需要另外指定char型別

這些是python中特有的型別
list類似C中的array
tuple類似用來協調的X-Y pair
dict就是dictionary
set是數值的集合 但它會自動消除重複項

為了減少人類的開發時間 有很多功能跟函數被內建在python裡面去自動處理包括記憶體管理在內的底層操作 所以相較於C只執行我們寫的程式 python實際上需要執行更多程式 所以python的執行速度會比C慢

因此在使用更現代更高階的語言時 往往需要付出性能的代價 當然也有很多科學家在努力提高執行效率 特別是在重複執行程式時 程式可能會利用編譯優化技術 在後台經過某種形式的編譯 所以在後續執行時會變快

## [condition](https://youtu.be/LfaMVlDaQ24?t=51311)

if:
這是C

這是python 可以發現條件的小括號跟行為的大括號不見了 並且多了冒號 注意冒號後的下一行要縮排4個空格 縮排代表這一行是條件的一部份

python不像其他語言使用大括號 而是使用冒號和縮排 (indentation) 來定義條件塊的內容

if/else:
這是C

這是python

if/else if/else:
這是C

這是python 注意else if被改叫做elif了

## [variable](https://youtu.be/LfaMVlDaQ24?t=51475)

這是C

這是python

這是C

這是python

python也可以這樣寫 但python就不能用++的寫法了

## [loop](https://youtu.be/LfaMVlDaQ24?t=51558)

while:
這是C

這是python

這是C

for:
這是python
`[0, 1, 2]`看起來像array 但別忘了python中沒有array 這在python中是代表list 所以`for i in [0, 1, 2]`代表i會從0變1再變2 這種寫法的問題是萬一需要循環很多次的話就要寫很長

這時就可以改用`range(3)`了 事實上這種寫法的效率更好 `range(3)`生成的是一個表示[0, 1, 2]連續整數範圍的對象 但它不會立即創建一個包含所有元素的列表 而是在循環的每一步生成下一個整數 這樣可以節省記憶體 特別是在循環次數非常大的情況下

以發撲克牌為例的話 list的寫法是一次給三張牌 range的寫法是每次給一張牌 重複三次

最後是無限迴圈
這是python

python不像C需要int main(void){}作為程式執行的入口點 python解釋器會直接從上到下執行.py檔案裏面的程式碼

如果不用cs50的get_int 而是用內建的input 可以看到1+2的結果變成了12 因為input預設是回傳字串

解決方法:使用int()來轉型

## [truncation/floating-point imprecision](https://youtu.be/LfaMVlDaQ24?t=52242)

C語言中 整數相除會被截斷剩下整數部分 而python會自動幫我們轉成float

但是用f""來格式化結果時 一樣會出現浮點數不精確的問題
`:.50f`中.50代表顯示小數點後50位 f代表指定顯示的數字型態為浮點數

## [integer overflow](https://youtu.be/LfaMVlDaQ24?t=52405)

python會自動調整記憶體空間以容納任意大小的整數 所以不會像C語言中把整數的32 bits用完的狀況 所以沒有integer overflow的問題 但當整數轉換為字串並顯示在螢幕上時 顯示的位數會受限於螢幕的顯示區域

## [範例](https://youtu.be/LfaMVlDaQ24?t=52514)

數字比大小

Y/N判斷
python不用||而是直接用or 另外python中沒有char 只有string 而且python的string可以用"" 也可以用''

python還可以用list的寫法 但更好的方式是把s轉成全小寫 這樣就不用列舉所有可能了

## [OOP](https://youtu.be/LfaMVlDaQ24?t=52942)

在過去C語言中是使用程序式程式設計 (procedural programming) 程式主要由一系列的函數 也就是程序 (procedure) 組成 要改變變數的值時 我們需要把變數傳進程序 然後程序會給我們結果

但如果某些型別自己有內建的函數是一種更好的設計 這樣我們就不用把變數跟函數分開 而是用變數內建的函數來改變變數 物件導向程式設計 (object-criented programming) 就是這樣的技術 程式主要由物件組成 物件可以包含數據和相關的函數

C語言的變數只有結構 只能儲存資料 而python的結構 又稱為類別 (class) 不只可以儲存資料 還可以儲存函數 例如在python的字串str不只有屬性 還有自己專屬的內建函數 這樣的設計方式更強調封裝、抽象和代碼重用性

可以在這裡看到python中跟string有關的函數:
docs.python.org

透過`s = s.lower()` 就可以訪問str這個類別裡面的lower函數

當然 我們沒必要呼叫一樣的函數兩次

現在的寫法會導致我們丟失原來s的值 但是值得注意的是python的字串是不可變的 (immutable) 不像C語言中可以改變字串中的任意字符

`s.lower()`其實是回傳了一個全部小寫的s的複製品 原來記憶體中的s是不變的 當我們重新賦值給s時就等於忘記原來的s 因為python會自動管理記憶體 所以程式會釋放掉原來s的記憶體空間

## [範例](https://youtu.be/LfaMVlDaQ24?t=53303)

while loop

for loop

當然也可以把listk改成range

還可先定義一個meow函數

然後呼叫meow

出現錯誤了 錯誤在第二行 meow沒被定義 => 跟C一樣 函數必須要先定義才能呼叫

改變順序 讓meow先定義後呼叫就好了

但如果全部都先定義後呼叫的話 我們要執行的程式就會被擠到最下面 所以我們可以像C一樣自己定義一個main函數 這樣就可以把其他函數的定義放在main下面了 不過要記得在最下面呼叫main()

我們還可以讓meow接受參數

python沒有do-while loop 必須用while loop來達到類似的效果

這樣就完成了

接著我們定義main函數 並且將取得高度的部分封裝進函數裡面

注意python中似乎已經沒有作用域 (scope) 的問題了 在C語言中需要注意大括號的範圍 但python中不是那麼嚴格了 所以在11行的while loop中定義的n 在14行的while loop外面仍然可以用 也就是說python允許使用這在宣告之後的任意地方繼續使用同一個變數

我們可以直接在迴圈中return結果 這同時也會幫我們中斷迴圈

python style guide中建議 不同層次的類別和函數之間應該用兩個空行分隔

如果不用get_int()的話 也可以用內建的input() 並用int()轉型成整數 但是如果使用者輸入的不是數字時 程式會直接跳出例外

最後一行可以看到值錯誤的說明:'cat'不是十進位的整數

前面則是回溯程式執行的順序 先執行14行的main() 然後回到第2行 最後到第9行並發生錯誤

為了避免跳出例外 就需要錯誤處理

## [exception](https://youtu.be/LfaMVlDaQ24?t=54682)

print()可以接收多種參數 例如end是一個命名參數 (named argument) 命名參數有對應的名稱 end用於指定結尾的字符 預設的end是/n

而前面的"?"則是位置參數 (positional argument) 位置參數沒有對應的名稱 它們是按照位置的順序進行傳遞的

如果我們覆寫為end="" 印出來的時候就不會自動換行了

最後再加一個print()來讓它換行

print()還可以這樣寫 這樣就不需要迴圈了

如果要3x3的#可以用兩層迴圈

當然也可以這樣寫

## [len](https://youtu.be/LfaMVlDaQ24?t=55098)

因為python會自動處理記憶體分配 所以python除了沒有malloc跟free python也沒有指標 因此不像C中的array需要自己記得記憶體的大小跟位置 還要手動進行記憶體分配和釋放 python會自動處理這些東西 所以如果想要知道list的長度就直接問python就好了

在C中建立一個空的array沒有什麼意義 因為array的大小是靜態的 一旦分配了大小 就不能再改變 除非重新malloc

但是在python中建立一個空的list是有意義的 因為list是一種動態數組 可以自由變動大小

`scores.append(score)`的寫法可以寫成`scores += [score]` 也就是連接列表的意思

可以這樣轉換大寫 但是python不用像C一樣用迴圈一個字一個字轉換

python可以直接全部轉大寫

## [sys](https://youtu.be/LfaMVlDaQ24?t=55572)

如果想用命令列參數 可以引入sys的argv函數

注意一開始呼叫的python解釋器不算在參數裡面 第0個元素是腳本名稱 第1個元素開始是命令列參數

我們可以用迴圈印出所有參數 但是`for i in range(len(argv))`看起來有點抽象

直接用`for arg in argv` python就知道要歷遍全部元素了

如果我不要腳本名稱 用`for arg in argv[1:]`可以取得列表的第1個元素到最後的所有元素

如果引入整個程式庫 呼叫函數前要加上程式庫的名稱

這個範例中使用線性搜尋來搜尋名字

可以改成`if name in names`這種寫法 python就會自己處理線性搜尋的部分了

[ ]代表list
{ }代表dictionary

字典的用法類似列表 差別在列表的index是數字 而字典的index是key值

python字典的實現通常是基於哈希表的數據結構 理想上可以在恆定時間內找到`people[name]`的值

在C語言中 因為字串其實是指標 所以不能用\=\=比較 但是python沒有指標 所以不用擔心記憶體地址的問題 用\=\=程式就會自動幫我們比較字串的內容了

同理 這樣在C中會導致s跟t同時被修改 但是python就不用擔心這個問題 因為python的字串是不可變的 `s.capitalize`回傳的是s的複製品 s本身不會被改到

python的變數交換值也不需要像C語言中需要另外寫一個交換的函數 直接`x, y = y, x`就可以了

## [csv](https://youtu.be/LfaMVlDaQ24?t=56900)

`file = open("phonebook.csv", "a")`中 "a"代表是append mode (追加模式) 這種模式下 如果文件存在 寫入的內容將被追加到文件的末尾 而不會覆蓋文件原有的內容

`writer = csv.writer(file)`代表建一個csv寫入器 用於寫入csv格式的數據到指定的文件中

因為有的時候可能會因為忘記關閉檔案導致佔用太多記憶體 這樣就會在結束時自動關閉檔案了

如果改用DictWriter 就會按照欄位名稱填入值 而不是按照順序填入值 這樣可以確保數據的順序與欄位名稱的對應關係 避免改變欄位順序時可能帶來的錯誤

## [演示](https://youtu.be/LfaMVlDaQ24?t=57220)

# Lecture 7 - SQL

[回到目錄]

## [flat-file database](https://youtu.be/LfaMVlDaQ24?t=57794)

平面檔案資料庫 例如:csv檔案 (comma separated values)

可以用拖曳的方式把csv檔案放到VS Code中

這樣就可以看到原始的csv檔案內容

`open("favorites.csv", "r")`中 "r"代表讀取模式 可以從檔案中讀取資料 但不能寫入或修改檔案

`csv.reader`返回的對象可以視為一種迭代器 所以可以用`for row in reader`的方式歷遍資料 而且每個row都是一個包含該列各欄數據的列表 所以可以用index來取出特定欄位的值

用`| more`指令可以使結果分頁顯示 每次顯示一個屏幕的內容 按下空白鍵繼續顯示下一頁

但是用數字作為index來取出特定欄位的值可能會因為欄位順序不同而導致問題 => 別忘了第一列的值是標題

可以用`next(row)`來跳過第一列 但我們其實可以利用第一列

改用DictReader 此時每個row都是一個包含該列各欄數據的字典 這樣就可以用欄位名稱來取得資料了 而且因為會自動將第一列視為欄位名稱 所以不需要額外的操作來跳過第一列

統計器

但是要手動初始化所有語言的數量太缺乏彈性了 這邊改成字典 如果語言已經存在就加1 不存在就加入且設定數量為1

加上sorted()後會按照字母順序對資料進行排序

當然也可以倒序

預設排序的key值是字典的key值 但我們可以自己覆寫成用數量排大小 注意`key = get_value`中 get_value沒有傳入參數 因為我們不是要在裡面執行函數 而是要傳入這個函數作為sorted()的參數

這樣就會變成從數量最多到數量最少

如果覺得特地另外寫一個函數太麻煩 可以改用lambda寫法 直接把函數寫在參數裡面

`key=lambda language: counts[language]` :前面的language是參數 後面的counts[language]是回傳值

## [relational database](https://youtu.be/LfaMVlDaQ24?t=59576)

SQL的用途:CRUD => Create Read Update Delete

使用sqlite3命令列工具來建立/開啟資料庫檔案

執行這個指令後將進入sqlite程式 這樣就可以藉由sqlite程式在資料庫中執行SQL指令

指令前面的.是sqlite 也就是輕量版的sql特有的 sqlite不是真正的sql 標準的sql指令不需要.

`.mode csv`代表設定sqlite輸出結果的顯示方式為csv模式 這樣查詢結果將以csv格式顯示

`.import FILE TABLE`代表上傳csv檔案到sqlite中 並自動將其內容轉換成SQL database

`.schema`代表顯示資料庫中所有表格的創建語句 所以會顯示上一個自動建立資料庫指令的結果 => 如果不存在就建立資料庫 資料庫名稱是"favorites" 括號內則是欄位以及欄位型別

SELECT、FROM、WHERE...等sql keyword建議使用全部大寫 以提高查詢語句的可讀性

SELECT語句會幫我們打開檔案 => 歷遍內容 => 印出內容

sql中也有函數

如果不用csv模式就會這樣出現格線

查詢結果會被存儲在記憶體中的暫時性表格中 這個暫時性表格僅在查詢執行期間存在 當查詢結束就會被釋放

可以用AS為欄位建立別名

WHERE:用於過濾資料
LIKE:用於模糊搜尋
ORDER BY:用於排序
LIMIT:用於限制返回的資料筆數
GROUP BY:用於分組

sql中的字串通常是使用''包起來

sql中直接使用AND跟OR來組合多個條件

GROUP BY
ORDER BY

LIMIT

INSERT

UPDATE 要注意如果沒有設定條件的話 就會更新到全部的資料

DELETE 一樣注意如果沒有設定條件的話 就會刪除到全部的資料

資料表關係圖

sqlite有5種型別:

BLOB:binary large object 二進制數據型別 例如圖像或文件
INTEGER:整數
NUMERIC:特殊格式的數字 例如日期
REAL:浮點數
TEXT:字串

欄位的屬性附加條件:

NOT NULL:不允許儲存空值
UNIQUE:不允許有重複值

連接不同的資料表

## [index](https://youtu.be/LfaMVlDaQ24?t=63880)

用join的速度會比較慢 所以如果需要經常查詢特定欄位 可以為該欄位建立索引 這樣就可以提高查詢速度

sqlite的特殊功能 用`.timer on`可以顯示sql指令的執行時間

建立索引

指令執行後 sqlite會在資料庫的記憶體中建立一個B-tree (Balanced Tree) B-tree是一種比二分樹更有效率的結構

B-tree跟二分樹的差別在於 每個節點可以有兩個以上的子節點 這樣高度就會比較低 可以減少操作次數

可以發現查詢速度顯著提升了

如果索引可以讓查詢變快 為什麼不全部欄位都建索引? => 因為B-tree會佔用掉太多空間 而且每當進行插入、更新或刪除操作時 索引也需要被更新 所以索引太多可能會影響寫入效能

## [回到最初的範例](https://youtu.be/LfaMVlDaQ24?t=64363)

execute()會傳回一個字典的列表 每個字典代表查詢結果的一行資料 字典中的key值是sql查詢結果的SELECT欄位名稱 value值則是該欄位的實際資料值 如果沒有資料會回傳一個空的列表

想要把變數插入sql指令時 不應該用格式化字串 而是應該用佔位符 這樣可以防止SQL注入攻擊

## [race condition](https://youtu.be/LfaMVlDaQ24?t=64949)

當同時有大量資料訪問資料庫時 操作的順序就很重要 在多執行緒環境中 沒有適當的同步措施的情況下 可能會出現競態條件 (race condition) 從而導致意外

假設很多人同時給一篇貼文按讚 要更新貼文的按讚數時 如果沒有合適的同步機制 不同的按讚操作可能會彼此干擾 導致按讚數更新的過程中出現錯誤

可以用transaction來解決 也可以用lock來解決 但是lock會嚴重拖慢整個程式的速度 現在不常用

transaction可以讓sql指令原子化 (atomic) 意思事務中的操作是要嘛全部執行 要嘛全部不執行

## [SQL injection attacks](https://youtu.be/LfaMVlDaQ24?t=65477)

\-\-在SQL中是單行註解的開頭標記

如果用F-string的方式

此時惡意輸入的'\-\-會完成檢查帳號的指令 並使後面的指令變成註解 這樣密碼就不會被檢查到了

正確做法是使用佔位符 透過程式庫或框架提供的參數化查詢方法處理特殊字符 這樣就可以避免直接被插入危險的字符到sql指令中


# Lecture 8 - HTML, CSS, JavaScript

[回到目錄]

## [TCP/IP](https://youtu.be/LfaMVlDaQ24?t=66212)

路由器可以理解成電腦 或是伺服器 之間透過有線或無線連接以便讓資料可以從A點傳送到B點 現在路由器遍布全球 所以我們可以輕鬆的連接到世界各地的系統

為了從一個路由器傳送資料到另一個路由器 就需要做出路由決策 這部分通常是互聯網服務供應商 (internet service providers, ISPs) 負責處理的 而一些更大的實體 (例如大公司或國家) 則負責將大多數的資料從A點送到B點

路由器簡單說就是互相連接的伺服器 一個路由器要傳送資料到另一個路由器有很多種路徑 這樣如果途中某個路由器過於忙碌時 就可以改使用別的路由器

網路中的路徑決策是透過協定 (protocol) 完成的 這個協定的名稱是TCP/IP 所謂協定就是一連串的條件 這樣電腦就知道在什麼情況下應該做什麼事

IP (Internet Protocol) 是告訴電腦如何表示在網路上的地址的協定 也就是說IP決定了每台電腦都有一個自己的地址 這個地址的格式是#.#.#.# 每個#都是一個十進位數字 最小是0 最大是255 也就是8 bits的大小 所以IP的大小是32 bits 差不多有40億種組合 但其實這樣不算很多 所以現在有更新的第6代IP是128 bits的大小 在數據傳輸過程中 每個數據包都會有接收者的IP跟要發送者的IP 這樣伺服器就知道要把數據從哪裡送到哪裡

TCP (Transmission Control Protocol) 是負責數據傳輸的協定 為了區分不同服務的類型 人們將網路上可用的不同服務賦予不同的數字 其中一種服務就是Web 常見的Web服務用80代表HTTP 443代表HTTPS 這個數字稱為埠號 所以數據包上會有埠號 (port number) 來代表發送者的應用程序希望數據包被如何傳送 每個應用程序都可以選擇一個特定的埠號 這樣伺服器就可以區分訊息、影片、視訊...各種不同的要求

TCP做的另一件事是把圖片或影片等大型檔案分割成碎片並分配編號 這樣如果中途某個碎片被忽略了 接收者就可以發出訊號要求發送者重新發送特定的碎片 而不需要重新傳輸整個檔案 同時把檔案碎片化也可以讓不同人同時下載一個檔案 因為不同的人可以同時下載一個檔案的不同部分

## [DNS](https://youtu.be/LfaMVlDaQ24?t=67206)

因為要記IP地址會很麻煩 為了方便人類使用容易記憶的域名便有了DNS

DNS (Domain Name System) 是一群網路上的伺服器 專門用來將域名轉換成IP地址 有些根DNS伺服器會知道世界上所有的頂級域名 (例如`.com .net .edu`等) 還有一些小型DNS伺服器來自於公司、大學或家用路由器 這些本地DNS伺服器 也就是更快的DNS伺服器 它會記憶使用者最常用的IP地址 這樣當再次查詢相同域名時 就無需向更大的DNS伺服器發送請求 提高了速度和效率

在DNS伺服器裡面有一個對照表 key值是完全合格的域名 (www.google.com) value值則是對應的伺服器的一個或多個IP地址 (一個伺服器可能有多個IP地址 這樣當某個IP地址不可用時 仍然可以使用其他可用的IP地址)

域名

完全合格的域名

## [HTTP](https://youtu.be/LfaMVlDaQ24?t=67388)

在使用瀏覽器訪問網站時 一般瀏覽器會自動在域名前面加上HTTP或HTTPS來形成完整的URL

HTTP代表超文本傳輸協定 (Hypertext Transfer Protocol) 是網際網路通信的應用層協定 因為Web是運行在網際網路上的伺服器 而HTTP則是Web使用的主要協定 負責在客戶端和伺服器之間傳輸超文本資訊 <=> TCP/IP是在網際網路通信中的基礎協定套件

如果網址是`xxx.com` 其實在最後隱含了一個/ 也就是說真正的網址是`xxx.com/` 代表伺服器的根 或是預設的資料夾或頁面

網址也可以是路徑 可以在網址後面用/來指定資料夾或頁面

也可以指定資料夾裡的頁面

com是頂級域 (Top Level Domain, TLD) 之一 一開始代表商業組織 但現在已經被廣泛使用於商業以外的其他領域 其他頂級域還有edu代表教育機構 net代表某種網路 gov代表美國政府

還有國家代碼頂級域 (Country Code TLD, CCTLD) 例如uk或jp 每個國家都有自己的2個字母代號 例如cs50.io跟twitch.tv的io跟tv都是國家代碼頂級域 但因為io常用於代表input/output 而tv代表television 所以現在被廣泛應用於其他非國家用途

www是網站的主機名 (host name) 但不是必要的 所以有些網站可能直接使用域名 而不需要主機名

https是協定名稱 用來告訴瀏覽器要用什麼協定去訪問網站

localhost代表自己的電腦 電腦除了互聯網服務提供商分配的IP地址外 還有一個特殊的IP地址127.0.0.1 會永遠指向自己 這樣就可以在自己的電腦上進行測試和開發

當使用者通過瀏覽器訪問網站時 瀏覽器會發送HTTP請求給網站的伺服器 網站伺服器如何知道怎麼回應使用者的要求? => 使用者發送的HTTP請求中的開頭會有文字訊息代表HTTP方法 常見的有GET跟POST GET是取得資料 POST是提交資料

HTTP請求通常長這樣
第一行是HTTP方法 / HTTP/HTTP的版本
第二行則是host: 完全合格域名 這是為了避免同一個伺服器同時有多個域名時搞混

HTTP回應通常長這樣
第一行是HTTP/HTTP的版本 狀態碼 OK
第二行的HTTP header表示內容類型是text/html

curl用來發送HTTP請求並顯示伺服器的回應
可以看到伺服器回應了版本是HTTP/2 狀態碼是200
下方的標頭可以看到內容類別是text/html 字符集是UTF-8

如果改用http協定而不是https協定的話就會失敗
回傳的狀態碼是301 代表永久重定向 新位置是`https://www.harvard.edu/`

不過在瀏覽器中輸入`http://www.harvard.edu/`還是會成功 因為瀏覽器如果發現狀態碼是301時會自動導向到新位置

如果不給主機名的話也是一樣 伺服器會先希望你改用https

改用https之後 伺服器就會導向補齊主機名的正確地址 這有助於確保所有的訪問都是安全的

還有這些常見的狀態碼:

3XX代表重新導向
4XX代表用戶端錯誤 就是請求中存在錯誤 例如403代表未經授權 需要登入
5XX代表伺服器錯誤 例如503代表伺服器無法使用 通常是由於超載、維護或被攻擊等原因導致的

可以看到`google.com/search?q=dogs`中 網址之後用?來代表查詢字串開始 後面則代表參數q的值是dogs

## [HTML](https://youtu.be/LfaMVlDaQ24?t=69062)

HTML有兩個重要的基本概念:

標籤 (tags)
屬性 (attributes)

`<!DOCTYPE html>`是HTML文檔中的聲明 (document type declaration) 告訴瀏覽器用HTML5來解析文檔

`<html lang="en">`中 `<html>`是標籤 `lang="en"`是屬性 屬性提供標籤的額外信息 可以修改標籤的默認功能 `<html>`內部包含的各個部分稱為html元素

可以把html元素之間的關係理解成一種呈現樹狀結構的父子關係

因為html在渲染時會合併連續的空格和換行 所以在網頁上只會被解析為一個空格 因此需要用`<br>`來換行

之後是演示各種html元素的效果 建議自己看

比較特別的是這個video元素

把游標懸停在超連結上面時 左下角會出現該連結的URL 可以用這個方式來避免釣魚攻擊

如果在手機上瀏覽網頁發現字太小 加上這一行就可以使畫面根據設備的螢幕大小進行適應

`name="viewport"`代表這是設置viewport的meta元素 viewport是指瀏覽器用來渲染網頁的可見區域
`width=device-width`表示設定瀏覽器的viewport寬度等於裝置的寬度
`initial-scale=1`表示設定初始的縮放比例為1 讓網頁在載入時以正常比例顯示 不進行自動縮放

透過設定開放圖形協定 (Open Graph Protocol, og) 可以控制超連結在社交媒體平台或其他網站上的預覽資訊 包括標題、描述及圖片

可以在網址後面用?開始加入參數 如果有多個參數 則參數之間用&分隔

表單的運作原理:

提交表單時 瀏覽器會前往指定的action URL 並將表單數據附加到URL的查詢字串中

預設的方法就是GET 所以其實不用特別指定方法

但可以設定按鈕的文字 以及輸入框自動完成功能、自動設定焦點及輸入框內的提示文字

## [CSS](https://youtu.be/LfaMVlDaQ24?t=72101)

透過style可以直接在元素中設定樣式 並且用字符實體來表示特殊字符 例如`&#169;`代表版權符號©

子元素會繼承父元素的樣式

全部都用div的話會不好理解 這時可以用語義標籤 (Semantic tag) 雖然樣式還是跟div相同 但有助於描述文檔的結構和含義 因此當google之類的搜尋引擎在使用爬蟲探索網頁的內容時 可以通過分析語義標籤來獲取關於網頁結構和內容的更多信息 也可以幫助視覺障礙者在使用屏幕閱讀器 (screen reader) 瀏覽網頁時 可以更快理解網頁結構

把元素跟樣式都寫在html裡面會不好維護 所以可以透過把樣式移到header的style裡面把元素跟樣式分開 並且通過class創造出可重複使用的樣式

這樣在html的部分只要指定類別就可以使用對應的樣式了

我們可以進一步把樣式移到外部的css檔案裏面

css檔案裏面長這樣

## [framework](https://youtu.be/LfaMVlDaQ24?t=73223)

透過引入框架 例如bootstrap 並在元素中指定對應的類別 就可以使用別人寫好的漂亮樣式

## [JavaScript](https://youtu.be/LfaMVlDaQ24?t=73340)

JS可以使用條件式

也可以用變數

JS相較python 語法更接近C 當然也有迴圈

透過JS可以動態改變html元素 稱為DOM操作

DOM是一個表示文檔結構的樹狀結構 由html元素組成 每個html元素都被轉換為DOM中的一個節點 瀏覽器會自動將html文件轉換成DOM並存在記憶體中 一旦DOM建立完成 JS就可以使用DOM提供的方法和屬性來訪問和操作文檔的內容

JS中有很多事件可以使用

onsubmit指定表單提交時要執行的JS函數
return false告訴瀏覽器只要呼叫函數就好了 不要真的提交表單 防止頁面重新載入

當然 把JS從html文件中獨立出來也是更好的做法

因為html文件是從上到下逐行解析 所以如果JS使用了DOM中的元素 但這些元素還沒有被解析和建立就會導致錯誤 因此如果要把JS放在header裡面 要把程式包在DOMContentLoaded事件的監聽器中 DOMContentLoaded事件表示當html文件解析為DOM之後才會觸發

最後再把js移到外部的檔案中

js檔案裡面長這樣

下面還有一些範例演示 建議自己看

# Lecture 9 - Flask

[回到目錄]

## [複習](https://youtu.be/LfaMVlDaQ24?t=75733)

複習一下HTTP請求:
第一行是HTTP方法 / 請求的路徑 HTTP/HTTP的版本
第二行則是host: 完全合格域名

## [flask](https://youtu.be/LfaMVlDaQ24?t=75943)

執行flask run時 Flask會啟動一個本地開發伺服器 這樣就可以在瀏覽器中查看

要使用flask 至少需要一個python檔案跟一個templates資料夾

templates資料夾是用來放html模板的

一般還會有一個requirements.txt跟static資料夾

requirements.txt是用來列出所有要使用的第三方程式庫 這樣伺服器就會自動下載
static資料夾是拿來放圖片、CSS及JS之類的靜態資源

`__name__`是一個特殊的變數 代表當前的檔案 這個變數的值取決於檔案是作為主程序運行還是被導入到其他檔案中 如果作為主程序運行 則`__name__`的值為`__main__`

`app = Flask(__name__)`代表把當前的檔案轉換成Flask應用程式

`@app.route("/")`是一個裝飾器 代表定義應用程式的預設路徑 此時會執行下方的函數

上面的寫法只會顯示字串而已 如果要渲染整個html模板 就可以透過render_template函數去templates資料夾中找到指定的html檔案

`request.args`是一個特殊的變數 用來儲存url查詢字符串 (query string) 的參數 這些參數是以key-value對的形式儲存

這樣就可以尋找查詢字符串中有沒有name 如果有的話就取出 沒有就預設為world

render_template函數中要記得指定模板中的佔位符及其要插入的變數 (這邊是為了要示範才另外取一個名稱 一般通常會用一樣的名稱)

模板中要用兩個大括號把變數包起來

不想寫那麼複雜的話 可以直接用`request.args.get('name', 'world')` 第一個參數代表要找的參數名稱 第二個參數則是找不到時的預設值

我們重新改一下html模板

增加另一個模板

增加一個路由

## [layout](https://youtu.be/LfaMVlDaQ24?t=77606)

現在網頁運作正常了 但是每個模板都要重新寫一次html很麻煩 這時就可以用layout來解決

先建立一個layout.html 把要替換的部分改成`{% block body %}{% endblock %}` 其中body是自己命名的 用來代表這個區塊的名稱

要插入的html中 首先要透過`{% extends "layout.html" %}`聲明要插入的layout檔案 然後把要插入的元素放在`{% block body %}{% endblock %}`裡面

這樣在網頁的原始碼中就可以看到組合後的完整html

## [POST](https://youtu.be/LfaMVlDaQ24?t=78104)

為了避免資料直接顯示在網址中 在處理密碼、信用卡帳號...等敏感訊息時 就要用POST方法來把資料送到伺服器裡 另外因為網址的長度有上限 所以比較大的檔案數據也要用POST發送

POST方法將數據放在請求的主體中 這樣可以避免直接將敏感信息暴露在網址中 同時可以處理較大的檔案數據 這對於需要安全地傳輸敏感信息或大量數據的情況非常重要

但如果像上面那樣直接改的話 會出現405錯誤

405錯誤代表請求方法不允許 因為預設情況下app.py只支持GET方法

所以要在伺服器端的應用中允許POST方法 => 在裝飾器將methods參數改成POST

可以在網路 => 請求 => Payload (承載) 看到POST發送的值

為了要避免設定太多路徑 接下來嘗試把`/`跟`/greet`兩個路徑合併一下

首先把index畫面的表單提交路徑改成自己 不過預設就是自己 所以`action="/"`可以省略

接著改裝飾器的部分 如果請求是GET就到index.html 如果請求是POST就導到greet.html

這樣在重新整理的時候就會跳出通知詢問是否要重新提交表單 因為POST是用來提交資料對伺服器 甚至資料庫進行修改 而GET則是單純用來取得資料

如果單純要回到一開始的輸入頁面 只要點網址欄按enter就會用GET回到輸入畫面了

另外要注意的點是 在Flask中`request.args`只能用在GET

POST要用`request.form`

這樣才是正確的app

## [示範](https://youtu.be/LfaMVlDaQ24?t=78931)

先重新完成一個簡單的app

以及一個簡單的模板 不過現在還沒有/register的路徑 所以提交時會返回404

加上/register的路徑 不過現在還沒有success.html

先製作layout.html

然後把index.html也改一下

再加上success.html

/register要改成POST

接著把表單提交的資料放進字典裡 並且增加一個模板來呈現字典裡的資料

模板裡面這樣寫

但結果會發生錯誤 => 因為列表跟函數的名稱一樣

改一下名字

表單的選項忘記寫name了

回到終端機 先用ctrl+C終止程式運行把字典裡的紀錄清除 再用flask run重新啟動 就可以看到結果了

但現在的程式可能會有資安問題 因為所有使用者都可以看到並修改html

解決方法 => 我們先增加一個運動項目列表 並且將其放進index.html中

把index.html的選項改成動態產生

並且在register()中增加檢查 沒填名字或運動項目不在列表中就會導向失敗頁面

上面在伺服器檢查的方法會比在表單的欄位上增加required來的好

因為雖然用required方法 瀏覽器會幫我們提示

但使用者可以自己把required刪掉!!!!!

欄位驗證分成客戶端驗證跟伺服器端驗證 在客戶端驗證會比較使用者友好 但其資料是不可信任的 程式設計師不應該相信使用者提交的任何資料 所以無論如何都要進行伺服器端驗證

當flask停止運行時 我們存在字典裡的資料就會消失

我們可以改成用資料庫來儲存資料

在登記時 改成用INSERT來新增資料

並且在下方用redirect來導向另一個路徑

這樣就算flask停止運行 資料庫中的資料依然會存在

在刪除資料的部分 是透過一個隱藏的表單完成的

對應的程式是去取得表單提交的id 如果id是真的數字就刪除對應資料 並且重新導回列表頁面

但這樣做還是有風險 因為雖然欄位是隱藏的 但還是可以在原始碼中修改參數 => 加入身分驗證 讓成功登入的人可以刪除自己的資料

## [示範-cookie](https://youtu.be/LfaMVlDaQ24?t=81761)

程式如何得知使用者的登入狀態 => cookie

第一次成功登入時 就像去遊樂園在進場時會在手上蓋章一樣 每次點擊同一個網站的不同連結時 使用者的瀏覽器就會向網站展示蓋章 這個蓋章就是cookie

cookie是在使用者成功登入時由伺服器設定的一個小段資訊 存在於使用者的瀏覽器中 每當使用者訪問網站的不同頁面或連結時 瀏覽器會將這個cookie帶到伺服器 以示這是同一位已經登入的使用者

我們在這邊先假設一個發送給gmail的http請求

如果身分驗證成功 在http回應的標頭中會有一個Set-Cookie欄位 用來在瀏覽器中建立key-value pair結構的資料 也就是cookie

之後在訪問網站的不同頁面時 瀏覽器發出的http請求都會包含這個cookie

## [示範-session](https://youtu.be/LfaMVlDaQ24?t=82061)

這樣當使用者想刪除自己的資料時 我們就可以檢查登入者的cookie跟他要刪除的資料 在確認無誤後進行刪除動作 這一系列用來驗證使用者並處理相應數據的步驟被簡稱為session機制

flask除了會自動處理/驗證cookie 還提供了session這個抽象化工具 session是一個字典 它是伺服器端用來儲存與特定使用者相關資訊的地方 任何存放在session裡的資料會在相同使用者登入時重新出現

flask確保了網站在透過cookie驗證使用者身分後 網站會使用對應使用者的session資料 簡而言之 Flask的session機制是透過cookie實現了網站在用戶身份驗證後保留使用者狀態的功能

8-10行就是在伺服器端儲存session資料

網站如何記住使用者的 => 如果在session中沒有name資料 就重新導向/login路由 如果有就渲染index模板

我們在index模板中可以通過檢查session中是否有name資料來呈現對應畫面

為了簡化login模板 所以只有一個名稱欄位 不需要輸入密碼

/login路由會呼叫login函數 其中會判斷HTTP請求的方法 如果是POST就會把名字存放到session中 並導向到預設路由 如果是GET就單純顯示畫面

logout函數則是把session中的name資料清空

## [示範-綜合](https://youtu.be/LfaMVlDaQ24?t=82452)

加入購物車時先建立一個叫做cart的session欄位 並將其型別設定為列表
請求是POST時 如果回傳的商品id存在 就把該商品加入到cart中
請求是GET時則直接導向畫面顯示cart中的商品

sqlite中可以用(?)把列表放進sql查詢中 sqlite會自動把列表轉換成sql的查詢語句

預設情況下 session跟cookie都會在瀏覽器關閉後清除 但也可以自己設定過期時間 例如像gmail可能就會設定比較長的時間 不然每次關閉瀏覽器後都要重新登入太麻煩了

## [API](https://youtu.be/LfaMVlDaQ24?t=82969)

所有C、SQL、Python...的函數都是API (Application Programming Interface) 應用程式介面 因為所有函數都有標準的接口和用法 例如參數、名稱及返回值 API就是定義了如何使用這些函數 也可以說API是定義如何與服務進行互動的標準

因此現在有許多線上服務提供API 允許使用者透過URL來取得資料 這種通信通常使用HTTP作為標準的機制

這是一個根據名稱搜尋節目函數

注意模板中只有li元素的列表而已 沒有layout也沒有ul 這樣其他人拿到這些資料後就可以插入到自己的html裡面

在index中可以看到input每次輸入都會觸發一個非同步的函數 非同步的意思是因為這個函數可能會花一點時間去執行 所以讓它在背景執行 而不會等待該函數完成後再繼續執行下一個操作

這個函數會先透過fetch去呼叫/search路由 其中await表示這邊會等結果傳回來後再執行 而等待過程中其他部分會繼續執行 最後把結果放進ul元素中

## [JSON](https://youtu.be/LfaMVlDaQ24?t=83586)

但是拿到一堆li元素也不好 其他人如果想要把資料轉成PDF或者放到表格裡的話會很麻煩 應該要使用一個更通用的格式 而現在最常用的通用格式就是JSON (JavaScript Object Notation)

這是用JSON格式傳回的結果 雖然看起來很亂 但已經夠電腦去處理資料了

可以看到最外面是一個用[ ]包住的列表 列表裡面則是一個一個用{ }包住的字典 字典裡面用"key":value的方式儲存資料

這次index是這樣把JSON資料轉成html的

# Lecture 10 - Emoji

[回到目錄]

常見的命令列工具

git教學
[連結](https://youtu.be/MJUJ4wbFm_A)

運行網站

運行應用程式

更多學習資源

cs50課程自己的網站
[連結](https://cs50.harvard.edu/x/2024/communities/)

## [小測驗](https://youtu.be/LfaMVlDaQ24?t=86162)

















## [來賓演講 : Emoji是怎麼來的]()

講師 : Jennifer 8. Lee
[講師網站](https://www.jennifer8lee.com/)

Zero Width Joiner (ZWJ) 是Unicode中的一個特殊字符 它的作用是指示相鄰的字符應該形成一個 Emoji ZWJ序列 系統就知道這是一個組合的Emoji

因為不是所有語言都是從左至右書寫 所以Emoji的方向也有爭論

# Cybersecurity

[回到目錄]

## [密碼](https://youtu.be/LfaMVlDaQ24?t=90509)

最常用的一些密碼

4-digit passcode (四位數密碼) 是一種常用的密碼機制 但其安全性相對較低

brute-force attack (暴力攻擊) 是通過不斷嘗試所有可能的組合來找到正確的密碼

四位數密碼共有10\*10\*10\*10種可能 也就是10,000種組合 可以透過程式輕鬆列出所有組合來實現暴力攻擊

如果我們改成4-letter passcode (四字母密碼) 並且區分大小寫 那就會有52\*52\*52\*52種可能 也就是7,311,616種組合

如果我們再改成4-character passcode (四字符密碼) 除了大小寫字母 再加入數字跟標點符號 那就會有94\*94\*94\*94種可能 也就是78,074,896種組合

最後如果我們再改成8-character passcode (八字符密碼) 那就會有94\*94\*94\*94\*94\*94\*94\*94種可能 也就是6,095,689,385,410,816種組合

現在就很難用暴力攻擊的方式破解密碼了 或者說要破解密碼的成本變得很高 事實上我們只要讓我們的密碼比別人的密碼安全就好 因為安全性是比較出來的 我們很難達到絕對的安全 但我們只要相較多數人安全就可以大大減少被攻擊的風險

當然用這種密碼的代價就是不好記 但透過帳戶鎖定機制 就可以在密碼長度不變的情況下 把破解所需的時間拉長 但如果真的是用戶忘記密碼 那就會變得很麻煩 所以在設計時必須找到安全性跟易用性的平衡點

另一個常用的機制是two-factor authentication (雙因素身份驗證) 也就是必須在限定時間內到信箱或簡訊取得驗證碼 也就是說攻擊者除了破解密碼 還必須在物理上訪問用戶的設備或擁有用戶的手機號碼或信箱存取權 這樣就可以增加攻擊的難度

但這樣做的缺點是 如果用戶忘記帶手機 那用戶就沒辦法驗證了 => 在設計時必須找到安全性跟易用性的平衡點

要提高安全性還有其他的方法 例如password manager (密碼管理工具) 密碼管理工具不但可以生成安全性更高的密碼 還會記住這些密碼 並在登入時自動填入 不過使用密碼管理工具的前提是要保護好主密碼 因為如果主密碼被破解了 那其他密碼就會暴露在風險下

為什麼不要在不同網站使用同樣的密碼 => 一旦其中一個網站的密碼被泄露 攻擊者就有機會用相同的密碼訪問其他網站 這種現象被稱為連鎖攻擊 會迅速擴大安全風險

這些是常見的密碼管理工具

另一個提高安全性的常用方法是encryption (加密) 這樣理論上可以確保只有發送者跟接收者可以解密並讀取原始資訊 一種簡單的加密方式就是之前提過的凱薩密碼

生活中經常使用到加密 例如`https://` 其中的s代表secure 也就是說數據在傳輸過程中是加密的

另外還有end-to-end encryption (端對端加密) 端對端加密確保只有接收端能夠解密並閱讀數據 中間的任何節點 (例如服務提供商、網絡提供商等) 都無法解讀數據

雖然https也是加密的 但這只能確保用戶瀏覽器和網站伺服器 以及網站伺服器到接收者瀏覽器之間的傳輸是加密的 但是一旦數據到達伺服器 伺服器就能夠解讀該數據 這樣就可能被服務提供商或其他中介機構訪問未加密的資料

但端對端加密也有缺點 端對端加密通常會導致某些功能無法實現 因為這些功能可能需要在服務提供商的伺服器上處理數據

例如說如果要使用zoom提供的線上錄影或即時翻譯功能 就不能用端對端加密不讓zoom訪問內容 這時用普通的加密就可以在確保安全性的同時讓zoom還可以訪問內容

full-disk encryption (全磁碟加密) 意思是理想上將硬碟中的全部數據進行加密 確保硬碟上存儲的所有內容都受到保護 這樣即使硬碟被盜或遺失 未經授權的人仍然無法訪問數據 但是這樣做的缺點是速度可能會變慢

一些常見的全磁碟加密方案包括windows的BitLocker和macOS的FileVault

另外一個全磁碟加密可能導致的問題是 除了我們可以加密資料以外 攻擊者也可以加密我們的資料 然後不告訴我們密碼 以便進行勒索 這就是ransomware (勒索軟體) 攻擊的一個典型情境

=> 全磁碟加密可以提供保護 但如果攻擊者能夠取得存取權限 那就可以用這種能力進行惡意行為

最後要說的是incognito mode (無痕模式) 無痕模式通常跟加密無關 而是跟網路隱私有關 也就是說無痕模式無法防止服務供應商得知使用者訪問的網站 但無痕模式可以防止在公共電腦上保留個人資訊 因為無痕模式會在瀏覽器關閉後清除本地資訊 包括cookie跟session

[cs50其他課程的線上教學網站](https://www.edx.org/cs50)