《算法語言與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)指導(dǎo)書》由會(huì)員分享，可在線閱讀，更多相關(guān)《算法語言與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)指導(dǎo)書（31頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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

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

3、院校?的男、女總分和團(tuán)?體總分，并輸出。 三、實(shí)驗(yàn)內(nèi)容 假設(shè)有A、B、C、D、E五個(gè)高校?進(jìn)行田徑比?賽，各院校的單?項(xiàng)成績(jī)均已?存入計(jì)算機(jī)?，并構(gòu)成一張?表，表的每一行?的形式為：項(xiàng)目名稱 性別 校名 成績(jī) 得分 編程統(tǒng)計(jì)各?院校的男、女總分和團(tuán)?體總分，并輸出。 四、主要儀器設(shè)?備 PC機(jī)及T?C或VC 五、實(shí)驗(yàn)步驟 #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); } 六、注意事項(xiàng) （1）、將本實(shí)驗(yàn)上?機(jī)調(diào)試、運(yùn)行，注意調(diào)試過?程中出現(xiàn)的?問題； （2）、結(jié)合運(yùn)行結(jié)?果，對(duì)程序進(jìn)行?分析。 實(shí)驗(yàn)二 文件 一、實(shí)驗(yàn)?zāi)康? （1）學(xué)會(huì)使用文?件打開、關(guān)閉、讀、寫等文件操?作函數(shù)； （2）學(xué)會(huì)用緩沖?文件系統(tǒng)對(duì)?文件進(jìn)行簡(jiǎn)?單的操作； （3）設(shè)計(jì)并掌握?算法，學(xué)會(huì)分析算?法并培養(yǎng)用?算法解決實(shí)?際問題的能?力。 二、實(shí)驗(yàn)要求 （1）將這10個(gè)?學(xué)生信息存?入

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

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

14、法； （2）掌握順序表?上的插入、刪除和查找?操作。 二、實(shí)驗(yàn)要求 （1）設(shè)計(jì)相應(yīng)的?兩級(jí)測(cè)試數(shù)?據(jù)，一組為整形?數(shù)據(jù)，一組為字符?數(shù)據(jù)，個(gè)數(shù)不少于?10個(gè)； （2）在第5個(gè)位?置上插入一?個(gè)數(shù)或字符?； （3）將第7個(gè)元?素刪除； （4）查找值為？的元素，若存在將其?輸出，否則打印沒?有該元素。 三、實(shí)驗(yàn)內(nèi)容 用C語言數(shù)?組實(shí)現(xiàn)在順?序表上進(jìn)行?插入、刪除和查找?操作。 四、主要儀器設(shè)?備 PC機(jī)及T?C或VC 五、實(shí)驗(yàn)步驟 （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]); } 六、注意事項(xiàng) （1）、將本實(shí)驗(yàn)上?機(jī)調(diào)試、運(yùn)行，注意調(diào)試過?程中出現(xiàn)的?問題； （2）、結(jié)合運(yùn)行結(jié)?果，對(duì)程序進(jìn)行?分析。 實(shí)驗(yàn)四 鏈表基本操?作 一、實(shí)驗(yàn)?zāi)康? （1）、幫助讀者復(fù)?習(xí)C語言程?序設(shè)計(jì)中的?知識(shí)。 （2）、熟悉線性表?的基本運(yùn)算?在鏈?zhǔn)酱鎯?chǔ)?結(jié)構(gòu)上的實(shí)?現(xiàn)。 二、實(shí)驗(yàn)要求 （1）、掌握線性表?的邏輯結(jié)構(gòu)?。 （2）、掌握線性表?的鏈?zhǔn)酱鎯?chǔ)?結(jié)構(gòu)。 （3）、熟練掌握線?性表的插入?、刪除、按序號(hào)查找?和按值查找?操作等操作?。 三、實(shí)驗(yàn)內(nèi)容 用C語言編?程實(shí)現(xiàn)單鏈?表的建

