数据结构实验报告本

《数据结构》实验报告课程名称：数据结构实验室名称：机房开课学院：信息技术学院专业班级：计算机科学与技术B22-2组号：组长学号姓名：组员学号姓名：组员学号姓名：指导老师：5019.12

预备实验：C语言知识回顾实验日期：年月日实验目的及要求1.熟练掌握C语言中数组、函数、结构体、文件的使用；2.熟练掌握数组（包括结构体数组）的排序，遍历等基本算法的实现；实验内容任务一1．题目要求输入n个整数，输出其中与平均值最接近的元素的值及下标。要求定义下面功能函数，并在main函数中调用这些函数实现题目要求的功能：1.doublegetAvg(inta[],intn)功能：求数组a中n个数的平均值。2.intgetIndex(inta[],intn,doublex)功能：获取与x的值最接近的数组元素的下标。2．源程序清单（含必要的注释）3．程序运行时的输入输出结果任务二1．题目要求若有一文本文件records.txt中已存储学生身高表，每个学生信息包括学号和身高两个数据项，编程要求从文件获取学生身高表后，按身高从低到高的顺序排序后在屏幕上打印学生身高表。要求定义下面功能函数，并在main函数中调用这些函数实现题目要求的功能：1.intgetRecs(STUDENTSs[]);功能：从文件records.txt中读数据到结构体数组s中，并返回人数n。2.voidsort(STUDENTSs[],intn);功能：对结构体数组s按身高从低到高排序。2．学生信息类型定义及说明typedefstruct{intxh;/*学号*/floatsg;/*身高*/}STUDENTS;3．源程序清单（含必要的注释）4．原始数据文件records.txt内容及程序运行结果实验总结分析程序调试中出现的问题及解决方法，心得体会等实验一顺序表操作实现实验日期：年月日实验目的及要求1.熟练掌握线性表的基本操作在顺序存储上的实现；2.以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点；3.掌握线性表的顺序存储结构的定义和基本操作的实现；4.通过本实验加深对C语言的使用（特别是函数调用的参数传递、指针类型的应用）。实验内容已知程序文件seqlist.cpp已给出学生身高信息顺序表的类型定义和基本运算函数定义。（1）顺序表类型定义typedefstruct{intxh;/*学号*/floatsg;/*身高*/intsex;/*性别，0为男生，1为女生*/}datatype;typedefstruct{datatypedata[MAX];/*存放顺序表元素的数组*/intlast;/*表示data中实际存放元素个数*/}Seqlist;（2）基本运算函数原型voidinitList(Seqlist*lp);/*置一个空表*/voidcreateList(Seqlist*lp);/*建一个学生顺序表*/voidsort_xh(Seqlist*lp);/*按学号排序*/voidpntList(Seqlist*lp);/*输出学生表*/voidsave(Seqlist*lp,charstrname[]);/*保存学生顺序表到指定文件*/任务一阅读程序文件seqlist.cpp，其代码如下所示，理解顺序表类型Seqlist和基本运算函数后回答下列问题。/*seqlist.cpp程序文件代码*/#include<stdio.h>#include<stdlib.h>#defineMAX50typedefstruct{intxh;/*学号*/floatsg;/*身高*/intsex;/*性别，0为男生，1为女生*/}datatype;typedefstruct{datatypedata[MAX];/*存放顺序表元素的数组*/intlast;/*表示data中实际存放元素个数*/}Seqlist;voidinitList(Seqlist*lp);/*置一个空表*/voidcreateList(Seqlist*lp);/*建一个学生顺序表*/voidsort_xh(Seqlist*lp);/*按学号排序*/voidpntList(Seqlist*lp);/*输出学生表*/voidsave(Seqlist*lp,charstrname[]);/*保存学生顺序表到指定文件*//*置一个空表*/voidinitList(Seqlist*lp){lp->last=0;}/*建一个学生顺序表*/voidcreateList(Seqlist*lp){ FILE*fp; intxh,sex; floatsg; if((fp=fopen("records.txt","r"))==NULL) { printf("cannotopenreadfile!\n"); exit(1);/*返回OS,该函数定义在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);}/*按学号排升序*/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;} }}/*输出学生顺序表*/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);}/*保存学生顺序表到指定文件*/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）由顺序表类型定义可知，该顺序表类型名为，其中存放的元素为学生信息，学生信息定义的类型名为，包含、、三个成员（写出成员变量名），学生信息存储于数组，顺序表的表长变量为。（2）seqlist.cpp程序编译连接通过后能执行吗？为什么？其代码的整体结构有哪4个组成部分？（3）回答下列问题a）initList函数的形参变量lp存放什么值？顺序表置为空表的实质是做什么操作？b）在建立顺序表的createList函数中，顺序表的数据元素来自何处？已提供的数据如下，建完的顺序表表长是多少？c）sort_xh排序函数采用了什么排序方法？请列举5个学号值写出每趟（5个需排4趟）排序后的结果d）save函数中的形参数组strname中存放什么？

