算法與數(shù)據(jù)結(jié)構(gòu)實驗報告

1、金阪料扶學(xué)院學(xué)生實驗報告冊課程名稱：算法與數(shù)據(jù)結(jié)構(gòu)實驗項目名稱：順序表實驗學(xué)時:2同組學(xué)生姓名：實驗地點：工科樓A205實驗日期：2013年10月16日實驗成績：批改教師：批改時間：實驗1順序表一、實驗?zāi)康暮鸵笳莆枕樞虮淼亩ㄎ?、插入、刪除等操作。二、實驗儀器和設(shè)備TurboC三、實驗內(nèi)容與過程（含程序清單及流程圖）1、必做題（1）編寫程序建立一個順序表，并逐個輸出順序表中所有數(shù)據(jù)元素的值。編寫主函數(shù)測試結(jié)果。（2）編寫順序表定位操作子函數(shù)，在順序表中查找是否存在數(shù)據(jù)元素x。如果存在，返回順序表中和x值相等的第1個數(shù)據(jù)元素的序號（序號從0開始編號）；如果不存在，返回1。編寫主函數(shù)測試結(jié)果。（3

2、）在遞增有序的順序表中插入一個新結(jié)點x,保持順序表的有序性。解題思路：首先查找插入的位置，再移位，最后進(jìn)行插入操作；從第一個元素開始找到第一個大于該新結(jié)點值x的元素位置i即為插入位置；然后將從表尾開始依次將元素后移一個位置直至元素i；最后將新結(jié)點x插入到i位置。（4）刪除順序表中所有等于X的數(shù)據(jù)元素。2、選做題（5）已知兩個順序表A和B按元素值遞增有序排列，要求寫一算法實現(xiàn)將A和B歸并成一個按元素值遞減有序排列的順序表（允許表中含有值相同的元素）。程序清單：1、#definemaxsize100typedefstructintdatamaxsize;intlast;sequenlist;mai

3、n（）inti;sequenlistl=2,5,6,8,2,8,4,3,7;printf（"nThelistis:"）;for（i=0;i<=;i+）printf（"%2d",i）;2、#definemaxsize100typedefstructintdatamaxsize;intlast;sequenlist;main()intx,i,s=-1;sequenlistl=2,5,6,7,9,8,4,3,7;printf("nThelistis:");for(i=0;i<=;i+)printf("%2d"

4、,i);printf("nPleaseinputthenumber:");scanf("%d",&x);for(i=0;i<=;i+)ifi=x)s=i;break;printf("%d",s);3、#definemaxsize100typedefstructintdatamaxsize;intlast;sequenlist;main()inti,x,j;sequenlistl=1,3,5,6,7,9,5;printf("nThelistis:");for(i=0;i<=;i+)printf(&

5、quot;%2d",i);printf("nInputtheinsertnumber:");scanf("%d",&x);for(i=1;i<=;i+)ifi-1>x)break;for(j=;j>=i-1;j-)j+1=j;i-1=x;+;printf("thelistafterinsertionis:n");for(j=0;j<=;j+)printf("%3d",j);4、#definemaxsize100typedefstructintdatamaxsize;intl

