數據結構與算法：第2章 線性表

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

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

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

為ai的直接前驅，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}操作：設L的型為LIST線性表實例，x的型為elementtype的元素實例，p為位置變量。所有操作描述為：①INSERT(x,p,L)②LOCATE(x,L)③RETRIEVE(p,L)④DELETE(p,L)⑤PREVIOUS(p,L),NEXT(p,L)⑥MAKENULL(L)⑦FIRST(L)數學模型舉例：設計函數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線性表的實現問題：確定數據結構（存儲結構）實現型LIST，并在此基礎上實現各個基本操作。存儲結構的三種方式：①連續(xù)的存儲空間（數組）→靜態(tài)存儲②非連續(xù)存儲空間——指針（鏈表）→動態(tài)存儲③游標（連續(xù)存儲空間+動態(tài)管理思想）→靜態(tài)鏈表2.2.1指針和游標指針：地址量，其值為另一存儲空間的地址；游標：整型量，其值為數組的下標，用以表示指定元素的“地址”或“位置”2.2.2線性表的數組實現

第1個元素第2個元素

……

最后1個元素……012maxlength-1last表空單元圖2-1線性表的數組實現表的最大長度

……第i個元素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(“前驅元素不存在”);elsereturn(p–1);}⑧positionEND(LISTL){return(L.last+1);}⑦

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

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

2.2.3線性表的指針實現結點形式datanext結點信息下一結點地址NODE結點類型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;討論表頭結點的作用操作討論：刪除元素:q=p->next;P->next=q->next;deleteq;或：q=p->next;P->next=p->next->next;deleteq;討論結點ai的位置pa1header(a)刪除第一個元素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(“不存在前驅元素”)；

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;}舉例：遍歷線性鏈表，按照線性表中元素的順序，依次訪問表中的每一個元素，每個元素只能被訪問一次。VoidVISITE(LISTL){positionp;p=L→next;while(p!=NULL){cout<<p→data;p=p→next;}}線性表靜態(tài)存儲與動態(tài)存儲的比較比較參數←表的容量→←存取操作→←時間→←空間→…鏈式存儲靈活，易擴充順序存取訪問元素費時間實際長度，節(jié)省空間…順序存儲固定，不易擴充隨機存取插入刪除費時間估算表長度，浪費空間…2.2.4線性表的游標實現結點形式datanext結點信息下一結點位置spacestr結點類型structspacestr{elementtypedata;intnext;};線性表：spacestrSPACE[maxsize];typedefintposition;元素：SPACE[i].data→“型”為elementtype(基本、復合)下一元素位置：SPACE[i].next→“型”為int類似指針鏈表，對游標實現的線性表仍設表頭結點。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雙向鏈表結點形式datanext結點信息后繼結點指針dcelltypeprevious前驅結點指針結點類型

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)鏈表對線性鏈表的改進，解決“單向操作”的問題；改進后的鏈表，能夠從任意位置元素開始，訪問表中的每一個元素。單向環(huán)形鏈表：a1a2a3an…R

其結構與單向線性鏈表相同，用表尾指針標識鏈表，從而省去了表頭結點。表頭：R→next(亦即表中的一個元素a1)操作：①在表左端插入結點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;}};②在表右端插入結點INSERT(x,END(R),R);→RINSERT(x,R)VoidRINSERT(elementtypex,LISTR){LINSERT(x,R);R=R→next;}③從表左端刪除結點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)形鏈表的結構與雙向連表結構相同，只是將表頭元素的空previous域指向表尾，同時將表尾的空next域指向表頭結點，從而形成向前和向后的兩個環(huán)形鏈表，對鏈表的操作變得更加靈活。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;}；算法如下：舉例：設計算法，將一個單向環(huán)形鏈表反向。頭元素變成尾元素，尾元素變成新的頭元素，依次類推。2.3棧（Stack）

棧是線性表的一種特殊形式，是一種限定性數據結構，也就是在對線性表的操作加以限制后，形成的一種新的數據結構。定義：是限定只在表尾進行插入和刪除操作的線性表。棧又稱為后進先出(LastInFirstOut)的線性表。簡稱LIFO結構。棧舉例a1a2······an-1anInsertDeletetopbottom棧底棧頂棧示意圖棧的基本①MAKENULL(S)

操作②TOP(S)③POP(S)④PUSH(x,S)⑤EMPTY(S)例2：利用棧實現行編輯處理。設定符號“#”為擦訖符，用以刪除“#”前的字符；符號“@”為刪行符，用以刪除當前編輯行。原理：一般字符進棧；讀字符擦訖符退棧；刪行符則清棧算法：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棧的實現1、順序存儲順序棧示意圖an···ai···a3a2a1maxlength-1······3210top結構類型：

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、鏈式存儲

