數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教學(xué)手冊(cè)

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

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

實(shí)驗(yàn)二實(shí)驗(yàn)名稱單鏈表及其應(yīng)用實(shí)驗(yàn)性質(zhì)綜合性實(shí)驗(yàn)學(xué)時(shí)數(shù)4學(xué)時(shí)一、實(shí)驗(yàn)?zāi)康?．深入了解線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。2．熟練掌握在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上進(jìn)行插入、刪除等操作的算法。3．通過(guò)線性表結(jié)構(gòu)解決現(xiàn)實(shí)中的一些問(wèn)題。二、實(shí)驗(yàn)內(nèi)容1.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上進(jìn)行插入、刪除等操作的算法。3.通過(guò)線性表結(jié)構(gòu)解決現(xiàn)實(shí)中的一些問(wèn)題。三實(shí)驗(yàn)過(guò)程1、實(shí)驗(yàn)題目[問(wèn)題描述]（1）用頭插法或尾插法建立一個(gè)單鏈表，并將結(jié)果顯示到屏幕上。（2）對(duì)建好的單鏈表實(shí)現(xiàn)查找、插入、刪除、修改等操作。（3）設(shè)計(jì)一個(gè)選擇菜單。[基本要求]（1）按實(shí)驗(yàn)內(nèi)容編寫(xiě)完整的程序，并上機(jī)驗(yàn)證。（2）實(shí)驗(yàn)完成后，提交電子檔教師驗(yàn)收程序，并提交填寫(xiě)好的實(shí)驗(yàn)報(bào)告。[測(cè)試數(shù)據(jù)]由學(xué)生依據(jù)軟件工程的測(cè)試技術(shù)自己確定。注意測(cè)試邊界數(shù)據(jù)。[提高篇]（選作）建立一個(gè)有序單鏈表，實(shí)現(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("請(qǐng)輸入線性表的元素以$結(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é)點(diǎn)位置不合法！\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("請(qǐng)選擇您想要對(duì)線性表的操作:1:插入2:刪除3:查找4:修改5：打印0:退出\n");scanf("%d",&choice); switch(choice){ case1: charc; printf("請(qǐng)輸入要插入的字符的位置："); scanf("%d",&j); printf("請(qǐng)輸入要插入的字符："); c=getchar(); c=getchar(); inslist(L,j,c); printf("插入字符后的線性表為："); print(L); break; case2: intm;printf("請(qǐng)輸入要?jiǎng)h除的字符的位置:"); scanf("%d",&m); deilist(L,m); printf("刪除字符后的線性表為："); print(L); break; case3: intn; printf("請(qǐng)輸入要查找的字符的位置："); scanf("%d",&n); printf("您要查找的字符為%c.\n",get(L,n)); break; case4: inta; charx; printf("請(qǐng)輸入要修改的字符的位置:"); scanf("%d",&a); printf("請(qǐng)輸入要修改的字符:"); x=getchar(); x=getchar(); alterlist(L,a,x); printf("修改字符后的線性表為："); print(L); break; case5:print(L); case0:break; default: printf("請(qǐng)選擇正確的操作！\n"); break;} }while(choice!=0); printf("謝謝使用!\n"); return0; }四實(shí)驗(yàn)小結(jié)初步了解線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，及其定義格式。掌握了在鏈表上進(jìn)行插入、刪除等操作的算法。對(duì)鏈表的了解不是很深入，在其使用上往往會(huì)犯一些錯(cuò)誤比如在鏈表中進(jìn)行插入插不到指定位置，刪除時(shí)位置錯(cuò)誤等。五成績(jī)

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

實(shí)驗(yàn)五實(shí)驗(yàn)名稱二叉樹(shù)及其應(yīng)用實(shí)驗(yàn)性質(zhì)設(shè)計(jì)性實(shí)驗(yàn)學(xué)時(shí)數(shù)6學(xué)時(shí)一、實(shí)驗(yàn)?zāi)康?．掌握二叉樹(shù)鏈表的結(jié)構(gòu)和構(gòu)造過(guò)程。2．掌握用遞歸方法實(shí)現(xiàn)二叉樹(shù)的遍歷。3．加強(qiáng)對(duì)二叉樹(shù)的理解，培養(yǎng)解決實(shí)際問(wèn)題的能力。二、實(shí)驗(yàn)內(nèi)容1.用遞歸方法實(shí)現(xiàn)對(duì)二叉樹(shù)的遍歷等操作。2.二叉樹(shù)的其他操作算法。三、實(shí)驗(yàn)過(guò)程1、實(shí)驗(yàn)題目[問(wèn)題描述]以下題目根據(jù)自己興趣和能力可選作二道作為實(shí)驗(yàn)題目：（1）創(chuàng)建一顆二叉樹(shù)，用遞歸方法實(shí)現(xiàn)對(duì)其進(jìn)行先序、中序和后序遍歷的操作；（2）根據(jù)題目1，修改其中一個(gè)算法，用來(lái)計(jì)算統(tǒng)計(jì)二叉樹(shù)中葉子節(jié)點(diǎn)的個(gè)數(shù)和度為1、度為2的節(jié)點(diǎn)個(gè)數(shù)；（3）設(shè)計(jì)并實(shí)現(xiàn)一個(gè)哈夫曼樹(shù)并對(duì)其進(jìn)行編碼。（4）修理牧場(chǎng)。農(nóng)夫要修理牧場(chǎng)的一段柵欄，發(fā)現(xiàn)需要N塊木頭，每塊木頭長(zhǎng)度為整數(shù)Li個(gè)長(zhǎng)度單位，于是他購(gòu)買(mǎi)了一條很長(zhǎng)的、能鋸成N塊的木頭，即該木頭的長(zhǎng)度是Li的總和。但是農(nóng)夫自己沒(méi)有鋸子，請(qǐng)人鋸木的酬金跟這段木頭的長(zhǎng)度成正比。簡(jiǎn)單起見(jiàn)，設(shè)酬金等于所鋸木頭的長(zhǎng)度。例如，將長(zhǎng)度為20的木頭鋸成長(zhǎng)度為8、7和5的三段，第一次鋸木頭將木頭鋸成12和8，花費(fèi)20；第二次將木頭長(zhǎng)度為12的木頭鋸成7和5花費(fèi)12，總花費(fèi)為32.如果第一次將木頭鋸成15和5，則第二次鋸木頭花費(fèi)15，總花費(fèi)35（大于32）。請(qǐng)編寫(xiě)程序幫助農(nóng)夫計(jì)算將木頭鋸成N塊的最少花費(fèi)。輸入數(shù)據(jù)N表示要將木頭鋸成N塊，然后輸入N個(gè)整數(shù)，表示每段木塊的長(zhǎng)度。輸出將木頭鋸成N塊的最少花費(fèi)。（可采用哈夫曼算法和最小堆實(shí)現(xiàn)）[基本要求]（1）按實(shí)驗(yàn)內(nèi)容編寫(xiě)完整的程序，并上機(jī)驗(yàn)證。（2）實(shí)驗(yàn)完成后，提交電子檔教師驗(yàn)收程序，并提交填寫(xiě)好的實(shí)驗(yàn)報(bào)告。[測(cè)試數(shù)據(jù)]由學(xué)生依據(jù)軟件工程的測(cè)試技術(shù)自己確定。注意測(cè)試邊界數(shù)據(jù)。實(shí)驗(yàn)過(guò)程實(shí)驗(yàn)過(guò)程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("請(qǐng)輸入字符以.結(jié)束:");root=create(root);do{printf("請(qǐng)輸入你的選擇: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("輸入不合法，請(qǐng)重新輸入！\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("請(qǐng)輸入字符以.結(jié)束:");root=create(root);leaf(root);leaf1(root);leaf2(root);printf("葉子節(jié)點(diǎn)數(shù)為%d.\n",leafcount);printf("度為1的節(jié)點(diǎn)數(shù)為%d.\n",leafcount1);printf("度為2的節(jié)點(diǎn)數(shù)為%d.\n",leafcount2);return0; }四實(shí)驗(yàn)小結(jié)了解二叉樹(shù)鏈表的結(jié)構(gòu)和構(gòu)造過(guò)程。可以用遞歸方法實(shí)現(xiàn)二叉樹(shù)的遍歷。對(duì)二叉樹(shù)有了進(jìn)一步的理解能夠求出二叉樹(shù)中葉子節(jié)點(diǎn)，度為1一季度為2的節(jié)點(diǎn)的個(gè)數(shù)五成績(jī)

實(shí)驗(yàn)六實(shí)驗(yàn)名稱圖及其應(yīng)用實(shí)驗(yàn)性質(zhì)設(shè)計(jì)性實(shí)驗(yàn)學(xué)時(shí)數(shù)6學(xué)時(shí)一、實(shí)驗(yàn)?zāi)康?．掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)及其實(shí)現(xiàn)。2．掌握?qǐng)D的深度和廣度遍歷算法及其實(shí)現(xiàn)。3．掌握?qǐng)D的常見(jiàn)算法的思想及應(yīng)用。二、實(shí)驗(yàn)內(nèi)容1.實(shí)現(xiàn)對(duì)無(wú)向圖的存儲(chǔ)和遍歷等操作。2.最小生成樹(shù)問(wèn)題。三實(shí)驗(yàn)過(guò)程1、實(shí)驗(yàn)題目[問(wèn)題描述]以下題目根據(jù)自己興趣和能力可選作一道作為實(shí)驗(yàn)題目：（1）使用鄰接表或鄰接矩陣存儲(chǔ)一個(gè)無(wú)向圖，實(shí)現(xiàn)對(duì)其進(jìn)行深度和廣度遍歷的操作；（2）n個(gè)城市之間建立通信聯(lián)絡(luò)網(wǎng)，最多可能設(shè)置n(n-1)/2條線路，那么，如何在這些可能的線路中選擇n-1條，以使總的耗費(fèi)最少。使用最小生成樹(shù)實(shí)現(xiàn)解決此問(wèn)題。[基本要求]（1）按實(shí)驗(yàn)內(nèi)容編寫(xiě)完整的程序，并上機(jī)驗(yàn)證。（2）實(shí)驗(yàn)完成后，提交電子檔教師驗(yàn)收程序，并提交填寫(xiě)好的實(shí)驗(yàn)報(bào)告。[測(cè)試數(shù)據(jù)]由學(xué)生依據(jù)軟件工程的測(cè)試技術(shù)自己確定。注意測(cè)試邊界數(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("請(qǐng)輸入圖中頂點(diǎn)個(gè)數(shù)和邊數(shù)："); scanf("%d%d",&n,&e);G->vexnum=n; G->arcnum=e;printf("請(qǐng)輸入頂點(diǎn)的值：");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("請(qǐng)輸入有關(guān)聯(lián)的兩個(gè)頂點(diǎ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("無(wú)向圖的遍歷："); TraverseGraph(g); printf("\n"); return0;}四實(shí)驗(yàn)總結(jié)了解圖的存儲(chǔ)結(jié)構(gòu)以及圖的深度和廣度遍歷算法。能夠使用鄰接矩陣存儲(chǔ)一個(gè)無(wú)向圖，實(shí)現(xiàn)對(duì)其進(jìn)行深度和廣度遍歷的操作。五成績(jī)實(shí)驗(yàn)七實(shí)驗(yàn)名稱查找實(shí)驗(yàn)性質(zhì)設(shè)計(jì)性實(shí)驗(yàn)學(xué)時(shí)數(shù)4學(xué)時(shí)一、實(shí)驗(yàn)?zāi)康?．熟練掌握各種靜態(tài)查找表方法(順序查找、折半查找、索引順序表等)；2．熟練掌握二叉排序樹(shù)的構(gòu)造方法和查找算法；3．了解和掌握其它查找方法。二、實(shí)驗(yàn)內(nèi)容1.實(shí)現(xiàn)順序查找、折半查找等操作。2.二叉排序樹(shù)和哈希查找的實(shí)現(xiàn)。1、實(shí)驗(yàn)題目[問(wèn)題描述]以下題目根據(jù)自己興趣和能力可選作一道作為實(shí)驗(yàn)題目：(1)順序查找、折半查找算法的實(shí)現(xiàn)；(2)二叉排序樹(shù)的構(gòu)造與查找算法的實(shí)現(xiàn)；(3)Hash表的查找算法實(shí)現(xiàn)。[基本要求]（1）按實(shí)驗(yàn)內(nèi)容編寫(xiě)完整的程序，并上機(jī)驗(yàn)證。（2）實(shí)驗(yàn)完成后，提交電子檔教師驗(yàn)收程序，并提交填寫(xiě)好的實(shí)驗(yàn)報(bào)告。[測(cè)試數(shù)據(jù)]由學(xué)生依據(jù)軟件工程的測(cè)試技術(shù)自己確定。注意測(cè)試邊界數(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("請(qǐng)輸入數(shù)據(jù)長(zhǎng)度：");