6、ast;sequenlist;main()inti,j,x=0,k=0;sequenlistL=1,3,5,7,2,4,6,8,2,9,9;printf("nThelistis:");for(i=0;i<=;i+)printf("%3d",i);printf("nPleaseinputanumberx:");scanf("%d",&x);for(i=1;i<=+1;i+)ifi-1=x)for(j=i;j<=+1;j+)j-1=j;i-;k=1;if(k=1)printf("Th

7、elistafterdeletionis:n");for(j=0;j<=;j+)printf("%3d",j);elseprintf("Notfound!n");四、實驗結(jié)果與分析（程序運行結(jié)果及其分析）1、輸出結(jié)果：Thelistis：256828432、輸出結(jié)果：Thelistis：25679843Pleaseinputthenumber：85Thelistis：25679843Pleaseinputthenumber：1-13、輸出結(jié)果：Thelistis：135679Inputtheinsertnumber：8Thelistaft

8、erinsertionis：13567894、輸出結(jié)果：Thelistis：1357246829Pleaseinputanumberx：5Thelistafterdeletionis：137246829Thelistis：1357246829Pleaseinputanumberx：11Notfound！五、實驗體會（遇到問題及解決辦法，編程后的心得體會）遇到問題：讀取數(shù)據(jù)元素時，誤將=寫成=，導(dǎo)致錯誤。實驗過程中，順序表的賦值沒有弄懂，以致輸出多個0或者少輸出。格式運算符也要正確控制，否則系統(tǒng)會停止工作。實驗體會：通過實驗掌握了順序表的基本操作，如初始化、插入、讀取元素、刪除等等。并了解到線性

9、表順序存儲結(jié)構(gòu)的特點，即邏輯關(guān)系上相鄰的兩個元素在物理位置上也相鄰，然而從另一方面來看，在做插入和刪除時需要移動大量元素。本次實驗基本完成了實驗要求的目的，順序表的初始化，定義，插入，查找等，更好的了解了順序表基本操作的算法，以及更直觀的了解了數(shù)據(jù)結(jié)構(gòu)在C語言環(huán)境下的體現(xiàn)。工科樓A205實驗項目名稱：單鏈表實驗學(xué)時:同組學(xué)生姓名：實驗地點:實驗日期：2013年10月23日實驗成績:批改教師：批改時間:實驗2單鏈表一、實驗?zāi)康暮鸵?、實驗?zāi)康恼莆諉捂湵淼亩ㄎ?、插入、刪除等操作。2、實驗要求(1) 注意鏈表的空間是動態(tài)分配的，某結(jié)點不用之后要及時進(jìn)行物理刪除，以便釋放其內(nèi)存空間。(2) 鏈表不能

10、實現(xiàn)直接定位，一定注意指針的保存，防止丟失。二、實驗儀器和設(shè)備TurboC三、實驗內(nèi)容與過程(含程序清單及流程圖)1、必做題(1)編寫程序建立一個單鏈表，并逐個輸出單鏈表中所有數(shù)據(jù)元素。(2) 在遞增有序的單鏈表中插入一個新結(jié)點x,保持單鏈表的有序性。解題思路：首先查找插入的位置然后進(jìn)行插入操作；從第一個結(jié)點開始找到第一個大于該新結(jié)點值的結(jié)點即為插入位置；然后在找到的此結(jié)點之前插入新結(jié)點；注意保留插入位置之前結(jié)點的指針才能完成插入操作。(3) 編寫實現(xiàn)帶頭結(jié)點單鏈表就地逆置的子函數(shù),并編寫主函數(shù)測試結(jié)果。2、選做題已知指針LA和LB分別指向兩個無頭結(jié)點單鏈表的首元結(jié)點。要求編一算法實現(xiàn)，從表L

11、A中刪除自第i個元素起共len個元素后，將它們插入到表LB中第j個元素之前。程序清單：1、#include<>typedefintdatattype;typedefstructnodechardata;structnode*next;linklist;main()charch;linklist*head,*s,*r,*p;head=malloc(sizeof(linklist);r=head;scanf("%c",&ch);while(ch!='$')s=malloc(sizeof(linklist);s->data=ch;r-&g

12、t;next=s;r=s;scanf("%c",&ch);r->next=NULL;r=head->next;while(r!=NULL)printf("%c",r->data);r=r->next;2、#include""#include""typedefstructnodeintdata;structnode*next;linklist;main()intx,y;linklist*head,*s,*r,*p,*q,*m,*n;clrscr();head=malloc(sizeof

