# 目錄
- [CH1 計算機簡介](#CH1-計算機簡介)
- [CH2 數位資料表示法](#CH2-數位資料表示法)
- [CH3 計算機組織](#CH3-計算機組織)
- [CH4 作業系統](#CH4-作業系統)
- [CH5 電腦網路](#CH5-電腦網路)
- [CH6 網際網路](#CH6-網際網路)
- [CH7 網路應用](#CH7-網路應用)
- [CH8 網路安全](#CH8-網路安全)
- [CH9 程式語言](#CH9-程式語言)
- [CH10 資料結構](#CH10-資料結構)

## CH1 計算機簡介
- IBM 1924年
- IEEE 1963年 國際電機電子工程師學會
- IEEE 802.11 無線網路wifi標準
- Turing Award 1966年
---

### 圖靈獎得主
| 高德納 | Donald Knuth | |
| - | - | - |
| 姚期智 | Chi-Chin Yao | 2000年 華人 |
| 羅納德林 | ==Ronald Rivest== | RSA加密 |
| 薩莫爾 | ==Shamir== | RSA加密 |
| 阿德曼 | ==Adlemon== | RSA加密 |
| 惠特菲爾德 | Whitfield | 公開金鑰加密 |
| 馬丁赫爾曼 | Martin Hellman | 公開金鑰加密 |
| 辛頓 | Hinton | 2018年 物理獎 AI |
| 楊立昆 | Yann Lecun | AI |
| 班吉歐 | Bengio | AI |
---

### 馮紐曼架構 John von Neumann
1945年 介紹儲存程式

| 記憶體 | Memory |
| - | - |
| 算數邏輯單元 | ALU (Arithmetic Logic Unit) |
| 控制單元 | CU (Control Unit) |
| 輸入/輸出 | I/O |

>[!Important]
>中央處理器CPU (Central Processing Unit)
>由算數邏輯單元及控制單元組成
>==CPU = ALU + CU==


### 電腦四大時期
1. 真空管
2. 電晶體
3. 積體電路
4. 超大型積體電路
---

### 摩爾定律
積體電路上可容納的電晶體數目，約18~24個月會增加一倍。

## CH2 數位資料表示法
- 數位 Digital 不連續變化
- 類比 Analogy 連續變化

| 十進位 | Decimal |
| - | - |
| 二進位 | Binary |
| 八進位 | Octal |
| 十六進位 | Hexadecimal |
---

### 位元 Bit
Byte : 位元組
bit : 位元
- ==1Byte = 8bits==
- KB < MB < GB < TB
- 2^30^KB = 2^20^MB = 2^10^GB = 1TB
---

### 一補數1's Complement
- 範圍 : -127 ~ ±0 ~ 127
>[!Note]範例
>(40)~10~ -> (00101000)~2~
>(-40)~10~ 取反-> (11010111)~2~
---

### 二補數 2's Complement
- 範圍 : -128 ~ +0 ~ 127
>[!Note]範例
>(40)~10~ -> (00101000)~2~
>(-40)~10~ 取反-> (11010111)~2~ 再加1-> (11011000)~2~

>[!Tip]速解
> (-40)~10~ 右邊第一個1當分界線，==左邊0轉1、1轉0，右邊不變==
> (00101000)~2~ -> (11011000)~2~
---

### 溢位 Overflow
- 兩==正數==相加，符號位元為1
- 兩==負數==相加，符號位元為0
---

### 浮點數表示法
- IEEE 754
- ==過剩127==方式
1. 單精度
32位元 -> 1個符號，==8==個指數，23個尾數
2. 雙精度
64位元 -> 1格符號，==11==個指數，55個尾數

>[!Note]範例
>10110.100011 標準化-> 1.0110100011x2^4^
>過剩127 -> 4 + 127 = ==131==
>(131)~10~ -> (10000011)~2~
>最終 -> 0 ==10000011== 01101000110...000
---

### ASCII
- A = 65
- a = 97

## CH3 計算機組織
### 中央處理器 CPU (Central Processing Unit)
- 電腦的大腦。
- 由==算數邏輯單元 ALU 和控制單元 CU== 組成。
---

### 暫存器 Register
- 速度比主記憶體快

---

### 控制單元 CU (Control Unit)
控制電腦執行程式的流程
---

### 算術邏輯單元 ALU (Arithmetic Logic Unit)
負責計算加法、減法、乘法、除法等數學運算。

>[!Note]XOR資料遮罩範例
>DATA為==11010110==
>MASK為00101100
>做XOR運算後為11111010
>再做一次可回復資料==11010110==
---

### 匯流排 Bus
- 系統匯流排 (CPU與記憶體間的資料傳送)
- 控制匯流排 Control bus
- 位址匯流排 address bus
- 資料匯流排 data bus
- 擴充匯流排 (使用者彈性使用)
- USB、PCI...
>[!Warning]
>USB最多支援127台設備
---

### 記憶體 Memory
#### RAM (隨機存取記憶體)
斷電後資料會消失
- SRAM (靜態隨機存取記憶體)
- 速度快、價錢高
- 不需做更新動作
- 正反器
- DRAM (動態隨機存取記憶體)
- 速度慢、價錢低
- 需做週期更新
- 電容器
---

#### ROM (唯讀記憶體)
斷電後資料會保存，可用來儲存開機程序。
---

#### Main Memory (主記憶體)
速度比快取記憶體慢，但比硬碟快。

---

### 執行程式
fetch -> decode -> execute
- 擷取 (fetch)
- 解碼 (decode)
- 執行 (execute)

>[!Tip]生產線技術

## CH4 作業系統
扮演使用者與電腦硬體的中間人
### 功能
- CPU排班 (Scheduling)
- 記憶體管理 (Memory Management)
- 檔案管理 (File Management)
- I/O 管理
---

### 操作介面
- 圖形介面 (TUI)
- 操作簡單
- 效能較差
- 文字介面 (GUI)
- 操作較困難
- 效能較好
---

### 常見作業系統
- Windows
- MasOS
- Linux
- DOS
---

### 演進
- 批次處理 (Batch Processing)
- 一次處理整批資料，CPU閒置長。
- 多程式規劃 (Multiprogramming)
- 記憶體載入多個程式，當等待IO時切換。
- 可能造==死結== (Deadlock)
- ==分時系統== (Time-sharing)
- 將CPU時間切成==許多微小片段==，造成==多工==假象。
---

### CPU 排班演算法
- 先到先處理 (FCFS)
- 最短工作先處理 (SJF)
- ==平均等待時間最短==
- ==可能造成飢餓 (Starvation)==
- 優先權排班 (Priority)
- ==可能造成飢餓 (Starvation)==
- 依序循環 (Round Robin)
- 每個程式分配固定時間片段
- 時間到將內容及狀態寫進程序控制表 (PCB)
- 適合==分時系統==
- 二八原則

>[!Tip]二八原則
>20%程序所需時間大於間隔時間
>80%程序所需時間小於間隔時間

>[!Note]平均等待時間計算
>範例為==最短工作先處理==
>執行順序為 P2 -> P3 -> P1
>平均等待時間 (8 + 3) / 3 = 3.67

表1
| 程序 | 所需時間 |
| - | - |
| P1 | 7 |
| P2 | 3 |
| P3 | 5 |

表2
| 程序 | 等待時間 | 平均等待時間 |
| - | - | - |
| P1 | 8 | |
| P2 | 0 | |
| P3 | 3 | 3.67 |
---

### 程序生命週期
1. 新產生
2. 執行
3. 等待 I/O
4. 就緒
5. 結束
---

### 動態載入 Dynamic Loading
常式在被呼叫時才會載入，先檢查使否存在記憶體，若沒有再從硬碟載入記憶體。
---

### 覆蓋 Overlay
讓超過記憶體容量的程式能夠執行。
>[!Note]範例
>- 程式碼A : 80KB
>- 程式碼B : 70KB
>- 符號表 : 20KB
>- 呼叫到的常式 : 30KB
>- 覆蓋驅動程式 : 10KB
>一共 200KB，假設記憶體 150KB
>1. 載入符號表、常式、程式碼A、覆蓋驅動程式共 140KB
>2. 載入程式碼B覆蓋掉A，共130KB

---

### 檔案位置
- 絕對路徑
- 從==根目錄==開始
- 相對路徑
- 從當前目錄開始

>[!Note]路徑範例 (user3 -> hw1.docx)
>絕對路徑 : root/user1/Home-Work/hw1.docx
>相對路徑 : ../user1/Home-Work/hw1.docx

## CH5 電腦網路
### 網路類型
- 區域網路 (LAN)
- 範圍小
- 速度快
- 廣域網路 (WAN)
- 範圍大
- 跨國
---

### 網路拓樸 Topologies
- 匯流排 (Bus)
- 共用一條線
- 一次只能一台傳輸
- 容易發生==碰撞==
- ==CSMA/CD== 機制 (解決碰撞發生的情況)
- 星狀 (Star)
- 透過==交換器==連接
- 常見
- 容易除錯
- 環狀 (Ring)
- ==單向傳輸==
- 故障難找問題點
- 網狀 (Mesh)
- 最常見的區網架構
- 所有訊息需透過==中心點==傳輸
---

### 域名系統 DNS
將網址轉換成對應IP
---

### 傳輸媒介
- 電話線
- ==RJ-11==
- 傳輸速率慢
- 須配合數據機
- 同軸電纜
- 匯流排架構
- 傳輸速度快
- 雙絞線
- ==RJ-45==
- 順序標準
- 568-A 白綠、綠、白橙、藍、白藍、橙、白棕、棕
- 568-B ==白橙、橙、白綠、藍、白藍、綠、白棕、棕==
- 跳線
- 一端使用568A、另一端568B
- 連結兩種同裝置
- 光纎
- 速度最快
- 距離長
- 不受干擾
- ==單向傳輸==
- 電磁波
- 不需線路
- 頻段有嚴格規範
- 2.4GHz、5GHz
---

### ==OSI七層模型==
封包傳輸會進行封裝，每一層會對其增加標頭
傳送資料 應用層 -> 實體層
接收資料 實體層 -> 應用層
1. 實體層 Physical
- 將資料轉硬體訊號
- 傳送單位 : bit
2. 資料連結層 Data link
- 處理區域網路內的連線
- ==IEEE 802.11==
- 硬體位址 Mac Address
- 由 6 ==組 8-bit 的十六進位數字組成==，用以識別硬體裝置
>[!Note]查詢所有網路卡位址
>==ipconfig /all==
3. 網路層 Network
- 資料切割
- 辨識網路位址
- 傳送單位 : 封包
- ==IPv4、IPv6==
- IP位址種類 : A、B、C、D、E

>[!Note]私有 IP 範圍
>Class A : 10.0.0.0 ~ 10.255.255.255
>Class B : 172.16.0.0 ~ 172.31.255.255
>Class C : 192.168.0.0 ~ 192.168.255.255

>[!Tip]路由機制
>路由器透過路徑演算法計算最佳路徑

4. 傳輸層 Transport
- 流量控制
- ==TCP、UDP==
- 多工處理

>[!Tip]TCP / UDP
>TCP
>- 連接導向
>- 三向交握
>- ==可靠傳輸==
>
>UDP
>- 非連接導向
>- 速度快
>- ==不可靠==

>[!Note]常見 port 號
>- FTP : 21
>- SSH : 22
>- DNS : 53
>- HTTP : 80
>- POP3 : 110

5. 會議層 Session
- RPC 允許使用者執行遠端不同的函式呼叫
- RTSP 建立多通道分別傳輸聲音及影像
- SSL 建立多通道傳輸需要加密的文件
6. 表達層 Presentation
- 標準化方式處理使用者資料
- 解碼、解壓縮、加密...
7. 應用層 Application
- 常見通訊協定
- 最貼近使用者

>[!Tip]Email 通訊協定
>- ==SMTP==
>- ==POP3==
>- ==IMAP==

---

### TCP/IP
簡化的OSI模型，只有四層。
1. 網路存取層
2. 網際網路層
3. 傳輸層
4. 應用層

---

### 網路設備
- 網路卡 Network interface card
- 第二層
- 有才能上網
- 中繼器 Repeater
- 第一層
- ==延長網路線長度==
- 增強訊號
- 集線器 Hub
- 第一層
- 匯流排
- 有==碰撞問題==
- 橋接器 Bridge
- 第二層
- ==有線網路 802.3==
- ==無線網路 802.11==
- 交換器 Switch
- 第二層
- 可以建立==硬體實體位址與網路孔連接埠關係==
- 可==減少碰撞發生==
- 路由器 Router
- 第三層
- 封包傳送轉發
- 無線網路存取點 Wireless AP
- 第二層
- 橋接無線網路
---

### 電信網路
- 電話網路
- 線路交換 Circuit Switching
- 電腦網路
- ==封包交換 Packet Switching==

>[!Tip]POTS / PSTN
>市內電話 : POTS (Plain Old Telephone Service)
>公共電話 : PSTN (Public Switch Telephone Network)
---

### 無線射頻技術 RFID
透過特殊讀取裝置，用無線方式讀取。
>[!Note]常見使用
>- 一維碼
>- 二維碼
>- RFID
>- 門禁卡
>- 悠遊卡

>[!Tip]NFC
>基於RFID技術
>短距離、非接觸式通訊

## CH6 網際網路
### [OSI 七層模型](#OSI七層模型)
已補充於CH5
---

### 基本設定與除錯工具
- 連線四要素
- ==IP位址==
- ==網路遮罩 Netmask==
- ==預設閘道 Gateway==
- ==名稱伺服器 DNS Server==

>[!Tip]常用指令
>==ipconfig /all== : 檢查 IP 設定與 MAC 位址
>==ping== : 檢查網路有沒有通
>==nslookup== : 檢查 DNS 解析是否正常
>==tracert== : 追蹤封包路徑
>==netstat -na== : 檢查目前網路連線狀態

>[!Note]網路遮罩範例
>IP : 192.168.001.234
>Netmask : 255.255.255.255
>換成二進位後做 ==AND== 運算
>結果 : ==192.168.001.000==
---

### 網路模擬工具
- Cisco Packet Tracer
- 視覺化呈現[網路拓樸](#網路拓樸-Topologies)與線上學習
- GNS3
- 可模擬複雜的[網路拓樸](#網路拓樸-Topologies)與 VLAN 設定
- 主要以 Emulation 為主，==仿真模擬==
- ==Wireshark==
- 封包分析
- 封包攔截
## CH7 網路應用
## CH8 資訊安全
### 基本原則 : CIA
- 資料機密性 ( Confidentiality )
- ==防止第三人取得資料==
- 資料完整性 ( Integrity )
- ==防止資料被竄改==
- 系統可用性 ( Availability )
- ==確保資料和系統可即時取得==

### 加密 ( Encryption )
把讀取的資料(本文)加以處理，轉為無法讀懂的方法
>[!Important]
>#### 保障「資料機密性」
### 加密可分為 [對稱式密碼 ( symmetric )](#對稱式密碼-(-symmetric-)) 和 [非對稱式密碼 ( asymmetric )](#非對稱式密碼-(-asymmetric-))
---
### 對稱式密碼 ( symmetric )
**加解密用同一組密碼**
#### 範例一 : 位移法
加密時每個字母向前移 N 位
解密時，改往後位移 N 位

>[!Note]範例
>凱薩加密法，即為 N = 3

#### 範例二 : 查表法
密碼有一個對照表，加解密用同一張表

>[!Caution]
>若表被知道，就完了

#### 範例三 : 使用 XOR 運算
文字先轉 ASCII 後再轉二進位，並和密碼做 XOR 運算

>[!Tip]
>XOR 運算 :
>0 * 0 = 0
>0 * 1 = 1
>1 * 0 = 1
>1 * 1 = 0

>[!Note]
>對稱式加密還有更多應用
>1. IDEA
>2. DES ( 被破解 )
>3. AES ( 目前主流 )
>4. RCS
---
### 非對稱式密碼 ( asymmetric )
**加解密用不同密碼**

#### 範例一 : RSA 演算法 ==( 圖靈獎 )==
用質數的因數分解做加解密 ==( Factorization )==

>[!Important]RSA 的算法
>1. 先選兩質數 p , q，算 N = p * q
>2. 算 φ = ( p - 1 ) ( q - 1 )
>3. 從 1 ~ φ ( N ) 中挑一數 e ，需和 φ ( N ) 互質
>4. 找出 d ，滿足「d * e ≡ 1 ( mod φ ( N ) )」

>[!Note]範例
>取 φ ( N ) = 40，e = 7
>→ 7 * d ≡ 1 ( mod 40 )
>→ 找 d = 23，7 * 23 = 161 ≡ 1 ( mod 40 )

>[!Important]
>RSA 的發明人 : ==Ron Rivest==、==Adi Shamir==、==Leonard Adleman==

#### 範例二 : 雜湊函數 ( Hash Function )
將任意字串進行雜湊運算後，得到一固定長度的雜湊值
> [!Note]常見的雜湊函數
> - MD5 ( message digest 5 ) : 產生 128 - bit 的雜湊值
> - SHA - 1 ( secure hash algorithm 1 ) : 產生 160 - bit 的雜湊值
> - SHA - 256 ( secure hash algorithm 2 with 256 - bit digest ) : 產生256 - bit 的雜湊值

**雜湊函數的特性**
1. ==輸出的長度固定==
2. ==任一微小變化，結果完全不同== ( 雪崩效應 )
3. ==單向函數==
4. ==不易發生碰撞 ( collision )==

>[!Tip]應用
>目前大部分的 login 密碼幾乎以 hash function 存在 data base

#### 數位簽章 ( Digital Signature )
1. 不論原始資料長度為何，將要簽章的資料用 hash function 計算
2. 把雜湊值用數位簽章保護

>[!Important]
>1. 能把資料長度縮短至 128 ~ 512 bit
>2. 只需要針對 16 ~ 64 位元資料做保護

---
### 網路攻擊
**目的 :**
1. 取得未授權的資訊
2. 中斷網路的正常運作
---
### 常見的網路攻擊 ( 紅隊 )
#### 範例一 : 阻斷網路攻擊 ( ==Dos== )
> [!Important]
> ==破壞可用性==

攻擊者會產生大量網路流量，耗盡目標的網路頻寬
>[!Note]Ex
>產生大量 ping 封包、TCP 連線要求、UDP 封包

#### 範例一的進階 : 分散式阻斷網路攻擊 ( DDOS )
透過一大群機器進行阻斷服務攻擊 ( 比 DOS 還要更多 IP，所以更難防 )

#### 範例二 : 主機入侵 ( ==Host-based intrusion== )
通常是利用系統上的漏洞，且入侵後可再嘗試取得系統操作權限
>[!Note]常見
>- 網頁置換

**目的 :**
1. 竊取主機內的各種資料
2. 建置 「 釣魚網站 」 ( ==社交工程== )

#### 範例三 : 電腦病毒 ( ==Virus== )
帶有惡意的程式碼
>[!Important]種類
>- 病毒 ( ==Virus== ) : 不斷自我複製並感染
>- 蠕蟲 ( ==Worm== ) : 透過網路傳播
>- 特洛伊木馬程式 ( ==Trojan Horse== ) : 植入後門進而竊取資訊

### 網路防護 ( 藍隊 )
#### 範例一 : 防毒軟體 ( ==Antivirus Software== )
選擇多樣
>[!Note]偵測方式
>- 病毒的定義檔
>- 「 啟發式 」的偵測方式

#### 範例二 : 防火牆 ( ==Firewall== )
過濾規格可針對 OSI 協定的各層設定
>[!Tip]
>防火牆通常置於 LAN 通往 WAN 的路上

### 區塊鏈
**區塊鏈的目的為保護有相依性的紀錄不被修改**
把須被保護的紀錄 ( 區塊 ) 按關聯性串在一起，並用 Hash Function 對鏈上相鄰的資料進行完整性的驗證


### POW ( Proof - Of - Work ) 方法
若給定一個要新增到鏈結裡的區塊鏈資料以 X 表示，在驗證程序中，必須找出一個數值 k ，計算雜湊值 V = hash ( X , k ) ，並使 V 值前面 n 位數的值為 0

>[!Important]
>比特幣的主要運作原理

### 比特幣運作

#### Miner ( 礦工 ) : 會把很多個交易打包成一個區塊

>[!Important]
>主要用 hash 算出區塊，並讓每個交易加入區塊
>區塊被發現後有獎勵金，且區塊內的交易要給礦工交易費

**每個用戶都有一個 ==地址==、==公鑰==、==私鑰==**
**比特幣的運作流程**
##### 1. 新的交易廣播給所有節點知道
##### 2. 節點把收到的交易蒐集好，準備放入一個新的區塊
##### 3. 針對新的區塊，每個節點開始進行 POW 驗證
##### 4. 一旦完成 POW，完成 POW 的節點將這個區塊的結果廣播給網路中的其他節點
##### 5. 收到通知的節點可以驗證區塊中的交易內容和 POW 結果是否正確，並接收他
##### 6. 一旦新的區塊通過驗證並被接受，節點們重複這個流程和產生新的區塊
>[!Warning]
>- 如果有人假冒 A ? ==不可能被假冒 ( 沒有私鑰 )==
>- 每個區塊的交易量是否唯一 ? ==否==
>- 會不會有交易，沒有礦工打包 ? ==通常不會 ( 可以賺錢 )==
>- 礦工算出下一個區塊但不發布 ? ==通常不會 ( 怕被搶先 )==

---
### 後量子密碼學
希望在不依靠量子電腦的情況下，也可以設計抵抗量子電腦破解密碼的方法

## CH9 程式語言
- [FORTRAN](#FORTRAN)
- [LISP](#LISP)
- [COBOL](#COBOL)
- [BASIC](#BASIC)
- [PASCAL](#PASCAL)
- [C 語言](#C-語言)
- [PROLOG](#PROLOG)
- [ADA](#ADA)
- [C++](#C++)
- [Python](#python)
- [Java](#Java)
- [Javascript 和 ASP.NET](#Javascript-和-ASP.NET)
- [Kotlin 和 Swift](#Kotlin-和-Swift)

---
### FORTRAN
**第一個高階語言**
**程式敘述像==數學式子==**

---
### LISP
**不強調運算速率，提供彈性的==符號==和==運算式==**

---
### COBOL
**專為商業資料處理而設計的語言**
**有==便利的檔案描述==、重視==資料的定義==**

---
### BASIC
**DOS作業系統有內建開發環境**
**微軟推出 Visual Basic**
**不須明確==指出資料型態==**

---
### PASCAL
**完備的==資料型態==和結構化的==控制結構==，很有效率**
**==可讀性高==**

---
### C 語言
**高階的==結構化敘述==**
**具備類似低階語言的==硬體控制能力==**

#include <stdio.h>
int main(void) {
printf("Hello, world!");

return 0;
}

---
### PROLOG
**==邏輯化程式設計==的代表**
**專門設計邏輯推論，專家系統**
**和 LISP 一樣是 AI 的重要工具**

---
### ADA
**原先是希望結合所有語言的特性，但後來發現過於困難且實際上語法很難，所以不普及**

---
### C++
**==物件導向程式語言==的代表**
**強調==物件==的設計、==訊息的傳送==**
**更有==模組化==的概念、更易維護**
**C 語言為 C++ 的子集合**

---
### Python
**==可擴充==、提供多種==API==和==模組==**
**==開源==**
**==簡單==、高度可讀性、彈性**

---
### Java
**和 C++ 一樣是==物件導向==**
**提供==跨平台==功能**
>[!Note]跨平台功能
>同程式可在不同環境運行

---
### Javascript 和 ASP.NET
**Javascript 可直接編寫在網頁標記中**
**微軟提出一系列「 .NET 」，其中包括 ASP.NET 的開發平台，將程式分成 HTML 和 Script 的區塊，==物件導向==**

---
### Kotlin 和 Swift
**Swift 比 C 語言==更快==、==現代==、==安全==、更有==互動性==**
**Kotlin 和 Java 的標準程式庫的==環境相容==，可在 Android 上運行，且沒有專利**

---
### 以上的程式語言比較

| 類型 | 語言 | 描述 |
| - | - | - |
| 程序式 | FORTRAN、COBOL、BASIC、PASCAL、C 語言、ADA | 程式由==有順序==的指令組成 |
| 物件導向程式語言 | C++、Python、Java、Javascript、ASP.NET、Kotlin、Swift | 有==封裝性的物件==為核心 |
| 函數式 | LISP | 程式由==運算式==組成 |
| 邏輯式 | PROLOG | ==邏輯判斷==寫法 |

---
### 資料類型

#### 數 :
**整數 ( int ) : 32 bits**
**長整數 ( long int ) : 32 bits**
**短整數 ( short int ) : 16 bits**
**浮點數 ( float ) : 32 bits**
**雙精準數 ( double ) : 64 bits**
>[!Warning]
>在 ==32 - bit 系統==中，整數和長整數都是 32 bits 且表示範圍都是 - 2^31^ ~ 2^31^ - 1，但在 ==64 - bit 系統==中，長整數的大小是 64 bits，整數是 32 bits
#### 文字 :
**字元 ( char ) : 8 bits**
**字串 ( string )**

>[!Important]
>編譯器會檢查該變數在任何地方出現是否恰當
## CH10 資料結構
- [陣列](#陣列)
- [鏈結串列 ( link list )](#鏈結串列-(-link-list-))
- [堆疊 ( stack )](#堆疊-(-stack-))
- [佇列 ( Queue )](#佇列-(-Queue-))
- [樹狀結構 ( Tree )](#樹狀結構-(-Tree-))

---
## 陣列
**一系列相同型態的資料**
>[!Warning]
>陣列裡，第一個元素位置是0

**陣列可以很快的決定某個註標在記憶體的位置**

int array[5];

array[0] = 1;
array[1] = 2;
arrat[2] = 3;
array[3] = 4;
array[4] = 5;

### 二維陣列
**int array [ i ][ j ];**
**i : 有幾列**
**j : 有幾行**
>[!Important]陣列的儲存方式
>陣列在記憶體內是先存第一列再存第二列，以此類推

int array2[2][3] = {{0,1,2},
{3,4,5}};

## 鏈結串列 ( link list )
**利用指標建立鏈結串列，來表示不確定大小或會動態增減的資料**
>[!Note]優點
>**1. 可以避免需要預先知道資料大小的缺點，能靈活運用記憶體空間**
>**2. 鏈結串列無法隨機讀取**

>[!Warning]缺點
>**每個節點需要較大記憶體空間，程式執行較容易出錯**

void insert(struct node *p, int new_item)
{
struct node *temp = malloc(sizeof (struct node));

temp -> data = new_item;
temp -> next = p;
p = temp;
};
## 堆疊 ( stack )
**採用==後進先出 ( LIFO )==、==先進後出==**
>[!Tip]
>類似網球桶式的堆疊

==push : 加入==
==pop : 丟出來==

push :

void push (int data)
{
top = top + 1;
stack[ top ] = data;
}
pop :

int pop()
{
top = top - 1;
return stack[ top + 1 ];
}

## 佇列 ( Queue )
**採用==先進先出 ( FCFS )==**
>[!Tip]
>**佇列可以想成一根水管**

==put : 加入 ( 對應 push )==
==get : 拿出 ( 對應 pop )==

put :

void put (int data)
{
rear = rear + 1;
queue[ rear ] = data;
}

get :

int get()
{
front = front + 1;
return queue[ front ];
}

## 樹狀結構 ( Tree )
**樹由 ==node ( 節點 )== 和 ==edge ( 邊 )== 組成**
>[!Note]
>external node ( 外節點 ) : 樹的最下層
>internal node ( 內節點 ) : 樹的中間層
>樹的高度 ( height ) : 根節點 ~ 葉節點的最長距離

### 樹的探訪
+
/ \
* *
/ \ / \
A B C D

#### 前序法 ( preorder )
**==+ * AB * CD==**
>[!Important]
>先把父節點印出，再用遞迴印出左子節點，最後再用一樣方法處理右子樹

#### 中序法 ( inorder )
**==A * B + C * D==**
>[!Important]
>先把左子樹印出後，再印父節點，最後處理右子樹
#### 後序法 ( postorder )
**==AB * CD * +==**
>[!Important]
>先用 2 個遞迴把左子樹和右子樹都印出，再處理父節點