18、立、插入、刪除、按序號(hào)查找?和按值查找?操作算法。 四、主要儀器設(shè)?備 PC機(jī)及T?C或VC 五、實(shí)驗(yàn)步驟 1、算法分析 ①為使算法的?時(shí)間復(fù)雜度?為O(n+m)只能采用“平移指針，一次掃描”的方法，于是設(shè)兩個(gè)?指針分別指?向兩個(gè)線性?表表頭。 ②為使合并后?仍為一個(gè)有?序表，需對(duì)指針?biāo)?指結(jié)點(diǎn)的數(shù)?據(jù)域進(jìn)行比?較。 ③要使合并后?的有序表為?遞減有序表?，比較后選出?較小的一個(gè)?將其從原鏈?表中取出插?入到新表的?表首。 ④指針后移，重復(fù)②，③步，直到其中一?個(gè)表結(jié)束，將尚未結(jié)束?表的元素依?次取出插入?新表。 ⑤為減少頭指?針的變化，采用帶有頭?結(jié)點(diǎn)的鏈表?。 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); } 六、注意事項(xiàng) （1）、將本實(shí)驗(yàn)上?機(jī)調(diào)試、運(yùn)行，注意調(diào)試過?程中出現(xiàn)的?問題； （2）、結(jié)合運(yùn)行結(jié)?果，對(duì)程序進(jìn)行?分析。 實(shí)驗(yàn)五 一元稀疏多?項(xiàng)式運(yùn)算 一、實(shí)驗(yàn)?zāi)康? 設(shè)計(jì)并掌握?算法，學(xué)會(huì)分析算?法并培養(yǎng)用?算法解決實(shí)?際問題的能?力。 二、實(shí)驗(yàn)要求 （1）用帶頭結(jié)點(diǎn)?的單鏈表做?存

22、儲(chǔ)結(jié)構(gòu)； （2）構(gòu)造兩個(gè)多?項(xiàng)式，實(shí)現(xiàn)相加和?相乘。 三、實(shí)驗(yàn)內(nèi)容 用C語言編?程實(shí)現(xiàn)一元?稀疏多項(xiàng)式?加、減、乘運(yùn)算。 四、主要儀器設(shè)?備 PC機(jī)及T?C或VC 五、實(shí)驗(yàn)步驟 #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); } 六、注意事項(xiàng) （1）、將本實(shí)驗(yàn)上?機(jī)調(diào)試、運(yùn)行，注意調(diào)試過?程中出現(xiàn)的?問題； （2）、結(jié)合運(yùn)行結(jié)?果，對(duì)程序進(jìn)行?分析。 實(shí)驗(yàn)六 棧的應(yīng)用 一、實(shí)驗(yàn)?zāi)康? 1、使學(xué)生深入?了解堆棧的?特性，以便在遇到?實(shí)際問題時(shí)?靈活運(yùn)用堆?棧知識(shí)。 2、鞏固堆棧數(shù)?據(jù)結(jié)構(gòu)的構(gòu)?造方法。 二、實(shí)驗(yàn)要求 1、掌握堆棧的?邏輯結(jié)構(gòu)和?存儲(chǔ)結(jié)構(gòu)。 2、熟練掌握堆?棧的出棧、入棧等操作?。 三、實(shí)驗(yàn)內(nèi)容 用C語言編?程實(shí)現(xiàn)數(shù)制?

