数据结构课件

《數據結構》

第一章：緒論

什麼是數據結構基本概念和術語演算法和演算法分析1.1什麼是數據結構電腦解題的步驟提出問題（目標函數）→建模→設計演算法→

編程→調試→結果建模的實質提取操作對象→找出對象間的關係→數學語言描述例：數值計算問題圓的面積（函數）應力分析（線性方程組）人口增長預報（微分方程）例：非數值計算問題書目檢索自動化（表）人機對弈（樹）交通燈管理（圖）什麼是數據結構

數據結構是一門研究非數值計算的程式設計中電腦的操作對象以及它們之間的關係和操作等的學科。1.2基本概念和術語

數據：符號的總稱（數、串、圖象和聲音等）。數據元素：數據的基本單位（一本書、一個學生、一個班級、一個年級和一個學校等）。數據對象：性質相同的數據元素的集合（整數集、字母集等）數據結構：相互間存在某種特定關係的數據元素的集合，這種數據元素之間的關係稱為結構。

四種基本結構：集合（鬆散）、線性（一對一）、樹型（一對多）、圖狀或網狀（多對多）。

形式定義：Data_Structure=(D,S)

其中：D是數據元素的有限集。

S是D上關係的有限集。

1.2基本概念和術語例:

複數:Complex=(C,R)

課題小組:Group=(P,R)邏輯結構:

關係存儲結構:

表示(映象)(在高級語言層次上)

順序:位置相鄰(一維數組)

鏈式:指針(指針或數組)計算設計:

取決於選定的邏輯結構演算法實現:

依賴於採用的存儲結構1.2基本概念和術語數據類型:刻畫了操作對象的特性規定:值的集合和一組操作

