第二章線性表線性表是程序設計中最常遇到的一種操作對象，也是數據結構中最簡單、最重要的結構形式之一。線性表的概念及運算順序表及基本運算的實現鏈表及基本運算的實現應用實例一個線性表是n（表長）個數據元素的有限序列，記為：

(a1,a2,a3…,an)線性表可描述為：Liner-list=(D,R)，

其中：

D={ai|ai∈dataobject,1≤i≤n,n≥0}R={<ai-1,ai>|ai-1,ai∈D,2≤i≤n}線性表的基本概念

線性表的定義【例1】

英文字母表（A,B,C,…..,Z)是一個線性表。【例2】數據元素

線性表的邏輯特點對于非空的線性表(a1,a2,a3…,an)，有且僅有一個開始結點a1，有且僅有一個終端結點an

當i=1,2,…n-1時，ai有且僅有一個直接后繼ai+1

當i=2,…n時，ai有且僅有一個直接前趨ai-1線性表的基本概念線性表的抽象數據類型

ADTLinearlist

{

數據對象D：D={ai|ai∈dataobject,1≤i≤n,n≥0}

數據關系R：R={<ai,ai-1>|ai-1,ai∈D,2≤i≤n}

操作集合：CreatList(&L)構造空表Length(L)求表長Get(L,i)取結點Locate(L,x)定位Insert(L,x,i)插入Delete(L,i)刪除Prior(L,ai)取直接前趨Next(L,ai)取直接后繼}線性表的基本概念線性表的運算①CreatList(&L)構造空表②Length(L)求表長③Get(L,i)取結點⑦Prior(L,ai)取直接前趨④Locate(L,x)定位⑤Insert(L,x,i)插入⑥Delete(L,i)刪除更復雜的運算可利用以上基本運算實現⑧Next(L,ai)取直接后繼線性表的基本概念【例3】利用線性表的基本運算清除表L中多余的重復結點。voidPurge(Linear_list

L){

//刪除Ｌ中重復出現的多余結點

inti=1,j,x,y;

while(i<Length(L)){

x=Get(L,i);//取當前第i個結點

j=i+1;

while(j<=Length(L)){

y=Get(L,j);//取當前第j個結點

if(x==y)Delete(L,j);//

刪除當前第j個結點

elsej++;

}

i++;

}

}

線性表的基本概念順序表用一組地址連續的存儲單元依次存儲線性表的元素。元素地址的計算Loc(ai)=Loc(a1)+(i-1)*LLoc(ai+1)=Loc(ai)+La1a2an01n-112n內存a數組下標元素序號M-1…......備用空間其中：L—元素占用的存儲單元個數LOC(ai)—表中第i個元素的起始地址線性表的順序存儲結構順序表的類型描述a1a2an01n-112n內存a數組下標元素序號M-1…......備用空間【例】

typedefstructstu

{

intnum;

charname[20];

floatscore;}datatype;#defineM1000datatypedata[M];typedefintdatatype;#defineM1000datatypedata[M];線性表的順序存儲結構data[MAX]lastL向量中最后元素的位置順序表的類型描述線性表的順序存儲結構

typedefintdatatype;#defineMAX100typedefstruct

{

datatypedata[MAX];intlast;

}sequenlist;

sequenlist*L;也可定義成：順序存儲結構的特點順序表是用向量實現的線性表；以元素在計算機內物理位置的緊鄰來表示元素之間的邏輯關系。順序存儲結構是隨機存取結構；線性表的順序存儲結構順序表的運算——插入若在順序表的第i（1

i

n+1）個位置插入一個新的數據元素x，則：實現：將第i

至第

n

共（n-i+1）個元素后移，并將x放置插入位置。(a1,…,ai-1,x,ai,

…,an)