13、(linklist);r=head;printf("inputtheordernumbers:");scanf("%d",&x);while(x!=0)s=malloc(sizeof(linklist);s->data=x;r->next=s;r=s;scanf("%d",&x);r->next=NULL;printf("Pleaseinputtheinsertvalue:");scanf("%d",&y);p=head->next;while(p

14、!=NULL)if(p->data<y)p=p->next;elsebreak;q=malloc(sizeof(linklist);q->data=y;m=head;while(m->next!=p)m=m->next;q->next=p;m->next=q;n=head->next;printf("thelistare:");while(n!=NULL)printf("%3d",n->data);n=n->next;3、#include""#include"

15、"typedefstructnodeintdata;structnode*next;linklist;main()inta;linklist*head,*s,*r,*p,*q,*t;clrscr();head=malloc(sizeof(linklist);r=head;printf("Inputsomenumbers:");scanf("%d",&a);while(a!=0)s=malloc(sizeof(linklist);s->data=a;r->next=s;r=s;scanf("%d",&

16、;a);r->next=NULL;printf("nThelinklistbeforechangedis:n");p=head->next;while(p)printf("%d",p->data);p=p->next;p=head->next;q=p->next;while(q!=NULL)t=q->next;q->next=p;p=q;q=t;head->next->next=NULL;head->next=p;printf("nAfterchanged:n");p=

17、head->next;while(p!=NULL)printf("%d",p->data);p=p->next;四、實驗結(jié)果與分析(程序運行結(jié)果及其分析1、輸入：123abc$輸出結(jié)果：123abc2、輸入：inputtheordernumbers:1357890Pleaseinputtheinsertvalue:：4輸出結(jié)果：thelistare:13457893、輸入：Inputsomenumbers:134580輸出結(jié)果：Thelinklistbeforechangedis:13458Afterchanged:85431五、實驗體會（遇到問題及解決辦

18、法，編程后的心得體會）遇到問題：編寫成功后運行時，沒有加入$導(dǎo)致程序運行不成功，不能夠退出。后注意到這個問題才繼續(xù)運行下去。實驗體會：在編寫程序時，設(shè)置了結(jié)束字符一定要牢牢記住，并且在輸入時觀察仔細(xì)類型是什么，以及是否是輸入一串有順序的數(shù)字，編寫成功不難，但是要規(guī)范格式，不能僅僅以完成程序為目的。而完成這一章的實驗也讓我了解了，順序表便于查找不便于插入刪除，而鏈表恰恰相反，鏈表的插入刪除只需要移動指針，而順序表要從后往前依次移動，二者各有優(yōu)劣。實驗項目名稱：堆棧和隊列實驗學(xué)時:2同組學(xué)生姓名：實驗地點：工科樓A205實驗日期：2013年10月30日實驗成績：批改教師：批改時間：實驗3堆棧和隊列

19、一、實驗?zāi)康暮鸵螅?）掌握應(yīng)用棧解決問題的方法。（2）掌握利用棧進(jìn)行表達(dá)式求和的算法。（3）掌握隊列的存儲結(jié)構(gòu)及基本操作實現(xiàn)，并能在相應(yīng)的應(yīng)用問題中正確選用它們。二、實驗儀器和設(shè)備TurboC三、實驗內(nèi)容與過程（含程序清單及流程圖）1、必做題（1）判斷一個算術(shù)表達(dá)式中開括號和閉括號是否配對。（2）測試“漢諾塔”問題。（3）假設(shè)稱正讀和反讀都相同的字符序列為”回文”，試寫一個算法判別讀入的一個以''為結(jié)束符的字符序列是否是“回文”。2、選做題在順序存儲結(jié)構(gòu)上實現(xiàn)輸出受限的雙端循環(huán)隊列的入列和出列算法。設(shè)每個元素表示一個待處理的作業(yè)，元素值表示作業(yè)的預(yù)計時間。入隊列采取簡化的短作

20、業(yè)優(yōu)先原則，若一個新提交的作業(yè)的預(yù)計執(zhí)行時間小于隊頭和隊尾作業(yè)的平均時間，則插入在隊頭，否則插入在隊尾。程序清單：1、typedefintdatatype;#defineM100typedefstructchardataM;inttop;seqstack;main（）charstrM;intresult=0,i=0;seqstacks;=0;gets（str）;while（stri!='0'）if（stri='（'）+;='('if(stri=')')if=0)result=1;break;else;i+;if(result=0&

21、amp;&=0)printf("Match!n");elseif(result=1)printf("Missingleft!n");elseif>0)printf("Missingright!n");2、#include<>voidhanoi(intn,chara,charb,charc)if(n=1)printf("nMovedisk%dfrompile%ctopile%c",n,a,c);elsehanoi(n-1,a,c,b);printf("nMovedisk%dfrom

