第三章 鏈結串列 Linked List 版權屬作者所有,非經作者 同意不得用於教學以外用途.

Slides:



Advertisements
Similar presentations
資料結構 – 鏈結串列 Linked List 綠園. 鏈結串列 -Linked List Linked List 是由許多相同資料型態的項目所組 成的有限序列。 可以把鏈結串列想像成火車,有多少人就只掛多 少節的車廂,需要車廂時再跟系統要一個車廂, 人少了就把車廂還給系統。 鏈結串列是有多少資料用多少記憶體空間,有新.
Advertisements

第一單元 建立java 程式.
計算機程式語言實習課.
第一章 導論(Introduction).
第三章 鏈結串列 Linked List.
第三章 鏈結串列 Linked Lists.
第二章 线性表 1 线性表的逻辑结构及其基本操作 2 线性表的顺序存储结构 3 线性表的链式存储结构 4 静态链表 5 应用实例.
資料結構與C++程式設計進階 資料結構概論 講師:林業峻 CSIE, NTU 6/ 7, 2010.
Chap4 Tree.
資料結構 第2章 陣列.
第4章 鏈結串列(Linked Lists) 4-1 動態記憶體配置-(6) 4-2 鏈結串列的基礎-(7)
Linked List Operations
單向鏈結串列 Singly Linked Lists.
資料結構 第3章 鏈結串列.
程式設計 博碩文化出版發行.
第4章 鏈結串列(Linked Lists) 4-1 動態記憶體配置 4-2 鏈結串列的基礎 4-3 單向鏈結串列 4-4 環狀鏈結串列
struct 可以在同一個名稱下擁有多種資料型態。使用struct能讓資料的存取和處理更為靈活。
Visual C++ introduction
資料結構設計與C++程式應用 Fundamentals of Data Structures and Their Applications Using C++ 第3章 佇列 資料結構設計與C++程式應用.
鏈結串列 (Linked List).
資料結構與演算法 第四章 鍵結串列 徐熊健.
親愛的老師您好 感謝您選用本書作為授課教材,博碩文化準備本書精選簡報檔,特別摘錄重點提供給您授課專用。 說明: 博碩文化:
親愛的老師您好 感謝您選用本書作為授課教材,博碩文化準備本書精選簡報檔,特別摘錄重點提供給您授課專用。 說明: 博碩文化:
4.1 單項鏈結串列 4.2 環狀串列 4.3 雙向鏈結串列 4.4 鏈結串列之應用
补充内容 结构体 概述 定义结构体类型和定义结构体变量 结构体变量的引用 结构体变量的初始化 指针与结构体 用typedef定义类型的别名.
Chapter 3 鏈結串列結構 資料結構導論 - C語言實作.
101北一女中 資訊選手培訓營 妳不可不了解的指標 Nan.
串列(List) 撰寫一串列程式.
·线性表的定义及ADT ·线性表的顺序存储结构 ·线性表的链接存储结构 · 单向循环链表 · 双链表、双向循环链表 · 一元多项式的加法
Chap 4 鏈結串列 Linked Lists.
第2章 线性表(三) 1/.
第12章 樹狀搜尋結構 (Search Trees)
資料結構與C++程式設計進階 鏈結串列 講師:林業峻 CSIE, NTU 6/ 10, 2010.
類別(class) 類別class與物件object.
(Circular Linked Lists)
第十章 C高级程序应用—链表* 10.1链表的基本概念 10.2单向链表 10.3双向链表 10.4应用举例.
鏈結串列 (Linked List) 註:要會指標(Pointer)
第 六 章 鏈結串列(Link List) 課程名稱:資料結構 授課老師:________ 2019/1/2.
五、链 表 1、单链表 2、双向链表 3、链表应用.
Ch03 鏈結串列結構 淡江大學 周清江.
陈海明 副教授 信息学院 计算机系 电子信息类非计算机专业选修课 程序设计实践 陈海明 副教授 信息学院 计算机系
學習 2019/1/12. 學習 2019/1/12 Chapter 3 鏈結串列結構 資料結構導論 - C語言實作.
4.1 單向鏈結串列 4.2 堆疊的加入與刪除 4.3 佇列的加入與刪除 4.4 其他型式的佇列
第三章 鏈結串列 3-1  單向鏈結串列 3-2 環狀鏈結串列 3-3 雙向鏈結串列.
Chap3 Linked List 鏈結串列.
第三章 链表 单链表 (Singly Linked List) 循环链表 (Circular List) 多项式及其相加
第一單元 建立java 程式.
資料結構 優點 缺點 1 陣列 (Array) 沒有額外變量 (例head, next,...) 運作/操作較簡單 更新資料時,若要保持順序,需要移動較大量資料 靜態結構Static (宣告時已決定了陣列元素多少,不能在程式執行期間增減元素) 2 隊列Queue (FIFO) 容易更新 加入enqueue:
第三章 链表 单链表 循环链表 多项式及其相加 双向链表 稀疏矩阵.
挑戰C++程式語言 ──第8章 進一步談字元與字串
本教學投影片係屬教科書著作之延伸,亦受著作權法之保護。
資料結構 老師:李崇明 助教:楊斯竣.
樣版.
C qsort.
資料結構使用Java 第6章 鏈結串列(Linked List).
第14章 結構與其他資料形式.
陣列與結構.
Chapter 4 鏈結串列 Linked List 2019/5/14.
動畫演示 Node規範了一些基本的方法,像是增加節點、刪除節點、讓節點做一些事、取得第n個節點等等
北一女中 資訊選手培訓營 妳不可不了解的指標 Nan.
資料結構 – 鏈結串列 Linked List 綠園.
例題 1. 多項式的排列 1-2 多項式及其加減法 將多項式 按下列方式排列: (1) 降冪排列:______________________ (2) 升冪排列:______________________ 排列 降冪:次數由高至低 升冪;次數由低至高.
第4章 鏈結串列(Linked Lists) 4-1 動態記憶體配置-(6) 4-2 鏈結串列的基礎-(7)
資料結構使用Java 第5章 串列程式實作.
鏈結串列 Link List chapter 6 德明科技大學資訊科技系.
ABAP Basic Concept (2) 運算子 控制式與迴圈 Subroutines Event Block
String類別 在C語言中提供兩種支援字串的方式 可以使用傳統以null結尾的字元陣列 使用string類別
Array(陣列) Anny
鏈結串列 (Linked List).
ABAP Basic Concept (2) 運算子 控制式與迴圈 Subroutines Event Block
Presentation transcript:

