數據結構實驗答案(編輯修改稿)

　

【文章內容簡介】 printf(the stack is overflow!\n)。 else { sttop=sttop+1。 ststack[sttop]=x。 }}void pop(stacknode *st){ sttop=sttop1。}int main(){ char s[M]。 int i。 printf(create a empty stack!\n)。 stacknode *sp。 sp=malloc(sizeof(stacknode))。 init(sp)。 printf(input a expression:\n)。 gets(s)。 for(i=0。istrlen(s)。i++) { if(s[i]==39。(39。) push(sp,s[i])。 if(s[i]==39。)39。) pop(sp)。 } if(sptop==0) printf(39。(39。match39。)39。!\n)。 else printf(39。(39。not match39。)39。!\n)。 return 0。}l 輸入：2+((cd)*6(f7)*a)/6l 運行結果：l 輸入：a((cd)*6(s/3x)/2l 運行結果：l 程序的基本功能：以下為選做實驗：設計算法，將一個表達式轉換為后綴表達式，并按照后綴表達式進行計算，得出表達式得結果。l 實現代碼假設以帶頭結點的循環鏈表表示隊列，并且只設一個指針指向隊尾結點（不設隊頭指針），試編寫相應的置空隊列、入隊列、出隊列的算法。實現代碼：三、實驗小結基本掌握棧的結構特性及其入棧，出棧操作；以及隊列的結構特性及其入隊、出隊的操作，掌握循環隊列的特點及其操作四、教師評語實驗三 串的模式匹配一、實驗目的了解串的基本概念掌握串的模式匹配算法的實現 二、實驗內容和要求閱讀并運行下面程序，根據輸入寫出運行結果。includeincludedefine MAXSIZE 100typedef struct{ char data[MAXSIZE]。 int length。}SqString。int strCompare(SqString *s1,SqString *s2)。 /*串的比較*/void show_strCompare()。void strSub(SqString *s,int start,int sublen,SqString *sub)。 /*求子串*/void show_subString()。int strCompare(SqString *s1,SqString *s2){ int i。 for(i=0。is1lengthamp。amp。is1length。i++) if(s1data[i]!=s2data[i]) return s1data[i]s2data[i]。 return s1lengths2length。}void show_strCompare(){ SqString s1,s2。 int k。 printf(\n***show Compare***\n)。 printf(input string s1:)。 gets()。 =strlen()。 printf(input string s2:)。 gets()。 =strlen()。 if((k=strCompare(amp。s1,amp。s2))==0) printf(s1=s2\n)。 else if(k0) printf(s1s2\n)。 else printf(s1s2\n)。 printf(\n***show over***\n)。}void strSub(SqString *s,int start,int sublen,SqString *sub){ int i。 if(start1||startslength||sublenslengthstart+1){ sublength=0。 } for(i=0。isublen。i++) subdata[i]=sdata[start+i1]。 sublength=sublen。}void show_subString(){ SqString s,sub。 int start,sublen,i。 printf(\n***show subString***\n)。 printf(input string s:)。 gets()。 =strlen()。 printf(input start:)。 scanf(%d,amp。start)。 printf(input sublen:)。 scanf(%d,amp。sublen)。 strSub(amp。s,start,sublen,amp。sub)。 if(==0) printf(ERROR!\n)。 else{ printf(subString is :)。 for(i=0。isublen。i++) printf(%c,[i])。 } printf(\n***show over***\n)。}int main(){ int n。 do { printf(\nString\n)。 printf(1. strCompare\n)。 printf(2. subString\n)。 printf(0. EXIT\n)。 printf(\ninput choice:)。 scanf(%d,amp。n)。 getchar()。 switch(n){ case 1:show_strCompare()。break。 case 2:show_subString()。break。 default:n=0。break。 } }while(n)。 return 0。}l 運行程序輸入：1studentstudents2Computer Data Stuctures104運行結果：實現串的模式匹配算法。補充下面程序，實現串的BF和KMP算法。includeincludedefine MAXSIZE 100typedef struct{ char data[MAXSIZE]。 int length。}SqString。int index_bf(SqString *s,SqString *t,int start)。void getNext(SqString *t,int next[])。int index_kmp(SqString *s,SqString *t,int start,int next[])。void show_index()。int index_bf(SqString *s,SqString *t,int start){int i,j,pos。 if(tlength==0) return(0)。 pos=start。i=pos。j=0。 while(islengthamp。amp。jtlength) if(sdata[i]==tdata[j]){i++。j++。} else{pos++。 i=pos。j=0。 } if(j=tlength)return(pos)。 else return(1)。}}void getNext(SqString *t,int next[]){ int i=0,j=1。 next[0]=1。 while(itlength){ if((j==1)||(tdata[i]==tdata[j])){ i++。j++。next[i]=j。 }else j=next[j]。 }}int index_kmp(SqString *s,SqString *t,int start,int next[]){ int i,j。 if(tlength==0) return(0)。 i=start。j=0。 while(islength amp。amp。jtlength ) if(sdata [i]==tdata [j]) {i++。j++。} else j=next[j]。 if(j=tlength ) return (ij)。 else return (1)。}void show_index(){ SqString s,t。 int k,next[MAXSIZE]={0},i。 printf(\n***show index***\n)。 printf(input string s:)。 gets()。 =strlen()。 printf(input string t:)。 gets()。 =strlen()。 printf(input start position:)。 scanf(%d,amp。k)。 printf(BF:\nthe result of BF is %d\n,index_bf(amp。s,amp。t,k))。 getNext(amp。t,next)。 printf(KMP:\n)。 printf(next[]:)。 for(i=0。i。i++) printf(%3d,next[i])。 printf(\n)。 printf(the result of KMP is %d\n,index_kmp(amp。s,amp。t,k,next))。 printf(\n***show over***\n)。}int main(){show_index()。return 0。}輸入：abcaabbabcabaacbacbaabcabaa1運行結果：三、實驗小結通過對算法的運行，加上思考可以深刻了解串的基本概念。并且可以掌握串的模式匹配算法的建立。 四、教師評語實驗四 二叉樹一、實驗目的掌握二叉樹的基本特性掌握二叉樹的遞歸遍歷算法 理解二叉樹的非遞歸算法通過二叉樹的深度和層次遍歷算法，理解二叉樹的基本特性二、實驗內容和要求閱讀并運行下面程序，根據輸入寫出運行結果，并畫出二叉樹的形態。includeincludedefine MAX 20typedef struct BTNode{ /*節點結構聲明*/ char data 。 /*節點數據*/ struct BTNode *lchild。 struct BTNode *rchild 。 /*指針*/}*BiTree。void createBiTree(BiTree *t){ /* 先序遍歷創建二叉樹*/ char s。 BiTree q。 printf(\nplease input data:(exit for ))。 s=getche()。 if(s==39。39。){*t=NULL。 return。} q=(BiTree)malloc(sizeof(struct BTNode))。 if(q==NULL){printf(Memory alloc failure!)。 exit(0)。} qdata=s。 *t=q。 createBiTree(amp。qlchild)。 /*遞歸建立左子樹*/ createBiTree(amp。qrchild)。 /*遞歸建立右子樹*/}void PreOrder(BiTree p){ /* 先序遍歷二叉樹*/ if ( p!= NULL ) { printf(%c, pdata)。 PreOrder( plchild ) 。