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

《數(shù)據(jù)結(jié)構(gòu)》實驗報告課程名稱：數(shù)據(jù)結(jié)構(gòu)實驗室名稱：機房開課學(xué)院：信息技術(shù)學(xué)院專業(yè)班級：計算機科學(xué)與技術(shù)B22-2組號：組長學(xué)號姓名：組員學(xué)號姓名：組員學(xué)號姓名：指導(dǎo)老師：5019.12

預(yù)備實驗：C語言知識回顧實驗日期：年月日實驗?zāi)康募耙?.熟練掌握C語言中數(shù)組、函數(shù)、結(jié)構(gòu)體、文件的使用；2.熟練掌握數(shù)組（包括結(jié)構(gòu)體數(shù)組）的排序，遍歷等基本算法的實現(xiàn)；實驗內(nèi)容任務(wù)一1．題目要求輸入n個整數(shù)，輸出其中與平均值最接近的元素的值及下標。要求定義下面功能函數(shù)，并在main函數(shù)中調(diào)用這些函數(shù)實現(xiàn)題目要求的功能：1.doublegetAvg(inta[],intn)功能：求數(shù)組a中n個數(shù)的平均值。2.intgetIndex(inta[],intn,doublex)功能：獲取與x的值最接近的數(shù)組元素的下標。2．源程序清單（含必要的注釋）3．程序運行時的輸入輸出結(jié)果任務(wù)二1．題目要求若有一文本文件records.txt中已存儲學(xué)生身高表，每個學(xué)生信息包括學(xué)號和身高兩個數(shù)據(jù)項，編程要求從文件獲取學(xué)生身高表后，按身高從低到高的順序排序后在屏幕上打印學(xué)生身高表。要求定義下面功能函數(shù)，并在main函數(shù)中調(diào)用這些函數(shù)實現(xiàn)題目要求的功能：1.intgetRecs(STUDENTSs[]);功能：從文件records.txt中讀數(shù)據(jù)到結(jié)構(gòu)體數(shù)組s中，并返回人數(shù)n。2.voidsort(STUDENTSs[],intn);功能：對結(jié)構(gòu)體數(shù)組s按身高從低到高排序。2．學(xué)生信息類型定義及說明typedefstruct{intxh;/*學(xué)號*/floatsg;/*身高*/}STUDENTS;3．源程序清單（含必要的注釋）4．原始數(shù)據(jù)文件records.txt內(nèi)容及程序運行結(jié)果實驗總結(jié)分析程序調(diào)試中出現(xiàn)的問題及解決方法，心得體會等實驗一順序表操作實現(xiàn)實驗日期：年月日實驗?zāi)康募耙?.熟練掌握線性表的基本操作在順序存儲上的實現(xiàn)；2.以線性表的各種操作（建立、插入、刪除、遍歷等）的實現(xiàn)為重點；3.掌握線性表的順序存儲結(jié)構(gòu)的定義和基本操作的實現(xiàn)；4.通過本實驗加深對C語言的使用（特別是函數(shù)調(diào)用的參數(shù)傳遞、指針類型的應(yīng)用）。實驗內(nèi)容已知程序文件seqlist.cpp已給出學(xué)生身高信息順序表的類型定義和基本運算函數(shù)定義。（1）順序表類型定義typedefstruct{intxh;/*學(xué)號*/floatsg;/*身高*/intsex;/*性別，0為男生，1為女生*/}datatype;typedefstruct{datatypedata[MAX];/*存放順序表元素的數(shù)組*/intlast;/*表示data中實際存放元素個數(shù)*/}Seqlist;（2）基本運算函數(shù)原型voidinitList(Seqlist*lp);/*置一個空表*/voidcreateList(Seqlist*lp);/*建一個學(xué)生順序表*/voidsort_xh(Seqlist*lp);/*按學(xué)號排序*/voidpntList(Seqlist*lp);/*輸出學(xué)生表*/voidsave(Seqlist*lp,charstrname[]);/*保存學(xué)生順序表到指定文件*/任務(wù)一閱讀程序文件seqlist.cpp，其代碼如下所示，理解順序表類型Seqlist和基本運算函數(shù)后回答下列問題。/*seqlist.cpp程序文件代碼*/#include<stdio.h>#include<stdlib.h>#defineMAX50typedefstruct{intxh;/*學(xué)號*/floatsg;/*身高*/intsex;/*性別，0為男生，1為女生*/}datatype;typedefstruct{datatypedata[MAX];/*存放順序表元素的數(shù)組*/intlast;/*表示data中實際存放元素個數(shù)*/}Seqlist;voidinitList(Seqlist*lp);/*置一個空表*/voidcreateList(Seqlist*lp);/*建一個學(xué)生順序表*/voidsort_xh(Seqlist*lp);/*按學(xué)號排序*/voidpntList(Seqlist*lp);/*輸出學(xué)生表*/voidsave(Seqlist*lp,charstrname[]);/*保存學(xué)生順序表到指定文件*//*置一個空表*/voidinitList(Seqlist*lp){lp->last=0;}/*建一個學(xué)生順序表*/voidcreateList(Seqlist*lp){ FILE*fp; intxh,sex; floatsg; if((fp=fopen("records.txt","r"))==NULL) { printf("cannotopenreadfile!\n"); exit(1);/*返回OS,該函數(shù)定義在stdlib.h中*/ } while(!feof(fp)) { fscanf(fp,"%d%f%d",&xh,&sg,&sex); lp->data[lp->last].xh=xh; lp->data[lp->last].sg=sg; lp->data[lp->last].sex=sex; lp->last++; } fclose(fp);}/*按學(xué)號排升序*/voidsort_xh(Seqlist*lp){ inti,j,k; datatypest; for(i=0;i<lp->last-1;i++) {k=i; for(j=i+1;j<lp->last;j++) if(lp->data[j].xh<lp->data[k].xh) k=j; if(k!=i) {st=lp->data[k]; lp->data[k]=lp->data[i]; lp->data[i]=st;} }}/*輸出學(xué)生順序表*/voidpntList(Seqlist*lp){inti;for(i=0;i<lp->last;i++) printf("%2d:%.2f%d\n",lp->data[i].xh,lp->data[i].sg,lp->data[i].sex);}/*保存學(xué)生順序表到指定文件*/voidsave(Seqlist*lp,charstrname[]){ FILE*fp; inti; if((fp=fopen(strname,"w"))==NULL) { printf("cannotopenwritefile!\n"); exit(1);/*返回OS*/ } for(i=0;i<lp->last;i++) { fprintf(fp,"%2d%5.2f%2d\n",lp->data[i].xh,lp->data[i].sg,lp->data[i].sex); } fclose(fp);}

