清華大學(xué)課件-鏈表的用法-PPT(全)學(xué)習(xí)資料

清華大學(xué)課件-鏈表的用法-PPT(全)9.1鏈表的基本概念結(jié)構(gòu)數(shù)組--必須將數(shù)組的大小設(shè)定成足夠大的值太浪費能否需要多少分配多少？鏈表=動態(tài)內(nèi)存分配+結(jié)構(gòu)+指針?biāo)薪Y(jié)構(gòu)形成一條鏈可以在任何地方插入或刪除元素2023/1/1329.2單向鏈表

自引用結(jié)構(gòu)結(jié)構(gòu)中包含指向同類型結(jié)構(gòu)的指針通過指針連接成鏈表，終點是NULL指針(0)2023/1/1339.2.1單向鏈表定義例子：structnode{intdata;node*next;};

next：指向下一個node類型的結(jié)構(gòu)，連接node的紐帶head2852296NULL2023/1/1349.2.1單向鏈表定義存放學(xué)生信息的鏈表節(jié)點structstudent{intnum;charname[20];charsex;floatscore;student*next;};動態(tài)申請內(nèi)存的方法student*p=(student*)malloc(sizeof(student));或student*p=newstudent;2023/1/1359.2.2單向鏈表的操作建立單向鏈表聲明一個鏈?zhǔn)字羔樧兞縣ead，并賦初值NULL(包含0個節(jié)點的鏈表)動態(tài)分配一個新節(jié)點，將該節(jié)點鏈入鏈尾重復(fù)上一步2023/1/136例子1：建立鏈表，讀入n個整數(shù)，每個整數(shù)作為一個新結(jié)點插入到鏈尾#include<iostream.h>structnode{ intdata; node*next;};node*createList(intn);intmain(){intn;node*listHead=NULL;cout<<"Pleaseenterthenumberofnodes:";cin>>n;if(n>0) listHead=createList(n);

return0;}2023/1/137例子1：建立鏈表，讀入n個整數(shù)，每個整數(shù)作為一個新結(jié)點插入到鏈尾node*createList(intn){node*temp,*tail=NULL,*head=NULL;intnum;

cin>>num;head=newnode;//為新節(jié)點動態(tài)分配內(nèi)存

if(head==NULL){

cout<<"Nomemoryavailable!";returnNULL; } else{head->data=num;head->next=NULL;tail=head;}2023/1/138例子1：建立鏈表，讀入n個整數(shù)，每個整數(shù)作為一個新結(jié)點插入到鏈尾

for(inti=0;i<n-1;i++){cin>>num;temp=newnode;//為新節(jié)點動態(tài)分配內(nèi)存

if(temp==NULL){

cout<<"Nomemoryavailable!";returnhead;}else {temp->data=num;temp->next=NULL;tail->next=temp;tail=temp;}} returnhead;}

2023/1/139建立鏈表過程tailtempheadNULL初始狀態(tài)NULLNULL讀入1后tailtemphead1NULL2023/1/1310建立鏈表過程讀入2后tailtemphead12NULL讀入3后tailtemphead13NULL22023/1/13119.2.2單向鏈表的操作遍歷鏈表依次訪問鏈表中的每個節(jié)點的信息head->data=15;

head->next->data=15;一般遍歷方法node*curNode=head;while(curNode)curNode=curNode->next;

2023/1/1312例子2：編寫一個函數(shù)，輸出例1鏈表中各節(jié)點的data成員的值voidoutputList(node*head){cout<<"List:";node*curNode=head;while(curNode){cout<<curNode->data;if(curNode->next) cout<<"->";curNode=curNode->next;}cout<<endl;return;}2023/1/1313例子3：編寫一個函數(shù)，在例1的鏈表中查找包含指定整數(shù)的節(jié)點node*findData(intn,node*head){node*curNode=head;while(curNode){if(curNode->data==n){cout<<"Find"<<n<<"inthelist."<<endl;returncurNode;}curNode=curNode->next;}cout<<"Can'tfind"<<n<<"inthelist."<<endl;returnNULL;}

2023/1/13149.2.2單向鏈表的操作在鏈表中節(jié)點a之后插入節(jié)點c(1)指針cptr指向節(jié)點c,aptr指向節(jié)點a；(2)把a(bǔ)后繼節(jié)點的地址賦給節(jié)點c的后繼指針

cptr->next＝aptr->next；(3)把c的地址賦給節(jié)點a的后繼指針aptr->next=cptr;2023/1/1315例子4：編寫一個函數(shù)，將輸入的整數(shù)從小到大插入鏈表node*insertData(intn,node*head){node*curNode=head;//指向插入點的后節(jié)點

node*preNode=NULL;//指向插入點的前節(jié)點

node*newNode=NULL;//指向新建節(jié)點while((curNode!=NULL)&&(curNode->data<n)){preNode=curNode;//后節(jié)點變?yōu)榍肮?jié)點

curNode=curNode->next;}newNode=newnode;

if(newNode==NULL){

cout<<"Nomemoryavailable!"; returnhead; }2023/1/1316例子4：編寫一個函數(shù)，將輸入的整數(shù)從小到大插入鏈表newNode->data=n;if(preNode==NULL)//插入到鏈表頭{

newNode->next=curNode;

returnnewNode;}

