owned this note
owned this note
Published
Linked with GitHub
---
slideOptions:
theme: serif
---
# 回顧與展望
###### 06.23 鄭余玄
----
## 小提醒
- 隨著課程進入尾聲
- 記得下週是階段考喔
----
## 第十八週 06/30 第二階段檢定考試
- 規則與第一次相同
- 上機考
- 可以上網查
- 不能使用任何形式交談
- 自由去廁所
- 不克前來，記得提前**請假**
---
# 資訊之芽回顧
###### 大抄（？
----
## 第一階段
- 基礎語法
- 流程控制
- 字串
- 函數
- 基礎迴圈
----
## 第二階段
- 更多語法
- C++ 字串、串流
- 指標、參考(reference)
- 動態記憶體：```new```, ```delete```
- 更多遞迴
- 結構(struct)
- 串列、雙向串列
- 檔案流
- 標頭檔
----
## 第二階段
- 演算法：好壞?
- 排序：氣泡、插入、選擇
- 二分搜尋法
- 標準模板庫、範式
- vector, list
- stack, queue, deque
- iterator
- sort, next_permutation
----
## C++ String
```#include <string>```
```std::string myname = "sprout";```
- 長度
```c++
size_t len = myname.length();
```
- 插入
```c++
sprout.insert(6, "zzz");// sprout == "sproutzzz"
```
----
## C++ String
- 比較：字典序比較
- 尋找子字串
```c++
size_t pos = myname.find("pro");
// 判斷是否找不到
pos == std::string::npos
```
----
## C++ 串流格式
```#include <iomanip>```
- **注意**：最後一個輸出格式，會影響之後的輸出
- 輸出 16 進位
```c++
std::cout << std::hex << 123;
```
- 輸出小數點後第二位
```c++
std::cout << std::fixed << std::setprecision(2) << 3.1415926;
```
----
## stringstream
```#include <sstream>```
```std::stringstream ss;```
- ex: 數字轉字串
- 輸入：```ss << XXX;```
- 輸出：```ss >> OOO;```
- 清空：```ss.clear();```
----
## 指標與參考
- 指標
- **注意**：宣告多個指標 ```int *a, *b;```
```c++
int x = 123; // 取值 x, 取位址 &x
int *ptr; // ptr（的值）存位址，指向 int
ptr = &x;
*ptr = 456; // 取值 ptr, 取指向位址中的值 *ptr
```
```c++
int b[5] = {2, 3, 5, 7, 8};
*(b + 3); // == b[3]
```
- 參考：當作一般變數操作
```c++
int x = 123;
int &y = x;
y = 456;
```
----
## 函數傳遞參數
- 傳值：```void swap(int a, int b);```
- 指標：```void swap(int *a, int *b);```
- 參考：```void swap(int &a, int &b);```
----
## 動態記憶體
- ```new``` 使用之後**記得 ```delete```**
```c++
int n;
Student *stu = new Student[n];
delete[] stu;
```
----
## 結構（struct）
- 一般變數
```c++
SproutStudent sprout;
sprout.grade;
```
- 指標變數
```c++
SproutStudent *sptr = &sprout;
sptr->grade;
```
- 函數傳遞參數
```c++
bool isPass(const Student& rhs);
int totalGrade(const Student rhs[]);
```
----
## 串列
- 單向
- 雙向
----
## 排序
- 氣泡：兩兩交換
- 選擇：從未排最小，放到已排序中
----
## 二分搜尋
- *已經排序*完的陣列
----
## 標準模板庫 STL
- ```vector```：伸縮自如的陣列
- ```list```：雙向鏈結串列
- ```stack```：類似疊東西，優先取得最後的資料
- ```queue```：類似排隊，優先取得最早的資料
----
## 迭代器（iterator）
- 用來遍歷容器所有元素
```c++
std::vector<int> vec;
std::vector<int>::iterator it;
it = vec.begin();
for (; it != vec.end(); ++it) {
std::cout << *it << std::endl;
}
```
- 新增、刪除：```insert```, ```erase```
- **注意**：刪除後的 iterator 會失效
----
## ```std::sort``` 排序
```#include <algorithm>```
```c++
int arr[5];
std::sort(arr, arr + 5);
vector<int> vec;
std::sort(vec.begin(), vec.end());
```
- 自訂排序
```c++
struct Position { int x, y; };
// 如果 a < b 回傳 true, 反之 false
bool compare(const Position& a, const Position& b) {
return (a.x < b.x || (a.x == b.x && a.y < b.y));
}
Position pos[4]
std::sort(pos, pos + 4, compare);
```
----
## ```std::next_permutation``` 下個字典序
```#include <algorithm>```
```c++
int s[] = {1, 2, 3};
do {
std::cout << s << std::endl;
} while (std::next_permutation(s, s + 3));
```
Google Drive
Gist
Clipboard
Sign in with Wallet
