數(shù)據(jù)結(jié)構(gòu)與算法：第2章 線性表

2.1抽象數(shù)據(jù)型線性表2.2線性表的實(shí)現(xiàn)2.3棧（Stack）2.4隊(duì)列（Queue）實(shí)驗(yàn)一：多項(xiàng)式的代數(shù)運(yùn)算2.5串（String）2.6數(shù)組（Array）2.7廣義表(Lists)第2章線性表（LinerList）2.1抽象數(shù)據(jù)型線性表[定義]

線性表是由n(n≥0)個(gè)相同類型的元素組成的有序集合。記為：

(a1,a2,a3,……ai-1,ai,ai+1,……an)其中：①n為線性表中元素個(gè)數(shù)，稱為線性表的長(zhǎng)度；當(dāng)n=0時(shí)，為空表，記為（）。②ai為線性表中的元素，類型定義為elementtype③a1為表中第1個(gè)元素，無前驅(qū)元素；an為表中最后一個(gè)元素，無后繼元素；對(duì)于…ai-1,ai,ai+1…(1<i<n)，稱ai-1

為ai的直接前驅(qū)，ai+1為ai的直接后繼。④線性表是有限的，也是有序的。線性表LIST=(D,R)D={ai|ai

∈Elementset,i=1,2,…,n,n≥0}R={H}H={<ai-1,ai>|ai-1,ai

∈D,i=2,…,n}操作：設(shè)L的型為L(zhǎng)IST線性表實(shí)例，x的型為elementtype的元素實(shí)例，p為位置變量。所有操作描述為：①INSERT(x,p,L)②LOCATE(x,L)③RETRIEVE(p,L)④DELETE(p,L)⑤PREVIOUS(p,L),NEXT(p,L)⑥MAKENULL(L)⑦FIRST(L)數(shù)學(xué)模型舉例：設(shè)計(jì)函數(shù)DELEVAL（LIST&L,elementtyped)其功能為刪除L中所有值為d的元素。

VoidDELEVAL(LIST&L,elementtyped){positionp;p=FIRST(L);while(P!=END(L)){if(same(RETRIEVE(p,L),d))DELETE(p,L);elsep=NEXT(p,L);}}2.2線性表的實(shí)現(xiàn)問題：確定數(shù)據(jù)結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）實(shí)現(xiàn)型LIST，并在此基礎(chǔ)上實(shí)現(xiàn)各個(gè)基本操作。存儲(chǔ)結(jié)構(gòu)的三種方式：①連續(xù)的存儲(chǔ)空間（數(shù)組）→靜態(tài)存儲(chǔ)②非連續(xù)存儲(chǔ)空間——指針（鏈表）→動(dòng)態(tài)存儲(chǔ)③游標(biāo)（連續(xù)存儲(chǔ)空間+動(dòng)態(tài)管理思想）→靜態(tài)鏈表2.2.1指針和游標(biāo)指針：地址量，其值為另一存儲(chǔ)空間的地址；游標(biāo)：整型量，其值為數(shù)組的下標(biāo)，用以表示指定元素的“地址”或“位置”2.2.2線性表的數(shù)組實(shí)現(xiàn)

第1個(gè)元素第2個(gè)元素

……

最后1個(gè)元素……012maxlength-1last表空單元圖2-1線性表的數(shù)組實(shí)現(xiàn)表的最大長(zhǎng)度

……第i個(gè)元素1≤i≤last類型定義：#definemaxlength100structLIST{elementtypedata[maxlength];intlast;};位置類型：

typedefintposition;線性表L:LISTL;操作：①VoidINSERT(elementtypex,positionp,LIST&L){positionq;if(L.last>=maxlength–1)error(“表滿”)；

elseif((P>L.last+1)||(p<1))error(“指定位置不存在”)；

else{for(q=L.last;q>=p;q--)L.data[q+1]=L.data[q];L.last=L.last+1;L.data[p]=x;}}②positionLOCATE(elementtypex,LISTL){positionq;for(q=1;q<=L.last;q++)if(L.data[q]==x)return(q);return(L.last+1);}③elementtypeRETRIEVE(positionp,LISTL){if(p>L.last)error(“指定元素不存在”);elsereturn(L.data[p]);}④VoidDELETE(positionp,LIST&L){positionq;if((p>L.last)||(p<1))error(“指定位置不存在”)；

else{L.last=L.last–1;for(q=p;q<=L.last;q++)L.data[q]=L.data[q+1];}}⑤positionPREVIOUS(positionp,LISTL){if((p<=1)||(p>L.last))error(“前驅(qū)元素不存在”);elsereturn(p–1);}⑧positionEND(LISTL){return(L.last+1);}⑦

