數(shù)據(jù)結(jié)構(gòu)實驗教學(xué)手冊

第2頁共30頁PAGE許昌學(xué)院計算機科學(xué)與技術(shù)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》課程實驗教學(xué)手冊《數(shù)據(jù)結(jié)構(gòu)》課程實驗教學(xué)手冊姓名：姓名：王俊東學(xué)號：1101120216專業(yè)：計算機科學(xué)與技術(shù)班級：2012級2班任課教師：王爽時間：2013-2014年度第1學(xué)期綜合成績：許昌學(xué)院計算機科學(xué)與技術(shù)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》課程實驗教學(xué)手冊計算機科學(xué)與技術(shù)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》課程組實驗手冊使用及要求實驗操作是教學(xué)過程中理論聯(lián)系實際的重要環(huán)節(jié)，而實驗報告的撰寫又是知識系統(tǒng)化的吸收和升華過程，因此，實驗報告應(yīng)該體現(xiàn)完整性、規(guī)范性、正確性、有效性?，F(xiàn)將實驗報告撰寫的有關(guān)內(nèi)容說明如下：實驗預(yù)習(xí)報告必須在實驗前完成。實驗時帶好實驗手冊方可進行實驗。實驗時按實驗預(yù)習(xí)報告內(nèi)容進行實驗。并如實填寫實驗過程及實驗小結(jié)。實驗結(jié)束后填寫通過后的源程序。通過后的源程序可以手寫也可以打印粘貼。實驗情況一覽表實驗序號實驗名稱實驗性質(zhì)學(xué)時實驗一順序表及其應(yīng)用驗證性實驗2實驗二單鏈表及其應(yīng)用綜合性試驗4實驗三線性表綜合練習(xí)設(shè)計性試驗6實驗四棧和隊列及其應(yīng)用設(shè)計性試驗4實驗五二叉樹及其應(yīng)用設(shè)計性試驗6實驗六圖及其應(yīng)用設(shè)計性試驗6實驗七查找設(shè)計性試驗4實驗八排序設(shè)計性試驗4

實驗一實驗名稱順序表及其應(yīng)用實驗性質(zhì)驗證性實驗學(xué)時數(shù)2學(xué)時一、實驗?zāi)康?．深入了解線性表的順序存儲結(jié)構(gòu)。2．熟練掌握在順序存儲結(jié)構(gòu)上進行插入、刪除等操作的算法。3．通過線性表結(jié)構(gòu)解決現(xiàn)實中的一些問題。二、實驗內(nèi)容1.線性表的順序存儲結(jié)構(gòu)。2.順序存儲結(jié)構(gòu)上進行插入、刪除等操作的算法。3.通過線性表結(jié)構(gòu)解決現(xiàn)實中的一些問題。三、實驗過程1、實驗題目[問題描述]設(shè)計一個順序表，要求：（1）包含不少于5個元素，并在屏幕上顯示。（2）對建好的順序表實現(xiàn)查找、插入、刪除等操作，并程序執(zhí)行結(jié)果顯示到屏幕上。（3）設(shè)計一個選擇菜單。[基本要求]（1）按實驗內(nèi)容編寫完整的程序，并上機驗證。（2）實驗完成后，提交電子檔教師驗收程序，并提交填寫好的實驗報告。[測試數(shù)據(jù)]由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。2、源程序#include"stdio.h"#include"malloc.h"#defineMAXSIZE200//線性表允許的最大長度#definedatatypeinttypedefstruct{//定義線性表的結(jié)構(gòu) datatypedata[MAXSIZE];//表示線性表（a1，a2，,an） intlast;//last表示線性表的實際長度}SeqList;voidinit_SeqList(SeqList*L)//線性表初始化{ L->last=-1;}intinsert_SeqList(SeqList*L,inti,datatypex)//插入操作{ intj; if((i<1)||(i>L->last+2)) { printf("插入位置不合法！"); return0; } if(L->last>=MAXSIZE-1) { printf("表已滿無法插入！"); return0; }for(j=L->last;j>=i-1;j--)L->data[j+1]=L->data[j];L->data[i-1]=x;L->last++;printf("插入成功\n");}intDelete_SeqList(SeqList*L,inti)//刪除操作{intk;if((i<1)||(i>L->last+1)) { printf("刪除位置不合法！"); return0;} for(k=i;k<=L->last;k++) L->data[k-1]=L->data[k]; L->last--; printf("刪除成功!\n"); }intLocation_SeqList(SeqList*L,datatypex)//按值查找{ inti,index; for(i=0;i<L->last;i++) if(L->data[i]==x) index=i; return(index+1);}voidprint(SeqList*L)//打印線性表{ inti; printf("該線性表為："); for(i=0;i<L->last;i++) printf("%4d",L->data[i]); printf("\n");}intmain()//主函數(shù)voidmain(){SeqListL;inti,choice;init_SeqList(&L); printf("請輸入線性表的長度:");scanf("%d",&L.last); printf("請輸入線性表的元素:");for(i=0;i<L.last;i++)scanf("%d",&L.data[i]);do {printf("請選擇您想要對線性表的操作:1:插入2:刪除3:查找4:打印0:退出\n");scanf("%d",&choice); switch(choice){ case1: intx,j; printf("請輸入要插入的數(shù)的位置和數(shù)值："); scanf("%d%d",&j,&x); insert_SeqList(&L,j,x); break; case2: intm; printf("請輸入要刪除的數(shù)的位置:"); scanf("%d",&m); Delete_SeqList(&L,m); break; case3: intn; printf("請輸入要查找的數(shù)："); scanf("%d",&n); printf("您要查找的數(shù)位于線性表的第%d位.\n",Location_SeqList(&L,n)); break; case4: print(&L); break; case0: break; default: printf("請選擇正確的操作！\n"); break; } }while(choice!=0); printf("謝謝使用!\n"); return0; }四實驗小結(jié)初步了解線性表的順序存儲結(jié)構(gòu)，及其定義格式。掌握在順序表上進行插入、刪除等操作的算法。但在順序表的操作上不是十分熟練。五成績