(整數的範圍:(16位)-32768～32767

操作：+、-、*、DIV、%）

抽象數據類型（ADT）：數學模型和一組操作。（“抽象”的定義在於數據類型的數學抽象特性）

分類：原子類型：100整數。固定聚合類型：複數（C1，C2）。可變聚合類型：有序整數類型。

抽象數據類型的形式定義：

ADT=（D，S，P）其中：D是數據對象；S是D上的關係集；P是對D的基本操作集。（用類C作為描述工具，來討論數據結構及其演算法）1.3演算法和演算法分析演算法：解題步驟的描述，指令的有限序列。演算法的特性：有窮性、確定性、可行性、輸入、輸出。演算法評價標準：可讀性、健壯性、效率（時間、空間）

（前提：正確性：（1）無語法錯誤（2）隨意數據（3）刻意數據（4）一切合法數據）演算法效率的度量：

（1）事後統計法（2）事前估算法（最大語句頻度）1.3演算法和演算法分析時間複雜度：T（n）=O（f（n））

例：for(i=1;i<=n;i++)n+1for(j=1;j<=n;j++)n*(n+1){c[i][j]=0;n*nfor(k=1;k<=n;k++)n*n*(n+1)c[i][j]+=a[i][k]*b[k][j];n*n*n}T(n)=2n3+3n2+2n+1=O(n3)

（漸近時間複雜度、平均時間複雜度、最壞情況下的時間複雜度）空間複雜度：S（n）=O（f（n））練習題1.下列是幾種用二元組表示的數據結構，畫出它們分別對應的邏輯圖形表示，並指出它們分別屬於何種結構。

（1）A=（K，R）其中：K={a，b，c，d，e}；R={r}；

r={<a,b>,<b,c>,<c,d>,<d,e>}

（2）C=(K,R)其中:K={1,2,3,4};R={r};r={(1,2),(1,3),(2,4),(3,4)}2.指出下列各演算法的時間複雜度。

（1）i=1;while(i<=n)i=i*3;

（2）fact(intn){if(n<=1)return(1);elsereturn(n*fact(n-1));}參考答案：(1)abcd

(2)①②③

④2.Log3nT(n)=O(1)+T(n-1)=2*O(1)+T(n-2)……=(n-1)*O(1)+T(1)=n*O(1)=O(n)第二章線性表線性表的類型定義線性表的順序表示和實現線性表的鏈式表示和實現一元多項式的表示和相加2.1線性表的類型定義線性結構的特點：除第一個元素沒有直接前驅和最後一個元素沒有直接後繼之外，其他元素只有一個直接前驅和只有一個後繼。例：線性表、棧和佇列、串。線性表：n個數據元素的有限序列。（a1,a2,a3,……,an）其中：ai可以是數、字元和記錄等。抽象數據結構類型線性表的定義（除上述11種基本操作之外，還可是：合併、拆分和複製等）例：A=（1，2，3）B=（2，3，4，5）

A∪B=（2，3）2.2線性表的順序表示和實現線性表的順序表示:是指用一組地址連續的存儲單元依次存放數據元素。元素的存儲位置關係式:Loc(ai)=Loc(a1)+(i-1)*l

由公式可見，線性表的順序存儲結構是一種隨機存取的存儲結構。由於數組類型具有上述特性，所以，通常用數組來描述順序存儲結構。線性表的基本操作:

插入:

前：（a1,a2,…,ai-1,ai,…,an）表長：n

後：（a1,a2,…,ai-1,x,ai,…,an

）表長：n+1

（向後移動數據元素，以保證“位置相鄰”來體現數據元素的順序關係。）

2.2線性表的順序表示和實現順序表的存儲結構

#defineLIST_INIT_SIZE100#defineLISTINCREAMENT10typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;2.2線性表的順序表示和實現StatusListInsert_sq(Sqlist&L,inti,ElemTypee){if(i<1||i>L.length+1)returnERROR;if(L.length>=L.listsize){newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=e;++L.length;returnOK;}2.2線性表的順序表示和實現刪除:

前：（a1,a2,…,ai-1,ai,…,an）表長：n

後：（a1,a2,…,ai-1,ai+1,…,an

）表長：n-1（向前移動數據元素，以保證“位置相鄰”來體現數據元素的順序關係。）StatusListDelete_sq(Sqlist&L,inti,ElemType&e){if((i<1)||(i>L.length))returnERROR;p=&(L.elem[i-1]);e=*p;q=L.elem+L.length-1;for(++p;p<=q;++p)*(p-1)=*p;--L.length;returnOK;}2.2線性表的順序表示和實現查找：intLocateElem_sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){i=1;p=L.elem;while((i<=L.length)&&!(*compare)(*p++,e))++i;if(i<=L.length)returni;elsereturn0;}2.2線性表的順序表示和實現公式:(移動數據元素的平均次數)Eins=1/(n+1)*(n+(n-1)+…+2+1+0)=n/2Edel=1/n*((n-1)+(n-2)+…+2+1+0)=(n-1)/2

在順序存儲結構的線性表中插入和刪除一個數據元素，平均移動表中一半元素。若表長為n，則演算法ListInsert_sq和ListDelete_sq的時間複雜度為O（n）。特點：優點：直觀、隨機存取。缺點：插入、刪除時，需大量移動數據元素。2.3線性表的鏈式表示和實現為彌補上述存儲結構的不足，引入鏈式存儲結構。線性表的鏈式表示：用一組任意的存儲單元存放數據元素。鏈表：動態鏈表：用指針來實現（單鏈表、雙鏈表、迴圈鏈表等）。靜態鏈表：用數組來實現。單鏈表：建立、查找、插入和刪除。雙鏈表：插入、刪除。迴圈鏈表：合併。2.3線性表的鏈式表示和實現單鏈表的結構

datanextL∧La1a2…an∧

（帶頭結點的空表）（帶頭結點的非空表）

頭結點的作用：對空表和非空表、第一元素和非第一元素作統一處理。

typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;2.3線性表的鏈式表示和實現單鏈表的建立

VoidCreateList_L(LinkList&L,intn){L=(LinkList)malloc(sizeof(Lnode));L->next=NULL;for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(Lnode));scanf(&p->data);p->next=L->next;L->next=p;}}

2.3線性表的鏈式表示和實現單鏈表的查找