positionFIRST(LISTL){return(1);}positionNEXT(positionp,LISTL){if((p<1)||(p>=L.last))error(“前驅(qū)元素不存在”);elsereturn(p+1);}⑥

positionMAKENULL(LIST&L){L.last=0;return(L.last+1);}

2.2.3線性表的指針實(shí)現(xiàn)結(jié)點(diǎn)形式datanext結(jié)點(diǎn)信息下一結(jié)點(diǎn)地址NODE結(jié)點(diǎn)類型structNODE{elementtypedata;structNODE*next;};typedefNODE*LIST;typedefNODE*position;LISTheader;positionp,q;a1a2a3an∧…h(huán)eaderqpa2:(*p).data;q:(*p).next;a2:p->data;q:p->next;記法:操作討論：插入元素:pa1xheaderqai-1aixpqan∧x∧qp(a)表頭插入元素(b)中間插入元素(c)表尾插入元素q=newNODE;q->data=x;q->next=p->next;p→next=q;或:temp=p->next;P->next=newNODE;P->next->data=x;P->next->next=temp;討論表頭結(jié)點(diǎn)的作用操作討論：刪除元素:q=p->next;P->next=q->next;deleteq;或：q=p->next;P->next=p->next->next;deleteq;討論結(jié)點(diǎn)ai的位置pa1header(a)刪除第一個(gè)元素a2qpai-1aipq(b)刪除中間元素ai+1an∧an-1qp(c)刪除表尾元素∧ADT操作：①positionEND(LIST){positionq;q=L;while(q→next!=NULL)q=q→next;return(q);};②VoidINSERT(elementtypex,positionp,LIST&L){positionq;q=newNODE;q→data=x;q→next=p→next;p→next=q;}③positionLOCATE(elementtypex,LISTL){positionp;p=L;while(p→next!=NULL)if(p→next→data==x)returnp;elsep=p→next;returnp;}④elementtypeRETRIEVE(positionp,LISTL){return(p→next→data);}⑤VoidDELETE(positionp,LIST&L){positionq;if(p→next!=NULL){q=p→next;p→next=q→next;deleteq;}};⑥positionPREVIOUS(positionp,LISTL){positionq;if(p==L→next)error(“不存在前驅(qū)元素”)；

else{q=L;while(q→next!=p)q=q→next;returnq;}}⑦positionNEXT(positionp,LISTL){positionq;if(p→next==NULL)error(“不存在后繼元素”)；

else{q=p→next;returnq;}}⑧positionMAKENULL(LIST&L){L=newNODE;L→next=NULL;returnL;}⑨positionFIRST(LISTL){returnL;}舉例：遍歷線性鏈表，按照線性表中元素的順序，依次訪問表中的每一個(gè)元素，每個(gè)元素只能被訪問一次。VoidVISITE(LISTL){positionp;p=L→next;while(p!=NULL){cout<<p→data;p=p→next;}}線性表靜態(tài)存儲(chǔ)與動(dòng)態(tài)存儲(chǔ)的比較比較參數(shù)←表的容量→←存取操作→←時(shí)間→←空間→…鏈?zhǔn)酱鎯?chǔ)靈活，易擴(kuò)充順序存取訪問元素費(fèi)時(shí)間實(shí)際長(zhǎng)度，節(jié)省空間…順序存儲(chǔ)固定，不易擴(kuò)充隨機(jī)存取插入刪除費(fèi)時(shí)間估算表長(zhǎng)度，浪費(fèi)空間…2.2.4線性表的游標(biāo)實(shí)現(xiàn)結(jié)點(diǎn)形式datanext結(jié)點(diǎn)信息下一結(jié)點(diǎn)位置spacestr結(jié)點(diǎn)類型structspacestr{elementtypedata;intnext;};線性表：spacestrSPACE[maxsize];typedefintposition;元素：SPACE[i].data→“型”為elementtype(基本、復(fù)合)下一元素位置：SPACE[i].next→“型”為int類似指針鏈表，對(duì)游標(biāo)實(shí)現(xiàn)的線性表仍設(shè)表頭結(jié)點(diǎn)。d65c-1--0a108e-1--4-1--11b21210123456789101112SPACE73LM9available線性表：

