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

《數(shù)據(jù)結(jié)構(gòu)》課程實驗教學(xué)手冊姓 名： 王俊東學(xué) 號： 1101120216專 業(yè)： 計算機科學(xué)與技術(shù)班 級： 2012 級 2 班任課教師： 王爽時 間：2013-2014年度第1學(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)容說明如下：1、實驗預(yù)習(xí)報告必須在實驗前完成。2、實驗時帶好實驗手冊方可進(jìn)行實驗。3、實驗時按實驗預(yù)習(xí)報告容進(jìn)行實驗。并如實填寫實驗過程及實驗小結(jié)。4、實驗結(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)上進(jìn)行插入、刪除等操作的算法。3．通過線性表結(jié)構(gòu)解決現(xiàn)實中的一些問題。二、實驗容線性表的順序存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)上進(jìn)行插入、刪除等操作的算法。通過線性表結(jié)構(gòu)解決現(xiàn)實中的一些問題。三

1、實驗題目[問題描述]設(shè)計一個順序表，要求：（1）包含不少于5個元素，并在屏幕上顯示。（2）對建好的順序表實現(xiàn)查找、插入、刪除等操作，并程序執(zhí)行結(jié)果顯示到屏幕上。（3）設(shè)計一個選擇菜單。[基本要求]（1）按實驗容編寫完整的程序，并上機驗證。實（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é)構(gòu)，及其定義格式。驗掌握在順序表上進(jìn)行插入、刪除等操作的算法。小 但在順序表的操作上不是十分熟練。結(jié)五成績實驗二實驗名稱 單鏈表及其應(yīng)用 實驗性質(zhì) 綜合性 實驗學(xué)時數(shù) 4學(xué)時一、實驗?zāi)康?．深入了解線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。2．熟練掌握在鏈?zhǔn)酱鎯Y(jié)構(gòu)上進(jìn)行插入、刪除等操作的算法。3．通過線性表結(jié)構(gòu)解決現(xiàn)實中的一些問題。二、實驗容線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。鏈?zhǔn)酱鎯Y(jié)構(gòu)上進(jìn)行插入、刪除等操作的算法。通過線性表結(jié)構(gòu)解決現(xiàn)實中的一些問題。1、實驗題目[問題描述]（1）用頭插法或尾插法建立一個單鏈表，并將結(jié)果顯示到屏幕上。（2）對建好的單鏈表實現(xiàn)查找、插入、刪除、修改等操作。（3）設(shè)計一個選擇菜單。[基本要求]（1）按實驗容編寫完整的程序，并上機驗證。（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;}四 初步了解線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，及其定義格式。實 掌握了在鏈表上進(jìn)行插入、刪除等操作的算法。驗 對鏈表的了解不是很深入，在其使用上往往會犯一些錯誤比如在鏈表小中進(jìn)行插入插不到指定位置，刪除時位置錯誤等。結(jié)五成績實驗三實驗名稱 線性表綜合練習(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)實中的一些問題。二、實驗容線性表的兩種存儲結(jié)構(gòu)。不同存儲結(jié)構(gòu)上進(jìn)行插入、刪除等操作的算法。通過線性表結(jié)構(gòu)解決現(xiàn)實中的一些問題。1、實驗題目[問題描述]、設(shè)計一個學(xué)生信息系統(tǒng)，要求：實（1）每條信息包含學(xué)號，姓名，性別，院系，宿舍等項。驗（2）能夠?qū)?shù)據(jù)信息進(jìn)行查找，插入，刪除等。過（3）選擇合適的存儲結(jié)構(gòu)，在主程序上運行，驗證其正確性，并寫出程序執(zhí)行程結(jié)果。[基本要求]（1）按實驗容編寫完整的程序，并上機驗證。（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;}四 對鏈?zhǔn)奖碛辛诉M(jìn)一步的了解，能夠利用鏈?zhǔn)奖斫鉀Q一些實際問題。實了解了鏈?zhǔn)奖淼膬?yōu)勢，他不會造成空間的浪費，對于插入和刪除操作上鏈?zhǔn)奖肀软樞虮碛序炐?明顯的優(yōu)勢。結(jié)五成績實驗四實驗名稱 棧和隊列及其應(yīng)用 實驗性質(zhì) 設(shè)計性 實驗學(xué)時數(shù) 4學(xué)時一、實驗?zāi)康?．掌握棧與隊列的抽象數(shù)據(jù)類型描述及特點。2．掌握棧和隊列的順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)與基本算法實現(xiàn)。3．掌握棧和隊列在實際問題中的應(yīng)用和基本編程技巧。二、實驗容1.棧和隊列在不同存儲結(jié)構(gòu)上進(jìn)行插入、刪除等操作的算法。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節(jié)介紹的思想，設(shè)計并實現(xiàn)一個對簡化表達(dá)式求值的系統(tǒng)（4）銀行業(yè)務(wù)隊列簡單模擬。設(shè)某銀行有 A、B兩個業(yè)務(wù)窗口，其中 A窗口的處理速度是B窗口的2倍，給定到達(dá)銀行的顧客序號，請按業(yè)務(wù)完成的順序輸出顧客序列（假設(shè)奇數(shù)編號到A窗口辦理，偶數(shù)編號到B窗口辦理，不同窗口同時處理完2個顧客，A窗口優(yōu)先輸出）。[基本要求]（1）按實驗容編寫完整的程序，并上機驗證。（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）對鏈棧操作scanf("%d",&choice);switch(choice){case1:initstack(&s1);do{printf("請輸入你的選擇:(1)入棧 （2）出棧 （3）打印scanf("%d",&choice1);switch(choice1){case1:

0:退出\n");0:退出\n");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;}四 對棧和隊列有了初步的了解，他們都是一種特殊的操作受限制線性表，棧實 的特點是先進(jìn)后出而隊列的是先進(jìn)先出。驗 在寫程序中出現(xiàn)了一些問題，參數(shù)傳遞不匹配，還有一些錯誤雖然編譯通總 過了但執(zhí)行的時候卻錯誤了，后經(jīng)調(diào)試修改得到是參數(shù)傳遞過程中出現(xiàn)了結(jié) 問題。五成績實驗五實驗名稱 二叉樹及其應(yīng)用 實驗性質(zhì) 設(shè)計性 實驗學(xué)時數(shù) 6學(xué)時一、實驗?zāi)康?．掌握二叉樹鏈表的結(jié)構(gòu)和構(gòu)造過程。2．掌握用遞歸方法實現(xiàn)二叉樹的遍歷。3．加強對二叉樹的理解，培養(yǎng)解決實際問題的能力。二、實驗容用遞歸方法實現(xiàn)對二叉樹的遍歷等操作。二叉樹的其他操作算法。1、實驗題目[問題描述]、以下題目根據(jù)自己興趣和能力可選作二道作為實驗題目：實（1）創(chuàng)建一顆二叉樹，用遞歸方法實現(xiàn)對其進(jìn)行先序、中序和后序遍歷的操作；（2）根據(jù)題目1，修改其中一個算法，用來計算統(tǒng)計二叉樹中葉子節(jié)點的個數(shù)驗和度為1、度為2的節(jié)點個數(shù)；過（3）設(shè)計并實現(xiàn)一個哈夫曼樹并對其進(jì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）按實驗容編寫完整的程序，并上機驗證。（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);}elseroot=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);}elseroot=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)造過程。可以用遞歸方法實現(xiàn)二叉樹的遍歷。對二叉樹有了進(jì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)用。二、實驗容實現(xiàn)對無向圖的存儲和遍歷等操作。最小生成樹問題。、實驗題目[問題描述]以下題目根據(jù)自己興趣和能力可選作一道作為實驗題目：（1）使用鄰接表或鄰接矩陣存儲一個無向圖，實現(xiàn)對其進(jìn)行深度和廣度遍歷的操作；（2）n個城市之間建立通信聯(lián)絡(luò)網(wǎng)，最多可能設(shè)置 n(n-1)/2條線路，那么，如何在這些可能的線路中選擇 n-1條，以使總的耗費最少。使用最小生成樹實現(xiàn)解決此問題。[基本要求]實 （1）按實驗容編寫完整的程序，并上機驗證。驗 （2）實驗完成后，提交電子檔教師驗收程序，并提交填寫好的實驗報告。過[測試數(shù)據(jù)]程 由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。、源程序#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,{ 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);