22、pile%ctopile%c",n,a,c);hanoi(n-1,b,a,c);voidmain()intn;clrscr();printf("nPleaseenterthenumberofdiskstobemoved:");scanf("%d",&n);hanoi(n,'A','B','C');3、#include<>#defineM100typedefstructchardataM;inttop;seqstack;main()charstrM;inti=0,n;seqsta

23、cks;=0;gets(str);while(stri!='')i+;if(i=1)printf("Yesn");return;n=i;for(i=0;i<n/2;i+)+;=stri;i=i-1;if(n%2=0)i+;elsei=i+2;while(i<n&&=stri)i+;if(i=n)printf("Yesn");elseprintf("Non");四、實驗結(jié)果與分析(程序運行結(jié)果及其分析1、輸入：(a)輸出結(jié)果：Match！輸入：（a輸出結(jié)果：Missingright！輸入：a）

24、輸出結(jié)果：Missingleft！2、輸入：3輸出結(jié)果：Movedisk1frompileAtopileCMovedisk2frompileAtopileBMovedisk1frompileCtopileBMovedisk3frompileAtopileCMovedisk1frompileBtopileAMovedisk2frompileBtopileCMovedisk1frompileAtopileC3、輸入：qwewq輸出結(jié)果：Yes輸入：qwerewr輸出結(jié)果No五、實驗體會（遇到問題及解決辦法，編程后的心得體會）遇到問題：在本章棧和隊列中編程，有許多的if語句，編寫時一不小心就會少加一

25、個花括號，以致編寫不成功。在本章漢諾塔問題中，使用了棧以及函數(shù)的遞歸，這其中的過程一直不是很了解，在經(jīng)過老師的講解后，理解了大致過程。實驗體會：遞歸函數(shù)是編程中經(jīng)常會用到的一種函數(shù)，它可以實現(xiàn)許多我們在平時言語和解釋上解決不了的問題，我們需要理解并且可以熟練的使用它，這對我們之后的編程會有很大的幫助。而漢諾塔利用棧是一種很經(jīng)典的遞歸的算法，這讓我們理解棧和遞歸。實驗項目名稱：串實驗學(xué)時：2同組學(xué)生姓名：實驗地點：工科樓A205實驗日期：2013年11月6日實驗成績：批改教師：批改時間：實驗4串一、實驗?zāi)康暮鸵笳莆沾拇鎯皯?yīng)用。二、實驗儀器和設(shè)備TurboC三、實驗內(nèi)容與過程(含程序清單及流

26、程圖)1、必做題(1) 編寫輸出字符串s中值等于字符ch的第一個字符的函數(shù)，并用主函數(shù)測試結(jié)果。(2) 編寫輸出字符串s中值等于字符ch的所有字符的函數(shù)，并用主函數(shù)測試結(jié)果。解題思路：可以將第一題程序改進(jìn)成一個子函數(shù)，在本題中循環(huán)調(diào)用。(3) 設(shè)字符串采用單字符的鏈?zhǔn)酱鎯Y(jié)構(gòu)，編程刪除串s從位置i開始長度為k的子串。2、選做題假設(shè)以鏈結(jié)構(gòu)表示串，編寫算法實現(xiàn)將串S插入到串T中某個字符之后，若串T中不存在這個字符，則將串S聯(lián)接在串T的末尾。提示：為提高程序的通用性，插入位置字符應(yīng)設(shè)計為從鍵盤輸入。程序清單：1、#definemaxsize100typedefstructcharchmaxsize

