清華大學(xué)10課件

第11章鏈表及其應(yīng)用1本章主要內(nèi)容鏈表的基本概念鏈表的基本操作方法循環(huán)鏈表雙向鏈表鏈表的應(yīng)用2清華大學(xué)黃維通設(shè)計(jì)制作11.1鏈表的基本概念3清華大學(xué)黃維通設(shè)計(jì)制作structstu{intnum;floatvalue;數(shù)據(jù)域

charname[20];…structstu*next;指針域};鏈表的存儲(chǔ)結(jié)構(gòu)在內(nèi)存空間上由兩個(gè)域組成5清華大學(xué)黃維通設(shè)計(jì)制作6清華大學(xué)黃維通設(shè)計(jì)制作線性表的順序表示和實(shí)現(xiàn)用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。通常用數(shù)組來描述。特點(diǎn)：邏輯上相鄰的兩個(gè)元素，在物理上也具有相鄰的存儲(chǔ)位置?？梢噪S機(jī)存取任何一個(gè)元素。插入和刪除時(shí)需要移動(dòng)大量元素空間不能充分得到利用表的容量難以擴(kuò)充7清華大學(xué)黃維通設(shè)計(jì)制作

從以上討論可知，線性表順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是邏輯關(guān)系相鄰的兩個(gè)元素，其物理位置也相鄰，因此可以隨機(jī)存取表中任意元素，它的存儲(chǔ)位置可以用一個(gè)簡(jiǎn)單、直觀的表達(dá)式來表示，但刪除、修改時(shí)，需移動(dòng)大量的元素。而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：不要求邏輯上相鄰的元素在物理位置上也相鄰，因此它沒有順序存儲(chǔ)結(jié)構(gòu)所具有的弱點(diǎn)，但也失去了順序表可隨機(jī)存儲(chǔ)的優(yōu)點(diǎn)。9清華大學(xué)黃維通設(shè)計(jì)制作定義：線性表是n個(gè)數(shù)據(jù)元素的有限序列。線性表的基本操作判斷線性表是否為空構(gòu)造一個(gè)空線性表將一個(gè)線性表重置為空表求線性表的元素個(gè)數(shù)求線性表的第i個(gè)元素的值在線性表中查找第一個(gè)滿足指定條件的元素求指定元素的前驅(qū)，即為ai前面的元素ai-1求指定元素的后繼在線性表的第i個(gè)元素之前插入一個(gè)新元素刪除線性表的第i個(gè)元素遍歷線性表銷毀一個(gè)線性表線性表的定義和基本操作10清華大學(xué)黃維通設(shè)計(jì)制作11.1.2動(dòng)態(tài)內(nèi)存分配在棧上創(chuàng)建：保存函數(shù)內(nèi)的局部變量，函數(shù)結(jié)束時(shí)自動(dòng)地釋放掉內(nèi)存分配方式從靜態(tài)存儲(chǔ)區(qū)域分配：在程序編譯時(shí)分配，在程序的整個(gè)運(yùn)行期間都存在。比如全局變量和靜態(tài)變量從堆上分配：即動(dòng)態(tài)內(nèi)存分配，用malloc向系統(tǒng)申請(qǐng)一連續(xù)的內(nèi)存空間，不再需要時(shí)，用free函數(shù)釋放11清華大學(xué)黃維通設(shè)計(jì)制作11.2.1鏈表的建立使第一個(gè)結(jié)點(diǎn)的next指針指向第二個(gè)結(jié)點(diǎn)cursorcursor13清華大學(xué)黃維通設(shè)計(jì)制作如何使第二個(gè)結(jié)點(diǎn)的next指針指向第三個(gè)結(jié)點(diǎn)呢？cursorcursor14清華大學(xué)黃維通設(shè)計(jì)制作【例】創(chuàng)建一個(gè)包含表頭結(jié)點(diǎn)和10個(gè)結(jié)點(diǎn)的鏈表，假設(shè)這個(gè)鏈表表征學(xué)生的數(shù)據(jù)，包含學(xué)生的學(xué)號(hào)、考試成績(jī)。#include"stdlib.h"#include"stdio.h“#defineLENsizeof(structstu)structstu{intnum;floatscore;structstu*next;};15清華大學(xué)黃維通設(shè)計(jì)制作tempnode->score=20.5*i+10;cursor->next=tempnode; //將結(jié)點(diǎn)連接到鏈表上cursor=cursor->next; //移到下一個(gè)結(jié)點(diǎn)printf("num=%d,score=%f\n",tempnode->num,tempnode->score);}printf("\n");return(mylist);}