StatusGetelem_L(LinkListL,inti,ElemType&e){p=L->next;j=1;while(p&&j<i){p=p->next;++j;}if(!p||j>i)returnERROR;e=p->data;returnOK;}

(練習:查找結點數據為e的結點位置i)2.3線性表的鏈式表示和實現單鏈表的插入

p

ab

②

①se

s=(LinkList)malloc(sizeof(Lnode));s->data=e;①

s->next=p->next;②p->next=s(思考題：①②順序顛倒會怎樣？)2.3線性表的鏈式表示和實現單鏈表的刪除

q

…p

abc…q=p->next;

p->next=q->next;

e=q->data;free(q)練習題:1、編寫一演算法，實現在單鏈表中刪除多餘值相同的結點。

VoidDelval_L(LinkList&L){p=L;while(p<>NULL&&p->next<>NULL)

{q=p;r=p->next;while(r<>NULL){if(p->data=r->data){q->next=r->next;free(r);r=q->next;}else{q=r;r=r->next;}}p=p->next;

}}練習題:2、編寫一演算法,將帶頭結點的單鏈表倒置.

VoidInvertLinkList_L(LinkList&L){p=L->next;L->next=NULL;while(p){s=p;p=p->next;s->next=L->next;L->next=s;}}2.3線性表的鏈式表示和實現雙鏈表的插入

p…ab…

①②④③

se

s=(DLinkList)malloc(sizeof(DLnode));s->data=e;①s->prior=p->prior;②p->prior->next=s;③s->next=p;④p->prior=s;2.3線性表的鏈式表示和實現雙鏈表的插入(在p的後面插入)

s=(DLinkList)malloc(sizeof(DLnode));s->data=e;①s->prior=p;②s->next=p->next;③p->next->prior=s;④p->next=s;2.3線性表的鏈式表示和實現雙鏈表的刪除

①p…abc…

②

e=p->data;①p->prior->next=p->next;②p->next->prior=p->prior;

free(p);2.3線性表的鏈式表示和實現迴圈鏈表的合併

…A

p…B

Ap=A->next;A->next=B->next->next;B->next=p;A=B;2.3線性表的鏈式表示和實現靜態鏈表：用數組描述的鏈表。onedatacur01

#defineMAXSIZE1001a2typedefinestruct2b3{ElemTypedata;3cNULLintcur;two4x5}compoment,SLinkList[MAXSIZE];5y66m7

注：one是個帶頭結點的單鏈表7n4two是個單迴圈鏈表.2.4一元多項式的表示和相加一元多項式的數學表示：

pn(x)=p0+p1x+p2x2+…+pnxn一元多項式的線性表表示：

p=(p0,p1,p2,…,pn)

其中：每一項的指數i隱含在係數pi的序號裏。一元多項式的存儲結構（可採用順序結構或鏈式結構）2.4一元多項式的表示和相加利用線性鏈表的基本操作來實現一元多項式的運算

A-1703198517∧

B-181227-98∧C-170111227517∧上機實習題一元多項式的相加（單鏈表表示）。約瑟夫問題：（用迴圈鏈表做）

n個人圍成一圈，從第s個開始數1,2,3,…,數到m個則退出。然後從下一個重新開始數，依次重複，直到最後一個人退出為止。將上面兩個練習題上機驗證一下。第3章棧和佇列棧棧的應用舉例棧與遞歸的實現佇列3.1棧棧的定義

是限定僅在表尾進行插入或刪除操作的線性表，又稱為後進先出(LastInFirstOut,LIFO)的線性表。出棧進棧棧頂an

…

棧底a1棧的表示和實現

順序棧:利用一組地址連續的存儲單元依次存放自棧底到棧頂的數據元素,同時附設指針top指示棧頂元素在順序棧中的位置.

3.1棧順序棧的存儲結構

#defineSTACK_INIT_SIZE100#defineSTACKINCRAMENT10typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;

例:棧空:棧滿

:topEDCBtopbaseAbase

注：若base的值為NULL，則表明棧結構不存在。若top=base可作為棧空的標誌。通常，插入新的棧頂元素時，指針top增1,刪除棧頂元素時，指針top減1。因此，非空棧中的棧頂指針始終在棧頂元素的下一個位置上。3.1棧進棧：