第三章 鏈結串列 Linked List 版權屬作者所有,非經作者 同意不得用於教學以外用途

本章內容 3-1 串列的定義 3-2 用陣列直接儲存串列—循序配置串列 3-3 串列加上鏈結—鏈結配置串列 3-4 用結構體陣列實作鏈結串列 3-1 串列的定義 3-2 用陣列直接儲存串列—循序配置串列 3-3 串列加上鏈結—鏈結配置串列 3-4 用結構體陣列實作鏈結串列 3-5 指標與結構體 3-6 動態配置節點實作鏈結串列 3-7 鏈結串列的其他運算 3-8 環狀鏈結串列 3-9 雙向鏈結串列 3-10 鏈結串列的應用

3-1 串列(list)的定義 串列 是許多項目有順序的排列 ( 集合 (set) 裡的元素則沒有前後之分) 常用於串列上的幾個運算 二次大戰同盟國國名串列 中國 美國 英國 蘇俄 10到30之間的質數由小到大排列 11 13 17 19 23 29 常用於串列上的幾個運算 1. 插入新節點 (Insert) - 在原有的串列中加入一個新的元素。 2. 刪除某節點 (Delete) - 將某一個元素從原本的串列中移除。 3. 找尋某節點 (Find) - 依照需求將所指定的(或第幾個)元素值讀出來 串列的實作方式 「循序配置串列」(sequential allocation list) 「鏈結配置串列」(linked allocation list)

