數(shù)據(jù)結(jié)構(gòu)課件

線性表是一種最簡(jiǎn)單的線性結(jié)構(gòu)線性表

線性結(jié)構(gòu)的基本特徵:1．集合中必存在唯一的一個(gè)“第一元素”；2．集合中必存在唯一的一個(gè)“最後元素”；3．除最後元素在外，均有唯一的後繼；4．除第一元素之外，均有唯一的前驅(qū)。線性結(jié)構(gòu)

是一個(gè)數(shù)據(jù)元素的有序（次序）集2.1線性表的類(lèi)型定義2.2線性表的順序表示和實(shí)現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

2.3.1線性鏈表

2.3.2迴圈鏈表

2.3.3雙向鏈表2.4一元多項(xiàng)式的表示及相加2.1線性表的類(lèi)型定義抽象數(shù)據(jù)類(lèi)型線性表的定義如下：ADTList{

數(shù)據(jù)對(duì)象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}{稱n

為線性表的表長(zhǎng);

稱n=0

時(shí)的線性表為空表。}數(shù)據(jù)關(guān)係：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}{設(shè)線性表為(a1，a2,...，ai，...，an),

稱i為ai線上性表中的位序。}

基本操作：

結(jié)構(gòu)初始化操作結(jié)構(gòu)銷(xiāo)毀操作

引用型操作

加工型操作

}ADTList

InitList(&L)操作結(jié)果：構(gòu)造一個(gè)空的線性表L。初始化操作

結(jié)構(gòu)銷(xiāo)毀操作DestroyList(&L)初始條件：操作結(jié)果：線性表L已存在。銷(xiāo)毀線性表L。ListEmpty(L)ListLength(L)PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)

GetElem(L,i,&e)LocateElem(L,e,compare())ListTraverse(L,visit())引用型操作:

ListTraverse(L,visit())初始條件：操作結(jié)果：線性表L已存在。Visit()為某個(gè)訪問(wèn)函數(shù)。依次對(duì)L中每個(gè)元素調(diào)用函數(shù)標(biāo)visit()。一旦visit()失敗，則操作失敗。（遍曆線性表）加工型操作

ClearList(&L)PutElem(&L,i,e)ListInsert(&L,i,e)ListDelete(&L,i,&e)

利用上述定義的線性表類(lèi)型可以實(shí)現(xiàn)其他更複雜的操作。

假設(shè):有兩個(gè)集合A和B分別用兩個(gè)線性表LA和LB表示，即：線性表中的數(shù)據(jù)元素即為集合中的成員。

現(xiàn)要求一個(gè)新的集合A＝A∪B。例2-1

要求對(duì)線性表作如下操作：擴(kuò)大線性表LA，將存在於線性表LB中而不存在於線性表

LA中的數(shù)據(jù)元素插入到線性表LA

中去。上述問(wèn)題可演繹為：1．從線性表LB中依次察看每個(gè)數(shù)據(jù)元素;2．依值線上性表LA中進(jìn)行查訪;3．若不存在，則插入之。GetElem(LB,i)→e

LocateElem(LA,e,equal())

ListInsert(LA,n+1,e)(n表示線性表LA當(dāng)前長(zhǎng)度)操作步驟：

GetElem(Lb,i,e);//取Lb中第i個(gè)數(shù)據(jù)元素賦給e

if(!LocateElem(La,e,equal()))

ListInsert(La,++La_len,e);

//La中不存在和e相同的數(shù)據(jù)元素，則插入之La_len=ListLength(La);//求線性表的長(zhǎng)度

Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){}//for}//unionvoidunion(List&La,ListLb){若線性表中的數(shù)據(jù)元素相互之間可以比較，並且數(shù)據(jù)元素在表中依值非遞減或非遞增有序排列，即ai≥ai-1

或ai≤ai-1(i=2,3,…,n)，則稱該為有序表(OrderedList)。有序表則

歸併兩個(gè)“其數(shù)據(jù)元素按值非遞減有序排列”的有序表LA和LB，求得有序表LC也具有同樣特性。設(shè)

La=(a1,…,ai,…,an),Lb=(b1,…,bj,…,bm)

Lc=(c1,…,ck,…,cm+n)且已由(a1,…,ai-1)和(b1,…,bj-1)歸併得

(c1,…,ck-1)例

2-2k=1,2,…,m+n1．初始化LC為空表；基本操作：2．分別從LA和LB中取得當(dāng)前元素ai

和bj；3．若ai≤bj，則將ai

插入到LC中，否則將

bj

插入到LC中；4．重複2和3兩步，直至LA或LB中元素被取完為止；5．將LA表或LB表中剩餘元素複製插入到

LC表中。

//La和Lb均非空，i=j=1,k=0GetElem(La,i,ai);GetElem(Lb,j,bj);

if(ai<=bj){//將ai插入到Lc中

ListInsert(Lc,++k,ai);++i;}else{//將bj插入到Lc中

ListInsert(Lc,++k,bj);++j;}voidMergeList(ListLa,ListLb,List&Lc){

//本演算法將非遞減的有序表La和Lb歸併為L(zhǎng)c}//merge_listwhile((i<=La_len)&&(j<=Lb_len))

{//La和Lb均不空}while(i<=La_len)

//若La不空while(j<=Lb_len)//若Lb不空InitList(Lc);//構(gòu)造空的線性表Lci=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);

while(i<=La_len){//當(dāng)La不空時(shí)

GetElem(La,i++,ai);ListInsert(Lc,++k,ai);

}

//插入La表中剩餘元素

while(j<=Lb_len){//當(dāng)Lb不空時(shí)

GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);

}

//插入Lb表中剩餘元素2.2線性表類(lèi)型的實(shí)現(xiàn)----順序映象最簡(jiǎn)單的一種順序映象方法是：令y的存儲(chǔ)位置和x的存儲(chǔ)位置相鄰。順序映象——

以x的存儲(chǔ)位置和y的存儲(chǔ)位置之間某種關(guān)係表示邏輯關(guān)係<x,y>

用一組地址連續(xù)的存儲(chǔ)單元

依次存放線性表中的數(shù)據(jù)元素

a1a2

…ai-1ai

…an線性表的起始地址，稱作線性表的基地址以“存儲(chǔ)位置相鄰”表示有序?qū)?lt;ai-1，ai>

