《数据结构》(C语言版)严蔚敏著-实验指导

v1.0可编辑可修改v1.0可编辑可修改PAGEPAGEPAGE57PAGE57v1.0可编辑可修改PAGE《数据结构》实验指导及报告书/学年第学期姓名：______________学号：______________班级：______________指导教师：______________数学与统计学院2011

预备实验C语言的函数数组指针结构体知识一、实验目的1、复习C语言中函数、数组、指针、结构体与共用体等的概念。2、熟悉利用C语言进行程序设计的一般方法。二、实验预习说明以下C语言中的概念函数：数组：3、指针：4、结构体5、共用体三、实验内容和要求1、调试程序：输出100以内所有的素数（用函数实现）。#include<>intisprime(intn){/*判断一个数是否为素数*/intm; for(m=2;m*m<=n;m++) if(n%m==0)return0; return1;}intmain(){/*输出100以内所有素数*/ inti;printf("\n"); for(i=2;i<100;i++) if(isprime(i)==1)printf("%4d",i); return0;}运行结果：2、调试程序：对一维数组中的元素进行逆序排列。#include<>#defineN10intmain(){ inta[N]={0,1,2,3,4,5,6,7,8,9},i,temp; printf("\ntheoriginalArrayis:\n"); for(i=0;i<N;i++) printf("%4d",a[i]); for(i=0;i<N/2;i++){ /*交换数组元素使之逆序*/ temp=a[i]; 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<>#defineM3#defineN4intmain(){ inta[M][N],i,j,k; printf("\n请输入二维数组的数据：\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;}运行结果：4、调试程序：利用指针输出二维数组的元素。#include<>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、调试程序：设有一个教师与学生通用的表格，教师的数据有姓名、年龄、职业、教研室四项，学生有姓名、年龄、专业、班级四项，编程输入人员的数据，再以表格输出。#include<>#defineN10structstudent{ charname[8]; /*姓名*/ intage; /*年龄*/ charjob; /*职业或专业，用s或t表示学生或教师*/ union{intclass; /*班级*/charoffice[10];/*教研室*/}depa;}stu[N];intmain(){ inti;intn;printf(“\n请输入人员数(<10):\n”);scanf(“%d”,&n); for(i=0;i<n;i++){ /*输入n个人员的信息*/ printf("\n请输入第%d人员的信息：(nameagejobclass/office)\n",i+1); scanf("%s,%d,%c",stu[i].name,&stu[i].age,&stu[i].job); if(stu[i].job==’s’) scanf("%d",&stu[i].;elsescanf("%s",stu[i].; } printf(“nameagejobclass/office”); for(i=0;i<n;i++){ /*输出*/ if(stu[i].job==’s’) printf("%s%3d%3c%d\n",stu[i].name,stu[i].age,stu[i].job,stu[i].;else printf("%s%3d%3c%s\n",stu[i].name,stu[i].age,stu[i].job,stu[i].; }}输入的数据：2Wang19s99061Li36tcomputer运行结果：四、实验小结五、教师评语

