《算法語言與數(shù)據(jù)結構實驗指導指導書》由會員分享，可在線閱讀，更多相關《算法語言與數(shù)據(jù)結構實驗指導指導書（31頁珍藏版）》請在裝配圖網上搜索。

1、理學系實驗?指導書 算法語言與?數(shù)據(jù)結構 專業(yè)名稱：信息與計算?科學專業(yè) 課程名稱：算法語言與?數(shù)據(jù)結構 授課對象：本科生 總學時數(shù)：24學時 實驗室名稱?：信息與計算?科學實驗室? 內容摘要：《數(shù)據(jù)結構》是計算機應?用專業(yè)的一?門專業(yè)基礎?課，通過本實驗?的訓練，應培養(yǎng)學生?的數(shù)據(jù)抽象?能力和程序?設計能力。《數(shù)據(jù)結構》的先修課主?要是《C語言程序?設計》，本實驗以C?語言作為算?法描述和上?機實踐工具?。 根據(jù)教學內?容和教學目?標，實驗課共開?

2、設12次實?驗。學生應按照?實驗指導書?的要求，完成指定的?實驗任務。實驗課分班?進行，每個實驗班?50人左右?，配備一名實?驗指導教師?（另編寫了一?本實驗指導?與題解的教?材，8月份出版?）。 考核方式：以平時完成?實驗情況和?最后作業(yè)進?行評定。 實驗類別：專業(yè)必修課? 實驗一 結構體與共?用體 一、實驗目的 （1）掌握結構體?類型數(shù)組的?概念和使用?； （2）掌握枚舉類?型的概念與?使用； （3）設計并掌握?算法，學會分析算?法并培養(yǎng)用?算法解決實?際問題的能?力。 二、實驗要求 （1）設計相應原?始表格（比賽的成績?），選擇恰當?shù)?數(shù)據(jù)結構； （2）統(tǒng)計各

3、院校?的男、女總分和團?體總分，并輸出。 三、實驗內容 假設有A、B、C、D、E五個高校?進行田徑比?賽，各院校的單?項成績均已?存入計算機?，并構成一張?表，表的每一行?的形式為：項目名稱 性別 校名 成績 得分 編程統(tǒng)計各?院校的男、女總分和團?體總分，并輸出。 四、主要儀器設?備 PC機及T?C或VC 五、實驗步驟 #defin?e NULL 0 typed?ef struc?t{ char *sport?; enum{male,femal?e} gende?r;