即：LOC(ai)=LOC(ai-1)+C

一個(gè)數(shù)據(jù)元素所占存儲(chǔ)量↑所有數(shù)據(jù)元素的存儲(chǔ)位置均取決於第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置

LOC(ai)=

LOC(a1)+(i-1)×C

↑基地址順序映像的C語(yǔ)言描述線性表的靜態(tài)分配順序存儲(chǔ)結(jié)構(gòu)：#defineLISTSIZE100//存儲(chǔ)空間的最大分配量typedefstruct{ElemTypeelem[LISTSIZE];intlength;//當(dāng)前長(zhǎng)度

}Sqlist;

線上性表的靜態(tài)分配順序存儲(chǔ)結(jié)構(gòu)中，線性表的最多數(shù)據(jù)元素個(gè)數(shù)為L(zhǎng)ISTSIZE，元素?cái)?shù)量不能隨意增加，這是以數(shù)組方式描述線性表的缺點(diǎn)。為了實(shí)現(xiàn)線性表最大存儲(chǔ)數(shù)據(jù)元素?cái)?shù)可隨意變化，可以使用一個(gè)動(dòng)態(tài)分配的數(shù)組來(lái)取代上面的固定長(zhǎng)度數(shù)組，如下描述。線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)：#defineLIST_INIT_SIZE100//初始分配量#defineLISTINCREMENT10//分配增量typedefstruct{

}SqList;//俗稱順序表ElemType*elem;//存儲(chǔ)空間基址int

length;//當(dāng)前長(zhǎng)度int

listsize;//當(dāng)前分配的存儲(chǔ)容量

//(以sizeof(ElemType)為單位)線性表的基本操作在順序表中的實(shí)現(xiàn)InitList(&L)//結(jié)構(gòu)初始化LocateElem(L,e,compare())//查找ListInsert(&L,i,e)//插入元素ListDelete(&L,i)//刪除元素線性表操作

ListInsert(&L,i,e)的實(shí)現(xiàn)：首先分析:插入元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什麼變化？

(a1,…,ai-1,ai,…,an)改變?yōu)閍1a2

…ai-1ai

…ana1a2

…ai-1

…aiean<ai-1,ai><ai-1,e>,<e,ai>表的長(zhǎng)度增加(a1,…,ai-1,e,ai,…,an)