实验一顺序表与链表一、实验目的1、掌握线性表中元素的前驱、后续的概念。2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。3、对线性表相应算法的时间复杂度进行分析。4、理解顺序表、链表数据结构的特点（优缺点）。二、实验预习说明以下概念1、线性表：2、顺序表：3、链表：三、实验内容和要求1、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。#include<>#include<>#defineERROR0#defineOK1#defineINIT_SIZE5/*初始分配的顺序表长度*/#defineINCREM5/*溢出时，顺序表长度的增量*/typedefintElemType;/*定义表元素的类型*/typedefstructSqlist{ ElemType*slist;/*存储空间的基地址*/ intlength;/*顺序表的当前长度*/ intlistsize;/*当前分配的存储空间*/}Sqlist;intInitList_sq(Sqlist*L);/**/intCreateList_sq(Sqlist*L,intn);/**/intListInsert_sq(Sqlist*L,inti,ElemTypee);/**/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){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]=L->slist[k];}L->slist[i-1]=e;L->length++;returnOK;}/*ListInsert*//*在顺序表中删除第i个元素*/intListDelete_sq(Sqlist*L,inti){}/*在顺序表中查找指定值元素，返回其序号*/intListLocate(Sqlist*L,ElemTypee){}intmain(){Sqlistsl;intn,m,k;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);printf("\npleaseinputinsertlocationanddata:(location,data)\n"); scanf("%d,%d",&m,&k); ListInsert_sq(&sl,m,k); printf("\n3-PrintSqlist:\n"); PrintList_sq(&sl); printf("\n");}elseprintf("ERROR");return0;}运行结果算法分析2、为第1题补充删除和查找功能函数，并在主函数中补充代码验证算法的正确性。删除算法代码：运行结果算法分析查找算法代码：运行结果算法分析3、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。#include<>#include<>#defineERROR0#defineOK1typedefintElemType;/*定义表元素的类型*/typedefstructLNode{/*线性表的单链表存储*/ElemTypedata;structLNode*next;}LNode,*LinkList;LinkListCreateList(intn);/**/voidPrintList(LinkListL);/*输出带头结点单链表的所有元素*/intGetElem(LinkListL,inti,ElemType*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:");/*输入单链表的元素个数*/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;}运行结果算法分析4、为第3题补充插入功能函数和删除功能函数。并在主函数中补充代码验证算法的正确性。插入算法代码：运行结果算法分析删除算法代码：运行结果算法分析以下为选做实验：5、循环链表的应用（约瑟夫回环问题）n个数据元素构成一个环，从环中任意位置开始计数，计到m将该元素从表中取出，重复上述过程，直至表中只剩下一个元素。提示：用一个无头结点的循环单链表来实现n个元素的存储。算法代码6、设一带头结点的单链表，设计算法将表中值相同的元素仅保留一个结点。提示：指针p从链表的第一个元素开始，利用指针q从指针p位置开始向后搜索整个链表，删除与之值相同的元素；指针p继续指向下一个元素，开始下一轮的删除，直至p＝＝null为至，既完成了对整个链表元素的删除相同值。算法代码四、实验小结五、教师评语

实验二栈和队列一、实验目的1、掌握栈的结构特性及其入栈，出栈操作；2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。二、实验预习说明以下概念1、顺序栈：2、链栈：3、循环队列：4、链队三、实验内容和要求1、阅读下面程序，将函数Push和函数Pop补充完整。要求输入元素序列12345e，运行结果如下所示。#include<>#include<>#defineERROR0#defineOK1#defineSTACK_INT_SIZE10/*存储空间初始分配量*/#defineSTACKINCREMENT5/*存储空间分配增量*/typedefintElemType;/*定义元素的类型*/typedefstruct{ElemType*base;ElemType*top;intstacksize;/*当前已分配的存储空间*/}SqStack;intInitStack(SqStack*S);/*构造空栈*/intpush(SqStack*S,ElemTypee);/*入栈*/intPop(SqStack*S,ElemType*e);/*出栈*/intCreateStack(SqStack*S);/*创建栈*/voidPrintStack(SqStack*S);/*出栈并输出栈中元素*/intInitStack(SqStack*S){S->base=(ElemType*)malloc(STACK_INT_SIZE*sizeof(ElemType));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体现了栈的什么特性2、在第1题的程序中，编写一个十进制转换为二进制的数制转换算法函数（要求利用栈来实现），并验证其正确性。实现代码验证3、阅读并运行程序，并分析程序功能。#include<>#include<>#include<>#defineM20#defineelemtypechartypedefstruct{elemtypestack[M];inttop;}stacknode;voidinit(stacknode*st);voidpush(stacknode*st,elemtypex);voidpop(stacknode*st);voidinit(stacknode*st){st->top=0;}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){if(st->top>0)st->top--;elseprintf(“StackisEmpty!\n”);}intmain(){chars[M];inti;stacknode*sp;printf("createaemptystack!\n");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运行结果：输入：a-((c-d)*6-(s/3-x)/2运行结果：程序的基本功能：以下为选做实验：4、设计算法，将一个表达式转换为后缀表达式，并按照后缀表达式进行计算，得出表达式得结果。实现代码5、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点（不设队头指针），试编写相应的置空队列、入队列、出队列的算法。实现代码：四、实验小结五、教师评语

