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

《數(shù)據(jù)結(jié)構(gòu)》

第一章：緒論

什麼是數(shù)據(jù)結(jié)構(gòu)基本概念和術(shù)語演算法和演算法分析1.1什麼是數(shù)據(jù)結(jié)構(gòu)電腦解題的步驟提出問題（目標(biāo)函數(shù)）→建模→設(shè)計(jì)演算法→

編程→調(diào)試→結(jié)果建模的實(shí)質(zhì)提取操作對(duì)象→找出對(duì)象間的關(guān)係→數(shù)學(xué)語言描述例：數(shù)值計(jì)算問題圓的面積（函數(shù)）應(yīng)力分析（線性方程組）人口增長預(yù)報(bào)（微分方程）例：非數(shù)值計(jì)算問題書目檢索自動(dòng)化（表）人機(jī)對(duì)弈（樹）交通燈管理（圖）什麼是數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程式設(shè)計(jì)中電腦的操作對(duì)象以及它們之間的關(guān)係和操作等的學(xué)科。1.2基本概念和術(shù)語

數(shù)據(jù)：符號(hào)的總稱（數(shù)、串、圖象和聲音等）。數(shù)據(jù)元素：數(shù)據(jù)的基本單位（一本書、一個(gè)學(xué)生、一個(gè)班級(jí)、一個(gè)年級(jí)和一個(gè)學(xué)校等）。數(shù)據(jù)對(duì)象：性質(zhì)相同的數(shù)據(jù)元素的集合（整數(shù)集、字母集等）數(shù)據(jù)結(jié)構(gòu)：相互間存在某種特定關(guān)係的數(shù)據(jù)元素的集合，這種數(shù)據(jù)元素之間的關(guān)係稱為結(jié)構(gòu)。

四種基本結(jié)構(gòu)：集合（鬆散）、線性（一對(duì)一）、樹型（一對(duì)多）、圖狀或網(wǎng)狀（多對(duì)多）。

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

其中：D是數(shù)據(jù)元素的有限集。

S是D上關(guān)係的有限集。

1.2基本概念和術(shù)語例:

複數(shù):Complex=(C,R)

課題小組:Group=(P,R)邏輯結(jié)構(gòu):

關(guān)係存儲(chǔ)結(jié)構(gòu):

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

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

鏈?zhǔn)?指針(指針或數(shù)組)計(jì)算設(shè)計(jì):

取決於選定的邏輯結(jié)構(gòu)演算法實(shí)現(xiàn):

依賴於採用的存儲(chǔ)結(jié)構(gòu)1.2基本概念和術(shù)語數(shù)據(jù)類型:刻畫了操作對(duì)象的特性規(guī)定:值的集合和一組操作

(整數(shù)的範(fàn)圍:(16位)-32768～32767

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

抽象數(shù)據(jù)類型（ADT）：數(shù)學(xué)模型和一組操作。（“抽象”的定義在於數(shù)據(jù)類型的數(shù)學(xué)抽象特性）

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

抽象數(shù)據(jù)類型的形式定義：

ADT=（D，S，P）其中：D是數(shù)據(jù)對(duì)象；S是D上的關(guān)係集；P是對(duì)D的基本操作集。（用類C作為描述工具，來討論數(shù)據(jù)結(jié)構(gòu)及其演算法）1.3演算法和演算法分析演算法：解題步驟的描述，指令的有限序列。演算法的特性：有窮性、確定性、可行性、輸入、輸出。演算法評(píng)價(jià)標(biāo)準(zhǔn)：可讀性、健壯性、效率（時(shí)間、空間）

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

（1）事後統(tǒng)計(jì)法（2）事前估算法（最大語句頻度）1.3演算法和演算法分析時(shí)間複雜度：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)