任务二1．题目要求创建一个新的程序文件sy1.c，请调用seqlist.cpp提供的功能函数（以#include"seqlist.cpp"方式导入函数库）及自定义的函数完成以下操作：创建一个包含学生学号、身高、性别的学生身高信息表并输出到屏幕，学生信息从records.txt文件读取；从键盘输入一个身高值，统计高于该身高的学生个数并输出在屏幕；对已建立的学生身高信息表进行倒置，结果输出在屏幕；对已建立的学生身高信息表按学号从小到大排序，并把结果写入到数据文件中（result.txt）；从键盘输入一位学生的相关信息插入到已排序的学生身高信息表中，仍然保持学号的有序性；在程序文件sy1.c中需再定义以下三个功能函数：（1）intcount(Seqlist*lp,floaty)功能：统计学生表中身高值高于y的学生数并返回（2）voidreverse(Seqlist*lp)功能：对lp指向的顺序表进行倒置操作（3）voidinsertX(Seqlist*lp,datatypex)功能：在学号从小到大排序的学生表中插入值为x的学生仍保持学号的有序性2．请根据题目功能要求及程序中的注释填空完整sy1.c代码/*sy1.c程序文件代码*/#include"seqlist.cpp"//导入自定义类型及函数所在的文件seqlist.cpp，该文件与sy1.c存于同一目录中voidinsertX(Seqlist*lp,datatypex);voidreverse(Seqlist*lp);intcount(Seqlist*lp,floaty);intmain(){Seqliststu;//定义stu为学生顺序表变量datatypex;//x为存储一个学生信息的变量intc;charfilename[50];//filename为存储文件名的数组/*创建一个包含学生学号、身高、性别的学生身高信息表stu并输出到屏幕，学生信息从records.txt文件读取*///调用函数initList初始化顺序表stu//调用函数createList创建学生表stuprintf("\nsourcelist:\n");//调用函数pntList打印学生表stugetchar();//在执行程序能起到暂定的作用，按任意键继续/*从键盘输入一个身高值，统计高于该身高的学生个数并输出在屏幕*/printf("\nInputastudentheight:\n");scanf("%f",&x.sg);//统计身高高于指定值的学生数存于c中printf("\nThehigherheight:%d\n",c);getchar();/*对已建立的学生身高信息表进行倒置，结果输出在屏幕；*///倒置顺序表printf("\nlistafterreverse:\n");pntList(&stu); getchar();/*对已建立的学生身高信息表按学号从小到大排序，并把结果写入到数据文件中（result.txt）*///调用函数sort_xh对学生表stu按学号从小到大排序printf("\nInputnewfilenametosave:");//键盘输入文件名字符串存于filename数组中//调用函数save把排序后的顺序表stu存于文件中，文件名在filename数组中/*从键盘输入一位学生的相关信息插入到已排序的学生身高信息表中后仍然保持学号的有序性；*/printf("\nInputastudentinformation:\n");scanf("%d%f%d",&x.xh,&x.sg,&x.sex);//插入printf("\nlistafterinsert:\n");pntList(&stu); return0;}/*统计学生表中身高值高于y的学生数并返回*/intcount(Seqlist*lp,floaty){inti,ct=0;//遍历顺序表统计身高值高于y的学生数到ct变量并返回值}/*对lp指向的顺序表进行倒置操作*/voidreverse(Seqlist*lp){inti,j;datatypetemp;//通过前后数据元素交换的方式实现倒置}/*在学号从小到大排序的学生表中插入值为x的学生仍保持学号的有序性*/voidinsertX(Seqlist*lp,datatypex){inti;if(lp->last>=MAX){printf("listisfull");return;}//在学号升序的顺序表中找插入位置后，插入x并使表长增1}实验总结分析（本程序的重点与难点，调试中出现的问题及解决方法等）实验二链表操作实现实验日期：年月日实验目的及要求1.熟练掌握线性表的基本操作在链式存储上的实现；2.以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点；3.掌握线性表的链式存储结构的定义和基本操作的实现；4.通过本实验加深对C语言的使用（特别是函数的参数调用、指针类型的应用）。实验内容已知程序文件linklist.cpp已给出学生身高信息链表的类型定义和基本运算函数定义。（1）链表类型定义typedefstruct{intxh;/*学号*/floatsg;/*身高*/intsex;/*性别，0为男生，1为女生*/}datatype;typedefstructnode{datatypedata;/*数据域*/structnode*next;/*指针域*/}LinkNode;（2）带头结点的单链表的基本运算函数原型LinkNode*initList();/*置一个空表（带头结点）*/voidcreateList_1(LinkNode*head);/*创建单链表方法1*/voidcreateList_2(LinkNode*head);/*创建单链表方法2*/voidsort_xh(LinkNode*head);/*单链表排序*/voidreverse(LinkNode*head);/*对单链表进行结点倒置*/voidpntList(LinkNode*head);/*打印单链表*/voidsave(LinkNode*head,charstrname[]);/*保存单链表到文件*/任务一阅读程序文件linklist.cpp，其代码如下所示，理解LinkNode类型和基本运算函数后回答下列问题。#include<stdio.h>#include<stdlib.h>/*单链表结点类型*/typedefstruct{intxh;/*学号*/floatsg;/*身高*/intsex;/*性别，0为男生，1为女生*/}datatype;typedefstructnode{datatypedata;/*数据域*/structnode*next;/*指针域*/}LinkNode;/*带表头的单链表的基本运算函数*/LinkNode*initList();/*置一个空表（带头结点）*/voidcreateList_1(LinkNode*head);/*创建单链表*/voidcreateList_2(LinkNode*head);/*创建单链表*/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;}/*创建单链表方法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);}/*创建单链表方法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;/*利用原表头结点建新的空表*/while(p){q=p;/*q为被插入的结点*/p=p->next;/*用p记录后继结点*//*遍历新链表查找插入位置*/u=head;while(u->next!=NULL)/*查找插入位置*/{if(u->next->data.xh>q->data.xh)break;u=u->next; }/*插入在u结点的后面*/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指向结点头插到链表*/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）由单链表结点类型定义可知，该链表结点类型名为，向系统申请一个学生结点空间并把起始地址存于结点指针变量s中的语句是：。（2）回答问题：a）已知：LinkNode*head;画出执行head=initList();语句后的链表结构示意图b）在a)操作的基础上，根据下面records.txt中的数据，画出执行createList_1(head);语句后的链表结构示意图（可以只画学号成员）c）在b)操作的基础上，画出执行sort_xh(head);语句后的链表结构示意图d）在c)操作的基础上，画出执行reverse(head);语句后的链表结构示意图（3）写出下列操作对应的执行语句（以下的指针变量的类型都是上述定义的结点指针类型）a）把一个s指针指向的结点头插到以h为头指针带表头结点的单链表中的语句b）把一个s指针指向的结点头插到以h为头指针不带表头结点的单链表中的语句c）在单链表中删除r所指结点的后继结点（假设存在）的语句d）分别写出循环及非循环单链表中判断r所指结点是尾结点（假设存在）的条件任务二1．题目要求创建一个新的程序文件sy2.c，请调用linklist.cpp提供的功能函数（以#include"linklist.cpp"方式导入函数库）及自定义的函数完成以下操作：从数据文件records.txt中读取学生信息，建立与源数据同序的学生链表并打印在屏幕上；统计学生链表中身高达标人数（男女生的身高达标值由键盘输入），并打印结果；对学生链表按学号从小到大排序；从键盘输入一位学生的相关信息插入到已排序的学生身高链表中后仍然保持学号的有序性；对上述操作后的学生链表进行倒置，结果输出到数据文件result.txt中；删除链表中身高低于指定值的所有学生结点，并打印删除后的链表；在程序文件sy2.c中需再定义以下三个功能函数：（1）intcount(LinkNode*head,floatsg_fm,floatsg_m)功能：已知女生达标身高为sg_fm，男生达标身高为sg_m，统计head为头指针的学生链表中身高达标人数并返回；（2）voidinsertX(LinkNode*head,datatypex)功能：在学号从小到大排序的学生链表中插入值为x的学生，仍保持学号的有序性（3）intdelList(LinkNode*head,floatsg)功能：删除head为头指针的学生链表中身高低于指定身高的所有学生结点，删除成功返回1，否则返回0；2．请根据题目功能要求或程序中的注释完整sy2.c代码#include"linklist.cpp"intcount(LinkNode*head,floatsg_fm,floatsg_m);/*统计head为头指针的学生链表中身高达标人数并返回*/voidinsertX(LinkNode*head,datatypex);/*在学号从小到大排序的学生链表中插入值为x的学生仍保持学号的有序性*/intdelList(LinkNode*head,floatsg);/*删除head为头指针的学生链表中身高低于指定身高的所有学生结点，删除成功返回1，否则返回0*/voidmain(){LinkNode*head;intc,flag;floatsg,sg_fm,sg_m;datatypex;/*建立与源数据文件同序的学生链表并输出；*/head=;/*建空链表*/;/*调用建链表函数建立所需链表*/printf("\n与数据文件同序的学生链表：\n");;/*调用函数打印输出链表中信息*/getchar();/*统计学生链表中身高达标人数（男女生的身高达标值由键盘输入）并打印结果；*/printf("\n输入达标的女生、男生身高值：");scanf("%f%f",&sg_fm,&sg_m);c=count();printf("\n达标学生人数为：%d",c);getchar();/*对学生链表按学号进行排序*/sort_xh(head);/*在学生链表中插入指定的学生元素后使链表仍按学号有序*/x.xh=3;x.sg=1.67;x.sex=0;insertX();printf("\nnewlistafterinsert:\n");pntList(head);getchar();/*对学生链表进行倒置，结果输出到文件result.txt中；*/reverse(head);save(head,"result.txt");getchar();/*删除链表中身高低于指定值的所有学生结点;*/sg=1.67;flag=;if(flag)printf("\ndeletesucceed!\n");elseprintf("\ndeletefailed\n");printf("\nnewlistafterdelete:\n");pntList(head);getchar();}//统计学生链表中身高达标人数并返回(sg_fm女生身高达标值、sg_m男生身高达标值)intcount(LinkNode*head,floatsg_fm,floatsg_m){intn=0;LinkNode*p;}//删除学生链表中身高低于指定身高(存于sg中)的所有学生结点，删除成功返回1，否则返回0intdelList(LinkNode*head,floatsg){LinkNode*p,*q;intflag=0;q=head;p=head->next;while(p!=NULL){if(p->data.sg<sg){/*删除p所指结点*/flag=1;}else{}}returnflag;/*删除成功返回1,否则返回0*/}//在学号从小到大排序的学生链表中插入值为x的学生仍保持学号的有序性voidinsertX(LinkNode*head,datatypex){}实验总结分析（本程序的重点与难点，调试中出现的问题及解决方法等）实验三二叉树操作实现实验日期：年月日实验目的及要求1.熟练掌握树的基本概念、二叉树的基本操作及在链式存储结构上的实现；2.重点掌握二叉树的创建、遍历及求深度等算法；3.掌握运用递归方式描述算法及编写递归C程序的方法，提高算法分析和程序设计能力。4.掌握以顺序栈为辅助存储，对二叉树进行非递归中序遍历的算法。实验内容键盘输入一个字符串，利用二叉树前序遍历的结果建成一棵二叉树，并用三种遍历方法打印，比较是否与自己预先想象的相一致。再求树的深度、1度结点数、2度节点数，交换二叉树的左右子树并输出交换后的中序遍历结果验证交换的正确性。找到二叉树中序遍历最后一个结点并输出结点值。利用顺序栈为辅助存储对二叉树进行非递归中序遍历（选做）。利用顺序队列为辅助存储对二叉树进行层序遍历（选做）。二叉树结点类型定义：typedefchardatatype;typedefstructtnode{datatypedata;structtnode*left,*right;}BiTNode,*BiTree;顺序栈的类型定义：typedefstruct{BiTreedata[MAX];inttop;}SeqStack,*SeqStackptr;任务一：阅读自定义头文件seqStack_BTree.h，包含顺序栈的数据类型定义及顺序栈基本操作函数，定义的基本操作如下：（1）voidError(char*s);/*自定义错误处理函数*/（2）voidInitStack(SeqStackptrsp);/*初始化栈——置空栈*/（3）intEmptyStack(SeqStackptrsp);/*判栈空*/（4）intFullStack(SeqStackptrsp);/*判栈满*/（5）voidPush(SeqStackptrsp,BiTreex);/*进栈(元素压入栈顶)*/（6）BiTreePop(SeqStackptrsp);/*出栈(元素从栈顶弹出)*/（7）BiTreeGetTop(SeqStackptrsp);/*读栈顶元素(不出栈)*/（8）intCount(SeqStackptrsp);/*计算栈中元素个数*/请回答下列问题（1）栈是限定在表的一端进行插入或删除操作的线性表，其操作原则是。（2）设数组S[100]存储一个顺序栈的元素，变量top指示下一个入栈元素在数组中的下标位置，栈为空的条件是，栈为满的条件是。（3）在n个结点二叉树的二叉链表存储中，其指针域的总数为个，其中个用于链接孩子结点，个空闲着。（4）在二叉链表存储中，数据域为data，左右子树的指针分别为left和right，则判断：指针p所指结点为0度结点的条件是；指针p所指结点为1度结点的条件是；指针p所指结点为2度结点的条件是。（5）T为二叉树的根的地址，该树是空二叉树满足条件：。任务二1．题目要求创建一个程序文件sy3.c，自定义相应函数完成以下操作：BiTNode*createTree();/*以前序遍历的顺序建立二叉树*/voidpreOrder(BiTNode*T);/*前序遍历*/voidinOrder(BiTNode*T);/*中序遍历*/voidpostOrder(BiTNode*T);/*后序遍历*/intdeep(BiTNode*T);/*求二叉树深度*/intleaf(BiTNode*T);/*求叶子结点数*/intoneChild(BiTNode*T);/*求1度结点数*/inttwoChild(BiTNode*T);/*求2度结点数*/voidexchange(BiTNode*T);/*二叉树左右子树交换*/BiTNode*inOrderLastNode(BiTNode*T);/*二叉树中序遍历最后一个结点*/voidinOrderNonRecursive(BiTNode*T);/*中序遍历的非递归算法*/2．请根据题目功能要求或程序中的注释完成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);/*求叶子结点数*/intoneChild(BiTNode*T);/*求1度结点数*/inttwoChild(BiTNode*T);/*求2度结点数*/voidexchange(BiTNode*T);/*二叉树左右子树交换*/BiTNode*inOrderLastNode(BiTNode*T);/*找二叉树中序遍历最后一个结点*/voidinOrderNonRecursive(BiTNode*T);/*中序遍历的非递归算法*/intmain(){ BiTNode*root; /*利用二叉树前序遍历的结果建成一棵二叉树*/ show_tree(root);/*二叉树的显示，不要求掌握*/printf("\n先序遍历序列：");printf("\n中序遍历序列："); printf("\n后序遍历序列："); printf("\n树的深度=%d",); /*求树的深度*/ printf("\n叶子结点数=%d",); /*求叶子结点数*/ printf("\n1度结点数=%d",); /*求1度结点数*/ printf("\n2度结点数=%d",); /*求2度结点数*/ printf("\n交换左右子树后的中序遍历结果："); /*交换二叉树的左右子树*/ inOrder(root);/*输出交换后的中序遍历结果*/ /*找到二叉树中序遍历最后一个结点并输出结点值*/printf("\n中序遍历最后一个结点值：%c",); printf("\n中序遍历非递归："); /*非递归中序遍历二叉树*/ return0;}/*以前序遍历的顺序建立二叉树*/BiTNode*createTree(){ charch; BiTNode*T; if((ch=getchar())=='#') returnNULL; T=(BiTNode*)malloc(sizeof(BiTNode));/*生成二叉树的根结点*/ T->data=ch; T->left=createTree();/*递归实现左子树的建立*/ T->right=createTree();/*递归实现右子树的建立*/ 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=}/*求叶子结点数*/intleaf(BiTNode*T){}/*求1度结点数*/intoneChild(BiTNode*T){}/*求2度结点数*/inttwoChild(BiTNode*T){}/*二叉树左右子树交换*/voidexchange(BiTNode*T){BiTNode*tmp;if(T){}}/*找二叉树中序遍历最后一个结点*/BiTNode*inOrderLastNode(BiTNode*T){BiTNode*p=T;if(p){while(p->right)}}/*中序遍历的非递归算法*/voidinOrderNonRecursive(BiTNode*T){SeqStackss;BiTNode*bt=T;InitStack(&ss);/*创建并初始化堆栈S*/while(bt||!EmptyStack(&ss)){while(bt)/*一直向左并将沿途结点压入堆栈*/{}if(!EmptyStack(&ss)){/*结点弹出堆栈*/printf("%c",bt->data);/*（访问）打印结点*//*转向右子树*/}}}3．程序执行时屏幕上的输入内容实验总结分析（本程序的重点与难点，调试中出现的问题及解决方法等）实验四图操作实现实验日期：年月日实验目的及要求1.熟练掌握图的邻接矩阵和邻接表的存储方式；2.实现图的一些基本运算，特别是深度优先遍历和广度优先遍历；实验内容用邻接矩阵法建一个无向连通图（顶点信息为顺序字母A，B，C，D...，而非键盘输入），分别用dfs（深度优先搜索）和bfs（广度优先搜索）遍历，输出图中顶点信息并验证。邻接矩阵图类型定义：#defineMAX40typedefcharvexType;/*顶点类型*/typedefstruct{vexTypevex[MAX];intarcs[MAX][MAX];intvn,en;}MGraph;访问标记数组定义：intvisited[MAX];/*值为0时对应顶点未被访问，值为1时对应顶点已被访问*/顺序存储的循环队列类型定义：typedefintdatatype;/*队列元素为图的顶点下标,int型*/typedefstructnode{datatypedata[MAX];intfront,rear;}SeqQueue;/*顺序存储的循环队列类型*/任务1．阅读自定义函数库文件Queue_graph.h，其中为队列的相关操作。2．创建一个程序文件sy4.c，自定义相应函数完成以下操作：（1）voidcreateGraph(MGraph*g)/*建邻接矩阵存储的无向图*/（2）voidvisit(MGraph*g,intv)/*访问v号顶点*/（3）voiddfs(MGraph*g,intv)/*邻接矩阵存储的图的深度优先搜索*/（4）voidbfs(MGraph*g,intv)/*邻接矩阵存储的图的广度优先搜索*/3．回答下列问题（1）现有定义：MGraph*g，并且g指针指向的无向图已创建完成，请写出该图遍历前需初始化visited数组的C程序语句。（2）定义函数intcount(MGraph*g)统计非连通图的连通分量个数。（说明：借助遍历算法实现）4．sy4.c源程序清单（含必要的注释）#include"Queue_graph.h"typedefcharvexType;/*顶点类型*/typedefstruct{vexTypevex[MAX];intarcs[MAX][MAX];intvn,en;}MGraph;/*邻接矩阵图类型*/intvisited[MAX];/*访问标记数组*/voidcreateGraph(MGraph*g);/*建邻接矩阵存储的无向图*/voidvisit(MGraph*g,intv);/*访问v号顶点*/voiddfs(MGraph*g,intv);/*邻接矩阵存储的图的深度优先搜索*/voidbfs(MGraph*g,intv);/*邻接矩阵存储的图的广度优先搜索*/intmain(){MGraphmg;inti,j,start;/*创建邻接矩阵存储的无向图*/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);/*填空，深度优先搜索*/getchar();for(i=0;i<mg.vn;i++)visited[i]=0;printf("\ntranversalinbreathfirstserchalgorithm");(&mg,start);/*填空，广度优先搜索*/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,);/*填空，读入顶点的个数和边的个数*/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)/*邻接矩阵存储的图的深度优先搜索*/{inti;visit(g,v);visited[v]=1;}/*enddfsfunction*/voidbfs(MGraph*g,intv)/*邻接矩阵存储的图的广度优先搜索*/{SeqQueuesq;inti,j;InitQueue(&sq);EnQueue(&sq,v);visited[v]=1;while(!Empty(&sq)){}}/*endbfsfunction*/实验总结分析（本程序的重点与难点，调试中出现的问题及解决方法等）实验五顺序表的排序及查找实验日期：年月日实验目的及要求1.熟练掌握各种排序方法及不同查找运算的实现；2.重点用C程序对顺序表采用直接插入、冒泡法和直接选择法进行排序；4.重点掌握二分查找算法实现。实验内容建立一存有若干学生信息（学号、姓名、一门课成绩）的顺序表，学号为关键字，分别按学号升序、姓名升序、成绩降序要求对学生表进行排序并输出各排序后的学生信息，并能输入指定的学号查找该学生，若找到输出该生的学号、姓名及成绩信息，否则输出“Nofound”。任务程序文件sy5.c中自定义函数如下：（1）voidCreateTable(Tabler)创建学生信息顺序表，记录从数组的1号下标开始存放；（2）voidInsertSort(Tabler)直接插入法对学生表按学号排成升序；（3）voidBubbleSort(Tabler)冒泡法对学生表按姓名排成升序；（4）voidSelectSort(Tabler)简单选择法对学生表按成绩排降序；（5）voidOutput(Tabler)输出顺序表中的记录；（6）intBinary(Tabler,intk)给定一个学号以二分法查找已建顺序表中的学生记录，找到返回该记录下标，否则返回0。1．回答下列问题（1）以二分查找法（或称折半查找法）查找一个线性表时，此线性表必须是___________存储的________表。假设对于一个有序序列0,1,2,3,5,7,8,9采用二分查找法查找元素，如查找元素8，则依次比较的元素是。（2）n个记录的顺序表中，若采用直接插入排序时有可能最后一趟之前所有元素都不是最终排序位置，当待排记录事先是时最快，比较记录次数为，移动记录次数为，平均时间复杂度是；若采用冒泡排序时，记录的比较次数与记录初始状态无关，比较次数为，平均时