L=(a,b,c)L=7M=(d,e)M=3空閑表：available=9q=newspacestr;q=SPACE[available].next;SPACE[available].next=SPACE[q].next;deleteq;SPACE[q].next=SPACE[available].next;SPACE[available].next=q;①VoidINSERT(elementtypex,positionp,spacestr*SPACE){positionq;q=newspacestr;SPACE[q].data=x;SPACE[q].next=SPACE[p].next;SPACE[p].next=q;}②VoidDELETE(positionp,spacestr*SPACE){positionq;if(SPACE[p].next!=-1){SPACE[q]=SPACE[p].next;SPACE[p].next=SPACE[q].next;deleteq;}};操作：2.2.5雙向鏈表結(jié)點(diǎn)形式datanext結(jié)點(diǎn)信息后繼結(jié)點(diǎn)指針dcelltypeprevious前驅(qū)結(jié)點(diǎn)指針結(jié)點(diǎn)類型

structdnodetype{elementtypedata;dnodetype*next,*previous;};typedefdnodetype*DLIST;typedefdnodetype*position;ai-1

ai

ai+1

p刪除位置p的元素：p→previous→next=p→next;p→next→previous=p→previous;

∧header

an

∧tail操作：VoidINSERT(elementtypex,positionp,DLIST&L)；{positionq;q=newdnodetype;q→data=x;P→previous→next=q;q→previous=p→previous;q→next=p;p→previous=q;};討論：元素的位置？2.2.6環(huán)形鏈表單向線性鏈表雙向線性鏈表單向循環(huán)鏈表雙向循環(huán)鏈表對(duì)線性鏈表的改進(jìn)，解決“單向操作”的問題；改進(jìn)后的鏈表，能夠從任意位置元素開始，訪問表中的每一個(gè)元素。單向環(huán)形鏈表：a1a2a3an…R

其結(jié)構(gòu)與單向線性鏈表相同，用表尾指針標(biāo)識(shí)鏈表，從而省去了表頭結(jié)點(diǎn)。表頭：R→next(亦即表中的一個(gè)元素a1)操作：①在表左端插入結(jié)點(diǎn)INSERT(x,FIRST(R),R);→LINSERT(x,R)VoidLINSERT(elementtypex,LIST&R){celltype*p;p=newNODE;p→data=x;if(R==NULL){p→next=p;R=p;}else{p→next=R→next;R→next=p;}};②在表右端插入結(jié)點(diǎn)INSERT(x,END(R),R);→RINSERT(x,R)VoidRINSERT(elementtypex,LISTR){LINSERT(x,R);R=R→next;}③從表左端刪除結(jié)點(diǎn)DELETE(FIRST(R),R);→LDELETE(R)VoidLDELETE(LIST&R){structNODE*p;if(R==NULL)error(“空表”);else{p=R→next;R→next=p→next;if(p==R)R=NULL;deletep;}};雙向環(huán)形鏈表：a1

ai

an

……R

雙向環(huán)形鏈表的結(jié)構(gòu)與雙向連表結(jié)構(gòu)相同，只是將表頭元素的空previous域指向表尾，同時(shí)將表尾的空next域指向表頭結(jié)點(diǎn)，從而形成向前和向后的兩個(gè)環(huán)形鏈表，對(duì)鏈表的操作變得更加靈活。a1a2a3an…Ranan-1an-2a1…RVoidREVERS(LIST&R){positionp,q;p=R→next;R→next=p→next;p→next=p;while(R!=NULL){q=R→next;R→next=q→next;q→next=p→next;p→next=q;}R=p;}；算法如下：舉例：設(shè)計(jì)算法，將一個(gè)單向環(huán)形鏈表反向。頭元素變成尾元素，尾元素變成新的頭元素，依次類推。2.3棧（Stack）

棧是線性表的一種特殊形式，是一種限定性數(shù)據(jù)結(jié)構(gòu)，也就是在對(duì)線性表的操作加以限制后，形成的一種新的數(shù)據(jù)結(jié)構(gòu)。定義：是限定只在表尾進(jìn)行插入和刪除操作的線性表。棧又稱為后進(jìn)先出(LastInFirstOut)的線性表。簡(jiǎn)稱LIFO結(jié)構(gòu)。棧舉例a1a2······an-1anInsertDeletetopbottom棧底棧頂棧示意圖棧的基本①M(fèi)AKENULL(S)

