(完整版)数据结构实验答案及解析

WORD格式可编辑《数据结构》实验指导2013/2014学年第2学期姓名：______________学号：_________班级：______________指导教师：______________潍坊学院计算机工程学院2014专业知识整理分享WORD格式可编辑预备实验C语言的函数数组指针结构体知识一、实验目的1、复习C语言中函数、数组、指针和结构体的概念。2、熟悉利用C语言进行程序设计的一般方法。二、实验内容和要求1、调试程序：输出100以内所有的素数（用函数实现）。#include<stdio.h>/*判断一个数是否为素数*/intisprime(intn){for(intm=2;m*m<=n;m++){if(n%m==0)return0;return1;}/*输出100以内所有素数*/intmain(){inti;for(i=2;i<100;i++)if(isprime(i)==1)printf(“%4d”,i);return0;}运行结果：2、调试程序：对一维数组中的元素进行逆序排列。#include<stdio.h>#defineN10intmain(){inta[N]={0,1,2,3,4,5,6,7,8,9},i,temp;printf(“theoriginalArrayis:\n”);for(i=0;i<N;i++)printf(“%4d”,a[i]);for(i=0;i<N/2;i++){/*交换数组元素使之逆序*/temp=a[i];专业知识整理分享WORD格式可编辑a[i]=a[N-i-1];a[N-i-1]=temp;}printf(“\nthechangedArrayis:\n”);for(i=0;i<N;i++)printf(“%4d”,a[i]);return0;}运行结果：3、调试程序：在二维数组中，若某一位置上的元素在该行中最大，而在该列中最小，则该元素即为该二维数组的一个鞍点。要求从键盘上输入一个二维数组，当鞍点存在时，把鞍点找出来。#include<stdio.h>#defineM3#defineN4intmain(){inta[M][N],i,j,k;printf(“请输入二维数组的数据：\n”);for(i=0;i<M;i++)for(j=0;j<N;j++)scanf(“%d”,&a[i][j]);for(i=0;i<M;i++){for(j=0;j<N;j++)/*输出矩阵*/printf(“%4d”,a[i][j]);printf(“\n”);}for(i=0;i<M;i++){k=0;for(j=1;j<N;j++)/*找出第i行的最大值*/if(a[i][j]>a[i][k])k=j;for(j=0;j<M;j++)/*判断第i行的最大值是否为该列的最小值*/if(a[j][k]<a[i][k])break;if(j==M)/*在第i行找到鞍点*/printf(“%d,%d,%d\n”),a[i][k],i,k);}return0;专业知识整理分享WORD格式可编辑}运行结果：4、调试程序：利用指针输出二维数组的元素。#include<stdio.h>intmain(){inta[3][4]={1,3,5,7,9,11,13,15,17,19,21,23};int*p;for(p=a[0];p<a[0]+12;p++){if((p-a[0])%4==0)printf(“\n”);printf(%4d”,*p);}return0;}运行结果：5、调试程序：输入10个学生的成绩，每个学生成绩包括学号、姓名和三门课的成绩。要求打印出三门课的平均成绩及成绩最高者的姓名和成绩。#include<stdio.h>#defineN10;structstudent{charnum[6];/*学号*/charname[8];/*姓名*/intscore[3];/*成绩*/floatavr;/*平均成绩*/}stu[N];intmain(){inti,j,max,maxi,sum;专业知识整理分享WORD格式可编辑floataverage;for(i=0;i<N;i++){/*输入10个学生的成绩信息*/printf(“\n请输入第%d学生的成绩：\n”,i+1);printf(“学号：”);scanf(“%s”,stu[i].num);printf(“姓名”);scanf(“%s”,stu[i].name);for(j=0;j<3;j++){printf(“成绩%d”,j+1);scanf(“%d”,&stu[i].score[j]);}}average=0;max=0;maxi=0;for(i=0;i<N;i++){sum=0;/*计算平均成绩，找出成绩最高的学生*/for(j=0;j<3;j++)sum+=stu[i].score[j];stu[i].avr=sum/3.0;average+=stu[i].avr;if(sum>max){max=sum;maxi=i;}}average/=10;printf(“学号姓名成绩1成绩2成绩3平均分\n);for(i=0;i<10;i++){printf(“%8s%10s”,stu[i].num,stu[i].name);for(j=0;j<3;j++)printf(“%7d”,stu[i].score[j]);printf(“%6.2f\n”,stu[i].avr);}printf(“平均成绩是：%5.2f\n”,average);printf(“最好成绩的学生是：%s，总分是%d”,stu[maxi].name,max);return0;}运行结果专业知识整理分享WORD格式可编辑三、实验小结对C语言中函数、数组、指针和结构体的概念，有了进一步的加深。并且可以利用C语言进行初步程序设计。四、教师评语专业知识整理分享WORD格式可编辑实验一顺序表与链表一、实验目的1、掌握线性表中元素的前驱、后续的概念。2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。3、对线性表相应算法的时间复杂度进行分析。4、理解顺序表、链表数据结构的特点（优缺点）。二、实验内容和要求1、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。#include<stdio.h>#include<malloc.h>#defineERROR0#defineOK1#defineINIT_SIZE5/*初始分配的顺序表长度*/#defineINCREM5/*溢出时，顺序表长度的增量*/typedefintElemType;/*定义表元素的类型*/typedefstructSqlist{ElemType*slist;/*存储空间的基地址*/intlength;/*顺序表的当前长度*/intlistsize;/*当前分配的存储空间*/}Sqlist;intInitList_sq(Sqlist*L);/*初始化顺序表L，并将其长度设为0*/intCreateList_sq(Sqlist*L,intn);/*构造顺序表的长度为n*/intListInsert_sq(Sqlist*L,inti,ElemTypee);/*在顺序线性表L中第i个元素之前插入新的元素e*/intPrintList_sq(Sqlist*L);/*输出顺序表的元素*/intListDelete_sq(Sqlist*L,inti);/*删除第i个元素*/intListLocate(Sqlist*L,ElemTypee);/*查找值为e的元素*/intInitList_sq(Sqlist*L){L->slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));if(!L->slist)returnERROR;L->length=0;L->listsize=INIT_SIZE;returnOK;}/*InitList*/intCreateList_sq(Sqlist*L,intn){专业知识整理分享WORD格式可编辑ElemTypee;inti;for(i=0;i<n;i++){printf("inputdata%d",i+1);scanf("%d",&e);if(!ListInsert_sq(L,i+1,e))returnERROR;}returnOK;}/*CreateList*//*输出顺序表中的元素*/intPrintList_sq(Sqlist*L){inti;for(i=1;i<=L->length;i++)printf("%5d",L->slist[i-1]);returnOK;}/*PrintList*/intListInsert_sq(Sqlist*L,inti,ElemTypee){intk;if(i<1||i>L->length+1)returnERROR;if(L->length>=L->listsize){L->slist=(ElemType*)realloc(L->slist,(INIT_SIZE+INCREM)*sizeof(ElemType));if(!L->slist)returnERROR;L->listsize+=INCREM;}for(k=L->length-1;k>=i-1;k--){L->slist[k+1]=k;}L->slist[i-1]=e;L->length++;returnOK;}/*ListInsert*//*在顺序表中删除第i个元素*/intListDelete_sq(Sqlist*L,inti){if((i<1)||(i>L->length))returnERROR;for(p=i-1;p<->length-1;p++)L->slist[p]=L->slist[p+1];专业知识整理分享WORD格式可编辑L->length--;returnOK;}/*在顺序表中查找指定值元素，返回其序号*/intListLocate(Sqlist*L,ElemTypee){}intmain(){Sqlistsl;intn;printf("pleaseinputn:");/*输入顺序表的元素个数*/scanf("%d",&n);if(n>0){printf("\n1-CreateSqlist:\n");InitList_sq(&sl);CreateList_sq(&sl,n);printf("\n2-PrintSqlist:\n");PrintList_sq(&sl);}elseprintf("ERROR");return0;}算法分析与运行结果pleaseinputn:51-CreateSqlist:inputdata10inputdata25inputdata38inputdata43inputdata562-PrintSqlist:05836Pressanykeytocontinue专业知识整理分享WORD格式可编辑2、为第1题补充删除和查找功能函数，并在主函数中补充代码验证算法的正确性。算法代码：intListDelete_sq(Sqlist*L,inti){intp;if((i<1)||(i>L->length))returnERROR;for(p=i-1;p<L->length-1;p++){L->slist[p]=L->slist[p+1];}L->length--;returnOK;}/*在顺序表中查找指定值元素，返回其序号*/intListLocate(Sqlist*L,ElemTypee){inti=0;while((i<=L->length)&&(L->slist[i]!=e))i++;if(i<=L->length)return(i+1);elsereturn(-1);}专业知识整理分享WORD格式可编辑3、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。#include<stdio.h>#include<malloc.h>#defineERROR0#defineOK1typedefintElemType;/*定义表元素的类型*/typedefstructLNode{/*线性表的单链表存储*/ElemTypedata;structLNode*next;}LNode,*LinkList;LinkListCreateList(intn);/构造顺序表的长度*/voidPrintList(LinkListL);/*输出带头结点单链表的所有元素*/专业知识整理分享WORD格式可编辑intGetElem(LinkListL,inti,ElemType*e);/*在顺序线性表L中，当第i个元素存在时，将其赋值为e*/LinkListCreateList(intn){LNode*p,*q,*head;inti;head=(LinkList)malloc(sizeof(LNode));head->next=NULL;p=head;for(i=0;i<n;i++){q=(LinkList)malloc(sizeof(LNode));printf("inputdata%i:",i+1);scanf("%d",&q->data);/*输入元素值*/q->next=NULL;/*结点指针域置空*/p->next=q;/*新结点连在表末尾*/p=q;}returnhead;}/*CreateList*/voidPrintList(LinkListL){LNode*p;p=L->next;/*p指向单链表的第1个元素*/while(p!=NULL){printf("%5d",p->data);p=p->next;}}/*PrintList*/intGetElem(LinkListL,inti,ElemType*e){LNode*p;intj=1;p=L->next;while(p&&j<i){p=p->next;j++;}if(!p||j>i)returnERROR;*e=p->data;returnOK;}/*GetElem*/intmain(){intn,i;ElemTypee;LinkListL=NULL;/*定义指向单链表的指针*/printf("pleaseinputn:");/*输入单链表的元素个数*/专业知识整理分享WORD格式可编辑scanf("%d",&n);if(n>0){printf("\n1-CreateLinkList:\n");L=CreateList(n);printf("\n2-PrintLinkList:\n");PrintList(L);printf("\n3-GetElemfromLinkList:\n");printf("inputi=");scanf("%d",&i);if(GetElem(L,i,&e))printf("No%iis%d",i,e);elseprintf("notexists");}elseprintf("ERROR");return0;}算法分析与运行结果pleaseinputn:51-CreateLinkList:inputdata1:8inputdata2:6inputdata3:3inputdata4:5inputdata5:42-PrintLinkList:863543-GetElemfromLinkList:inputi=2No2is6Pressanykeytocontinue专业知识整理分享WORD格式可编辑4、为第3题补充插入功能函数和删除功能函数。并在主函数中补充代码验证算法的正确性。算法代码intListInsert_sq(LNode*L,inti,ElemTypee){intk;if(i<1||i>L->length+1)returnERROR;if(L->length>=L->listsize){L->data=(ElemType*)realloc(L->data,(INIT_SIZE+INCREM)*sizeof(ElemType));if(!L->data)returnERROR;L->listsize+=INCREM;}专业知识整理分享WORD格式可编辑#include<stdio.h>#include<malloc.h>#defineERROR0#defineOK1typedefintElemType;/*定义表元素的类型*/typedefstructLNode{/*线性表的单链表存储*/ElemTypedata;structLNode*next;}LNode,*LinkList;LinkListCreateList(intn);/*专业知识整理分享WORD格式可编辑以下为选做实验：5、循环链表的应用（约瑟夫回环问题）n个数据元素构成一个环，从环中任意位置开始计数，计到m将该元素从表中取出，重复上述过程，直至表中只剩下一个元素。提示：用一个无头结点的循环单链表来实现n个元素的存储。算法代码6、设一带头结点的单链表，设计算法将表中值相同的元素仅保留一个结点。提示：指针p从链表的第一个元素开始，利用指针q从指针p位置开始向后搜索整个链表，删除与之值相同的元素；指针p继续指向下一个元素，开始下一轮的删除，直至p＝＝null为至，既完成了对整个链表元素的删除相同值。算法代码三、实验小结具体的掌握线性表中元素的前驱、后续的概念。以及顺序表与链表的建立、插入元素、删除表中某元素的算法。并学习了对线性表相应算法的时间复杂度进行分析。四、教师评语专业知识整理分享WORD格式可编辑实验二栈和队列一、实验目的1、掌握栈的结构特性及其入栈，出栈操作；2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。二、实验内容和要求1、阅读下面程序，将函数Push和函数Pop补充完整。要求输入元素序列12345e，运行结果如下所示。#include<stdio.h>#include<malloc.h>#defineERROR0#defineOK1#defineSTACK_INT_SIZE10/*存储空间初始分配量*/#defineSTACKINCREMENT5/*存储空间分配增量*/typedefintElemType;/*定义元素的类型*/typedefstruct{ElemType*base;ElemType*top;intstacksize;/*当前已分配的存储空间*/}SqStack;intInitStack(SqStack*S);/*构造空栈*/intpush(SqStack*S,ElemType*e);/*入栈*/intPop(SqStack*S,ElemType*e);/*出栈*/intCreateStack(SqStack*S);/*创建栈*/voidPrintStack(SqStack*S);/*出栈并输出栈中元素*/intInitStack(SqStack*S){S->base=(ElemType*)malloc(STACK_INT_SIZE*sizeof(ElemType));专业知识整理分享WORD格式可编辑if(!S->base)returnERROR;S->top=S->base;S->stacksize=STACK_INT_SIZE;returnOK;}/*InitStack*/intPush(SqStack*S,ElemTypee){}/*Push*/intPop(SqStack*S,ElemType*e){}/*Pop*/intCreateStack(SqStack*S){inte;if(InitStack(S))printf("InitSuccess!\n");else{printf("InitFail!\n");returnERROR;}printf("inputdata:(Terminatedbyinputingacharacter)\n");while(scanf("%d",&e))Push(S,e);returnOK;}/*CreateStack*/voidPrintStack(SqStack*S){ElemTypee;while(Pop(S,&e))printf("%3d",e);}/*Pop_and_Print*/intmain(){SqStackss;printf("\n1-createStack\n");CreateStack(&ss);printf("\n2-Pop&Print\n");PrintStack(&ss);return0;}算法分析：输入元素序列12345，为什么输出序列为54321？体现了栈的什么特性？专业知识整理分享WORD格式可编辑2、在第1题的程序中，编写一个十进制转换为二进制的数制转换算法函数（要求利用栈来实现），并验证其正确性。实现代码voidconveshen(SqStack*S){ElemTypen,h;intm=0,k=0;InitStack(S);printf("Inputelement\n");scanf("%d",&n);while(n){m++;Push(S,n%2);n=n/2;}while(k<m){k++;Pop(S,&h);printf("%d",h);}}intmain(){SqStackS;conveshen(&S);printf("\n");}专业知识整理分享WORD格式可编辑3、阅读并运行程序，并分析程序功能。#include<stdio.h>#include<malloc.h>#include<string.h>#defineM20#defineelemtypechartypedefstruct{elemtypestack[M];inttop;}stacknode;voidinit(stacknode*st);voidpush(stacknode*st,elemtypex);voidpop(stacknode*st);voidinit(stacknode*st){st->top=0;}专业知识整理分享WORD格式可编辑voidpush(stacknode*st,elemtypex){if(st->top==M)printf("thestackisoverflow!\n");else{st->top=st->top+1;st->stack[st->top]=x;}}voidpop(stacknode*st){st->top=st->top-1;}intmain(){chars[M];inti;printf("createaemptystack!\n");stacknode*sp;sp=malloc(sizeof(stacknode));init(sp);printf("inputaexpression:\n");gets(s);for(i=0;i<strlen(s);i++){if(s[i]=='(')push(sp,s[i]);if(s[i]==')')pop(sp);}if(sp->top==0)printf("'('match')'!\n");elseprintf("'('notmatch')'!\n");return0;}输入：2+((c-d)*6-(f-7)*a)/6运行结果：专业知识整理分享WORD格式可编辑输入：a-((c-d)*6-(s/3-x)/2运行结果：程序的基本功能：以下为选做实验：专业知识整理分享WORD格式可编辑4、设计算法，将一个表达式转换为后缀表达式，并按照后缀表达式进行计算，得出表达式得结果。实现代码5、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点（不设队头指针），试编写相应的置空队列、入队列、出队列的算法。实现代码：三、实验小结基本掌握栈的结构特性及其入栈，出栈操作；以及队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作四、教师评语专业知识整理分享WORD格式可编辑实验三串的模式匹配一、实验目的1、了解串的基本概念2、掌握串的模式匹配算法的实现二、实验内容和要求1、阅读并运行下面程序，根据输入写出运行结果。#include<stdio.h>#include<string.h>#defineMAXSIZE100typedefstruct{chardata[MAXSIZE];intlength;}SqString;intstrCompare(SqString*s1,SqString*s2);/*串的比较*/voidshow_strCompare();voidstrSub(SqString*s,intstart,intsublen,SqString*sub);/*求子串*/voidshow_subString();intstrCompare(SqString*s1,SqString*s2){inti;for(i=0;i<s1->length&&i<s1->length;i++)if(s1->data[i]!=s2->data[i])returns1->data[i]-s2->data[i];returns1->length-s2->length;}voidshow_strCompare(){SqStrings1,s2;intk;printf("\n***showCompare***\n");printf("inputstrings1:");gets(s1.data);s1.length=strlen(s1.data);printf("inputstrings2:");gets(s2.data);s2.length=strlen(s2.data);if((k=strCompare(&s1,&s2))==0)printf("s1=s2\n");专业知识整理分享WORD格式可编辑elseif(k<0)printf("s1<s2\n");elseprintf("s1>s2\n");printf("\n***showover***\n");}voidstrSub(SqString*s,intstart,intsublen,SqString*sub){inti;if(start<1||start>s->length||sublen>s->length-start+1){sub->length=0;}for(i=0;i<sublen;i++)sub->data[i]=s->data[start+i-1];sub->length=sublen;}voidshow_subString(){SqStrings,sub;intstart,sublen,i;printf("\n***showsubString***\n");printf("inputstrings:");gets(s.data);s.length=strlen(s.data);printf("inputstart:");scanf("%d",&start);printf("inputsublen:");scanf("%d",&sublen);strSub(&s,start,sublen,&sub);if(sub.length==0)printf("ERROR!\n");else{printf("subStringis:");for(i=0;i<sublen;i++)printf("%c",sub.data[i]);}printf("\n***showover***\n");}intmain(){intn;do{printf("\n---String---\n");printf("1.strCompare\n");printf("2.subString\n");专业知识整理分享WORD格式可编辑printf("0.EXIT\n");printf("\ninputchoice:");scanf("%d",&n);getchar();switch(n){case1:show_strCompare();break;case2:show_subString();break;default:n=0;break;}}while(n);return0;}运行程序输入：1studentstudents2ComputerDataStuctures104运行结果：专业知识整理分享WORD格式可编辑2、实现串的模式匹配算法。补充下面程序，实现串的BF和KMP算法。#include<stdio.h>#include<string.h>#defineMAXSIZE100typedefstruct{chardata[MAXSIZE];专业知识整理分享WORD格式可编辑intlength;}SqString;intindex_bf(SqString*s,SqString*t,intstart);voidgetNext(SqString*t,intnext[]);intindex_kmp(SqString*s,SqString*t,intstart,intnext[]);voidshow_index();intindex_bf(SqString*s,SqString*t,intstart){inti,j,pos;if(t->length==0)return(0);pos=start;i=pos;j=0;while(i<s->length&&j<t->length)if(s->data[i]==t->data[j]){i++;j++;}else{pos++;i=pos;j=0;}if(j>=t->length)return(pos);elsereturn(-1);}}voidgetNext(SqString*t,intnext[]){inti=0,j=-1;next[0]=-1;while(i<t->length){if((j==-1)||(t->data[i]==t->data[j])){i++;j++;next[i]=j;}elsej=next[j];}}intindex_kmp(SqString*s,SqString*t,intstart,intnext[]){inti,j;if(t->length==0)return(0);i=start;j=0;while(i<s->length&&j<t->length)专业知识整理分享WORD格式可编辑if(s->data[i]==t->data[j]){i++;j++;}elsej=next[j];if(j>=t->length)return(i-j);elsereturn(-1);}voidshow_index(){SqStrings,t;intk,next[MAXSIZE]={0},i;printf("\n***showindex***\n");printf("inputstrings:");gets(s.data);s.length=strlen(s.data);printf("inputstringt:");gets(t.data);t.length=strlen(t.data);printf("inputstartposition:");scanf("%d",&k);printf("BF:\ntheresultofBFis%d\n",index_bf(&s,&t,k));getNext(&t,next);printf("KMP:\n");printf("next[]:");for(i=0;i<t.length;i++)printf("%3d",next[i]);printf("\n");printf("theresultofKMPis%d\n",index_kmp(&s,&t,k,next));printf("\n***showover***\n");}intmain(){show_index();return0;}输入：abcaabbabcabaacbacbaabcabaa专业知识整理分享WORD格式可编辑1运行结果：三、实验小结通过对算法的运行，加上思考可以深刻了解串的基本概念。并且可以掌握串的模式匹配算法的建立。四、教师评语专业知识整理分享WORD格式可编辑实验四二叉树一、实验目的1、掌握二叉树的基本特性2、掌握二叉树的递归遍历算法3、理解二叉树的非递归算法4、通过二叉树的深度和层次遍历算法，理解二叉树的基本特性二、实验内容和要求1、阅读并运行下面程序，根据输入写出运行结果，并画出二叉树的形态。#include<stdio.h>#include<malloc.h>#defineMAX20typedefstructBTNode{/*节点结构声明*/chardata;/*节点数据*/structBTNode*lchild;structBTNode*rchild;/*指针*/}*BiTree;voidcreateBiTree(BiTree*t){/*先序遍历创建二叉树*/chars;BiTreeq;printf("\npleaseinputdata:(exitfor#)");s=getche();if(s=='#'){*t=NULL;return;}q=(BiTree)malloc(sizeof(structBTNode));if(q==NULL){printf("Memoryallocfailure!");exit(0);}q->data=s;*t=q;createBiTree(&q->lchild);/*递归建立左子树*/createBiTree(&q->rchild);/*递归建立右子树*/}voidPreOrder(BiTreep){/*先序遍历二叉树*/if(p!=NULL){printf("%c",p->data);PreOrder(p->lchild);PreOrder(p->rchild);}}voidInOrder(BiTreep){/*中序遍历二叉树*/if(p!=NULL){专业知识整理分享WORD格式可编辑InOrder(p->lchild);printf("%c",p->data);InOrder(p->rchild);}}voidPostOrder(BiTreep){/*后序遍历二叉树*/if(p!=NULL){PostOrder(p->lchild);PostOrder(p->rchild);printf("%c",p->data);}}voidPreorder_n(BiTreep){/*先序遍历BiTreestack[MAX],q;inttop=0,i;的非递归算法*/for(i=0;i<MAX;i++)stack[i]=NULL;/*初始化栈*/q=p;while(q!=NULL){printf("%c",q->data);if(q->rchild!=NULL)stack[top++]=q->rchild;if(q->lchild!=NULL)q=q->lchild;elseif(top>0)q=stack[--top];elseq=NULL;}}voidrelease(BiTreet){/*释放二叉树空间*/if(t!=NULL){release(t->lchild);release(t->rchild);free(t);}}intmain(){BiTreet=NULL;createBiTree(&t);printf("\n\nPreOrderthetreeis:");PreOrder(t);printf("\n\nInOrderthetreeis:");InOrder(t);printf("\n\nPostOrderthetreeis:");专业知识整理分享WORD格式可编辑PostOrder(t);printf("\n\n先序遍历序列（非递归）:");Preorder_n(t);release(t);return0;}运行程序输入：ABC##DE#G##F###运行结果：2、在上题中补充求二叉树中求结点总数算法（提示：可在某种遍历过程中统计遍历的结点数），并在主函数中补充相应的调用验证正确性。专业知识整理分享WORD格式可编辑算法代码：intPreOrder_num(BiTreep){intj=0;BiTreestack[MAX],q;inttop=0,i;for(i=0;i<MAX;i++)stack[i]=NULL;/*初始化栈*/q=p;while(q!=NULL){j++;0if(q->rchild!=NULL)stack[top++]=q->rchild;if(q->lchild!=NULL)q=q->lchild;elseif(top>0)q=stack[--top];elseq=NULL;}returnj;}专业知识整理分享WORD格式可编辑3、在上题中补充求二叉树中求叶子结点总数算法（提示：可在某种遍历过程中统计遍历的叶子结点数），并在主函数中补充相应的调用验证正确性。算法代码：intBTNodeDepth(BiTreep){intlchilddep,rchilddep;if(p==NULL)return0;else{lchilddep=BTNodeDepth(p->lchild);rchilddep=BTNodeDepth(p->rchild);return(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1);}4、在上题中补充求二叉树深度算法，并在主函数中补充相应的调用验证正确性。算法代码：intBTNodeDepth(BiTreep){专业知识整理分享WORD格式可编辑intlchilddep,rchilddep;if(p==NULL)return0;else{lchilddep=BTNodeDepth(p->lchild);rchilddep=BTNodeDepth(p->rchild);return(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1);}}选做实验：（代码可另附纸）5、补充二叉树层次遍历算法。（提示：利用队列实现）6、补充二叉树中序、后序非递归算法。三、实验小结掌握二叉树的基本特性，以及对递归和非递归的了解。并且通过实验对二叉树在算法的应用有了更深的理解。专业知识整理分享WORD格式可编辑四、教师评语专业知识整理分享WORD格式可编辑实验五图的表示与遍历一、实验目的1、掌握图的邻接矩阵和邻接表表示2、掌握图的深度优先和广度优先搜索方法3、理解图的应用方法二、实验内容和要求1、阅读并运行下面程序，根据输入写出运行结果。#include<stdio.h>#defineN20#defineTRUE1#defineFALSE0intvisited[N];typedefstruct/*队列的定义*/{intdata[N];intfront,rear;}queue;typedefstruct/*图的邻接矩阵*/{intvexnum,arcnum;charvexs[N];intarcs[N][N];}graph;voidcreateGraph(graph*g);/*建立一个无向图的邻接矩阵*/voiddfs(inti,graph*g);/*从第i个顶点出发深度优先搜索*/voidtdfs(graph*g);/*深度优先搜索整个图*/voidbfs(intk,graph*g);/*从第k个顶点广度优先搜索*/voidtbfs(graph*g);/*广度优先搜索整个图*/voidinit_visit();/*初始化访问标识数组*/voidcreateGraph(graph*g)/*建立一个无向图的邻接矩阵*/{inti,j;charv;g->vexnum=0;g->arcnum=0;i=0;printf("输入顶点序列(以#结束)：\n");while((v=getchar())!='#')专业知识整理分享WORD格式可编辑{g->vexs[i]=v;/*读入顶点信息*/i++;}g->vexnum=i;/*顶点数目*/for(i=0;i<g->vexnum;i++)/*邻接矩阵初始化*/for(j=0;j<g->vexnum;j++)g->arcs[i][j]=0;printf("输入边的信息：\n");scanf("%d,%d",&i,&j);/*读入边i,j*/while(i!=-1)/*读入i,j为－1时结束*/{g->arcs[i][j]=1;g->arcs[j][i]=1;scanf("%d,%d",&i,&j);}}voiddfs(inti,graph*g)/*从第i个顶点出发深度优先搜索*/{intj;printf("%c",g->vexs[i]);visited[i]=TRUE;for(j=0;j<g->vexnum;j++)if((g->arcs[i][j]==1)&&(!visited[j]))dfs(j,g);}voidtdfs(graph*g)/*深度优先搜索整个图*/{inti;printf("\n从顶点%C开始深度优先搜索序列：for(i=0;i<g->vexnum;i++)if(visited[i]!=TRUE)dfs(i,g);",g->vexs[0]);}voidbfs(intk,graph*g)/*从第k个顶点广度优先搜索*/{inti,j;queueqlist,*q;q=&qlist;q->rear=0;q->front=0;专业知识整理分享WORD格式可编辑printf("%c",g->vexs[k]);visited[k]=TRUE;q->data[q->rear]=k;q->rear=(q->rear+1)%N;while(q->rear!=q->front){i=q->data[q->front];q->front=(q->front+1)%N;for(j=0;j<g->vexnum;j++)if((g->arcs[i][j]==1)&&(!visited[j])){printf("%c",g->vexs[j]);visited[j]=TRUE;q->data[q->rear]=j;q->rear=(q->rear+1)%N;}}}voidtbfs(graph*g)/*广度优先搜索整个图*/{inti;printf("\n从顶点%C开始广度优先搜索for(i=0;i<g->vexnum;i++)if(visited[i]!=TRUE)bfs(i,g);序列：",g->vexs[0]);}voidinit_visit()/*初始化访问标识数组*/{inti;for(i=0;i<N;i++)visited[i]=FALSE;}intmain(){graphga;inti,j;createGraph(&ga);printf("无向图的邻接矩阵：\n");for(i=0;i<ga.vexnum;i++){for(j=0;j<ga.vexnum;j++)专业知识整理分享WORD格式可编辑printf("%3d",ga.arcs[i][j]);printf("\n");}init_visit();tdfs(&ga);init_visit();tbfs(&ga);return0;}▪根据右图的结构验证实验，输入：ABCDEFGH#0,10,20,51,31,42,52,63,74,7-1,-1▪运行结果：专业知识整理分享WORD格式可编辑2、阅读并运行下面程序，补充拓扑排序算法。#include<stdio.h>#include<malloc.h>#defineN20typedefstructedgenode{/*图的邻接表：邻接链表结点*/intadjvex;/*顶点序号*/structedgenode*next;/*下一个结点的指针*/}edgenode;typedefstructvnode{/*图的邻接表：邻接表*/chardata;/*顶点信息*/intind;/*顶点入度*/structedgenode*link;/*指向邻接链表指针*/}vnode;voidcreateGraph_list(vnodeadjlist[],int*p)；/*建立有向图的邻接表*/voidtopSort(vnodeg[],intn)；/*拓扑排序*/voidcreateGraph_list(vnodeadjlist[],int*p){/*建立有向图的邻接表*/inti,j,n,e;charv;edgenode*s;i=0;n=0;e=0;专业知识整理分享WORD格式可编辑printf("输入顶点序列(以#结束)：\n");while((v=getchar())!='#'){adjlist[i].data=v;/*读入顶点信息*/adjlist[i].link=NULL;adjlist[i].ind=0;i++;}n=i;*p=n;/*建立邻接链表*/printf("\n请输入弧的信息(i=-1结束)：i,j:\n");scanf("%d,%d",&i,&j);while(i!=-1){s=(structedgenode*)malloc(sizeof(edgenode));s->adjvex=j;s->next=adjlist[i].link;adjlist[i].link=s;adjlist[j].ind++;/*顶点j的入度加1*/e++;scanf("%d,%d",&i,&j);}printf("邻接表:");for(i=0;i<n;i++){/*输出邻接表*/printf("\n%c,%d:",adjlist[i].data,adjlist[i].ind);s=adjlist[i].link;while(s!=NULL){printf("->%d",s->adjvex);s=s->next;}}}voidtopSort(vnodeg[],intn){/*拓扑排序*/voidtopSort(vnodeg[],intn){/*拓扑排序*/intTopoSort(AdjListG){StackS;intindegree[MAX_VERTEX_NUM];inti,count,k;AreNode*p;FindID(G,indegree);InitStack(&s);专业知识整理分享WORD格式可编辑for(i=0;i<G.vexnum;i++)if(indegree[i]==0)Push(&s,i)count=0;while(!IsEmpty(s)){Pap(&s,&i);}intmain(){vnodeadjlist[N];intn,*p;p=&n;createGraph_list(adjlist,p);return0;}▪根据输入，输出有向图的拓扑排序序列。并画出有向图。输入:ABCDEF#0,11,22,34,14,5-1,-1▪运行结果：专业知识整理分享WORD格式可编辑3、阅读并运行下面程序。#include<stdio.h>#defineN20#defineTRUE1#defineINF32766/*邻接矩阵中的无穷大元素*/#defineINFIN32767/*比无穷大元素大的数*/typedefstruct{/*图的邻接矩阵*/intvexnum,arcnum;charvexs[N];intarcs[N][N];}graph;voidcreateGraph_w(graph*g,intflag);voidprim(graph*g,intu);voiddijkstra(graphg,intv);voidshowprim();voidshowdij();/*建带权图的邻接矩阵,若flag为1则为无向图，flag为0为有向图*/voidcreateGraph_w(graph*g,intflag){inti,j,w;charv;g->vexnum=0;g->arcnum=0;i=0;printf("输入顶点序列(以#结束)：\n");while((v=getchar())!='#'){g->vexs[i]=v;/*读入顶点信息*/i++;}g->vexnum=i;for(i=0;i<6;i++)/*邻接矩阵初始化*/for(j=0;j<6;j++)g->arcs[i][j]=INF;printf("输入边的信息：\n");scanf("%d,%d,%d",&i,&j,&w);/*读入边(i,j,w)*/while(i!=-1)/*读入i为－1时结束*/{g->arcs[i][j]=w;专业知识整理分享WORD格式可编辑if(flag==1)g->arcs[j][i]=w;scanf("%d,%d,%d",&i,&j,&w);}}voidprim(graph*g,intu)/*出发顶点u*/{intlowcost[N],closest[N],i,j,k,min;for(i=0;i<g->vexnum;i++)/*求其他顶点到出发顶点u的权*/{lowcost[i]=g->arcs[u][i];closest[i]=u;}lowcost[u]=0;for(i=1;i<g->vexnum;i++)/*循环求最小生成树中的各条边*/{min=INFIN;for(j=0;j<g->vexnum;j++)/*选择得到一条代价最小的边*/if(lowcost[j]!=0&&lowcost[j]<min){min=lowcost[j];k=j;}printf("(%c,%c)--%d\n",g->vexs[closest[k]],g->vexs[k],lowcost[k]);/*输出该边*/lowcost[k]=0;/*顶点k纳入最小生成树*/for(j=0;j<g->vexnum;j++)/*求其他顶点到顶点k的权*/if(g->arcs[k][j]!=0&&g->arcs[k][j]<lowcost[j]){lowcost[j]=g->arcs[k][j];closest[j]=k;}}}voiddijkstra(graphg,intv){/*dijkstra算法求单源最短路径*/intpath[N][N],dist[N],s[N];intmindis,i,j,u,k;for(i=0;i<g.vexnum;i++){dist[i]=g.arcs[v][i];s[i]=0;for(j=0;j<g.vexnum;j++)path[i][j]=0;if(dist[i]<INF){专业知识整理分享WORD格式可编辑path[i][v]=1;path[i][i]=1;}}dist[v]=0;s[v]=1;for(i=0,u=1;i<g.vexnum;i++){mindis=INFIN;for(j=0;j<g.vexnum;j++)if(s[j]==0)if(dist[j]<mindis){u=j;mindis=dist[j];}s[u]=1;for(j=0;j<g.vexnum;j++)if((s[j]==0)&&dist[u]+g.arcs[u][j]<dist[j]){dist[j]=dist[u]+g.arcs[u][j];for(k=0;k<g.vexnum;k++)path[j][k]=path[u][k];