4、 char schoo?lname?; char *resul?t; int score?; } resul?ttype?; typed?ef struc?t{ int males?core; int femal?escor?e; int total?score?; } score?type; void summa?ry(resul?ttype? resu

5、l?t[ ]) { score?type score?[5]={{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0}}; int i=0; while?(resul?t[i].sport?!=NULL) { switc?h(resul?t[i].schoo?lname?) { case A: score?[0].total?score?+=resul?t[i].score?; if(resul?t[i].gende?r==0) score?[0].males?core+=resul?t[i].score

6、?; else score?[0].femal?escor?e+=resul?t[i].score?; break?; case B: score?[1].total?score?+=resul?t[i].score?; if(resul?t[i].gende?r==0) score?[1].males?core+=resul?t[i].score?; else score?[1].femal?escor?e+=resul?t[i].score?; break?;

7、 case C: score?[2].total?score?+=resul?t[i].score?; if(resul?t[i].gende?r==0) score?[2].males?core+=resul?t[i].score?; else score?[2].femal?escor?e+=resul?t[i].score?; break?; case D: score?[3].total?score?+=resul?t[i].score?; if(resul?t

8、[i].gende?r==0) score?[3].males?core+=resul?t[i].score?; else score?[3].femal?escor?e+=resul?t[i].score?; break?; case E: score?[4].total?score?+=resul?t[i].score?; if(resul?t[i].gende?r==0) score?[4].males?core+=resul?t[i].score?; else score?[4].f

9、emal?escor?e+=resul?t[i].score?; break?; } i++; } for(i=0;i<5;i++) { print?f("Schoo?l %d:\n",i); print?f("Total? score? of male:%d\n",score?[i].males?core); print?f("Total? score? of femal?e:%d\n",score?[i].femal?escor?e); print?f("Total? score? of all

10、:%d\n\n",score?[i].total?score?); } } main() {resul?ttype? resul?t[20]={{"bm",male,A,"veryg?ood",9},{"ty",femal?e,A,"good",8}, {"bm",male,B,"good",8},{"ty",femal?e,B,"veryg?ood",10}, {"bm",male,C,"good",7},{"ty",femal?e,C,"good",8}, {"bm",male,D,"veryg?ood",10},{"ty",femal?e,d,"goo

11、d",9}, {"bm",male,E,"good",9},{"ty",femal?e,E,"veryg?ood",9}}; summa?ry(resul?t); } 六、注意事項 （1）、將本實驗上?機調試、運行，注意調試過?程中出現(xiàn)的?問題； （2）、結合運行結?果，對程序進行?分析。 實驗二 文件 一、實驗目的 （1）學會使用文?件打開、關閉、讀、寫等文件操?作函數(shù)； （2）學會用緩沖?文件系統(tǒng)對?文件進行簡?單的操作； （3）設計并掌握?算法，學會分析算?法并培養(yǎng)用?算法解決實?際問題的能?力。 二、實驗要求 （1）將這10個?學生信息存?入

12、到磁盤文?件stud?ent中； （2）將磁盤文件?中的所有學?生記錄讀入?內存中一塊?靜態(tài)順序空?間中，求出所有學?生的平均成?績； （3）將學生成績?按平均分進?行排序處理?，將已排序的?學生數(shù)據(jù)存?入一個新文?件stu_?sort中?。 三、實驗內容 （1）有10個學?生，每個學生有?3門課的成?績，從鍵盤輸入?數(shù)據(jù)（包括學生號?、姓名、3門課成績?）計算平均成?績，將原有數(shù)據(jù)?和計算出的?平均分數(shù)存?放在磁盤文?件stud?ent中。 （2）將上題st?udent?文件中的學?生數(shù)據(jù)，按平均分進?行排序處理?，將已排序的?學生數(shù)據(jù)存?入一個新文?件stu_?sort中

13、?（并檢查該文?件中的內容?是否正確）。 四、主要儀器設?備 PC機及T?C或VC 五、實驗步驟 l 學生記錄結?構如下： Struc?t stude?nt_ty?pe{ Char id[5]; Char name[11]; int age; int math; int eng; int data_?struc?t; int os;} 六、注意事項 （1）、將本實驗上?機調試、運行，注意調試過?程中出現(xiàn)的?問題； （2）、結合運行結?果，對程序進行?分析。 實驗三 順序表基本?操作 一、實驗目的 （1）掌握線性表?的順序存儲?結構及其實?現(xiàn)方

14、法； （2）掌握順序表?上的插入、刪除和查找?操作。 二、實驗要求 （1）設計相應的?兩級測試數(shù)?據(jù)，一組為整形?數(shù)據(jù)，一組為字符?數(shù)據(jù)，個數(shù)不少于?10個； （2）在第5個位?置上插入一?個數(shù)或字符?； （3）將第7個元?素刪除； （4）查找值為？的元素，若存在將其?輸出，否則打印沒?有該元素。 三、實驗內容 用C語言數(shù)?組實現(xiàn)在順?序表上進行?插入、刪除和查找?操作。 四、主要儀器設?備 PC機及T?C或VC 五、實驗步驟 （1）算法提示：參照書本上?的算法。 （2）參考源代碼? #inclu?de #defin?e init_?size

15、 20 typed?ef int elemt?ype ; typed?ef struc?t { elemt?ype *elem; int lengt?h; int lists?ize; }sqlis?t; int Inser?t_sqL?ist(sqlis?t *va,int x) {int i; if(va->lengt?h+1>va->lists?ize) retur?n -1; va->lengt?h++; for(i=va->lengt?h;va->elem[i]>x&&i>=0;i--) va->elem[i+1]=va->elem[i

16、]; va->elem[i+1]=x; retur?n 1; } main() {sqlis?t va; int i,e; va.elem=(elemt?ype *)mallo?c(init_?size*sizeo?f(elemt?ype)); va.lengt?h=10; va.lists?ize=init_?size; for(i=1;i<= va.lengt?h;i++) scanf?("%d",&va.elem[i]); scanf?("%d",&e); if(Inser?t_sqL?ist(&va,e)); for(i=1;i<=va.lengt

17、?h;i++) print?f("%d ",va.elem[i]); } 六、注意事項 （1）、將本實驗上?機調試、運行，注意調試過?程中出現(xiàn)的?問題； （2）、結合運行結?果，對程序進行?分析。 實驗四 鏈表基本操?作 一、實驗目的 （1）、幫助讀者復?習C語言程?序設計中的?知識。 （2）、熟悉線性表?的基本運算?在鏈式存儲?結構上的實?現(xiàn)。 二、實驗要求 （1）、掌握線性表?的邏輯結構?。 （2）、掌握線性表?的鏈式存儲?結構。 （3）、熟練掌握線?性表的插入?、刪除、按序號查找?和按值查找?操作等操作?。 三、實驗內容 用C語言編?程實現(xiàn)單鏈?表的建

18、立、插入、刪除、按序號查找?和按值查找?操作算法。 四、主要儀器設?備 PC機及T?C或VC 五、實驗步驟 1、算法分析 ①為使算法的?時間復雜度?為O(n+m)只能采用“平移指針，一次掃描”的方法，于是設兩個?指針分別指?向兩個線性?表表頭。 ②為使合并后?仍為一個有?序表，需對指針所?指結點的數(shù)?據(jù)域進行比?較。 ③要使合并后?的有序表為?遞減有序表?，比較后選出?較小的一個?將其從原鏈?表中取出插?入到新表的?表首。 ④指針后移，重復②，③步，直到其中一?個表結束，將尚未結束?表的元素依?次取出插入?新表。 ⑤為減少頭指?針的變化，采用帶有頭?結點的鏈表?。 2、算法

19、如下 struc?t node {int data; struc?t node *link; } typed?ef struc?t node NODE; NODE *merge?_link?(NODE *head_?a,NODE *head_?b) {NODE *p,*q,*head; head=(NODE*)mallo?c(sizeo?f(NODE)); head->link=NULL; p=head_?a->link; q=head_?b->link; while?((p!=NULL)&&(q!=NULL)) if(p->datadata

20、) {head_?a->link=p->link; p->link=head->link; head->link=p; p=head_?a->link; } else {head_?b->link=q->link; q->link=head->link; head->link=q;q=head_?b->link; } while?(p!=NULL) {head_?a->link=p->link; p->link=head->link; head->link=p; p=head_?a->link; } while?(q!=NULL)

21、 {head_?b->link=q->link; q->link=head->link; head->link=q; q=head_?b->link; } free(head_?a); free(head_?b); retur?n(head); } 六、注意事項 （1）、將本實驗上?機調試、運行，注意調試過?程中出現(xiàn)的?問題； （2）、結合運行結?果，對程序進行?分析。 實驗五 一元稀疏多?項式運算 一、實驗目的 設計并掌握?算法，學會分析算?法并培養(yǎng)用?算法解決實?際問題的能?力。 二、實驗要求 （1）用帶頭結點?的單鏈表做?存

22、儲結構； （2）構造兩個多?項式，實現(xiàn)相加和?相乘。 三、實驗內容 用C語言編?程實現(xiàn)一元?稀疏多項式?加、減、乘運算。 四、主要儀器設?備 PC機及T?C或VC 五、實驗步驟 #defin?e NULL 0 #inclu?de #inclu?de typed?ef struc?t term{ float? coef; int expn; struc?t term *next;}term,*polyn?omial?; term *creat?(int n) {term *head, *p,*q; int i; fl

23、oat? s; head=(polyn?omial?)mallo?c(sizeo?f(term)); head->next=NULL;head->coef=0.0;head->expn=-1; q=head; for(i=n;i>0;i--){ p=(polyn?omial?)mallo?c(sizeo?f(term)); scanf?("%f,%d",&s,&p->expn); p->coef=s; p->next=q->next;q->next=p;q=p;} retur?n(head);} void print?(polyn?omial? head) {term *

24、p; p=head->next; print?f("%f*x^%d",p->coef,p->expn); p=p->next; while?(p) {if(p->coef>0) print?f("+%f*x^%d",p->coef,p->expn); else if(p->coef<0) print?f("%f*x^%d",p->coef,p->expn); p=p->next;} } polyn?omial? addpo?lyn(polyn?omial? f,polyn?omial? g) {polyn?omial? p,q,pre,u; float? sum;

25、p=f->next;q=g->next;pre=f; while?(p&&q) {if(p->expnexpn) {pre=p;p=p->next;} else if(p->expn==q->expn) {sum=p->coef+q->coef; if(sum!=0) {p->coef=sum;pre=p;} else{pre->next=p->next;free(p);} p=pre->next;u=q;q=q->next;free(u);} else {u=q->next;q->next=p;p

26、re->next=q;pre=q;q=u;} } if(q) pre->next=q; free(g); retur?n(f); } main() {polyn?omial? f,g,h; int n,m; print?f("n="); scanf?("%d",&n); f=creat?(n); print?f("m="); scanf?("%d",&m); g=creat?(m); h=addpo?lyn(f,g); print?(h); } #defin?e NULL 0 #inclu?de #inclu?de

27、 typed?ef struc?t term{ float? coef; int expn; struc?t term *next;}term,*polyn?omial?; term *creat?(int n) {term *head, *p,*q; int i; float? s; head=(polyn?omial?)mallo?c(sizeo?f(term)); head->next=NULL;head->coef=0.0;head->expn=-1; q=head; for(i=n;i>0;i--){ p=(polyn?omial?)m

28、allo?c(sizeo?f(term)); scanf?("%f,%d",&s,&p->expn); p->coef=s; p->next=q->next;q->next=p;q=p;} retur?n(head);} void print?(polyn?omial? head) {term *p; p=head->next; print?f("%f*x^%d",p->coef,p->expn); p=p->next; while?(p) {if(p->coef>0) print?f("+%f*x^%d",p->coef,p->expn); else if(p->c

29、oef<0) print?f("%f*x^%d",p->coef,p->expn); p=p->next;} } polyn?omial? rever?se(polyn?omial? l) {polyn?omial? p,q; p=l->next;l->next=NULL; while?(p) {q=p->next; p->next=l->next;l->next=p;p=q;} retur?n(l);} polyn?omial? *multi?ply(polyn?omial? f,polyn?omial? g) {polyn?omial? h,l,fp,gp,hp,q

30、; int max,k,r; float? c; max=f->next->expn+g->next->expn; h=(term *)mallo?c(sizeo?f(term));h->coef=0.0;h->expn=-1; h->next=NULL;hp=h; l=rever?se(g); for(r=max;r>=0;r--) {c=0.0;fp=f->next;gp=l->next; while?(fp&&gp) {k=fp->expn+gp->expn; if(k>r) fp=fp->next; else if(k

31、p->next; else{ c+=fp->coef*gp->coef; fp=fp->next;gp=gp->next;} } if(c!=0.0) {q=(term*)mallo?c(sizeo?f(term)); q->expn=r;q->coef=c;q->next=hp->next;hp->next=q;hp=q;} } retur?n(h); } main() {polyn?omial? f,g,h; int n,m; print?f("n="); scanf?("%d",&n); f=creat?(n);

32、 print?f("m="); scanf?("%d",&m); g=creat?(m); h=multi?ply(f,g); print?(h); } 六、注意事項 （1）、將本實驗上?機調試、運行，注意調試過?程中出現(xiàn)的?問題； （2）、結合運行結?果，對程序進行?分析。 實驗六 棧的應用 一、實驗目的 1、使學生深入?了解堆棧的?特性，以便在遇到?實際問題時?靈活運用堆?棧知識。 2、鞏固堆棧數(shù)?據(jù)結構的構?造方法。 二、實驗要求 1、掌握堆棧的?邏輯結構和?存儲結構。 2、熟練掌握堆?棧的出棧、入棧等操作?。 三、實驗內容 用C語言編?程實現(xiàn)數(shù)制?

33、轉換和算術?表達式的求?值。 四、主要儀器設?備 PC機及T?C或VC 五、實驗步驟 1、算法分析 將十進制數(shù)?N和其它d?進制數(shù)的轉?換是計算機?實現(xiàn)計算的?基本問題，其解決方案?很多，其中最簡單?方法基于下?列原理：即除d取余?法。例如:(1348)10=(2504)8 　　N　　N div 8　　N mod 8 　1348 　　168 　　　　4 　168　　　21　　　　　0 　21 　　　2 　　　　　5 　2　　　　0 　　　　　2 　　從中我們可?以看出，最先產生的?余數(shù)4是轉?換結果的最?低位，這正好符合?棧的特性即?后進先出的?特性。所以可以用?順序棧來

34、模?擬這個過程?。 2、源程序如下? struc?t node {int data; struc?t node *link; } typed?ef struc?t node NODE; NODE *top=NULL; void conve?rsion?(int x) { while?(x>0) {push(top,x%8); x=x/8; } while?(!stack?empty?(top)) /* stack?empty?( )為判斷堆棧?是否為空函?數(shù)*/ {x=pop(s); print?f(“%d”,x); } #defi

35、n?e Maxsi?ze 100 #inclu?de void trans?(char str[],char exp[]) {char stack?[Maxsi?ze]; char ch; int i=0,j,t,top=0; i=1,t=1; ch=str[i]; while?(ch!=#) {if(ch>=0&& ch<=9) {exp[t]=ch;t++;} else if(ch==() {top++;stack?[top]=ch;} else if(ch==)) {while?(stack?[top]!=() {

36、exp[t]=stack?[top];top--;t++;} top--; } else if(ch==+||ch==-) {while?(top!=0 && stack?[top]!=() {exp[t]=stack?[top];top--;t++;} top++;stack?[top]=ch;} else if(ch==*||ch==/) { while?(stack?[top]==/||stack?[top]==*) {exp[t]=stack?[top]; top--;t++;} top++;stack?[top

37、]=ch; } i++; ch=str[i]; } while?(top!=0) {exp[t]=stack?[top];t++;top--;} exp[t]=#; for(j=1;j<=t;j++) print?f("%c",exp[j]); print?f("\n"); } void compv?alue(char exp[]) {float? stack?[Maxsi?ze],d; char c; int t=1,top=0; c=exp[t],t++; while?(c!=#) { d=c-

38、0; if (c>=0&&c<=9) {top++; stack?[top]=d;} else { switc?h(c) { case +:stack?[top-1]=stack?[top-1]+stack?[top]; break?; case -:stack?[top-1]=stack?[top-1]-stack?[top]; break?; case *:stack?[top-1]=stack?[top-1]*stack?[top]; break?; case /:if (stack?[top]!=0) sta

39、ck?[top-1]=stack?[top-1]/stack?[top]; else print?f("chu ling chuo wu !\n"); break?; } top--; } c=exp[t]; t++; } print?f("ji suan jie guo shi:%g",stack?[top]); } main() {char str[Maxsi?ze]; char exp[Maxsi?ze]; int i=0,j,t=0; do {i++; scanf?("%c",&str[

40、i]); }while? (str[i]!=#&& i

41、和?存儲結構。 （2）、熟練掌握隊?列的出隊、入隊等操作?。 三、實驗內容 用C語言編?程實現(xiàn)迷宮?問題求解。 四、主要儀器設?備 PC機及T?C或VC 五、實驗步驟 （1）、算法分析 迷宮的定義?如下： #defin?e m 6 /* 迷宮的實際?行 */ #defin?e n 8 /* 迷宮的實際?列 */ int maze [m+2][n+2] ; maze[i][j]=0或1; 其中：0表示通路?，1表示不通?，當從某點向?下試探時，中間點有8?個方向可以?試探，（見圖3.4）而四個角點?有3個方向?，其它邊緣點?有5個方向?，為使問題

42、簡?單化我們用?maze[m+2][n+2]來表示迷宮?，而迷宮的四?周的值全部?為1。 Move數(shù)?組定義如下?： typed?ef struc?t { int x，y } item ; item move[8] ; 當?shù)竭_了某?點而無路可?走時需返回?前一點，再從前一點?開始向下一?個方向繼續(xù)?試探。因此，壓入棧中的?不僅是順序?到達的各點?的坐標，而且還要有?從前一點到?達本點的方?向。 typed?ef struc?t {int x , y , d ;/* 橫縱坐標及?方向*/ }datat?ype ; 迷宮求解算?法思想如下?： 1

43、． 棧初始化; 2． 將入口點坐?標及到達該?點的方向（設為－１）入棧 3． while? (棧不空) { 棧頂元素＝＞（x , y , d） 出棧 ; 求出下一個?要試探的方?向d++ ; while? （還有剩余試?探方向時） { if （d方向可走?） 則 { （x , y , d）入棧 ; 求新點坐標? (i, j ) ; 將新點（i , j）切換為當前?點（x , y） ; if ( (x ,ｙ)= =(ｍ,n) ) 結束 ; else 重置 d=0 ; }

44、 else d++ ; } } 2、源程序如下? #inclu?de #defin?e M 6 #defin?e N 8 typed?ef struc?t {int x,y,pre; }sqtyp?e; sqtyp?e sq[400]; struc?t moved? {int x,y; }move[8]; int maze[M+2][N+2]; void print?path(sqtyp?e sq[],int rear) {int i; i=rear; do {prin

45、t?f("(%d,%d)<-",sq[i].x,sq[i].y); i=sq[i].pre; }while?(i!=0); } int short?path() {int i,j,v,front?,rear,x,y; sq[1].x=1;sq[1].y=1;sq[1].pre=0; front?=1;rear=1; maze[1][1]=-1; while?(front?<=rear) {x=sq[front?].x;y=sq[front?].y; for(v=0;v<8;v++) {i=x+move[v].x; j=y+move[v].y; if(

46、maze[i][j]==0) {rear++;sq[rear].x=i;sq[rear].y=j;sq[rear].pre=front?; maze[i][j]=-1;} if((i==M)&&(j==N)) {print?path(sq,rear); retur?n(1); } } front?++; }retur?n(0); } main() {int i,j; for(i=1;i<=M;i++) for(j=1;j<=N;j++) scanf?("%1d",&maze[i][j]); for(i=0;i<=M+1;i++) {

47、maze[i][0]=1;maze[i][N+1]=1;} for(j=0;j<=N+1;j++) {maze[0][j]=1;maze[M+1][j]=1;} move[0].x=0;move[0].y=1; move[1].x=1;move[1].y=1; move[2].x=1;move[2].y=0; move[3].x=1;move[3].y=-1; move[4].x=0;move[4].y=-1; move[5].x=-1;move[5].y=-1; move[6].x=-1;move[6].y=0; move[7].x=-1;move[7

48、].y=1; short?path(); } 六、注意事項 （1）、將本實驗上?機調試、運行，注意調試過?程中出現(xiàn)的?問題； （2）、結合運行結?果，對程序進行?分析。 實驗八 串的基本運?算 一、實驗目的 （1）掌握串在順?序存儲結構?下的基本運?算； （2）掌握串模式?匹配的BF?算法和KM?P算法； （3）設計并掌握?算法，理解串的具?體應用，從而培養(yǎng)用?算法解決實?際問題的能?力。。 二、實驗要求 （1）、掌握串的邏?輯結構及順?序存儲結構?； （2）、熟練掌握串?的一些基本?運算。 三、實驗內容 （1）求兩個串的?最長公共子?串； （2）

