鏈結串列 (Linked List).

Slides:



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

第一單元 建立java 程式.
第三章 鏈結串列 Linked List 版權屬作者所有,非經作者 同意不得用於教學以外用途.
第三章 鏈結串列 Linked List.
第三章 鏈結串列 Linked Lists.
Linked List(串列) Why Linked List? Pointer Dynamic Allocation
第4章 鏈結串列(Linked Lists) 4-1 動態記憶體配置-(6) 4-2 鏈結串列的基礎-(7)
Linked List Operations
單向鏈結串列 Singly Linked Lists.
第2章 线性表 线性结构 是一个数据元素的有序集合。.
第6章 佇列(Queues) 6-1 佇列的基礎 6-2 佇列的表示法 6-3 環狀佇列 6-4 雙佇列.
資料結構 第3章 鏈結串列.
結構(struct).
第4章 鏈結串列(Linked Lists) 4-1 動態記憶體配置 4-2 鏈結串列的基礎 4-3 單向鏈結串列 4-4 環狀鏈結串列
佇列 (Queue).
資料結構設計與C++程式應用 Fundamentals of Data Structures and Their Applications Using C++ 第3章 佇列 資料結構設計與C++程式應用.
4.4 佇列 特徵: c b a c b d c b 新增 d 刪除 入口 入口 入口 尾端(rear) 尾端(rear) 尾端(rear)
資料結構 第5章 佇列.
鏈結串列 (Linked List).
資料結構與演算法 第四章 鍵結串列 徐熊健.
親愛的老師您好 感謝您選用本書作為授課教材,博碩文化準備本書精選簡報檔,特別摘錄重點提供給您授課專用。 說明: 博碩文化:
4.1 單項鏈結串列 4.2 環狀串列 4.3 雙向鏈結串列 4.4 鏈結串列之應用
补充内容 结构体 概述 定义结构体类型和定义结构体变量 结构体变量的引用 结构体变量的初始化 指针与结构体 用typedef定义类型的别名.
Chapter 3 鏈結串列結構 資料結構導論 - C語言實作.
101北一女中 資訊選手培訓營 妳不可不了解的指標 Nan.
·线性表的定义及ADT ·线性表的顺序存储结构 ·线性表的链接存储结构 · 单向循环链表 · 双链表、双向循环链表 · 一元多项式的加法
Chap 4 鏈結串列 Linked Lists.
第12章 樹狀搜尋結構 (Search Trees)
第9章 自訂資料型態 – 結構 9-1 結構資料型態 9-2 結構陣列 9-3 指標與結構 9-4 動態記憶體配置 9-5 聯合資料型態
資料結構與C++程式設計進階 鏈結串列 講師:林業峻 CSIE, NTU 6/ 10, 2010.
C語言簡介 日期 : 2018/12/2.
(Circular Linked Lists)
第十章 C高级程序应用—链表* 10.1链表的基本概念 10.2单向链表 10.3双向链表 10.4应用举例.
第5章 堆疊(Stacks) 5-1 堆疊的基礎 5-2 堆疊的表示法 5-3 堆疊的應用 - 運算式的計算與轉換
第5章 堆疊(Stacks) 5-1 堆疊的基礎 5-2 堆疊的表示法 5-3 堆疊的應用 - 運算式的計算與轉換
第3章 堆栈和队列 堆栈 堆栈应用 队列 队列应用 优先级队列 主要知识点.
鏈結串列 (Linked List) 註:要會指標(Pointer)
第 六 章 鏈結串列(Link List) 課程名稱:資料結構 授課老師:________ 2019/1/2.
資料結構與C++程式設計進階 堆疊與佇列(Stack & Queue) 講師:林業峻 CSIE, NTU 6/ 21, 2010.
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:
自我參考結構 (self-reference – 1)
第三章 链表 单链表 循环链表 多项式及其相加 双向链表 稀疏矩阵.
常宝宝 北京大学计算机科学与技术系 数据结构(三) 常宝宝 北京大学计算机科学与技术系
第十章 指標.
Linked Lists Prof. Michael Tsai 2013/3/12.
挑戰C++程式語言 ──第8章 進一步談字元與字串
本教學投影片係屬教科書著作之延伸,亦受著作權法之保護。
C qsort.
資料結構使用Java 第6章 鏈結串列(Linked List).
第14章 結構與其他資料形式.
陣列與結構.
指標、串列 (Linked List).
Chapter 4 鏈結串列 Linked List 2019/5/14.
北一女中 資訊選手培訓營 妳不可不了解的指標 Nan.
資料結構 – 鏈結串列 Linked List 綠園.
第4章 鏈結串列(Linked Lists) 4-1 動態記憶體配置-(6) 4-2 鏈結串列的基礎-(7)
第四章 陣列、指標與參考 4-1 物件陣列 4-2 使用物件指標 4-3 this指標 4-4 new 與 delete
鏈結串列 Link List chapter 6 德明科技大學資訊科技系.
ABAP Basic Concept (2) 運算子 控制式與迴圈 Subroutines Event Block
方法(Method) 函數.
ABAP Basic Concept (2) 運算子 控制式與迴圈 Subroutines Event Block
InputStreamReader Console Scanner
Presentation transcript:

