資料結構 第3章　鏈結串列.

Presentation on theme: "資料結構 第3章　鏈結串列."— Presentation transcript:

1 資料結構 第3章　鏈結串列

2 3-1　單向鏈結串列 串列 (list) 是一群相同類型的元素依照一定順序排列而成的有序集合，通常表示成 (item0, item1, …, itemn-1)。 串列常見的運算如下 ： 讀取 (retrieve) 寫入 (store) 取代 (replace) 插入 (insert) 刪除 (delete) 搜尋 (search) 走訪 (traverse) 取得長度 (find length)

3 使用陣列存放串列 (2, 3, 5, 7, 11, 13) 及其優缺點 使用鏈結串列存放串列 (2, 3, 5, 7, 11, 13) 及其優缺點

4 3-1-1 宣告節點的結構 typedef struct node{ int data; struct node *next;
3-1-1　宣告節點的結構 typedef struct node{ int data; struct node *next; }list_node; typedef list_node *list_pointer; data next

5 3-1-2 插入節點 在目前節點 (current) 的前面插入一個新節點 (ptr)，其步驟如下： 配置記憶體空間 掛上新節點的鏈結
3-1-2　插入節點 在目前節點 (current) 的前面插入一個新節點 (ptr)，其步驟如下： 配置記憶體空間 掛上新節點的鏈結 ptr = (list_pointer)malloc(sizeof(list_node)); ptr->data = 50; ptr->next = current;

6 改變舊節點的鏈結 previous->next = ptr;

7 3-1-3　建立串列 建立串列的首要步驟必須將串列初始化，然後一一將新節點插入串列，而且新節點可以插入串列的前端、尾端或任意位置 (例如依照data欄位的值由大到小排列)。

8 3-1-4 刪除節點 若要刪除目前節點 (current)，其步驟如下： 改變舊節點的鏈結 釋放記憶體空間
3-1-4　刪除節點 若要刪除目前節點 (current)，其步驟如下： 改變舊節點的鏈結 釋放記憶體空間 previous->next = current->next; free(current);

9 3-1-5　串列長度 串列長度指的是串列的節點個數，但不包含首節點，以下面的串列為例，它的長度為3。

10 3-1-6　串列連接 串列連接指的是將兩個串列連接成一個串列，下面是一個例子。

11 3-1-7　串列反轉 串列反轉指的是將串列的鏈結方向反轉過來，下面是一個例子。

12 3-1-8　環狀鏈結串列 環狀鏈結串列的運算和單向鏈結串列大致相同，但是多了一個優點，無論您從環狀鏈結串列的哪個節點出發，都能拜訪所有節點 (繞一圈即可) 。

13 3-2 雙向鏈結串列 線性雙向鏈結串列 (linear doubly linked list)
3-2　雙向鏈結串列 線性雙向鏈結串列 (linear doubly linked list) 環狀雙向鏈結串列 (circular doubly linked list)

14 3-2-1 宣告節點的結構 typedef struct dnode{ struct dnode *llink; int data;
3-2-1　宣告節點的結構 typedef struct dnode{ struct dnode *llink; int data; struct dnode *rlink; }dlist_node; typedef dlist_node *dlist_pointer; llink data rlink

15 3-2-2 插入節點 若要在目前節點 (current) 的前面插入一個新節點 (ptr)，其步驟如下： 配置記憶體空間 掛上新節點的鏈結
3-2-2　插入節點 若要在目前節點 (current) 的前面插入一個新節點 (ptr)，其步驟如下： 配置記憶體空間 掛上新節點的鏈結 ptr = (dlist_pointer)malloc(sizeof(dlist_node)); ptr->data = 50; (1)ptr->llink = current->llink; (2)ptr->rlink = current;

16 改變舊節點的鏈結 (3)current->llink->rlink = ptr;
(4)current->llink = ptr;

17 3-2-3 刪除節點 若要刪除目前節點 (current)，其步驟如下：
3-2-3　刪除節點 若要刪除目前節點 (current)，其步驟如下： current->llink->rlink = current->rlink; current->rlink->llink = current->llink; free(current);

18 3-3　鏈結串列的應用 鏈結串列本身不僅是資料結構，更可以用來實作其它抽象資料型別 (ADT)，包括多項式、矩陣、串列、堆疊、佇列、樹、圖形…。例如將多項式非零項的結構宣告成如下： typedef struct pnode{ int coef; int exp; struct pnode *next; }poly_node; typedef poly_node *poly_ptr; coef exp next

19 以A(X) = 8X4 - 6X2 + 3X5 + 5、B(X) = 2X6 + 4X2 + 1和C(X) = A(X) + B(X)為例，可以表示成如下：

20 計算C(X) = A(X) + B(X) 的過程如下：

21

22