49、串模式匹配?的BF算法?和KMP算?法實現(xiàn)。 （3）、實現(xiàn)兩個串?的最長公共?子串。 四、主要儀器設?備 PC機及T?C或VC 五、實驗步驟 方法一： 1、算法分析 該算法的基?本思想是在?主串s中取?從第i個字?符起并且長?度和串t相?等的子串和?t比較，若相等，則求得函數(shù)?值為i，否則，i增1直至?串中不存在?從i開始和?t相等的子?串，匹配失敗，返回0。 2、算法如下 #defin?e NAX 100 int index?(char s[ ],char t[ ],int start?) {int i,eq,m,n; char subch?[MAX]; m=

50、strle?n(s);n=strle?n(t); if(start?<=0||n==0||start?+n>m) retur?n(0); i=start?; while?(eq=sub(s,i,n,subch?)) /*sub為取?子串函數(shù)*/ if(strcm?p(t,subch?))break?; else i+ +; if(eq)retur?n(i+1); else retur?n(0);} 方法二： 1、算法分析 本算法不依?賴串的其他?操作的匹配?算法，在該算法中?設置兩個指?針i和j分?別指向主串?s和模式串?t中當前正?待比較的字?符位置。算法的基本?

51、思想是：從主串s的?第一個字符?(i=0)起和模式串?的第一個字?符(j=0)比較，若相等，則繼續(xù)逐個?比較后續(xù)字?符(i++,j++)，否則從主串?的第二個字?符起再重新?和模式串比?較(i返回到原?位置加1，j返回0)。依此類推，直至模式串?t的第一個?字符依次和?主串s 的一個連續(xù)?的字符序列?相等，則稱匹配成?功，否則稱匹配?失敗。該算法與方?法一所討論?的相同，只是前者是?以每一個位?置為始點，取出子串與?串t比較，而后者以每?一個位置為?出發(fā)點，與t比較，并且若匹配?成功比較到?t串結束，否則只需要?比較到某一?位置，即串s與串?t的字符不?相同。 2、算法如下 int ind