實驗二實驗名稱單鏈表及其應(yīng)用實驗性質(zhì)綜合性實驗學(xué)時數(shù)4學(xué)時一、實驗?zāi)康?．深入了解線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。2．熟練掌握在鏈?zhǔn)酱鎯Y(jié)構(gòu)上進行插入、刪除等操作的算法。3．通過線性表結(jié)構(gòu)解決現(xiàn)實中的一些問題。二、實驗內(nèi)容1.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。2.鏈?zhǔn)酱鎯Y(jié)構(gòu)上進行插入、刪除等操作的算法。3.通過線性表結(jié)構(gòu)解決現(xiàn)實中的一些問題。三實驗過程1、實驗題目[問題描述]（1）用頭插法或尾插法建立一個單鏈表，并將結(jié)果顯示到屏幕上。（2）對建好的單鏈表實現(xiàn)查找、插入、刪除、修改等操作。（3）設(shè)計一個選擇菜單。[基本要求]（1）按實驗內(nèi)容編寫完整的程序，并上機驗證。（2）實驗完成后，提交電子檔教師驗收程序，并提交填寫好的實驗報告。[測試數(shù)據(jù)]由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。[提高篇]（選作）建立一個有序單鏈表，實現(xiàn)上述操作。2、源程序#include"stdio.h"#include"malloc.h"typedefstructNode{chardata; structNode*next;}Node,*linklist;voidcreatefromtail(linklistL){Node*r,*s; intflag=1; charc; r=L; printf("請輸入線性表的元素以$結(jié)束:"); while(flag) {c=getchar(); if(c!='$') {s=(Node*)malloc(sizeof(Node)); s->data=c; r->next=s; r=s;} else{ flag=0; r->next=NULL;} }}charget(linklistL,inti){intj; Node*p; if(i<=0)return0; p=L;j=0; while((p->next!=NULL)&&(j<i)) {p=p->next; j++;} if(i==j)returnp->data; elsereturn0;}intinslist(linklistL,inti,charx){Node*pre,*s; intk; if(i<=0) {printf("插入位置不合法！\n"); return0;}pre=L;k=0; while(pre!=NULL&&k<i-1) {pre=pre->next; k=k+1;} if(!pre) {printf("插入位置不合法！\n"); return0;} else {s=(Node*)malloc(sizeof(Node)); s->data=x; s->next=pre->next; pre->next=s;} }intdeilist(linklistL,inti){Node*pre,*r;intk;pre=L;k=0;while(pre->next!=NULL&&k<i-1){pre=pre->next;k=k+1;}if(!(pre->next)){printf("刪除的節(jié)點位置不合法！\n"); return0;}r=pre->next;pre->next=r->next;free(r);return1;}voidalterlist(linklistL,inti,charx){intj; linklistp; p=L;j=0; if(i<=0) printf("修改位置不合法！\n"); else {while((p->next!=NULL)&&(j<i)) {p=p->next; j++;} p->data=x; printf("修改成功!\n");}}voidprint(linklistL){linklistp;p=L->next;while(p){printf("%c",p->data); p=p->next;}printf("\n");}intmain(){linklistL;inti,choice,x,j;createfromtail(L); do{printf("請選擇您想要對線性表的操作:1:插入2:刪除3:查找4:修改5：打印0:退出\n");scanf("%d",&choice); switch(choice){ case1: charc; printf("請輸入要插入的字符的位置："); scanf("%d",&j); printf("請輸入要插入的字符："); c=getchar(); c=getchar(); inslist(L,j,c); printf("插入字符后的線性表為："); print(L); break; case2: intm;printf("請輸入要刪除的字符的位置:"); scanf("%d",&m); deilist(L,m); printf("刪除字符后的線性表為："); print(L); break; case3: intn; printf("請輸入要查找的字符的位置："); scanf("%d",&n); printf("您要查找的字符為%c.\n",get(L,n)); break; case4: inta; charx; printf("請輸入要修改的字符的位置:"); scanf("%d",&a); printf("請輸入要修改的字符:"); x=getchar(); x=getchar(); alterlist(L,a,x); printf("修改字符后的線性表為："); print(L); break; case5:print(L); case0:break; default: printf("請選擇正確的操作！\n"); break;} }while(choice!=0); printf("謝謝使用!\n"); return0; }四實驗小結(jié)初步了解線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，及其定義格式。掌握了在鏈表上進行插入、刪除等操作的算法。對鏈表的了解不是很深入，在其使用上往往會犯一些錯誤比如在鏈表中進行插入插不到指定位置，刪除時位置錯誤等。五成績

