清華大學(xué)課件-鏈表的用法-PPT(全).ppt

1、2020/9/4,1,第9章 鏈表,2020/9/4,2,講授內(nèi)容,自引用結(jié)構(gòu)、鏈表的概念 內(nèi)存的動(dòng)態(tài)分配和釋放 單向鏈表的定義與操作 雙向鏈表的定義與操作,2020/9/4,3,9.1 鏈表的基本概念,結(jié)構(gòu)數(shù)組-必須將數(shù)組的大小設(shè)定成足夠大的值 太浪費(fèi) 能否需要多少分配多少？ 鏈表 = 動(dòng)態(tài)內(nèi)存分配 + 結(jié)構(gòu) + 指針 所有結(jié)構(gòu)形成一條鏈 可以在任何地方插入或刪除元素,2020/9/4,4,9.2 單向鏈表,自引用結(jié)構(gòu) 結(jié)構(gòu)中包含指向同類型結(jié)構(gòu)的指針 通過指針連接成鏈表，終點(diǎn)是NULL指針 (0),2020/9/4,5,9.2.1 單向鏈表定義,例子： struct node int dat

2、a; node * next; ; next：指向下一個(gè)node類型的結(jié)構(gòu)，連接node 的紐帶,2020/9/4,6,9.2.1 單向鏈表定義,存放學(xué)生信息的鏈表節(jié)點(diǎn) struct student int num; char name20; char sex; float score; student * next; ; 動(dòng)態(tài)申請(qǐng)內(nèi)存的方法 student *p=(student*) malloc(sizeof(student); 或 student * p = new student;,2020/9/4,7,9.2.2 單向鏈表的操作,建立單向鏈表 聲明一個(gè)鏈?zhǔn)字羔樧兞縣ead，并賦初值N

3、ULL(包含0個(gè)節(jié)點(diǎn)的鏈表) 動(dòng)態(tài)分配一個(gè)新節(jié)點(diǎn)，將該節(jié)點(diǎn)鏈入鏈尾 重復(fù)上一步,2020/9/4,8,例子1：建立鏈表，讀入n個(gè)整數(shù)，每個(gè)整數(shù)作為一個(gè)新結(jié)點(diǎn)插入到鏈尾,#include struct node int data; node * next; ; node * createList(int n); int main() int n; node * listHead = NULL; cout n; if (n 0) listHead = createList(n); return 0; ,2020/9/4,9,例子1：建立鏈表，讀入n個(gè)整數(shù)，每個(gè)整數(shù)作為一個(gè)新結(jié)點(diǎn)插入到鏈尾,node

4、 *createList(int n) node *temp, *tail = NULL, *head = NULL ; int num; cin num; head = new node ; / 為新節(jié)點(diǎn)動(dòng)態(tài)分配內(nèi)存 if (head = NULL) cout data = num; head-next = NULL; tail = head; ,2020/9/4,10,例子1：建立鏈表，讀入n個(gè)整數(shù)，每個(gè)整數(shù)作為一個(gè)新結(jié)點(diǎn)插入到鏈尾,for ( int i = 0; i num; temp = new node ; / 為新節(jié)點(diǎn)動(dòng)態(tài)分配內(nèi)存 if (temp = NULL) cout da

5、ta = num; temp-next = NULL; tail-next = temp; tail = temp; return head ; ,2020/9/4,11,建立鏈表過程,2020/9/4,12,建立鏈表過程,2020/9/4,13,9.2.2 單向鏈表的操作,遍歷鏈表 依次訪問鏈表中的每個(gè)節(jié)點(diǎn)的信息 head-data = 15; head-next-data = 15; 一般遍歷方法 node * curNode = head; while (curNode ) curNode = curNode-next;,2020/9/4,14,例子2：編寫一個(gè)函數(shù)，輸出例1鏈表中各節(jié)點(diǎn)

6、的data成員的值,void outputList(node * head) cout data; if (curNode -next) cout ; curNode = curNode -next; cout endl; return; ,2020/9/4,15,例子3：編寫一個(gè)函數(shù)，在例1的鏈表中查找包含指定整數(shù)的節(jié)點(diǎn),node * findData(int n, node * head) node *curNode = head; while ( curNode ) if ( curNode-data = n) coutnext; coutCant find n in the list.

7、endl; return NULL; ,2020/9/4,16,9.2.2 單向鏈表的操作,在鏈表中節(jié)點(diǎn)a之后插入節(jié)點(diǎn)c (1) 指針cptr指向節(jié)點(diǎn)c,aptr指向節(jié)點(diǎn)a； (2) 把a(bǔ)后繼節(jié)點(diǎn)的地址賦給節(jié)點(diǎn)c的后繼指針 cptr-nextaptr-next； (3) 把c的地址賦給節(jié)點(diǎn)a的后繼指針 aptr-next=cptr;,2020/9/4,17,例子4：編寫一個(gè)函數(shù)，將輸入的整數(shù)從小到大插入鏈表,node * insertData(int n, node * head) node *curNode = head;/ 指向插入點(diǎn)的后節(jié)點(diǎn) node *preNode = NULL;/

8、指向插入點(diǎn)的前節(jié)點(diǎn) node *newNode = NULL;/ 指向新建節(jié)點(diǎn) while (curNode!=NULL) ,2020/9/4,18,例子4：編寫一個(gè)函數(shù)，將輸入的整數(shù)從小到大插入鏈表,newNode-data = n; if (preNode = NULL) /插入到鏈表頭 newNode-next = curNode; return newNode; else preNode-next = newNode; newNode-next = curNode; return head; ,2020/9/4,19,9.2.2 單向鏈表的操作,從鏈表中刪除一個(gè)節(jié)點(diǎn)c (1)在鏈表中查

9、找要?jiǎng)h除的節(jié)點(diǎn)c，用指針cptr指向節(jié)點(diǎn)c; (2)如果c有前驅(qū)節(jié)點(diǎn)(設(shè)為d,用指針dptr指向d)，則將d的后繼指針指向c的后繼節(jié)點(diǎn)：dptr-next=cptr-next (3)釋放c占用的空間,2020/9/4,20,例子5：編寫一個(gè)函數(shù)，刪除鏈表中包含指定整數(shù)的節(jié)點(diǎn),node * deleteData(int n, node * head) node *curNode = head;/ 指向當(dāng)前節(jié)點(diǎn) node *preNode = NULL;/ 指向當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn) while (curNode / 返回鏈?zhǔn)字羔?,2020/9/4,21,9.3 雙向鏈表,單向鏈表：有利于從鏈?zhǔn)紫蜴?/p>