statuspush(sqstack&s,selemtypee){if(s.top-s.base>=s.stacksize){s.base=(elemtype*)realloc(s.base,(s.stacksize+stackincrement)+sizeof(elemtype));if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=stackincrement;}

*s.top++=e;return(OK);}3.1棧出棧：Statuspop(sqstack&s,selemtype&e){if(s.top==s.base)returnERROR;

e=*--s.top;returnOK;}鏈棧:用鏈式存儲結構來表示棧。

top

…

∧

3.2棧的應用舉例數制轉換運算式求值例：

(25)10=(31)8Voidconversion(){Initstack(s);scanf(“%d”,&n);while(n)top3{Push(s,n%8);n=n/8;}top11topwhile(!Stackempty)(a)(b)(c){Pop(s,e);printf(“%d”,e);}}3.2棧的應用舉例例：計算

3*（7-2）

步驟OPTR棧OPND棧輸入字元主要操作

1#3*（7-2）#PUSH（OPND，‘3’）

2#3*（7-2）#PUSH（OPTR，‘*’）

3#*3（7-2）#PUSH（OPTR，‘（’）

4#*（37-2）#PUSH（OPND，‘7’）

5#*（37-2）#PUSH（OPTR，‘-’）

6#*（-372）#PUSH（OPND，‘2’）

7#*（-372）#operate(‘7’,’-’,’2’)8#*(35)#POP(OPTR)9#*35#operate(‘3’,‘*’,‘5’)10#15#return(GETTOP(OPND))3.2棧的應用舉例Operandtypeevaluateexpression(){Initstack(OPTR);Push(OPTR,‘#’);Initstack(OPND);c=getchar();while(c!=‘#’||Gettop(optr!=‘#’)){if(!In(c,OP)){Push(OPND,c);c=getchar();}elseswitch(Precede(Gettop(OPTR),c)){case‘<’:Push(OPTR,c);c=getchar();break;case‘=’:Pop(OPTR,x);c=getchar();break;case‘>’:Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}}returnGettop(OPND);}3.3棧與遞歸的實現遞歸的定義：一個函數、過程或數據結構（如廣義表、樹等），若在它們定義的內部又出現有本身的應用，則稱它們是遞歸的，或者是遞歸定義的。

例：自然數的集合（1）1是自然數（2）一個自然數的後繼是一個自然數。遞歸的條件：複雜簡單終結

例：

1n=0n!=n*(n-1)!n>03.3棧與遞歸的實現n!的遞歸程序及內部實現

main()Voidfact1(intn,int&r){…①{if(n==0)fact1(3,f)

②r=1;i:…③else{fact1(n-1,w);}④r=n*w;}⑤}3.3棧與遞歸的實現

執行語句標號運行棧的狀態（返址、n、r、w）

01(i3&f-)1,32(42&w1-)1(i3&f-)1,33(41&w2-)2(42&w1-)1(i3&f-)1,34(40&w3-)3(41&w2-)2(42&w1-)1(i3&f-)1,23(41&w2

1)2(42&w1-)1(i3&f-)4,52(42&w1

1)1(i3&f-)4,51(i3&f2)3.3棧與遞歸的實現遞歸與非遞歸的轉換

voidfact2(intn,int&r){top=1;st[1]=n;while(st[top]>1){top++;st[top]=st[top-1]-1;}r=1;while(top>0){r=st[top]*r;top--;}}練習題:一個棧的入棧序列是a,b,c,d,e,，則棧的不可能序列是：

(A)edcba(B)decba(C)dceab(D)abcde判定一個棧ST（最多元素為m0）為空的條件是？為滿的條件是？

棧空的條件：ST->top=0

棧滿的條件：ST->top=m0練習題:指出下列程式的功能

voidreverse(){scanf(“%c”,&ch);if(ch!=‘.’){reverse;printf(“%c”,ch);}}練習題:McCathy函數定義如下：