StatusListInsert_Sq(SqList&L,inti,ElemTypee){

//

在順序表L的第i個(gè)元素之前插入新的元素e,

//i的合法範(fàn)圍為1≤i≤L.length+1}//ListInsert_Sq

演算法時(shí)間複雜度為:O(ListLength(L))q=&(L.elem[i-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;//插入位置及之後的元素右移*q=e;//插入e++L.length;//表長(zhǎng)增1returnOK;……元素右移if(L.length>=L.listsize)returnOVERFLOW;//當(dāng)前存儲(chǔ)空間已滿

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

returnERROR;

//

插入位置不合法考慮移動(dòng)元素的平均情況:

假設(shè)在第

i個(gè)元素之前插入的概率為，

則在長(zhǎng)度為n的線性表中插入一個(gè)元素所需移動(dòng)元素次數(shù)的期望值為：

若假定線上性表中任何一個(gè)位置上進(jìn)行插入的概率都是相等的，則移動(dòng)元素的期望值為：2118307542568721183075例如：ListInsert_Sq(L,5,66)

L.length-10pppq87564266q=&(L.elem[i-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;p線性表操作

ListDelete(&L,i,&e)的實(shí)現(xiàn)：首先分析：刪除元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什麼變化？

(a1,…,ai-1,ai,ai+1,…,an)改變?yōu)閍i+1…an<ai-1,ai>,<ai,ai+1><ai-1,ai+1>表的長(zhǎng)度減少a1a2

…ai-1ai

ai+1

…ana1a2

…ai-1

(a1,…,ai-1,ai+1,…,an)StatusListDelete_Sq(SqList&L,inti,ElemType&e){}//ListDelete_Sqfor(++p;p<=q;++p)*(p-1)=*p;

//

被刪除元素之後的元素左移--L.length;//表長(zhǎng)減1returnOK;演算法時(shí)間複雜度為:

O(ListLength(L))p=&(L.elem[i-1]);//p為被刪除元素的位置e=*p;//被刪除元素的值賦給eq=L.elem+L.length-1;//表尾元素的位置if((i<1)||(i>L.length))returnERROR;

//刪除位置不合法元素左移考慮移動(dòng)元素的平均情況:

假設(shè)刪除第

i個(gè)元素的概率為

,則在長(zhǎng)度為n的線性表中刪除一個(gè)元素所需移動(dòng)元素次數(shù)的期望值為：若假定線上性表中任何一個(gè)位置上進(jìn)行刪除的概率都是相等的，則移動(dòng)元素的期望值為：2118307542568721183075L.length-10pppq8756p=&(L.elem[i-1]);q=L.elem+L.length-1;for(++p;p<=q;++p)*(p-1)=*p;例如：ListDelete_Sq(L,5,e)

p2.3線性表類(lèi)型的實(shí)現(xiàn)----鏈?zhǔn)接诚笠?、單鏈表二、結(jié)點(diǎn)和單鏈表的C語(yǔ)言描述三、線性表的操作在單鏈表中的實(shí)現(xiàn)四、其他形式的鏈表

用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。一、單鏈表以元素(數(shù)據(jù)元素的映象)

+指針(指示後繼元素存儲(chǔ)位置)=結(jié)點(diǎn)

(表示數(shù)據(jù)元素或數(shù)據(jù)元素的映象)以“結(jié)點(diǎn)的序列”表示線性表

稱作鏈表

以線性表中第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址作為線性表的地址，稱作線性表的頭指針頭結(jié)點(diǎn)

a1a2…...an^頭指針頭指針

有時(shí)為了操作方便，在第一個(gè)結(jié)點(diǎn)之前虛加一個(gè)“頭結(jié)點(diǎn)”，以指向頭結(jié)點(diǎn)的指針為鏈表的頭指針空指針線性表為空表時(shí)，頭結(jié)點(diǎn)的指針域?yàn)榭?/p>

typedefstructLNode{ElemTypedata;//數(shù)據(jù)域

structLnode*next;//指針域

}LNode,*LinkList;

二、結(jié)點(diǎn)和單鏈表的C語(yǔ)言描述LinkListL；//L為單鏈表的頭指針三、單鏈表操作的實(shí)現(xiàn)GetElem(L,i,e)//取第i個(gè)數(shù)據(jù)元素ListInsert(&L,i,e)//插入數(shù)據(jù)元素ListDelete(&L,i,e)//刪除數(shù)據(jù)元素ClearList(&L)//重置線性表為空表CreateList(&L,n)

//生成含n個(gè)數(shù)據(jù)元素的鏈表L

線性表的操作

GetElem(L,i,&e)在單鏈表中的實(shí)現(xiàn):211830754256∧pppj123

因此，查找第i個(gè)數(shù)據(jù)元素的基本操作為：移動(dòng)指針，比較j和i

單鏈表是一種順序存取的結(jié)構(gòu)，為找第i個(gè)數(shù)據(jù)元素，必須先找到第i-1個(gè)數(shù)據(jù)元素。

令指針p

始終指向線性表中第j

個(gè)數(shù)據(jù)元素

StatusGetElem_L(LinkListL,inti,ElemType&e){//L是帶頭結(jié)點(diǎn)的鏈表的頭指針，以e返回第i個(gè)元素}//GetElem_L演算法時(shí)間複雜度為:O(ListLength(L))p=L->next;j=1;//p指向第一個(gè)結(jié)點(diǎn)，j為計(jì)數(shù)器while(p&&j<i){p=p->next;++j;}//

順指針向後查找，直到p指向第i個(gè)元素

//

或p為空if(!p||j>i)

returnERROR;//第i個(gè)元素不存在e=p->data;//取得第i個(gè)元素returnOK;ai-1

線性表的操作

ListInsert(&L,i,e)

在單鏈表中的實(shí)現(xiàn)：

有序?qū)?lt;ai-1,ai>

改變?yōu)?lt;ai-1,e>和<e,ai>eaiai-1

因此，在單鏈表中第i個(gè)結(jié)點(diǎn)之前進(jìn)行插入的基本操作為:

找到線性表中第i-1個(gè)結(jié)點(diǎn)，然後修改其指向後繼的指針。

可見(jiàn)，在鏈表中插入結(jié)點(diǎn)只需要修改指針。但同時(shí)，若要在第i個(gè)結(jié)點(diǎn)之前插入元素，修改的是第i-1個(gè)結(jié)點(diǎn)的指針。StatusListInsert_L(LinkList&L,inti,ElemTypee){

//L為帶頭結(jié)點(diǎn)的單鏈表的頭指針，本演算法

//在鏈表中第i個(gè)結(jié)點(diǎn)之前插入新的元素e

}//LinstInsert_L演算法的時(shí)間複雜度為:O(ListLength(L))……p=L;j=0;while(p&&j<i-1)

{p=p->next;++j;}

//

尋找第i-1個(gè)結(jié)點(diǎn)if(!p||j>i-1)

returnERROR;//

i大於表長(zhǎng)或者小於1s=newLNode;

//生成新結(jié)點(diǎn)if(s==NULL)returnERROR;s->data=e;s->next=p->next;p->next=s;//插入returnOK;eai-1aiai-1sp線性表的操作ListDelete(&L,i,&e)在鏈表中的實(shí)現(xiàn):有序?qū)?lt;ai-1,ai>和<ai,ai+1>

改變?yōu)?lt;ai-1,ai+1>ai-1aiai+1ai-1

在單鏈表中刪除第

i個(gè)結(jié)點(diǎn)的基本操作為:找到線性表中第i-1個(gè)結(jié)點(diǎn)，修改其指向後繼的指針。ai-1aiai+1ai-1q=p->next;p->next=q->next;

e=q->data;delete(q);pqStatusListDelete_L(LinkList&L,inti,ElemType&e){

//刪除以L為頭指針(帶頭結(jié)點(diǎn))的單鏈表中第i個(gè)結(jié)點(diǎn)

}//ListDelete_L演算法的時(shí)間複雜度為:O(ListLength(L))p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}

//尋找第i個(gè)結(jié)點(diǎn)，並令p指向其前趨q=p->next;p->next=q->next;

//刪除並釋放結(jié)點(diǎn)e=q->data;delete(q);returnOK;if(!(p->next)||j>i-1)

returnERROR;//刪除位置不合理操作ClearList(&L)在鏈表中的實(shí)現(xiàn):voidClearList(&L){//將單鏈表重新置為一個(gè)空表

while(L->next){

p=L->next;L->next=p->next;

}}//ClearListdelete(p);演算法時(shí)間複雜度：O(ListLength(L))如何從線性表得到單鏈表？鏈表是一個(gè)動(dòng)態(tài)的結(jié)構(gòu)，它不需要予分配空間，因此生成鏈表的過(guò)程是一個(gè)結(jié)點(diǎn)“逐個(gè)插入”的過(guò)程。例如：逆位序輸入n個(gè)數(shù)據(jù)元素的值，建立帶頭結(jié)點(diǎn)的單鏈表。操作步驟(頭插法)：一、建立一個(gè)“空表”；二、輸入數(shù)據(jù)元素an，建立結(jié)點(diǎn)並插入；三、輸入數(shù)據(jù)元素an-1，建立結(jié)點(diǎn)並插入；ananan-1四、依次類(lèi)推，直至輸入a1為止。voidCreateList_L(LinkList&L,intn){//逆序輸入n個(gè)數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)的單鏈表}//CreateList_L演算法的時(shí)間複雜度為:O(Listlength(L))L=newLNode;L->next=NULL;

