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

〔理工類〕課程名稱：算法與數(shù)據(jù)構(gòu)造專業(yè)班級學生學號：學生：所屬院部：計算機工程學院指導教師：章海鷗2016——2017學年第1學期金陵科技學院教務(wù)處制實驗報告書寫要求實驗報告原那么上要求學生手寫，要求書寫工整。假設(shè)因課程特點需打印的，要遵照以下字體、字號、間距等的具體要求。紙一律采用A4的紙。實驗報告書寫說明實驗報告中一至四項容為必填項，包括實驗目的和要求；實驗儀器和設(shè)備；實驗容與過程；實驗結(jié)果與分析。各院部可根據(jù)學科特點和實驗具體要求增加工程。填寫考前須知〔1〕細致觀察，及時、準確、如實記錄?！?〕準確說明，層次清晰?！?〕盡量采用專用術(shù)語來說明事物?！?〕外文、符號、公式要準確，應(yīng)使用統(tǒng)一規(guī)定的名詞和符號?！?〕應(yīng)獨立完成實驗報告的書寫，嚴禁抄襲、復印，一經(jīng)發(fā)現(xiàn)，以零分論處。實驗報告批改說明實驗報告的批改要及時、認真、仔細，一律用紅色筆批改。實驗報告的批改成績采用百分制，具體評分標準由各院部自行制定。實驗報告裝訂要求實驗批改完畢后，任課教師將每門課程的每個實驗工程的實驗報告以自然班為單位、按學號升序排列，裝訂成冊，并附上一份該門課程的實驗大綱。實驗工程名稱：順序表實驗學時：2同組學生：╱實驗地點：實驗日期：實驗成績：批改教師：批改時間：實驗1順序表一、實驗目的和要求掌握順序表的定位、插入、刪除等操作。二、實驗儀器和設(shè)備VC6.0三、實驗容與過程〔含程序清單及流程圖〕1、必做題編寫程序建立一個順序表，并逐個輸出順序表中所有數(shù)據(jù)元素的值。編寫主函數(shù)測試結(jié)果。編寫順序表定位操作子函數(shù)，在順序表中查找是否存在數(shù)據(jù)元素x。如果存在，返回順序表中和x值相等的第1個數(shù)據(jù)元素的序號〔序號從0開場編號〕；如果不存在，返回－1。編寫主函數(shù)測試結(jié)果。在遞增有序的順序表中插入一個新結(jié)點x，保持順序表的有序性。解題思路：首先查找插入的位置，再移位，最后進展插入操作；從第一個元素開場找到第一個大于該新結(jié)點值x的元素位置i即為插入位置；然后將從表尾開場依次將元素后移一個位置直至元素i；最后將新結(jié)點x插入到i位置。刪除順序表中所有等于X的數(shù)據(jù)元素。2、選做題兩個順序表A和B按元素值遞增有序排列，要求寫一算法實現(xiàn)將A和B歸并成一個按元素值遞減有序排列的順序表〔允許表中含有值一樣的元素〕。程序清單：(1)#include<stdio.h>#definemaxsize20typedefintdatatype;typedefstruct{datatypedata[maxsize];intlast;}sequenlist;voidCreateList(sequenlist*L,intn){inti;printf("pleaseinputnnumbers\n");for(i=0;i<n;i++){scanf("%d",&L->data[i]);(*L).last=n;}}voidPrintList(sequenlist*L,intn){inti;printf("thesequenlistis\n");for(i=0;i<n;i++)printf("%d",L->data[i]);}main(){inti,x;intn=10;sequenlistL;CreateList(&L,n);PrintList(&L,n);getchar();}(2)#include<stdio.h>typedefintdatatype;#definemaxsize1024typedefstruct{datatypedata[maxsize];intlast;}sequenlist;intfun(sequenlistL,intx,intn){ inti; for(i=0;i<n;i++) if(L.data[i]==x) returni; return-1;}voidmain(){ sequenlistL; inti,n,y; intx;printf("請輸入元素的個數(shù)："); scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",&L.data[i]); } printf("\n請輸入要查找的數(shù)據(jù)元素："); scanf("%d",&x); y=fun(L,x,n); if(y==1) printf("\n所要查找的數(shù)據(jù)元素不存在\n"); else printf("\n數(shù)據(jù)元素%d所在的位置為%d\n",x,y);}(3)#include<stdio.h>#definemaxsize100typedefstruct{ intdata[maxsize]; intlast;}sequenlist;main(){ inti,x,j; sequenlistl={{1,2,4,5,6,7,8},6}; printf("\n插入元素前的數(shù)據(jù)為:"); for(i=0;i<=l.last;i++) printf("%2d",l.data[i]); printf("\n請輸入要插入的元素:"); scanf("%d",&x); for(i=1;i<=l.last;i++) if(l.data[i-1]>x)break; if(i>l.last) { l.data[l.last+1]=x; } else { for(j=l.last;j>=i-1;j--) l.data[j+1]=l.data[j]; l.data[i-1]=x; } l.last++; printf("插入元素后的數(shù)據(jù)為:\n"); for(j=0;j<=l.last;j++) printf("%3d",l.data[j]); printf("\n"); return0;}(4)#include<stdio.h>#definemaxsize100typedefstruct{ intdata[maxsize]; intlast;}sequenlist;main(){ inti,j,x=0,k=0; sequenlistL={{1,3,5,7,2,4,6,8,2,9},9};printf("\n原數(shù)據(jù)為:"); for(i=0;i<=L.last;i++)printf("%3d",L.data[i]); printf("\n請輸入要刪除的數(shù)據(jù):"); scanf("%d",&x); for(i=1;i<=L.last+1;i++) if(L.data[i-1]==x) { for(j=i;j<=L.last+1;j++)L.data[j-1]=L.data[j]; L.last--; i--; k=1; }if(k==1) { printf("刪除后的數(shù)據(jù)為:\n"); for(j=0;j<=L.last;j++) printf("%3d",L.data[j]); } elseprintf("Notfound!\n"); printf("\n");}四、實驗結(jié)果與分析〔程序運行結(jié)果及其分析〕1.11.21.31.4五、實驗體會〔遇到問題及解決方法，編程后的心得體會〕遇到問題：讀取數(shù)據(jù)元素時，誤將==寫成=，導致錯誤。實驗過程中，順序表的賦值沒有弄懂，以致輸出多個0或者少輸出。格式運算符也要正確控制，否那么系統(tǒng)會停頓工作。實驗體會：通過實驗掌握了順序表的根本操作，如初始化、插入、讀取元素、刪除等等。并了解到線性表順序存儲構(gòu)造的特點，即邏輯關(guān)系上相鄰的兩個元素在物理位置上也相鄰，然而從另一方面來看，在做插入和刪除時需要移動大量元素。本次實驗根本完成了實驗要求的目的，順序表的初始化，定義，插入，查找等，更好的了解了順序表根本操作的算法，以及更直觀的了解了數(shù)據(jù)構(gòu)造在C語言環(huán)境下的表達。實驗工程名稱：單鏈表實驗學時：2同組學生：╱實驗地點：實驗日期：實驗成績：批改教師：批改時間：實驗2單鏈表一、實驗目的和要求1、實驗目的掌握單鏈表的定位、插入、刪除等操作。2、實驗要求〔1〕注意鏈表的空間是動態(tài)分配的，某結(jié)點不用之后要及時進展物理刪除，以便釋放其存空間?！?〕鏈表不能實現(xiàn)直接定位，一定注意指針的保存，防止喪失。二、實驗儀器和設(shè)備VisualC++6.0三、實驗容與過程〔含程序清單及流程圖〕1、必做題編寫程序建立一個單鏈表，并逐個輸出單鏈表中所有數(shù)據(jù)元素。在遞增有序的單鏈表中插入一個新結(jié)點x，保持單鏈表的有序性。解題思路：首先查找插入的位置然后進展插入操作；從第一個結(jié)點開場找到第一個大于該新結(jié)點值的結(jié)點即為插入位置；然后在找到的此結(jié)點之前插入新結(jié)點；注意保存插入位置之前結(jié)點的指針才能完成插入操作。編寫實現(xiàn)帶頭結(jié)點單鏈表就地逆置的子函數(shù)，并編寫主函數(shù)測試結(jié)果。2、選做題指針LA和LB分別指向兩個無頭結(jié)點單鏈表的首元結(jié)點。要求編一算法實現(xiàn)，從表LA中刪除自第i個元素起共len個元素后，將它們插入到表LB中第j個元素之前。程序清單：〔1〕#include<stdio.h>#include<stdlib.h>typedefstructnode{intdata;structnode*next;}*Linklist,Node;Linklistcreat(intn){Linklisthead,r,p;intx,i;head=(Node*)malloc(sizeof(Node));r=head;printf("輸入數(shù)字:\n");for(i=n;i>0;i--){ scanf("%d",&x); p=(Node*)malloc(sizeof(Node)); p->data=x; r->next=p; r=p;}r->next=NULL;returnhead;}voidoutput(Linklisthead){ Linklistp; p=head->next; do{ printf("%3d",p->data); p=p->next; }while(p); printf("\n");}voidmain(){ Linklisthead; intx,n; printf("輸入數(shù)字的個數(shù)(n):\n"); scanf("%d",&n); head=creat(n); printf("輸出數(shù)字:\n"); output(head);}〔2〕#include<stdio.h>#include<stdlib.h>typedefstructnode{intdata;structnode*next;}linklist;main(){intx,y;linklist*h,*s,*r,*p,*q,*m,*n;h=malloc(sizeof(linklist));r=h;printf("請輸入一個數(shù)組:");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("請輸入插入值:");scanf("%d",&y);p=h->next;while(p!=NULL){if((p->data)<y) p=p->next;else break;}q=malloc(sizeof(linklist));q->data=y;m=h;while(m->next!=p) m=m->next;q->next=p;m->next=q;n=h->next;printf("這個鏈表是:");while(n!=NULL){printf("%2d",n->data);n=n->next;}}〔3〕#include<stdio.h>#include<stdlib.h>typedefstructnode{intdata;structnode*next;}linklist;main(){intx;linklist*h,*s,*r,*p,*q,*t;h=malloc(sizeof(linklist));r=h;printf("請輸入一個數(shù)組:");scanf("%d",&x);while(x!=-1){s=malloc(sizeof(linklist));s->data=x;r->next=s;r=s;scanf("%d",&x);}r->next=NULL;printf("\n這個鏈表是:\n");p=h->next;while(p!=NULL){printf("%2d",p->data);p=p->next;}p=h->next;q=p->next;while(q!=NULL){t=q->next;q->next=p;p=q;q=t;}h->next->next=NULL;h->next=p;printf("\n翻轉(zhuǎn)轉(zhuǎn)后的鏈表是:\n");p=h->next;while(p!=NULL){printf("%2d",p->data);p=p->next;}}四、實驗結(jié)果與分析〔程序運行結(jié)果及其分析〕(1)(2)(3)五、實驗體會〔遇到問題及解決方法，編程后的心得體會〕遇到問題：編寫成功后運行時，沒有參加$導致程序運行不成功，不能夠退出。后注意到這個問題才繼續(xù)運行下去。實驗體會：在編寫程序時，設(shè)置了完畢字符一定要牢牢記住，并且在輸入時觀察仔細類型是什么，以及是否是輸入一串有順序的數(shù)字，編寫成功不難，但是要規(guī)格式，不能僅僅以完成程序為目的。而完成這一章的實驗也讓我了解了，順序表便于查找不便于插入刪除，而鏈表恰恰相反，鏈表的插入刪除只需要移動指針，而順序表要從后往前依次移動，二者各有優(yōu)劣.實驗工程名稱：堆棧和隊列實驗學時：2同組學生：╱實驗地點：實驗日期：實驗成績：批改教師：批改時間：實驗3堆棧和隊列一、實驗目的和要求〔1〕掌握應(yīng)用棧解決問題的方法?！?〕掌握利用棧進展表達式求和的算法?！?〕掌握隊列的存儲構(gòu)造及根本操作實現(xiàn)，并能在相應(yīng)的應(yīng)用問題中正確選用它們。二、實驗儀器和設(shè)備VisualC++6.0三、實驗容與過程〔含程序清單及流程圖〕1、必做題判斷一個算術(shù)表達式中開括號和閉括號是否配對。測試“漢諾塔〞問題。假設(shè)稱正讀和反讀都一樣的字符序列為〞回文〞，試寫一個算法判別讀入的一個以’’為完畢符的字符序列是否是“回文〞。2、選做題在順序存儲構(gòu)造上實現(xiàn)輸出受限的雙端循環(huán)隊列的入列和出列算法。設(shè)每個元素表示一個待處理的作業(yè)，元素值表示作業(yè)的預計時間。入隊列采取簡化的短作業(yè)優(yōu)先原那么，假設(shè)一個新提交的作業(yè)的預計執(zhí)行時間小于隊頭和隊尾作業(yè)的平均時間，那么插入在隊頭，否那么插入在隊尾。程序清單：〔1〕#include<stdio.h>#include<stdlib.h>typedefchardatatype;#definemaxsize64typedefstruct{datatypedata[maxsize];inttop;}seqstack;intmatch(charexp[],intn){charst[maxsize];//設(shè)置一個棧，用來存放掃描表達式中的括號inttop=-1,i=0,tag=1;while(i<n&&tag==1){if(exp[i]=='('||exp[i]=='['||exp[i]=='{')//遇到'(''[''{',那么將其入棧{top++;st[top]=exp[i];}if(exp[i]==')')//遇到')',假設(shè)棧頂是'(',那么繼續(xù)處理，否那么以不配對返回if(st[top]=='(')top--;elsetag=0;if(exp[i]==']')if(st[top]=='[')top--;elsetag=0;if(exp[i]=='}')if(st[top]=='{')top--;elsetag=0;i++;}if(top>=0)tag=0;//假設(shè)棧不空，那么不配對returntag;}main(){inttag,i;charexp[7]={'+','(','2','-','4',')'};printf("請輸入一個算式表達式：\n");for(i=0;i<7;i++)exp[i]=getchar();tag=match(exp,7);if(tag)printf("算式表達式中的開括號和閉括號配對。");elseprintf("算式表達式中的開括號和閉括號不配對！");}(2)#include<stdio.h>voidmove(charx,charz){printf("%c-->",x);printf("%c\n",z);}voidHanoi(intn,charx,chary,charz){if(n==1)move(x,z);else{Hanoi(n-1,x,z,y);move(x,z);Hanoi(n-1,y,x,z);}}main(){intm;printf("請你輸入A上面的碟子總數(shù)");scanf("%d",&m);Hanoi(m,'A','B','C');getchar();getchar();}(3)#include<stdio.h>#defineN100typedefstruct{chardata[N];inttop;}seqstack;main(){charstr[N];inti=0,n;seqstacka;a.top=0;gets(str);while(str[i]!='') i++;n=i;for(i=0;i<n/2;i++){a.top++;a.data[a.top]=str[i];}i=i-1;if(n%2==0)i++;elsei=i+2;while(i<n&&a.data[a.top]==str[i]){i++;a.top--;}if(i==n) printf("是回文數(shù)組\n");else printf("不是回文數(shù)組\n");}四、實驗結(jié)果與分析〔程序運行結(jié)果及其分析〕123五、實驗體會〔遇到問題及解決方法，編程后的心得體會〕遇到問題：在本章棧和隊列中編程，有許多的if語句，編寫時一不小心就會少加一個花括號，以致編寫不成功。在本章漢諾塔問題中，使用了棧以及函數(shù)的遞歸，這其中的過程一直不是很了解，在經(jīng)過教師的講解后，理解了大致過程。實驗體會：遞歸函數(shù)是編程中經(jīng)常會用到的一種函數(shù)，它可以實現(xiàn)許多我們在平時言語和解釋上解決不了的問題，我們需要理解并且可以熟練的使用它，這對我們之后的編程會有很大的幫助。而漢諾塔利用棧是一種很經(jīng)典的遞歸的算法，這讓我們理解棧和遞歸。實驗工程名稱：串實驗學時：2同組學生：╱實驗地點：實驗日期：實驗成績：批改教師：批改時間：實驗4串一、實驗目的和要求掌握串的存儲及應(yīng)用。二、實驗儀器和設(shè)備VisualC++6.0三、實驗容與過程〔含程序清單及流程圖〕1、必做題編寫輸出字符串s中值等于字符ch的第一個字符的函數(shù)，并用主函數(shù)測試結(jié)果。編寫輸出字符串s中值等于字符ch的所有字符的函數(shù)，并用主函數(shù)測試結(jié)果。解題思路：可以將第一題程序改良成一個子函數(shù)，在此題中循環(huán)調(diào)用。設(shè)字符串采用單字符的鏈式存儲構(gòu)造，編程刪除串s從位置i開場長度為k的子串。2、選做題假設(shè)以鏈構(gòu)造表示串，編寫算法實現(xiàn)將串S插入到串T中某個字符之后，假設(shè)串T中不存在這個字符，那么將串S聯(lián)接在串T的末尾。提示：為提高程序的通用性，插入位置字符應(yīng)設(shè)計為從鍵盤輸入。程序清單：(1)#include<stdio.h>voidsearch(char*s,charch){ inti=0,n=0; while(*(s+i)) { if(*(s+i)==ch) { printf("第一個字符：s[%d]=%c\n",i,ch); n++; break; } i++; }if(!n) printf("NoFound!\n");}voidmain(){ chars[20],ch; printf("請輸入一個串:"); gets(s); printf("請輸入要找的元素:"); scanf("%c",&ch); search(s,ch);}(2)#include<stdio.h>voidsearch(char*s,charch){ inti=0,n=0; while(*(s+i)) { if(*(s+i)==ch) { n++; printf("第%d個%c在串中的下標為：%d\n",n,ch,i); } i++; } if(!n) printf("NoFound!\n");}voidmain(){ chars[20],ch; printf("請輸入串元素："); gets(s); printf("請輸入要找的元素："); scanf("%c",&ch); search(s,ch);}(3)#include<stdio.h>#include<stdlib.h>typedefstructlinknode{ chardata; structlinknode*next;}linkstring;linkstring*CREAT(){ linkstring*head=NULL,*p=NULL,*s=NULL; inta; printf("請輸入順序表的值，'-1'表示輸入完畢：\n"); scanf("%d",&a); while(a!=-1) { s=(linkstring*)malloc(sizeof(linkstring)); if(s==NULL) exit(0); s->data=a; if(head==NULL) head=s; else p->next=s; p=s; scanf("%d",&a); } p->next=NULL; printf("建立完畢！\n"); returnhead;}intSEARCH(linkstring*s,inti,intk){ linkstring*p=s; intj=0; for(;j<i+k-2&&p->next!=NULL;j++) { p=p->next; } if(j==i+k-2) return1; return0;}voidDELETE(linkstring*s,inti,intk){ linkstring*p=s,*q=NULL; intj=1; for(;j<i-1;j++) { p=p->next; } for(j=0;j<k;j++) { q=p->next; p->next=q->next; free(q); }printf("成功刪除！");}voidPRINT(linkstring*head){ linkstring*s=NULL; s=head; while(s) { printf("%d",s->data); s=s->next; } printf("打印完畢！\n\n");}intmain(){ linkstring*ls; inti,k,m; ls=CREAT(); PRINT(ls); printf("輸入你想刪除第幾個字符起的連續(xù)的多少個字符："); scanf("%d%d",&i,&k); m=SEARCH(ls,i,k); if(m==0) printf("不存在這樣的子串，刪除失敗！"); else { DELETE(ls,i,k); PRINT(ls); } return0;} 四、實驗結(jié)果與分析〔程序運行結(jié)果及其分析〕(1)(2)(3)五、實驗體會〔遇到問題及解決方法，編程后的心得體會〕實驗體會：本章第一題可以作為第二題的子函數(shù)，使用調(diào)用；也可以從開頭查找對應(yīng)的字符到結(jié)尾，最后全部輸出。前兩題使用順序串，后面一題是鏈串。串的存儲構(gòu)造包含有順序存儲構(gòu)造和鏈式存儲構(gòu)造。在串的順序存儲構(gòu)造中，表示串的長度通常有兩種方法：一種方法是設(shè)置一個串的長度參數(shù)，其優(yōu)點在于便于在算法中用長度參數(shù)控制循環(huán)過程；另一種方法是在串值得末尾添加完畢標記，此種方法的優(yōu)點在于便于系統(tǒng)自動實現(xiàn)。在串的存儲過程中，串值用雙引號引起來，系統(tǒng)將自動在串值得末尾添加完畢標記\0字符。實驗工程名稱：二叉樹實驗學時：2同組學生：╱實驗地點：實驗日期：實驗成績：批改教師：批改時間：實驗5二叉樹一、實驗目的和要求〔1〕掌握二叉樹的生成，以及前、中、后序遍歷算法?！?〕掌握應(yīng)用二叉樹遞歸遍歷思想解決問題的方法。二、實驗儀器和設(shè)備VisualC++6.0三、實驗容與過程〔含程序清單及流程圖〕1、必做題建立一棵二叉樹。對此樹進展前序遍歷、中序遍歷及后序遍歷，輸出遍歷序列。在第一題根底上，求二叉樹中葉結(jié)點的個數(shù)。在第一題根底上，求二叉樹中結(jié)點總數(shù)。在第一題根底上，求二叉樹的深度。2、選做題一棵完全二叉樹存于順序表sa中，sa.elem[1…sa.last]存儲結(jié)點的值。試編寫算法由此順序存儲構(gòu)造建立該二叉樹的二叉鏈表。解題思路：根據(jù)完全二叉樹順序存儲的性質(zhì)來確定二叉樹的父子關(guān)系即“復原〞了二叉樹，之后再按照二叉樹二叉鏈表的構(gòu)造方法進展建立。完全二叉樹順序存儲的一個重要性質(zhì)為，第i個結(jié)點的左孩子是編號為2i的結(jié)點，第i個結(jié)點的右孩子是編號為2i+1的結(jié)點。程序清單：〔1〕#include<stdio.h>#include<stdlib.h>#definemaxsize20typedefstructnode{chardata;structnode*lchild,*rchild;}bitree;bitree*Q[maxsize];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->rchild=NULL;}rear++;Q[rear]=s;if(rear==1)root=s;else{if(s&&Q[front]) if(rear%2==0)Q[front]->lchild=s; else Q[front]->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*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;root=Creatree();printf("preorderis:");preorder(root);printf("\n");printf("inorderis:");inorder(root);printf("\n");printf("postorderis:");postorder(root);printf("\n");}(2)#include<stdio.h>#include<stdlib.h>#definemaxsize100typedefstructnode{chardata;structnode*lchild,*rchild;}bitree;bitree*Q[maxsize];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->rchild=NULL;}rear++;Q[rear]=s;if(rear==1)root=s;else{if(s&&Q[front]) if(rear%2==0)Q[front]->lchild=s; else Q[front]->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;else{num1=left(t->lchild);num2=left(t->rchild);return(num1+num2);}}main(){bitree*root;root=Creatree();printf("leftsis%d\n",left(root));}(3)#include<stdio.h>#include<stdlib.h>#definemaxsize100typedefstructnode{chardata;structnode*lchild,*rchild;}bitree;bitree*Q[maxsize];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->rchild=NULL;}rear++;Q[rear]=s;if(rear==1)root=s;else{if(s&&Q[front]) if(rear%2==0)Q[front]->lchild=s; else Q[front]->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;else{num1=nodes(t->lchild);num2=nodes(t->rchild);return(num1+num2+1);}}main(){bitree*root;root=Creatree();printf("nodesis%d\n",nodes(root));}(4)#include<stdio.h>#include<stdlib.h>#definemaxsize100typedefstructnode{chardata;structnode*lchild,*rchild;}bitree;bitree*Q[maxsize];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->rchild=NULL;}rear++;Q[rear]=s;if(rear==1)root=s;else{if(s&&Q[front]) if(rear%2==0)Q[front]->lchild=s; else Q[front]->rchild=s;if(rear%2==1)front++;}ch=getchar();}returnroot;}intdepth(bitree*t){intdep1,dep2;if(t==NULL)return0;else{dep1=depth(t->lchild);dep2=depth(t->rchild);if(dep1>dep2)return(dep1+1);elsereturn(dep2+1);}}main(){bitree*root;root=Creatree();printf("depthis%d\n",depth(root));}四、實驗結(jié)果與分析〔程序運行結(jié)果及其分析〕1.2.3.4.五、實驗體會〔遇到問題及解決方法，編程后的心得體會〕遇到問題：這章從一開場編寫成功后運行就一直不順利，理論上程序時正確的，但是輸入運行處的結(jié)果卻總是錯誤一大堆。在詢問教師后，經(jīng)過運行及測試，才明白我是對ch=getchar();這個函數(shù)的理解錯誤，在這個函數(shù)中，空格也算作一個字符，所以當我輸入的時候，每一個字符中間空一個，輸入五個對于程序我相當于輸入了十個字符。實驗體會：這次的實驗讓我明白了根底理論知識的重要性，沒有堅實的根底知識，在這種問題上，即使編寫出來了，檢查錯誤調(diào)試就要花許多時間。并且我也學會了二叉樹的輸入賦值以及它的各種計算。實驗工程名稱：圖實驗學時：2同組學生：╱實驗地點：實驗日期：實驗成績：批改教師：批改時間：實驗6圖一、實驗目的和要求〔1〕熟練掌握圖的根本概念、構(gòu)造及其存儲構(gòu)造?！?〕熟練掌握對圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷的算法。二、實驗儀器和設(shè)備VisualC++6.0三、實驗容與過程〔含程序清單及流程圖〕1、必做題〔1〕構(gòu)造一個無向圖〔用鄰接矩陣表示存儲構(gòu)造〕?！?〕對上面所構(gòu)造的無向圖，進展深度優(yōu)先遍歷和廣度優(yōu)先遍歷，輸出遍歷序列。2、選做題采用鄰接表存儲構(gòu)造，編寫一個判別無向圖中任意給定的兩個頂點之間是否存在一條長度為k的簡單路徑的算法。簡單路徑是指其頂點序列中不含有重復頂點的路徑。提示：兩個頂點及k值均作為參數(shù)給出。程序清單：〔1〕#include<stdio.h>#include<stdlib.h>typedefintdatatype;#definemaxsize1024#definen100typedefcharVEXTYPE;typedefintADJTYPE;typedefstruct{VEXTYPEvexs[n];ADJTYPEarcs[n][n];intnum;}GRAPH;voidGraphInit(GRAPH*L){L->num=0;}intGraphVexs(GRAPH*L){return(L->num);}voidGraphCreate(GRAPH*L){inti,j;GraphInit(L);printf("請輸入頂點數(shù)目：\n");scanf("%d",&L->num);printf("請輸入各頂點的信息：\n");for(i=0;i<L->num;i++){fflush(stdin);scanf("%c",&L->vexs[i]);}printf("請輸入邊權(quán)矩陣的信息：\n");for(i=0;i<L->num;i++){for(j=0;j<L->num;j++){scanf("%d",&L->arcs[i][j]);}}printf("圖已經(jīng)創(chuàng)立完畢！");}voidGraphOut(GRAPHL){inti,j;printf("\n圖的頂點數(shù)目為：%d",L.num);printf("\n圖的各頂點的信息為：\n");for(i=0;i<L.num;i++)printf("%6c",L.vexs[i]);printf("\n圖的邊權(quán)矩陣的信息為：\n");printf("\n");for(i=0;i<L.num;i++){for(j=0;j<L.num;j++){printf("%6d",L.arcs[i][j]);}printf("\n");}printf("圖已經(jīng)輸出完畢！");}voidmain(){GRAPHtu;GraphCreate(&tu);GraphOut(tu);system("pause");}(2)#include<stdio.h>#include<stdlib.h>typedefintdatatype;#definemaxsize1024#definen100typedefcharVEXTYPE;typedefintADJTYPE;typedefstruct{VEXTYPEvexs[n];ADJTYPEarcs[n][n];intnum;}GRAPH;voidGraphInit(GRAPH*L){L->num=0;}intGraphVexs(GRAPH*L){return(L->num);}voidGraphCreate(GRAPH*L){inti,j;GraphInit(L);printf("請輸入頂點數(shù)目：\n");scanf("%d",&L->num);printf("請輸入各頂點的信息：\n");for(i=0;i<L->num;i++){fflush(stdin);scanf("%c",&L->vexs[i]);}printf("請輸入邊權(quán)矩陣的信息：\n");for(i=0;i<L->num;i++){for(j=0;j<L->num;j++){scanf("%d",&L->arcs[i][j]);}}printf("圖已經(jīng)創(chuàng)立完畢！");}voidGraphOut(GRAPHL){inti,j;printf("\n圖的頂點數(shù)目為：%d",L.num);printf("\n圖的各頂點的信息為：\n");for(i=0;i<L.num;i++)printf("%6c",L.vexs[i]);printf("\n圖的邊權(quán)矩陣的信息為：\n");printf("\n");for(i=0;i<L.num;i++){for(j=0;j<L.num;j++){printf("%6d",L.arcs[i][j]);}printf("\n");}printf("圖已經(jīng)輸出完畢！");}voidDFS(GRAPHg,intqidian,intmark[]){intv1;mark[qidian]=1;printf("%6c",g.vexs[qidian]);for(v1=0;v1<g.num;v1++){if(g.arcs[qidian][v1]!=0&&mark[v1]==0)DFS(g,v1,mark);}}voidGraphDFS(GRAPHg){intqidian,v,v1,mark[maxsize];printf("\n深度優(yōu)先遍歷：");printf("\n請輸入起點的下標：");scanf("%d",&qidian);for(v=0;v<g.num;v++){mark[v]=0;}for(v=qidian;v<g.num+qidian;v++){v1=v%g.num;if(mark[v1]==0)DFS(g,v1,mark);}}typedefintDATATYPE;typedefstruct{DATATYPEdata[maxsize];intfront,rear;}SEQQUEUE;voidQueueInit(SEQQUEUE*sq){sq->front=0;sq->rear=0;}intQueueIsEmpty(SEQQUEUEsq){if(sq.rear==sq.front)return(1);elsereturn(0);}intQueueFront(SEQQUEUEsq,DATATYPE*e){if(QueueIsEmpty(sq)){printf("queueisempty!\n");return0;}else{*e=sq.data[(sq.front)];return1;}}intQueueIn(SEQQUEUE*sq,DATATYPEx){if(sq->front==(sq->rear+1)%maxsize){printf("queueisfull!\n");return0;}else{sq->data[sq->rear]=x;sq->rear=(sq->rear+1)%maxsize;return(1);}}intQueueOut(SEQQUEUE*sq){if(QueueIsEmpty(*sq)){printf("queueisempty!\n");return0;}else{sq->front=(sq->front+1)%maxsize;return1;}}voidBFS(GRAPHg,intv,intmark[]){intv1,v2;SEQQUEUEq;QueueInit(&q);QueueIn(&q,v);mark[v]=1;printf("%6c",g.vexs[v]);while(QueueIsEmpty(q)==0){QueueFront(q,&v1);QueueOut(&q);for(v2=0;v2<g.num;v2++){if(g.arcs[v1][v2]!=0&&mark[v2]==0){QueueIn(&q,v2);mark[v2]=1;printf("%6c",g.vexs[v2]);}}}}voidGraphBFS(GRAPHg){intqidian,v,v1,mark[maxsize];printf("\n廣度優(yōu)先遍歷：");printf("\n請輸入起點的下標：");scanf("%d",&qidian);for(v=0;v<g.num;v++){mark[v]=0;}for(v=qidian;v<g.num+qidian;v++){v1=v%g.num;if(mark[v1]==0)BFS(g,v1,mark);}}voidmain(){GRAPHtu;GraphCreate(&tu);GraphOut(tu);GraphDFS(tu);GraphBFS(tu);system("pause");}四、實驗結(jié)果與分析〔程序運行結(jié)果及其分析〕1.2.五、實驗體會〔遇到問題及解決方法，編程后的心得體會〕遇到問題：這一章編寫的極其的不順利，首先在理論上我認為是正確的程序在運行時卻一次次的出現(xiàn)error和warning，讓我這章容進展了兩次課時。耽誤了下一章的編寫。首先是在文檔中編寫時，首字母自動大寫而沒有發(fā)現(xiàn)，其次是有clrscr()這個函數(shù)但是頭文件卻忘記寫了，然后教師批評最嚴重的一個問題是沒有標志語言，這章圖的編寫即使輸入進去也不會顯示出來，因此應(yīng)該添加標志語言。實驗體會：在編寫時需要認真對待，認真檢查C語言語法以及在編寫時有可能忘記的容。最重要的是在一些程序中，需要添加標志語言，不能因為完成了就是完成了，需要簡明易懂給人提示。實驗工程名稱：排序?qū)嶒瀸W時：2同組學生：╱實驗地點：實驗日期：實驗成績：批改教師：批改時間：實驗7排序一、實驗目的和要求〔1〕熟練掌握希爾排序、堆排序、直接插入排序、起泡排序、快速排序、直接選擇排序、歸并排序和基數(shù)排序的根本概念。〔2〕掌握以上各種排序的算法。區(qū)分以上不同排序的優(yōu)、缺點。二、實驗儀器和設(shè)備VisualC++6.0三、實驗容與過程〔含程序清單及流程圖〕1、必做題用隨機數(shù)產(chǎn)生100000個待排序數(shù)據(jù)元素的關(guān)鍵字值。測試以下各排序函數(shù)的機