（漸近時(shí)間複雜度、平均時(shí)間複雜度、最壞情況下的時(shí)間複雜度）空間複雜度：S（n）=O（f（n））練習(xí)題1.下列是幾種用二元組表示的數(shù)據(jù)結(jié)構(gòu)，畫出它們分別對(duì)應(yīng)的邏輯圖形表示，並指出它們分別屬於何種結(jié)構(gòu)。

（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.指出下列各演算法的時(shí)間複雜度。

（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)第二章線性表線性表的類型定義線性表的順序表示和實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)一元多項(xiàng)式的表示和相加2.1線性表的類型定義線性結(jié)構(gòu)的特點(diǎn)：除第一個(gè)元素沒有直接前驅(qū)和最後一個(gè)元素沒有直接後繼之外，其他元素只有一個(gè)直接前驅(qū)和只有一個(gè)後繼。例：線性表、棧和佇列、串。線性表：n個(gè)數(shù)據(jù)元素的有限序列。（a1,a2,a3,……,an）其中：ai可以是數(shù)、字元和記錄等。抽象數(shù)據(jù)結(jié)構(gòu)類型線性表的定義（除上述11種基本操作之外，還可是：合併、拆分和複製等）例：A=（1，2，3）B=（2，3，4，5）

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

由公式可見，線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。由於數(shù)組類型具有上述特性，所以，通常用數(shù)組來描述順序存儲(chǔ)結(jié)構(gòu)。線性表的基本操作:

插入:

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

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

）表長：n+1

（向後移動(dòng)數(shù)據(jù)元素，以保證“位置相鄰”來體現(xiàn)數(shù)據(jù)元素的順序關(guān)係。）

2.2線性表的順序表示和實(shí)現(xiàn)順序表的存儲(chǔ)結(jié)構(gòu)

#defineLIST_INIT_SIZE100#defineLISTINCREAMENT10typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;2.2線性表的順序表示和實(shí)現(xiàn)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線性表的順序表示和實(shí)現(xiàn)刪除:

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

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

）表長：n-1（向前移動(dòng)數(shù)據(jù)元素，以保證“位置相鄰”來體現(xiàn)數(shù)據(jù)元素的順序關(guān)係。）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線性表的順序表示和實(shí)現(xiàn)查找：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線性表的順序表示和實(shí)現(xiàn)公式:(移動(dòng)數(shù)據(jù)元素的平均次數(shù))Eins=1/(n+1)*(n+(n-1)+…+2+1+0)=n/2Edel=1/n*((n-1)+(n-2)+…+2+1+0)=(n-1)/2

在順序存儲(chǔ)結(jié)構(gòu)的線性表中插入和刪除一個(gè)數(shù)據(jù)元素，平均移動(dòng)表中一半元素。若表長為n，則演算法ListInsert_sq和ListDelete_sq的時(shí)間複雜度為O（n）。特點(diǎn)：優(yōu)點(diǎn)：直觀、隨機(jī)存取。缺點(diǎn)：插入、刪除時(shí)，需大量移動(dòng)數(shù)據(jù)元素。2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)為彌補(bǔ)上述存儲(chǔ)結(jié)構(gòu)的不足，引入鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。線性表的鏈?zhǔn)奖硎荆河靡唤M任意的存儲(chǔ)單元存放數(shù)據(jù)元素。鏈表：動(dòng)態(tài)鏈表：用指針來實(shí)現(xiàn)（單鏈表、雙鏈表、迴圈鏈表等）。靜態(tài)鏈表：用數(shù)組來實(shí)現(xiàn)。單鏈表：建立、查找、插入和刪除。雙鏈表：插入、刪除。迴圈鏈表：合併。2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)單鏈表的結(jié)構(gòu)

datanextL∧La1a2…an∧

（帶頭結(jié)點(diǎn)的空表）（帶頭結(jié)點(diǎn)的非空表）

頭結(jié)點(diǎn)的作用：對(duì)空表和非空表、第一元素和非第一元素作統(tǒng)一處理。

typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)單鏈表的建立

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線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)單鏈表的查找

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;}