//先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表for(i=n;i>0;--i){p=newLNode;

scanf(&p->data);//輸入元素值

p->next=L->next;L->next=p;//插入}尾插法建表

頭插法建立鏈表雖然演算法簡(jiǎn)單，但生成的鏈表中結(jié)點(diǎn)的次序和輸入的順序相反。若希望二者次序一致，可採(cǎi)用尾插法建表。該方法是將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上，為此必須增加一個(gè)尾指針r，使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)。

linklistcreater(){charch;linklisthead;lnode*p，*r;//(，*head;)head=NULL;r=NULL;while((ch=getchar()!=‵\n′){p=(lnode*)malloc(sizeof(lnode));p–>data=ch;if(head=NULL)head=p;elser–>next=p;r=p;}if(r!=NULL)r–>next=NULL;return(head);}說(shuō)明：第一個(gè)生成的結(jié)點(diǎn)是開(kāi)始結(jié)點(diǎn)，將開(kāi)始結(jié)點(diǎn)插入到空表中，是在當(dāng)前鏈表的第一個(gè)位置上插入，該位置上的插入操作和鏈表中其他位置上的插入操作處理是不一樣的，原因是開(kāi)始結(jié)點(diǎn)的位置是存放在頭指針（指針變數(shù)）中，而其餘結(jié)點(diǎn)的位置是在其前趨結(jié)點(diǎn)的指針域中。演算法中的第一個(gè)if語(yǔ)句就是用來(lái)對(duì)第一個(gè)位置上的插入操作做特殊處理。演算法中的第二個(gè)if語(yǔ)句的作用是為了分別處理空表和非空表兩種不同的情況，若讀入的第一個(gè)字元就是結(jié)束標(biāo)誌符，則鏈表head是空表，尾指針r亦為空，結(jié)點(diǎn)*r不存在；否則鏈表head非空，最後一個(gè)尾結(jié)點(diǎn)*r是終端結(jié)點(diǎn)，應(yīng)將其指針域置空。

如果我們?cè)阪湵淼拈_(kāi)始結(jié)點(diǎn)之前附加一個(gè)結(jié)點(diǎn)，並稱它為頭結(jié)點(diǎn)，那麼會(huì)帶來(lái)以下兩個(gè)優(yōu)點(diǎn)：a、由於開(kāi)始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中，所以在鏈表的第一個(gè)位置上的操作就和在表的其他位置上的操作一致，無(wú)需進(jìn)行特殊處理；b、無(wú)論鏈表是否為空，其頭指針是指向頭結(jié)點(diǎn)在的非空指針（空表中頭結(jié)點(diǎn)的指針域?yàn)榭眨虼丝毡砗头强毡淼奶幚硪簿徒y(tǒng)一了。其演算法如下：linklistcreatelistr1(){charch;linklisthead=(linklist)malloc(sizeof(listnode));listnode*p，*r;r=head;while((ch=getchar())!=‵\n′){p=(listnode*)malloc(sizeof(listnode));p–>data=ch;r–>next=p;r=p;}r–>next=NULL;return(head);}

上述演算法裏動(dòng)態(tài)申請(qǐng)新結(jié)點(diǎn)空間時(shí)未加錯(cuò)誤處理，可作下列處理：

p=(listnode*)malloc(sizeof(listnode));if(p==NULL)error(〝Nospacefornodecanbeobtained〞);returnERROR;

以上演算法的時(shí)間複雜度均為O(n)。

最後一個(gè)結(jié)點(diǎn)的指針域的指針又指回第一個(gè)結(jié)點(diǎn)的鏈表a1a2…...an1.迴圈鏈表

和單鏈表的差別僅在於，判別鏈表中最後一個(gè)結(jié)點(diǎn)的條件不再是“後繼是否為空”，而是“後繼是否為頭結(jié)點(diǎn)”。四、其他形式的鏈表

在很多實(shí)際問(wèn)題中，表的操作常常是在表的首尾位置上進(jìn)行，此時(shí)頭指針表示的單迴圈鏈表就顯得不夠方便.如果改用尾指針rear來(lái)表示單迴圈鏈表，則查找開(kāi)始結(jié)點(diǎn)a1和終端結(jié)點(diǎn)an都很方便，它們的存儲(chǔ)位置分別是(rear–>next)—>next和rear，顯然，查找時(shí)間都是O(1)。因此，實(shí)際中多採(cǎi)用尾指針表示單迴圈鏈表。由於迴圈鏈表中沒(méi)有NULL指針，故涉及遍曆操作時(shí)，其終止條件就不再像非迴圈鏈表那樣判斷p或p—>next是否為空，而是判斷它們是否等於某一指定指針，如頭指針或尾指針等。例、在設(shè)尾指針的單迴圈鏈表上實(shí)現(xiàn)將兩個(gè)線性表(a1，a2，a3，…an)和(b1，b2，b3，…bn)鏈接成一個(gè)線性表的運(yùn)算。

linklistconnect(linklistA，linklistB){linklistp=A—>next;A—>next=(B—>next)—>next;free(B—>next);B—>next=p;A=B;return(A);}2.雙向鏈表typedefstructDuLNode{ElemTypedata;

//數(shù)據(jù)域

structDuLNode*prior;

//指向前驅(qū)的指針域

structDuLNode*next;

//

指向後繼的指針域}

DuLNode,*DuLinkList;雙向迴圈鏈表空表非空表a1a2…...an雙向鏈表的操作特點(diǎn)：“查詢”和單鏈表相同“插入”和“刪除”時(shí)需要同時(shí)修改兩個(gè)方向上的指針。ai-1aies->next=p->next;p->next=s;s->next->prior=s;s->prior=p;psai-1ai插入ai-1刪除aiai+1p->next=p->next->next;p->next->prior=p;pai-12.4一元多項(xiàng)式的表示在電腦中，可以用一個(gè)線性表來(lái)表示:P=(p0,p1,…，pn)一元多項(xiàng)式但是對(duì)於形如S(x)=1+3x10000–2x20000的多項(xiàng)式，上述表示方法是否合適？

