《数据结构(c语言版)黄国瑜 叶乃菁 课件 ch03》由会员分享，可在线阅读，更多相关《数据结构(c语言版)黄国瑜 叶乃菁 课件 ch03（23页珍藏版）》请在金锄头文库上搜索。
1、黃國瑜、葉乃菁著,資料結構,1,資料結構,第三章 鏈結串列,黃國瑜、葉乃菁著,資料結構,2,本章大綱,3-1 何謂鏈結串列 3-2 單向鏈結串列的建立3-2-1 單向鏈結串列內節點的配置 3-2-2 單向鏈結串列內節點的釋回 3-2-3 單向鏈結串列的建立與釋回 3-2-4 單向鏈結串列的搜尋3-3-5 單向鏈結串列的比較,黃國瑜、葉乃菁著,資料結構,3,本章大綱,3-3 單向鏈結串列的基本處理3-3-1 單向鏈結串列內節點的插入 3-3-2 單向鏈結串列內節點的刪除 3-3-3 單向鏈結串列的反轉3-3-4 單向鏈結串列的連結3-3-5 單向鏈結串列的比較,黃國瑜、葉乃菁著,資料結構,4,3
2、-1 何謂鏈結串列,鏈結串列 是一種有序串列 串連方式 陣列結構,黃國瑜、葉乃菁著,資料結構,5,3-1 何謂鏈結串列,動態配置,黃國瑜、葉乃菁著,資料結構,6,3-2 單向鏈結串列的建立,單向鏈結串列內節點的配置 結構： Struct List Int Data;Struct List *Next; ; typedef struct List Node; Typedef Node *Link; Link New; 使用： New = (Link) malloc (sizeof(Node);,黃國瑜、葉乃菁著,資料結構,7,3-2 單向鏈結串列的建立,單向鏈結串列內節點的配置 圖示：單向鏈結串
3、列內節點的釋回 Free(New);,New,NULL,黃國瑜、葉乃菁著,資料結構,8,3-2 單向鏈結串列的建立,單向鏈結串列的建立與釋回 依次將節點串連 Node_1-Next = Node_2 Node_2-Next = Node_3,Node_1,Node_2,Node_3,NULL,黃國瑜、葉乃菁著,資料結構,9,3-2 單向鏈結串列的建立,單向鏈結串列的搜尋 線性搜尋 採用線性搜尋法搜尋鏈結串列中的資料。和陣列不同的是，原本陣列是遞增陣列索引，來搜尋資料，在鏈結串列中，是往下一個節點搜尋。,黃國瑜、葉乃菁著,資料結構,10,3-3 單向鏈結串列基本處理,單向鏈結串列內節點的插入 插
4、入在鏈結串列開頭NEW-Next = PointerHEAD = New,黃國瑜、葉乃菁著,資料結構,11,3-3 單向鏈結串列基本處理,單向鏈結串列內節點的插入 插入在鏈結串列中間NEW-Next = Pointer-NextPointer-Next = NEW,Pointer Pointer-Next,黃國瑜、葉乃菁著,資料結構,12,3-3 單向鏈結串列基本處理,單向鏈結串列內節點的插入 插入在鏈結串列尾端NEW-Next = Pointer-NextPointer-Next = NEW,Pointer,黃國瑜、葉乃菁著,資料結構,13,3-3 單向鏈結串列基本處理,單向鏈結串列內節點的
5、刪除 刪除鏈結串列首節點HEAD = Pointer-NextFree(Pointer),Pointer,從記憶體中釋回,黃國瑜、葉乃菁著,資料結構,14,3-3 單向鏈結串列基本處理,單向鏈結串列內節點的刪除 刪除鏈結串列中間節點Back-Next = Pointer-NextFree(Pointer),Back Pointer,從記憶體中釋回,黃國瑜、葉乃菁著,資料結構,15,3-3 單向鏈結串列基本處理,單向鏈結串列內節點的刪除 刪除鏈結串列尾端節點 Back-Next = Pointer-Next Free(Pointer),Back Pointer,從記憶體中釋回,黃國瑜、葉乃菁著,
6、資料結構,16,3-3 單向鏈結串列基本處理,單向鏈結串列的反轉 Step 1 Back = HEAD Pointer = Back-Next Next = Pointer-Next Pointer-Next = Back Back = Pointer Pointer = Next,黃國瑜、葉乃菁著,資料結構,17,3-3 單向鏈結串列基本處理,單向鏈結串列的反轉 Step 1圖示,黃國瑜、葉乃菁著,資料結構,18,3-3 單向鏈結串列基本處理,Step 2 Next = Pointer-Next Pointer-Next = Back Back = Pointer Pointer = Nex
7、t 重覆Step 2，直到Pointer節點的指標指向NULL,黃國瑜、葉乃菁著,資料結構,19,3-3 單向鏈結串列基本處理,Step 2圖示,黃國瑜、葉乃菁著,資料結構,20,3-3 單向鏈結串列基本處理,Step 3 Pointer-Next = back Head = Pointer,黃國瑜、葉乃菁著,資料結構,21,3-3 單向鏈結串列基本處理,Step 3圖示,黃國瑜、葉乃菁著,資料結構,22,3-3 單向鏈結串列基本處理,單向鏈結串列的連結 找到第一個鏈結串列的尾端 將該節點指標指向第二個節點的首節點。,黃國瑜、葉乃菁著,資料結構,23,3-3 單向鏈結串列基本處理,單向鏈結串列的比較 找到第一個鏈結串列的首節點與第二個鏈結串列的首節點 依次比較其節點，直到鏈結串列尾端為止。,
