數(shù)據(jù)結構實驗規(guī)范標準答案

1、!-數(shù)據(jù)結構實驗指導2013/ 2014學年第2學期名:t=r.號:級:指導教師:濰坊學院計算機工程學院2014預備實驗C語言的函數(shù)數(shù)組指針結構體知識、實驗目的1、復習C語言中函數(shù)、數(shù)組、指針和結構體的概念。2、熟悉利用C語言進行程序設計的一般方法。二、實驗內容和要求1、調試程序：輸出100以內所有的素數(shù)(用函數(shù)實現(xiàn))。#in clude<stdio.h>/*判斷一個數(shù)是否為素數(shù)*/int isp rime(i nt n)for(i nt m=2;m*m <=n ;m+)if(n %m= =0) return 0; return 1;/*輸出100以內所有素數(shù)*/int ma

2、i n()int i;for(i=2;i<100;i+)“4d' ,i);if(is prime(i)= =1) printf(return 0;運行結果:VI755? 11 IJ 17 IV*1 +JS? «n IJt7Priii1a -inv hihv L樸 nmH2、調試程序：對一維數(shù)組中的元素進行逆序排列。#in clude<stdio.h>#defi ne N 10int mai n()int aN=0,1,2,3,4,5,6,7,8,9,i,tem p;pnntf( the original Array is:n ”； for(i=0;i<

3、N;i+)printf( %4d”ai);*/for(i=0;i<N/2;i+)/*交換數(shù)組元素使之逆序temp=ai;ai=aN-i-1;aN-i-1=te mp;pnntf( hthe changed Array is:n ” for(i=0;i<N;i+)printf( %4d”ai);return 0;運行結果: Iw -"Tr»3f Iv-I» L 工 H F4 ha Eli.r>gKd rv*” xeIT7 t I3、調試程序：在二維數(shù)組中，若某一位置上的元素在該行中最大，而在該列中最小，則該 元素即為該二維數(shù)組的一個鞍點。要求從鍵盤

4、上輸入一個二維數(shù)組，當鞍點存在時，把鞍點找出來。#in clude<stdio.h>#defi ne M 3 #defi ne N 4int mai n()int aMN,i,j,k;printf(請輸入二維數(shù)組的數(shù)據(jù)：n”)；for(i=0;i<M;i+)for(j=0;j<N;j+)scanf( “ d'，&aij);for(i=0;i<M;i+)/* 輸出矩陣 */for(j=0;j<N;j+)printf( “ 4d' ,aij);printf( n”)； for(i=0;i<M;i+)k=0;for(j=1;j<

5、N;j+)/*找出第i行的最大值*/if(aij>aik)k=j;for(j=0;j<M;j+)/*判斷第i行的最大值是否為該列的最小值*/if(ajk<aik)break;/*在第i行找到鞍點*/“d,%d,%”),aik,i,k);if(j=M)printf(return 0;運行結果:訕I(yè)d 強加 Vti 汕 It 4L 7 4 » 4ble1)昭4C7B附IE«.743246iFF-IR 七n* h時Vo-nclRiufi4、調試程序：利用指針輸出二維數(shù)組的元素。#in clude<stdio.h>int mai n()int a34=