實驗三實驗名稱線性表綜合練習(xí)實驗性質(zhì)設(shè)計性實驗學(xué)時數(shù)6學(xué)時一、實驗?zāi)康?．根據(jù)實際問題，應(yīng)用線性表的順序存儲結(jié)構(gòu)。2．根據(jù)實際問題，深入理解線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。3．通過線性表結(jié)構(gòu)解決現(xiàn)實中的一些問題。二、實驗內(nèi)容1.線性表的兩種存儲結(jié)構(gòu)。2.不同存儲結(jié)構(gòu)上進行插入、刪除等操作的算法。3.通過線性表結(jié)構(gòu)解決現(xiàn)實中的一些問題。三、實驗過程1、實驗題目[問題描述]設(shè)計一個學(xué)生信息系統(tǒng)，要求：（1）每條信息包含學(xué)號，姓名，性別，院系，宿舍等項。（2）能夠?qū)?shù)據(jù)信息進行查找，插入，刪除等。（3）選擇合適的存儲結(jié)構(gòu)，在主程序上運行，驗證其正確性，并寫出程序執(zhí)行結(jié)果。[基本要求]（1）按實驗內(nèi)容編寫完整的程序，并上機驗證。（2）實驗完成后，提交電子檔教師驗收程序，并提交填寫好的實驗報告。[測試數(shù)據(jù)]由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。2、源程序#include"stdio.h"#include"string.h"#include"stdlib.h"#include"malloc.h"typedefstructNode{charnumber[10];charname[10];charsex[4];chardepartment[16];chardorm[6]; structNode*next; }Node,*linklist;voidcreatefromtail(linklistL){ inti,n; printf("請輸入學(xué)生數(shù):"); scanf("%d",&n); charnumber[10],name[10],sex[4],department[16],dorm[6]; Node*r,*s; r=L; printf("請輸入學(xué)生的信息!\n"); for(i=0;i<n;i++) { printf("請輸入學(xué)生學(xué)號："); scanf("%s",number); printf("請輸入學(xué)生姓名："); scanf("%s",name); printf("請輸入學(xué)生性別："); scanf("%s",sex); printf("請輸入學(xué)生院系："); scanf("%s",department); printf("請輸入學(xué)生宿舍號："); scanf("%s",dorm); s=(Node*)malloc(sizeof(Node)); strcpy(s->number,number); strcpy(s->name,name); strcpy(s->sex,sex); strcpy(s->department,department); strcpy(s->dorm,dorm); r->next=s; r=s; } r->next=NULL;}intinslist(linklistL){ charnumber[10],name[10],sex[4],department[16],dorm[6]; Node*pre,*s; intk,i; printf("請輸入插入位置"); scanf("%d",&i); if(i<=0) { printf("插入位置不合法！\n"); return0; } pre=L;k=0; while(pre!=NULL&&k<i-1) { pre=pre->next; k=k+1; } if(!pre) { printf("插入位置不合法！\n"); return0; } else { printf("請輸入學(xué)生學(xué)號："); scanf("%s",number); printf("請輸入學(xué)生姓名："); scanf("%s",name); printf("請輸入學(xué)生性別："); scanf("%s",sex); printf("請輸入學(xué)生院系："); scanf("%s",department); printf("請輸入學(xué)生宿舍號："); scanf("%s",dorm); s=(Node*)malloc(sizeof(Node)); strcpy(s->number,number); strcpy(s->name,name); strcpy(s->sex,sex); strcpy(s->department,department); strcpy(s->dorm,dorm); s->next=pre->next; pre->next=s; } }intget(linklistL,inti){ charnumber[10],name[10],sex[4],department[16],dorm[6]; intj; Node*p; if(i<=0)return0; p=L;j=0; while((p->next!=NULL)&&(j<i)) { p=p->next; j++; } if(i==j) { printf("該學(xué)生的信息為：\n"); printf("學(xué)號：%s",p->number); printf("姓名：%s",p->name); printf("性別：%s",p->sex); printf("學(xué)院：%s",p->department); printf("宿舍號：%s",p->dorm); printf("\n"); } elsereturn0;}intdeilist(linklistL){Node*pre,*r;intk,i;printf("請輸入要刪除的字符的位置:");scanf("%d",&i);pre=L;k=0;while(pre->next!=NULL&&k<i-1){pre=pre->next;k=k+1;}if(!(pre->next)){ printf("刪除的節(jié)點位置不合法！\n"); return0;}r=pre->next;pre->next=r->next;free(r);return1;}voidprint(linklistL){linklistp;p=L->next;while(p){ printf("學(xué)號：%s",p->number); printf("姓名：%s",p->name); printf("性別：%s",p->sex); printf("學(xué)院：%s",p->department); printf("宿舍號：%s",p->dorm); printf("\n"); p=p->next;}}intmain(){linklistL;inti,choice,x,j;createfromtail(L); do {printf("請選擇您想要對線性表的操作:1:插入2:刪除3:查找4：打印0:退出\n");scanf("%d",&choice); switch(choice){ case1: inslist(L); print(L); break; case2: deilist(L); print(L); break; case3: intn; printf("請輸入要查找的學(xué)生的位置："); scanf("%d",&n); get(L,n); break; case4: print(L); break; case0: break; default: printf("請選擇正確的操作！\n"); break; } }while(choice!=0); printf("謝謝使用!\n"); return0; }四實驗小結(jié)對鏈?zhǔn)奖碛辛诉M一步的了解，能夠利用鏈?zhǔn)奖斫鉀Q一些實際問題。了解了鏈?zhǔn)奖淼膬?yōu)勢，他不會造成空間的浪費，對于插入和刪除操作上鏈?zhǔn)奖肀软樞虮碛忻黠@的優(yōu)勢。五成績實驗四實驗名稱棧和隊列及其應(yīng)用實驗性質(zhì)設(shè)計性實驗學(xué)時數(shù)4學(xué)時一、實驗?zāi)康?．掌握棧與隊列的抽象數(shù)據(jù)類型描述及特點。2．掌握棧和隊列的順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)與基本算法實現(xiàn)。3．掌握棧和隊列在實際問題中的應(yīng)用和基本編程技巧。二、實驗內(nèi)容1.棧和隊列在不同存儲結(jié)構(gòu)上進行插入、刪除等操作的算法。2.通過棧或隊列解決現(xiàn)實中的一些問題。1、實驗題目[問題描述]以下題目根據(jù)自己興趣和能力可選作一道作為實驗題目：（1）根據(jù)棧的數(shù)據(jù)結(jié)構(gòu)，建立一個順序棧和鏈棧并實現(xiàn)對其基本操作；（2）根據(jù)隊列的數(shù)據(jù)結(jié)構(gòu)，建立一個循環(huán)隊列和鏈隊并實現(xiàn)對其基本操作；（3）根據(jù)教材3.4.3（4）銀行業(yè)務(wù)隊列簡單模擬。設(shè)某銀行有A、B兩個業(yè)務(wù)窗口，其中A窗口的處理速度是B窗口的2倍，給定到達(dá)銀行的顧客序號，請按業(yè)務(wù)完成的順序輸出顧客序列（假設(shè)奇數(shù)編號到A窗口辦理，偶數(shù)編號到B窗口辦理，不同窗口同時處理完2個顧客，A窗口優(yōu)先輸出）。[基本要求]（1）按實驗內(nèi)容編寫完整的程序，并上機驗證。（2）實驗完成后，提交電子檔教師驗收程序，并提交填寫好的實驗報告。[測試數(shù)據(jù)]由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。三實驗過程2、源程序#include"stdio.h"#include"stdlib.h"typedefstruct{intelem[50];inttop;}Seqstack;typedefstructnode{intdata; structnode*next;}linkstacknode;typedeflinkstacknode*linkstack;voidinitstack(Seqstack*s){s->top=-1;}intpush(Seqstack*s,intx){if(s->top==49) {printf("棧已滿！\n"); return0;} s->top++;s->elem[s->top]=x; return1;}voidpop(Seqstack*s){intx; if(s->top==-1)printf("棧為空！\n"); else{ x=s->elem[s->top]; s->top--; printf("出棧元素為：%d.\n",x);}}voidprint(Seqstacks){inti;if(s.top==-1)printf("棧為空！\n");else{printf("棧里的元素為：");do{printf("%4d",s.elem[s.top]); s.top--;}while(s.top!=-1);printf("\n");}}voidinitlinstack(linkstacktop){top->next=NULL;}intPush(linkstacktop,intx){linkstacknode*temp; temp=(linkstacknode*)malloc(sizeof(linkstacknode)); if(temp==NULL) return0; else {temp->data=x; temp->next=top->next; top->next=temp; return1; } }intPop(linkstacktop){intx; linkstacknode*temp; temp=top->next; if(temp==NULL) {printf("棧已空！\n"); return0;} else {x=temp->data; top->next=temp->next; free(temp); returnx;} }voidPrint(linkstacks){printf("棧里的元素為:"); while(s->next!=NULL) printf("%4d",Pop(s));printf("\n");}intmain(){intchoice,choice1,choice2,x1,x2,y;Seqstacks1;linkstacknodes2;do{printf("請輸入你的選擇:(1)對順序棧操作（2）對鏈棧操作0:退出\n");scanf("%d",&choice);switch(choice){case1:initstack(&s1);do{printf("請輸入你的選擇:(1)入棧（2）出棧（3）打印0:退出\n");scanf("%d",&choice1);switch(choice1){case1:printf("請輸入入棧元素：");scanf("%d",&x1);push(&s1,x1);break;case2:pop(&s1);break;case3:print(s1);break;case0:break;}}while(choice1!=0);break;case2:initlinstack(&s2);do{printf("請輸入你的選擇:(1)入棧（2）出棧（3）打印0:退出\n");scanf("%d",&choice2); switch(choice2){case1:printf("請輸入入棧元素：");scanf("%d",&x2);Push(&s2,x2);break;case2:y=Pop(&s2);if(y!=0)printf("出棧元素為：%d.\n",y);break;case3:Print(&s2);break;case0:break;}}while(choice2!=0);break;case0:break;}}while(choice!=0);return0;}四實驗總結(jié)對棧和隊列有了初步的了解，他們都是一種特殊的操作受限制線性表，棧的特點是先進后出而隊列的是先進先出。在寫程序中出現(xiàn)了一些問題，參數(shù)傳遞不匹配，還有一些錯誤雖然編譯通過了但執(zhí)行的時候卻錯誤了，后經(jīng)調(diào)試修改得到是參數(shù)傳遞過程中出現(xiàn)了問題。五成績