(練習(xí):查找結(jié)點(diǎn)數(shù)據(jù)為e的結(jié)點(diǎn)位置i)2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)單鏈表的插入

p

ab

②

①se

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

s->next=p->next;②p->next=s(思考題：①②順序顛倒會(huì)怎樣？)2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)單鏈表的刪除

q

…p

abc…q=p->next;

p->next=q->next;

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

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;

}}練習(xí)題:2、編寫一演算法,將帶頭結(jié)點(diǎn)的單鏈表倒置.

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線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)雙鏈表的插入

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線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)雙鏈表的插入(在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線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)雙鏈表的刪除

①p…abc…

②

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

free(p);2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)迴圈鏈表的合併

…A

p…B

Ap=A->next;A->next=B->next->next;B->next=p;A=B;2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)靜態(tài)鏈表：用數(shù)組描述的鏈表。onedatacur01

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

注：one是個(gè)帶頭結(jié)點(diǎn)的單鏈表7n4two是個(gè)單迴圈鏈表.2.4一元多項(xiàng)式的表示和相加一元多項(xiàng)式的數(shù)學(xué)表示：

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

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

其中：每一項(xiàng)的指數(shù)i隱含在係數(shù)pi的序號(hào)裏。一元多項(xiàng)式的存儲(chǔ)結(jié)構(gòu)（可採用順序結(jié)構(gòu)或鏈?zhǔn)浇Y(jié)構(gòu)）2.4一元多項(xiàng)式的表示和相加利用線性鏈表的基本操作來實(shí)現(xiàn)一元多項(xiàng)式的運(yùn)算

A-1703198517∧

B-181227-98∧C-170111227517∧上機(jī)實(shí)習(xí)題一元多項(xiàng)式的相加（單鏈表表示）。約瑟夫問題：（用迴圈鏈表做）

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

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

…

棧底a1棧的表示和實(shí)現(xiàn)

順序棧:利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素,同時(shí)附設(shè)指針top指示棧頂元素在順序棧中的位置.

3.1棧順序棧的存儲(chǔ)結(jié)構(gòu)

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

例:棧空:棧滿

:topEDCBtopbaseAbase

注：若base的值為NULL，則表明棧結(jié)構(gòu)不存在。若top=base可作為棧空的標(biāo)誌。通常，插入新的棧頂元素時(shí)，指針top增1,刪除棧頂元素時(shí)，指針top減1。因此，非空棧中的棧頂指針始終在棧頂元素的下一個(gè)位置上。3.1棧進(jìn)棧：

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;}鏈棧:用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來表示棧。

top

…

∧

3.2棧的應(yīng)用舉例數(shù)制轉(zhuǎn)換運(yùn)算式求值例：

(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棧的應(yīng)用舉例例：計(jì)算

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棧的應(yīng)用舉例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棧與遞歸的實(shí)現(xiàn)遞歸的定義：一個(gè)函數(shù)、過程或數(shù)據(jù)結(jié)構(gòu)（如廣義表、樹等），若在它們定義的內(nèi)部又出現(xiàn)有本身的應(yīng)用，則稱它們是遞歸的，或者是遞歸定義的。

例：自然數(shù)的集合（1）1是自然數(shù)（2）一個(gè)自然數(shù)的後繼是一個(gè)自然數(shù)。遞歸的條件：複雜簡單終結(jié)

例：

1n=0n!=n*(n-1)!n>03.3棧與遞歸的實(shí)現(xiàn)n!的遞歸程序及內(nèi)部實(shí)現(xià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棧與遞歸的實(shí)現(xiàn)

執(zhí)行語句標(biāo)號(hào)運(yùn)行棧的狀態(tài)（返址、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棧與遞歸的實(shí)現(xiàn)遞歸與非遞歸的轉(zhuǎn)換

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--;}}練習(xí)題:一個(gè)棧的入棧序列是a,b,c,d,e,，則棧的不可能序列是：

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