27、;intcurlen;seqstring;main()inti;charch;seqstrings="asdfghg",6;for(i=0;i<i+)printf("%c",i);printf("nPleaseinputaacharacterch:");scanf("%c",&ch);for(i=0;i<i+)ifi=ch)printf("ch=%d=%cn",i,i);break;if(i>=printf("Notfind!n");2、#defin

28、emaxsize100typedefstructcharchmaxsize;intcurlen;seqstring;main()inti,flag=0;charch;seqstrings="abadeag",6;for(i=0;i<i+)printf("%c",i);printf("nPleaseinputaacharacterch:");scanf("%c",&ch);for(i=0;i<i+)ifi=ch)printf("ch=%d=%cn",i,i);flag+;if(

29、flag=0)printf("Notfind!n");3、#include<>#include<>typedefstructlinknodechardata;structlinknode*next;linkstring;main()linkstring*head,*s,*r,*p,*q;inti,b,l,k=0;charch;head=NULL;r=NULL;printf("nNexttocreatLinkString,$asendmarkn");ch=getchar();while(ch!='$')s=mallo

30、c(sizeof(linkstring);s->data=ch;if(head=NULL)head=s;elser->next=s;r=s;ch=getchar();if(r!=NULL)r->next=NULL;q=head;while(q)printf("%c",q->data);q=q->next;k+;printf("nNowinputtwointforstratpostionandlengthfordeleted:");scanf("%d%d",&b,&l);if(b>k-

31、1|b+l>k)printf("Error!n");return;p=head;for(i=0;i<b-1;i+)p=p->next;printf("%c%d%d%dn",p->data,b,l,k);for(i=b-1;i<b+l-1;i+)q=p->next;p->next=q->next;free(q);q=head;while(q)printf("%c",q->data);q=q->next;printf（"n"）;四、實驗結(jié)果與分析（程序運行結(jié)果

32、及其分析）1、輸入：s輸出結(jié)果：ch=1=s2、輸入：a輸出結(jié)果：ch=0=ach=2=ach=5=a3、輸入：asdfghjkl$25輸出結(jié)果：s259askl五、實驗體會（遇到問題及解決辦法，編程后的心得體會）實驗體會：本章第一題可以作為第二題的子函數(shù)，使用調(diào)用；也可以從開頭查找對應(yīng)的字符到結(jié)尾，最后全部輸出。前兩題使用順序串，后面一題是鏈串。串的存儲結(jié)構(gòu)包含有順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。在串的順序存儲結(jié)構(gòu)中，表示串的長度通常有兩種方法：一種方法是設(shè)置一個串的長度參數(shù)，其優(yōu)點在于便于在算法中用長度參數(shù)控制循環(huán)過程；另一種方法是在串值得末尾添加結(jié)束標(biāo)記，此種方法的優(yōu)點在于便于系統(tǒng)自動實現(xiàn)。在

33、串的存儲過程中，串值用雙引號引起來，系統(tǒng)將自動在串值得末尾添加結(jié)束標(biāo)記0字符。工科樓A205實驗項目名稱：二叉樹實驗學(xué)時:同組學(xué)生姓名：實驗地點:實驗日期：2013年11月13日實驗成績:批改教師：批改時間:實驗5二叉樹一、實驗?zāi)康暮鸵螅?）掌握二叉樹的生成，以及前、中、后序遍歷算法。（2）掌握應(yīng)用二叉樹遞歸遍歷思想解決問題的方法。二、實驗儀器和設(shè)備TurboC三、實驗內(nèi)容與過程（含程序清單及流程圖）1、必做題（1）建立一棵二叉樹。對此樹進(jìn)行前序遍歷、中序遍歷及后序遍歷，輸出遍歷序列。（2）在第一題基礎(chǔ)上，求二叉樹中葉結(jié)點的個數(shù)。（3）在第一題基礎(chǔ)上，求二叉樹中結(jié)點總數(shù)。（4）在第一題基礎(chǔ)上

34、，求二叉樹的深度。2、選做題已知一棵完全二叉樹存于順序表sa中，1.存儲結(jié)點的值。試編寫算法由此順序存儲結(jié)構(gòu)建立該二叉樹的二叉鏈表。解題思路：根據(jù)完全二叉樹順序存儲的性質(zhì)來確定二叉樹的父子關(guān)系即“還原”了二叉樹，之后再按照二叉樹二叉鏈表的構(gòu)造方法進(jìn)行建立。完全二叉樹順序存儲的一個重要性質(zhì)為，第i個結(jié)點的左孩子是編號為2i的結(jié)點，第i個結(jié)點的右孩子是編號為2i+1的結(jié)點。程序清單：1（1）#include<>#include<>#definemaxsize100typedefstructnodechardata;structnode*lchild,*rchild;bitr