M(x)=x-10x>100M(M(x+11))x≤100（1）編寫一個遞歸函數計算給定x的M(x)值。（2）編寫一個非遞歸函數計算給定x的M(x)值。intm(intx){inty;if(x>100)return(x-10);else{y=m(x+11);return(m(y));}}intm1(intx){intlevel=1,y;if(x>100)return(x-10);else{level++;y=x+11;}while(level>0){if(y>100){level--;y=y-10;}else{level++;y=y+11;}}return(y);}3.4佇列佇列的定義：

是一種先進先出(FirstInFirstOut,FIFO)的線性表，只允許在表的一端進行插入，而在另一端刪除元素。佇列的表示和實現

出佇列a1a2a3…an

入隊列隊頭隊尾

順序佇列:用一維數組表示的佇列。鏈佇列:用鏈表表示的佇列。迴圈佇列:將順序佇列臆造為一個環狀的空間。3.4佇列datanextQ.front頭結點隊頭

…Q.rear^隊尾單鏈佇列的存儲結構：TypedefstructQnodetypedefstruct{Qelemtypedata;{Queueptrfront;structQnode*next;Queueptrrear;}Qnode,*Queueptr;}Linkqueue;鏈佇列：入隊：StatusEnqueue(Linkqueue&Q,Qelemtypee){p=(Queueptr)malloc(sizeof(Qnode));if(!p)exit(OVERFLOW);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}出隊：StatusDequeue(LinkQueue&Q,Qelemtype&e){if(Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);returnOK;}3.4佇列迴圈佇列：

maxsize-1…0

Q.rear…1

Q.front隊空：Q.front=Q.rear隊滿:(Q.rear+1)%maxsize=Q.front3.4佇列迴圈佇列的順序存儲結構：

#defineMAXSIZE100typedefstruct{Qelemtype*base;intfront;intrear;}SeQueue;入隊：StatusEnqueue(SeQueue&Q,Qelemtypee){if((Q.rear+1)%MAXSIZE==Q.front)returnERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXSIZE;returnOK;}出隊：StatusDequeue(SeQueue&Q,Qelemtype&e){if(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXSIZE;returnOK;}練習題:上機實習題迷宮求解八皇后問題迷宮求解基本思路：從迷宮入口點(1,1)出發，向四周搜索，記下所有能一步通達的座標點，依次進行下去，直至到達迷宮出口點(m,n)為止。這樣就找到了從入口到出口的一條最短路徑。需要解決的幾個問題：（1）如何表示迷宮？（二維數組，0：表示通；1：表示不通）（2）如何從某一座標點出發搜索其四周的鄰點？（v:8個方向）

i=x+move[v].xy=y+move[v].y

（3）如何存儲搜索路徑？（佇列）

(北)(x-1,y-1)(x-1,y)(x-1,y+1)(西)(x,y-1)(x,y)(x,y+1)(東)(x+1,y-1)(x+1,y)(x+1,y+1)

(南)Sq[i]:xypre11102221(1,1)front33324312(2,2)(2,4)5343rear6243(3,1)(3,3)(3,4)…

#include<stdio.h>#definem8#definen10Structsqtype{intx,y,pre;}sq[200];intmg[m+1][n+1];Structmtype{intx;inty;}move[8];

Voidprint(intrear){inti;i=rear;do{printf(“%d,%d”,sq[i].x,sq[i].y);i=sq[i].rear;}while(i!=0)}Voidmglj(){inti,j,x,y,k,front,rear,find;sq[1].x=1;sq[1].y=1;sq[1].pre=0;find=0;front=1;rear=1;mg[1][1]=-1;While(front<=rear&&!find){x=sq[front].x;y=sq[front].y;for(k=1;k<=8;k++)

{i=x+move[k].x;j=y+mov[k].y;if(mg[i][j]==0){rear++;sq[rear].x=i;sq[rear].y=j;sq[rear].pre=front;mg[i][j]=-1;}if(i==m&&j==n){print(rear);find=1;}

}front++;}if(!find)printf(“不存在路徑：\n”);}第四章串串及其運算串的存儲結構串基本運算的實現串的應用4.1串及其運算串是一種特殊的線性表，它的結點僅有一個字元組成。它在文字編輯、詞法掃描、符號處理和定理證明等領域有廣泛的應用。串的定義

