Chapter 3 鏈結串列結構 資料結構導論 - C語言實作.

Presentation on theme: "Chapter 3 鏈結串列結構 資料結構導論 - C語言實作."— Presentation transcript:

1 Chapter 3 鏈結串列結構 資料結構導論 - C語言實作

2 3.1 前言 陣列結構(Array)和鏈結串列(Linked List)： 陣列的使用是透過陣列變數及對應的索引來存取陣列個別元素。
鏈結串列儲存資料的方式是將個別資料項次(data item)透過鏈結串在一起。 資料結構導論 - C語言實作

3 3.2單向鏈結串列 給定一組未經排序的六筆資料{5，78，65，31，83，98} ，經由小而大排序後再存入一個大小為10的一維陣列DATA中，如圖3.1所示。 假設我們希望將資料45加入這些排序過的資料中並維持由小到大的順序，利用陣列結構在處理資料的插入是相當麻煩的。 圖3.1 陣列結構DATA[10] 資料結構導論 - C語言實作

4 3.2單向鏈結串列 圖3.2 陣列結構DATA[10]（插入45後的結果） 圖3.3 陣列結構DATA[10]（刪除31後的結果）
資料結構導論 - C語言實作

5 3.2單向鏈結串列 以C語言為例，宣告單向鏈結串列的語法如下： 【範例】定義一個單向鏈結串列之節點資料型態
struct node{ /* 定義一個單向鏈結節點類別(結構) */ int data; /* data 用來儲存節點資料值 */ struct node *link; /* 為一個 node 指標，它指向下一個節點 */ }; 資料結構導論 - C語言實作

6 3.2單向鏈結串列 【範例】定義一個單向鏈結串列之的開端節點指標front 以C語言為例，宣告單向鏈結串列的開端節點指標語法如下：
struct node *front; front = (struct node *) malloc(sizeof(struct node)); front->link = NULL; 前端指標 front 資料結構導論 - C語言實作

7 3.2單向鏈結串列 【範例】動態要求一個節點的空間 new_node struct node *new_node;
new_node = (struct node *) malloc(sizeof(struct node)); if (new_node == NULL) { printf(“\n所需的記憶體空間無法配置”); } 前端指標 new_node 資料結構導論 - C語言實作

8 3.2單向鏈結串列 【範例】釋放不再用到的節點空間 free(temp_node); 資料結構導論 - C語言實作

9 3.2單向鏈結串列 【範例】建立一個包含兩個節點的單向鏈結串列 前端指標 10 struct node *front;
struct node *first, *second; front = (struct node *) malloc(sizeof(struct node)); first = (struct node *) malloc(sizeof(struct node)); second = (struct node *) malloc(sizeof(struct node)); front->link = first; first->data = 10; first->link = second; second->data = 20; second->link = NULL; NULL 10 20 first 前端指標 front second 資料結構導論 - C語言實作

10 3.2單向鏈結串列 【範例】宣告單向鏈結串列的尾端指標rear 前端指標 尾端指標 10 struct node *rear;
rear->link = NULL; rear->link = second; NULL 10 20 first 前端指標 front second 尾端指標 rear 資料結構導論 - C語言實作

11 3.2單向鏈結串列 我們將利用圖3.7中一個包含六筆資料的有序單向鏈結串列為例子來介紹幾種基本的運作。 圖3.7 有序單向鏈結串列
圖3.7 有序單向鏈結串列 資料結構導論 - C語言實作

12 3.2單向鏈結串列 圖3.8 將資料45插入圖3.7之鏈結串列之結果 圖3.9 從鏈結串列中刪除資料78 資料結構導論 - C語言實作

13 3.2.3 將單向鏈結串列反轉 單向鏈結串列是一個具有方向性的資料表示法，要將一個單向鏈結串列反轉就是要將節點與節點之間的順序關係倒轉。
(a) 反轉前的單向鏈結串列 (b) 反轉後的單向鏈結串列 圖3.12 單向鏈結串列之反轉範例 資料結構導論 - C語言實作