else{preNode->next=newNode;newNode->next=curNode;

returnhead;}}2023/1/13179.2.2單向鏈表的操作從鏈表中刪除一個節(jié)點c(1)在鏈表中查找要刪除的節(jié)點c，用指針cptr指向節(jié)點c;(2)如果c有前驅(qū)節(jié)點(設(shè)為d,用指針dptr指向d)，則將d的后繼指針指向c的后繼節(jié)點：dptr->next=cptr->next(3)釋放c占用的空間2023/1/1318例子5：編寫一個函數(shù)，刪除鏈表中包含指定整數(shù)的節(jié)點node*deleteData(intn,node*head){node*curNode=head;//指向當(dāng)前節(jié)點

node*preNode=NULL;//指向當(dāng)前節(jié)點的前驅(qū)節(jié)點

while(curNode&&curNode->data!=n){preNode=curNode;//當(dāng)前節(jié)點變?yōu)榍膀?qū)節(jié)點curNode=curNode->next;}

if(curNode==NULL){cout<<"Can'tfind"<<n<<"inthelist"<<endl;returnhead;}if(preNode==NULL)//刪除鏈?zhǔn)坠?jié)點

head=head->next;else

preNode->next=curNode->next;deletecurNode;returnhead; //返回鏈?zhǔn)字羔榼

2023/1/13199.3雙向鏈表單向鏈表：有利于從鏈?zhǔn)紫蜴溛脖闅v有些時候雙向遍歷是需要的——雙向鏈表2023/1/13209.3.1雙向鏈表的定義定義雙向鏈表的節(jié)點：structnode{intdata; node*next;//指向后續(xù)節(jié)點 node*pre;//指向前面的節(jié)點};2023/1/13219.3.1雙向鏈表的定義雙向鏈表的例子：雙向鏈表一般也由頭指針唯一確定雙向鏈表首尾相接可以構(gòu)成雙向循環(huán)鏈表head28NULL52296NULL2023/1/13229.3.2雙向鏈表的操作建立雙向鏈表新節(jié)點鏈入鏈尾原鏈尾節(jié)點的后繼指針指向新節(jié)點新節(jié)點的前驅(qū)指針指向原鏈尾節(jié)點新鏈尾節(jié)點的后繼指針置為空指針將新節(jié)點鏈入鏈頭原鏈頭節(jié)點的前驅(qū)指針指向新節(jié)點新節(jié)點的后繼指針指向原鏈頭節(jié)點新鏈頭節(jié)點的前驅(qū)指針置為空指針2023/1/1323例子6：編寫一個函數(shù)，按數(shù)據(jù)輸入的順序建立雙向鏈表node*createBidirList(intn){node*temp,*tail=NULL,*head=NULL; intnum;

cin>>num;head=newnode;//為新節(jié)點動態(tài)分配內(nèi)存

if(head==NULL) {

cout<<"Nomemoryavailable!";returnNULL;}else{head->data=num;head->next=NULL;head->pre=NULL;tail=head;}2023/1/1324例子6：編寫一個函數(shù)，按數(shù)據(jù)輸入的順序建立雙向鏈表for(inti=0;i<n-1;i++){cin>>num;temp=newnode;//為新節(jié)點動態(tài)分配內(nèi)存

if(temp==NULL){

cout<<"Nomemoryavailable!";returnhead;}else{temp->data=num;temp->next=NULL;temp->pre=tail;tail->next=temp;tail=temp;}}returnhead;}2023/1/13259.3.2雙向鏈表的操作雙向鏈表的遍歷有鏈?zhǔn)坠?jié)點，則可以沿著后繼指針從頭至尾遍歷有鏈尾節(jié)點，則可以沿著前驅(qū)指針從尾向頭遍歷2023/1/1326例子7：編寫一個函數(shù)，輸出雙向鏈表中各節(jié)點的data成員的值voidoutputBidirList(node*head){cout<<"List:";node*curNode=head;while(curNode){if(curNode->pre)cout<<"<-";cout<<curNode->data;if(curNode->next)cout<<"->";curNode=curNode->next;}cout<<endl;return;}2023/1/13279.3.2雙向鏈表的操作在雙向鏈表中插入和刪除一個節(jié)點優(yōu)點：獲取插入節(jié)點或被刪除節(jié)點的前驅(qū)和后繼節(jié)點比較方便注意點：需要維護(hù)的指針較多2023/1/1328例子8：編寫函數(shù)，將整數(shù)n插入到一個已排序的雙向鏈表中(從小到大)node*insertData(intn,node*head){ node*curNode=head; //指向插入點的后節(jié)點

node*preNode=NULL; //指向插入點的前節(jié)點

node*newNode=NULL; //指向新建節(jié)點 //尋找插入位置

while((curNode!=NULL)&&(curNode->data<n)){ preNode=curNode; curNode=curNode->next; } newNode=newnode;//為新節(jié)點動態(tài)分配內(nèi)存

if(newNode==NULL){//內(nèi)存分配不成功

cout<<"Notmemoryavailable!"; returnhead; }2023/1/1329例子8：編寫函數(shù)，將整數(shù)n插入到一個已排序的雙向鏈表中(從小到大) newNode->data=n; if(preNode==NULL) {//鏈頭

newNode->next=curNode; newNode->pre=NULL; if(curNode!=NULL) curNode->pre=newNode; returnnewNode; } if(curNode==NULL) {//鏈尾

newNode->pre=preNode; preNode->next=newNode; newNode->next=NULL; returnhead; }2023/1/1330例子8：編寫函數(shù)，將整數(shù)n插入到一個已排序的雙向鏈表中(從小到大) else {//鏈中

preNode->next=newNode; newNode->next=curNode; n