?？盏臈l件：ST->top=0

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

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

M(x)=x-10x>100M(M(x+11))x≤100（1）編寫一個(gè)遞歸函數(shù)計(jì)算給定x的M(x)值。（2）編寫一個(gè)非遞歸函數(shù)計(jì)算給定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佇列佇列的定義：

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

出佇列a1a2a3…an

入隊(duì)列隊(duì)頭隊(duì)尾

順序佇列:用一維數(shù)組表示的佇列。鏈佇列:用鏈表表示的佇列。迴圈佇列:將順序佇列臆造為一個(gè)環(huán)狀的空間。3.4佇列datanextQ.front頭結(jié)點(diǎn)隊(duì)頭

…Q.rear^隊(duì)尾單鏈佇列的存儲(chǔ)結(jié)構(gòu)：TypedefstructQnodetypedefstruct{Qelemtypedata;{Queueptrfront;structQnode*next;Queueptrrear;}Qnode,*Queueptr;}Linkqueue;鏈佇列：入隊(duì)：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;}出隊(duì)：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隊(duì)空：Q.front=Q.rear隊(duì)滿:(Q.rear+1)%maxsize=Q.front3.4佇列迴圈佇列的順序存儲(chǔ)結(jié)構(gòu)：

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

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

（3）如何存儲(chǔ)搜索路徑？（佇列）

(北)(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”);}第四章串串及其運(yùn)算串的存儲(chǔ)結(jié)構(gòu)串基本運(yùn)算的實(shí)現(xiàn)串的應(yīng)用4.1串及其運(yùn)算串是一種特殊的線性表，它的結(jié)點(diǎn)僅有一個(gè)字元組成。它在文字編輯、詞法掃描、符號(hào)處理和定理證明等領(lǐng)域有廣泛的應(yīng)用。串的定義

串：是由零個(gè)或多個(gè)字元組成的有限序列。一般記為：S=‘a(chǎn)1,a2,…,an’n≥0

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

長度：串中字元的數(shù)目。

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

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

主串：包含子串的串。例：‘a(chǎn)bcde’

子串：主串中的任意個(gè)連續(xù)的字元組成的子序列。例：‘bcd’4.1串及其運(yùn)算

位置：字元在序列中的序號(hào)。串相等：當(dāng)且僅當(dāng)這兩個(gè)串的值相等。（長度相等；各個(gè)對(duì)應(yīng)位置的字元相等。）

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

例:S=‘a(chǎn)bc’S=T⑵聯(lián)接(+或concat(S,T))

例:S1+S2=‘a(chǎn)1,a2,…,amb1,b2,…,bn’concat(S1,S2)4.1串及其運(yùn)算串的基本運(yùn)算⑶

求串長(Length(S))

例:Length(S1)=mLength(‘a(chǎn)bc’)=3Length(‘’)=0Length(‘’)=1⑷求子串(Substr(S,i,j))

例:Substr(S1,i,j)=‘a(chǎn)i,ai+1,…,ai+j-1’⑸串比較(Strcmp(S,T))S<T-1S=T0S>T14.1串及其運(yùn)算串插入(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(‘a(chǎn)bcdef’,‘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串的存儲(chǔ)結(jié)構(gòu)串的三種機(jī)內(nèi)表示

順序存儲(chǔ)：用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字元序列。（在做插入、置換和聯(lián)接操作時(shí)，可能產(chǎn)生超界。）

堆分配存儲(chǔ)：仍以一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字元序列。但它們的存儲(chǔ)空間是在程式執(zhí)行過程中動(dòng)態(tài)分配而得。（較好的克服上述弊病。）

塊鏈存儲(chǔ)：用鏈?zhǔn)椒绞酱鎯?chǔ)串值。除設(shè)頭指針外，還設(shè)一個(gè)尾指針，並給出當(dāng)前串的長度。4.3串基本運(yùn)算的實(shí)現(xiàn)串聯(lián)接:(順序存儲(chǔ))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串基本運(yùn)算的實(shí)現(xiàn)求子串：（順序存儲(chǔ)）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串基本運(yùn)算的實(shí)現(xiàn)串聯(lián)接：（堆分配存儲(chǔ)）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串基本運(yùn)算的實(shí)現(xiàn)求子串：（堆分配存儲(chǔ)）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串基本運(yùn)算的實(shí)現(xiàn)模式匹配演算法

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