3-2 用陣列直接儲存串列—循序配置串列 利用陣列循序儲存串列的方式,具有以下的優缺點: 中國 Alli[0] 11 Prime[0] 美國 Alli[1] 13 Prime[1] 英國 Alli[2] 17 Prime[2] 蘇俄 Alli[3] 19 Prime[3] 23 Prime[4] 29 Prime[5] 利用陣列循序儲存串列的方式,具有以下的優缺點: 優點:只要標明要查詢第幾個元素,就能很快地根據元素註標讀寫該元素,因為陣列的隨機存取 (random access) 效率相當高,時間複雜度為 O(1)。 缺點:插入元素 (insert) 和刪除元素 (delete) 兩個動作所需時間的複雜度為O(n)。這是因為陣列所有元素在記憶體中的實體位置 (physical location) 是連續的,因此不論是執行元素的插入或刪除,都必須進行資料的搬移,以維持正確的順序(參考2.2節)。

3-3 串列加上鏈結—鏈結配置串列 「鏈結串列」(linked list) 可以用來解決陣列循序配置的缺點: 1. 鏈結串列的元素之間不必實體連續(不必依元素順序佔用記憶體中的連續位址),只要有邏輯上 (logical) 的順序存在即可 2. 「鏈結」(link) 就是用來維持這順序的工具,它可以告訴我們「下一個元素放在哪裡」。 無首節點 (由一個指標指到) listA 中國 美國 英國 蘇俄 有首節點 中國 美國 英國 蘇俄 首節點

3-4 用結構體陣列實作鏈結串列 data 欄位存放資料本身 next 欄位存放下一個資料的位置 3 1 3 6 1 7 6 7 data 3-4 用結構體陣列實作鏈結串列 data next 從這裡開始 Table[0] 3 3 [1] 美 國 6 6 data 欄位存放資料本身 [2] -1 [3] 中 國 1 1 [4] -1 next 欄位存放下一個資料的位置 [5] -1 [6] 英 國 7 7 [7] 蘇 俄 [8] -1 節散散佈在陣列中,實體位置沒有連續,但根據鏈結可以得到以下次序 3 首節點 1 中國 3 6 美國 1 7 英國 6 蘇俄 7

插入新節點  找到一個空節點(next值為-1),填入資料 ‘法國’ 7  找到英國,或者條件已知 要在 ‘英國’ 節點之後插入一個新節點 ‘法國’ data next Table[0] 3  找到一個空節點(next值為-1),填入資料 ‘法國’ [1] 美 國 6 [2]  法 國 7 →7  -1  找到英國,或者條件已知 [3] 中 國 1 [4] -1  將英國的 next (7) 複製到法國的next [5] -1 [6]  英 國 →2  7  將法國的位置 (2) 填入英國的next [7] 蘇 俄 [8] -1 3 1 6 7 3 中國 1 美國 6 英國 7 蘇俄 2 首節點 法國

刪除節點 3 1 6 2 7 3 1 2 7 要刪除 ‘英國’ 節點 data next Table[0] 3  沿著串列找到英國 (6),以及英國的前一個節點 ‘美國’(1) [1] 美 國 →2 6 [2] 法 國 7  將英國的 next (2) 複製到美國的next [3] 中 國 1  將英國節點還原為空節點 [4] -1 [5] -1 [6] 英 國 → -1 2 [7] 蘇 俄 [8] -1 3 1 6 2 7 3 中國 1 英國 2 法國 7 蘇俄 美國 6 首節點

要將「阿里山」加在「太魯閣」之後 data next table[0] 5 table[1] 日 月 潭 2 table[2] 墾 丁 日 月 潭 2 table[2] 墾 丁 table[3] -1 table[4] table[5] 溪 頭 7 table[6] table[7] 太 魯 閣 1 table[8] data next table[0] 5 table[1] 日 月 潭 2 table[2] 墾 丁 table[3] 阿 里 山 -1→1 table[4] -1 table[5] 溪 頭 7 table[6] table[7] 太 魯 閣 1→3 table[8] 鏈結串列圖示 溪頭 7 太魯閣 1 日月潭 2 墾丁 0 5 首節點 7 1 2 插入新節點 墾丁 0 日月潭 2 阿里山 1 太魯閣 3 溪頭 7 5 首節點 7 2 3 1