實驗五實驗名稱二叉樹及其應(yīng)用實驗性質(zhì)設(shè)計性實驗學(xué)時數(shù)6學(xué)時一、實驗?zāi)康?．掌握二叉樹鏈表的結(jié)構(gòu)和構(gòu)造過程。2．掌握用遞歸方法實現(xiàn)二叉樹的遍歷。3．加強對二叉樹的理解，培養(yǎng)解決實際問題的能力。二、實驗內(nèi)容1.用遞歸方法實現(xiàn)對二叉樹的遍歷等操作。2.二叉樹的其他操作算法。三、實驗過程1、實驗題目[問題描述]以下題目根據(jù)自己興趣和能力可選作二道作為實驗題目：（1）創(chuàng)建一顆二叉樹，用遞歸方法實現(xiàn)對其進行先序、中序和后序遍歷的操作；（2）根據(jù)題目1，修改其中一個算法，用來計算統(tǒng)計二叉樹中葉子節(jié)點的個數(shù)和度為1、度為2的節(jié)點個數(shù)；（3）設(shè)計并實現(xiàn)一個哈夫曼樹并對其進行編碼。（4）修理牧場。農(nóng)夫要修理牧場的一段柵欄，發(fā)現(xiàn)需要N塊木頭，每塊木頭長度為整數(shù)Li個長度單位，于是他購買了一條很長的、能鋸成N塊的木頭，即該木頭的長度是Li的總和。但是農(nóng)夫自己沒有鋸子，請人鋸木的酬金跟這段木頭的長度成正比。簡單起見，設(shè)酬金等于所鋸木頭的長度。例如，將長度為20的木頭鋸成長度為8、7和5的三段，第一次鋸木頭將木頭鋸成12和8，花費20；第二次將木頭長度為12的木頭鋸成7和5花費12，總花費為32.如果第一次將木頭鋸成15和5，則第二次鋸木頭花費15，總花費35（大于32）。請編寫程序幫助農(nóng)夫計算將木頭鋸成N塊的最少花費。輸入數(shù)據(jù)N表示要將木頭鋸成N塊，然后輸入N個整數(shù)，表示每段木塊的長度。輸出將木頭鋸成N塊的最少花費。（可采用哈夫曼算法和最小堆實現(xiàn)）[基本要求]（1）按實驗內(nèi)容編寫完整的程序，并上機驗證。（2）實驗完成后，提交電子檔教師驗收程序，并提交填寫好的實驗報告。[測試數(shù)據(jù)]由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。實驗過程實驗過程2、源程序一#include"stdio.h"#include"stdlib.h"typedefstructnode{chardata; structnode*lchild; structnode*rchild;}bitnode,*bitree;voidinist(bitree*root){(*root)=(bitree)malloc(sizeof(bitnode)); (*root)->lchild=NULL; (*root)->rchild=NULL;}bitreecreate(bitreeroot){charch; ch=getchar(); if(ch!='.') {if((root=(bitree)malloc(sizeof(bitnode)))!=NULL) root->data=ch; root->lchild=create(root->lchild); root->rchild=create(root->rchild); } else root=NULL; returnroot;}voidpreorder(bitreeroot){if(root!=NULL) {printf("%c",root->data); preorder(root->lchild); preorder(root->rchild); }}voidinorder(bitreeroot){if(root!=NULL) {inorder(root->lchild); printf("%c",root->data); inorder(root->rchild); }}voidpostorder(bitreeroot){if(root!=NULL) {postorder(root->lchild); postorder(root->rchild); printf("%c",root->data); }}intmain(){intchoice;bitreeroot;inist(&root);printf("初始化成功！\n");root=(bitree)malloc(sizeof(bitnode));printf("請輸入字符以.結(jié)束:");root=create(root);do{printf("請輸入你的選擇:1前序遍歷2中序遍歷3后序遍歷0退出\n"); scanf("%d",&choice); switch(choice) {case1: preorder(root); printf("\n"); break; case2: inorder(root); printf("\n"); break; case3: postorder(root); printf("\n"); break; case0: break; default: printf("輸入不合法，請重新輸入！\n"); break;}}while(choice!=0);printf("謝謝使用！\n");return0; }2#include"stdio.h"#include"stdlib.h"intleafcount=0;intleafcount1=0;intleafcount2=0;typedefstructnode{chardata; structnode*lchild; structnode*rchild;}bitnode,*bitree;voidinist(bitree*root){(*root)=(bitree)malloc(sizeof(bitnode)); (*root)->lchild=NULL; (*root)->rchild=NULL;}bitreecreate(bitreeroot){charch; ch=getchar(); if(ch!='.') {if((root=(bitree)malloc(sizeof(bitnode)))!=NULL) root->data=ch; root->lchild=create(root->lchild); root->rchild=create(root->rchild); } else root=NULL; returnroot;}voidleaf(bitreeroot){if(root!=NULL) {leaf(root->lchild); leaf(root->rchild); if(root->lchild==NULL&&root->rchild==NULL) leafcount++; }}voidleaf1(bitreeroot){if(root!=NULL) {leaf1(root->lchild); leaf1(root->rchild);if((root->lchild!=NULL&&root->rchild==NULL)||(root->lchild==NULL&&root->rchild!=NULL)) leafcount1++; }}voidleaf2(bitreeroot){if(root!=NULL) {leaf2(root->lchild); leaf2(root->rchild); if(root->lchild!=NULL&&root->rchild!=NULL) leafcount2++; }}intmain(){intchoice;bitreeroot;inist(&root);printf("初始化成功！\n");root=(bitree)malloc(sizeof(bitnode));printf("請輸入字符以.結(jié)束:");root=create(root);leaf(root);leaf1(root);leaf2(root);printf("葉子節(jié)點數(shù)為%d.\n",leafcount);printf("度為1的節(jié)點數(shù)為%d.\n",leafcount1);printf("度為2的節(jié)點數(shù)為%d.\n",leafcount2);return0; }四實驗小結(jié)了解二叉樹鏈表的結(jié)構(gòu)和構(gòu)造過程?？梢杂眠f歸方法實現(xiàn)二叉樹的遍歷。對二叉樹有了進一步的理解能夠求出二叉樹中葉子節(jié)點，度為1一季度為2的節(jié)點的個數(shù)五成績