(p80—圖4.3)

4.3串基本運(yùn)算的實(shí)現(xiàn)

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串基本運(yùn)算的實(shí)現(xiàn)KMP匹配方法（無回朔）：每當(dāng)一趟匹配過程中出現(xiàn)字元不等時(shí)，不需回朔i指針，而是利用已經(jīng)得到的“部分匹配”結(jié)果將模式向右“滑動(dòng)”盡可能遠(yuǎn)的一段距離後，繼續(xù)進(jìn)行比較。(該法由克努特-莫裏斯-普拉特同時(shí)發(fā)現(xiàn)，所以稱為KMP方法。)Next函數(shù)的計(jì)算

0當(dāng)j=1時(shí)

Next[j]=Max{k|1<k<j且’p1…pk-1’=‘pj-k+1…pj-1’}1其他情況例：abaab01122(p80—圖4.5)練習(xí)題:根據(jù)模式串的next函數(shù)的定義，推出下列模式串的next[i]函數(shù)值。例：aaabcd若S和T是用結(jié)點(diǎn)大小為1的單鏈表存儲(chǔ)的兩個(gè)串，設(shè)計(jì)一個(gè)演算法將串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;}

}}上機(jī)實(shí)習(xí)題建立詞索引表（詞典有序），並將生成的詞索引表輸出。

基本要求：直接輸入關(guān)鍵字和書號(hào)，生成詞索引表。生成詞索引表後，輸入一關(guān)鍵字，則輸出其有關(guān)書號(hào)。

較高要求：從書目檔中生成詞索引表，並輸出到檔中和螢?zāi)簧稀Ｉ稍~索引表後，輸入一關(guān)鍵字，則輸出其有關(guān)書號(hào)。（判斷關(guān)鍵字，必須與常用詞表中的常用詞進(jìn)行比較，不是常用詞（an,a,of,the,to等），則為關(guān)鍵字。）第五章數(shù)組和廣義表多維數(shù)組矩陣的壓縮存儲(chǔ)廣義表

（多維數(shù)組和廣義表則是一種複雜的非線性結(jié)構(gòu)，它的邏輯特徵是一個(gè)數(shù)據(jù)元素可能有多個(gè)直接前驅(qū)和直接後繼。）5.1多維數(shù)組多維數(shù)組

是向量的推廣。對(duì)於二維數(shù)組，可以看成是由m個(gè)行向量組成的向量，也可以看成是由n個(gè)列向量組成的向量。

a11a12…a1nAm*n=a21a22…a2n

…am1am2…amn

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

通常有兩種：（1）給定一組下標(biāo)，存取相應(yīng)的數(shù)組元素。（2）給定一組下標(biāo)，修改相應(yīng)數(shù)據(jù)元素的某一個(gè)或幾個(gè)數(shù)據(jù)項(xiàng)的值。數(shù)組的順序存儲(chǔ)結(jié)構(gòu)由於電腦記憶體結(jié)構(gòu)是一維的，因此，用一維的記憶體來存放多維數(shù)組的數(shù)據(jù)元素，就必須按某種次序?qū)?shù)組元素排成一個(gè)線性序列，然後將這個(gè)線性序列順序存放在記憶體中。通常有兩種順序存儲(chǔ)方式：（1）按行優(yōu)先：a11,a12,…,a1n,a21,a22,…,amm

（2）按列優(yōu)