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

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

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

是一個數(shù)據(jù)元素的有序（次序）集2.1線性表的類型定義2.2線性表的順序表示和實現(xiàn)2.3線性表的鏈式表示和實現(xiàn)

2.3.1線性鏈表

2.3.2迴圈鏈表

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

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

為線性表的表長;

稱n=0

時的線性表為空表。}數(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)銷毀操作

引用型操作

加工型操作

}ADTList

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

結(jié)構(gòu)銷毀操作DestroyList(&L)初始條件：操作結(jié)果：線性表L已存在。銷毀線性表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()為某個訪問函數(shù)。依次對L中每個元素調(diào)用函數(shù)標visit()。一旦visit()失敗，則操作失敗。（遍曆線性表）加工型操作

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

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

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

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

要求對線性表作如下操作：擴大線性表LA，將存在於線性表LB中而不存在於線性表

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

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

LocateElem(LA,e,equal())

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

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

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

ListInsert(La,++La_len,e);

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

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)。有序表則

歸併兩個“其數(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中取得當前元素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歸併為Lc}//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){//當La不空時

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

}

//插入La表中剩餘元素

while(j<=Lb_len){//當Lb不空時

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

}

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

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

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

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

a1a2

…ai-1ai

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

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

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

LOC(ai)=

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

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

}Sqlist;

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

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

length;//當前長度int

listsize;//當前分配的存儲容量

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

ListInsert(&L,i,e)的實現(xiàn)：首先分析:插入元素時，線性表的邏輯結(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>表的長度增加(a1,…,ai-1,e,ai,…,an)

StatusListInsert_Sq(SqList&L,inti,ElemTypee){

//

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

//i的合法範圍為1≤i≤L.length+1}//ListInsert_Sq

演算法時間複雜度為: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;//表長增1returnOK;……元素右移if(L.length>=L.listsize)returnOVERFLOW;//當前存儲空間已滿

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

returnERROR;

//

插入位置不合法考慮移動元素的平均情況:

假設(shè)在第

i個元素之前插入的概率為，

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

若假定線上性表中任何一個位置上進行插入的概率都是相等的，則移動元素的期望值為：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)的實現(xiàn)：首先分析：刪除元素時，線性表的邏輯結(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>表的長度減少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;//表長減1returnOK;演算法時間複雜度為:

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

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

假設(shè)刪除第

i個元素的概率為

,則在長度為n的線性表中刪除一個元素所需移動元素次數(shù)的期望值為：若假定線上性表中任何一個位置上進行刪除的概率都是相等的，則移動元素的期望值為：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線性表類型的實現(xiàn)----鏈式映象一、單鏈表二、結(jié)點和單鏈表的C語言描述三、線性表的操作在單鏈表中的實現(xiàn)四、其他形式的鏈表

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

+指針(指示後繼元素存儲位置)=結(jié)點

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

稱作鏈表

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

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

有時為了操作方便，在第一個結(jié)點之前虛加一個“頭結(jié)點”，以指向頭結(jié)點的指針為鏈表的頭指針空指針線性表為空表時，頭結(jié)點的指針域為空

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

structLnode*next;//指針域

}LNode,*LinkList;

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

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

線性表的操作

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

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

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

令指針p

始終指向線性表中第j

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

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

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

//

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

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

線性表的操作

ListInsert(&L,i,e)

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

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

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

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

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

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

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

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

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

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

//

尋找第i-1個結(jié)點if(!p||j>i-1)

returnERROR;//

i大於表長或者小於1s=newLNode;

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

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

在單鏈表中刪除第

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

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

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

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

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

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

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

while(L->next){

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

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

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

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

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

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

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);}說明：第一個生成的結(jié)點是開始結(jié)點，將開始結(jié)點插入到空表中，是在當前鏈表的第一個位置上插入，該位置上的插入操作和鏈表中其他位置上的插入操作處理是不一樣的，原因是開始結(jié)點的位置是存放在頭指針（指針變數(shù)）中，而其餘結(jié)點的位置是在其前趨結(jié)點的指針域中。演算法中的第一個if語句就是用來對第一個位置上的插入操作做特殊處理。演算法中的第二個if語句的作用是為了分別處理空表和非空表兩種不同的情況，若讀入的第一個字元就是結(jié)束標誌符，則鏈表head是空表，尾指針r亦為空，結(jié)點*r不存在；否則鏈表head非空，最後一個尾結(jié)點*r是終端結(jié)點，應(yīng)將其指針域置空。

如果我們在鏈表的開始結(jié)點之前附加一個結(jié)點，並稱它為頭結(jié)點，那麼會帶來以下兩個優(yōu)點：a、由於開始結(jié)點的位置被存放在頭結(jié)點的指針域中，所以在鏈表的第一個位置上的操作就和在表的其他位置上的操作一致，無需進行特殊處理；b、無論鏈表是否為空，其頭指針是指向頭結(jié)點在的非空指針（空表中頭結(jié)點的指針域為空），因此空表和非空表的處理也就統(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);}

上述演算法裏動態(tài)申請新結(jié)點空間時未加錯誤處理，可作下列處理：

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

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

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

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

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

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雙向鏈表的操作特點：“查詢”和單鏈表相同“插入”和“刪除”時需要同時修改兩個方向上的指針。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一元多項式的表示在電腦中，可以用一個線性表來表示:P=(p0,p1,…，pn)一元多項式但是對於形如S(x)=1+3x10000–2x20000的多項式，上述表示方法是否合適？