一般情況下的一元稀疏多項(xiàng)式可寫(xiě)成

Pn(x)=p1xe1+p2xe2+┄+pmxem其中：pi

是指數(shù)為ei

的項(xiàng)的非零係數(shù)，

0≤e1<e2<┄<em=n可以下列線性表表示：（（p1,e1）,(p2,e2),┄,(pm,em)）

P999(x)=7x3-2x12-8x999例如:可用線性表

((7,3),(-2,12),(-8,999))表示ADTPolynomial{

數(shù)據(jù)對(duì)象：

數(shù)據(jù)關(guān)係：抽象數(shù)據(jù)類(lèi)型一元多項(xiàng)式的定義如下：D＝{ai|ai∈TermSet,i=1,2,...,m,m≥0TermSet中的每個(gè)元素包含一個(gè)表示係數(shù)的實(shí)數(shù)和表示指數(shù)的整數(shù)

}R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n

且ai-1中的指數(shù)值＜ai中的指數(shù)值

}

CreatPolyn(&P,m)

DestroyPolyn(&P)

PrintPolyn(&P)

基本操作：操作結(jié)果：輸入

m項(xiàng)的係數(shù)和指數(shù)，建立一元多項(xiàng)式

P。初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：銷(xiāo)毀一元多項(xiàng)式P。初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：列印輸出一元多項(xiàng)式P。

PolynLength(P)

AddPolyn(&Pa,&Pb)SubtractPolyn(&Pa,&Pb)……}ADTPolynomial初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：返回一元多項(xiàng)式P中的項(xiàng)數(shù)。初始條件：一元多項(xiàng)式Pa和Pb已存在。操作結(jié)果：完成多項(xiàng)式相加運(yùn)算，即：

Pa=Pa＋Pb，並銷(xiāo)毀一元多項(xiàng)式Pb。小結(jié)：順序表和鏈表的比較

在本章介紹了線性表的邏輯結(jié)構(gòu)及它的兩種存儲(chǔ)結(jié)構(gòu)：順序表和鏈表。通過(guò)對(duì)它們的討論可知它們各有優(yōu)缺點(diǎn)，順序存儲(chǔ)有三個(gè)優(yōu)點(diǎn)：(1)方法簡(jiǎn)單，各種高級(jí)語(yǔ)言中都有數(shù)組，容易實(shí)現(xiàn)。(2)不用為表示結(jié)點(diǎn)間的邏輯關(guān)係而增加額外的存儲(chǔ)開(kāi)銷(xiāo)。(3)順序表具有按元素序號(hào)隨機(jī)訪問(wèn)的特點(diǎn)。但它也有兩個(gè)缺點(diǎn)：(1)

在順序表中做插入刪除操作時(shí)，平均移動(dòng)大約表中一半的元素，因此對(duì)n較大的順序表效率低。(2)

需要預(yù)先分配足夠大的存儲(chǔ)空間，估計(jì)過(guò)大，可能會(huì)導(dǎo)致順序表後部大量閒置；預(yù)先分配過(guò)小，又會(huì)造成溢出。鏈表的優(yōu)缺點(diǎn)恰好與順序表相反。在實(shí)際中怎樣選取存儲(chǔ)結(jié)構(gòu)呢？通常有以下幾點(diǎn)考慮：１．基於存儲(chǔ)的考慮順序表的存儲(chǔ)空間是靜態(tài)分配的，在程式執(zhí)行之前必須明確規(guī)定它的存儲(chǔ)規(guī)模，也就是說(shuō)事先對(duì)＂MAXSIZE＂要有合適的設(shè)定，過(guò)大造成浪費(fèi)，過(guò)小造成溢出。可見(jiàn)對(duì)線性表的長(zhǎng)度或存儲(chǔ)規(guī)模難以估計(jì)時(shí)，不宜採(cǎi)用順序表；鏈表不用事先估計(jì)存儲(chǔ)規(guī)模，但鏈表的存儲(chǔ)密度較低，存儲(chǔ)密度是指一個(gè)結(jié)點(diǎn)中數(shù)據(jù)元素所占的存儲(chǔ)單元和整個(gè)結(jié)點(diǎn)所占的存儲(chǔ)單元之比。顯然鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的存儲(chǔ)密度是小於１的。２．基於運(yùn)算的考慮在順序表中按序號(hào)訪問(wèn)ai的時(shí)間性能時(shí)O(1)，而鏈表中按序號(hào)訪問(wèn)的時(shí)間性能O(n)，所以如果經(jīng)常做的運(yùn)算是按序號(hào)訪問(wèn)數(shù)據(jù)元素，顯然順序表優(yōu)於鏈表；而在順序表中做插入、刪除時(shí)平均移動(dòng)表中一半的元素，當(dāng)數(shù)據(jù)元素的資訊量較大且表較長(zhǎng)時(shí)，這一點(diǎn)是不應(yīng)忽視的；在鏈表中作插入、刪除，雖然也要找插入位置，但操作主要是比較操作，從這個(gè)角度考慮顯然後者優(yōu)於前者。３．基於環(huán)境的考慮順序表容易實(shí)現(xiàn)，任何高級(jí)語(yǔ)言中都有數(shù)組類(lèi)型，鏈表的操作是基於指針的，相對(duì)來(lái)講前者簡(jiǎn)單些，也是用戶考慮的一個(gè)因素?？傊?，兩種存儲(chǔ)結(jié)構(gòu)各有長(zhǎng)短，選擇那一種由實(shí)際問(wèn)題中的主要因素決定。通?！拜^穩(wěn)定”的線性表選擇順序存儲(chǔ)，而頻繁做插入刪除的即動(dòng)態(tài)性較強(qiáng)的線性表宜選擇鏈?zhǔn)酱鎯?chǔ)。本章小結(jié)1.瞭解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)係，在電腦中表示這種關(guān)係的兩類(lèi)不同的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用前者表示的線性表簡(jiǎn)稱為順序表，用後者表示的線性表簡(jiǎn)稱為鏈表。2.熟練掌握這兩類(lèi)存儲(chǔ)結(jié)構(gòu)的描述方法，以及線性表的各種基本操作的實(shí)現(xiàn)。3.能夠從時(shí)間和空間複雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。順序表應(yīng)用1將順序表

