回顧與展望

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";

• 長度

size_t len = myname.length();

• 插入

sprout.insert(6, "zzz");// sprout == "sproutzzz"

---

C++ String

• 比較：字典序比較
• 尋找子字串

size_t pos = myname.find("pro");
// 判斷是否找不到
pos == std::string::npos

---

C++ 串流格式

#include <iomanip>

• 注意：最後一個輸出格式，會影響之後的輸出
• 輸出 16 進位

std::cout << std::hex << 123;

• 輸出小數點後第二位

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;

int x = 123; // 取值 x, 取位址 &x
int *ptr; // ptr（的值）存位址，指向 int
ptr = &x;
*ptr = 456; // 取值 ptr, 取指向位址中的值 *ptr

int b[5] = {2, 3, 5, 7, 8};
*(b + 3); // == b[3]

• 參考：當作一般變數操作

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

int n;
Student *stu = new Student[n];
delete[] stu;

---

結構（struct）

• 一般變數

SproutStudent sprout;
sprout.grade;

• 指標變數

SproutStudent *sptr = &sprout;
sptr->grade;

• 函數傳遞參數

bool isPass(const Student& rhs);
int totalGrade(const Student rhs[]);

---

串列

• 單向
  
  
• 雙向
  
  

---

排序

• 氣泡：兩兩交換
• 選擇：從未排最小，放到已排序中

---

二分搜尋

• 已經排序完的陣列

---

標準模板庫 STL

• vector：伸縮自如的陣列
• list：雙向鏈結串列
• stack：類似疊東西，優先取得最後的資料
• queue：類似排隊，優先取得最早的資料

---

迭代器（iterator）

• 用來遍歷容器所有元素

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>

int arr[5];
std::sort(arr, arr + 5);
vector<int> vec;
std::sort(vec.begin(), vec.end());

• 自訂排序

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>

int s[] = {1, 2, 3};
do {
    std::cout << s << std::endl;
} while (std::next_permutation(s, s + 3));