數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)規(guī)范標(biāo)準(zhǔn)答案

1、!-數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)2013/ 2014學(xué)年第2學(xué)期名:t=r.號(hào):級(jí):指導(dǎo)教師:濰坊學(xué)院計(jì)算機(jī)工程學(xué)院2014預(yù)備實(shí)驗(yàn)C語(yǔ)言的函數(shù)數(shù)組指針結(jié)構(gòu)體知識(shí)、實(shí)驗(yàn)?zāi)康?、復(fù)習(xí)C語(yǔ)言中函數(shù)、數(shù)組、指針和結(jié)構(gòu)體的概念。2、熟悉利用C語(yǔ)言進(jìn)行程序設(shè)計(jì)的一般方法。二、實(shí)驗(yàn)內(nèi)容和要求1、調(diào)試程序：輸出100以內(nèi)所有的素?cái)?shù)(用函數(shù)實(shí)現(xiàn))。#in clude<stdio.h>/*判斷一個(gè)數(shù)是否為素?cái)?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以內(nèi)所有素?cái)?shù)*/int ma

2、i n()int i;for(i=2;i<100;i+)“4d' ,i);if(is prime(i)= =1) printf(return 0;運(yùn)行結(jié)果:VI755? 11 IJ 17 IV*1 +JS? «n IJt7Priii1a -inv hihv L樸 nmH2、調(diào)試程序：對(duì)一維數(shù)組中的元素進(jìn)行逆序排列。#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;運(yùn)行結(jié)果: Iw -"Tr»3f Iv-I» L 工 H F4 ha Eli.r>gKd rv*” xeIT7 t I3、調(diào)試程序：在二維數(shù)組中，若某一位置上的元素在該行中最大，而在該列中最小，則該 元素即為該二維數(shù)組的一個(gè)鞍點(diǎn)。要求從鍵盤

4、上輸入一個(gè)二維數(shù)組，當(dāng)鞍點(diǎn)存在時(shí)，把鞍點(diǎn)找出來(lái)。#in clude<stdio.h>#defi ne M 3 #defi ne N 4int mai n()int aMN,i,j,k;printf(請(qǐng)輸入二維數(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行找到鞍點(diǎn)*/“d,%d,%”),aik,i,k);if(j=M)printf(return 0;運(yùn)行結(jié)果:訕I(yè)d 強(qiáng)加 Vti 汕 It 4L 7 4 » 4ble1)昭4C7B附IE«.743246iFF-IR 七n* h時(shí)Vo-nclRiufi4、調(diào)試程序：利用指針輸出二維數(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;運(yùn)行結(jié)果:5、調(diào)試程序：輸入10個(gè)學(xué)生的成績(jī)，每個(gè)學(xué)生成績(jī)包括學(xué)號(hào)、姓名和三門課的成績(jī)。要 求打印出三門課的平均成績(jī)及成績(jī)最高者的姓名和成績(jī)。#in clude<stdio.h>#defi ne N 10;struct stude ntchar num6;/*學(xué)號(hào) */char name8; /* 姓名 */int score3; /* 成績(jī) */ fl

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