(a1，a2，...，an)重新排列為以

a1為界的兩部分：a1前面的值均比

a1小，a1後面的值都比

a1大(這裏假設(shè)數(shù)據(jù)元素的類(lèi)型具有可比性,不妨設(shè)為整型)，這一操作稱為劃分。

2有順序表A和B，其元素均按從小到大的昇冪排列，編寫(xiě)一個(gè)演算法將它們合併成一個(gè)順序表C，要求C的元素也是從小到大的昇冪排列。通常稱，棧和佇列是限定插入和刪除只能在表的“端點(diǎn)”進(jìn)行的線性表。

線性表?xiàng)辛蠭nsert(L,

i,x)Insert(S,n+1,x)Insert(Q,n+1,x)

1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)

1≤i≤n棧和佇列是兩種常用的數(shù)據(jù)類(lèi)型3.1棧的類(lèi)型定義3.2棧的應(yīng)用舉例3.3棧類(lèi)型的實(shí)現(xiàn)3.4佇列的類(lèi)型定義3.5佇列類(lèi)型的實(shí)現(xiàn)3.1

棧的類(lèi)型定義ADTStack

{

數(shù)據(jù)對(duì)象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

數(shù)據(jù)關(guān)係：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

約定an

端為棧頂，a1端為棧底?；静僮鳎?/p>

}ADTStackInitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(S)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())

InitStack(&S)

操作結(jié)果：構(gòu)造一個(gè)空棧S。

DestroyStack(&S)

初始條件：棧S已存在。

操作結(jié)果：棧S被銷(xiāo)毀。

StackEmpty(S)

初始條件：棧S已存在。

操作結(jié)果：若棧S為空棧，則返回TRUE，否則FALE。

StackLength(S)

初始條件：棧S已存在。

操作結(jié)果：返回S的元素個(gè)數(shù)，即棧的長(zhǎng)度。

GetTop(S,&e)

初始條件：棧S已存在且非空。操作結(jié)果：用e返回S的棧頂元素。a1a2an……

ClearStack(&S)

初始條件：棧S已存在。

操作結(jié)果：將S清為空棧。Push(&S,e)

初始條件：棧S已存在。

操作結(jié)果：插入元素e為新的棧頂元素。a1a2ane……Pop(&S,&e)

初始條件：棧S已存在且非空。

操作結(jié)果：刪除S的棧頂元素，並用e返回其值。a1a2anan-1

……3.2

棧的應(yīng)用舉例例一、數(shù)制轉(zhuǎn)換例二、括弧匹配的檢驗(yàn)例三、行編輯程式問(wèn)題例四、迷宮求解例五、運(yùn)算式求值例六、實(shí)現(xiàn)遞歸

例一、數(shù)制轉(zhuǎn)換

算法基于原理：

N=(Ndivd)×d+Nmodd

例如：（1348)10=(2504)8

，其運(yùn)算過(guò)程如下：

NNdiv8Nmod8

13481684

168210

2125

202計(jì)算順序輸出順序voidconversion(){InitStack(S);

scanf("%d",N);

while(N){

Push(S,N%8);N=N/8;

}

while(!StackEmpty(S)){

Pop(S,e);

printf("%d",e);

}}//conversion例二、括弧匹配的檢驗(yàn)假設(shè)在運(yùn)算式中（［］（））或［（［］［］）］等為正確的格式，［（］）或（［（））或(()])均為不正確的格式。則檢驗(yàn)括弧是否匹配的方法可用“期待的急迫程度”這個(gè)概念來(lái)描述。分析可能出現(xiàn)的不匹配的情況:到來(lái)的右括弧非是所“期待”的;例如：考慮下列括弧序列：