6、1,3,5,7,9,11,13,15,17,19,21,23; int *p;for(p=a0; p<a0+12; p+)if(p-a0)%4= =0) printf(n” “printf(%4d”，*p);return 0;運行結果:5、調試程序：輸入10個學生的成績，每個學生成績包括學號、姓名和三門課的成績。要 求打印出三門課的平均成績及成績最高者的姓名和成績。#in clude<stdio.h>#defi ne N 10;struct stude ntchar num6;/*學號 */char name8; /* 姓名 */int score3; /* 成績 */ fl

7、oat avr; /* 平均成績 */stuN;int mai n()int i,j,max,maxi,sum;float average;for(i=0;i<N;i+)/*輸入10個學生的成績信息*/printf( “n請輸入第d學生的成績：n”+1);printf(學號：”seanf( %s",stui.num);printf(姓名”seanf( %s",);for(j=0;j<3;j+)printf(成績 d”+1);scanf( %d ”，&stui.seorej);average=0;max=0;maxi=0;/*計算平均成績

8、，找出成績最高的學生*/for(i=0;i<N;i+)sum=0;for(j=0;j<3;j+)sum+=stui.seorej; stui.avr=sum/3.0; average+=stui.avr; if(sum>max)max=sum;maxi=i;average/=10;printf( “學號 姓名 成績1 成績2 成績3 平均分n); for(i=0;i<10;i+)printf( %8s%10s'',stui.num,); for(j=0;j<3;j+)printf( %7d '',stui.scor

9、ej);printf( %6.2fn ”,stui.avr);printf(平均成績是：%5.2fn ”,average);printf(最好成績的學生是：s,總分是 %d”,,max);return 0;運行結果 li 衛(wèi) 3 G 士 V R 貝皿JDLU呵財塑噩時;珂2 *7.67 *1 M 92,t? tid.t? 恥.n F.flO a»M 73-HW 7ft.-jnnIMa?SV令9*&財K站 艸 W 丹 H M 福"-話評 1 r 1 ff 士 y 3 UH 1 ffu xff 金 F 3 »H _3t£ J

10、奇生彎生“雷屮吋主曙生聶生譏雷"瑞生尋今罷" -費.£-百人-叵人衣八：住二 審人 忌人覺，慮 呂一忖.孑"鳥-名尊-需mjer 一一 _,w S. WiT _左皙若731|"呂fej rd 至宇I;、壤工一話？¥.龍¥弋f .¥亠芋.2$.工*一斗社f |>f =-J ft占hu heM生 毎 二 L-,三、實驗小結C語言進對C語言中函數(shù)、數(shù)組、指針和結構體的概念，有了進一步的加深。并且可以利用 行初步程序設計。四、教師評語實驗順序表與鏈表、實驗目的1、2、3、4、掌握線性表中元素的前驅、后續(xù)的概念。掌握順

11、序表與鏈表的建立、插入元素、刪除表中某元素的算法。 對線性表相應算法的時間復雜度進行分析。理解順序表、鏈表數(shù)據(jù)結構的特點（優(yōu)缺點）。二、實驗內容和要求1、閱讀下面程序，在橫線處填寫函數(shù)的基本功能。并運行程序，寫出結果。#in clude<stdio.h> #in clude<malloc.h>#defi ne ERROR 0#defi ne OK 1 int In itList_sq(Sqlist *L)#defi ne INIT_SIZE 5 /* #defi ne INCREM 5/*typ edef int ElemT ype; /* typ edef struc

12、t SqlistElemT ype *slist;/*int len gth; /* int listsize;Sqlist;/*初始分配的順序表長度 */ 溢出時，順序表長度的增量*/定義表元素的類型*/存儲空間的基地址*/ 順序表的當前長度*/ 當前分配的存儲空間*/int In itList_sq(Sqlist *L); /*int CreateList_sq(Sqlistint ListI nsert_sq(Sqlist *L,i nt i,ElemTy pe e);/* 元素之前插入新的元素e */int Prin tList_sq(Sqlist *L); /*int ListDel

13、ete_sq(Sqlist *L,int i); /*int ListLocate(Sqlist *L,ElemTy pe e); /*初始化順序表L,并將其長度設為0*L,int n）; /*構造順序表的長度為n*/*/在順序線性表L中第i個輸出順序表的元素*/刪除第i個元素*/查找值為e的元素*/L->slist=(ElemTy pe*)malloc(INIT_SIZE*sizeof(ElemTy pe); if(!L->slist) return ERROR;L->le ngth=O;L->listsize=INIT_SIZE;return OK;/*lni tL

14、ist*/ int CreateList_sq(Sqlist *L,i nt n)ElemT ype e;int i;for(i=0;i< n; i+)prin tf("i nput data %d",i+1); scan f("%d", &e);if(!ListI nsert_sq(L,i+1,e) return ERROR;return OK;/*CreateList*/*輸出順序表中的元素*/int Prin tList_sq(Sqlist *L)int i;for(i=1;i<=L->le ngth;i+) prin t

15、f("%5d",L->slisti-1);return OK;/*Prin tList*/int ListI nsert_sq(Sqlist *L,i nt i,ElemT ype e)int k;if(i<1|i> L->le ngth+1)return ERROR;if(L->le ngth>=L->listsize) L->slist=(ElemT yp e*)realloc(L->slist,(INIT_SIZE+INCREM)*sizeof(ElemT yp e);if(!L->slist)return

16、ERROR; L->listsize+=INCREM;for(k=L->le ngth-1;k>=i-1;k-)L->slistk+1=k;L->slisti-1=e;L->le ngth+;return OK;/*ListI nsert*/*在順序表中刪除第i個元素*/int ListDelete_sq(Sqlist *L,i nt i)if(i<1)|(i>L->le ngth) return ERROR; for(p=i-1; p<->le ngth-1; p+)L >slist p =L->slist p +

17、1;L >le ngth-; return OK;/*在順序表中查找指定值元素，返回其序號*/int ListLocate(Sqlist *L,ElemT ype e)int mai n()Sqlist sl;int n;輸入順序表的元素個數(shù)*/prin tf(" pl ease input n:"); /* scan f("%d", &n);if(n >0)prin tf("n1-Create Sqlist:n");In itList_sq(&sl); CreateList_s q(&sl, n)

18、;prin tf("n2-Print Sqlist:n"); Prin tList_sq(&sl);elseprin tf("ERROR"); return 0;算法分析與運行結果pl ease input n:51- Create Sqlist:input data 10input data 25input data 38input data 43input data 562- Print Sqlist:0 5 8 3 6P ress any key to con ti nueinput n *5data (taCadato dataIB?&#

19、163;432-Print主0 E H3bPm士G any I<bto continue2、為第1題補充刪除和查找功能函數(shù)，并在主函數(shù)中補充代碼驗證算法的正確性。 算法代碼：int ListDelete_sq(Sqlist *L,i nt i) int p;if(i<1)|(i>L->le ngth) return ERROR; for(p=i-1; p<L->le ngth-1; p+) L >slist p =L->slist p +1;L->le ngth-;return OK;/*在順序表中查找指定值元素，返回其序號*/int Li

20、stLocate(Sqlist *L,ElemT ype e)int i=0;while(i<=L->le ngth) &&(L->slisti!=e) i+;if(i<=L->le ngth)return(i+1);elsereturn(-1);3、閱讀下面程序，在橫線處填寫函數(shù)的基本功能。并運行程序，寫出結果。#in clude<stdio.h> #in clude<malloc.h>#defi ne ERROR 0#defi ne OK 1typ edef int ElemT ype; /* typ edef stru

21、ct LNode /* ElemT ype data; struct LNode *n ext;LNode,*L in kList;定義表元素的類型*/ 線性表的單鏈表存儲*/Lin kList*/CreateList(i ntn);/void Prin tList(Li nkList L); /*輸出帶頭結點單鏈表的所有元素*/int GetElem(LinkList L,int i,ElemType *e); /*在順序線性表 L 中，當?shù)?i個元素存在時，將其賦值為e*/Lin kList CreateList(i nt n)LNode *p ,*q,*head;int i;head=(

22、L in kList)malloc(sizeof(LNode); p=head;for(i=0;i< n; i+)q=(L in kList)malloc(sizeof(LNode); data %i:",i+1);scan f("%d"，& q->data);q-> next=NULL;p->n ext=q;p=q;retur n head;/*CreateList*/head-next=NULL;prin tf("i nput/*/*/*輸入元素值*/ 結點指針域置空*/ 新結點連在表末尾*/指向單鏈表的第1個元素*/

23、void Prin tList(L in kList L) LNode *p;p=L->n ext; /*pwhile( p!=NULL)prin tf("%5d", p->data); p=p->n ext;/*Prin tList*/int GetElem(Li nkList L,i nt i,ElemTy pe *e) LNode *p;int j=1;p=L->n ext;while( p&&j<i)p=p->n ext;j+;if(!p|j>i)return ERROR;*e=p->data; ret

24、urn OK;/*GetElem*/ int mai n()int n ,i;ElemT ype e;Li nkList L=NULL;/*printfC'pl ease input n:”)； /*scan f("%d", &n);if(n >0)prin tf("n1-Create Lin kList:n");L=CreateList (n);prin tf("n2-Print Lin kList:n");Prin tList(L);prin tf("n3-GetElem from Lin kLis

25、t:n");prin tf("i nput i=");scan f("%d",&i);if(GetElem(L,i, &e)prin tf("No%i is %d",i,e);elseprintf("not exists");elseprin tf("ERROR");return 0;算法分析與運行結果定義指向單鏈表的指針*/輸入單鏈表的元素個數(shù)*/pl ease input n:5 1-Create Lin kList: inp ut data 1:8 input d

26、ata 2:6 input data 3:3 input data 4:5 input data 5:42- Print Lin kList:8635 43- GetElem from Lin kList: input i=2No2 is 6P ress any key to con ti nuevlease tniiut nsSdxit A dtadt A d>Ata1!«2浦3:3S：4LinkLlsi：: in pat input input In尸t imput站一Print LiF*kLlst =U t 3 S 4 3-CBtEl#n fpon LinkList: 詢

27、胛t i 7HoS xs 4P1-C3 5 ah y key to cont inuc4、為第3題補充插入功能函數(shù)和刪除功能函數(shù)。并在主函數(shù)中補充代碼驗證算法的正確性。算法代碼int ListI nsert_sq(LNode *L,i nt i,ElemTy pe e)int k;if(i<1|i>L->le ngth+1)return ERROR;if(L->le ngth>=L->listsize) L->data =(ElemT yp e*)realloc(L->data,(INIT_SIZE+INCREM)*sizeof(ElemT yp

28、 e);if(!L->data)return ERROR;L->listsize+=INCREM;#in clude<stdio.h>#in clude<malloc.h> #defi ne ERROR 0#defi ne OK 1typ edef int ElemT ype; /* typ edef struct LNode /* ElemT ype data; struct LNode *n ext;LNode,*L in kList;定義表元素的類型*/ 線性表的單鏈表存儲*/Lin kList CreateList(i nt n);/*以下為選做實驗

29、：5、循環(huán)鏈表的應用（約瑟夫回環(huán)問題）m將該元素從表中取出，重復上n個數(shù)據(jù)元素構成一個環(huán)，從環(huán)中任意位置開始計數(shù)，計到 述過程，直至表中只剩下一個元素。提示：用一個無頭結點的循環(huán)單鏈表來實現(xiàn)n個元素的存儲。算法代碼6、設一帶頭結點的單鏈表，設計算法將表中值相同的元素僅保留一個結點。提示：指針P從鏈表的第一個元素開始，利用指針q從指針P位置開始向后搜索整個鏈表，刪除與之值相同的元素；指針P繼續(xù)指向下一個元素，開始下一輪的刪除，直至p= null為至，既完成了對整個鏈表元素的刪除相同值。算法代碼三、實驗小結具體的掌握線性表中元素的前驅、后續(xù)的概念。以及順序表與鏈表的建立、插入元素、刪除 表中某元素

30、的算法。并學習了對線性表相應算法的時間復雜度進行分析。四、教師評語實驗二棧和隊列、實驗目的1、掌握棧的結構特性及其入棧，出棧操作；2、掌握隊列的結構特性及其入隊、出隊的操作，掌握循環(huán)隊列的特點及其操作。二、實驗內容和要求1、閱讀下面程序，將函數(shù)Push和函數(shù)Pop補充完整。要求輸入元素序列1 2 3 4 5 e ，運行結果如下所示。CA D；lProgram Fi lesCodeBlackscansole_r unner.eneiC re-ateSt Ack Irlt Successf input data： (Terninated by inputin甘 a cJiarcter> 1

31、2 3 4 5 e 2-Pop6Print54321Fpess ny key to continue.zJ#in clude<stdio.h> #in clude<malloc.h>#defi ne ERROR 0#defi ne OK 1#defi ne STACK_INT_SIZE 10 /*#defi ne STACKINCREMENT 5/*typ edef int ElemT ype; /* typ edef structElemT ype *base;ElemT ype *top;int stacksize; /* SqStack;存儲空間初始分配量*/ 存

32、儲空間分配增量*/定義元素的類型*/當前已分配的存儲空間*/構造空棧*/入棧*/出棧*/創(chuàng)建棧*/出棧并輸出棧中元素*/int In itStack(SqStack *S); /*int p ush(SqStack *S,ElemT ype *e); /* int Pop (SqStack *S,ElemT ype *e); /* int CreateStack(SqStack *S);/*void Prin tStack(SqStack *S); /* int In itStack(SqStack *S)S->base=(ElemTy pe *)malloc(STACK_INT_SIZ

33、E *sizeof(ElemT yp e);if(!S->base) return ERROR;S->t op=S->base;S->stacksize=STACK_INT_SIZE; return OK;/*ln itStack*/ int P ush(SqStack *S,ElemTy pe e) /*P ush*/ int Pop (SqStack *S,ElemTy pe *e) /*Pop*/ int CreateStack(SqStack *S)int e;if(lni tStack(S)prin tf("I nit Success!n"

34、);elseprin tf("I nit Fail!n");return ERROR;prin tf("i nput data:(Term in ated by inpu ti ng a character)n"); while(sca nf("%d", &e)P ush(S,e);return OK;/*CreateStack*/ void Prin tStack(SqStack *S)ElemT ype e;while( Pop( S, &e)prin tf("%3d",e);/*Pop_an

35、d_Pri nt*/ int mai n()SqStack ss;prin tf("n1-createStackn");CreateStack(&ss);prin tf("n2-Pop&Prin t n");Prin tStack(&ss);return 0;算法分析：輸入元素序列1 2 3 45，為什么輸出序列為5432 1?體現(xiàn)了棧的什么特性？2、在第1題的程序中，編寫一個十進制轉換為二進制的數(shù)制轉換算法函數(shù)（要求利用棧來 實現(xiàn)），并驗證其正確性。實現(xiàn)代碼void con veshe n( SqStack *S) ElemT

36、ype n,h;int m=0,k=0;In itStack(S);prin tf("I nput eleme ntn"); sca nf("%d",&n);while( n)m+;Push(S, n%2);n=n/2;while(k<m)k+;Pop (S,&h); prin tf("%d",h);int mai n()SqStack S; con veshe n(&S);prin tf("n");input N=111011Press any hey to continue.3、閱

37、讀并運行程序，并分析程序功能。#in clude<stdio.h>#in clude<malloc.h>#in clude<stri ng.h>#defi ne M 20#defi ne elemt ype char typ edef structelemty pe stackM;int top;stack no de;void in it(stack node *st);void pu sh(stack node *st,elemt ype x); void pop( stack node *st);void in it(stack node *st) s

38、t->t op=0; void pu sh(stack node *st,elemt ype x) if(st->to p=M)prin tf("the stack is overflow!n"); elsest->t op=st->t op+1; st->stackst->t op=x; void pop( stack node *st) st->t op=st->to p-1; int mai n()char sM;int i;prin tf("create a empty stack!n"); sta

39、ck node *sp;sp=malloc(sizeof(stack no de); ini t(s p);prin tf("i nput a exp ressi on:n ”)； gets(s);for(i=0;i<strle n(s);i+)if(si='(') push(s p,si);if(si=')') pop(sp); if(sp->top=O) prin tf("'('match')'!n");elseprin tf("'(' not match&#

40、39;)'!n"); return 0;輸入：2+(c-d)*6-(f-7)*a)/6運行croAtv Abc< 0K卩Edcivn：ft*CCcT>-t- (=/3-3c»3YFot nntch*>*t Presskey to continue輸入：a-(c-d)*6-(s/3-x)/2運行crcAtfr a cnpty stAChf injpiit A evp-rass ion i 2h<<c-d«6-<f-7)»ii>/6Pre*! dny hey tft cant inite程序的基本功能:以下為

41、選做實驗: 4、設計算法，將一個表達式轉換為后綴表達式，并按照后綴表達式進行計算，得出表達式 得結果。實現(xiàn)代碼5、假設以帶頭結點的循環(huán)鏈表表示隊列，并且只設一個指針指向隊尾結點（不設隊頭指針），試編寫相應的置空隊列、入隊列、出隊列的算法。實現(xiàn)代碼：三、實驗小結 基本掌握棧的結構特性及其入棧，出棧操作；以及隊列的結構特性及其入隊、出隊的操作, 掌握循環(huán)隊列的特點及其操作四、教師評語實驗三串的模式匹配、實驗目的1、了解串的基本概念2、掌握串的模式匹配算法的實現(xiàn)二、實驗內容和要求1、閱讀并運行下面程序，根據(jù)輸入寫出運行結果。#in clude<stdio.h> #in cludevstr

42、i ng.h>#defi ne MAXSIZE 100 typ edef structchar dataMAXSIZE; int len gth;SqStri ng;串的比較*/int strCo mp are(SqStri ng *s1,SqStri ng *s2); /*void show_strC omp are();void strSub(SqStri ng *s,i nt start,i nt suble n, SqStri ng *sub);/*求子串*/void show_subStri ng();int strCom pare(SqStri ng *s1,SqStri n

43、g *s2) int i;for(i=0;i<s1->le ngth&&i< s1->le ngth;i+) if(s1->datai!=s2->datai) return s1->datai-s2->datai;return s1->le ngth-s2->le ngth;void show_strC omp are()SqStri ng s1,s2;int k;prin tf("n*show Comp are*n");prin tf("i nput stri ng s1:")

44、;gets(s1.data);s1.le ngth=strle n( s1.data);prin tf("i nput stri ng s2:");gets(s2.data);s2.le ngth=strle n( s2.data);if(k=strCom pare(&s1, &s2)=0) prin tf("s1=s2n");else if(k<0)prin tf("s1<s2n");elseprin tf("s1>s2n");prin tf("n*show over*

45、n");void strSub(SqStri ng *s,i nt start,i nt suble n, SqStri ng *sub) int i;if(start<1|start>s->le ngth|suble n> s->le ngth-start+1) sub->le ngth=O;for(i=0;i<suble n;i+) sub->datai=s->datastart+i-1;sub->le ngth=suble n;void show_subStri ng()SqStri ng s,sub;int star

46、t,suble n,i;prin tf("n*show subStri ng*n");prin tf("i nput stri ng s:");gets(s.data);s.len gth=strle n( s.data);prin tf("i nput start:");scan f("%d", &start);prin tf("i nput suble n:");scan f("%d", &suble n);strSub( &s,start,sub

47、le n,& sub);if(sub.le ngth=0)prin tf("ERROR!n");elseprin tf("subStri ng is :");for(i=0;i<suble n;i+)prin tf("%c",sub.datai);prin tf("n*show over*n"); int mai n()int n;do prin tf("n-Stri ng-n");prin tf("1. strCo mp aren");prin tf(&quo

48、t;2. subStri ngn ”)；prin tf("O. EXIT' n");prin tf("ninput choice:");scan f("%d",&n);getchar();switch( n)case 1:show_strC omp are();break;case 2:show_subStri ng();break; default :n=O;break;while( n);return 0;運行程序輸入：1stude nt stude nts2Compu ter Data Stuctures104運

49、行結果："FAC-H+WENJIANXDebugV 三.exhStping1,哲vCoitijpge2- suhStping EXIIinput cho ：1*slwjw Cciypar* input sti'ing si:student input; stringf s2 - studen ts s1<e2Etrin1 * strConjpareEXIT2, subStping 0-input cbo ic« ：2substring*invut string s =CQnputerStpwctiii'effinifut start ：16irpu &

50、#163;uli l«nsubEt;rlns iw =)ata *slww flv«r*Si*lnsf-1. strConpare 2 substring B EXIIBF和KMP算法。2、實現(xiàn)串的模式匹配算法。補充下面程序，實現(xiàn)串的#in clude<stdio.h> #in cludevstri ng.h>#defi ne MAXSIZE 100 typ edef structchar dataMAXSIZE;int len gth;SqStri ng;int in dex_bf(SqStri ng *s,SqStri ng *t,i nt start

51、);void getNext(SqStri ng *t,i nt next);int in dex_k mp( SqStri ng *s,SqStri ng *t,i nt start,i nt n ext);void show_i ndex();int in dex_bf(SqStri ng *s,SqStri ng *t,i nt start)|int i,j, pos;IIif(t->le ngth=O) return( 0);Ipos=start;i=pos;j=O;while(i<s->le ngth &&j<t->le ngth)if(

52、s->datai=t->dataj)i+;j+; else po S+;Ii=po s;j=O; Is if(j>=t->le ngth)retur n(p os);else return(-1);void getNext(SqStri ng *t,i nt next)int i=O,j=-1;n ext0=-1;while(i<t->le ngth) if(j=-1)ll(t->datai=t->dataj) i+;j+; nexti=j;elsej=nextj;int in dex_k mp (SqStri ng *s,SqStri ng *

53、t,i nt start,i nt next)lint i,j;if(t->le ngth=O) return(O);i=start;j=O;while(i<s->le ngth &&i <t->le ngth ) if(s->data i=t->data j)i+;j+;1else Ij=nextj; I if(j>=t->length ) return (i-j); else return (-1);Ivoid showndex()SqStri ng s,t;int k,n extMAXSIZE=O,i;prin tf(

54、"n*show in dex*n");prin tf("i nput stri ng s:");gets(s.data);s.len gth=strle n( s.data);prin tf("i nput stri ng t:");gets(t.data);t.len gth=strle n(t.data);prin tf("i nput start po siti on:”)；scan f("%d", &k);prin tf("BF:nthe result of BF is %dn&

55、quot;,i ndex_bf(&s, &t,k); getNext (& t, next);prin tf("K MP :n");prin tf(" next:");for(i=0;i<t.le ngth;i+)prin tf("%3d", nexti);prin tf("n");prin tf("the result of KMP is %dn",i ndex_k mp(& s, &t,k, next); prin tf("n*show

56、 over*n"); int mai n()show_i ndex(); return 0;輸入：abcaabbabcabaacbacba abcabaa運行結果:!"*» "Iwi? I linpii-t Bkr inq 三Lnt br 仙 I lAfatilui kniltintllbp： khr話 BP 1. 7Ltat (tE b H A « I f Ln TBduU pf HHP It f三、實驗小結并且可以掌握串的模式匹配算法通過對算法的運行， 加上思考可以深刻了解串的基本概念。的建立。四、教師評語、實驗目的實驗四二叉樹1、掌握二叉樹的基本特性2、掌握二叉樹的遞歸遍歷算法3、理解二叉樹的非遞歸算法4、通過二叉樹的深度和層次遍歷算法，理解二叉樹的基本特性二、實驗內容和要求1、閱讀并運行下面程序，根據(jù)輸入寫出運行結果，并畫出二叉樹的形態(tài)。#in clude<stdio.h>#in clude<malloc.h>#defi ne MAX 20typ edef struct BTNode/*char data ;/*struct BTNode *lchild; struct