采用由指針形成的線性鏈表來實現棧的存儲,要考慮鏈表的哪一端實現元素的插入和刪除比較方便。實現的方式如右圖所示，其操作與線性鏈表的表頭插入和刪除元素相同。anan-1a2······a1∧top3、多個棧共用一個存儲空間的討論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個棧是否滿，滿返回1，否則返回0*/{……}VoidMove_Stack_i(STACK&S,int&bot,int&top,inti,intdt)/*移動第i個棧，dt為位移量*/{……}…CallB…主程序A…CallC…主程序B…CallD…主程序C……i…主程序DBeginEndDaDaDbDcDbDc棧入棧出棧例1：子程序的嵌套調用2.3.2棧的應用1、棧和遞歸過程調用Bα

βγδ調用C調用BABC棧調用Bαβ

βγδ調用C調用BABC棧調用Bαβγ

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

βγδ調用C調用BABC棧調用Bαβγ

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

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

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

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

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

出發(fā)，再向東試探下一步。否則仍在(i,j)方位換一個方向試探。⑷若(i,j)方位周圍8個方位阻塞或已經過，則需退一步，并換一個方位試探。若(i,j)=(1,1)則到達入口，說明迷宮走不通。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、表達式求值

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

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

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

對后綴表達式從左至右依次掃描，與Ⅰ相反，遇到操作數時，將操作數進棧保留；當遇到操作符時，從棧中退出兩個操作數并作相應運算，將計算結果進棧保留；直到表達式結束，棧中唯一元素即為表達式的值。2.4隊列（Queue）

隊列是對線性表的插入和刪除操作加以限定的另一種限定型數據結構。[定義]

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

structNODE{elementtypedata；

celltype*next；

}；隊列的“型”：

structQUEUE{celltype*front；

celltype*rear；}a1a2an∧…Q.frontQ.rear隊列的指針實現示意圖操作：①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(“空隊列”);else{temp=Q.front→next;Q.front→next=temp→next;deletetemp;if(Q.front→next==NULL)Q.rear=Q.front;}};2.4.2隊列的數組實現隊列的“型”：

structQUEUE{elementtypedata[maxlength];intfront；

intrear；

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

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

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

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

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

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

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

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(“隊列滿”);else{Q.rear=addone(Q.rear);Q.datas[Q.rear]=x;}}⑤VoidDEQUEUE(QUEUEQ);{if(EMPTY(Q))error(“空隊列”);elseQ.front=addone(Q.front);};實驗一多項式的代數運算P(x)=∑aixii=n-10方案1：數組一方案2：數組二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]結點結構coefexplink系數指數下一項地址結點類型：

structpolynode{intcoef；

intexp；

polylink*link；

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

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

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)

串是線性表的一種特殊形式，表中每個元素的類型為字符型，是一個有限的字符序列。串的基本形式可表示成：S=‘a1a2a3······an’；其中：charai；0≤i≤n；n≥0；當n=0時，為空串。

n為串的長度；C語言中串有兩種實現方法：

1、字符數組，如：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抽象數據型串例一：將串T插在串S中第i個字符之后INSERT(S,T,i)。VoidINSERT(STRING&S,STRINGT,inti){STRINGt1,t2;if((i<0)||(i>LEN(S))error‘指定位置不對’;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串的實現1、串的順序存儲采用連續(xù)的存儲空間（數組），自第一個元素開始，依次存儲字符串中的每一個字符。

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

0123456789str串的順序存儲操作：NULL，ISNULL，IN，LEN，CONCAT，SUBSTR，INDEX2、串的鏈式存儲構造線性鏈表，element類型為char，自第一個元素開始，依次存儲字符串中的每一個字符。2、串的鏈式存儲‘i’

‘n’

‘a’∧‘C’

‘h’

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

‘C’‘￠’‘￠’‘￠’∧str2假設地址量（link）占用2個字節(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數組(ARRAY)2.6.1抽象數據型數組●數組是由下標（index）和值（value）組成的序對（index，value）的集合?！褚部梢远x為是由相同類型的數據元素組成有限序列。●數組在內存中是采用一組連續(xù)的地址空間存儲的，正是由于此種原因，才可以實現下標運算?！袼袛到M都是一個一維向量。數組1：(a1,a2,a3,···,ai,···,an);數組2：(a11,···,a1n,a21,···,a2n,···,aij,···,am1,···,amn);1≤i≤m,1≤j≤n;數組3:(a111,···,a11n,a121,···,a12n,···,aijk,···,amn1,···,am