串：是由零個或多個字元組成的有限序列。一般記為：S=‘a1,a2,…,an’n≥0

串名串值其中：ai可以是字母、數字或其他字元。

長度：串中字元的數目。

空串：長度為零的串。例：‘’

空格串：由一個或多個空格組成的串。例：‘’

主串：包含子串的串。例：‘abcde’

子串：主串中的任意個連續的字元組成的子序列。例：‘bcd’4.1串及其運算

位置：字元在序列中的序號。串相等：當且僅當這兩個串的值相等。（長度相等；各個對應位置的字元相等。）

(在程式中通常使用的有串常量和串變數)4.1串及其運算串的一般表示（大寫字母表示串S；小寫字母表示組成串的字元）例：S1=‘a1,a2,…,am’S2=‘b1,b2,…,bn’串的基本運算⑴賦值（=或ASSIGN(S,T)）：

例:S=‘abc’S=T⑵聯接(+或concat(S,T))

例:S1+S2=‘a1,a2,…,amb1,b2,…,bn’concat(S1,S2)4.1串及其運算串的基本運算⑶

求串長(Length(S))

例:Length(S1)=mLength(‘abc’)=3Length(‘’)=0Length(‘’)=1⑷求子串(Substr(S,i,j))

例:Substr(S1,i,j)=‘ai,ai+1,…,ai+j-1’⑸串比較(Strcmp(S,T))S<T-1S=T0S>T14.1串及其運算串插入(Insert(S1,i,S2))

Inseert(S1,i,S2)=Substr(S1,1,i)+S2+Substr(S1,i+1,Length(S1)-i)串刪除(Delete(S1,i,j))

Delete(S1,i,j)=Substr(S1,1,i-1)+Substr(S1,i+j,Length(S1)-(i+j-1))求子串位置(Index(S1,S2))

Index(‘abcdef’,‘cde’)=3串置換(Replace(S1,i,j,S2))

Replace(S1,i,j,S2)=Substr(S1,1,i-1)+S2+Substr(S1,i+j,Length(S1)-(i+j-1))4.2串的存儲結構串的三種機內表示

順序存儲：用一組地址連續的存儲單元存儲串值的字元序列。（在做插入、置換和聯接操作時，可能產生超界。）

堆分配存儲：仍以一組地址連續的存儲單元存儲串值的字元序列。但它們的存儲空間是在程式執行過程中動態分配而得。（較好的克服上述弊病。）

塊鏈存儲：用鏈式方式存儲串值。除設頭指針外，還設一個尾指針，並給出當前串的長度。4.3串基本運算的實現串聯接:(順序存儲)Statusconcat(Sstring&T,SstringS1,SstringS2){if(S1[0]+S2[0]<=MAXSTRLEN){T[1..s1[0]]=S1[1..S1[0]];T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]];T[0]=S1[0]+S2[0];uncut=TRUE;}elseif(S1[0]<MAXSTRSIZE){T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]];T[0]=MAXSTRLEN;uncut=FALSE;}else{T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];uncut=FALSE;}returnuncut;}4.3串基本運算的實現求子串：（順序存儲）StatusSubString(Sstring&Sub,SstringS,intpos,intlen){if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)returnERROR;Sub[1..len]=S[pos..pos+len-1];Sub[0]=len;returnOK;}4.3串基本運算的實現串聯接：（堆分配存儲）StatusConcat(Hstring&T,HStringS1,HstringS2){if(T.ch)free(T.ch);if(!(T.ch=(char*)malloc((S1.length+S2.length)*sizeof(char))))exit(OVERFLOW);T.ch[0..s1.length-1]=S1.ch[0..s1.length-1];T.length=S1.length+S2.length;T.ch[S1.length..T.length-1]=S2.ch[0..S2.length-1];returnOK;}4.3串基本運算的實現求子串：（堆分配存儲）StatusSubString(Hstring&Sub,HstringS,intpos,intlen){if(pos<1||pos>S.length||len<0||len>S.length-pos+1)returnERROR;if(Sub.ch)free(Sub.ch);if(!len){Sub.ch=NULL;Sub.length=0;}else{Sub.ch=(char*)malloc(len*sizeof(char));Sub.ch[0..len-1]=S[pos-1..pos+len-2];Sub.length=len;}returnOK;}4.3串基本運算的實現模式匹配演算法