8、，找出成績(jī)最高的學(xué)生*/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( “學(xué)號(hào) 姓名 成績(jī)1 成績(jī)2 成績(jī)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(平均成績(jī)是：%5.2fn ”,average);printf(最好成績(jī)的學(xué)生是：s,總分是 %d”,,max);return 0;運(yùn)行結(jié)果 li 衛(wèi) 3 G 士 V R 貝皿JDLU呵財(cái)塑噩時(shí);珂2 *7.67 *1 M 92,t? tid.t? 恥.n F.flO a»M 73-HW 7ft.-jnnIMa?SV令9*&財(cái)K站 艸 W 丹 H M 福"-話評(píng) 1 r 1 ff 士 y 3 UH 1 ffu xff 金 F 3 »H _3t£ J

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

11、序表與鏈表的建立、插入元素、刪除表中某元素的算法。 對(duì)線性表相應(yīng)算法的時(shí)間復(fù)雜度進(jìn)行分析。理解順序表、鏈表數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)（優(yōu)缺點(diǎn)）。二、實(shí)驗(yàn)內(nèi)容和要求1、閱讀下面程序，在橫線處填寫函數(shù)的基本功能。并運(yùn)行程序，寫出結(jié)果。#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;/*初始分配的順序表長(zhǎng)度 */ 溢出時(shí)，順序表長(zhǎng)度的增量*/定義表元素的類型*/存儲(chǔ)空間的基地址*/ 順序表的當(dāng)前長(zhǎng)度*/ 當(dāng)前分配的存儲(chǔ)空間*/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,并將其長(zhǎng)度設(shè)為0*L,int n）; /*構(gòu)造順序表的長(zhǎng)度為n*/*/在順序線性表L中第i個(gè)輸出順序表的元素*/刪除第i個(gè)元素*/查找值為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個(gè)元素*/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;/*在順序表中查找指定值元素，返回其序號(hào)*/int ListLocate(Sqlist *L,ElemT ype e)int mai n()Sqlist sl;int n;輸入順序表的元素個(gè)數(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;算法分析與運(yùn)行結(jié)果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題補(bǔ)充刪除和查找功能函數(shù)，并在主函數(shù)中補(bǔ)充代碼驗(yàn)證算法的正確性。 算法代碼：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;/*在順序表中查找指定值元素，返回其序號(hào)*/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ù)的基本功能。并運(yùn)行程序，寫出結(jié)果。#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;定義表元素的類型*/ 線性表的單鏈表存儲(chǔ)*/Lin kList*/CreateList(i ntn);/void Prin tList(Li nkList L); /*輸出帶頭結(jié)點(diǎn)單鏈表的所有元素*/int GetElem(LinkList L,int i,ElemType *e); /*在順序線性表 L 中，當(dāng)?shù)?i個(gè)元素存在時(shí)，將其賦值為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/*/*/*輸入元素值*/ 結(jié)點(diǎn)指針域置空*/ 新結(jié)點(diǎn)連在表末尾*/指向單鏈表的第1個(gè)元素*/

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;算法分析與運(yùn)行結(jié)果定義指向單鏈表的指針*/輸入單鏈表的元素個(gè)數(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題補(bǔ)充插入功能函數(shù)和刪除功能函數(shù)。并在主函數(shù)中補(bǔ)充代碼驗(yàn)證算法的正確性。算法代碼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;定義表元素的類型*/ 線性表的單鏈表存儲(chǔ)*/Lin kList CreateList(i nt n);/*以下為選做實(shí)驗(yàn)

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

30、的算法。并學(xué)習(xí)了對(duì)線性表相應(yīng)算法的時(shí)間復(fù)雜度進(jìn)行分析。四、教師評(píng)語(yǔ)實(shí)驗(yàn)二棧和隊(duì)列、實(shí)驗(yàn)?zāi)康?、掌握棧的結(jié)構(gòu)特性及其入棧，出棧操作；2、掌握隊(duì)列的結(jié)構(gòu)特性及其入隊(duì)、出隊(duì)的操作，掌握循環(huán)隊(duì)列的特點(diǎn)及其操作。二、實(shí)驗(yàn)內(nèi)容和要求1、閱讀下面程序，將函數(shù)Push和函數(shù)Pop補(bǔ)充完整。要求輸入元素序列1 2 3 4 5 e ，運(yùn)行結(jié)果如下所示。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;存儲(chǔ)空間初始分配量*/ 存

32、儲(chǔ)空間分配增量*/定義元素的類型*/當(dāng)前已分配的存儲(chǔ)空間*/構(gòu)造空棧*/入棧*/出棧*/創(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題的程序中，編寫一個(gè)十進(jìn)制轉(zhuǎn)換為二進(jìn)制的數(shù)制轉(zhuǎn)換算法函數(shù)（要求利用棧來(lái) 實(shí)現(xiàn)），并驗(yàn)證其正確性。實(shí)現(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、讀并運(yùn)行程序，并分析程序功能。#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運(yùn)行croAtv Abc< 0K卩Edcivn：ft*CCcT>-t- (=/3-3c»3YFot nntch*>*t Presskey to continue輸入：a-(c-d)*6-(s/3-x)/2運(yùn)行crcAtfr a cnpty stAChf injpiit A evp-rass ion i 2h<<c-d«6-<f-7)»ii>/6Pre*! dny hey tft cant inite程序的基本功能:以下為

41、選做實(shí)驗(yàn): 4、設(shè)計(jì)算法，將一個(gè)表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，并按照后綴表達(dá)式進(jìn)行計(jì)算，得出表達(dá)式 得結(jié)果。實(shí)現(xiàn)代碼5、假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾結(jié)點(diǎn)（不設(shè)隊(duì)頭指針），試編寫相應(yīng)的置空隊(duì)列、入隊(duì)列、出隊(duì)列的算法。實(shí)現(xiàn)代碼：三、實(shí)驗(yàn)小結(jié) 基本掌握棧的結(jié)構(gòu)特性及其入棧，出棧操作；以及隊(duì)列的結(jié)構(gòu)特性及其入隊(duì)、出隊(duì)的操作, 掌握循環(huán)隊(duì)列的特點(diǎn)及其操作四、教師評(píng)語(yǔ)實(shí)驗(yàn)三串的模式匹配、實(shí)驗(yàn)?zāi)康?、了解串的基本概念2、掌握串的模式匹配算法的實(shí)現(xiàn)二、實(shí)驗(yàn)內(nèi)容和要求1、閱讀并運(yùn)行下面程序，根據(jù)輸入寫出運(yùn)行結(jié)果。#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;運(yùn)行程序輸入：1stude nt stude nts2Compu ter Data Stuctures104運(yùn)

49、行結(jié)果："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、實(shí)現(xiàn)串的模式匹配算法。補(bǔ)充下面程序，實(shí)現(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運(yùn)行結(jié)果:!"*» "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三、實(shí)驗(yàn)小結(jié)并且可以掌握串的模式匹配算法通過(guò)對(duì)算法的運(yùn)行， 加上思考可以深刻了解串的基本概念。的建立。四、教師評(píng)語(yǔ)、實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)四二叉樹1、掌握二叉樹的基本特性2、掌握二叉樹的遞歸遍歷算法3、理解二叉樹的非遞歸算法4、通過(guò)二叉樹的深度和層次遍歷算法，理解二叉樹的基本特性二、實(shí)驗(yàn)內(nèi)容和要求1、閱讀并運(yùn)行下面程序，根據(jù)輸入寫出運(yùn)行結(jié)果，并畫出二叉樹的形態(tài)。#in clude<stdio.h>#in clude<malloc.h>#defi ne MAX 20typ edef struct BTNode/*char data ;/*struct BTNode *lchild; struct