17清華大學(xué)黃維通設(shè)計(jì)制作調(diào)用create()函數(shù)的主函數(shù)及鏈表輸出函數(shù)print(structstu*list){structstu*cursor;cursor=list;if(list!=NULL)

do{cursor=cursor->next;//依次遍歷鏈表

printf("%d%f\n",cursor->num,cursor->score);}while(cursor->next!=NULL);}voidmain(){intn; //鏈表結(jié)點(diǎn)數(shù)structstu*my_list;scanf("%d",&n); //輸入鏈表結(jié)點(diǎn)數(shù)my_list=create(n); //返回所創(chuàng)建的鏈表print(my_list);}18清華大學(xué)黃維通設(shè)計(jì)制作對(duì)鏈表結(jié)點(diǎn)的訪問，必須從頭結(jié)點(diǎn)開始，依次遍歷鏈表，直到找到該結(jié)點(diǎn)(如果所要找的數(shù)據(jù)在鏈表的尾結(jié)點(diǎn)上，則需要遍歷整個(gè)鏈表才能找到)。而數(shù)組可以通過下標(biāo)快速定位元素的存儲(chǔ)位置。下面給出找第n個(gè)結(jié)點(diǎn)的算法。11.2.2鏈表結(jié)點(diǎn)的訪問

19清華大學(xué)黃維通設(shè)計(jì)制作【例】鏈表的連接。structstu*link(structstu*list1,structstu*list2){structstu*cursor;cursor=list1;

while(cursor->next!=NULL)cursor=cursor->next; //找到第一個(gè)鏈表的最后一個(gè)結(jié)點(diǎn)cursor->next=list2->next; //將兩個(gè)鏈表連接起來return(list1);}11.2.3同結(jié)構(gòu)鏈表的連接

21清華大學(xué)黃維通設(shè)計(jì)制作11.2.4鏈表結(jié)點(diǎn)的插入

第一種情況：在頭結(jié)點(diǎn)之前插入22清華大學(xué)黃維通設(shè)計(jì)制作第二種情況：在鏈表的中間位置插入結(jié)點(diǎn)

23清華大學(xué)黃維通設(shè)計(jì)制作【例】無表頭結(jié)點(diǎn)的鏈表中結(jié)點(diǎn)的插入structstu*insert_node(structstu*list,structstu*newnode){structstu*cursor;cursor=list;if(cursor==NULL||cursor->num>newnode->num)//鏈表為空，或新結(jié)點(diǎn)的num值在鏈表結(jié)點(diǎn)中是最小的，則插入到第一個(gè)結(jié)點(diǎn)的位置。{newnode->next=cursor;list=newnode;}25清華大學(xué)黃維通設(shè)計(jì)制作else//插入表中和表尾的情況同時(shí)處理{while(cursor->next&&cursor->next->num<newnode->num)

//若cursor不為尾結(jié)點(diǎn)，且下一結(jié)點(diǎn)的num值仍小于newnode的num值，繼續(xù)向后移動(dòng)光標(biāo)cursor=cursor->next;newnode->next=cursor->next;cursor->next=newnode; //將newnode插入到cursor與cursor->next之間}returnlist;}26清華大學(xué)黃維通設(shè)計(jì)制作【例】刪除帶無表頭結(jié)點(diǎn)的鏈表結(jié)點(diǎn)算法structstu*delete_node_withhead(structstu*list,intvalue){structstu*cursor;cursor=list;if(cursor->num==value){list=cursor->next;free(cursor);}

else//刪除頭結(jié)點(diǎn){while(cursor->next&&cursor->next->num!=value)cursor=cursor->next;//若cursor->next為有效結(jié)點(diǎn)且不是要?jiǎng)h除//的結(jié)點(diǎn)，則cursor指針向后移動(dòng)。

if(cursor->next)cursor->next=cursor->next->next;}return(list);}29清華大學(xué)黃維通設(shè)計(jì)制作【例】刪除不帶有表頭結(jié)點(diǎn)的鏈表結(jié)點(diǎn)算法structstu*delete_node_withouthead(structstu*list,intvalue){structstu*cursor;cursor=list;

while(cursor->next&&cursor->next->num!=value)cursor=cursor->next;if(cursor->next)//若cursor->next為有效結(jié)點(diǎn)且該結(jié)點(diǎn)不//是要?jiǎng)h除的結(jié)點(diǎn)，cursor指針向后移動(dòng)cursor->next=cursor->next->next;return(list);}30清華大學(xué)黃維通設(shè)計(jì)制作【例】鏈表存儲(chǔ)空間的釋放。voidfree_list(structstu*list){structstu*tempnode;while(list){ tempnode=list; list=list->next; free(tempnode);}}11.2.6釋放鏈表存儲(chǔ)空間

31清華大學(xué)黃維通設(shè)計(jì)制作11.3循環(huán)鏈表

帶表頭的空循環(huán)鏈表帶表頭的非空的循環(huán)鏈表32清華大學(xué)黃維通設(shè)計(jì)制作structstu_dual{intnum;floatscore;structstu_dual*next;//指向后繼結(jié)點(diǎn)的指針structstu_dual*previous;//指向前驅(qū)結(jié)點(diǎn)的指針}11.4雙向鏈表

雙鏈表的結(jié)構(gòu)定義雙向循環(huán)鏈表33清華大學(xué)黃維通設(shè)計(jì)制作對(duì)鏈表結(jié)點(diǎn)的操作，要先確定結(jié)點(diǎn)位置，然后才進(jìn)行操作，此外，由于鏈表需要額外的空間開銷，這將影響性能11.5鏈表的應(yīng)用

【例】合并兩個(gè)有序鏈表的并從大到小順序輸出排序后的結(jié)果#include"stdlib.h"#include"stdio.h"structstu{intnum;structstu*next;};34清華大學(xué)黃維通設(shè)計(jì)制作structstu*Merge(structstu*list1,structstu*list2){structstu*cursor1=list1; //指向list1structstu*cursor2=list2; //指向list2structstu*tmp; //保存插入前cursor2的位置

while(cursor1!=NULL&&cursor2!=NULL){if(cursor2->num<=cursor1->num){tmp=cursor2;cursor2=cursor2->next;tmp->next=cursor1; //插入tmplist1=tmp;cursor1=tmp;}35清華大學(xué)黃維通設(shè)計(jì)制作elseif(cursor2->num>cursor1->num&&cursor1->next==NULL){cursor1->next=cursor2;break;}elseif(cursor2->num>cursor1->num&&

cursor2->num<=cursor1->next->num){tmp=cursor2; //cursor2位于cursor1之后后移cursor2cursor2=cursor2->next;tmp->next=cursor1->next;//插入cursor2cursor1->next=tmp;}else cursor1=cursor1->next;}list1=list1->next; return(list