实验三串的模式匹配一、实验目的1、了解串的基本概念2、掌握串的模式匹配算法的实现二、实验预习说明以下概念1、模式匹配：2、BF算法：3、KMP算法：三、实验内容和要求1、阅读并运行下面程序，根据输入写出运行结果。#include<>#include<>#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<s2->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;=strlen;printf("inputstrings2:");gets;=strlen;if((k=strCompare(&s1,&s2))==0)printf("s1=s2\n");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;=strlen;printf("inputstart:");scanf("%d",&start);printf("inputsublen:");scanf("%d",&sublen);strSub(&s,start,sublen,&sub);if==0)printf("ERROR!\n");else{printf("subStringis:");for(i=0;i<sublen;i++)printf("%c",[i]);}printf("\n***showover***\n");}intmain(){intn;do{printf("\nString\n");printf("1.strCompare\n");printf("2.subString\n");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运行结果：2、实现串的模式匹配算法。补充下面程序，实现串的BF和KMP算法。#include<>#include<>#defineMAXSIZE100typedefstruct{ chardata[MAXSIZE]; 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){补充代码}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; }else j=next[j];}}intindex_kmp(SqString*s,SqString*t,intstart,intnext[]){ 补充代码}voidshow_index(){SqStrings,t;intk,next[MAXSIZE]={0},i;printf("\n***showindex***\n");printf("inputstrings:");gets;=strlen;printf("inputstringt:");gets;=strlen;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<;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;}输入：abcaabbabcabaacbacbaabcabaa1运行结果：四、实验小结五、教师评语

实验四二叉树一、实验目的1、掌握二叉树的基本特性2、掌握二叉树的先序、中序、后序的递归遍历算法3、理解二叉树的先序、中序、后序的非递归遍历算法4、通过求二叉树的深度、叶子结点数和层序遍历等算法，理解二叉树的基本特性二、实验预习说明以下概念1、二叉树：2、递归遍历：非递归遍历：4、层序遍历：三、实验内容和要求1、阅读并运行下面程序，根据输入写出运行结果，并画出二叉树的形态。#include<>#include<>#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){ 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:");PostOrder(t);printf("\n\n先序遍历序列（非递归）:");Preorder_n(t);release(t);return0;}运行程序输入：ABC##DE#G##F###运行结果：2、在上题中补充求二叉树中求结点总数算法（提示：可在某种遍历过程中统计遍历的结点数），并在主函数中补充相应的调用验证正确性。算法代码：3、在上题中补充求二叉树中求叶子结点总数算法（提示：可在某种遍历过程中统计遍历的叶子结点数），并在主函数中补充相应的调用验证正确性。算法代码：4、在上题中补充求二叉树深度算法，并在主函数中补充相应的调用验证正确性。算法代码：选做实验：（代码可另附纸）补充二叉树层次遍历算法。（提示：利用队列实现）5、补充二叉树中序、后序非递归算法。四、实验小结五、教师评语