操作②TOP(S)③POP(S)④PUSH(x,S)⑤EMPTY(S)例2：利用棧實(shí)現(xiàn)行編輯處理。設(shè)定符號(hào)“#”為擦訖符，用以刪除“#”前的字符；符號(hào)“@”為刪行符，用以刪除當(dāng)前編輯行。原理：一般字符進(jìn)棧；讀字符擦訖符退棧；刪行符則清棧算法：VoidLINEEDIT(){STACKＳ；

charc;MAKENULL(S);c=getchar();while(c!=‘\n’){if(c==‘#’)POP(S);elseif(c==‘@’)MAKENULL(S);elsePUSH(c,S);c=getchar();}

逆序輸出棧中所有元素；｝2.3.1棧的實(shí)現(xiàn)1、順序存儲(chǔ)順序棧示意圖an···ai···a3a2a1maxlength-1······3210top結(jié)構(gòu)類型：

typedefstruct{elementtypedata[maxlength];inttop;}STACK;STACKS;棧的容量：maxlength–1;棧空：S.top=0;棧滿：S.top=maxlength–1;棧頂元素：S.data[S.top];操作：①VoidMAKENULL(STACK&S){S.top=0;};②BooleanEMPTY(STACKS){if(S.top<1)returnTRUEelsereturnFALSE;};③elementtypeTOP(STACKS){ifEMPTY(S)returnNULL;elsereturn(S.data[S.top]);};操作：④elementtypePOP(STACK&S){if(EMPTY(S))error(“?？铡?;elseS.top=S.top–1;};⑤VoidPUSH(elementtypex,STACK&S){if(S.top==maxlength-1)error(“棧滿”);else{S.top=S.top+1;S.data[S.top]=x;}};2、鏈?zhǔn)酱鎯?chǔ)

采用由指針形成的線性鏈表來實(shí)現(xiàn)棧的存儲(chǔ),要考慮鏈表的哪一端實(shí)現(xiàn)元素的插入和刪除比較方便。實(shí)現(xiàn)的方式如右圖所示，其操作與線性鏈表的表頭插入和刪除元素相同。anan-1a2······a1∧top3、多個(gè)棧共用一個(gè)存儲(chǔ)空間的討論STACK[maxlength]bot[1]top[1]bot[2]top[2]bot[3]top[3]top[2]bot[n]top[n]············0Maxlength-1bot[n+1]bot[i]top[i]IntIs_Stack_i_Full(STACKS,intbot,inttop,inti)/*判斷第i個(gè)棧是否滿，滿返回1，否則返回0*/{……}VoidMove_Stack_i(STACK&S,int&bot,int&top,inti,intdt)/*移動(dòng)第i個(gè)棧，dt為位移量*/{……}…CallB…主程序A…CallC…主程序B…CallD…主程序C……i…主程序DBeginEndDaDaDbDcDbDc棧入棧出棧例1：子程序的嵌套調(diào)用2.3.2棧的應(yīng)用1、棧和遞歸過程調(diào)用Bα

βγδ調(diào)用C調(diào)用BABC棧調(diào)用Bαβ

βγδ調(diào)用C調(diào)用BABC棧調(diào)用Bαβγ

βγδ調(diào)用C調(diào)用BABC棧A的返回點(diǎn)(1)子程序A正在執(zhí)行(2)A調(diào)用B，B在執(zhí)行(3)B調(diào)用C，C在執(zhí)行先進(jìn)先出的規(guī)則：在執(zhí)行的任何點(diǎn)處，若一個(gè)程序要將控制返回到調(diào)用程序，則該程序一定是最末一個(gè)進(jìn)入的。例2：間接遞歸3個(gè)程序A、B、C，其中A調(diào)用B，B調(diào)用C，而C又遞歸調(diào)用B。調(diào)用Bαβ

βγδ調(diào)用C調(diào)用BABC棧調(diào)用Bαβγ

βγδ調(diào)用C調(diào)用BABC棧(6)C返回到B，（第一次調(diào)用）

B在執(zhí)行，C執(zhí)行完畢成(5)B返回到C，C在執(zhí)行對(duì)B的遞歸調(diào)用完畢調(diào)用Bα

βγδ調(diào)用C調(diào)用BABC棧(7)B返回到A，A在執(zhí)行，非遞歸調(diào)用B完畢調(diào)用Bαβγδ

βγδ調(diào)用C調(diào)用BABC棧(4)C遞歸調(diào)用B，,B在執(zhí)行SubA…CallA…Da1Da2Da3…Dan-1Da1Da2Da3…Dan-1DanDanBeginEnd例3：直接遞歸2、迷宮求解問題：010001100011111100011011100111011000011110011110111101101100110100101111111001101110100111011110011111111001101101111101110001101100000001111100011110010011111011110

一個(gè)迷宮可用上圖所示方陣[m,n]表示，0表示能通過，1表示不能通過?，F(xiàn)假設(shè)耗子從左上角[1,1]進(jìn)入迷宮，編寫算法，尋求一條從右下角[m,n]出去的路徑。11×15→m×n出口入口**********************************************迷宮示例2、迷宮求解分析：⑴迷宮可用二維數(shù)組Maze[i][j](1≤i≤m,1≤j≤n)表示，入口maze[1][1]=0;耗子在任意位置可用（i,j）坐標(biāo)表示；⑵位置(i,j)周圍有8個(gè)方向可以走通，分別記為：E,SE,S,SW,W,NW,N,NE;如圖所示。方向v按從正東開始且順時(shí)針分別記為1-8，v=1,8;設(shè)二維數(shù)組move記下八個(gè)方位的增量；i,jN:(i-1,j)NE:(i-1,j+1)E:(i,j+1)SE:(i+1,j+1)S:(i+1,j)SW:(i+1,j-1)W:(i,j-1)NW:(i-1,j-1)ji從(i,j)到(g,h)且v=2(東南）則有：g=i+move[v][1]=i+1;h=j+move[v][2]=j+1;Vij說明101E211SE310S41-1SW50-1W6-1-1NW7-10N8-11NE⑶為避免時(shí)時(shí)監(jiān)測(cè)邊界狀態(tài)，可把二維數(shù)組maze[1:m,1:n]擴(kuò)大為maze[0:m+1,0:n+1]，且令0行和0列、m+1行和n+1列的值為1；出口入口****************************迷宮示例⑷采用試探的方法，當(dāng)?shù)竭_(dá)某個(gè)位置且周圍八個(gè)方向走不通時(shí)需要回退到上一個(gè)位置，并換一個(gè)方向繼續(xù)試探；為解決回退問題，需設(shè)一個(gè)棧，當(dāng)?shù)竭_(dá)一個(gè)新位置時(shí)將（i,j,v）進(jìn)棧，回退時(shí)退棧。⑸每次換方向?qū)ふ倚挛恢脮r(shí)，需測(cè)試該位置以前是否已經(jīng)經(jīng)過，對(duì)已到達(dá)的位置，不能重復(fù)試探，為此設(shè)矩陣mark，其初值為0，一旦到達(dá)位置(i,j)時(shí)，置mark[i][j]=1;文字描述算法：⑴耗子在(1,1)進(jìn)入迷宮，并向正東（v=1）方向試探。⑵檢測(cè)下一方位(g,h)。若(g,h)=(m,n)且maze[m][n]=0，則耗子到達(dá)出口，輸出走過的路徑；程序結(jié)束。⑶若(g,h)≠(m,n),但(g,h)方位能走通且第一次經(jīng)過,則記下這一步，并從(g,h)