inti)}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é)構(gòu)以及圖的深度和廣度遍歷算法。實 能夠使用鄰接矩陣存儲一個無向圖，實現(xiàn)對其進(jìn)行深度和廣度遍歷的操作。驗總結(jié)五成績實驗七實驗名稱 查 找 實驗性質(zhì) 設(shè)計性 實驗學(xué)時數(shù) 4學(xué)時一、實驗?zāi)康?．熟練掌握各種靜態(tài)查找表方法 (順序查找、折半查找、索引順序表等 )；2．熟練掌握二叉排序樹的構(gòu)造方法和查找算法；3．了解和掌握其它查找方法。二、實驗容1.實現(xiàn)順序查找、折半查找等操作。2.二叉排序樹和哈希查找的實現(xiàn)。1、實驗題目[問題描述]以下題目根據(jù)自己興趣和能力可選作一道作為實驗題目：順序查找、折半查找算法的實現(xiàn)；二叉排序樹的構(gòu)造與查找算法的實現(xiàn)；Hash表的查找算法實現(xiàn)。[基本要求]（1）按實驗容編寫完整的程序，并上機驗證。（2）實驗完成后，提交電子檔教師驗收程序，并提交填寫好的實驗報告。[測試數(shù)據(jù)]由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。、源程序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;elselow=mid+1;}return0;}intmain(){intk,k1,x;recordlistl;printf("請輸入數(shù)據(jù)長度：");scanf("%d",&x);printf("請輸入%