实验五图的表示与遍历一、实验目的1、掌握图的邻接矩阵和邻接表表示2、掌握图的深度优先和广度优先搜索方法3、理解图的应用方法二、实验预习说明以下概念1、深度优先搜索遍历：2、广度优先搜索遍历：3、拓扑排序：4、最小生成树：5、最短路径：三、实验内容和要求1、阅读并运行下面程序，根据输入写出运行结果。#include<>#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())!='#'){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开始深度优先搜索序列：",g->vexs[0]);for(i=0;i<g->vexnum;i++)if(visited[i]!=TRUE)dfs(i,g);}voidbfs(intk,graph*g)/*从第k个顶点广度优先搜索*/{inti,j;queueqlist,*q;q=&qlist;q->rear=0;q->front=0;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开始广度优先搜索序列：",g->vexs[0]);for(i=0;i<g->vexnum;i++)if(visited[i]!=TRUE)bfs(i,g);}voidinit_visit()/*初始化访问标识数组*/{inti;for(i=0;i<N;i++)visited[i]=FALSE;}intmain(){graphga;inti,j;createGraph(&ga);printf("无向图的邻接矩阵：\n");for(i=0;i<;i++){for(j=0;j<;j++)printf("%3d",[i][j]);printf("\n");}init_visit();tdfs(&ga);init_visit();tbfs(&ga);return0;}根据右图的结构验证实验，输入：ABCDEFGH#ABABCDEFGH012345670,20,51,31,42,52,63,74,7-1,-1运行结果：2、阅读并运行下面程序，补充拓扑排序算法。#include<>#include<>#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;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){/*拓扑排序*/}intmain(){vnodeadjlist[N];intn,*p;p=&n;createGraph_list(adjlist,p);return0;}根据输入，输出有向图的拓扑排序序列。并画出有向图。输入:ABCDEF#0,11,22,34,14,5-1,-1运行结果：3、阅读并运行下面程序。#include<>#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;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;}}}voidprintPath(graphg,intstartVex,intEndVex){intstack[N],top=0;/*堆栈*/inti,k,j;intflag[N];/*输出路径顶点标志*/k=EndVex;for(i=0;i<;i++)flag[i]=0;j=startVex;printf("%c",[j]);flag[j]=1;stack[top++]=k;while(top>0)/*找j到k的路径*/{for(i=0;i<;i++){if(path[k][i]==1&&flag[i]==0)/*j到k的路径含有i顶点*/{if[j][i]!=INF)/*j到i的路径含有中间顶点*/{printf("->%c(%d)",[i],[j][i]);/*输出j到k的路径的顶点i*/flag[i]=1;j=i;k=stack[--top];break;}else{if(i!=k)stack[top++]=i;/*break;*/}}}}voiddijkstra(graphg,intv){/*dijkstra算法求单源最短路径*/intpath[N][N],dist[N],s[N];intmindis,i,j,u,k;for(i=0;i<;i++){dist[i]=[v][i];s[i]=0;for(j=0;j<;j++)path[i][j]=0;if(dist[i]<INF){path[i][v]=1;path[i][i]=1;}}dist[v]=0;s[v]=1;for(i=0,u=1;i<;i++){mindis=INFIN;for(j=0;j<;j++)if(s[j]==0)if(dist[j]<mindis){u=j;mindis=dist[j];}s[u]=1;for(j=0;j<;j++)if((s[j]==0)&&dist[u]+[u][j]<dist[j]){dist[j]=dist[u]+[u][j];for(k=0;k<;k++)path[j][k]=path[u][k];path[j][j]=1;}}printf("\n顶点%c->到各顶点的最短路径\n",[v]);for(i=0;i<;i++){printf("\n顶点%c->顶点%c：",[v],[i]);if(dist[i]==INF||dist[i]==0)printf("无路径");else{printf("%d",dist[i]);printf("经过顶点：");printPath(g,v,i);/*输出v到i的路径*/}}}voidshowprim()/*最小生成树prim算法演示*/{graphga;createGraph_w(&ga,1);prim(&ga,0);}voidshowdij(){/*dijstra算法演示*/graphga;createGraph_w(&ga,0);dijkstra(ga,0);}intmain(){showprim();/*prim算法演示*/getchar();showdij();/*dijstra算法演示*/return0;}下面的输入分别验证prim算法和dijstra算法。输入实例的第一部分为无向图，求其最小生成树；输入的第二部分为有向图，求其最短路径。最小生成树最短路径ABCDEF#0,1,60,2,10,3,51,2,51,4,32,3,52,4,62,5,43,5,24,5,6-1,-1,-1ABCDEF#0,2,100,5,1000,4,301,2,52,3,503,4,203,5,104,3,204,5,60-1,-1,-1PAGEPAGE73运行结果：（并画出两个图）最小生成树最短路径四、实验小结五、教师评语