鏈結串列 (Linked List)

指 標 在指標類型中,兩種重要的運算子: null 指標代表此指標不指向任何物件或函數 可用 0 來表示 null 指標。 & :位址運算子,用來取得變數的記憶體位址。 * :取值運算子,用來取得指標所指向變數的內容 null 指標代表此指標不指向任何物件或函數 可用 0 來表示 null 指標。 例如: if (pi == NULL) printf(“It’s a empty pointer\n”); 可寫成 if (!pi)

指標變數=(指標變數所指向的型態 *) malloc(所需的記憶空間) 動態記憶體配置指的是在執行階段才向作業系統要求配置記憶體空間。 在C語言中,每次呼叫 malloc()函數,就會取得一塊可用的記憶體空間。 malloc函數配置失敗時會傳回一個空指標。 語法: 指標變數=(指標變數所指向的型態 *) malloc(所需的記憶空間) 將malloc()所傳回的位址強制轉換成指標變數所指向的型態

動態記憶體配置---malloc函數 例一: 例二: ptr = (資料型態*) malloc(sizeof(資料型態)); int *ptr; ptr=(int *) malloc(12); //配置3*4-12Bytes記憶空間,並把ptr指向它 例二: ptr=(int *) malloc(3*sizeof(int)); //配置可存放3個整數的記憶空間 ptr = (資料型態*) malloc(sizeof(資料型態)); 型別轉換,將malloc函數傳回的 指標轉成符合配置的資料型態 算出所需的記憶體空間大小 ptr = (float*)malloc(sizeof(float)); 配置一塊 float 的記憶體空間,指標 fp 指向此空間

動態記憶體配置---malloc函數 範例: #include<stdio.h> #include<stdlib.h> int main() { float *fp; fp=(float *)malloc(sizeof(float)); if(fp!=NULL) { *fp=3.14; printf(“數字=%f\n”,*fp); } else printf(“記憶體配置失敗!\n”);

動態記憶體配置---free函數 free函數可將已配置的記憶體空間歸還。 用法: 範例: free(指標變數); int main() { float *fp; fp=(float *)malloc(sizeof(float)); if(fp==NULL) printf(“記憶體配置失敗\n”); free(fp); }

單向鏈結串列 單向鏈結串列是由節點(node)所串成的串列,如下圖所示。 指向第ㄧ個節點的指標名稱(ptr)為此鏈結串列的名稱。 bat ‧ cat ‧ sat NULL vat ‧ ptr 指向第ㄧ個節點的指標名稱(ptr)為此鏈結串列的名稱。 在單向鏈結串列中每個節點都包含兩個欄位: 資料欄位:存放資料的地方 鏈結欄位:指向下一個 node Data Link 單向鏈結串列的節點結構

單向鏈結串列 可使用自我參考結構(self-referential structure)來定義節點 結構,如下: typedef struct node SN; struct node { int data; SN *link; } ; SN *ptr; 定義節點結構 ptr為node結構的指標 可使用malloc函數來建立新節點,如下: 為指標,指向另ㄧ個node結構 ptr=(SN *)malloc(sizeof(SN)); ptr 配置一塊記憶體空間 data link

單向鏈結串列 程式範例: #include<stdio.h> int main() { typedef struct node SN; struct node { int data; SN *link; }; SN *ptr, *first; ptr =(SN *)malloc(sizeof(SN)); first = (SN *)malloc(sizeof(SN)); ptr->data=10; first->data=20; ptr->link=first; printf("第一個數= %d\n",ptr->data); printf("第二個數= %d\n",ptr->link->data); } first ptr data link 10 data link 20

單向鏈結串列-加入串列前端 加入於串列的前端 步驟如下: ptr NULL x 步驟如下: (1)x=(struct node *) malloc (sizeof(struct node)); /*配置記憶體空間*/ (2)x→link=ptr; /*將x節點的point指到head指的地方*/ (3)ptr=x; /*head換指到x節點(前端變成x節點)*/

單向鏈結串列-加入串列尾端 加入於串列的尾端 步驟如下: head NULL next x null 步驟如下: (1)x=(struct node*) malloc (sizeof(struct node)); x->link=NULL; (2)next=head; while(next->link!=NULL) next=next->link; next->link=x;

單向鏈結串列-加入某一節點之後 加入在串列某一特定節點(add節點)的後面 步驟如下: ptr NULL x 步驟如下: (1)x=(struct node*) malloc (sizeof(struct node)); (2)x→link=add→link; (3)add→link=x;

單向鏈結串列-刪除串列前端 刪除串列前端的節點 步驟如下: (1)temp=ptr; (2)ptr=ptr->link; NULL temp 步驟如下: (1)temp=ptr; (2)ptr=ptr->link; (3)free(temp);