[([][])]12345678到來(lái)的是“不速之客”;直到結(jié)束，也沒(méi)有到來(lái)所“期待”的括弧;演算法的設(shè)計(jì)思想：1）凡出現(xiàn)左括弧，則進(jìn)棧；2）凡出現(xiàn)右括弧，首先檢查棧是否空若棧空，則表明該“右括弧”多餘否則和棧頂元素比較，若相匹配，則“左括弧出?！狈駝t表明不匹配3）運(yùn)算式檢驗(yàn)結(jié)束時(shí)，若?？?，則表明運(yùn)算式中匹配正確否則表明“左括弧”有餘Statusmatching(string&exp){

intstate=1;

while(i<=Length(exp)&&state){

switchofexp[i]{

case

左括弧:{Push(S,exp[i]);i++;break;}

case”)”:{

if(NOTStackEmpty(S)&&GetTop(S)=“(“{Pop(S,e);i++;}

else{state=0;}

break;}……}

if(StackEmpty(S)&&state)returnOK;…...例三、行編輯程式問(wèn)題如何實(shí)現(xiàn)？“每接受一個(gè)字元即存入記憶體”?

並不恰當(dāng)！

設(shè)立一個(gè)輸入緩衝區(qū)，用以接受用戶輸入的一行字元，然後逐行存入用戶數(shù)據(jù)區(qū);並假設(shè)“#”為後退字元，“@”為退行符。

在用戶輸入一行的過(guò)程中，允許用戶輸入出差錯(cuò)，並在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正。合理的作法是：假設(shè)從終端接受了這樣兩行字元：

whli##ilr#e（s#*s)

outcha@putchar(*s=#++);則實(shí)際有效的是下列兩行：

while(*s)

putchar(*s++);

while(ch!=EOF&&ch!='\n'){

switch(ch){

case'#':Pop(S,c);break;

case'@':ClearStack(S);break;//重置S為空棧

default

:Push(S,ch);break;

}ch=getchar();//從終端接收下一個(gè)字元

}ClearStack(S);//重置S為空棧if(ch!=EOF)ch=getchar();while(ch!=EOF){//EOF為全文結(jié)束符將從棧底到棧頂?shù)淖衷獋魉椭琳{(diào)用過(guò)程的數(shù)據(jù)區(qū)；例四、迷宮求解通常用的是“窮舉求解”的方法

11

112

222

232

133

134

424

125

126

416

315

314

43$$$$$$$$求迷宮路徑演算法的基本思想是：若當(dāng)前位置“可通”，則納入路徑，繼續(xù)前進(jìn);若當(dāng)前位置“不可通”，則後退，換方向繼續(xù)探索;若四周“均無(wú)通路”，則將當(dāng)前位置從路徑中刪除出去。設(shè)定當(dāng)前位置的初值為入口位置；

do｛

若當(dāng)前位置可通，

則｛將當(dāng)前位置插入棧頂；

若該位置是出口位置，則演算法結(jié)束；否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；

｝

否則{

｝｝while(棧不空）；求迷宮中一條從入口到出口的路徑的演算法：

…

…若棧不空且棧頂位置尚有其他方向未被探索，則設(shè)定新的當(dāng)前位置為:沿順時(shí)針?lè)较蛐D(zhuǎn)找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，則｛刪去棧頂位置；//從路徑中刪去該通道塊

若棧不空，則重新測(cè)試新的棧頂位置，

直至找到一個(gè)可通的相鄰塊或出棧至?？眨唬魲？眨瑒t表明迷宮沒(méi)有通路。

限於二元運(yùn)算符的運(yùn)算式定義:

運(yùn)算式::=(運(yùn)算元)+(運(yùn)算符)+(運(yùn)算元)

運(yùn)算元::=簡(jiǎn)單變數(shù)|運(yùn)算式簡(jiǎn)單變數(shù)::=識(shí)別字|無(wú)符號(hào)整數(shù)例五、運(yùn)算式求值

運(yùn)算式的三種標(biāo)識(shí)方法：設(shè)

Exp=S1+

OP

+S2則稱

OP

+S1+S2

為首碼表示法

S1+

OP

+S2

為中綴表示法

S1+S2+

OP

為尾碼表示法

例如:Exp=a

b

+

(c

d/e)

f首碼式:+

ab

c/def中綴式:a

b

+

c

d/e

f尾碼式:ab

cde/

f

+結(jié)論:1）運(yùn)算元之間的相對(duì)次序不變;2）運(yùn)算符的相對(duì)次序不同;3）中綴式丟失了括弧資訊，致使運(yùn)算的次序不確定;4)首碼式的運(yùn)算規(guī)則為:連續(xù)出現(xiàn)的兩個(gè)運(yùn)算元和在它們之前且緊靠它們的運(yùn)算符構(gòu)成一個(gè)最小運(yùn)算式;5)尾碼式的運(yùn)算規(guī)則為:

運(yùn)算符在式中出現(xiàn)的順序恰為運(yùn)算式的運(yùn)算順序;

每個(gè)運(yùn)算符和在它之前出現(xiàn)

且緊靠它的兩個(gè)運(yùn)算元構(gòu)成一個(gè)最小運(yùn)算式;如何從尾碼式求值？先找運(yùn)算符，再找運(yùn)算元例如：

ab

cde/

f

+a

bd/ec-d/e(c-d/e)

f如何從原運(yùn)算式求得尾碼式？

每個(gè)運(yùn)算符的運(yùn)算次序要由它之後的一個(gè)運(yùn)算符來(lái)定，在尾碼式中,優(yōu)先數(shù)高的運(yùn)算符領(lǐng)先於優(yōu)先數(shù)低的運(yùn)算符。分析“原運(yùn)算式”和“尾碼式”中的運(yùn)算符:原運(yùn)算式:a+b

c

d/e

f

尾碼式:abc

+de/f

從原運(yùn)算式求得尾碼式的規(guī)律為：1)設(shè)立暫存運(yùn)算符的棧;2)設(shè)運(yùn)算式的結(jié)束符為“#”,

予設(shè)運(yùn)算符棧的棧底為“#”3)若當(dāng)前字元是運(yùn)算元，則直接發(fā)送給尾碼式;4)若當(dāng)前運(yùn)算符的優(yōu)先數(shù)高於棧頂運(yùn)算符，則進(jìn)棧;5)否則，退出棧頂運(yùn)算符發(fā)送給尾碼式;

6)“(”對(duì)它之前後的運(yùn)算符起隔離作用，“)”可視為自相應(yīng)左括弧開(kāi)始的運(yùn)算式的結(jié)束符。從原運(yùn)算式求得尾碼式的規(guī)律為：voidtransform(charsuffix[],charexp[]){InitStack(S);Push(S,

#

);p=exp;ch=*p;

while(!StackEmpty(S)){if(!IN(ch,OP))Pass(Suffix,ch);else{}

if(ch!=

#

){p++;ch=*p;}else{Pop(S,ch);Pass(Suffix,ch);}

}//while}//CrtExptree……switch(ch){

case

(

:Push(S,ch);break;

case

)

:

Pop(S,c);

while(c!=

(

)

{Pass(Suffix,c);Pop(S,c)}

break;

defult:while(Gettop(S,c)&&(precede(c,ch)))

{Pass(Suffix,c);Pop(S,c);}

if(ch!=

#

)Push(S,ch);

break;

}

//switch例六、實(shí)現(xiàn)遞歸將所有的實(shí)在參數(shù)、返回地址等資訊傳遞給被調(diào)用函數(shù)保存;為被調(diào)用函數(shù)的局部變數(shù)分配存儲(chǔ)區(qū);將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。

當(dāng)在一個(gè)函數(shù)的運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行該被調(diào)用函數(shù)之前，

需先完成三項(xiàng)任務(wù)：保存被調(diào)函數(shù)的計(jì)算結(jié)果;釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū);依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成下列三項(xiàng)任務(wù)：多個(gè)函數(shù)嵌套調(diào)用的規(guī)則是:此時(shí)的記憶體管理實(shí)行“棧式管理”後調(diào)用先返回！例如：voidmain(){voida(){voidb(){

………a();b();

……}//main}//a}//bMain的數(shù)據(jù)區(qū)函數(shù)a的數(shù)據(jù)區(qū)函數(shù)b的數(shù)據(jù)區(qū)遞歸工作棧：遞歸過(guò)程執(zhí)行過(guò)程中佔(zhàn)用的數(shù)據(jù)區(qū)。遞歸工作記錄：每一層的遞歸參數(shù)合成一個(gè)記錄。當(dāng)前活動(dòng)記錄：棧頂記錄指示當(dāng)前層的執(zhí)行情況。當(dāng)前環(huán)境指針：遞歸工作棧的棧頂指針。遞歸函數(shù)執(zhí)行的過(guò)程可視為同一函數(shù)進(jìn)行嵌套調(diào)用，例如：voidhanoi(intn,charx,chary,charz){//將塔座x上按直徑由小到大且至上而下編號(hào)為1至n//的n個(gè)圓盤(pán)按規(guī)則搬到塔座z上，y可用作輔助塔座。1if(n==1)2move(x,1,z);//將編號(hào)為１的圓盤(pán)從x移到z3else{4hanoi(n-1,x,z,y);//將x上編號(hào)為１至n-1的

//圓盤(pán)移到y(tǒng),z作輔助塔5move(x,n,z);//將編號(hào)為n的圓盤(pán)從x移到z6hanoi(n-1,y,x,z);//將y上編號(hào)為１至n-1的

//圓盤(pán)移到z,x作輔助塔7}8}83abc返址nxyz52acb51abcvoidhanoi(intn,charx,chary,charz){1if(n==1)2move(x,1,z);3else{4hanoi(n-1,x,z,y);5move(x,n,z);6hanoi(n-1,y,x,z);7}8}71cab3.3 棧類(lèi)型的實(shí)現(xiàn)順序棧鏈棧//-----棧的順序存儲(chǔ)表示

-----

#defineSTACK_INIT_SIZE100

typedefstruct{

SElemType

*base;

SElemType

*top;

intstacksize;

}

SqStack;

類(lèi)似於線性表的順序映象實(shí)現(xiàn)，指向表尾的指針可以作為棧頂指針。

StatusInitStack(SqStack&S,intmaxsize){

//構(gòu)造一個(gè)最大空間為maxsize的空順序棧SS.base=new

ElemType[maxsize];

if(!S.base)exit(OVERFLOW);//存儲(chǔ)分配失敗

S.top=S.base;S.stacksize=maxsize;

returnOK;}

StatusPush(SqStack&S,SElemTypee){//

若棧不滿，則將e插入棧頂

if(S.top-S.base>=S.stacksize)

//棧滿

returnOVERFLOW;*S.top++=e;

returnOK;}StatusPop(SqStack&S,SElemType&e){//若棧不空，則刪除S的棧頂元素，

//用e返回其值，並返回OK；

//否則返回ERROR

if

(S.top

==

S.base)

returnERROR;

e=*--S.top;

returnOK;}棧頂指針鏈?！腶1an注意:鏈棧中指針的方向an-1棧底元素ADTQueue{

數(shù)據(jù)對(duì)象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

數(shù)據(jù)關(guān)係：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

約定其中a1

端為佇列頭，an

端為佇列尾基本操作：3.4佇列的類(lèi)型定義}

ADTQueue佇列的基本操作：

InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)ClearQueue(&Q)DeQueue(&Q,&e)EnQueue(&Q,e)QueueTravers(Q,visit())InitQueue(&Q)

操作結(jié)果：構(gòu)造一個(gè)空佇列Q。

DestroyQueue(&Q)

初始條件：佇列Q已存在。

操作結(jié)果：佇列Q被銷(xiāo)毀，

不再存在。

QueueEmpty(Q)

初始條件：佇列Q已存在。

操作結(jié)果：若Q為空佇列，則返回TRUE，否則返回FALSE。

QueueLength(Q)

初始條件：佇列Q已存在。

操作結(jié)果：返回Q的元素個(gè)數(shù)，即佇列的長(zhǎng)度。

GetHead(Q,&e)

初始條件：Q為非空佇列。

操作結(jié)果：用e返回Q的隊(duì)頭元素。a1a2an……

ClearQueue(&Q)

初始條件：佇列Q已存在。

操作結(jié)果：將Q清為空佇列。

EnQueue(&Q,e)

初始條件：佇列Q已存在。

操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素。a1a2ane……

DeQueue(&Q,&e)

初始條件：Q為非空佇列。

操作結(jié)果：刪除Q的隊(duì)頭元素，並用e返回其值。a1a2an……

3.5佇列類(lèi)型的實(shí)現(xiàn)鏈佇列——鏈?zhǔn)接诚筠捜辛小樞蛴诚?/p>