实验六查找一、实验目的1、掌握查找表、动态查找表、静态查找表和平均查找长度的概念。2、掌握线性表中顺序查找和折半查找的方法。3、学会哈希函数的构造方法，处理冲突的机制以及哈希表的查找。二、实验预习说明以下概念1、顺序查找：2、折半查找：3、哈希函数：4、冲突及处理：三、实验内容和要求1.静态查找表技术依据顺序查找算法和折半查找算法的特点，对下面的两个查找表选择一个合适的算法，设计出完整的C源程序。并完成问题：查找表1：{8，15，19，26，33，41，47，52，64，90}，查找key=41查找表2：{12，76，29，15，62，35，33，89，48，20}，查找key=35查找key=41的算法：比较次数：查找key=35的算法：比较次数：顺序查找算法算法实现代码折半查找算法算法实现代码2、哈希表的构造与查找/*采用开放地址法构造哈希表*/#include<>#include<>#defineMAXSIZE25#defineP13#defineOK1#defineERROR0#defineDUPLICATE-1#defineTRUE1#defineFALSE0typedefstruct{/*哈希表元素结构*/intkey;/*关键字值*/intflag;/*是否存放元素*/}ElemType;typedefstruct{ElemTypedata[MAXSIZE];intcount;/*元素个数*/intsizeindex;/*当前哈希表容量*/}HashTable;intd1[15]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14};/*线性探测序列*/intd2[15]={0,1,-1,2*2,-2*2,3*3,-3*3,4*4,-4*4,5*5,-5*5,6*6,-6*6,7*7,-7*7};/*二次探测序列*/voiddataset(intds[],int*len);intInsertHash(HashTable*H,inte,intd[]);intCreateHash(HashTable*H,intds[],intlen,intd[]);intSearchHash(HashTable*H,inte,intd[]);voidmenu();/*输入查找表*/voiddataset(intds[],int*len){intn,m;n=0;printf("\n查找表输入：");while(scanf("%d",&m)==1){/*以输入一个非整数作为结束*/ds[n]=m;n++;}*len=n;}/*计算哈希地址，插入哈希表*/intInsertHash(HashTable*H,inte,intd[]){intk,i=1;k=e%P;while(H->data[k].flag==TRUE||k<0){k=(e%P+d[i])%MAXSIZE;i++;if(i>=15)returnERROR;}H->data[k].key=e;H->data[k].flag=TRUE;H->count++;returnOK;}/*构造哈希表*/intCreateHash(HashTable*H,intds[],intlen,intd[]){inti;for(i=0;i<len;i++){if(SearchHash(H,ds[i],d)!=-1)returnDUPLICATE;InsertHash(H,ds[i],d);if(H->count>=MAXSIZE)returnERROR;}returnOK;}/*初始化哈希表*/voidInitHash(HashTable*H){inti;for(i=0;i<MAXSIZE;i++){H->data[i].key=0;H->data[i].flag=FALSE;}}/*在哈希表中查找*/intSearchHash(HashTable*H,inte,intd[]){intk,i=1;k=e%P;while(H->data[k].key!=e){k=(e%P+d[i])%MAXSIZE;i++;if(i>=15)return-1;}returnk;}/*演示菜单*/voidmenu(){intchoice;int*p;HashTableh;=0;=MAXSIZE;inta[MAXSIZE]={0};inti,n,e;dataset(a,&n);/*建立查找表*/getchar();printf("\n");do{printf("\n哈希查找演示\n");printf("\n1.线性探测构造哈希表\n");printf("\n2.二分探测构造哈希表\n");printf("\n3.退出\n");printf("\n输入选择：");scanf("%d",&choice);if(choice==1)p=d1;elseif(choice==2)p=d2;elsereturn;InitHash(&h);/*初始化哈希表*/if(!(i=CreateHash(&h,a,n,p)))/*构造哈希表*/printf("\n哈希表构造失败！\n");elseif(i==DUPLICATE)printf("\n哈希表具有重复关键字！\n");else{printf("\n哈希表：\n");for(i=0;i<;i++)printf("%3d",[i].key);printf("\n\n哈希查找\n输入要查找的key值：");getchar();