14 3.2.3 將單向鏈結串列反轉 以C語言為例，反轉一個單向鏈結串列的處理程序列語法如下: 【反轉一個單向鏈結串列】
【反轉一個單向鏈結串列】 int invert_list(struct node *head) { struct node *mid_node, *last_node;  mid_node=NULL; while( head!=NULL ) last_node=mid_node; /* 把中間節點傳遞給結尾指標 */ mid_node=head; /* 把前頭節點傳遞給中間指標 */ head=head->link; /* 前頭指標往前進一個節點 */ mid_node->link=last_node; /* 反轉原本的前頭與中間節點順序關係 */ } return(mid_node); /* 將反轉後的開端指標傳回 */ 資料結構導論 - C語言實作

15 3.2.4 計算串列之長度 串列之長度指的是串列中儲存資料之節點個數，不包含front及rear。 以C語言為例，計算串列之長度語法如下:
【計算串列之長度】 void length(struct node *front_) { int count = 0; struct node *this_node; if (front_->link != NULL) /* queue is not empty */ this_node = front_->link; while(this_node->link != NULL) count ++; this_node = this_node->link; } 資料結構導論 - C語言實作

16 3.2.4 計算串列之長度 printf(" ==> 串列長度為 : %d\n",count); } else
printf(" !!! 空串列，串列長度為 : 0 \n"); 資料結構導論 - C語言實作

17 3.2.5 串列之合併 假設我們希望將兩個單向鏈結串列x與y合併，我們必須將串列y中的所有節點合併到串列x的所有節點後面，產生一個合併後的串列z。在合併的處理中我們發現可能會有下列三種可能狀況出現： (1). 當串列x是空的則合併後的串列z就是串列y。 (2). 當串列y是空的則合併後的串列z就是串列x。 (3). 如果串列x與y都不是空串列，則必須將串列y中所有的節點搬移到串列x的所有節點之後，即可完成兩個串列合併的動作。 資料結構導論 - C語言實作

18 3.2.5 串列之合併 假設串列x與y皆為非空的串列，我們發現合併的動作包含下列幾個步驟： 1.將front_z 指向串列x的第一個節點。
圖3.16 串列之合併 資料結構導論 - C語言實作

19 3.2.5 串列之合併(1) 以C語言為例，將 y 串列合併到 x 串列之後，並以 front_z 為新串列的前端，其語法如下:
【將 y 串列合併到 x 串列之後，並以 front_z 為新串列的前端】 void cancatenate(struct node *front_x, struct node *front_y, struct node *front_z) { struct node *this_node; if (front_x->link == NULL) /* front_x 為空串列 */ front_z->link = front_y->link; else if (front_y->link == NULL) /* front_y 為空串列 */ front_z->link = front_x->link; } 資料結構導論 - C語言實作

20 3.2.5 串列之合併(1) else /* front_x, front_y 均非空串列 */ {
front_z->link = front_x->link; this_node = front_x->link; while(this_node->link != NULL) this_node = this_node->link; this_node->link = front_y->link; } 資料結構導論 - C語言實作

21 3.2.5 串列之合併(2) 以C語言為例，將 y 串列合併到 x 串列之後，並以 front_z 為新串列的前端，其語法如下:
【將 y 串列合併到 x 串列之後，並以 front_z 為新串列的前端】 void cancatenate(struct node *front_x, struct node *rear_x, struct node *front_y, struct node *rear_y, struct node *front_z, struct node *rear_z) { struct node *this_node; if (front_x->link == NULL) /* front_x 為空串列 */ front_z->link = front_y->link; rear_z->link = rear_y->link; } else if (front_y->link == NULL) /* front_y 為空串列 */ front_z->link = front_x->link; rear_z->link = rear_x->link; 資料結構導論 - C語言實作

22 3.2.5 串列之合併(2) else /* front_x, front_y 均非空串列 */ {
front_z->link = front_x->link; this_node = rear_x->link; this_node->link = front_y->link; rear_z->link = rear_y->link; } 資料結構導論 - C語言實作

