線性表順序表 鏈表順序表與鏈表的比較

線性表順序表鏈表順序表與鏈表的比較第二章線性表線性表(LinearList)線性表的定義和特點(diǎn)

定義

n（0）個(gè)數(shù)據(jù)元素的有限序列，記作

（a1,a2,…,an）

ai

是表中數(shù)據(jù)元素，n是表長度。

遍歷逐項(xiàng)訪問：

從前向后從后向前線性表的特點(diǎn)除第一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè)直接前驅(qū)。除最后一個(gè)元素外，其他每一個(gè)元素有一個(gè)且僅有一個(gè)直接后繼。a1a2a3a4a5a6順序表(SequentialList)順序表的定義和特點(diǎn)

定義將線性表中的元素相繼存放在一個(gè)連續(xù)的存儲空間中?？衫靡痪S數(shù)組描述存儲結(jié)構(gòu)特點(diǎn)

線性表的順序存儲方式

遍歷順序訪問,可以隨機(jī)存取

253457164809

012345data順序表的連續(xù)存儲方式352749186054778341020123456789llll

l

lllll

LOC(i)=LOC(i-1)+l=a+i*lLOC(i)=

LOC(i-1)+l=a+i*l,i>0

a,i=0

a+i*la順序表(SeqList)的定義#defineListSize100//最大允許長度typedefintListData;typedefstruct

{

ListData*data;

//存儲數(shù)組

intlength; //當(dāng)前元素個(gè)數(shù)}SeqList;

順序表基本運(yùn)算的實(shí)現(xiàn)構(gòu)造一個(gè)空的順序表

voidInitList

(

SeqList&L){

L.data=(ListData*)

malloc

(ListSize*

sizeof(ListData)

);if(L.data==NULL){

printf

(“存儲分配失敗!\n”

);exit(1);}L.length=0;}求表的長度

int

Length(SeqList&L){returnL.length;

}

提取函數(shù)：在表中提取第i個(gè)元素的值

ListData

GetData(SeqList

&L,int

i){

if(i>=0&&i<L.length)

returnL.data[i];

else

printf(“參數(shù)

i不合理！\n”); }

//在出錯(cuò)情況，函數(shù)返回值不能用！按值查找：在順序表中從頭查找結(jié)點(diǎn)值等于給定值x

的結(jié)點(diǎn)

int

Find(SeqList&L,ListDatax){

int

i=0;while(i<L.length&&L.data[i]!=x)i++;if(i<L.length)returni;elsereturn-1;}順序查找圖示253457164809

012345data查找

16i253457164809

i253457164809

i253457164809

i查找成功2534571648

01234data查找

50i2534571648

i2534571648

i2534571648

i2534571648

i查找失敗查找成功的平均比較次數(shù)

若查找概率相等，則

查找不成功數(shù)據(jù)比較n

次表項(xiàng)的插入2534571648096301234567data50插入x253457501648096301234567data50i

表項(xiàng)的插入

int

Insert(SeqList

&L,ListDatax,

inti){//在表中第

i個(gè)位置插入新元素

x

if(i<0

||

i>L.length

||L.length==

ListSize)

return0;//插入不成功

else{

for(

intj=L.length;j>i;j--)L.data[j]=L.data[j-1]; L.data[i]=x;L.length++;

return1;

//插入成功

}}表項(xiàng)的刪除253457501648096301234567data16刪除

x2534575048096301234567data

表項(xiàng)的刪除

int

Delete(SeqList

&L,ListDatax){

//在表中刪除已有元素

x

int

i=Find(L,x);

//在表中查找

x

if(i>=0){ L.length--

; for(

intj=i;j<L.length;j++)L.data[j]=L.data[j+1];

return1; //成功刪除

}

return0;//表中沒有

x}順序表的應(yīng)用：集合的“并”運(yùn)算voidUnion(SeqList

&A,SeqList

&B){

int

n=Length(A);

intm=Length(B);

for(

inti=0;i<m;i++){

intx=GetData(B,i);//在B中取一元素

int

k=Find(A,x);

//在A中查找它

if(k==

-1)

//若未找到插入它

{Insert(A,x,n);n++;}

}}

voidIntersection(SeqList

&A,SeqList

&B){

int

n=Length(A);

intm=Length(B);int

i=0;

while(i<n){

intx=GetData(A,i);//在A中取一元素

int

k=Find(B,x);//在B中查找它

if(k==-1){Delete(A,i);n--;} elsei++;//未找到在A中刪除它}}順序表的應(yīng)用：集合的“交”運(yùn)算鏈表（LinkedList）鏈接表是線性表的鏈接存儲表示單鏈表靜態(tài)鏈表

循環(huán)鏈表雙向鏈表單鏈表(SinglyLinkedList)特點(diǎn)

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

結(jié)點(diǎn)可以連續(xù)，可以不連續(xù)存儲結(jié)點(diǎn)的邏輯順序與物理順序可以不一致表可擴(kuò)充datalinka0a1a2a3a4first單鏈表的存儲映像free(a)可利用存儲空間a0a2a1a3freefirst(b)經(jīng)過一段運(yùn)行后的單鏈表結(jié)構(gòu)單鏈表的定義typedefchar

ListData;typedefstructnode{

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

ListDatadata;

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

struct

node*link;

//結(jié)點(diǎn)鏈域}ListNode;typedef

ListNode*LinkList;//鏈表頭指針LinkListfirst;//鏈表頭指針單鏈表中的插入與刪除插入

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

newnode->link=first;

first=newnode;（插入前）（插入后）

firstnewnodenewnodefirst

(插入前)(插入后)

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

newnode->link=p->link; p->link=newnode；newnodepnewnodep

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

newnode->link=p->link; p->link=newnode；(插入前)(插入后)newnodenewnodeppint

Insert(LinkList&first,

intx,int

i){//在鏈表第

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));

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

//插在表前

newnode->link=first;

first=newnode;}else{

//插在表中或末尾

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

return1;

}刪除第一種情況:刪除表中第一個(gè)元素第二種情況:刪除表中或表尾元素在單鏈表中刪除含ai的結(jié)點(diǎn)ai-1ai-1aiaiai+1ai+1pq刪除前刪除后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++;

}

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

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

}else{

//刪除表中或表尾元素

q=p->link;

//重新鏈接

p->link=q->link;

}}free(q);