(a1,…,ai-1,ai,

…,an)x內存a1a2aiai+1an01i-1下標n-1i12i元素序號i+1n..................內存a1a2aian01i-1下標n-1i12i元素序號i+1n............an-1n+1n......順序表的運算——插入intInsert(sequenlist

L,intx,inti){

intj;

if((L->last)==maxsize

1)

{

//

表空間溢出

printf("overflow");

return(0);

}

else

if((i<1)||(i>(L->last+2)

{//

非法位置

printf("error");

return(0);

}

else

{

for(j=L->last;j>=i

1;j

)

L->data[j+1]=L->data[j];//

結點后移

L->data[i

1]=x;//插入x，存在L->data[i

1]中

L->last=L->last+1;//

終端結點下標加1

}

return1;

}順序表的運算——插入若刪除順序表的第i（1

i

n）個位置的數據元素，則：實現：將第n

至第

i+1

共（n-i）個元素前移。(a1,…,ai-1,ai+1,

…,an)

(a1,…,ai-1,ai,

…,an)順序表的運算——刪除內存a1a2ai+101i-1a數組下標n-212i元素序號n-1............an......內存a1a2aiai+1an01i-1a數組下標n-1i12i元素序號i+1n..................順序表的運算——刪除intDelete(sequenlist

L,inti){

intj;

if((i<1)||(i>L->last+1)){//非法位置

print("error");

return0

;}

else{

for(j=i;j<=L->last;j++)//第i個結點下標值是i

1

L->data[j

1]=L->data[j];//結點前移

L->last

;//表長減1

}

return1;

}順序表的運算——刪除插入運算設pi是在第i個位置上插入一個元素的概率，則在長度為n的線性表中插入一個元素時，所需移動元素的平均次數為：期望值：離散型隨機變量的一切可能的取值xi與對應的概率之積的和。即隨機變量的平均取值。順序表的運算——算法分析設Qi是刪除第i個元素的概率，則在長度為n的線性表中刪除一個元素所需移動元素的平均次數為：

刪除運算順序表的運算——算法分析

結論在順序表上進行或刪除運算時，均需移動表中約一半的元素。若表長為n，則兩個算法的時間復雜度為O(n)。因此，當表長n較大時，算法的效率較低。順序表的運算——算法分析線性表的鏈式存儲結構

順序存儲結構的優點邏輯相鄰，物理相鄰；存儲空間使用緊湊。順序存儲結構是隨機存取結構，可隨機存取任一元素，存儲位置可用簡單、直觀公式表示；

順序存儲結構的缺點插入、刪除操作需要移動大量的元素；預先分配空間需按最大空間分配，空間利用不充分；表的容量難以擴充。線性表的鏈式存儲結構鏈式存儲結點結構用一組任意的存儲單元存儲線性表的數據元素利用指針體現元素之間的邏輯關系每個ai除存儲本身信息外，還需存儲其直接后繼地址信息數據域：元素本身信息指針域：指示直接后繼的存儲位置數據域指針域【例4】

線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)。LIQIANSUNWANGWUZHAOZHENGZHOU存儲地址17131925313743鏈式存儲無法表達元素間的邏輯關系ZHAOQIANSUNLIZHOUWUZHENGWANG順序存儲01i-16......存儲地址線性表的鏈式存儲結構頭指針31HLIQIANSUNWANGWUZHAOZHENGZHOU存儲地址17131925313743數據域指針域431371913NULL725ZHAOQIANSUNLIZHOUWUZHENGWANG∧H【例4】

線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)。線性表的鏈式存儲結構結點中只含一個指針域的鏈表叫單鏈表。結點空間的分配與釋放分配結點空間p=(linklist*)

malloc(sizeof(linklist))

;系統回收結點空間free(p);單鏈表特點非隨機存取頭指針唯一確定單鏈表typedefstructnode

{

datatypedata;structnode*next;}

linklist;linklist*head,*p;類型描述單鏈表從一個空表開始，重復讀入數據，生成新結點，將數據存放到新結點的數據域中，然后將新結點插入到當前鏈表的表頭上，直至數據輸入結束。【例5】

建立單鏈表存放(a,b,c,d,e)。①s=(linklist*)malloc(sizeof(linklist));abheadd②s->data=‘d’;③s->next=head;④head=s;單鏈表的建立——頭插法linklist

