2024/4/81第9章鏈表2024/4/82講授內(nèi)容自引用結(jié)構(gòu)、鏈表的概念內(nèi)存的動態(tài)分配和釋放單向鏈表的定義與操作雙向鏈表的定義與操作2024/4/839.1鏈表的基本概念結(jié)構(gòu)數(shù)組--必須將數(shù)組的大小設(shè)定成足夠大的值太浪費(fèi)能否需要多少分配多少？鏈表=動態(tài)內(nèi)存分配+結(jié)構(gòu)+指針?biāo)薪Y(jié)構(gòu)形成一條鏈可以在任何地方插入或刪除元素2024/4/849.2單向鏈表自引用結(jié)構(gòu)結(jié)構(gòu)中包含指向同類型結(jié)構(gòu)的指針通過指針連接成鏈表，終點(diǎn)是NULL指針(0)2024/4/859.2.1單向鏈表定義例子：structnode{intdata;node*next;};

next：指向下一個node類型的結(jié)構(gòu)，連接node的紐帶head2852296NULL2024/4/869.2.1單向鏈表定義存放學(xué)生信息的鏈表節(jié)點(diǎn)structstudent{intnum;charname[20];charsex;floatscore;student*next;};動態(tài)申請內(nèi)存的方法student*p=(student*)malloc(sizeof(student));或student*p=newstudent;2024/4/879.2.2單向鏈表的操作建立單向鏈表聲明一個鏈?zhǔn)字羔樧兞縣ead，并賦初值NULL(包含0個節(jié)點(diǎn)的鏈表)動態(tài)分配一個新節(jié)點(diǎn)，將該節(jié)點(diǎn)鏈入鏈尾重復(fù)上一步2024/4/88例子1：建立鏈表，讀入n個整數(shù)，每個整數(shù)作為一個新結(jié)點(diǎn)插入到鏈尾#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;}2024/4/89例子1：建立鏈表，讀入n個整數(shù)，每個整數(shù)作為一個新結(jié)點(diǎn)插入到鏈尾node*createList(intn){node*temp,*tail=NULL,*head=NULL;intnum;

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

if(head==NULL){

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

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

if(temp==NULL){

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

2024/4/811建立鏈表過程tailtempheadNULL初始狀態(tài)NULLNULL讀入1后tailtemphead1NULL2024/4/812建立鏈表過程讀入2后tailtemphead12NULL讀入3后tailtemphead13NULL22024/4/8139.2.2單向鏈表的操作遍歷鏈表依次訪問鏈表中的每個節(jié)點(diǎn)的信息head->data=15;head->next->data=15;一般遍歷方法node*curNode=head;while(curNode)curNode=curNode->next;2024/4/814例子2：編寫一個函數(shù)，輸出例1鏈表中各節(jié)點(diǎn)的data成員的值voidoutputList(node*head){cout<<"List:";node*curNode=head;while(curNode){cout<<curNode->data;if(curNode->next) cout<<"->";curNode=curNode->next;}cout<<endl;return;}2024/4/815例子3：編寫一個函數(shù)，在例1的鏈表中查找包含指定整數(shù)的節(jié)點(diǎn)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;}2024/4/8169.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->next＝aptr->next；(3)把c的地址賦給節(jié)點(diǎn)a的后繼指針aptr->next=cptr;2024/4/817例子4：編寫一個函數(shù)，將輸入的整數(shù)從小到大插入鏈表node*insertData(intn,node*head){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)&&(curNode->data<n)){preNode=curNode;//后節(jié)點(diǎn)變?yōu)榍肮?jié)點(diǎn)

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

if(newNode==NULL){

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

newNode->next=curNode;

returnnewNode;}

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

returnhead;}}2024/4/8192024/4/8209.2.2單向鏈表的操作從鏈表中刪除一個節(jié)點(diǎn)c(1)在鏈表中查找要刪除的節(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占用的空間2024/4/821例子5：編寫一個函數(shù)，刪除鏈表中包含指定整數(shù)的節(jié)點(diǎn)node*deleteData(intn,node*head){node*curNode=head;//指向當(dāng)前節(jié)點(diǎn)

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

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

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

head=head->next;else

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

2024/4/8229.3雙向鏈表單向鏈表：有利于從鏈?zhǔn)紫蜴溛脖闅v有些時候雙向遍歷是需要的——雙向鏈表2024/4/8239.3.1雙向鏈表的定義定義雙向鏈表的節(jié)點(diǎn)：structnode{intdata; node*next;//指向后續(xù)節(jié)點(diǎn) node*pre;//指向前面的節(jié)點(diǎn)};2024/4/8249.3.1雙向鏈表的定義雙向鏈表的例子：雙向鏈表一般也由頭指針唯一確定雙向鏈表首尾相接可以構(gòu)成雙向循環(huán)鏈表head28NULL52296NULL2024/4/8259.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ū)指針指向新節(jié)點(diǎn)新節(jié)點(diǎn)的后繼指針指向原鏈頭節(jié)點(diǎn)新鏈頭節(jié)點(diǎn)的前驅(qū)指針置為空指針2024/4/826例子6：編寫一個函數(shù)，按數(shù)據(jù)輸入的順序建立雙向鏈表node*createBidirList(intn){node*temp,*tail=NULL,*head=NULL; intnum;

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

if(head==NULL) {

cout<<"Nomemoryavailable!";returnNULL;}else{head->data=num;head->next=NULL;head->pre=NULL;tail=head;}2024/4/827例子6：編寫一個函數(shù)，按數(shù)據(jù)輸入的順序建立雙向鏈表for(inti=0;i<n-1;i++){cin>>num;temp=newnode;//為新節(jié)點(diǎn)動態(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;}2024/4/8289.3.2雙向鏈表的操作雙向鏈表的遍歷有鏈?zhǔn)坠?jié)點(diǎn)，則可以沿著后繼指針從頭至尾遍歷有鏈尾節(jié)點(diǎn)，則可以沿著前驅(qū)指針從尾向頭遍歷2024/4/829例子7：編寫一個函數(shù)，輸出雙向鏈表中各節(jié)點(diǎn)的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;}2024/4/8309.3.2雙向鏈表的操作在雙向鏈表中插入和刪除一個節(jié)點(diǎn)優(yōu)點(diǎn)：獲取插入節(jié)點(diǎn)或被刪除節(jié)點(diǎn)的前驅(qū)和后繼節(jié)點(diǎn)比較方便注意點(diǎn)：需要維護(hù)的指針較多2024/4/831例子8：編寫函數(shù)，將整數(shù)n插入到一個已排序的雙向鏈表中(從小到大)node*insertData(intn,node*head){ 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)&&(curNode->data<n)){ preNode=curNode; curNode=curNode->next; } newNode=newnode;//為新節(jié)點(diǎn)動態(tài)分配內(nèi)存

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

cout<<"Notmemoryavailable!"; returnhead; }2024/4/832例子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; }2024/4/833例子8：編寫函數(shù)，將整數(shù)n插入到一個已排序的雙向鏈表中(從小到大) else {//鏈中

preNode->next