23 3.2.6 釋放鏈結串列的空間 當我們在程式的執行過程中不再需要用到某個鏈結串列時，我們便需要將此鏈結串列所使用的空間加以釋放。詳細的C 語言程式片斷如下所列： 【歸還單向鏈結串列】 void free_list(struct node *front_) { struct node *this_node; struct node *temp_node; if (front_->link != NULL) /* queue is not empty */ this_node=front_link; while ( this_node != NULL ) temp_node=this_node; 資料結構導論 - C語言實作

24 3.2.6 釋放鏈結串列的空間 this_node=this_node->link; free(temp_node); } else
{ printf("Find a empty list.\n"); 資料結構導論 - C語言實作

25 3.2.7 列印(走訪)串列中所有節點的值 void print(struct node *front_) {
struct node *this_node; if (front_->link != NULL) this_node = front_->link; printf(" ==> 串列內容為 : "); while(this_node->link != NULL) printf("%d ->",this_node->data); this_node = this_node->link; } printf("%d \n",this_node->data); else printf(" !!! 空串列\n"); 資料結構導論 - C語言實作

26 範例程式2：節點資料之排序(p.3-28) /*******************************************************************/ /*【程式名稱】: 3_singlelist.c */ /*【程式功能】: 節點資料由小至大排序之單向鏈結串列的資料增刪與列印 */ /*【資料結構】: 單向鏈結串列(singly linked list)，節點結構 */ /*【變數名稱及用途】 */ /* struct node : 定義 node 為一個節點結構 */ /* data : 用來儲存節點資料值 */ /* link : 為一個 node 指標，它指向下一個節點 */ /* front : 為一個 node 指標，它指向單向鏈結串列的前端 */ /* rear : 為一個 node 指標，它指向單向鏈結串列的尾端 */ 資料結構導論 - C語言實作

27 #include <stdio.h> #include <stdlib.h> #define N 6
void create_single_list(void); void free_single_list(void); int empty(void); void insert_node(int key); void delete_node(int key); void print(void); void reverse(void); /* */ /* 定義 node 為一個節點結構 */ struct node{ /* 定義一個單向鏈結節點結構 */ int data; /* data 用來儲存節點資料值 */ struct node *link; /* 為一個 node 指標，它指向下一個節點 */ }; struct node *front, *rear; 資料結構導論 - C語言實作

28 /* 產生一個空串列，它只有 front 及 rear 兩個節點 */
void create_single_list(void) /* Constructor */ { front = (struct node *) malloc(sizeof(struct node)); rear = (struct node *) malloc(sizeof(struct node)); front->link = NULL; rear->link = NULL; } void free_single_list(void) /* Destructor */ struct node *this_node, *temp_node; if (front->link != NULL) this_node = front->link; while(this_node->link != NULL) temp_node = this_node; this_node = this_node->link; free(temp_node); free(this_node); else; free(front); free(rear); 資料結構導論 - C語言實作

29 if(front->link == NULL) /* 空串列 */ return 1; /* true */ else
/* 判斷是否為空串列 */ int empty(void) { if(front->link == NULL) /* 空串列 */ return 1; /* true */ else return 0; /* false */ } /* 將資料(key)插入單向鏈結串列中，並按小至大順序排列 */ void insert_node(int key) struct node *new_node, *prev_node, *this_node; new_node = (struct node *) malloc(sizeof(struct node)); new_node->data = key; new_node->link = NULL; if (empty()) /* 空串列，插入第一個節點到front之後 */ front->link = new_node; rear->link = new_node; this_node = front->link; if (key < this_node->data) /* 插入到串列之前端 */ new_node->link = this_node; 資料結構導論 - C語言實作

30 while(this_node->link != NULL) /* 插入到串列中間 */ prev_node = this_node;
else { while(this_node->link != NULL) /* 插入到串列中間 */ prev_node = this_node; this_node = this_node->link; if (key < this_node->data) prev_node->link = new_node; new_node->link = this_node; return; } else; this_node->link = new_node; /* 插入到串列尾端 */ rear->link = new_node; 資料結構導論 - C語言實作

31 /* 自單向鏈結串列中刪除資料(key) */ void delete_node(int key) {
struct node *this_node, *prev_node, *temp_node; prev_node = front; this_node = front->link; while(this_node->link != NULL) /* 當不是最後一個節點時 */ if (key == this_node->data) temp_node = this_node; prev_node->link = this_node->link; free(temp_node); return; } prev_node = this_node; this_node = this_node->link; if (key == this_node->data) /* 判斷最後一個節點 */ prev_node->link = NULL; /* 我們將最後一個節點的link指向NULL */ rear->link = prev_node; else printf("... 找不到資料 %d \n",key); 資料結構導論 - C語言實作

32 /* 從 front 開始列印資料(由小至大) */ void print(void) { struct node *this_node;
if (! empty()) /* 若非空串列 */ this_node = front->link; printf(" ==> 串列內容為 : "); while(this_node->link != NULL) printf("%d ->",this_node->data); this_node = this_node->link; } printf("%d \n",this_node->data); else printf(" !!! 空串列\n"); 資料結構導論 - C語言實作

33 struct node *prev_node, *this_node, *next_node;
void reverse(void) { struct node *prev_node, *this_node, *next_node; next_node = front->link; this_node = NULL; while(next_node->link != NULL) prev_node = this_node; this_node = next_node; next_node = next_node->link; this_node->link = prev_node; } next_node->link = this_node; front->link = next_node; void main(void) int i; int a[N] = {5, 65, 31, 83, 78, 21}; create_single_list( ); clrscr( ); printf("\n【將資料插入單向鏈結串列，並保持資料由小至大之排序】...\n"); 資料結構導論 - C語言實作

34 printf("\n 步驟 <%d> 插入 %d\n",i,a[i]); insert_node(a[i]); print();
for(i = 0; i < N; i++) { printf("\n 步驟 <%d> 插入 %d\n",i,a[i]); insert_node(a[i]); print(); } printf("\n【刪除 5】...\n"); delete_node(5); printf("\n【刪除 83】...\n"); delete_node(83); printf("\n【刪除 31】...\n"); delete_node(31); printf("\n【將串列反轉】...\n"); reverse(); free_single_list(); 資料結構導論 - C語言實作

35 範例程式3：串列之合併、串列之長度(p.3-36)
/******************************************************************/ /**【程式名稱】: 3_concatenate2list_1.c */ /**【程式功能】: 以將兩個單向鏈結串列合併成一個串列 */ /**【資料結構】: 單向鏈結串列(singly linked list)，節點結構 */ /**【變數名稱及用途】 */ /** struct node : 定義 node 為一個節點結構 */ /** data : 用來儲存節點資料值 */ /** link : 為一個 node 指標，它指向下一個節點 */ /** front : 為一個 node 指標，它指向單向鏈結串列的前端 */ /** rear : 為一個 node 指標，它指向單向鏈結串列的尾端 */ 資料結構導論 - C語言實作

36 範例程式4:串列之合併 (使用rear指標) (p.3-43)
void main(void) { int i; int a[N] = {0, 1, 2, 3, 4, 5}; int b[N] = {10, 11, 12, 13, 14, 15}; create_list_1( ); create_list_2( ); create_list_3( ); for(i = 0; i < N; i++) { insert(a[i], front_1, rear_1); } printf("\n【單向鏈結串列 1】...\n"); print(front_1); length(front_1); 資料結構導論 - C語言實作

37 insert(b[i], front_2, rear_2); } printf("\n【單向鏈結串列 2】...\n");
for(i = 0; i < N; i++) { insert(b[i], front_2, rear_2); } printf("\n【單向鏈結串列 2】...\n"); print(front_2); length(front_2); printf("\n【單向鏈結串列 3】...\n"); print(front_3); length(front_3); cancatenate(front_1, rear_1, front_2, rear_2, front_3, rear_3); printf("\n【 合併後的單向鏈結串列】...\n"); 資料結構導論 - C語言實作

38 3.3 雙向鏈結串列 雙向鏈結串列包含了許多個節點以及紀錄節點間順序關係的鏈結。 一個雙向鏈結串列的節點包含三個欄位：
(1).左鏈結欄位(Left Link Field, LLINK) : LLINK鏈結欄是用來指向前一個節點。 (2).資料欄位(Data Filed) : data資料欄仍然用來儲存資料。 (3).右鏈結欄位(Right Link Field, RLINK) : RLINK欄則用來指向下一個節點。 資料結構導論 - C語言實作

39 3.3 雙向鏈結串列 圖3.17 雙向鏈結串列的節點結構 雙向鏈結串列的一個節點比起單向鏈結串列的一個節點需要更多的記憶體空間，因為雙向鏈結串列的節點有兩個鏈結欄位而單向鏈結串列的節點只有一個鏈結欄位。 雙向鏈結串列的優點為資料較不容易遺失；相對於單向鏈結串列或環狀串列萬一不幸其中有一個鏈結斷裂，那麼後面的串列資料便遺失而永遠無法再復原了。 資料結構導論 - C語言實作

40 3.3 雙向鏈結串列 【範例】定義一個雙向鏈結串列之節點資料型態 以C語言為例，定義一個雙向鏈結串列之節點資料型態語法如下:
【範例】定義一個雙向鏈結串列之節點資料型態 struct node{ /* 定義一個單向鏈結節點類別(結構) */ int data; /* data 用來儲存節點資料值 */ struct node *l_link; /* 為一個 node 指標，它指向前一個節點 */ struct node *r_link; /* 為一個 node 指標，它指向下一個節點 */ }; l_link data r_link 資料結構導論 - C語言實作

41 3.3 雙向鏈結串列 【範例】利用雙向鏈結串列結構來表示一組由小到大排序的六筆資料{5， 31，65， 78，83，98} 。
圖3.18 只有使用開端節點指標的雙向鏈結串列 資料結構導論 - C語言實作

42 3.3 雙向鏈結串列 【範例】宣告雙向鏈結串列的開端與尾端指標並設定起始值 尾端指標 前端指標
struct node *front, *rear; front = (struct node *) malloc(sizeof(struct node)); rear = (struct node *) malloc(sizeof(struct node)); front->link = NULL; rear->link = NULL; NULL 前端指標 front 尾端指標 rear 資料結構導論 - C語言實作

43 3.3 雙向鏈結串列 圖3.19 使用開端與節尾節點指標的雙向鏈結串列 資料結構導論 - C語言實作

44 圖3.20 從雙向鏈結串列插入資料45的鏈結改變示意圖
3.3 雙向鏈結串列 【範例】插入資料45到圖3.18的雙向鏈結串列之詳細過程列於圖3.20 。 圖3.20 從雙向鏈結串列插入資料45的鏈結改變示意圖 資料結構導論 - C語言實作

45 圖3.21 從圖3.18的雙向鏈結串列刪除資料78之鏈結改變示意圖
3.3 雙向鏈結串列 【範例】從圖3.18的雙向鏈結串列刪除資料78 。 圖3.21 從圖3.18的雙向鏈結串列刪除資料78之鏈結改變示意圖 資料結構導論 - C語言實作

46 3.3 雙向鏈結串列(p.3-53) 【範例】新增資料到雙向鏈結串列中並維持由小到大的順序
void insert_node(int key) { struct node *new_node, *prev_node, *this_node; new_node = (struct node *) malloc(sizeof(struct node)); new_node->data = key; new_node->l_link = NULL; new_node->r_link = NULL; if (empty()) /* 空串列，插入第一個節點到front之後 */ front->r_link = new_node; rear->r_link = new_node; new_node->l_link = front; new_node->r_link = front; /* 我們將最後一個節點的r_link指向front */ } 資料結構導論 - C語言實作

47 this_node = front->r_link;
else { this_node = front->r_link; if (key < this_node->data) /* 插入到串列之前端 */ front->r_link = new_node; new_node->r_link = this_node; new_node->l_link = front; } while(this_node->r_link != front) /* 插入到串列中間 */ prev_node = this_node; this_node = this_node->r_link; if (key < this_node->data) prev_node->r_link = new_node; new_node->l_link = prev_node; this_node->l_link = new_node; return; 資料結構導論 - C語言實作

48 this_node->r_link = new_node; /* 插入到串列之尾端 */
else; } this_node->r_link = new_node; /* 插入到串列之尾端 */ new_node->l_link = this_node; new_node->r_link = front; /* 我們將最後一個節點的r_link指向front */ rear->r_link = new_node; 資料結構導論 - C語言實作