35、ee;bitree*Qmaxsize;bitree*Creatree（）charch;intfront,rear;bitree*root,*s;root=NULL;front=1;rear=0;printf("NowCreatthebitree,inputbaseingtheordertoptobottom,lefttoright:n");ch=getchar();while(ch!='#')s=NULL;if(ch!='')s=malloc(sizeof(bitree);s->data=ch;s->lchild=NULL;s-&

36、gt;rchild=NULL;rear+;Qrear=s;if(rear=1)root=s;elseif(s&&Qfront)if(rear%2=0)Qfront->lchild=s;elseQfront->rchild=s;if(rear%2=1)front+;ch=getchar();returnroot;voidpreorder(t)bitree*t;if(t)printf("%c",t->data);preorder(t->lchild);preorder(t->rchild);voidinorder(t)bitree*

37、t;if(t)inorder(t->lchild);printf("%c",t->data);inorder(t->rchild);voidpostorder(t)bitree*t;if(t)postorder(t->lchild);postorder(t->rchild);printf("%c",t->data);main()bitree*root;clrscr();root=Creatree();printf("preorderis:");preorder(root);printf("

38、n");printf("inorderis:");inorder(root);printf("n");printf("postorderis:");postorder(root);printf("n");(2)#include<>#include<>#definemaxsize100typedefstructnodechardata;structnode*lchild,*rchild;bitree;bitree*Qmaxsize;bitree*Creatree()charch;in

39、tfront,rear;bitree*root,*s;root=NULL;front=1;rear=0;printf("NowCreatthebitree,inputbaseingtheordertoptobottom,lefttoright:n");ch=getchar();while(ch!='#')s=NULL;if(ch!='')s=malloc(sizeof(bitree);s->data=ch;s->lchild=NULL;s->rchild=NULL;rear+;Qrear=s;if(rear=1)root=s

40、;elseif(s&&Qfront)if(rear%2=0)Qfront->lchild=s;elseQfront->rchild=s;if(rear%2=1)front+;ch=getchar();returnroot;intleft(bitree*t)intnum1,num2;if(t=NULL)return0;elseif(t->lchild=NULL&&t->rchild=NULL)return1;elsenum1=left(t->lchild);num2=left(t->rchild);return(num1+num

41、2);main()bitree*root;clrscr();root=Creatree();printf("leftsis%dn",left(root);(3) #include<>#include<>#definemaxsize100typedefstructnodechardata;structnode*lchild,*rchild;bitree;bitree*Qmaxsize;bitree*Creatree()charch;intfront,rear;bitree*root,*s;root=NULL;front=1;rear=0;printf(

42、"NowCreatthebitree,inputbaseingtheordertoptobottom,lefttoright:n");ch=getchar();while(ch!='#')s=NULL;if(ch!='')s=malloc(sizeof(bitree);s->data=ch;s->lchild=NULL;s->rchild=NULL;rear+;Qrear=s;if(rear=1)root=s;elseif(s&&Qfront)if(rear%2=0)Qfront->lchild=s;e

43、lseQfront->rchild=s;if(rear%2=1)front+;ch=getchar();returnroot;intnodes(bitree*t)intnum1,num2;if(t=NULL)return0;elseif(t->lchild=NULL&&t->rchild=NULL)return1;elsenum1=nodes(t->lchild);num2=nodes(t->rchild);return(num1+num2+1);main()bitree*root;clrscr();root=Creatree();printf(&

44、quot;nodesis%dn",nodes(root);(4) #include<>#include<>#definemaxsize100typedefstructnodechardata;structnode*lchild,*rchild;bitree;bitree*Qmaxsize;bitree*Creatree()charch;intfront,rear;bitree*root,*s;root=NULL;front=1;rear=0;printf("NowCreatthebitree,inputbaseingtheordertoptobott

45、om,lefttoright:n");ch=getchar();while(ch!='#')s=NULL;if(ch!='')s=malloc(sizeof(bitree);s->data=ch;s->lchild=NULL;s->rchild=NULL;rear+;Qrear=s;if(rear=1)root=s;elseif(s&&Qfront)if(rear%2=0)Qfront->lchild=s;elseQfront->rchild=s;if(rear%2=1)front+;ch=getchar(

46、);returnroot;intdepth(bitree*t)intdep1,dep2;if(t=NULL)return0;elsedep1=depth(t->lchild);dep2=depth(t->rchild);if(dep1>dep2)return(dep1+1);elsereturn(dep2+1);main()bitree*root;clrscr();root=Creatree();printf("depthis%dn",depth(root);四、實驗結(jié)果與分析(程序運行結(jié)果及其分析)(1) NowCreatthebitree,inputb

47、aseingtheordertoptobottom,lefttoright:abc#preorderis:abcinorderis:abcpostorderis:cba(2) NowCreatthebitree,inputbaseingtheordertoptobottom,lefttoright:abc#leftsis1(3) NowCreatthebitree,inputbaseingtheordertoptobottom,lefttoright:abc#nodesis3（4）NowCreatthebitree,inputbaseingtheordertoptobottom,lefttor

48、ight:abc#depthis3五、實驗體會（遇到問題及解決辦法，編程后的心得體會）遇到問題：這章從一開始編寫成功后運行就一直不順利，理論上程序時正確的，但是輸入運行處的結(jié)果卻總是錯誤一大堆。在詢問老師后，經(jīng)過運行及測試，才明白我是對ch=getchar（）;這個函數(shù)的理解錯誤，在這個函數(shù)中，空格也算作一個字符，所以當(dāng)我輸入的時候，每一個字符中間空一個，輸入五個對于程序我相當(dāng)于輸入了十個字符。實驗體會：這次的實驗讓我明白了基礎(chǔ)理論知識的重要性，沒有堅實的基礎(chǔ)知識，在這種問題上，即使編寫出來了，檢查錯誤調(diào)試就要花許多時間。并且我也學(xué)會了二叉樹的輸入賦值以及它的各種計算。工科樓A205實驗項目名

49、稱：圖實驗學(xué)時:同組學(xué)生姓名：實驗地點:實驗日期：2013年11月20日實驗成績:批改教師：批改時間:實驗6圖一、實驗?zāi)康暮鸵?1)熟練掌握圖的基本概念、構(gòu)造及其存儲結(jié)構(gòu)。(2)熟練掌握對圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷的算法。二、實驗儀器和設(shè)備TurboC三、實驗內(nèi)容與過程(含程序清單及流程圖)1、必做題(1)構(gòu)造一個無向圖(用鄰接矩陣表示存儲結(jié)構(gòu))。(2)對上面所構(gòu)造的無向圖，進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，輸出遍歷序列。2、選做題采用鄰接表存儲結(jié)構(gòu)，編寫一個判別無向圖中任意給定的兩個頂點之間是否存在一條長度為k的簡單路徑的算法。簡單路徑是指其頂點序列中不含有重復(fù)頂點的路徑。提示：

50、兩個頂點及k值均作為參數(shù)給出。程序清單：1(1)#include<>#definen6#definee8typedefstructcharvexsn;floatarcsnn;graph1;creatgraph()graph1*ga;inti,j,k;floatw;clrscr();for(i=0;i<n;i+)ga->vexsi=getchar();printf("okn");for(i=0;i<n;i+)for(j=0;j<n;j+)ga->arcsij=0;for(k=0;k<e;k+)scanf("%d%d%f

51、",&i,&j,&w);ga->arcsij=w;ga->arcsji=w;printf("okn");main()creatgraph();(2)#include<>#definen3#definee2typedefstructcharvexsn;floatarcsnn;graph1;creatgraph()graph1*ga;inti,j,k;floatw;clrscr();for(i=0;i<n;i+)ga->vexsi=getchar();printf("okn");for(i

52、=0;i<n;i+)for(j=0;j<n;j+)ga->arcsij=0;for(k=0;k<e;k+)scanf("%d%d%f",&i,&j,&w);ga->arcsij=w;ga->arcsji=w;printf("okn");intvisitedn=0;dfs(i);inti;intj;printf("node:%cn",i);visitedi=1;for(j=0;j<n;j+)ifij&&(!visitedj)dfs(j);typedefst

53、ructintdata10;intfront,read;sequeue;sequeueQ;bfs(i)inti,j;=-1;=-1;printf("%cn",k);visitedk=1;+=k;while!=+;i=;for(j=0;j<n;j+)ifij&&(!visitedj)printf("%cn",j);visitedj=1;+=j;main()creatgraph();dfs(1);bfs(0);四、實驗結(jié)果與分析（程序運行結(jié)果及其分析）1（1）abcdefok1211131201150216034504152355345

54、5ok（2）abcok01110212ok深度優(yōu)先：abc廣度優(yōu)先：abc五、實驗體會（遇到問題及解決辦法，編程后的心得體會）遇到問題：這一章編寫的極其的不順利，首先在理論上我認(rèn)為是正確的程序在運行時卻一次次的出現(xiàn)error和warning,讓我這章內(nèi)容進(jìn)行了兩次課時。耽誤了下一章的編寫。首先是在文檔中編寫時，首字母自動大寫而沒有發(fā)現(xiàn)，其次是有clrscr（）這個函數(shù)但是頭文件卻忘記寫了，然后老師批評最嚴(yán)重的一個問題是沒有標(biāo)志語言,這章圖的編寫即使輸入進(jìn)去也不會顯示出來,因此應(yīng)該添加標(biāo)志語言。實驗體會：在編寫時需要認(rèn)真對待，認(rèn)真檢查C語言語法以及在編寫時有可能忘記的內(nèi)容。最重要的是在一些程序中

55、，需要添加標(biāo)志語言，不能因為完成了就是完成了，需要簡明易懂給人提示。實驗項目名稱：排序?qū)嶒瀸W(xué)時：2同組學(xué)生姓名：實驗地點：工科樓A205實驗日期：2013年11月27日實驗成績：批改教師：批改時間：實驗7排序一、實驗?zāi)康暮鸵螅?）熟練掌握希爾排序、堆排序、直接插入排序、起泡排序、快速排序、直接選擇排序、歸并排序和基數(shù)排序的基本概念。（2）掌握以上各種排序的算法。區(qū)分以上不同排序的優(yōu)、缺點。二、實驗儀器和設(shè)備TurboC三、實驗內(nèi)容與過程（含程序清單及流程圖）1、必做題用隨機(jī)數(shù)產(chǎn)生100000個待排序數(shù)據(jù)元素的關(guān)鍵字值。測試下列各排序函數(shù)的機(jī)器實際執(zhí)行時間（至少測試兩個）：直接插入排序、希爾排

56、序（增量為4，2，1）、冒泡排序、快速排序、直接選擇排序、二路歸并排序、堆排序和基于鏈?zhǔn)疥犃械幕鶖?shù)排序。2、選做題假設(shè)含n個記錄的序列中，其所有關(guān)鍵字為值介于v和w之間的整數(shù)，且其中很多關(guān)鍵字的值是相同的。則可按如下方法排序：另設(shè)數(shù)組numberv.w,令numberi統(tǒng)計關(guān)鍵字為整數(shù)i的紀(jì)錄個數(shù)，然后按number重排序列以達(dá)到有序。試編寫算法實現(xiàn)上述排序方法，并討論此種方法的優(yōu)缺點。程序清單：1（1）#include<>#include<>#include<>#include<>#include<>#defineM20000typedefstructintaM;intkey;sequenlist;main（）inti,j,k,temp;sequenlistL;time_tfirst,second;clrscr();first=time(NULL);randomize();for(i=0;i<M-1;i+)i=rand()%1000;fo