33、轉(zhuǎn)換和算術(shù)?表達(dá)式的求?值。 四、主要儀器設(shè)?備 PC機(jī)及T?C或VC 五、實(shí)驗(yàn)步驟 1、算法分析 將十進(jìn)制數(shù)?N和其它d?進(jìn)制數(shù)的轉(zhuǎn)?換是計(jì)算機(jī)?實(shí)現(xiàn)計(jì)算的?基本問題，其解決方案?很多，其中最簡(jiǎ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 　　從中我們可?以看出，最先產(chǎn)生的?余數(shù)4是轉(zhuǎn)?換結(jié)果的最?低位，這正好符合?棧的特性即?后進(jìn)先出的?特性。所以可以用?順序棧來

34、模?擬這個(gè)過程?。 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、和?存儲(chǔ)結(jié)構(gòu)。 （2）、熟練掌握隊(duì)?列的出隊(duì)、入隊(duì)等操作?。 三、實(shí)驗(yàn)內(nèi)容 用C語言編?程實(shí)現(xiàn)迷宮?問題求解。 四、主要儀器設(shè)?備 PC機(jī)及T?C或VC 五、實(shí)驗(yàn)步驟 （1）、算法分析 迷宮的定義?如下： #defin?e m 6 /* 迷宮的實(shí)際?行 */ #defin?e n 8 /* 迷宮的實(shí)際?列 */ int maze [m+2][n+2] ; maze[i][j]=0或1; 其中：0表示通路?，1表示不通?，當(dāng)從某點(diǎn)向?下試探時(shí)，中間點(diǎn)有8?個(gè)方向可以?試探，（見圖3.4）而四個(gè)角點(diǎn)?有3個(gè)方向?，其它邊緣點(diǎn)?有5個(gè)方向?，為使問題

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

43、． 棧初始化; 2． 將入口點(diǎn)坐?標(biāo)及到達(dá)該?點(diǎn)的方向（設(shè)為－１）入棧 3． while? (棧不空) { 棧頂元素＝＞（x , y , d） 出棧 ; 求出下一個(gè)?要試探的方?向d++ ; while? （還有剩余試?探方向時(shí)） { if （d方向可走?） 則 { （x , y , d）入棧 ; 求新點(diǎn)坐標(biāo)? (i, j ) ; 將新點(diǎn)（i , j）切換為當(dāng)前?點(diǎn)（x , y） ; if ( (x ,ｙ)= =(ｍ,n) ) 結(jié)束 ; 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(); } 六、注意事項(xiàng) （1）、將本實(shí)驗(yàn)上?機(jī)調(diào)試、運(yùn)行，注意調(diào)試過?程中出現(xiàn)的?問題； （2）、結(jié)合運(yùn)行結(jié)?果，對(duì)程序進(jìn)行?分析。 實(shí)驗(yàn)八 串的基本運(yùn)?算 一、實(shí)驗(yàn)?zāi)康? （1）掌握串在順?序存儲(chǔ)結(jié)構(gòu)?下的基本運(yùn)?算； （2）掌握串模式?匹配的BF?算法和KM?P算法； （3）設(shè)計(jì)并掌握?算法，理解串的具?體應(yīng)用，從而培養(yǎng)用?算法解決實(shí)?際問題的能?力。。 二、實(shí)驗(yàn)要求 （1）、掌握串的邏?輯結(jié)構(gòu)及順?序存儲(chǔ)結(jié)構(gòu)?； （2）、熟練掌握串?的一些基本?運(yùn)算。 三、實(shí)驗(yàn)內(nèi)容 （1）求兩個(gè)串的?最長(zhǎng)公共子?串； （2）

49、串模式匹配?的BF算法?和KMP算?法實(shí)現(xiàn)。 （3）、實(shí)現(xiàn)兩個(gè)串?的最長(zhǎng)公共?子串。 四、主要儀器設(shè)?備 PC機(jī)及T?C或VC 五、實(shí)驗(yàn)步驟 方法一： 1、算法分析 該算法的基?本思想是在?主串s中取?從第i個(gè)字?符起并且長(zhǎng)?度和串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、算法分析 本算法不依?賴串的其他?操作的匹配?算法，在該算法中?設(shè)置兩個(gè)指?針i和j分?別指向主串?s和模式串?t中當(dāng)前正?待比較的字?符位置。算法的基本?

51、思想是：從主串s的?第一個(gè)字符?(i=0)起和模式串?的第一個(gè)字?符(j=0)比較，若相等，則繼續(xù)逐個(gè)?比較后續(xù)字?符(i++,j++)，否則從主串?的第二個(gè)字?符起再重新?和模式串比?較(i返回到原?位置加1，j返回0)。依此類推，直至模式串?t的第一個(gè)?字符依次和?主串s 的一個(gè)連續(xù)?的字符序列?相等，則稱匹配成?功，否則稱匹配?失敗。該算法與方?法一所討論?的相同，只是前者是?以每一個(gè)位?置為始點(diǎn)，取出子串與?串t比較，而后者以每?一個(gè)位置為?出發(fā)點(diǎn)，與t比較，并且若匹配?成功比較到?t串結(jié)束，否則只需要?比較到某一?位置，即串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); } 四、實(shí)驗(yàn)內(nèi)容 模式匹配 ①若串t是串?s的子串，則函數(shù)值為?s中第一個(gè)?這樣的子串?在主串中的?位置，否則函數(shù)值?為零。 ②串t非空。 五、實(shí)驗(yàn)報(bào)告要?求 1、認(rèn)真閱讀和?掌握本實(shí)驗(yàn)?內(nèi)容所給的?程序。 2、將本實(shí)驗(yàn)上?機(jī)

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

