第二章線性表煙臺大學(xué)計算機學(xué)院孟佳娜線性結(jié)構(gòu)在數(shù)據(jù)元素的非空的有限集合中：存在唯一的一個被稱為“第一個”的數(shù)據(jù)元素；存在唯一的一個被稱為“最后一個”的數(shù)據(jù)元素；除第一個元素外，集合中每個元素都有且僅有一個前驅(qū)；除最后一個元素外，集合中每個元素都有且僅有一個后繼；線性表(LinearList)定義定義：

n個具有相同特性的數(shù)據(jù)元素組成的有限序列；表示：{a1,…,ai-1,ai,ai+1,…,an}ai-1是ai的直接前驅(qū)元素，ai+1是ai的直接后繼元素數(shù)據(jù)元素ai在線性表中有確定的位置i，i稱為位序線性表中數(shù)據(jù)元素的個數(shù)n稱為線性表的長度,n=0時，線性表稱為空表抽象數(shù)據(jù)類型定義ADTList{數(shù)據(jù)對象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai,ai-1∈D,1=2,…,n}基本操作：ListInit(L)；ListLength(L)；ListGet(L,i);ListLocate(L,x);ListLength(L);ListClear(L);ListEmpty(L)；ListPrior(L,e)；ListNext(L,e)；ListInsert(L,i,e);ListDelete(L,i);}ADTList線性表舉例1（遍歷線性表L）

ListTraverse(ListL，visit()){//遍歷線性表

if(ListEmpty(L))printf(“空表”);

else for(i=1;i<=ListLength(L);i++) visit(ListGet(L,i))；

}

線性表舉例2（合并線性表L）ListListMerge(ListLa,ListLb){//La和Lb是兩個非遞減有序的線性表，將線性表La和Lb合并成一個新的線性表Lc，Lc也非遞減。

ListInit(Lc); i=j=1;k=0; La_len=ListLength(La);Lb_len=ListLength(Lb); while((i<=La_len)&&(j<Lb_len)) {//La和Lb均非空

ai=ListGet(La,i);bj=ListGet(Lb,j);

if(ai<=bj) {ListInsert(Lc,++k,ai);++i;}

else{ListInsert(Lc,++k,bj);++j;} }

線性表舉例2（合并線性表L）while(i<=La_len) {//Lb已空，將La表的剩余部分復(fù)制到新表

ai=ListGet(La,i++); ListInsert(Lc,++k,ai); } while(j<=Lb_len) {//La已空，將Lb表的剩余部分復(fù)制到新表

bj=ListGet(Lb,j++); ListInsert(Lc,++k,bj); }

return(Lc);}//ListMerge線性表的順序表示和實現(xiàn)線性表的順序表示:線性表的順序存儲是指在內(nèi)存中用地址連續(xù)的一塊存儲空間順序存放線性表的各元素，用這種存儲形式存儲的線性表稱為順序表。

設(shè)

a１的存儲地址為Loc(a１)，每個數(shù)據(jù)元素占L個存儲單元，則第i個數(shù)據(jù)元素的地址為：

Loc(ai)=Loc(a1)+(i-1)*L1≤i≤n01i-1

i

n-1

MAXSIZE-1a1a2…ai…an…

dataai-1ai+1順序存儲結(jié)構(gòu)的線性表的類型定義如下：

typedefstruct