CreateListF(){

charch;

linklist

head,

s;

head=NULL;//

鏈表開始為空

ch=getchar();//

讀入第一個結點的值

while(ch!='$'){

//

'$'為結束標志

s=(linklist

)malloc(sizeof(linlist));

s→data=ch;

s→next=head;

head=s;//將新結點插入到表頭上

ch=getchar();//讀入下一個結點的值

}

returnhead;//返回鏈表頭指針}abheadsd單鏈表的建立——頭插法【例6】

建立單鏈表存放(a,b,c,d,e)。ahead①s=(linklist*)malloc(sizeof(linklist));②s->data='c';③r->next=s;將新結點插入到當前鏈表的表尾上。為此必須增加一個尾指針r，使其始終指向當前鏈表的表尾。brc④r=s;單鏈表的建立——尾插法linkist

CreatListR(){

charch;

linklist

head,

s,

r;

head=NULL;r=head;//頭指針、尾指針初值為空

ch=getchar();

while(ch!='$'){//'$'為輸入結束符

s=(linklist

)malloc(sizeof(linklist));

s→data=ch;

if(head==NULL)head=s;

//新結點插入空表elser->next=s;

//

非空表，新結點插入表尾

r=s;

//尾指針r指向新的表尾

ch=getchar();

//讀入下一個結點的值

}

if(r!=NULL)

r→next=NULL;

returnhead;

//返回表頭指針}單鏈表的建立——尾插法分析上述算法必須對第一個位置上的插入操作進行特殊處理。改進：在開始結點之前附加一個頭結點。頭結點

head

…

∧非空表

head空表

∧單鏈表的建立——尾插法帶頭結點鏈表的優點（1）開始結點和其它結點處理一致；（2）空表和非空表的處理一致。linkist

CreatListR(){

charch;

linklist

head,

s,

r;

head=(linklist

)malloc(sizeof(linklist));

//

生成頭結點

r=head;//尾指針指向頭結點

ch=getchar();

while(ch!='$'){//

'$'為輸入結束符

s=(linklist

)malloc(sizeof(linklist));

s→data=ch;

r→next=s;

//

新結點插入表尾

r=s;

//尾指針r指向新的表尾

ch=getchar();//

讀入下一個結點的值

}

r→next=NULL;

returnhead;

//返回表頭指針}單鏈表的建立——尾插法【例7】

查找單鏈表head中的第3個結點。①p=head;i=0;

//

i為計數器②while((i!=3)&&(p->next!=NULL)){p=p->next;i++;}ppp返回地址p

d∧cbaheadp單鏈表的查找——按序號//帶頭結點的單鏈表

linklist

Get(linklist

head,inti)

{

intj;

linklinst

p;

p=head;j=0;//從頭結點開始掃描

while((p→next!=NULL)&&(j<i)

{

p=p→next;

//

掃描下一個結點

j++;//

已掃描結點計數器

}

if(j==i)

//找到了第i個結點

returnp;

else

returnNULL;//

i>n，找不到}

單鏈表的查找——按序號【例8】

查找單鏈表head中值為'c'的結點。①p=head;②while((p->data!='c')&&(p->next!=NULL))p=p->next;ppp返回地址p

d∧cbaheadp單鏈表的查找——按序號//帶頭結點的單鏈表linklinst

Locate(linklinst

head,datatypekey)

{

linklist

p;

p=head→next;

//從開始結點比較

while(p!=NULL)

if(p→data!=key)

p=p→next;//沒找到，繼續循環

else

break;//找到結點key，退出循環

returnp;//若p!=NULL，則找到結點}

單鏈表的查找——按值查pxs……③④②s->data=x;③s->next=p->next;④p->next=s;①s=(linklist*)malloc(sizeof(linklist));①②將結點*s插入到結點*p之后注意第③步和第④的次序單鏈表的插入

單鏈表的查找——按值查voidInsertAfter(linklist

p,datatypex){

linklist

s;

s=(linklist

)malloc(sizeof(linkist));s→data=x;

s→next=p→next;p→next=s;//

將*s插入*p之后

}算法評價：T(n)=O(1)算法：

單鏈表的查找——按值查voidInsertAfter(linklist

p,datatypex){

linklist

s;

s=(linklist

)malloc(sizeof(linkist));s→data=x;

s→next=p→next;p→next=s;//

將*s插入*p之后

}算法評價：T(n)=O(1)算法：

單鏈表的插入將結點*s插入到結點*p之前pxs……③⑤②s->data=x;③q=head;

whiel(q->next!=p)q=q->next;④q->next=s;①s=(linklist*)malloc(sizeof(linklist));①②q④⑤s->next=p;

單鏈表的插入算法：//

帶頭結點的單鏈表

voidInsertBefore(linkist

head,linkist

p,intx)

{

linklis

s,

q;

s=(linklist

)malloc(sizeof(linklist));

s→data=x;

q=head;//從頭指針開始

while(q→next!=p)//查找

p的前趨結點

q

q=q→next;

s→next=p;

q→next=s;//將新結點

s插入

p之前

}(1)算法評價：T(n)=O(n)(3)如何修改算法，改進時間性能為：

T(n)=O(1)(2)若表無頭結點，則*p是開始結點時，需特殊處理。…headp

單鏈表的插入改進算法：//算法T(n)=O(1)

voidInsertBefore(linkist

head,linkist

p,intx)

{

linklis

s,

q;

datatypet;

s=(linklist

)malloc(sizeof(linklist));

s→data=x;

s->next=p->next;

p->next=s;

//將*s插入到*p之后

t=s->data;//

交換數據

s->data=p->data;

p->data=t;

}

單鏈表的插入【例9】

在單鏈表上實現線性表的插入運算Insert(L,x,i)。…headpii-1voidInsert(linklist

L,datatypex,inti)

{

linklist

p;

intj;if((i<1)||(i>n)){printf(“error”);return(0);}

j=i

1;

p=GET(L,j);

//

找第i

1個結點

p

InsertAfter(p,x);

//將新結點插到

p之后}

單鏈表的刪除刪除結點*pp……②q->next=p->next;③free(p);①q=head;

whiel(q->next!=p)q=q->next;①q②③

存儲池

單鏈表的刪除算法：

void

Delete(linklist

p,linklist

head){

linklist

q;

q=head;

while(q→next!=p)//查找*p的前趨結點

q=q→next;

q→next=p→next;//刪除結點

p

free(p);

//釋放結點

p

}

單鏈表的刪除【例10】

在單鏈表上實現線性表的刪除運算Delete(L,i)。voidDelete(linklist

L,inti)

{

linklist

p,

r;intj;

j=i

1;

p=GET(L,j);//找第i

1個結點

if((p!=NULL)&&(p→next!=NULL)

{

r=p→next;//

*r為結點

p的后繼

p→next=r→next;//

將結點*r從鏈表上摘下

free(r);//

釋放結點*r

}

else//

i<1或i>n

printf(“error”)

}算法評價：T(n)=O(n)…headpir

單鏈表的運算【例11】將兩個遞增單鏈表合并為一個遞增單鏈表(不另辟空間)。將lb中的結點依此插入到la中。分析：la1510∧lb241112∧p（1）if(p→data≤q→data)

{

r=p;

p=p→next;

}（2）if(p→data＞q→data){

u=q->next;

r→next=q;q→next=p;r=q;q=u;

}ulb241112∧rq

單鏈表的運算linklist*Union(linklist*la,linklist*lb){linklist*p,*q,*r,*u;p=la->next;q=lb->next;r=la;

while(p!=NULL)&&(q!=NULL){if(p→data≤q→data){r=p;p=p→next;}else{

u=q->next;r→next=q;

q→next=p;r=q;q=u;

}

}if(q!=NULL)r→next=q;returnla;}

算法：head空表head

非空表表中最后一個結點的指針指向頭結點，使鏈表構成環狀

特點：從表中任一結點出發均可找到表中其他結點，提高查找效率，方便操作。

操作與單鏈表基本一致，循環條件不同

單鏈表

p==NULL或

p->next==NULL

循環鏈表p==head或

p->next==head

循環鏈表【例12】

在循環鏈表的第i個元素之后插入元素x。voidInsert(linklist

head,datatypex,inti)

{

linklist

s;

intj;

p=head;j=0;

while((p→next!=head)&&(j<i))

{

p=p→next;j++;

}

if(i==j)

{

s=(

linklist)malloc(sizeof(linklist));

s→data=x;

//生成值為x的新結點

s→next=p→next;p→next=s;

//插入操作

}

elseprintf(“error”);}

循環鏈表L空雙向循環鏈表非空雙向循環鏈表LAB克服了單鏈表的單向性的缺點，便于操作。特點

雙向鏈表typedefstructnode

{datatypedata;structnode*prior,*next;}dlinklist*head;類型描述L空雙向循環鏈表bcapp->prior->next=p=p->next->proir

雙向鏈表克服了單鏈表的單向性的缺點，便于操作。特點typedefstructnode

{datatypedata;structnode*prior,*next;}dlinklist*head;類型描述雙向鏈表bcap②p->next->prior=p->prior;①p->prior->next=p->next;③free(p)voidDeleteNodeP(dlinklist*p)

{

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

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

free(p);}算法：算法評價：T(n)=O(1)雙向鏈表算法：baps①x②③④⑤⑥voidDINSERTBEFORE(dlinklist*p,dadatypex)

{

dlinklist*s;

s=(dlinklist*)malloc(sizeof(dlinklist));

s->data=x;s->prior=p->prior;

s->next=p;

p->prior->next=s;

p->prior=s;}算法評價：T(n)=O(1)應用實例——學生學籍信息管理問題要求實現學生信息的錄入、查找、插入和刪除等。數據結構