10、尾遍歷 有些時(shí)候雙向遍歷是需要的雙向鏈表,2020/9/4,22,9.3.1 雙向鏈表的定義,定義雙向鏈表的節(jié)點(diǎn)： struct node int data; node * next; /指向后續(xù)節(jié)點(diǎn) node * pre; /指向前面的節(jié)點(diǎn) ;,2020/9/4,23,9.3.1 雙向鏈表的定義,雙向鏈表的例子： 雙向鏈表一般也由頭指針唯一確定 雙向鏈表首尾相接可以構(gòu)成雙向循環(huán)鏈表,2020/9/4,24,9.3.2 雙向鏈表的操作,建立雙向鏈表 新節(jié)點(diǎn)鏈入鏈尾 原鏈尾節(jié)點(diǎn)的后繼指針指向新節(jié)點(diǎn) 新節(jié)點(diǎn)的前驅(qū)指針指向原鏈尾節(jié)點(diǎn) 新鏈尾節(jié)點(diǎn)的后繼指針置為空指針 將新節(jié)點(diǎn)鏈入鏈頭 原鏈頭節(jié)點(diǎn)的前驅(qū)

11、指針指向新節(jié)點(diǎn) 新節(jié)點(diǎn)的后繼指針指向原鏈頭節(jié)點(diǎn) 新鏈頭節(jié)點(diǎn)的前驅(qū)指針置為空指針,2020/9/4,25,例子6：編寫一個(gè)函數(shù)，按數(shù)據(jù)輸入的順序建立雙向鏈表,node *createBidirList (int n) node *temp, *tail = NULL, *head = NULL ; int num; cin num; head = new node ; / 為新節(jié)點(diǎn)動(dòng)態(tài)分配內(nèi)存 if (head = NULL) cout data = num; head-next = NULL; head-pre = NULL; tail = head; ,2020/9/4,26,例子6：編寫一

12、個(gè)函數(shù)，按數(shù)據(jù)輸入的順序建立雙向鏈表,for ( int i = 0; i num; temp = new node ; / 為新節(jié)點(diǎn)動(dòng)態(tài)分配內(nèi)存 if (temp = NULL) cout data = num; temp-next = NULL; temp-pre = tail; tail-next = temp; tail = temp; return head ; ,2020/9/4,27,9.3.2 雙向鏈表的操作,雙向鏈表的遍歷 有鏈?zhǔn)坠?jié)點(diǎn)，則可以沿著后繼指針從頭至尾遍歷 有鏈尾節(jié)點(diǎn)，則可以沿著前驅(qū)指針從尾向頭遍歷,2020/9/4,28,例子7：編寫一個(gè)函數(shù)，輸出雙向鏈表中各節(jié)點(diǎn)

13、的data成員的值,void outputBidirList(node * head) cout pre) cout data; if (curNode -next) cout ; curNode = curNode -next; cout endl; return; ,2020/9/4,29,9.3.2 雙向鏈表的操作,在雙向鏈表中插入和刪除一個(gè)節(jié)點(diǎn) 優(yōu)點(diǎn)：獲取插入節(jié)點(diǎn)或被刪除節(jié)點(diǎn)的前驅(qū)和后繼節(jié)點(diǎn)比較方便 注意點(diǎn)：需要維護(hù)的指針較多,2020/9/4,30,例子8：編寫函數(shù)，將整數(shù)n插入到一個(gè)已排序的雙向鏈表中(從小到大),node * insertData(int n, node * he

14、ad) node *curNode = head;/ 指向插入點(diǎn)的后節(jié)點(diǎn) node *preNode = NULL;/ 指向插入點(diǎn)的前節(jié)點(diǎn) node *newNode = NULL;/ 指向新建節(jié)點(diǎn) /尋找插入位置 while(curNode != NULL) ,2020/9/4,31,例子8：編寫函數(shù)，將整數(shù)n插入到一個(gè)已排序的雙向鏈表中(從小到大),newNode-data = n; if(preNode=NULL) /鏈頭 newNode-next = curNode; newNode-pre = NULL; if (curNode != NULL) curNode-pre = newN

15、ode; return newNode; if (curNode = NULL) / 鏈尾 newNode-pre = preNode; preNode-next = newNode; newNode-next = NULL; return head; ,2020/9/4,32,例子8：編寫函數(shù)，將整數(shù)n插入到一個(gè)已排序的雙向鏈表中(從小到大),else /鏈中 preNode-next = newNode; newNode-next = curNode; newNode-pre = preNode; curNode-pre = newNode; return head; ,2020/9/4,33,例子9：編寫函數(shù)，在雙向鏈表中查找并刪除指定,node * deleteData(int n, node * head) node *curNode = head;/ 指向當(dāng)前節(jié)點(diǎn) while ( curNode ,2020/9/4,34,例子9：編寫函數(shù)，在雙向鏈表中查找并刪除指定,if