出發(fā)，再向東試探下一步。否則仍在(i,j)方位換一個(gè)方向試探。⑷若(i,j)方位周圍8個(gè)方位阻塞或已經(jīng)過，則需退一步，并換一個(gè)方位試探。若(i,j)=(1,1)則到達(dá)入口，說明迷宮走不通。VoidGETMAZE(maze,mark,move,S){(i,j,v)=(1,1,1);mark[1][1]=1;s.top=0;do{g=i+move[v][1];h=j+move[v][2];if((g==m)&&(h==n)&&(maze[m][n]==0)){output(S);return;}if((maze[g][h]==0)&&mark[g][h]==0)){mark[g][h]=1;PUSH(i,j,v,S);(i,j,v)=(g,h,1);}elseif(v<8)v=v+1;else{while((s.v==8)&&(!EMPTY(S)))POP(S);if(s.top>0)(i,j,v＋＋)=POP(S);};}while((s.top)&&(v!=8));cout<<“路徑不存在！”；}3、表達(dá)式求值

前綴表達(dá)式（逆波蘭式）表達(dá)式：中綴表達(dá)式后綴表達(dá)式（波蘭式）例如：*+ab－ab(a+b)*(a－b)(a+b)*(a－b)ab+ab－*

高級(jí)語言中，采用類似自然語言的中綴表達(dá)式，但計(jì)算機(jī)對(duì)中綴表達(dá)式的處理是很困難的，而對(duì)后綴或前綴表達(dá)式則顯得非常簡(jiǎn)單。后綴表達(dá)式的特點(diǎn)：①在后綴表達(dá)式中，變量（操作數(shù)）出現(xiàn)的順序與中綴表達(dá)式順序相同。②后綴表達(dá)式中不需要括弧定義計(jì)算順序，而由運(yùn)算（操作符）的位置來確定運(yùn)算順序。波蘭邏輯學(xué)家J.Lukasiewicz于1929年提出的一種表達(dá)式。Ⅰ.將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式