57、?是：用其中的一?個(gè)多項(xiàng)式去?除另一個(gè)多?項(xiàng)式，然后將所得?余式變成除?式，原除式變成?被除式。如此反復(fù)相?除，直至余式為?零時(shí)，最后的除式?即為最大公?因式。 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。 五、實(shí)驗(yàn)報(bào)告要?求 1、認(rèn)真閱讀和?掌握本實(shí)驗(yàn)?內(nèi)容所給的?程序。 2、將本實(shí)驗(yàn)上?機(jī)運(yùn)行。 3、結(jié)合運(yùn)行結(jié)?果，對(duì)程序進(jìn)行?分析。 4、如果用三元?組形式表示?稀疏矩陣A?和B，試編寫一個(gè)?求解A＋B的算法。 實(shí)驗(yàn)七 樹的應(yīng)用 一、實(shí)驗(yàn)?zāi)康? 1、使學(xué)生熟練?掌握二叉樹?的邏輯結(jié)構(gòu)?和存儲(chǔ)結(jié)構(gòu)?。 2、熟練掌握二?叉樹的遍歷?。 二、實(shí)驗(yàn)前的準(zhǔn)?備工作 1、掌握樹的邏?輯結(jié)構(gòu)。 2、掌握二叉樹?的邏輯結(jié)構(gòu)?和存儲(chǔ)結(jié)構(gòu)?。 3、掌握二叉樹?的遍歷。 三、實(shí)驗(yàn)指導(dǎo) 1、算法分析 刪除算法

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

61、中?序遍歷的最?后一個(gè)結(jié)點(diǎn)?（左子樹的最?右結(jié)點(diǎn)）替換*p。首先，沿*p的左子樹?的右鏈，查找右指針?域?yàn)榭盏慕Y(jié)?點(diǎn)*s；然后，用*s的數(shù)據(jù)替?換*p的數(shù)據(jù)；最后，刪除*s結(jié)點(diǎn)。因?yàn)椋?s是其雙親?結(jié)點(diǎn)的右孩?子，并且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為要?jiǎng)h除?結(jié)點(diǎn)，f為p的雙?親，s為p的左?子樹的最右?邊結(jié)點(diǎn)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; /*刪除根結(jié)點(diǎn)?*/ if(p->lch==NULL && p->rch==NULL) /*刪除葉子結(jié)?點(diǎn)*/ { 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) /*刪除單分支?結(jié)點(diǎn)　,沒有左子樹?*/ {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) /*刪除單分支?結(jié)點(diǎn)　,沒有右子樹?*/ {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; /*刪除雙分支?結(jié)點(diǎn)*

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); } 四、實(shí)驗(yàn)內(nèi)容 1、二叉排序樹?的刪除 2、在二叉排序?樹中刪除結(jié)?點(diǎn)，首先要進(jìn)行?查找，若查找成功?則刪除該結(jié)?點(diǎn)，但刪除之后?，不能破壞二?叉排序樹中?結(jié)點(diǎn)的關(guān)系?，即刪除后二?叉樹的中序?序列仍然是?按關(guān)鍵值遞?增有序。 五、實(shí)驗(yàn)報(bào)告要?求 1、認(rèn)真閱讀和?掌握本實(shí)驗(yàn)?內(nèi)容所給的?程序。 2、

66、將本實(shí)驗(yàn)上?機(jī)運(yùn)行。 3、結(jié)合運(yùn)行結(jié)?果，對(duì)程序進(jìn)行?分析。 4、寫出對(duì)二叉?樹進(jìn)行中序?遍歷的非遞?歸算法并上?機(jī)運(yùn)行。 實(shí)驗(yàn)八 圖的應(yīng)用 一、實(shí)驗(yàn)?zāi)康? 1、使學(xué)生熟悉?圖的存儲(chǔ)結(jié)?構(gòu)。 2、使學(xué)生熟練?掌握?qǐng)D的遍?歷。 二、實(shí)驗(yàn)前的準(zhǔn)?備工作 1、掌握?qǐng)D的邏?輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)。 2、熟練掌握?qǐng)D?的遍歷。 3、了解最小生?成樹的概念?、性質(zhì)。 三、實(shí)驗(yàn)指導(dǎo) 1、算法分析 普里姆算法?是利用最小?生成樹的性?質(zhì)：U是頂點(diǎn)V?的一個(gè)非空?子集，若(u,v)是一條具有?最小權(quán)值的?邊，其中u∈U,v∈V-U,則必存在一?棵包含邊(u,v)的最小生成?樹。 假設(shè)G=(V，E)是帶權(quán)的連?通無向圖，從u0∈V開始構(gòu)造?G上最小生?成樹G’=(U，TE)，初始U={u0},TE=ф 。重復(fù)以下步?驟：