{ElemTypedata[MAXSIZE];//存放線性表的數(shù)組

intlength;//length是順序表的長度}SeqList;順序表上基本運算的實現(xiàn)(1)

順序表的初始化:SeqListSeqListInit(){//構(gòu)造一個空的線性表LSeqListL;//定義L為順序表

L.length=0; //順序表最后一個元素的下標(biāo)returnL;}順序表上基本運算的實現(xiàn)(2)插入運算:在第i個位置，插入元素e思想：把第i個位置開始的元素，依次后移步驟：

1.當(dāng)前表是否已經(jīng)滿？ 2.輸入是否有效？ 3.插入元素 順序表上基本運算的實現(xiàn)(2)

插入元素:voidSeqListInsert(SeqListL,inti,ElemTypex){//在順序表中的第

i個位置插入元素

xif(L.length==MAXSIZE){printf(＂表滿＂);exit(0);}//表滿，退出

if(i<1||i>L.length+1)

{printf(＂位置錯＂);exit(0);}//插入位置錯，退出

for(j=L.length-1;j>=i-1;j--) L.data[j+1]=L.data[j];//第i個位置后的數(shù)組元素逐一后移

L.data[i-1]=x;

//新元素插入到第i個位置

L.length++;

//length仍指向最后元素 }順序表上基本運算的實現(xiàn)(3)刪除運算:刪除第i個元素e思想：把第i＋1個位置開始的元素，依次前移步驟：

1.要檢查刪除位置的有效性。

2.依次元素 3.長度加1 順序表上基本運算的實現(xiàn)(3)

刪除元素:voidSeqListDelete(SeqListL,inti){//刪除順序表中的第i個元素

if(i<1||i>L.length){printf(“位置非法”)

exit(0);}//檢查空表及刪除位置的合法性

for(j=i;j<=L.length-1;j++)L.data[j-1]=L.data[j];//向上移動

L.length--;

//length仍指向最后元素}

順序表上基本運算的實現(xiàn)(4)

按值查找:intSeqListLocate(SeqListL,ElemTypex){{//在順序表L中查找第一個與x值相等的元素。若查找成功，則返回它在順序表中的下標(biāo)；否則，返回0。

i=1;while(i<=L.length&&L.data[i-1]!=x)i++;if(i<=L.length)returni;//返回數(shù)據(jù)元素的下標(biāo)

elsereturn0;//查找失敗}

順序結(jié)構(gòu)的缺點1.插入和刪除操作復(fù)雜，移動大量的數(shù)據(jù)元素，在插入操作時，還要涉及到重新分配大塊空間問題.2.在實際的系統(tǒng)中，操作系統(tǒng)可以動態(tài)分配的內(nèi)存空間總時有限的，尤其是大塊可利用的內(nèi)存.線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)線性表的鏈?zhǔn)奖硎?

以鏈?zhǔn)浇Y(jié)構(gòu)存儲的線性表稱之為線性鏈表。線性表中的數(shù)據(jù)元素可以用任意的存儲單元來存儲，邏輯相鄰的兩元素的存儲空間可以是不連續(xù)的。為表示邏輯上的順序關(guān)系，對表的每個數(shù)據(jù)元素除存儲本身的信息之外，還需存儲指示其后繼的信息。這兩部分信息組成數(shù)據(jù)元素的存儲映象，稱為結(jié)點。

可以考慮利用小的零散空間“串”起來，表示線性表，即把線性表的元素分散插入到系統(tǒng)所控制的零散空間中，然后用“指針”串起來，組成一個有序的線性表，用指針表示數(shù)據(jù)元素的有序性。這樣的小空間，可以是連續(xù)的，也可以不是連續(xù)的?？臻g至少包括：數(shù)據(jù)元素和指針兩個區(qū)域。線性表的鏈?zhǔn)奖硎綼[0]a[2]a[3]a[1]300020001000單鏈表結(jié)構(gòu)圖示ainexta1nexta2nextanNULL鏈表

結(jié)點aihead單鏈表結(jié)構(gòu)圖示單鏈表的頭指針為H：

LinkListH; 110a5200…

…150a2190160a1150…

…190a3210200a6260210a4110…

….240a8NULL…

...

260a7240H160單鏈表的C表示結(jié)點描述方法：

typedef

structLNode{ElemTypedata;

structLNode*next; }LNode,*LinkedList；帶頭結(jié)點的單鏈表通常情況下，在第一個結(jié)點前附設(shè)一個結(jié)點，成為“頭結(jié)點”LNode*p;p=（LNode*）malloc(sizeof(LNode))；則完成了申請一塊LNode類型的存儲單元的操作，并將其地址賦值給變量p。

∧H(a)a1a2an∧H

(b)…Pp->datap->next線性鏈表操作的實現(xiàn)(1)帶頭結(jié)點的單鏈表的初始化：LinkedListLinkedListInit(){//建立一個空的單鏈表

L=(LNode*)malloc(sizeof(LNode))if(L==null){printf(“沒有分配內(nèi)存空間”);exit(0);}L->next=NULL;returnL;}線性鏈表操作的實現(xiàn)(2)求表長:intLinkedListLength(LinkedListL){//求帶頭結(jié)點的單鏈表的長度p=L->next;

//p指向頭結(jié)點j=0; while(p){j++;p=p->next;} //p所指的是第

j個結(jié)點returnj;}線性鏈表操作的實現(xiàn)(3)按序號查找:LinkedListLinkedListGet(LinkedListL,inti);{//在單鏈表L中查找第i個元素結(jié)點，返回該結(jié)點，否則返回空

p=L->next; j=1; while(p!=NULL&&j<i)

{p=p->next;j++;} if(j==i)returnp; elsereturnNULL;}線性鏈表操作的實現(xiàn)(4)按值查找:LinkedListLinkedListLocate(LinkedListL,ElemTypex){//在單鏈表L中查找值為x的結(jié)點，找到后返回其指針，否則返回空p=L->next;j=0;while(p!=NULL&&p->data!=x){p=p->next;j++;}if(p->data==x)returnj;elsereturn0;}線性鏈表操作的實現(xiàn)(5)若p表示當(dāng)前結(jié)點，pre表示前一個結(jié)點。在p前插入元素ss->next=pre->next; pre->next=s;aknext插入元素：ai-1nextainextpre線性鏈表操作的實現(xiàn)(5)插入算法:voidLinkedListInsert(LinkedListL,LinkedListp,ElemTypex){//在結(jié)點p之前插入元素為x的結(jié)點

pre=L; while(pre->next!=p&&pre!=NULL) pre=pre->next;//找p的直接前驅(qū)if(!pre){printf(“不存在*p結(jié)點”)；exit(0);}s=(LNode*)malloc(sizeof(LNode));//創(chuàng)建新結(jié)點s->data=x;//設(shè)置新結(jié)點的元素值s->next=pre->next;pre->next=s;

//插入新結(jié)點}

線性鏈表操作的實現(xiàn)(6)若p表示當(dāng)前結(jié)點，pre表示前一個結(jié)點。pre->next=p->next;free(p); //p=pre->next;刪除元素:ai-1nextainextai+1next線性鏈表操作的實現(xiàn)(6)刪除元素:

voidLinkedListDel(LinkedListL，inti){//刪除單鏈表L上的第i個結(jié)點p=L;j=1; while(p->next&&j<i) {p=p->next;j++} if(p->next==NULL||j>i) {printf(“刪除位置不正確”)；exit(0);}q=p->next;p->next=q->next;//從鏈表中刪除free(q);

//釋放被刪除結(jié)點

}線性鏈表操作的實現(xiàn)(7)建立單鏈表－－頭插法:

∧L36∧L36∧45L1036∧45L231036∧45L36∧45102367L線性鏈表操作的實現(xiàn)(7)頭插法建立單鏈表算法:

LinkedListLinkedListCreat1(){//用頭插法建立帶頭結(jié)點的單鏈表

LinkedListL;L=(LNode*)malloc(sizeof(LNode));L->next=NULL;

//初始化一個空鏈表，L為頭指針

scanf(x);//x是和鏈表元素具有相同類型的變量

while(x!=flag)//flag為結(jié)束輸入的標(biāo)志{p=(LNode*)malloc(sizeof(LNode));//生成新的結(jié)點

p->data=x; //輸入元素值

p->next=L->next;L->next=p;//插入到表頭

scanf(x);//讀入下一個元素的值}

returnL;}

線性鏈表操作的實現(xiàn)(7)建立單鏈表－－尾插法:

67rL2367rL102367rL36∧45102367rL45102367rL線性鏈表操作的實現(xiàn)(7)尾插法建立單鏈表算法:

LinkedListLinkedListCreat3(){//用尾插法建立帶頭結(jié)點的單鏈表

LinkedListL;L=(LNode*)malloc(sizeof(LNode));L->next=NULL;r=L;

scanf(x);while(x!=flag)//設(shè)置結(jié)束標(biāo)志{p=(LNode*)malloc(sizeof(LNode);//生成新結(jié)點

p->data=x;//插入元素值

r->next=p;//在尾部插入新結(jié)點

r=p;//r指向新的尾結(jié)點

scanf(x);}r->next=NULL;//最后結(jié)點的指針域放空指針

returnL;}鏈?zhǔn)浇Y(jié)構(gòu)的特點非隨機存貯結(jié)構(gòu)，所以取表元素要慢于順序表。節(jié)約了大塊內(nèi)存適合于插入和刪除操作實際上用空間換取了時間，結(jié)點中加入了指針，使得這兩種操作轉(zhuǎn)換為指針操作;線性表實現(xiàn)方法的比較實現(xiàn)不同順序表方法簡單，各種高級語言中都有數(shù)組類型，容易實現(xiàn)；鏈表的操作是基于指針的，相對來講復(fù)雜些。

存儲空間的占用和分配不同從存儲的角度考慮來看，順序表的存儲空間是靜態(tài)分配的，在程序執(zhí)行之前必須明確規(guī)定它的存儲規(guī)模，也就是說事先對“MAXSIZE”要有合適的設(shè)定，過大造成浪費，過小造成溢出。而鏈表是動態(tài)分配存儲空間的，不用事先估計存儲規(guī)模?？梢妼€性表的長度或存儲規(guī)模難以估計時，采用鏈表。線性表運算的實現(xiàn)不同

按序號訪問數(shù)據(jù)元素，使用順序表優(yōu)于鏈表。插入刪除操作，使用鏈表優(yōu)于順序表。

循環(huán)鏈表單循環(huán)鏈表:

循環(huán)鏈表：鏈表尾結(jié)點的指針域指向頭結(jié)點。這樣形成的鏈表我們叫做循環(huán)鏈表。

(a)非空表a1Han…(b)空表H連接兩個單循環(huán)鏈表L1和L2操作如下：p=R1–>next; //保存L1的頭結(jié)點指針R1->next=R2->next->next; //頭尾連接free(R2->next); //釋放第二個表的頭結(jié)點

R2->next=p;

R2b1

bn…×a1

an…R1×p雙鏈表

希望查找前驅(qū)的時間復(fù)雜度達到O(1)，我們可以用空間換時間,每個結(jié)點再加一個指向前驅(qū)的指針域，使鏈表可以進行雙方向查找。用這種結(jié)點結(jié)構(gòu)組成的鏈表稱為雙向鏈表。

結(jié)點的結(jié)構(gòu)圖:priornextdata雙向鏈表的邏輯表示priordatanextLL雙向鏈表的C表示typedef

structDLNode{ElemTypedata;

structDLNode*prior,*next;}DLNode,*DLinkedList;雙向鏈表結(jié)點的類型定義如下：雙向鏈表的插入psp->prior->next=s;s->prior=p->prior;s->next=p;p->prior=s;12雙向鏈表的刪除p12p->prior->next=p->next;P->next->prior=p->prior;free(p);靜態(tài)鏈表

用數(shù)組表示線性表L=（2，3，4，6，8，9）。這次雖然我們使用的是數(shù)組，但是并不是采用順序存儲結(jié)構(gòu)，而是使用的鏈?zhǔn)酱鎯Y(jié)構(gòu)，數(shù)組SL[MAXSIZE]中存放著鏈表L，其中鏈表SL是一個帶頭結(jié)點的單鏈表。

靜態(tài)鏈表datanext0416623334142259-16857891011靜態(tài)鏈表靜態(tài)鏈表定義如下：

#defineMAXSIZE1000

typedef

struct