//刪除q

return1;

}帶表頭結(jié)點(diǎn)的單鏈表表頭結(jié)點(diǎn)位于表的最前端，本身不帶數(shù)據(jù)，僅標(biāo)志表頭。設(shè)置表頭結(jié)點(diǎn)的目的是統(tǒng)一空表與非空表的操作簡化鏈表操作的實(shí)現(xiàn)。非空表

空表0ana1firstfirst0在帶表頭結(jié)點(diǎn)的單鏈表第一個(gè)結(jié)點(diǎn)前插入新結(jié)點(diǎn)

newnode->link=p->link;p->link=newnode;firstnewnodefirstnewnode插入firstnewnode0firstnewnode0插入pppp

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

從帶表頭結(jié)點(diǎn)的單鏈表中刪除第一個(gè)結(jié)點(diǎn)firstfirst(非空表）first0first(空表）0pqpq前插法建立單鏈表從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)：生成新結(jié)點(diǎn)將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中將該新結(jié)點(diǎn)插入到鏈表的前端直到讀入結(jié)束符為止。firstnewnodefirstnewnode00LinkListcreateListF(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;}

后插法建立單鏈表每次將新結(jié)點(diǎn)加在鏈表的表尾；設(shè)置一個(gè)尾指針r，總是指向表中最后一個(gè)結(jié)點(diǎn)，新結(jié)點(diǎn)插在它的后面；尾指針r初始時(shí)置為指向表頭結(jié)點(diǎn)地址。00newnodefirstnewnode00rrrrLinkListcreateListR(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;}

firstqfirstfirstqqfirsta0a1a1a2a2a2單鏈表清空單鏈表清空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);