單向鏈結串列-刪除串列最後節點 刪除串列的最後節點 步驟如下: prev ptr temp (1) temp=ptr; NULL NULL temp 步驟如下: (1) temp=ptr; while(temp->link!=NULL) { prev=temp; temp=temp->link; } (2) prev->link=NULL; (3) free(temp);

單向鏈結串列-刪除某一節點 刪除某一特定的節點 步驟如下: (1)必須先用兩個指標this和prev,分別指到即將被刪除節點及前一節點。 ptr NULL 步驟如下: (1)必須先用兩個指標this和prev,分別指到即將被刪除節點及前一節點。 (2)prev->link=this->link; (3) free(this);

計算單向鏈結串列之長度 串列長度指的是此串列共有多少個節點,只要指標指到的節點非NULL,則利用一變數做累加,直到指標到NULL為止。 int length (struct node *ptr ) { struct node *this; this=ptr; int leng=0; while (this != NULL) { leng ++; this=this->link; } return leng ; } 

二、環狀串列 定義:將單向鏈結串列最後一個node的指標指回第一個node。 特色:不論從哪一節點開始尋找,都能夠經過串列中所有節點。

三、雙向鏈結串列 1.每個節點皆有三個欄位,一為左鏈結(LLINK),二為資料(DATA),三為右鏈結(RLINK),其中LLINK指向前一個節點,而RLINK指向後一個節點。 2.通常在雙向鏈結串列中會加上一個串列首。 此串列首的資料欄不存任何資料。 LLINK DATA RLINk 串列首

雙向鏈結串列的優缺點 優點: 加入/刪除任何一個節點時,無需知道其前一節點的位址 可由任何一個節點立即找到前一個或後一個節點 從任何ㄧ個節點開始,必可經過串列中所有nodes 缺點: 增加一個指標空間,需要更多記憶體 新加入ㄧ個節點時需改變四個指標,而單向鏈節串列只需改變兩個指標 刪除時需改變兩個指標,而單向只要改變一個指標

四、多項式的表示 利用鏈結串列來表示多項式: 其中COEF表示變數的係數 EXP表示變數的指數 LINK為指到下一節點的指標 23 3 12 1 11 NULL

多項式的相加 假設兩個多項式 與 相加 以單向鏈結串列方式呈現,C語言程式如下: 假設兩個多項式 與 相加 以單向鏈結串列方式呈現,C語言程式如下: void poly_add(struct poly *eql, struct poly *eq2, struct poly *ans_h, struct poly *ptr) { struct poly *thisl, *this2, *prev; this1 = eq1; this2 = eq2; prev = NULL; while(this1 != NULL || this2 != NULL) ptr = (struct poly*) malloc(sizeof(struct poly)); ptr ->link = NULL;

ptr->coef = this1->coef; ptr->exp = this1->exp; if (this1 != NULL && (this2 = = NULL | | this1->exp > this2 ->exp)) { ptr->coef = this1->coef; ptr->exp = this1->exp; this1 = this1->next; } else if (this1 == NULL || this1->exp < this2 ->exp) ptr->coef = this2->coef; ptr->exp = this2->exp; this2 = this2->link; else ptr->coef = this1->coef + this2->coef; if (this1 != NULL) this1 = this1->link; 第ㄧ個多項式指數大於第二個多項式 第ㄧ個多項式指數小於第二個多項式 兩個多項式指數相等,進行相加

if (ptr->coef != 0) { if (ans_h = = NULL) ans_h = ptr; else prev -> next = ptr; prev = ptr; } free (ptr);

五、使用鏈結串列製作堆疊 加入一個節點於堆疊中,由於堆疊的運作都在同一端,因此可將它視為將節點加入於串列的前端。 堆疊加入演算法 ptr void push(int num , node *ptr , node *top) { ptr = (node *)malloc(sizeof(node)); ptr->data=num; ptr->link=top; top=ptr; } top num 在程式中item為新加入的資料,堆疊的加入就相當單向鏈結串列中的加入前端,將ptr加入於top之前。 null

刪除堆疊頂端的頂點:其運作類似刪除串列的前端節點。 刪除資料的演算法 void pop(int num , node *top) { node *clear; if(top==NULL) printf(“stack is empty”); return; } clear=top; num=top->data; top=top->link; free(clear); 刪除堆疊頂端的頂點:其運作類似刪除串列的前端節點。 top clear top 堆疊的刪除就如同刪除單向鏈結串列於前端,在刪除前必須先以if(top==NULL)來測試堆疊是否為空的,若為空的則顯示堆疊內沒有資料後結束函數的執行。

六、使用鏈結串列製作佇列 佇列的加入 void AddQ(int num , node *front , node *rear) { node *ptr; ptr = (node *)malloc(sizeof(node)); ptr->data=num; ptr->next=NULL; if(rear==NULL) front=rear=ptr; else rear->link=ptr; rear=ptr; } front ptr rear null num null rear

六、使用鏈結串列製作佇列 佇列的刪除 void DeleteQ(int num , node *front) { node *clear; if (front==NULL) printf(“queue empty”); return; } num=front->data; clear=front; front=front->link; free(clear); clear front rear null