刪除「太魯閣」 data next table[0] 5 table[1] 日 月 潭 2 table[2] 墾 丁 table[3] 日 月 潭 2 table[2] 墾 丁 table[3] 阿 里 山 -1→1 table[4] -1 table[5] 溪 頭 7 table[6] table[7] 太 魯 閣 1→3 table[8] data next table[0] 5 table[1] 日 月 潭 2 table[2] 墾 丁 table[3] 阿 里 山 1 table[4] -1 table[5] 溪 頭 7→3 table[6] table[7] 太 魯 閣 3→-1 table[8] 鏈結串列圖示 墾丁 0 日月潭 2 阿里山 1 太魯閣 3 溪頭 7 5 首節點 7 2 3 1 刪除節點 溪頭 3 阿里山 1 日月潭 2 墾丁 0 5 首節點 3 1 2

3-5 指標與結構體 ◎變數是存放資料的地方 int i, j; i 5 j 5 p i ◎指標是存放位址的地方 int *p; 5 同義詞 3-5 指標與結構體 ◎變數是存放資料的地方 int i, j; i 5 i = 5 ; j = i ; j 5 p i ◎指標是存放位址的地方 int *p; p = &i ; 5 同義詞 p 指向 i ←→ p 裡面存放 i 的位址

◎ *p 是 “p 所指變數” 的同義詞 p i 10 j p i 10 10 相當於 i=10 ; *p = 10 ; 相當於 j = i ; j p i j = *p ; 10 10