請回答下列問題：（1）由順序表類型定義可知，該順序表類型名為，其中存放的元素為學(xué)生信息，學(xué)生信息定義的類型名為，包含、、三個成員（寫出成員變量名），學(xué)生信息存儲于數(shù)組，順序表的表長變量為。（2）seqlist.cpp程序編譯連接通過后能執(zhí)行嗎？為什么？其代碼的整體結(jié)構(gòu)有哪4個組成部分？（3）回答下列問題a）initList函數(shù)的形參變量lp存放什么值？順序表置為空表的實質(zhì)是做什么操作？b）在建立順序表的createList函數(shù)中，順序表的數(shù)據(jù)元素來自何處？已提供的數(shù)據(jù)如下，建完的順序表表長是多少？c）sort_xh排序函數(shù)采用了什么排序方法？請列舉5個學(xué)號值寫出每趟（5個需排4趟）排序后的結(jié)果d）save函數(shù)中的形參數(shù)組strname中存放什么？

任務(wù)二1．題目要求創(chuàng)建一個新的程序文件sy1.c，請調(diào)用seqlist.cpp提供的功能函數(shù)（以#include"seqlist.cpp"方式導(dǎo)入函數(shù)庫）及自定義的函數(shù)完成以下操作：創(chuàng)建一個包含學(xué)生學(xué)號、身高、性別的學(xué)生身高信息表并輸出到屏幕，學(xué)生信息從records.txt文件讀??；從鍵盤輸入一個身高值，統(tǒng)計高于該身高的學(xué)生個數(shù)并輸出在屏幕；對已建立的學(xué)生身高信息表進行倒置，結(jié)果輸出在屏幕；對已建立的學(xué)生身高信息表按學(xué)號從小到大排序，并把結(jié)果寫入到數(shù)據(jù)文件中（result.txt）；從鍵盤輸入一位學(xué)生的相關(guān)信息插入到已排序的學(xué)生身高信息表中，仍然保持學(xué)號的有序性；在程序文件sy1.c中需再定義以下三個功能函數(shù)：（1）intcount(Seqlist*lp,floaty)功能：統(tǒng)計學(xué)生表中身高值高于y的學(xué)生數(shù)并返回（2）voidreverse(Seqlist*lp)功能：對lp指向的順序表進行倒置操作（3）voidinsertX(Seqlist*lp,datatypex)功能：在學(xué)號從小到大排序的學(xué)生表中插入值為x的學(xué)生仍保持學(xué)號的有序性2．請根據(jù)題目功能要求及程序中的注釋填空完整sy1.c代碼/*sy1.c程序文件代碼*/#include"seqlist.cpp"http://導(dǎo)入自定義類型及函數(shù)所在的文件seqlist.cpp，該文件與sy1.c存于同一目錄中voidinsertX(Seqlist*lp,datatypex);voidreverse(Seqlist*lp);intcount(Seqlist*lp,floaty);intmain(){Seqliststu;//定義stu為學(xué)生順序表變量datatypex;//x為存儲一個學(xué)生信息的變量intc;charfilename[50];//filename為存儲文件名的數(shù)組/*創(chuàng)建一個包含學(xué)生學(xué)號、身高、性別的學(xué)生身高信息表stu并輸出到屏幕，學(xué)生信息從records.txt文件讀取*///調(diào)用函數(shù)initList初始化順序表stu//調(diào)用函數(shù)createList創(chuàng)建學(xué)生表stuprintf("\nsourcelist:\n");//調(diào)用函數(shù)pntList打印學(xué)生表stugetchar();//在執(zhí)行程序能起到暫定的作用，按任意鍵繼續(xù)/*從鍵盤輸入一個身高值，統(tǒng)計高于該身高的學(xué)生個數(shù)并輸出在屏幕*/printf("\nInputastudentheight:\n");scanf("%f",&x.sg);//統(tǒng)計身高高于指定值的學(xué)生數(shù)存于c中printf("\nThehigherheight:%d\n",c);getchar();/*對已建立的學(xué)生身高信息表進行倒置，結(jié)果輸出在屏幕；*///倒置順序表printf("\nlistafterreverse:\n");pntList(&stu); getchar();/*對已建立的學(xué)生身高信息表按學(xué)號從小到大排序，并把結(jié)果寫入到數(shù)據(jù)文件中（result.txt）*///調(diào)用函數(shù)sort_xh對學(xué)生表stu按學(xué)號從小到大排序printf("\nInputnewfilenametosave:");//鍵盤輸入文件名字符串存于filename數(shù)組中//調(diào)用函數(shù)save把排序后的順序表stu存于文件中，文件名在filename數(shù)組中/*從鍵盤輸入一位學(xué)生的相關(guān)信息插入到已排序的學(xué)生身高信息表中后仍然保持學(xué)號的有序性；*/printf("\nInputastudentinformation:\n");scanf("%d%f%d",&x.xh,&x.sg,&x.sex);//插入printf("\nlistafterinsert:\n");pntList(&stu); return0;}/*統(tǒng)計學(xué)生表中身高值高于y的學(xué)生數(shù)并返回*/intcount(Seqlist*lp,floaty){inti,ct=0;//遍歷順序表統(tǒng)計身高值高于y的學(xué)生數(shù)到ct變量并返回值}/*對lp指向的順序表進行倒置操作*/voidreverse(Seqlist*lp){inti,j;datatypetemp;//通過前后數(shù)據(jù)元素交換的方式實現(xiàn)倒置}/*在學(xué)號從小到大排序的學(xué)生表中插入值為x的學(xué)生仍保持學(xué)號的有序性*/voidinsertX(Seqlist*lp,datatypex){inti;if(lp->last>=MAX){printf("listisfull");return;}//在學(xué)號升序的順序表中找插入位置后，插入x并使表長增1}實驗總結(jié)分析（本程序的重點與難點，調(diào)試中出現(xiàn)的問題及解決方法等）實驗二鏈表操作實現(xiàn)實驗日期：年月日實驗?zāi)康募耙?.熟練掌握線性表的基本操作在鏈式存儲上的實現(xiàn)；2.以線性表的各種操作（建立、插入、刪除、遍歷等）的實現(xiàn)為重點；3.掌握線性表的鏈式存儲結(jié)構(gòu)的定義和基本操作的實現(xiàn)；4.通過本實驗加深對C語言的使用（特別是函數(shù)的參數(shù)調(diào)用、指針類型的應(yīng)用）。實驗內(nèi)容已知程序文件linklist.cpp已給出學(xué)生身高信息鏈表的類型定義和基本運算函數(shù)定義。（1）鏈表類型定義typedefstruct{intxh;/*學(xué)號*/floatsg;/*身高*/intsex;/*性別，0為男生，1為女生*/}datatype;typedefstructnode{datatypedata;/*數(shù)據(jù)域*/structnode*next;/*指針域*/}LinkNode;（2）帶頭結(jié)點的單鏈表的基本運算函數(shù)原型LinkNode*initList();/*置一個空表（帶頭結(jié)點）*/voidcreateList_1(LinkNode*head);/*創(chuàng)建單鏈表方法1*/voidcreateList_2(LinkNode*head);/*創(chuàng)建單鏈表方法2*/voidsort_xh(LinkNode*head);/*單鏈表排序*/voidreverse(LinkNode*head);/*對單鏈表進行結(jié)點倒置*/voidpntList(LinkNode*head);/*打印單鏈表*/voidsave(LinkNode*head,charstrname[]);/*保存單鏈表到文件*/任務(wù)一閱讀程序文件linklist.cpp，其代碼如下所示，理解LinkNode類型和基本運算函數(shù)后回答下列問題。#include<stdio.h>#include<stdlib.h>/*單鏈表結(jié)點類型*/typedefstruct{intxh;/*學(xué)號*/floatsg;/*身高*/intsex;/*性別，0為男生，1為女生*/}datatype;typedefstructnode{datatypedata;/*數(shù)據(jù)域*/structnode*next;/*指針域*/}LinkNode;/*帶表頭的單鏈表的基本運算函數(shù)*/LinkNode*initList();/*置一個空表（帶頭結(jié)點）*/voidcreateList_1(LinkNode*head);/*創(chuàng)建單鏈表*/voidcreateList_2(LinkNode*head);/*創(chuàng)建單鏈表*/voidsort_xh(LinkNode*head);/*單鏈表排序*/voidreverse(LinkNode*head);/*單鏈表倒置*/voidpntList(LinkNode*head);/*打印單鏈表*/voidsave(LinkNode*head,charstrname[]);/*保存單鏈表到文件*//*置一個空表*/LinkNode*initList(){LinkNode*p;p=(LinkNode*)malloc(sizeof(LinkNode));p->next=NULL;returnp;}/*創(chuàng)建單鏈表方法1*/voidcreateList_1(LinkNode*head){FILE*fp; datatypestu; LinkNode*p; if((fp=fopen("records.txt","r"))==NULL) {printf("cannotopenreadfile!"); exit(1); } while(!feof(fp)) { fscanf(fp,"%d%f%d",&stu.xh,&stu.sg,&stu.sex); p=(LinkNode*)malloc(sizeof(LinkNode)); p->data=stu; p->next=head->next; head->next=p; } fclose(fp);}/*創(chuàng)建單鏈表方法2*/voidcreateList_2(LinkNode*head){ FILE*fp; datatypestu; LinkNode*p,*rear; if((fp=fopen("records.txt","r"))==NULL) {printf("cannotopenreadfile!"); exit(1); } rear=head; while(!feof(fp)) { fscanf(fp,"%d%f%d",&stu.xh,&stu.sg,&stu.sex); p=(LinkNode*)malloc(sizeof(LinkNode)); p->data=stu; p->next=NULL; rear->next=p; rear=p; } fclose(fp);}/*單鏈表排序*/voidsort_xh(LinkNode*head){LinkNode*q,*p,*u;p=head->next;head->next=NULL;/*利用原表頭結(jié)點建新的空表*/while(p){q=p;/*q為被插入的結(jié)點*/p=p->next;/*用p記錄后繼結(jié)點*//*遍歷新鏈表查找插入位置*/u=head;while(u->next!=NULL)/*查找插入位置*/{if(u->next->data.xh>q->data.xh)break;u=u->next; }/*插入在u結(jié)點的后面*/q->next=u->next;u->next=q;}}/*單鏈表倒置*/voidreverse(LinkNode*head){LinkNode*p,*r;p=head->next;head->next=NULL;while(p){r=p;p=p->next;/*r指向結(jié)點頭插到鏈表*/r->next=head->next;head->next=r;}}/*輸出單鏈表*/voidpntList(LinkNode*head){ LinkNode*p; p=head->next; while(p!=NULL) {printf("%2d:%.2f%d\n",p->data.xh,p->data.sg,p->data.sex); p=p->next; }}/*保存單鏈表到文件*/voidsave(LinkNode*head,charstrname[]){ FILE*fp; LinkNode*p; if((fp=fopen(strname,"w"))==NULL) {printf("cannotopenwritefile!"); exit(1); } p=head->next; while(p!=NULL) {fprintf(fp,"%2d%5.2f%2d\n",p->data.xh,p->data.sg,p->data.sex); p=p->next; } fclose(fp);}請回答下列問題：（1）由單鏈表結(jié)點類型定義可知，該鏈表結(jié)點類型名為，向系統(tǒng)申請一個學(xué)生結(jié)點空間并把起始地址存于結(jié)點指針變量s中的語句是：。（2）回答問題：a）已知：LinkNode*head;畫出執(zhí)行head=initList();語句后的鏈表結(jié)構(gòu)示意圖b）在a)操作的基礎(chǔ)上，根據(jù)下面records.txt中的數(shù)據(jù)，畫出執(zhí)行createList_1(head);語句后的鏈表結(jié)構(gòu)示意圖（可以只畫學(xué)號成員）c）在b)操作的基礎(chǔ)上，畫出執(zhí)行sort_xh(head);語句后的鏈表結(jié)構(gòu)示意圖d）在c)操作的基礎(chǔ)上，畫出執(zhí)行reverse(head);語句后的鏈表結(jié)構(gòu)示意圖（3）寫出下列操作對應(yīng)的執(zhí)行語句（以下的指針變量的類型都是上述定義的結(jié)點指針類型）a）把一個s指針指向的結(jié)點頭插到以h為頭指針帶表頭結(jié)點的單鏈表中的語句b）把一個s指針指向的結(jié)點頭插到以h為頭指針不帶表頭結(jié)點的單鏈表中的語句c）在單鏈表中刪除r所指結(jié)點的后繼結(jié)點（假設(shè)存在）的語句d）分別寫出循環(huán)及非循環(huán)單鏈表中判斷r所指結(jié)點是尾結(jié)點（假設(shè)存在）的條件任務(wù)二1．題目要求創(chuàng)建一個新的程序文件sy2.c，請調(diào)用linklist.cpp提供的功能函數(shù)（以#include"linklist.cpp"方式導(dǎo)入函數(shù)庫）及自定義的函數(shù)完成以下操作：從數(shù)據(jù)文件records.txt中讀取學(xué)生信息，建立與源數(shù)據(jù)同序的學(xué)生鏈表并打印在屏幕上；統(tǒng)計學(xué)生鏈表中身高達標人數(shù)（男女生的身高達標值由鍵盤輸入），并打印結(jié)果；對學(xué)生鏈表按學(xué)號從小到大排序；從鍵盤輸入一位學(xué)生的相關(guān)信息插入到已排序的學(xué)生身高鏈表中后仍然保持學(xué)號的有序性；對上述操作后的學(xué)生鏈表進行倒置，結(jié)果輸出到數(shù)據(jù)文件result.txt中；刪除鏈表中身高低于指定值的所有學(xué)生結(jié)點，并打印刪除后的鏈表；在程序文件sy2.c中需再定義以下三個功能函數(shù)：（1）intcount(LinkNode*head,floatsg_fm,floatsg_m)功能：已知女生達標身高為sg_fm，男生達標身高為sg_m，統(tǒng)計head為頭指針的學(xué)生鏈表中身高達標人數(shù)并返回；（2）voidinsertX(LinkNode*head,datatypex)功能：在學(xué)號從小到大排序的學(xué)生鏈表中插入值為x的學(xué)生，仍保持學(xué)號的有序性（3）intdelList(LinkNode*head,floatsg)功能：刪除head為頭指針的學(xué)生鏈表中身高低于指定身高的所有學(xué)生結(jié)點，刪除成功返回1，否則返回0；2．請根據(jù)題目功能要求或程序中的注釋完整sy2.c代碼#include"linklist.cpp"intcount(LinkNode*head,floatsg_fm,floatsg_m);/*統(tǒng)計head為頭指針的學(xué)生鏈表中身高達標人數(shù)并返回*/voidinsertX(LinkNode*head,datatypex);/*在學(xué)號從小到大排序的學(xué)生鏈表中插入值為x的學(xué)生仍保持學(xué)號的有序性*/intdelList(LinkNode*head,floatsg);/*刪除head為頭指針的學(xué)生鏈表中身高低于指定身高的所有學(xué)生結(jié)點，刪除成功返回1，否則返回0*/voidmain(){LinkNode*head;intc,flag;floatsg,sg_fm,sg_m;datatypex;/*建立與源數(shù)據(jù)文件同序的學(xué)生鏈表并輸出；*/head=;/*建空鏈表*/;/*調(diào)用建鏈表函數(shù)建立所需鏈表*/printf("\n與數(shù)據(jù)文件同序的學(xué)生鏈表：\n");;/*調(diào)用函數(shù)打印輸出鏈表中信息*/getchar();/*統(tǒng)計學(xué)生鏈表中身高達標人數(shù)（男女生的身高達標值由鍵盤輸入）并打印結(jié)果；*/printf("\n輸入達標的女生、男生身高值：");scanf("%f%f",&sg_fm,&sg_m);c=count();printf("\n達標學(xué)生人數(shù)為：%d",c);getchar();/*對學(xué)生鏈表按學(xué)號進行排序*/sort_xh(head);/*在學(xué)生鏈表中插入指定的學(xué)生元素后使鏈表仍按學(xué)號有序*/x.xh=3;x.sg=1.67;x.sex=0;insertX();printf("\nnewlistafterinsert:\n");pntList(head);getchar();/*對學(xué)生鏈表進行倒置，結(jié)果輸出到文件result.txt中；*/reverse(head);save(head,"result.txt");getchar();/*刪除鏈表中身高低于指定值的所有學(xué)生結(jié)點;*/sg=1.67;flag=;if(flag)printf("\ndeletesucceed!\n");elseprintf("\ndeletefailed\n");printf("\nnewlistafterdelete:\n");pntList(head);getchar();}//統(tǒng)計學(xué)生鏈表中身高達標人數(shù)并返回(sg_fm女生身高達標值、sg_m男生身高達標值)intcount(LinkNode*head,floatsg_fm,floatsg_m){intn=0;LinkNode*p;}//刪除學(xué)生鏈表中身高低于指定身高(存于sg中)的所有學(xué)生結(jié)點，刪除成功返回1，否則返回0intdelList(LinkNode*head,floatsg){LinkNode*p,*q;intflag=0;q=head;p=head->next;while(p!=NULL){if(p->data.sg<sg){/*刪除p所指結(jié)點*/flag=1;}else{}}returnflag;/*刪除成功返回1,否則返回0*/}//在學(xué)號從小到大排序的學(xué)生鏈表中插入值為x的學(xué)生仍保持學(xué)號的有序性voidinsertX(LinkNode*head,datatypex){}實驗總結(jié)分析（本程序的重點與難點，調(diào)試中出現(xiàn)的問題及解決方法等）實驗三二叉樹操作實現(xiàn)實驗日期：年月日實驗?zāi)康募耙?.熟練掌握樹的基本概念、二叉樹的基本操作及在鏈式存儲結(jié)構(gòu)上的實現(xiàn)；2.重點掌握二叉樹的創(chuàng)建、遍歷及求深度等算法；3.掌握運用遞歸方式描述算法及編寫遞歸C程序的方法，提高算法分析和程序設(shè)計能力。4.掌握以順序棧為輔助存儲，對二叉樹進行非遞歸中序遍歷的算法。實驗內(nèi)容鍵盤輸入一個字符串，利用二叉樹前序遍歷的結(jié)果建成一棵二叉樹，并用三種遍歷方法打印，比較是否與自己預(yù)先想象的相一致。再求樹的深度、1度結(jié)點數(shù)、2度節(jié)點數(shù)，交換二叉樹的左右子樹并輸出交換后的中序遍歷結(jié)果驗證交換的正確性。找到二叉樹中序遍歷最后一個結(jié)點并輸出結(jié)點值。利用順序棧為輔助存儲對二叉樹進行非遞歸中序遍歷（選做）。利用順序隊列為輔助存儲對二叉樹進行層序遍歷（選做）。二叉樹結(jié)點類型定義：typedefchardatatype;typedefstructtnode{datatypedata;structtnode*left,*right;}BiTNode,*BiTree;順序棧的類型定義：typedefstruct{BiTreedata[MAX];inttop;}SeqStack,*SeqStackptr;任務(wù)一：閱讀自定義頭文件seqStack_BTree.h，包含順序棧的數(shù)據(jù)類型定義及順序?；静僮骱瘮?shù)，定義的基本操作如下：（1）voidError(char*s);/*自定義錯誤處理函數(shù)*/（2）voidInitStack(SeqStackptrsp);/*初始化?！每諚?/（3）intEmptyStack(SeqStackptrsp);/*判棧空*/（4）intFullStack(SeqStackptrsp);/*判棧滿*/（5）voidPush(SeqStackptrsp,BiTreex);/*進棧(元素壓入棧頂)*/（6）BiTreePop(SeqStackptrsp);/*出棧(元素從棧頂彈出)*/（7）BiTreeGetTop(SeqStackptrsp);/*讀棧頂元素(不出棧)*/（8）intCount(SeqStackptrsp);/*計算棧中元素個數(shù)*/請回答下列問題（1）棧是限定在表的一端進行插入或刪除操作的線性表，其操作原則是。（2）設(shè)數(shù)組S[100]存儲一個順序棧的元素，變量top指示下一個入棧元素在數(shù)組中的下標位置，棧為空的條件是，棧為滿的條件是。（3）在n個結(jié)點二叉樹的二叉鏈表存儲中，其指針域的總數(shù)為個，其中個用于鏈接孩子結(jié)點，個空閑著。（4）在二叉鏈表存儲中，數(shù)據(jù)域為data，左右子樹的指針分別為left和right，則判斷：指針p所指結(jié)點為0度結(jié)點的條件是；指針p所指結(jié)點為1度結(jié)點的條件是；指針p所指結(jié)點為2度結(jié)點的條件是。（5）T為二叉樹的根的地址，該樹是空二叉樹滿足條件：。任務(wù)二1．題目要求創(chuàng)建一個程序文件sy3.c，自定義相應(yīng)函數(shù)完成以下操作：BiTNode*createTree();/*以前序遍歷的順序建立二叉樹*/voidpreOrder(BiTNode*T);/*前序遍歷*/voidinOrder(BiTNode*T);/*中序遍歷*/voidpostOrder(BiTNode*T);/*后序遍歷*/intdeep(BiTNode*T);/*求二叉樹深度*/intleaf(BiTNode*T);/*求葉子結(jié)點數(shù)*/intoneChild(BiTNode*T);/*求1度結(jié)點數(shù)*/inttwoChild(BiTNode*T);/*求2度結(jié)點數(shù)*/voidexchange(BiTNode*T);/*二叉樹左右子樹交換*/BiTNode*inOrderLastNode(BiTNode*T);/*二叉樹中序遍歷最后一個結(jié)點*/voidinOrderNonRecursive(BiTNode*T);/*中序遍歷的非遞歸算法*/2．請根據(jù)題目功能要求或程序中的注釋完成sy3.c代碼#include"bitree2.cpp"#include"seqStack_BTree.h"BiTNode*createTree();/*以前序遍歷的順序建立二叉樹*/voidpreOrder(BiTNode*T);/*前序遍歷*/voidinOrder(BiTNode*T);/*中序遍歷*/voidpostOrder(BiTNode*T);/*后序遍歷*/intdeep(BiTNode*T);/*求二叉樹深度*/intleaf(BiTNode*T);/*求葉子結(jié)點數(shù)*/intoneChild(BiTNode*T);/*求1度結(jié)點數(shù)*/inttwoChild(BiTNode*T);/*求2度結(jié)點數(shù)*/voidexchange(BiTNode*T);/*二叉樹左右子樹交換*/BiTNode*inOrderLastNode(BiTNode*T);/*找二叉樹中序遍歷最后一個結(jié)點*/voidinOrderNonRecursive(BiTNode*T);/*中序遍歷的非遞歸算法*/intmain(){ BiTNode*root; /*利用二叉樹前序遍歷的結(jié)果建成一棵二叉樹*/ show_tree(root);/*二叉樹的顯示，不要求掌握*/printf("\n先序遍歷序列：");printf("\n中序遍歷序列："); printf("\n后序遍歷序列："); printf("\n樹的深度=%d",); /*求樹的深度*/ printf("\n葉子結(jié)點數(shù)=%d",); /*求葉子結(jié)點數(shù)*/ printf("\n1度結(jié)點數(shù)=%d",); /*求1度結(jié)點數(shù)*/ printf("\n2度結(jié)點數(shù)=%d",); /*求2度結(jié)點數(shù)*/ printf("\n交換左右子樹后的中序遍歷結(jié)果："); /*交換二叉樹的左右子樹*/ inOrder(root);/*輸出交換后的中序遍歷結(jié)果*/ /*找到二叉樹中序遍歷最后一個結(jié)點并輸出結(jié)點值*/printf("\n中序遍歷最后一個結(jié)點值：%c",); printf("\n中序遍歷非遞歸："); /*非遞歸中序遍歷二叉樹*/ return0;}/*以前序遍歷的順序建立二叉樹*/BiTNode*createTree(){ charch; BiTNode*T; if((ch=getchar())=='#') returnNULL; T=(BiTNode*)malloc(sizeof(BiTNode));/*生成二叉樹的根結(jié)點*/ T->data=ch; T->left=createTree();/*遞歸實現(xiàn)左子樹的建立*/ T->right=createTree();/*遞歸實現(xiàn)右子樹的建立*/ returnT;}/*前序遍歷*/voidpreOrder(BiTNode*T){ if(T) { }}/*中序遍歷*/voidinOrder(BiTNode*T){ if(T) { inOrder(T->left); printf("%c",T->data); inOrder(T->right); }}/*后序遍歷*/voidpostOrder(BiTNode*T){ if(T) { }}/*求二叉樹深度*/intdeep(BiTNode*T){intlh,rh;if(T==NULL)return0;lh=rh=}/*求葉子結(jié)點數(shù)*/intleaf(BiTNode*T){}/*求1度結(jié)點數(shù)*/intoneChild(BiTNode*T){}/*求2度結(jié)點數(shù)*/inttwoChild(BiTNode*T){}/*二叉樹左右子樹交換*/voidexchange(BiTNode*T){BiTNode*tmp;if(T){}}/*找二叉樹中序遍歷最后一個結(jié)點*/BiTNode*inOrderLastNode(BiTNode*T){BiTNode*p=T;if(p){while(p->right)}}/*中序遍歷的非遞歸算法*/voidinOrderNonRecursive(BiTNode*T){SeqStackss;BiTNode*bt=T;InitStack(&ss);/*創(chuàng)建并初始化堆棧S*/while(bt||!EmptyStack(&ss)){while(bt)/*一直向左并將沿途結(jié)點壓入堆棧*/{}if(!EmptyStack(&ss)){/*結(jié)點彈出堆棧*/printf("%c",bt->data);/*（訪問）打印結(jié)點*//*轉(zhuǎn)向右子樹*/}}}3．程序執(zhí)行時屏幕上的輸入內(nèi)容實驗總結(jié)分析（本程序的重點與難點，調(diào)試中出現(xiàn)的問題及解決方法等）實驗四圖操作實現(xiàn)實驗日期：年月日實驗?zāi)康募耙?.熟練掌握圖的鄰接矩陣和鄰接表的存儲方式；2.實現(xiàn)圖的一些基本運算，特別是深度優(yōu)先遍歷和廣度優(yōu)先遍歷；實驗內(nèi)容用鄰接矩陣法建一個無向連通圖（頂點信息為順序字母A，B，C，D...，而非鍵盤輸入），分別用dfs（深度優(yōu)先搜索）和bfs（廣度優(yōu)先搜索）遍歷，輸出圖中頂點信息并驗證。鄰接矩陣圖類型定義：#defineMAX40typedefcharvexType;/*頂點類型*/typedefstruct{vexTypevex[MAX];intarcs[MAX][MAX];intvn,en;}MGraph;訪問標記數(shù)組定義：intvisited[MAX];/*值為0時對應(yīng)頂點未被訪問，值為1時對應(yīng)頂點已被訪問*/順序存儲的循環(huán)隊列類型定義：typedefintdatatype;/*隊列元素為圖的頂點下標,int型*/typedefstructnode{datatypedata[MAX];intfront,rear;}SeqQueue;/*順序存儲的循環(huán)隊列類型*/任務(wù)1．閱讀自定義函數(shù)庫文件Queue_graph.h，其中為隊列的相關(guān)操作。2．創(chuàng)建一個程序文件sy4.c，自定義相應(yīng)函數(shù)完成以下操作：（1）voidcreateGraph(MGraph*g)/*建鄰接矩陣存儲的無向圖*/（2）voidvisit(MGraph*g,intv)/*訪問v號頂點*/（3）voiddfs(MGraph*g,intv)/*鄰接矩陣存儲的圖的深度優(yōu)先搜索*/（4）voidbfs(MGraph*g,intv)/*鄰接矩陣存儲的圖的廣度優(yōu)先搜索*/3．回答下列問題（1）現(xiàn)有定義：MGraph*g，并且g指針指向的無向圖已創(chuàng)建完成，請寫出該圖遍歷前需初始化visited數(shù)組的C程序語句。（2）定義函數(shù)intcount(MGraph*g)統(tǒng)計非連通圖的連通分量個數(shù)。（說明：借助遍歷算法實現(xiàn)）4．sy4.c源程序清單（含必要的注釋）#include"Queue_graph.h"typedefcharvexType;/*頂點類型*/typedefstruct{vexTypevex[MAX];intarcs[MAX][MAX];intvn,en;}MGraph;/*鄰接矩陣圖類型*/intvisited[MAX];/*訪問標記數(shù)組*/voidcreateGraph(MGraph*g);/*建鄰接矩陣存儲的無向圖*/voidvisit(MGraph*g,intv);/*訪問v號頂點*/voiddfs(MGraph*g,intv);/*鄰接矩陣存儲的圖的深度優(yōu)先搜索*/voidbfs(MGraph*g,intv);/*鄰接矩陣存儲的圖的廣度優(yōu)先搜索*/intmain(){MGraphmg;inti,j,start;/*創(chuàng)建鄰接矩陣存儲的無向圖*/for(i=0;i<mg.vn;i++){for(j=0;j<mg.vn;j++)/*輸出鄰接矩陣*/printf("\n");}printf("\ninputstartpointer:\n");/*輸入遍歷的起始頂點的下標*/for(i=0;i<mg.vn;i++)visited[i]=0;printf("\ntranversalindepthfirstsearchalgorithm");(&mg,start);/*填空，深度優(yōu)先搜索*/getchar();for(i=0;i<mg.vn;i++)visited[i]=0;printf("\ntranversalinbreathfirstserchalgorithm");(&mg,start);/*填空，廣度優(yōu)先搜索*/getchar(); return0;}voidcreateGraph(MGraph*g)/*建鄰接矩陣存儲的無向圖*/{ inti,j,v,e; FILE*fp; fp=fopen("graph.txt","r"); if(fp==NULL) { printf("errorfile\n"); exit(1); }fscanf(fp,);/*填空，讀入頂點的個數(shù)和邊的個數(shù)*/for(v=0;v<g->vn;v++) /*頂點信息為順序字母A，B，C，D...*/g->vex[v]='A'+v;/*填空，鄰接矩陣賦初值*/for(e=0;e<g->en;e++){/*填空，讀入圖的邊*/}}voidvisit(MGraph*g,intv)/*訪問v號頂點*/{ printf("\nv=%dvertex:%c",v,g->vex[v]);}voiddfs(MGraph*g,intv)/*鄰接矩陣存儲的圖的深度優(yōu)先搜索*/{inti;visit(g,v);visited[v]=1;}/*enddfsfunction*/voidbfs(MGraph*g,intv)/*鄰接矩陣存儲的圖的廣度優(yōu)先搜索*/{SeqQueuesq;inti,j;InitQueue(&sq);EnQueue(&sq,v);visited[v]=1;while(!Empty(&sq)){}}/*endbfsfunction*/實驗總結(jié)分析（本程序的重點與難點，調(diào)試中出現(xiàn)的問題及解決方法等）實驗五順序表的排序及查找實驗日期：年月日實驗?zāi)康募耙?.熟練掌握各種排序方法及不同查找運算的實現(xiàn)；2.重點用C程序?qū)樞虮聿捎弥苯硬迦?、冒泡法和直接選擇法進行排序；4.重點掌握二分查找算法實現(xiàn)。實驗內(nèi)容建立一存有若干學(xué)生信息（學(xué)號、姓名、一門課成績）的順序表，學(xué)號為關(guān)鍵字，分別按學(xué)號升序、姓名升序、成績降序要求對學(xué)生表進行排序并輸出各排序后的學(xué)生信息，并能輸入指定的學(xué)號查找該學(xué)生，若找到輸出該生的學(xué)號、姓名及成績信息，否則輸出“Nofound”。任務(wù)程序文件sy5.c中自定義函數(shù)如下：（1）voidCreateTable(Tabler)創(chuàng)建學(xué)生信息順序表，記錄從數(shù)組的1號下標開始存放；（2）voidInsertSort(Tabler)直接插入法對學(xué)生表按學(xué)號排成升序；（3）voidBubbleSort(Tabler)冒泡法對學(xué)生表按姓名排成升序；（4）voidSelectSort(Tabler)簡單選擇法對學(xué)生表按成績排降序；（5）voidOutput(Tabler)輸出順序表中的記錄；（6）intBinary(Tabler,intk)給定一個學(xué)號以二分法查找已建順序表中的學(xué)生記錄，找到返回該記錄下標，否則返回0。1．回答下列問題（1）以二分查找法（或稱折半查找法）查找一個線性表時，此線性表必須是___________存儲的________表。假設(shè)對于一個有序序列0,1,2,3,5,7,8,9采用二分查找法查找元素，如查找元素8，則依次比較的元素是。（2）n個記錄的順序表中，若采用直接插入排序時有可能最后一趟之前所有元素都不是最終排序位置，當待排記錄事先是時最快，比較記錄次數(shù)為，移動記錄次數(shù)為，平均時間復(fù)雜度是；若采用冒泡排序時，記錄的比較次數(shù)與記錄初始狀態(tài)無關(guān)，比較次數(shù)為，平均時