實驗六實驗名稱圖及其應(yīng)用實驗性質(zhì)設(shè)計性實驗學(xué)時數(shù)6學(xué)時一、實驗?zāi)康?．掌握圖的存儲結(jié)構(gòu)及其實現(xiàn)。2．掌握圖的深度和廣度遍歷算法及其實現(xiàn)。3．掌握圖的常見算法的思想及應(yīng)用。二、實驗內(nèi)容1.實現(xiàn)對無向圖的存儲和遍歷等操作。2.最小生成樹問題。三實驗過程1、實驗題目[問題描述]以下題目根據(jù)自己興趣和能力可選作一道作為實驗題目：（1）使用鄰接表或鄰接矩陣存儲一個無向圖，實現(xiàn)對其進行深度和廣度遍歷的操作；（2）n個城市之間建立通信聯(lián)絡(luò)網(wǎng)，最多可能設(shè)置n(n-1)/2條線路，那么，如何在這些可能的線路中選擇n-1條，以使總的耗費最少。使用最小生成樹實現(xiàn)解決此問題。[基本要求]（1）按實驗內(nèi)容編寫完整的程序，并上機驗證。（2）實驗完成后，提交電子檔教師驗收程序，并提交填寫好的實驗報告。[測試數(shù)據(jù)]由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。2、源程序#include"stdlib.h"#include"stdio.h"intvisited[20];typedefstructArcNode{ intadj;}ArcNode;typedefstruct{ intvertex[20]; ArcNodearc[20][20]; intvexnum,arcnum;}AdjMatrix;voidCreate(AdjMatrix*G){inti,j,k,n,e; printf("請輸入圖中頂點個數(shù)和邊數(shù)："); scanf("%d%d",&n,&e);G->vexnum=n; G->arcnum=e;printf("請輸入頂點的值：");for(i=0;i<G->vexnum;i++) {scanf("%d",&G->vertex[i]);} for(i=0;i<G->vexnum;i++) {for(j=0;j<G->vexnum;j++) G->arc[i][j].adj=0;}printf("請輸入有關(guān)聯(lián)的兩個頂點下標(biāo)：\n");for(k=0;k<G->arcnum;k++){ scanf("%d%d",&i,&j);G->arc[i][j].adj=1; G->arc[j][i].adj=1;}}voidDepthFirstSearch(AdjMatrixg,inti){intj;printf("%d",g.vertex[i]);visited[i]=1;for(j=0;j<g.vexnum;j++)if(!visited[j]&&g.arc[i][j].adj==1)DepthFirstSearch(g,j);}voidTraverseGraph(AdjMatrixg){inti; for(i=0;i<g.vexnum;i++) visited[i]=0; for(i=0;i<g.vexnum;i++) if(!visited[i])DepthFirstSearch(g,i);}intmain(){inti,j; AdjMatrixg; Create(&g); printf("輸出關(guān)系二維矩陣：");for(i=0;i<g.vexnum;i++) {for(j=0;j<g.vexnum;j++)printf("%d",g.arc[i][j].adj);printf("\t");} printf("無向圖的遍歷："); TraverseGraph(g); printf("\n"); return0;}四實驗總結(jié)了解圖的存儲結(jié)構(gòu)以及圖的深度和廣度遍歷算法。能夠使用鄰接矩陣存儲一個無向圖，實現(xiàn)對其進行深度和廣度遍歷的操作。五成績實驗七實驗名稱查找實驗性質(zhì)設(shè)計性實驗學(xué)時數(shù)4學(xué)時一、實驗?zāi)康?．熟練掌握各種靜態(tài)查找表方法(順序查找、折半查找、索引順序表等)；2．熟練掌握二叉排序樹的構(gòu)造方法和查找算法；3．了解和掌握其它查找方法。二、實驗內(nèi)容1.實現(xiàn)順序查找、折半查找等操作。2.二叉排序樹和哈希查找的實現(xiàn)。1、實驗題目[問題描述]以下題目根據(jù)自己興趣和能力可選作一道作為實驗題目：(1)順序查找、折半查找算法的實現(xiàn)；(2)二叉排序樹的構(gòu)造與查找算法的實現(xiàn)；(3)Hash表的查找算法實現(xiàn)。[基本要求]（1）按實驗內(nèi)容編寫完整的程序，并上機驗證。（2）實驗完成后，提交電子檔教師驗收程序，并提交填寫好的實驗報告。[測試數(shù)據(jù)]由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。2、源程序#include"stdio.h"typedefstruct{ intr[21]; intlength;}recordlist;voidinsertinto(recordlist*l,intx){ inti; l->length=x;for(i=1;i<l->length+1;i++)scanf("%d",&l->r[i]); }intseqsearch(recordlistl,intk){ inti; l.r[0]=k; i=l.length; while(l.r[i]!=k) i--; return(i);}intbinsrch(recordlistl,intk){ intlow,high,mid; low=1; high=l.length; while(low<=high) { mid=(low+high)/2; if(k==l.r[mid]) returnmid; elseif(k<l.r[mid]) high=mid-1; else low=mid+1; } return0;}intmain(){ intk,k1,x; recordlistl; printf("請輸入數(shù)據(jù)長度：");