模式匹配：子串的定位操作。（其中子串T為模式串））傳統匹配方法：從主串S的第一個字元起和模式串T的第一個字元比較之，若相等，則繼續逐個比較後續字元。否則從主串的第二個字元起再重新和模式串的字元比較，依次類推，直至模式串中的每個字元依次和主串中的一個連續的字元序列相等。

(p80—圖4.3)

4.3串基本運算的實現

intindex(SstringS,SstringT,intpos){i=pos;j=1;while(i<=s[0]&&j<=T[0]){if(S[i]==T[j]){++i;++j;}else{i=i-j+2;j=1;}}if(j>T[0])returni-T[0];elsereturn0;注：S[0]、T[0]分別為S、T串的長度。

}pos初始值為1。4.3串基本運算的實現KMP匹配方法（無回朔）：每當一趟匹配過程中出現字元不等時，不需回朔i指針，而是利用已經得到的“部分匹配”結果將模式向右“滑動”盡可能遠的一段距離後，繼續進行比較。(該法由克努特-莫裏斯-普拉特同時發現，所以稱為KMP方法。)Next函數的計算

0當j=1時

Next[j]=Max{k|1<k<j且’p1…pk-1’=‘pj-k+1…pj-1’}1其他情況例：abaab01122(p80—圖4.5)練習題:根據模式串的next函數的定義，推出下列模式串的next[i]函數值。例：aaabcd若S和T是用結點大小為1的單鏈表存儲的兩個串，設計一個演算法將串S中首次與串T匹配的子串逆置。參考答案：

011311inverseLink(LinkList&S,LinkListT){ps=qs=S->next;rs=S;pt=T;while(ps&&pt)

{if(ps->data==pt->data){ps=ps->next;pt=pt->nexty;}else{rs=qs;qs=qs->next;ps=qs;pt=T;}if(pt==NULL){p=qs;while(p!=ps){q=p;p=p->next;q->next=rs->next;rs->next=q;}qs->next=ps;}

}}上機實習題建立詞索引表（詞典有序），並將生成的詞索引表輸出。

基本要求：直接輸入關鍵字和書號，生成詞索引表。生成詞索引表後，輸入一關鍵字，則輸出其有關書號。

較高要求：從書目檔中生成詞索引表，並輸出到檔中和螢幕上。生成詞索引表後，輸入一關鍵字，則輸出其有關書號。（判斷關鍵字，必須與常用詞表中的常用詞進行比較，不是常用詞（an,a,of,the,to等），則為關鍵字。）第五章數組和廣義表多維數組矩陣的壓縮存儲廣義表

（多維數組和廣義表則是一種複雜的非線性結構，它的邏輯特徵是一個數據元素可能有多個直接前驅和直接後繼。）5.1多維數組多維數組

是向量的推廣。對於二維數組，可以看成是由m個行向量組成的向量，也可以看成是由n個列向量組成的向量。

a11a12…a1nAm*n=a21a22…a2n

…am1am2…amn

（二維數組中的每個元素aij均屬於兩個向量，第i行的行向量和第j列的列向量。）5.1多維數組數組的操作

通常有兩種：（1）給定一組下標，存取相應的數組元素。（2）給定一組下標，修改相應數據元素的某一個或幾個數據項的值。數組的順序存儲結構由於電腦記憶體結構是一維的，因此，用一維的記憶體來存放多維數組的數據元素，就必須按某種次序將數組元素排成一個線性序列，然後將這個線性序列順序存放在記憶體中。通常有兩種順序存儲方式：（1）按行優先：a11,a12,…,a1n,a21,a22,…,amm

（2）按列優