對(duì)中綴表達(dá)式從左至右依次掃描，由于操作數(shù)的順序保持不變，當(dāng)遇到操作數(shù)時(shí)直接輸出；為調(diào)整運(yùn)算順序，設(shè)立一個(gè)棧用以保存操作符，掃描到操作符時(shí)，將操作符壓入棧中，進(jìn)棧的原則是保持棧頂操作符的優(yōu)先級(jí)要高于棧中其他操作符的優(yōu)先級(jí)，否則，將棧頂操作符依次退棧并輸出，直到滿足要求為止。遇到“（”進(jìn)棧，當(dāng)遇到“）”時(shí)，退棧輸出直到“）”為止。Ⅱ.由后綴表達(dá)式計(jì)算表達(dá)式的值

對(duì)后綴表達(dá)式從左至右依次掃描，與Ⅰ相反，遇到操作數(shù)時(shí)，將操作數(shù)進(jìn)棧保留；當(dāng)遇到操作符時(shí)，從棧中退出兩個(gè)操作數(shù)并作相應(yīng)運(yùn)算，將計(jì)算結(jié)果進(jìn)棧保留；直到表達(dá)式結(jié)束，棧中唯一元素即為表達(dá)式的值。2.4隊(duì)列（Queue）

隊(duì)列是對(duì)線性表的插入和刪除操作加以限定的另一種限定型數(shù)據(jù)結(jié)構(gòu)。[定義]

將線性表的插入和刪除操作分別限制在表的兩端進(jìn)行，和棧相反，隊(duì)列是一種先進(jìn)先出（FirstInFirstOut，簡(jiǎn)稱FIFO結(jié)構(gòu)）的線性表。a1，a2，a3，···，···，an-1，an出隊(duì)列入隊(duì)列，插入，排隊(duì)刪除，出隊(duì)隊(duì)頭隊(duì)尾隊(duì)列示意圖frontrear操作：MAKENULL(Q)、FRONT(Q)、ENQUEUE(x,Q)、DEQUEUE(Q)、EMPTY(Q)2.4.1隊(duì)列的指針實(shí)現(xiàn)元素結(jié)構(gòu)：

structNODE{elementtypedata；

celltype*next；

}；隊(duì)列的“型”：

structQUEUE{celltype*front；

celltype*rear；}a1a2an∧…Q.frontQ.rear隊(duì)列的指針實(shí)現(xiàn)示意圖操作：①VoidMAKENULL(QUEUE&Q){Q.front=NewNODE;Q.front→next=NULL;Q.rear=Q.front;};②booleanEMPTY(Q);QUEUE&Q;{if(Q.front==Q.rear)returnTRUE;elsereturnFALSE;};③elementtypeFRONT(Q);QUEUEQ;{returnQ.front→data;};④VoidENQUEUE(elementtypex,QUEUE&Q){Q.rear→next=newNODE;Q.rear=Q.rear→next;Q.rear→data=x;Q.rear→next=NULL;};⑤VoidDELETE(QUEUE&Q){celltype*temp;if(EMPTY(Q))error(“空隊(duì)列”);else{temp=Q.front→next;Q.front→next=temp→next;deletetemp;if(Q.front→next==NULL)Q.rear=Q.front;}};2.4.2隊(duì)列的數(shù)組實(shí)現(xiàn)隊(duì)列的“型”：

structQUEUE{elementtypedata[maxlength];intfront；

intrear；

}隨著不斷有元素出隊(duì)和進(jìn)隊(duì)（插入和刪除），隊(duì)列的狀態(tài)由1變成2；此時(shí)an占據(jù)隊(duì)列的最后一個(gè)位置；第n+1個(gè)元素?zé)o法進(jìn)隊(duì),但實(shí)際上，前面部分位置空閑。a1a2a3a4···an···

