複習一下 struct

struct Student {
	char firstName[20];
	std::string lastName;
	int age;
	bool gender;
	int grade;
};

struct 變數宣告

Student sprout1;

匿名 struct 變數宣告

• 可以在定義 struct 時宣告變數

struct SproutStudent {
	std::string name;
	bool gender;
	int grade;
} sprout;

• 可以在不定義 struct 名稱時宣告變數

struct {
	std::string name;
	bool gender;
	int grade;
} sprout;

struct 初始化

// 結構名稱 變數 = { 第一個成員的值, 第二個成員的值, ... };
SproutStudent sprout1 = {"chengscott", true, 87};

存取 struct 成員

• 一般變數：點號（.）

sprout1.grade; // == 87
sprout1.gender = false;

• 指標變數：箭號（->）

SproutStudent *s = &sprout1;
s->grade; // == 87
s->gender = true;
// [思考] 為什麼不用: *s.grade
// -> 和 . 運算子優先順序比 * 高

函數參數傳遞

bool isPass(Student rhs); // 慢
bool isPass(Student* rhs); // 資料不安全

bool isPass(const Student* rhs) {
	return rhs->grade >= 60;
}

bool isPass(const Student& rhs) {
	return rhs.grade >= 60;
}

函數參數傳遞

int totalGrade(Student rhs[]); // 資料不安全
int totalGrade(Student *rhs); // 資料不安全
int totalGrade(const Student rhs[]); // 安全

配置與釋放記憶體

• 靜態
  • 和之前相同，會自動在宣告時配置記憶體，在結束生命週期時釋放
• 動態
  • new 和 delete 運算子

new 和 delete

Student *sprout = new Student;
// ...
delete sprout;
// sprout == nullptr

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

• new 使用之後記得 delete
• 小心不要操作到 delete 後的指標

情境

• 想像你現在要儲存一串數字，該怎麼存？
  • 陣列
• 如果要支援"增加數字"、或是"刪除數字"的操作，該怎麼維護這個「結構」？
  • 陣列的搬移
• 能不能設計更好的「結構」更有效率的達成我們的目的？

單向鏈結串列

struct Node {
	int data; // 節點資料
	Node *next; // 指向下一個節點
};
Node *head_ = new Node;

• 第一個節點位置是 head_
• 最後一個會指向空節點（通常是 nullptr）

如何遍歷？

• 找到第二個節點？
• 找到第 n 個節點？

Node *cur;
cur = head_;
for (int i = 0; i < n; ++i) {
	cur = cur->next;
}
cur->data; // 第 n 個

• 找到最後一個？

while (cur != nullptr) {
	cur = cur->next;
}
cur->data; // 最後一個

插入節點

1. 產生新節點
2. 填寫新節點元素值
3. 填寫新節點元素下一個節點
4. 修改 p 節點的下一個節點為新節點

刪除節點

1. 將 del_node 節點指向 p 節點的下一個節點
2. p 節點的下一個節點指向 del_node 節點的下一個節點
3. 刪除 del_node 節點

雙向鏈結串列

struct Node {
	int data; // 節點資料
	Node *prev; // 指向上一個節點
	Node *next; // 指向下一個節點
};

如何？複雜度是多少？

• 找到第 n 個節點？
• 找到最後一個節點？
• 插入節點？
• 刪除節點？

範例

#include <iostream>
struct Node {
    int data;
    Node* next;
};

int main(){
  Node* head = new Node({0, NULL});
  for(int i = 0 ; i < 5 ; i++){
    Node* tmp = new Node({i+1, head});
    head = tmp;
  }
  return 0;
}

• visualization

上課練習

• No. 250 Linked-List

• 實作 linked list 的一些操作