結構體 (structure) 結構體是將不同型別的元素集合起來,形成一種新的資料型別 1. struct student { 2. char name[8]; //姓名欄位 3. int age; //年齡欄位 4. int height; //身高欄位 5. } ; 此時就會產生一種叫做student的新結構體,這種結構體含有三個欄位,其中姓名欄位是一個字元陣列、年齡欄位是整數、身高欄位也是整數。 S1 S1 S1.age = 18 ; S1.height = 160 ; strcpy(S1.name, “Mary”) ; name name Mary age age 18 height height 160 宣告 typedef int INTEGER ; 就產生一個「新」的型別叫INTEGER,可以根據這個型別來宣告變數: INTEGER i, j ; 它的效果就好像宣告 int i, j; 一樣。

3-6 動態配置節點實作鏈結串列 動態配置節點方式實作鏈結串列,常會執行的串列運算按照順序為: 1. 宣告節點結構 2. 動態配置節點 3-6 動態配置節點實作鏈結串列 動態配置節點方式實作鏈結串列,常會執行的串列運算按照順序為: 1. 宣告節點結構 2. 動態配置節點 3. 指標在串列中移動 4. 插入新節點 5. 刪除節點 6. 建立串列

listA->next = NULL ; 宣告節點結構 注意:鏈結欄位改為指標 typedef struct listnode { int data; /*資料欄位*/ struct listnode *next; /*鏈結欄位*/ }NODE; NODE *listA; 2. 動態配置節點 listA = (NODE *) malloc( sizeof(NODE)) ; 在C++語言中則可用 new 運算子 listA = new NODE ; data next 20 填入資料欄位,NULL 填入鏈結欄位: listA->data = 20 ; listA->next = NULL ; listA

3. 指標在串列中移動 執行敘述 p = p->next ; 指標 p 指向下一個節點 40 30 20 10 首節點 p 40 30

走訪整個鏈結串列 void ListTraverse(ListNode *head) { ListNode *p = head; } p = p->next ; while ( p != NULL ) { printf( “\n%d”, p->data ); //印出節點資料 } p = p->next ; //指標p沿著鏈結而指向下一個節點

插入新節點 … … … … … … … 要將指標 NewNode 所指到的新節點,插入指標 p 所指舊節點之後 p NewNode 第一步:掛上新節點的鏈結 NewNode->next = p->next ; … … p NewNode 第二步:改變舊節點的鏈結 p->next = NewNode ; … p NewNode … … NewNode p

1. int InsertAfter(ListNode *p, int value) 2. { ListNode *NewNode; 3. NewNode = (ListNode*) malloc(sizeof(ListNode)); //動態配置節點 // C++: NewNode = new ListNode; 4. if (NewNode == NULL) 5. return FALSE; //配置失敗 6. NewNode->data = value; //將新節點的值填入 7. NewNode->next = p->next; //掛上新節點的鏈結 8. p->next = NewNode; //改變原有節點的鏈結 9. return TRUE; //傳回成功訊息 10. }

刪除節點 … … … … … 要刪除指標 Node 所指到的節點 Node 第一步:找到前一個節點 Node PreNode PreNode = GetPreNode(head,Node) ; 第二步:前一節點的鏈結,使它越過舊節點 PreNode->next = Node->next ; … Node PreNode 第三步:將舊節點動態歸還 … PreNode free( Node ) ;

1.int DeleteNode(ListNode *head, ListNode *OldNode) 2.{ ListNode *PreNode; 3. if (head == OldNode) //不可刪除首節點 4. return FALSE; //非法刪除,傳回失敗訊息 5. PreNnode = GetPreNode(head, OldNode); //找到前一節點 6. if ( PreNode == NULL)//OldNode節點不在串列中 7. return FALSE; //無法刪除,傳回失敗訊息 8. PreNode->next = OldNode->next; //越過刪除原有節點 9. free(OldNode); //歸還被刪除節點 // C++: delete OldNode; 10 return TRUE; 11.}

6. 建立鏈結串列 建立鏈結串列的方法是重複地將新節點加入串列。 新節點加入的位置 可以是串列的前面 也可以是在串列的尾端 也可以是在串列的特定地方(例如按照 data 欄位大小排列)。 39 39 41 39 41 58 39 41 58 103

3-6 鏈結串列的其他運算 ◎計算串列長度(節點數目)-- 線性鏈結串列 int ListLength( NODE *head) 3-6 鏈結串列的其他運算 ◎計算串列長度(節點數目)-- 線性鏈結串列 Head P在這裡時,count = 0 P在這裡時,count = 1 P在這裡時,count = 2 P在這裡時,count = 3 P在這裡時,count = 4 P在這裡時,迴圈結束 int ListLength( NODE *head) { int counter = 0 ; NODE *p = head ; while ( (p = p->next) != NULL) counter ++ ; return counter ; }

void ListConcate( NODE *listA, NODE *listB) { NODE *p = listA ; ◎串接兩鏈結串列 -- 線性鏈結串列 A p B void ListConcate( NODE *listA, NODE *listB) { NODE *p = listA ; while ( p->next != NULL) // p一路往右直到最後一個節點 p = p->next ; p->next = listB->next ; // 改變其鏈結 }

3-7 環狀鏈結串列 環狀鏈結串列的特點 1. 最後節點的鏈結不接地,而是指向首節點 3-7 環狀鏈結串列 線性鏈結串列 最後節點 Head 環狀鏈結串列 最後節點 Head 環狀鏈結串列的特點 1. 最後節點的鏈結不接地,而是指向首節點 2. 從任何一個節點開始,都可以走訪所有節點。只要繞回原起點就可以停止

3-8 雙向鏈結串列 typedef struct dlist_node { struct dlist_node *left; 3-8 雙向鏈結串列 typedef struct dlist_node { struct dlist_node *left; int data; struct dlist_node *right; }Dnode; 線性雙向鏈結串列 Head 環狀雙向鏈結串列 Head

插入新節點 … … p … p … p … NewNode NewNode NewNode 要將指標 NewNode 所指到的新節點,插入指標 p 所指舊節點之右 p NewNode 第一步:掛上新節點的兩個鏈結 … p NewNode NewNode->left = p; NewNode->right = p->right ; 第二步:改變舊節點的兩個鏈結 … p NewNode p->right->left = NewNode; p->right = NewNode ; …

刪除節點 p … … … p … p … 要刪除指標 p 所指到的節點 第一步:改變左邊節點的右指標使它越過舊節點 p->left->right = p->right ; 第二步:改變右邊節點的左指標使它越過舊節點 … p p->right ->left = p->left ; 第三步:將舊節點歸還系統 free( p ) ; …

3-9 鏈結串列的應用 5x4 可表示為: ◎ 多項式的表示與運算 3-9 鏈結串列的應用 ◎ 多項式的表示與運算 使用鏈結串列表示多項式,每個非零項使用一個節點,每個節點包含兩個資料欄位:係數欄位和冪次欄位,以及一個鏈結欄位。節點結構可以宣告為: typedef struct plistnode { float coef ; /* 係數*/ int expo ; /* 冪次*/ struct plistnode *next ; /*鏈結指標*/ } Pnode; 係數 冪次 5x4 可表示為: 5 4

2. 比較兩項冪次大小,冪次大者,複製此項至C(x),如果冪次相同,則係數相加後,同樣複製此項至C(x)。 A(x) = 5x4 + 6.1x2 + 2.9x +6 A 5 4 6.1 2 2.9 1 6 B(x) = 9x5 + 3.2x2 B 9 5 3.2 2 ※ 多項式相加 1.    兩多項式分別從高冪次項往右掃瞄。 2.    比較兩項冪次大小,冪次大者,複製此項至C(x),如果冪次相同,則係數相加後,同樣複製此項至C(x)。 3.    凡是已被複製的項,多項式就往右移一項。重複步驟1,2,直到兩個多項式都用完為止。

2. pb->exp(=5) 大於 pa->exp(=4) ,複製 *pb,pb往右一個節點 1. 初始狀態 pa A 5 4 6.1 2 2.9 1 6 pb B 9 5 3.2 2 ctail C 2. pb->exp(=5) 大於 pa->exp(=4) ,複製 *pb,pb往右一個節點 pa A 5 4 6.1 2 2.9 1 6 pb B 9 5 3.2 2 ctail C 9 5

3. pa->exp(=4) 大於 pb->exp(=2) ,複製 *pa,pa往右一個節點 5 4 6.1 2 2.9 1 6 pb B 9 5 3.2 2 ctail C 9 5 5 4 4. pa->exp 等於 pb->exp,新節點係數為 pa->coef 加 pb->coef,pa及pb往右一個節點 pa A 5 4 6.1 2 2.9 1 6 pb B 9 5 3.2 2 ctail 9 5 C 5 4 9.3 2

5. pb已經接地,將串列 A 剩下的節點複製到串列 C pa A 5 4 6.1 2 2.9 1 6 pb B 9 5 3.2 2 C 9 5 5 4 9.3 2 ctail 2.9 1 6

M矩陣的 30 (5  6) 個元素中只有 9 個非零項,使用率只有 9/30 = 30% ◎ 稀疏矩陣的表示 0 0 1 0 2 0 -1 0 0 6 0 0 0 1 0 0 0 0 0 0 0 3 0 1 0 0 2 0 0 6 M =   5  6 M矩陣的 30 (5  6) 個元素中只有 9 個非零項,使用率只有 9/30 = 30%       ◎使用節點來表示每個非零項,每個節點結構有 3 個資料欄位— data、row、col 之外,兩個鏈結欄位— right、down。 同一列的節點藉著 right 鏈結成為一個串列, 同一行節點也藉著down鏈結成為一個串列。節點的結構可以圖示為: row col data 例如 1 3 6 down right

0 0 1 0 2 0 -1 0 0 6 0 0 0 1 0 0 0 0 0 0 0 3 0 1 0 0 2 0 0 6 M = 5 ×6 c0 c1 c2 c3 c4 c5 1 2 3 4 5 2 1 4 2 r0 1 1 -1 1 3 6 r1 2 2 1 1 r2 3 3 3 3 3 5 1 r3 4 4 2 2 4 5 6 r4