Qfrontrearmaxlength右圖：隊(duì)列Q狀態(tài)1“假溢出“maxlengtha1a2a3a4a5a6···anQfrontrear下圖：隊(duì)列Q狀態(tài)2

解決假溢出的方法有多種；一是通過不斷移動(dòng)元素位置，每當(dāng)有元素出隊(duì)列時(shí)，后面的元素前移一個(gè)位置，是隊(duì)頭元素始終占據(jù)隊(duì)列的第一個(gè)位置。第二種方法是采用循環(huán)隊(duì)列。?········Q.rearQ.front01maxlength-1隊(duì)列Q······插入元素：

Q.rear=(Q.rear+1）%maxlength刪除元素：

Q.front=(Q.front+1）%maxlength隊(duì)空：

(Q.rear+1）%maxlength==Q.front隊(duì)滿：

(Q.rear+1)%maxlength==Q.front012345…n-1n-2i…frontreara1a2a3a4a5Q.rear=(Q.rear+1）%nQ.front=(Q.front+1）%n問題：如何解決循環(huán)隊(duì)列中隊(duì)空與隊(duì)滿狀態(tài)相同？方法一：約定隊(duì)列頭指針在隊(duì)列尾指針的下一位置上；方法二：另設(shè)一個(gè)標(biāo)志位用以區(qū)別隊(duì)空與隊(duì)滿兩種狀態(tài)；結(jié)論：兩種方法的代價(jià)是相同的。操作：

intaddone(inti){return((i+1）%maxlength);};①VoidMAKENULL(QUEUE&Q){Q.front=0;Q.rear=maxlength–1;}②booleanEMPTY(Q)QUEUEQ;{if(addone(Q.rear)==Q.front)returnTRUE;elsereturnFALSE;}

操作：③elementtypeFRONT(QUEUEQ){if(EMPTY(Q))returnNULL;elsereturn(Q.data[Q.front]);};④VoidENQUEUE(elementtypex,QUEUEQ){if(addone(addone(Q.rear))==Q.front)error(“隊(duì)列滿”);else{Q.rear=addone(Q.rear);Q.datas[Q.rear]=x;}}⑤VoidDEQUEUE(QUEUEQ);{if(EMPTY(Q))error(“空隊(duì)列”);elseQ.front=addone(Q.front);};實(shí)驗(yàn)一多項(xiàng)式的代數(shù)運(yùn)算P(x)=∑aixii=n-10方案1：數(shù)組一方案2：數(shù)組二n-1an-1……iai……3a32a21a10a0coefn-1expn-1coefn-2expn-2……coefiexpi……coef2exp2coef1exp1coef0exp0……P(x)=3x14+2x8+1P(x)=3x14+2x8+1143130120110100908270605040302010013142810…coeftypep[N};Struct{coeftypecoef;exptypeexp;}p[N]結(jié)點(diǎn)結(jié)構(gòu)coefexplink系數(shù)指數(shù)下一項(xiàng)地址結(jié)點(diǎn)類型：

structpolynode{intcoef；

intexp；

polylink*link；

}typedefpolynode*polypointer；P(x)=∑aixii=n0方案3：鏈表例如：多項(xiàng)式p(x)=3x14+2x8+1采用鏈表表示如下：3142810∧P算法attch(c,e,d)建立一個(gè)新結(jié)點(diǎn)，其系數(shù)coef=c，指數(shù)exp=e；并把它鏈到d所指結(jié)點(diǎn)之后，返回該結(jié)點(diǎn)指針。

polypointerattch(intc,inte,polypointerd){polypointerx;x=newpolynode;x→coef=c;x→exp=e;d→link=x;returnx;};算法padd實(shí)現(xiàn)兩個(gè)多項(xiàng)式

a，b相加；

c(x)=a(x)+b(x)polypointerpadd()polypointera,polypointerb;{polypointerp,q,d,c;intx;p=a→link;q=b→link;c=newpolynode;d=c;while((p!=NULL)&&(q!=NULL))switch(compare(p→exp,q→exp)){case‘=‘:x=p→coef+q→coef;if(x)d=attch(x,p→exp,d);p=p→link;q=q→link;break;case‘>’:d=attch(p→coef,p→exp,d);p=p→link;break;case‘<‘:d=attch(q→coef,q→exp,d);q=q→link;break;}while(p!=NULL){d=attch(p→coef,p→exp,d);p=p→link;}while(q!=NULL){d=attch(q→coef,q→exp,d);q=q→link;}d→link=NULL;p=c;c=c→link;deletep;returnc;}2.5串(String)

串是線性表的一種特殊形式，表中每個(gè)元素的類型為字符型，是一個(gè)有限的字符序列。串的基本形式可表示成：S=‘a(chǎn)1a2a3······an’；其中：charai；0≤i≤n；n≥0；當(dāng)n=0時(shí)，為空串。

n為串的長(zhǎng)度；C語言中串有兩種實(shí)現(xiàn)方法：

1、字符數(shù)組，如：charstr1[10]；

2、字符指針，如：char*str2；操作：stringNULL();booleanISNULL(S);VoidIN(S,a);intLEN(S);VoidCONCAT(S1,S2);stringSUBSTR(S,m,n);booleanINDEX(S,S1);2.5.1抽象數(shù)據(jù)型串例一：將串T插在串S中第i個(gè)字符之后INSERT(S,T,i)。VoidINSERT(STRING&S,STRINGT,inti){STRINGt1,t2;if((i<0)||(i>LEN(S))error‘指定位置不對(duì)’;elseif(ISNULL(S))S=T;elseif(ISNULL(T)){t1=SUBSTR(S,1,i);t2=SUBSTR(S,i+1,LEN(S));S=CONCAT(t1,CONCAT(T,t2));}}VoidDELETE(STRING&S,STRINGT){STRINGt1,t2;intm,n;m=INDEX(S,T);if(m==0)error‘串S中不包含子串T’;else{n=LEN(T);t1=SUBSTR(S,1,m-1);t2=SUBSTR(S,m+n,LEN(S));S=CONCAT(t1,t2);}}例二：從串S中將子串T刪除DELETE(S,T)。2.5.2串的實(shí)現(xiàn)1、串的順序存儲(chǔ)采用連續(xù)的存儲(chǔ)空間（數(shù)組），自第一個(gè)元素開始，依次存儲(chǔ)字符串中的每一個(gè)字符。

charstr[10]=“China”；‘C’‘h’‘i’‘n’‘a(chǎn)’‘\0’

0123456789str串的順序存儲(chǔ)操作：NULL，ISNULL，IN，LEN，CONCAT，SUBSTR，INDEX2、串的鏈?zhǔn)酱鎯?chǔ)構(gòu)造線性鏈表，element類型為char，自第一個(gè)元素開始，依次存儲(chǔ)字符串中的每一個(gè)字符。2、串的鏈?zhǔn)酱鎯?chǔ)‘i’

‘n’

‘a(chǎn)’∧‘C’

‘h’

str1structnode{chardata;node*link;};typedefnode*STRING1;STRINGstr1;structnode{chardata[4];node*link;};typedefnode*STRING2;STRINGstr2;‘C’‘h’‘i’‘n’

‘C’‘￠’‘￠’‘￠’∧str2假設(shè)地址量（link）占用2個(gè)字節(jié)5/155/12intINDEX(STRING1S,S1){structnode*p,*q,*i;intt;if((S1!=NULL)&&(S!=NULL)){t=1;i=S;q=S1;do{if(p→data==q→data){q=q→link;if(q==NULL)return(t);p=p→link;}else{t=t+1;i=i→link;p=i;q=S1;}}while(p!=NULL);}return0;};INDEX(S,S1)若

S1是S的子串則返回

S1首字符在S中的位置；否則返回0；操作：2.6數(shù)組(ARRAY)2.6.1抽象數(shù)據(jù)型數(shù)組●數(shù)組是由下標(biāo)（index）和值（value）組成的序?qū)Γ╥ndex，value）的集合?！褚部梢远x為是由相同類型的數(shù)據(jù)元素組成有限序列?！駭?shù)組在內(nèi)存中是采用一組連續(xù)的地址空間存儲(chǔ)的，正是由于此種原因，才可以實(shí)現(xiàn)下標(biāo)運(yùn)算?！袼袛?shù)組都是一個(gè)一維向量。數(shù)組1：(a1,a2,a3,···,ai,···,an);數(shù)組2：(a11,···,a1n,a21,···,a2n,···,aij,···,am1,···,amn);1≤i≤m,1≤j≤n;數(shù)組3:(a111,···,a11n,a121,···,a12n,···,aijk,···,amn1,···,am