//釋放它

}

}firstpa0a1a2c=0firstpa0a1a2c=1firstpa0a1a2c=2firstpa0a1a2c=3計(jì)算單鏈表長度int

Length(LinkListfirst){

ListNode*p=first->link;

//檢測指針p

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

int

count=0;

while(p!=NULL){

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

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

returncount;}計(jì)算單鏈表長度ListNode

*Find(LinkListfirst,ListData

value

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

ListNode*p=first->link;

//檢測指針

p

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

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

p=p->link;

returnp;}在單鏈表中按值查找ListNode*Locate(LinkListfirst,

inti){//返回表中第i

個(gè)元素的地址

if(i<0)returnNULL;

//i值不合理

ListNode*p=first;

int

k=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}在單鏈表中按序號查找（定位）在單鏈表中插入新結(jié)點(diǎn)

newnode->link=p->link;p->link=newnode;firstnewnodefirstnewnode插入newnodenewnode插入ppppintInsert(LinkListfirst,ListDatax,

int

i){//將新元素x插入在鏈表中第i

號結(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}在單鏈表中插入新元素在單鏈表中刪除一個(gè)結(jié)點(diǎn)

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

first0firstpppqqqintdelete(LinkListfirst,int

i){//將鏈表第i

號元素刪去

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ù)

typedefint

ListData;

intsum(LinkListls){

ListNode*p=

ls->link;

intretvalue=0;while(p!=NULL){

retvalue+=p->data;//

累加

p=p->link;}

returnretvalue; }循環(huán)鏈表(CircularList)循環(huán)鏈表是單鏈表的變形。循環(huán)鏈表最后一個(gè)結(jié)點(diǎn)的link

指針不為NULL，而是指向了表的前端。為簡化操作，在循環(huán)鏈表中往往加入表頭結(jié)點(diǎn)。循環(huán)鏈表的特點(diǎn)是：只要知道表中某一結(jié)點(diǎn)的地址，就可搜尋到所有其他結(jié)點(diǎn)的地址。循環(huán)鏈表的示例帶表頭結(jié)點(diǎn)的循環(huán)鏈表

a0a1a2an-1firstan-1firsta1a0first(空表)(非空表)查找成功查找不成功循環(huán)鏈表的查找firstfirst3131484815155757查找15查找25pppppppp循環(huán)鏈表的定義typedefchar

ListData;typedefstructcnode

{

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

ListDatadata;

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

structcnode*link;

//結(jié)點(diǎn)鏈域}CircListNode;typedef

CircListNode*CircLinkList;//循環(huán)鏈表頭指針CircLinkListfirst;//循環(huán)鏈表頭指針循環(huán)鏈表的查找算法CircListNode

*Find(CircLinkListfirst,ListData

value

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

CircListNode*p=first->link;

//檢測指針

p

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

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

p=p->link;

returnp;}帶尾指針的循環(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)將循環(huán)鏈表鏈入單鏈表鏈頭rear1520253010first60657055rear1520253010p60657055first雙向鏈表(DoublyLinkedList)雙向鏈表是指在前驅(qū)和后繼方向都能游歷(遍歷)的線性鏈表。雙向鏈表每個(gè)結(jié)點(diǎn)結(jié)構(gòu)：

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

后繼方向priordata

next結(jié)點(diǎn)指向

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

空表p->priorp->nextppriornextfirstfirst雙向循環(huán)鏈表的定義typedefintListData;typedefstructdnode

{

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

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

建立空的雙向循環(huán)鏈表void

CreateDblList(DblList&

first){

first=(DblNode*)malloc

(sizeof

(DblNode));

if(first==NULL)

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

//表頭結(jié)點(diǎn)的鏈指針指向自己}計(jì)算雙向循環(huán)鏈表的長度int

Length(DblListfirst){//計(jì)算帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表的長度

DblNode*p=first->next;

intcount=0;

while(p!=first)

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

}returncount;}查找成功查找不成功雙向循環(huán)鏈表的查找firstfirst3131484815155757查找15查找25ListNode*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ū))方向查找,程序類似。DblNode*Locate(DblListfirst,int

i){

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)在鏈中的位置雙向