數(shù)據(jù)結(jié)構(gòu)：鏈表

鏈表順序表與鏈表的比較數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第1頁。鏈表（LinkedList）鏈接表是線性表的鏈接存儲(chǔ)表示單鏈表靜態(tài)鏈表循環(huán)鏈表雙向鏈表數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第2頁。單鏈表(SinglyLinkedList)特點(diǎn)

每個(gè)元素(表項(xiàng))由結(jié)點(diǎn)(Node)構(gòu)成。線性結(jié)構(gòu)

結(jié)點(diǎn)可以連續(xù)，可以不連續(xù)存儲(chǔ)結(jié)點(diǎn)的邏輯順序與物理順序可以不一致表可擴(kuò)充datalinka0a1a2a3a4first數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第3頁。單鏈表的存儲(chǔ)映像free(a)可利用存儲(chǔ)空間a0a2a1a3freefirst(b)經(jīng)過一段運(yùn)行后的單鏈表結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第4頁。單鏈表的定義typedefcharListData;typedefstructnode{

//鏈表結(jié)點(diǎn)

ListDatadata;

//結(jié)點(diǎn)數(shù)據(jù)域

structnode*link;

//結(jié)點(diǎn)鏈域}ListNode;typedefListNode*LinkList;//鏈表頭指針LinkListfirst;//鏈表頭指針數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第5頁。單鏈表中的插入與刪除插入

第一種情況：在第一個(gè)結(jié)點(diǎn)前插入

newnode->link=first;first=newnode;（插入前）（插入后）

firstnewnodenewnodefirst數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第6頁。

(插入前)(插入后)

第二種情況：在鏈表中間插入

newnode->link=p->link; p->link=newnode；newnodepnewnodep數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第7頁。

第三種情況：在鏈表末尾插入

newnode->link=p->link; p->link=newnode；(插入前)(插入后)newnodenewnodepp數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第8頁。intInsert(LinkList&first,intx,inti){//在鏈表第

i個(gè)結(jié)點(diǎn)處插入新元素

x

ListNode*p=first;intk=0;while(

p!=NULL&&k<i-1)

{p=p->link;k++;

}

//找第i-1個(gè)結(jié)點(diǎn)

if(p==NULL&&first!=NULL){

printf(“無效的插入位置!\n”);return0;}ListNode*newnode=

//創(chuàng)建新結(jié)點(diǎn)

(ListNode*)malloc(sizeof(ListNode));

數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第9頁。

newnode->data=x;if(first==NULL||i==1){

//插在表前

newnode->link=first;

first=newnode;}else{

//插在表中或末尾

newnode->link=p->link;p->link=newnode;}

return1;

}數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第10頁。刪除第一種情況:刪除表中第一個(gè)元素第二種情況:刪除表中或表尾元素在單鏈表中刪除含ai的結(jié)點(diǎn)ai-1ai-1aiaiai+1ai+1pq刪除前刪除后數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第11頁。intDelete(LinkList&first,inti){//在鏈表中刪除第i個(gè)結(jié)點(diǎn)

ListNode*p,*q;if(i==1)

//刪除表中第

1個(gè)結(jié)點(diǎn)

{q=first;first=first->link;}else{

p=first;intk=0;

//找第i-1個(gè)結(jié)點(diǎn)

while(p!=NULL&&k<i-1)

{p=p->link;

k++;

}

數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第12頁。

if(p==NULL||p->link==NULL){

printf(“無效的刪除位置!\n”);return0;

}else{

//刪除表中或表尾元素

q=p->link;

//重新鏈接

p->link=q->link;}}free(q);

//刪除q

return1;

}數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第13頁。帶頭結(jié)點(diǎn)的單鏈表頭結(jié)點(diǎn)位于表的最前端，本身不帶數(shù)據(jù)，僅標(biāo)志表頭。設(shè)置頭結(jié)點(diǎn)的目的是統(tǒng)一空表與非空表的操作簡(jiǎn)化鏈表操作的實(shí)現(xiàn)。非空表 空表0ana1firstfirst0數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第14頁。在帶頭結(jié)點(diǎn)的單鏈表第一個(gè)結(jié)點(diǎn)前插入新結(jié)點(diǎn)

newnode->link=p->link;p->link=newnode;firstnewnodefirstnewnode插入firstnewnode0firstnewnode0插入pppp數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第15頁。

q=p->link;p->link=q->link;deleteq;

從帶頭結(jié)點(diǎn)的單鏈表中刪除第一個(gè)結(jié)點(diǎn)firstfirst(非空表）first0first(空表）0pqpq數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第16頁。前插法建立單鏈表從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)：生成新結(jié)點(diǎn)將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中將該新結(jié)點(diǎn)插入到鏈表的前端直到讀入結(jié)束符為止。firstnewnodefirstnewnode00數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第17頁。LinkListcreateListF(void){charch;ListNode*s;

LinkListhead=//建立頭結(jié)點(diǎn)(LinkList)malloc(sizeof(ListNode));head->link=NULL;while((ch=getchar())!=‘\n’){s=(listNode*)malloc(sizeof(ListNode));s->data=ch;

//建立新結(jié)點(diǎn)

s->link=head->link;

//插入到表前端

head->link=s;

}

returnhead;}

數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第18頁。后插法建立單鏈表每次將新結(jié)點(diǎn)加在鏈表的表尾；設(shè)置一個(gè)尾指針r，總是指向表中最后一個(gè)結(jié)點(diǎn)，新結(jié)點(diǎn)插在它的后面；尾指針r初始時(shí)置為指向頭結(jié)點(diǎn)地址。00newnodefirstnewnode00rrrr數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第19頁。LinkListcreateListR(void){charch;

LinkListhead=//建立表頭結(jié)點(diǎn)(LinkList)malloc(sizeof(ListNode));ListNode*s,*r=head;

//r指向表尾

while((ch=getchar())!=‘\n’){s=(listNode*)malloc(sizeof(ListNode));s->data=ch;

//建立新結(jié)點(diǎn)

r->link=s;r=s;

//插入到表末端

}

r->link=NULL;

//表收尾

returnhead;}

數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第20頁。firstqfirstfirstqqfirsta0a1a1a2a2a2單鏈表清空數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第21頁。單鏈表清空voidmakeEmpty(LinkListfirst){//刪去鏈表中除表頭結(jié)點(diǎn)外的所有其他結(jié)點(diǎn)

ListNode*q;

while(first->link!=NULL){ q=first->link;first->link=q->link;

//將表頭結(jié)點(diǎn)后第一個(gè)結(jié)點(diǎn)從鏈中摘下

free(q);

//釋放它

}

}數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第22頁。firstpa0a1a2c=0firstpa0a1a2c=1firstpa0a1a2c=2firstpa0a1a2c=3計(jì)算單鏈表長(zhǎng)度數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第23頁。intLength(LinkListfirst){

ListNode*p=first->link;

//檢測(cè)指針p

指示第一個(gè)結(jié)點(diǎn)

intcount=0;

while(p!=NULL){

//逐個(gè)結(jié)點(diǎn)檢測(cè)

p=p->link;count++;}

returncount;}計(jì)算單鏈表長(zhǎng)度數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第24頁。ListNode

*Find(LinkListfirst,ListData

value

){//在鏈表中從頭搜索其數(shù)據(jù)值為value的結(jié)點(diǎn)

ListNode*p=first->link;

//檢測(cè)指針

p

指示第一個(gè)結(jié)點(diǎn)

while(p!=NULL&&p->data!=value)

p=p->link;

returnp;}在單鏈表中按值查找數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第25頁。ListNode*Locate(LinkListfirst,inti){//返回表中第i

個(gè)元素的地址

if(i<0)returnNULL;

//i值不合理

ListNode*p=first;intk=0;//置于表頭

while(p!=NULL&&k<i)

{p

=p->link;k++;}

//找第i個(gè)結(jié)點(diǎn)

if(k==i)returnp;

elsereturnNULL;//返回第i個(gè)結(jié)點(diǎn)地址或NULL}在單鏈表中按序號(hào)查找（定位）數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第26頁。在單鏈表中插入新結(jié)點(diǎn)

newnode->link=p->link;p->link=newnode;firstnewnodefirstnewnode插入newnodenewnode插入pppp數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第27頁。intInsert(LinkListfirst,ListDatax,inti){//將新元素x插入在鏈表中第i

號(hào)結(jié)點(diǎn)位置

ListNode*p=Locate(first,i-1);

if(p==NULL)return0; //不插入

ListNode*newnode=//創(chuàng)建新結(jié)點(diǎn)

(ListNode*)malloc(sizeof(ListNode));newnode->data=x;

newnode->link=p->link;//鏈入

p->link=newnode;return1;

//插入成功，函數(shù)返回1}在單鏈表中插入新元素?cái)?shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第28頁。在單鏈表中刪除一個(gè)結(jié)點(diǎn)

q=p->link;p->link=q->link;deleteq;

first0firstpppqqq數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第29頁。intdelete(LinkListfirst,inti){//將鏈表第i

號(hào)元素刪去

ListNode*p=Locate(first,i-1);

//尋找被刪結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)

if(p==NULL||p->link==NULL)

return0; //不刪除

ListNode*q=p->link;

//被刪結(jié)點(diǎn)地址

p->link=q->link;

//摘下被刪結(jié)點(diǎn)

free(q

);

//釋放

returnl;}在單鏈表中刪除一個(gè)結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第30頁?！纠繂捂湵砬蠛秃瘮?shù)

typedefintListData;

intsum(LinkListls){

ListNode*p=ls->link;intretvalue=0;while(p!=NULL){retvalue+=p->data;//

累加

p=p->link;}

returnretvalue; }數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第31頁。靜態(tài)鏈表結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第32頁。靜態(tài)鏈表定義constintMaxSize=100;//靜態(tài)鏈表大小typedefintListData;typedefstructnode{//靜態(tài)鏈表結(jié)點(diǎn)

ListDatadata;

intlink;}SNode;typedefstruct{//靜態(tài)鏈表

SNodeNodes[MaxSize];intnewptr; //當(dāng)前可分配空間首地址}SLinkList;數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第33頁。將鏈表空間初始化voidInitList(SLinkListSL){SL.Nodes[0].link=-1;SL.newptr=1;//當(dāng)前可分配空間從1開始

//建立帶表頭結(jié)點(diǎn)的空鏈表

for(inti=1;i<MaxSize-1;i++)SL.Nodes[i].link=i+1;

//構(gòu)成空閑鏈接表

SL.Nodes[MaxSize-1].link=-1;

//鏈表收尾}數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第34頁。在靜態(tài)鏈表中查找具有給定值的結(jié)點(diǎn)intFind(SLinkListSL,ListDatax){

intp=SL.Nodes[0].link;

//指針p指向鏈表第一個(gè)結(jié)點(diǎn)

while(p!=-1)

if(SL.Nodes[p].data!=x)p=SL.Nodes[p].link;elsebreak;

//逐個(gè)結(jié)點(diǎn)檢測(cè)查找具有給定值的結(jié)點(diǎn)

returnp;}數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第35頁。在靜態(tài)鏈表的表尾追加一個(gè)新結(jié)點(diǎn)intAppend(SLinkListSL,ListDatax){

if(SL.newptr==-1)return0;//追加失敗

intq=SL.newptr;//分配結(jié)點(diǎn)

SL.newptr=SL.Nodes[SL.newptr].link;SL.Nodes[q].data=x;SL.Nodes[q].link=NULL;

intp=0;//查找表尾

while(SL.Nodes[p].link!=-1)p=SL.Nodes[p].link;SL.Nodes[p].link=q;//追加

return1;}數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第36頁。在靜態(tài)鏈表中查找第

i個(gè)結(jié)點(diǎn)intLocate(SLinkListSL,inti){

if(i<0)return

-1;//參數(shù)不合理

intj=0,p=SL.Nodes[0].link;while(p!=-1&&j<i){

//循鏈查找第i號(hào)結(jié)點(diǎn)

p=SL.Nodes[p].link;

j++;}

if(i==0)return0;

returnp;}數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第37頁。在靜態(tài)鏈表第

i個(gè)結(jié)點(diǎn)處插入一個(gè)新結(jié)點(diǎn)intInsert(SLinkListSL,inti,ListDatax){

intp=Locate(SL,i-1);if(p==-1)return0;//找不到結(jié)點(diǎn)

intq=SL.newptr;//分配結(jié)點(diǎn)

SL.newptr=SL.Nodes[SL.newptr].link;SL.Nodes[q].data=x;SL.Nodes[q].link=SL.Nodes[p].link;SL.Nodes[p].link=q;//插入

return1;}數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第38頁。在靜態(tài)鏈表中釋放第

i個(gè)結(jié)點(diǎn)intRemove(SLinkListSL,inti){

intp=Locate(SL,i-1);if(p==-1)return0;//找不到結(jié)點(diǎn)

intq=SL.Nodes[p].link;//第i號(hào)結(jié)點(diǎn)

SL.Nodes[p].link=SL.Nodes[q].link;

SL.Nodes[q].link=SL.newptr;//釋放

SL.newptr=q;return1;}數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第39頁。循環(huán)鏈表(CircularList)循環(huán)鏈表是單鏈表的變形。循環(huán)鏈表最后一個(gè)結(jié)點(diǎn)的link

指針不為NULL，而是指向了表的前端。為簡(jiǎn)化操作，在循環(huán)鏈表中往往加入表頭結(jié)點(diǎn)。循環(huán)鏈表的特點(diǎn)是：只要知道表中某一結(jié)點(diǎn)的地址，就可搜尋到所有其他結(jié)點(diǎn)的地址。數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第40頁。循環(huán)鏈表的示例帶表頭結(jié)點(diǎn)的循環(huán)鏈表

a0a1a2an-1firstan-1firsta1a0first(空表)(非空表)數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第41頁。查找成功查找不成功循環(huán)鏈表的查找firstfirst3131484815155757查找15查找25pppppppp數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第42頁。循環(huán)鏈表的定義typedefcharListData;typedefstructcnode{

//鏈表結(jié)點(diǎn)

ListDatadata;

//結(jié)點(diǎn)數(shù)據(jù)域

structcnode*link;

//結(jié)點(diǎn)鏈域}CircListNode;typedefCircListNode*CircLinkList;//循環(huán)鏈表頭指針CircLinkListfirst;//循環(huán)鏈表頭指針數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第43頁。循環(huán)鏈表的查找算法CircListNode

*Find(CircLinkListfirst,ListData

value

){//在鏈表中從頭搜索其數(shù)據(jù)值為value的結(jié)點(diǎn)

CircListNode*p=first->link;

//檢測(cè)指針

p

指示第一個(gè)結(jié)點(diǎn)

while(p!=first&&p->data!=value)

p=p->link;

returnp;}數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第44頁。帶尾指針的循環(huán)鏈表rear3148155722

如果插入與刪除僅在鏈表的兩端發(fā)生，可采用帶表尾指針的循環(huán)鏈表結(jié)構(gòu)。在表尾插入，時(shí)間復(fù)雜性O(shè)(1)

在表尾刪除，時(shí)間復(fù)雜性O(shè)(n)

在表頭插入，相當(dāng)于在表尾插入在表頭刪除，時(shí)間復(fù)雜性O(shè)(1)數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第45頁。將循環(huán)鏈表鏈入單鏈表鏈頭rear1520253010first60657055rear1520253010p60657055first數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第46頁。雙向鏈表(DoublyLinkedList)雙向鏈表是指在前驅(qū)和后繼方向都能游歷(遍歷)的線性鏈表。雙向鏈表每個(gè)結(jié)點(diǎn)結(jié)構(gòu)：

雙向鏈表通常采用帶表頭結(jié)點(diǎn)的循環(huán)鏈表形式。前驅(qū)方向

后繼方向priordatanext數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第47頁。結(jié)點(diǎn)指向

p==p->prior->next==p->next->prior非空表

空表p->priorp->nextppriornextfirstfirst數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第48頁。雙向循環(huán)鏈表的定義typedefintListData;typedefstructdnode{

ListNodedata;//數(shù)據(jù)

structdnode*prior,*next;//指針}DblNode;typedefDblNode*DblList;//雙向鏈表

數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第49頁。建立空的雙向循環(huán)鏈表voidCreateDblList(DblList&

first){

first=(DblNode*)malloc

(sizeof(DblNode));

if(first==NULL)

{print(“存儲(chǔ)分配錯(cuò)!\n”);exit(1);}first->prior=first->next=first;

//表頭結(jié)點(diǎn)的鏈指針指向自己}數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第50頁。計(jì)算雙向循環(huán)鏈表的長(zhǎng)度intLength(DblListfirst){//計(jì)算帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表的長(zhǎng)度

DblNode*p=first->next;

intcount=0;

while(p!=first)

{p=p->next;count++;

}returncount;}數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第51頁。查找成功查找不成功雙向循環(huán)鏈表的查找firstfirst3131484815155757查找15查找25數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第52頁。ListNode*Find(DblListfirst,ListDatax){//在雙向循環(huán)鏈表中搜索含x的結(jié)點(diǎn),

若找到,//則返回該結(jié)點(diǎn)的地址,否則返回表頭地址。

DblNode*p=first->next;

while(p!=first&&p->data!=x)p=p->next; returnp;}//也可以在prior(前驅(qū))方向查找,程序類似。數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第53頁。DblNode*Locate(DblListfirst,inti){

if(i<0)returnfirst;

DblNode*p=first->next;intj=1;

while(p!=first&&j<i)

{p=p->next;j++;}returnp;}//也可以在prior(前驅(qū))方向查找,程序類似。定位：查找第i個(gè)結(jié)點(diǎn)在鏈中的位置數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第54頁。雙向循環(huán)鏈表的插入(非空表)firstfirst314815在結(jié)點(diǎn)*p

后插入25pp31482515q->prior=p; q->next=p->next;p->next=q;q->next->prior=q;q數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第55頁。雙向循環(huán)鏈表的插入(空表)first在結(jié)點(diǎn)*p后插入25pq25q->prior=p; q->next=p->next;

(=first)p->next=q;q->next->prior=q;

(first->prior=q)

firstp數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第56頁。intInsert(DblListfirst,inti,ListDatax){DblNode*p=Locate(first,i-1);

//指針定位于插入位置

if(p==first&&i!=1)return0;DblNode*q=(DblNode*)malloc(sizeof(DblNode));//分配結(jié)點(diǎn)

q->data=x;

q->prior=p; p->next->prior=q;

//在前驅(qū)方向鏈入新結(jié)點(diǎn)

q->next=p->next;p->next=q;

//在后繼方向鏈入新結(jié)點(diǎn)

return1;}數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第57頁。刪除48雙向循環(huán)鏈表的刪除firstfirst非空表314815p3115p->next->prior=p->prior;p->prior->next=p->next;數(shù)據(jù)結(jié)構(gòu)：鏈表全文共66頁，當(dāng)前為第58頁。刪除31雙向循環(huán)