typedefstructQNode{//結(jié)點(diǎn)類(lèi)型

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;鏈佇列——鏈?zhǔn)接诚髏ypedefstruct{

//鏈佇列類(lèi)型

QueuePtrfront;//隊(duì)頭指針

QueuePtrrear;//隊(duì)尾指針}LinkQueue;a1∧an…Q.frontQ.frontQ.rear∧空佇列Q.rear

StatusInitQueue(LinkQueue&Q){//構(gòu)造一個(gè)空佇列Q

Q.front=Q.rear=

newQNode;

if(!Q.front)exit(OVERFLOW);//存儲(chǔ)分配失敗

Q.front->next=NULL;

returnOK;}

StatusEnQueue(LinkQueue&Q,QElemTypee){

//插入元素e為Q的新的隊(duì)尾元素

p=newQNode;

if(!p)exit(OVERFLOW);//存儲(chǔ)分配失敗

p->data=e;p->next=NULL;

Q.rear->next=p;Q.rear=p;

returnOK;}a1∧anQ.frontQ.rear∧ep

StatusDeQueue(LinkQueue&Q,QElemType&e){//若佇列不空，則刪除Q的隊(duì)頭元素，

//用e返回其值，並返回OK；否則返回ERROR

if(Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data;

Q.front->next=p->next;delete(p);

returnOK;}if(Q.rear==p)Q.rear=Q.front;#defineMAXQSIZE100//最大隊(duì)列長(zhǎng)度typedefstruct{QElemType*bas