49 3.3 雙向鏈結串列(p.3-55) 【範例】刪除雙向鏈結串列中的一筆資料 void delete_node(int key) {
struct node *this_node, *prev_node, *temp_node; prev_node = front; this_node = front->r_link; while(this_node->r_link != front) /* 當不是最後一個節點時 */ if (key == this_node->data) temp_node = this_node; prev_node->r_link = this_node->r_link; this_node->r_link->l_link = prev_node; free(temp_node); return; } prev_node = this_node; this_node = this_node->r_link; 資料結構導論 - C語言實作

50 if (key == this_node->data) /* 判斷最後一個節點 */ { temp_node = this_node;
prev_node->r_link = front; /* 我們將最後一個節點的r_link指向front */ rear->r_link = prev_node; free(temp_node); } else printf("... 找不到資料 %d \n",key); 資料結構導論 - C語言實作

51 範例程式5：節點資料之排序(p.3-56) /*【程式名稱】: 3_doublelist.c /*【程式功能】: 節點資料由小至大排序之雙向鏈結串列的資料增刪與列印 */ /*【資料結構】: 雙向鏈結串列(double linked list)，節點結構 /****************************************************************/*【變數名稱及用途】 /* struct node : 定義 node 為一個節點結構 /* data : 用來儲存節點資料值 /* r_link : 為一個 node 指標，它指向下一個節點 /* l_link : 為一個 node 指標，它指向前一個節點 /* front : 為一個 node 指標，它指向雙向鏈結串列的前端(串列的頭) */ /* rear : 為一個 node 指標，它指向雙向鏈結串列的尾端(串列的尾) */ /**************************************************************** 資料結構導論 - C語言實作

52 3.4 環狀串列 (Circular Linked List)
在3.2節所介紹的單向鏈結串列與3.3節所介紹的雙向鏈結串列在表示最後一個節點時將單向鏈結串列的節點鏈結欄位(Link)與雙向鏈結串列的右鏈結欄位(RLINK)設定是空的(NULL)。這樣的做法若是串列的開端指標受到破壞就會造成整個串列的資料流失。 資料結構導論 - C語言實作

53 3.4.1 環狀單向鏈結串列 環狀單向鏈結串列: 將單向鏈結串列(Singly Linked List)的最後一個節點的指標欄位指向串列的第一個節點就會形成一個具有單一方向性的環型結構，也就是說鏈結單向串列(Circular Singly Linked List)的最後一個節點之鏈結欄不再指向NULL(0或接地)而是指向鏈結串列的第一個節點。 資料結構導論 - C語言實作

54 3.4.1 環狀單向鏈結串列 【範例】將圖3.7中一個包含六筆資料的有序單向鏈結串列轉換成單向環狀鏈結串列 。 圖3.22 環狀單向鏈結串列
圖3.22 環狀單向鏈結串列 資料結構導論 - C語言實作

55 圖3.23 新增資料到環狀單向鏈結串列的第一個節點
3.4.1 環狀單向鏈結串列 【範例】新增資料2到圖3.22中的環狀單向鏈結串列 。 圖3.23 新增資料到環狀單向鏈結串列的第一個節點 資料結構導論 - C語言實作

56 3.4.1 環狀單向鏈結串列 【範例】刪除圖3.22的環狀單向鏈結串列第一個節點 。 圖3.24 刪除環狀單向鏈結串列的第一個節點
圖3.24 刪除環狀單向鏈結串列的第一個節點 資料結構導論 - C語言實作

57 3.4.2 環狀雙向鏈結串列 【範例】利用圖3.18中一個包含六筆資料的有序雙向鏈結串列轉換成環狀雙向鏈結串列 。
圖3.25 環狀雙向鏈結串列 資料結構導論 - C語言實作

58 3.4.3利用環狀鏈結串列表示稀疏矩陣 稀疏矩陣(Sparse Matrix):
當一個矩陣的非零元素之個數遠低於零元素之個數，我們就稱該矩陣為稀疏矩陣。 圖 6稀疏矩陣 資料結構導論 - C語言實作

59 3.4.3利用環狀鏈結串列表示稀疏矩陣 圖3.27 用7*3矩陣表示圖3.26 資料結構導論 - C語言實作

60 3.4.3利用環狀鏈結串列表示稀疏矩陣 【範例】利用環狀串列來表示稀疏矩陣的內容。 圖3.28 用以表示二維稀疏矩陣的節點結構
圖3.28 用以表示二維稀疏矩陣的節點結構 資料結構導論 - C語言實作

61 3.4.3利用環狀鏈結串列表示稀疏矩陣 利用C語言來描述環狀串列節點的資料型態宣告列於下：
【範例】定義一個利用環狀串列儲存稀疏矩陣的節點資料型態 struct node{ /* 定義一個環狀鏈結節點類別(結構) */ int row; /* row 用來儲存非零元素的列數 */ int col; /* col 用來儲存非零元素的行數 */ int data; /* data用來儲存非零元素的數值 */ struct node *right; /* 為一個 node 指標，它指向同一列的下一個節點 */ struct node *down; /* 為一個 node 指標，它指向同一行的下一個節點 */ }; 資料結構導論 - C語言實作

