Linked list - HackMD

# Linked list ###### 05.20 Winston ###### 投影片 by 竹區講師鄭余玄 ---  # struct ----  ## 複習一下 struct ```c++ struct Student { char firstName[20]; std::string lastName; int age; bool gender; int grade; }; ``` ----  ## struct 變數宣告 ```c++ Student sprout1; ``` ----  ## 匿名 struct 變數宣告 - 可以在定義 struct 時宣告變數 ```c++ struct SproutStudent { std::string name; bool gender; int grade; } sprout; ``` - 可以在不定義 struct 名稱時宣告變數 ```c++ struct { std::string name; bool gender; int grade; } sprout; ``` ----  ## struct 初始化 ```c++ // 結構名稱變數 = { 第一個成員的值, 第二個成員的值, ... }; SproutStudent sprout1 = {"chengscott", true, 87}; ``` ----  ## 存取 struct 成員 - 一般變數：點號（```.```） ```c++ sprout1.grade; // == 87 sprout1.gender = false; ``` - 指標變數：箭號（```->```） ```c++ SproutStudent *s = &sprout1; s->grade; // == 87 s->gender = true; // [思考] 為什麼不用: *s.grade // -> 和 . 運算子優先順序比 * 高 ``` ----  ## 函數參數傳遞 ```c++ bool isPass(Student rhs); // 慢 bool isPass(Student* rhs); // 資料不安全 ``` ```c++ bool isPass(const Student* rhs) { return rhs->grade >= 60; } ``` ```c++ bool isPass(const Student& rhs) { return rhs.grade >= 60; } ``` ----  ## 函數參數傳遞 ```c++ int totalGrade(Student rhs[]); // 資料不安全 int totalGrade(Student *rhs); // 資料不安全 int totalGrade(const Student rhs[]); // 安全 ``` ---  # 動態配置記憶體 ----  ## 配置與釋放記憶體 - 靜態 - 和之前相同，會自動在宣告時配置記憶體，在結束生命週期時釋放 - 動態 - ```new``` 和 ```delete``` 運算子 ----  ## ```new``` 和 ```delete``` ```c++ Student *sprout = new Student; // ... delete sprout; // sprout == nullptr ``` ```c++ int n; Student *stu = new Student[n]; delete[] stu; ``` - ```new``` 使用之後記得 ```delete``` - 小心不要操作到 ```delete``` 後的指標 ---  # 串列 ## Linked List ----  ## 情境 - 想像你現在要儲存一串數字，該怎麼存？ - 陣列 - 如果要支援"增加數字"、或是"刪除數字"的操作，該怎麼維護這個「結構」？ - 陣列的搬移 - 能不能設計更好的「結構」更有效率的達成我們的目的？ ----  ## 單向鏈結串列 ```c++ struct Node { int data; // 節點資料 Node *next; // 指向下一個節點 }; Node *head_ = new Node; ``` - 第一個節點位置是 ```head_``` - 最後一個會指向空節點（通常是 ```nullptr```） ![](https://i.imgur.com/nh0kmE9.png) ----  ## 如何遍歷？ - 找到第二個節點？ - 找到第 n 個節點？ ```c++ Node *cur; cur = head_; for (int i = 0; i < n; ++i) { cur = cur->next; } cur->data; // 第 n 個 ``` - 找到最後一個？ ```c++ while (cur != nullptr) { cur = cur->next; } cur->data; // 最後一個 ``` ----  ## 插入節點 1. 產生新節點 2. 填寫新節點元素值 3. 填寫新節點元素下一個節點 4. 修改 ```p``` 節點的下一個節點為新節點 ![](https://i.imgur.com/BL0YIQN.png) ----  ## 刪除節點 1. 將 ```del_node``` 節點指向 ```p``` 節點的下一個節點 2. p 節點的下一個節點指向 ```del_node``` 節點的下一個節點 3. 刪除 ```del_node``` 節點 ![](https://i.imgur.com/975hQHe.png) ----  ## 雙向鏈結串列 ```c++ struct Node { int data; // 節點資料 Node *prev; // 指向上一個節點 Node *next; // 指向下一個節點 }; ``` ![](https://i.imgur.com/ANGPexo.png) ----  ## 如何？複雜度是多少？ - 找到第 n 個節點？ - 找到最後一個節點？ - 插入節點？ - 刪除節點？ ----  ## 範例 ```c++ #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](https://goo.gl/Q4K66c) ----  ## 上課練習 - [No. 250 Linked-List](http://neoj.sprout.tw/problem/250/) - 實作 linked list 的一些操作