52、ex? (char s[],char t[],int start?) {int i,j,m,n; m=strle?n(s); n=strle?n(t); if(start?<=0||n==0||start?+n>m) retur?n(0); i=start?;j=0; while?(i=n) retur?n(i-n+1); else retur?n(0); } int next[9]; int Index?(char *S,char

53、 *T,int pos){ int 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]) retur?n i-T[0]; else retur?n 0; } int Index?_KMP(char *S,char *T,int pos){ int i=pos,j=1; while?(i<=S[0]&&j<=T[0]){ if(j==0||S[i]==T[j]){++i;++j;} else j=next

54、[j]; } if(j>T[0]) retur?n i-T[0]; else retur?n 0; } void get_n?ext(char *T,int next[]){ int i=1,j=0; next[1]=0; while?(i

55、 T[]={8,a,b,a,a,b,c,a,c}; /*for(i=0;i<=11;i++) print?f("%c ",S[i]);*/ get_n?ext(T,next); /*for(i=1;i<=8;i++) print?f("%d",next[i]);*/ i=Index?_KMP(S,T,3); print?f("%d",i); } 四、實驗內容 模式匹配 ①若串t是串?s的子串，則函數(shù)值為?s中第一個?這樣的子串?在主串中的?位置，否則函數(shù)值?為零。 ②串t非空。 五、實驗報告要?求 1、認真閱讀和?掌握本實驗?內容所給的?程序。 2、將本實驗上?機

56、運行。 3、結合運行結?果，對程序進行?分析。 4、試編寫從s?串中刪除一?個子串t的?算法，子串由起始?位置sta?rt和長度?len決定?。 實驗六 數(shù)組的應用? 一、實驗目的 1、使學生更進?一步掌握數(shù)?組的邏輯結?構和存儲結?構。 2、熟練特殊矩?陣的存儲結?構。 二、實驗前的準?備工作 1、掌握數(shù)組的?邏輯結構及?存儲結構。 2、掌握稀疏矩?陣的存儲結?構及一些運?算的實現(xiàn)。 三、實驗指導 1、算法分析 設多項式的?系數(shù)按冪次?由高到低的?順序存于一?數(shù)組中，多項式的冪?次存于另一?變量中。輾轉相除法?求兩個多項?式的最大公?因式的算法

57、?是：用其中的一?個多項式去?除另一個多?項式，然后將所得?余式變成除?式，原除式變成?被除式。如此反復相?除，直至余式為?零時，最后的除式?即為最大公?因式。 2、算法如下 int remai?nder(doubl?e *pa,int an,doubl?e *pb,int bn,doubl?e **q) {doubl?e x,y,*temp; int k,j; if(an0) {bn--;pb++;} i

58、f(*pb==0.0&&bn==0)break?; k=0;x=*pb; while?(k<=bn)pb[k++]/=x; for(k=0;k<=an-bn;k++) {x=pa[k]; for(j=0;j

59、知稀疏矩?陣M為m*n矩陣，稀疏矩陣和?N為n*p矩陣,求M*N。 五、實驗報告要?求 1、認真閱讀和?掌握本實驗?內容所給的?程序。 2、將本實驗上?機運行。 3、結合運行結?果，對程序進行?分析。 4、如果用三元?組形式表示?稀疏矩陣A?和B，試編寫一個?求解A＋B的算法。 實驗七 樹的應用 一、實驗目的 1、使學生熟練?掌握二叉樹?的邏輯結構?和存儲結構?。 2、熟練掌握二?叉樹的遍歷?。 二、實驗前的準?備工作 1、掌握樹的邏?輯結構。 2、掌握二叉樹?的邏輯結構?和存儲結構?。 3、掌握二叉樹?的遍歷。 三、實驗指導 1、算法分析 刪除算法

60、可?分下面三種?情況討論(假定：p指向要刪?除結點，f指向p的?雙親結點，且不失一般?性，設p是f的?右孩子。 ①若*p結點為葉?子結點，只需直接刪?除。即：將雙親結點?指向它的指?針，設置為空指?針（f->rch=NULL） ②若*p結點為單?分支結點，只需用它惟?一子樹的根?去繼承它的?位置。即：將雙親結點?原指向它原?指針，設置為指向?它的左孩子?或右孩子(若只有左子?樹，則f->rch=p->lch;若只有右子?樹，則f->rch =p->rch)。 ③若*p結點為雙?親分支結點?，為保證刪除?該結點后，該樹的中序?序列仍然是?按關鍵值遞?增有序。有如下解決?方法： 用左子樹

61、中?序遍歷的最?后一個結點?（左子樹的最?右結點）替換*p。首先，沿*p的左子樹?的右鏈，查找右指針?域為空的結?點*s；然后，用*s的數(shù)據(jù)替?換*p的數(shù)據(jù)；最后，刪除*s結點。因為，*s是其雙親?結點的右孩?子，并且s->rch為N?ULL。所以，若s->lch也為?空，則置*s雙親的右?指針為NU?LL，刪除*s;若s->lch不為?空，則置*s雙親的右?指針為s->lch，刪除*s。 2、算法如下 　struc?t node {int data; struc?t node *lch,*rch; }; typed?ef struc?t node NODE; NODE *d

62、el (NODE *root,int x) {NODE *p,*f,*s_f,*s; /*p為要刪除?結點，f為p的雙?親，s為p的左?子樹的最右?邊結點s_?f為s的雙?親*/ if(root==NULL)retur?n; f=NULL; p=root; while?(p!=NULL && p->data!=x) {if(p->data>x) if(p->lch!=NULL) {f=p;p=p->lch;} else break?; else if(p->rch!=NULL) {f=p;p=p->rch;} else break?; if(p==NULL

63、||p->data!=x)retur?n(root); if(p==root)retur?n; /*刪除根結點?*/ if(p->lch==NULL && p->rch==NULL) /*刪除葉子結?點*/ { if(f==NULL) {free(p);retur?n(NULL);} if(f->lch==p) f->lch=NULL; else f->rch=NULL; free(p); retur?n(root); if(p->lch==NULL) /*刪除單分支?結點　,沒有左子樹?*/ {if(f==NULL) {root=p->rch;free

64、(p);retur?n(root);} if(f->lch==p) f->lch=p->rch; else f->rch=p->rch; free(p); retur?n(root); if(p->rch==NULL) /*刪除單分支?結點　,沒有右子樹?*/ {if(f==NULL) {root=p->lch;free(p);retur?n(root);} if(f->lch==p) f->lch=p->lch; else f->rch=p->lch; free(p); retur?n(root); s_f=p;s=p->lch; /*刪除雙分支?結點*

65、/ while?(s->rch!=NULL) {s_f=s;s=s->rch;} p->data=s->data; if(s->lch==NULL) s_f->rch=NULL; else s_f->rch=s->lch; free(s);retur?n(root); } 四、實驗內容 1、二叉排序樹?的刪除 2、在二叉排序?樹中刪除結?點，首先要進行?查找，若查找成功?則刪除該結?點，但刪除之后?，不能破壞二?叉排序樹中?結點的關系?，即刪除后二?叉樹的中序?序列仍然是?按關鍵值遞?增有序。 五、實驗報告要?求 1、認真閱讀和?掌握本實驗?內容所給的?程序。 2、

66、將本實驗上?機運行。 3、結合運行結?果，對程序進行?分析。 4、寫出對二叉?樹進行中序?遍歷的非遞?歸算法并上?機運行。 實驗八 圖的應用 一、實驗目的 1、使學生熟悉?圖的存儲結?構。 2、使學生熟練?掌握圖的遍?歷。 二、實驗前的準?備工作 1、掌握圖的邏?輯結構、存儲結構。 2、熟練掌握圖?的遍歷。 3、了解最小生?成樹的概念?、性質。 三、實驗指導 1、算法分析 普里姆算法?是利用最小?生成樹的性?質：U是頂點V?的一個非空?子集，若(u,v)是一條具有?最小權值的?邊，其中u∈U,v∈V-U,則必存在一?棵包含邊(u,v)的最小生成?樹。 假設G=(V，E)是帶權的連?通無向圖，從u0∈V開始構造?G上最小生?成樹G’=(U，TE)，初始U={u0},TE=ф 。重復以下步?驟：