一般情況下的一元稀疏多項式可寫成

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

是指數(shù)為ei

的項的非零係數(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ù)對象：

數(shù)據(jù)關(guān)係：抽象數(shù)據(jù)類型一元多項式的定義如下：D＝{ai|ai∈TermSet,i=1,2,...,m,m≥0TermSet中的每個元素包含一個表示係數(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項的係數(shù)和指數(shù)，建立一元多項式

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

PolynLength(P)

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

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

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

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

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

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

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

a1小，a1後面的值都比

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

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

線性表棧佇列Insert(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ù)類型3.1棧的類型定義3.2棧的應(yīng)用舉例3.3棧類型的實現(xiàn)3.4佇列的類型定義3.5佇列類型的實現(xiàn)3.1

棧的類型定義ADTStack

{

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

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)造一個空棧S。

DestroyStack(&S)

初始條件：棧S已存在。

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

StackEmpty(S)

初始條件：棧S已存在。

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

StackLength(S)

初始條件：棧S已存在。

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

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)換例二、括弧匹配的檢驗例三、行編輯程式問題例四、迷宮求解例五、運算式求值例六、實現(xiàn)遞歸

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

算法基于原理：

N=(Ndivd)×d+Nmodd

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

，其運算過程如下：

NNdiv8Nmod8

13481684

168210

2125

202計算順序輸出順序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例二、括弧匹配的檢驗假設(shè)在運算式中（［］（））或［（［］［］）］等為正確的格式，［（］）或（［（））或(()])均為不正確的格式。則檢驗括弧是否匹配的方法可用“期待的急迫程度”這個概念來描述。分析可能出現(xiàn)的不匹配的情況:到來的右括弧非是所“期待”的;例如：考慮下列括弧序列：

[([][])]12345678到來的是“不速之客”;直到結(jié)束，也沒有到來所“期待”的括弧;演算法的設(shè)計思想：1）凡出現(xiàn)左括弧，則進棧；2）凡出現(xiàn)右括弧，首先檢查棧是否空若?？眨瑒t表明該“右括弧”多餘否則和棧頂元素比較，若相匹配，則“左括弧出?！狈駝t表明不匹配3）運算式檢驗結(jié)束時，若?？?，則表明運算式中匹配正確否則表明“左括弧”有餘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;…...例三、行編輯程式問題如何實現(xiàn)？“每接受一個字元即存入記憶體”?

並不恰當！

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

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

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

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

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();//從終端接收下一個字元

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

11

112

222

232

133

134

424

125

126

416

315

314

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

do｛

若當前位置可通，

則｛將當前位置插入棧頂；

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

｝

否則{

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

…

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

若棧不空，則重新測試新的棧頂位置，

直至找到一個可通的相鄰塊或出棧至?？?；｝若?？眨瑒t表明迷宮沒有通路。

限於二元運算符的運算式定義:

運算式::=(運算元)+(運算符)+(運算元)

運算元::=簡單變數(shù)|運算式簡單變數(shù)::=識別字|無符號整數(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）運算元之間的相對次序不變;2）運算符的相對次序不同;3）中綴式丟失了括弧資訊，致使運算的次序不確定;4)首碼式的運算規(guī)則為:連續(xù)出現(xiàn)的兩個運算元和在它們之前且緊靠它們的運算符構(gòu)成一個最小運算式;5)尾碼式的運算規(guī)則為:

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

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

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

ab

cde/

f

+a

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

f如何從原運算式求得尾碼式？

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

c

d/e

f

尾碼式:abc

+de/f

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

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

6)“(”對它之前後的運算符起隔離作用，“)”可視為自相應(yīng)左括弧開始的運算式的結(jié)束符。從原運算式求得尾碼式的規(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例六、實現(xiàn)遞歸將所有的實在參數(shù)、返回地址等資訊傳遞給被調(diào)用函數(shù)保存;為被調(diào)用函數(shù)的局部變數(shù)分配存儲區(qū);將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。

當在一個函數(shù)的運行期間調(diào)用另一個函數(shù)時，在運行該被調(diào)用函數(shù)之前，

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

………a();b();

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

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

//圓盤移到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 棧類型的實現(xiàn)順序棧鏈棧//-----棧的順序存儲表示

-----

#defineSTACK_INIT_SIZE100

typedefstruct{

SElemType

*base;

SElemType

*top;

intstacksize;

}

SqStack;

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

StatusInitStack(SqStack&S,intmaxsize){

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

ElemType[maxsize];

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

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ù)對象：

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佇列的類型定義}

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)造一個空佇列Q。

DestroyQueue(&Q)

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

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

不再存在。

QueueEmpty(Q)

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

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

QueueLength(Q)

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

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

GetHead(Q,&e)

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

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

ClearQueue(&Q)

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

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

EnQueue(&Q,e)

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

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

DeQueue(&Q,&e)

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

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

3.5佇列類型的實現(xiàn)鏈佇列——鏈式映象迴圈佇列——順序映象

typedefstructQNode{//結(jié)點類型

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;鏈佇列——鏈式映象typedefstruct{

//鏈佇列類型

QueuePtrfront;//隊頭指針

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

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

Q.front=Q.rear=

newQNode;

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

Q.front->next=NULL;

returnOK;}

StatusEnQueue(LinkQueue&Q,QElemTypee){

//插入元素e為Q的新的隊尾元素

p=newQNode;

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

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的隊頭元素，

//用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//最大隊列長度typedefstruct{QElemType*bas