62 3.4.3利用環狀鏈結串列表示稀疏矩陣 【範例】稀疏矩陣的環狀串列表示法。 圖3.28 用以表示二維稀疏矩陣的節點結構
圖3.28 用以表示二維稀疏矩陣的節點結構 資料結構導論 - C語言實作

63 3.5 多項式表示法 多項式 : f(x)=anxn+an-1xn-1+…+a1x1+a0x0是一個單變數x之多項式，其中an，an-1，…，a1，a0為此多項式之係數(Coefficient)，而n，n-1，…，1，0等為多項式的指數(Exponent)次方之數值。 【範例】多項式f(x)=6x5+12x3+11 。 圖3.30 利用陣列來表示給定的單變數多項式 資料結構導論 - C語言實作

64 圖3.31 另外一個利用陣列來表示給定的單變數多項式
3.5 多項式表示法 圖3.31 另外一個利用陣列來表示給定的單變數多項式 資料結構導論 - C語言實作

65 3.5 多項式表示法 利用鏈結串列來表示單一變數多項式。 【範例】利用單向鏈結串列表示多項式
3.5 多項式表示法 利用鏈結串列來表示單一變數多項式。 【範例】利用單向鏈結串列表示多項式 f(x)=6x5+12x3+11 。 圖3.32 用來表示單變數多項式非零項次的節點結構 圖3.33 利用單向鏈結串列表示多項式 f(x)=6x5+12x3+11 資料結構導論 - C語言實作

66 3.5 多項式表示法 利用鏈結串列來表示多變數多項式 。 【範例】利用單向鏈結串列表示多變數多項式
3.5 多項式表示法 利用鏈結串列來表示多變數多項式 。 【範例】利用單向鏈結串列表示多變數多項式 f(x,y,z)=6x5y4z3+4x3y2z+3xy 。 圖3.34 用來表示多變數多項式非零項次的節點結構 圖3.35 利用單向鏈結串列表示多項式 f(x,y,z)= 6x5y4z3+4x3y2z+3xy 資料結構導論 - C語言實作