数据结构实验教学手册

《数据结构》课程实验教学手册姓 名： 王俊东学 号： 1101120216专 业： 计算机科学与技术班 级： 2012 级 2 班任课教师： 王爽时 间：2013-2014年度第1学期综合成绩：计算机科学与技术学院《数据结构》课程组实验手册使用及要求实验操作是教学过程中理论联系实际的重要环节，而实验报告的撰写又是知识系统化的吸收和升华过程，因此，实验报告应该体现完整性、规性、正确性、有效性。现将实验报告撰写的有关容说明如下：1、实验预习报告必须在实验前完成。2、实验时带好实验手册方可进行实验。3、实验时按实验预习报告容进行实验。并如实填写实验过程及实验小结。4、实验结束后填写通过后的源程序。通过后的源程序可以手写也可以打印粘贴。实验情况一览表实验序号实验名称实验性质学时实验一顺序表及其应用验证性实验2实验二单链表及其应用综合性试验4实验三线性表综合练习设计性试验6实验四栈和队列及其应用设计性试验4实验五二叉树及其应用设计性试验6实验六图及其应用设计性试验6实验七查找设计性试验4实验八排序设计性试验4实验一实验名称 顺序表及其应用 实验性质 验证性 实验学时数 2学时一、实验目的1．深入了解线性表的顺序存储结构。2．熟练掌握在顺序存储结构上进行插入、删除等操作的算法。3．通过线性表结构解决现实中的一些问题。二、实验容线性表的顺序存储结构。顺序存储结构上进行插入、删除等操作的算法。通过线性表结构解决现实中的一些问题。三

1、实验题目[问题描述]设计一个顺序表，要求：（1）包含不少于5个元素，并在屏幕上显示。（2）对建好的顺序表实现查找、插入、删除等操作，并程序执行结果显示到屏幕上。（3）设计一个选择菜单。[基本要求]（1）按实验容编写完整的程序，并上机验证。实（2）实验完成后，提交电子档教师验收程序，并提交填写好的实验报告。验[测试数据]过

由学生依据软件工程的测试技术自己确定。注意测试边界数据。2、源程序程#include"stdio.h"#include"malloc.h"#defineMAXSIZE200 //线性表允许的最大长度#definedatatypeinttypedefstruct{ //定义线性表的结构datatypedata[MAXSIZE];//表示线性表（a1，a2，....,an）intlast;//last表示线性表的实际长度}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("表已满无法插入！");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() //主函数voidmain(){SeqListL;inti,choice;init_SeqList(&L);printf("请输入线性表的长度:");scanf("%d",&L.last);printf("请输入线性表的元素:");for(i=0;i<L.last;i++)scanf("%d",&L.data[i]);do{printf("请选择您想要对线性表的操作 :1:插入2:删除3:查找 4:打印0:退出\n");scanf("%d",&choice);switch(choice){case1:intx,j;printf("请输入要插入的数的位置和数值： ");scanf("%d%d",&j,&x);insert_SeqList(&L,j,x);break;case2:intm;printf("请输入要删除的数的位置 :");scanf("%d",&m);Delete_SeqList(&L,m);break;case3:intn;printf("请输入要查找的数：");scanf("%d",&n);printf("您要查找的数位于线性表的第 %d位.\n",Location_SeqList(&L,n));break;case4:print(&L);break;case0:break;default:printf("请选择正确的操作！\n");break;}}while(choice!=0);printf("谢谢使用!\n");return0;}四实初步了解线性表的顺序存储结构，及其定义格式。验掌握在顺序表上进行插入、删除等操作的算法。小 但在顺序表的操作上不是十分熟练。结五成绩实验二实验名称 单链表及其应用 实验性质 综合性 实验学时数 4学时一、实验目的1．深入了解线性表的链式存储结构。2．熟练掌握在链式存储结构上进行插入、删除等操作的算法。3．通过线性表结构解决现实中的一些问题。二、实验容线性表的链式存储结构。链式存储结构上进行插入、删除等操作的算法。通过线性表结构解决现实中的一些问题。1、实验题目[问题描述]（1）用头插法或尾插法建立一个单链表，并将结果显示到屏幕上。（2）对建好的单链表实现查找、插入、删除、修改等操作。（3）设计一个选择菜单。[基本要求]（1）按实验容编写完整的程序，并上机验证。（2）实验完成后，提交电子档教师验收程序，并提交填写好的实验报告。[测试数据]由学生依据软件工程的测试技术自己确定。注意测试边界数据。[提高篇]（选作）建立一个有序单链表，实现上述操作。2、源程序#include"stdio.h"#include"malloc.h"typedefstructNode{chardata;structNode*next;}Node,*linklist;voidcreatefromtail(linklistL){Node*r,*s;intflag=1;charc;r=L;printf("请输入线性表的元素以$结束:");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("删除的节点位置不合法！\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("请选择您想要对线性表的操作 :1:插入2:删除3:查找4:修改5：打印0:退出\n");scanf("%d",&choice);switch(choice){case1:charc;printf("请输入要插入的字符的位置： ");scanf("%d",&j);printf("请输入要插入的字符： ");c=getchar();c=getchar();inslist(L,j,c);printf("插入字符后的线性表为： ");print(L);break;case2:intm;printf("请输入要删除的字符的位置 :");scanf("%d",&m);deilist(L,m);printf("删除字符后的线性表为： ");print(L);break;case3:intn;printf("请输入要查找的字符的位置： ");scanf("%d",&n);printf("您要查找的字符为%c.\n",get(L,n));break;case4:inta;charx;printf("请输入要修改的字符的位置 :");scanf("%d",&a);printf("请输入要修改的字符:");x=getchar();x=getchar();alterlist(L,a,x);printf("修改字符后的线性表为： ");print(L);break;case5:print(L);case0:break;default:printf("请选择正确的操作！\n");break;}}while(choice!=0);printf("谢谢使用!\n");return0;}四 初步了解线性表的链式存储结构，及其定义格式。实 掌握了在链表上进行插入、删除等操作的算法。验 对链表的了解不是很深入，在其使用上往往会犯一些错误比如在链表小中进行插入插不到指定位置，删除时位置错误等。结五成绩实验三实验名称 线性表综合练习 实验性质 设计性 实验学时数 6学时一、实验目的1．根据实际问题，应用线性表的顺序存储结构。2．根据实际问题，深入理解线性表的链式存储结构。3．通过线性表结构解决现实中的一些问题。二、实验容线性表的两种存储结构。不同存储结构上进行插入、删除等操作的算法。通过线性表结构解决现实中的一些问题。1、实验题目[问题描述]、设计一个学生信息系统，要求：实（1）每条信息包含学号，姓名，性别，院系，宿舍等项。验（2）能够对数据信息进行查找，插入，删除等。过（3）选择合适的存储结构，在主程序上运行，验证其正确性，并写出程序执行程结果。[基本要求]（1）按实验容编写完整的程序，并上机验证。（2）实验完成后，提交电子档教师验收程序，并提交填写好的实验报告。[测试数据]由学生依据软件工程的测试技术自己确定。注意测试边界数据。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("请输入学生数:");scanf("%d",&n);charnumber[10],name[10],sex[4],department[16],dorm[6];Node*r,*s;r=L;printf("请输入学生的信息!\n");for(i=0;i<n;i++){printf("请输入学生学号：");scanf("%s",number);printf("请输入学生姓名：");scanf("%s",name);printf("请输入学生性别：");scanf("%s",sex);printf("请输入学生院系：");scanf("%s",department);printf("请输入学生宿舍号：");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("请输入插入位置");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("请输入学生学号：");scanf("%s",number);printf("请输入学生姓名：");scanf("%s",name);printf("请输入学生性别：");scanf("%s",sex);printf("请输入学生院系：");scanf("%s",department);printf("请输入学生宿舍号：");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("该学生的信息为：\n");printf("学号：%s",p->number);printf("姓名：%s",p->name);printf("性别：%s",p->sex);printf("学院：%s",p->department);printf("宿舍号：%s",p->dorm);printf("\n");}elsereturn0;}intdeilist(linklistL){Node*pre,*r;intk,i;printf("请输入要删除的字符的位置 :");scanf("%d",&i);pre=L;k=0;while(pre->next!=NULL&&k<i-1){pre=pre->next;k=k+1;}if(!(pre->next)){printf("删除的节点位置不合法！ \n");return0;}r=pre->next;pre->next=r->next;free(r);return1;}voidprint(linklistL){linklistp;p=L->next;while(p){printf("学号：%s",p->number);printf("姓名：%s",p->name);printf("性别：%s",p->sex);printf("学院：%s",p->department);printf("宿舍号：%s",p->dorm);printf("\n");p=p->next;}}intmain(){linklistL;inti,choice,x,j;createfromtail(L);do{printf("请选择您想要对线性表的操作 :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("请输入要查找的学生的位置： ");scanf("%d",&n);get(L,n);break;case4:print(L);break;case0:break;default:printf("请选择正确的操作！\n");break;}}while(choice!=0);printf("谢谢使用!\n");return0;}四 对链式表有了进一步的了解，能够利用链式表解决一些实际问题。实了解了链式表的优势，他不会造成空间的浪费，对于插入和删除操作上链式表比顺序表有验小 明显的优势。结五成绩实验四实验名称 栈和队列及其应用 实验性质 设计性 实验学时数 4学时一、实验目的1．掌握栈与队列的抽象数据类型描述及特点。2．掌握栈和队列的顺序和链式存储结构与基本算法实现。3．掌握栈和队列在实际问题中的应用和基本编程技巧。二、实验容1.栈和队列在不同存储结构上进行插入、删除等操作的算法。2.通过栈或队列解决现实中的一些问题。1、实验题目[问题描述]以下题目根据自己兴趣和能力可选作一道作为实验题目：（1）根据栈的数据结构，建立一个顺序栈和链栈并实现对其基本操作；（2）根据队列的数据结构，建立一个循环队列和链队并实现对其基本操作；（3）根据教材3.4.3节介绍的思想，设计并实现一个对简化表达式求值的系统（4）银行业务队列简单模拟。设某银行有 A、B两个业务窗口，其中 A窗口的处理速度是B窗口的2倍，给定到达银行的顾客序号，请按业务完成的顺序输出顾客序列（假设奇数编号到A窗口办理，偶数编号到B窗口办理，不同窗口同时处理完2个顾客，A窗口优先输出）。[基本要求]（1）按实验容编写完整的程序，并上机验证。（2）实验完成后，提交电子档教师验收程序，并提交填写好的实验报告。[测试数据]由学生依据软件工程的测试技术自己确定。注意测试边界数据。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("请输入你的选择:(1)对顺序栈操作 （2）对链栈操作scanf("%d",&choice);switch(choice){case1:initstack(&s1);do{printf("请输入你的选择:(1)入栈 （2）出栈 （3）打印scanf("%d",&choice1);switch(choice1){case1:

0:退出\n");0:退出\n");printf("请输入入栈元素：");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("请输入你的选择:(1)入栈（2）出栈（3）打印0:退出\n");scanf("%d",&choice2);switch(choice2){case1:printf("请输入入栈元素：");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;}四 对栈和队列有了初步的了解，他们都是一种特殊的操作受限制线性表，栈实 的特点是先进后出而队列的是先进先出。验 在写程序中出现了一些问题，参数传递不匹配，还有一些错误虽然编译通总 过了但执行的时候却错误了，后经调试修改得到是参数传递过程中出现了结 问题。五成绩实验五实验名称 二叉树及其应用 实验性质 设计性 实验学时数 6学时一、实验目的1．掌握二叉树链表的结构和构造过程。2．掌握用递归方法实现二叉树的遍历。3．加强对二叉树的理解，培养解决实际问题的能力。二、实验容用递归方法实现对二叉树的遍历等操作。二叉树的其他操作算法。1、实验题目[问题描述]、以下题目根据自己兴趣和能力可选作二道作为实验题目：实（1）创建一颗二叉树，用递归方法实现对其进行先序、中序和后序遍历的操作；（2）根据题目1，修改其中一个算法，用来计算统计二叉树中叶子节点的个数验和度为1、度为2的节点个数；过（3）设计并实现一个哈夫曼树并对其进行编码。（4）修理牧场。农夫要修理牧场的一段栅栏，发现需要N块木头，每块木头长程度为整数Li个长度单位，于是他购买了一条很长的、能锯成N块的木头，即该木头的长度是Li的总和。但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。简单起见，设酬金等于所锯木头的长度。例如，将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头将木头锯成12和8，花费20；第二次将木头长度为12的木头锯成7和5花费12，总花费为32.如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费35（大于32）。请编写程序帮助农夫计算将木头锯成N块的最少花费。输入数据N表示要将木头锯成N块，然后输入N个整数，表示每段木块的长度。输出将木头锯成N块的最少花费。（可采用哈夫曼算法和最小堆实现）[基本要求]（1）按实验容编写完整的程序，并上机验证。（2）实验完成后，提交电子档教师验收程序，并提交填写好的实验报告。[测试数据]由学生依据软件工程的测试技术自己确定。注意测试边界数据。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);}elseroot=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("请输入字符以.结束:");root=create(root);do{printf("请输入你的选择: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("输入不合法，请重新输入！ \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);}elseroot=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("请输入字符以.结束:");root=create(root);leaf(root);leaf1(root);leaf2(root);printf("叶子节点数为%d.\n",leafcount);printf("度为1的节点数为%d.\n",leafcount1);printf("度为2的节点数为%d.\n",leafcount2);return0;四实验小结五成绩

}了解二叉树链表的结构和构造过程。可以用递归方法实现二叉树的遍历。对二叉树有了进一步的理解能够求出二叉树中叶子节点，度为 1一季度为2的节点的个数实验六实验名称 图及其应用 实验性质 设计性 实验学时数 6学时一、实验目的1．掌握图的存储结构及其实现。2．掌握图的深度和广度遍历算法及其实现。3．掌握图的常见算法的思想及应用。二、实验容实现对无向图的存储和遍历等操作。最小生成树问题。、实验题目[问题描述]以下题目根据自己兴趣和能力可选作一道作为实验题目：（1）使用邻接表或邻接矩阵存储一个无向图，实现对其进行深度和广度遍历的操作；（2）n个城市之间建立通信联络网，最多可能设置 n(n-1)/2条线路，那么，如何在这些可能的线路中选择 n-1条，以使总的耗费最少。使用最小生成树实现解决此问题。[基本要求]实 （1）按实验容编写完整的程序，并上机验证。验 （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("请输入图中顶点个数和边数：");scanf("%d%d",&n,&e);G->vexnum=n;G->arcnum=e;printf("请输入顶点的值：");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("请输入有关联的两个顶点下标： \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,{ 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);

inti)}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("输出关系二维矩阵：");for(i=0;i<g.vexnum;i++){for(j=0;j<g.vexnum;j++)printf("%d",g.arc[i][j].adj);printf("\t");}printf("无向图的遍历：");TraverseGraph(g);printf("\n");return0;}四 了解图的存储结构以及图的深度和广度遍历算法。实 能够使用邻接矩阵存储一个无向图，实现对其进行深度和广度遍历的操作。验总结五成绩实验七实验名称 查 找 实验性质 设计性 实验学时数 4学时一、实验目的1．熟练掌握各种静态查找表方法 (顺序查找、折半查找、索引顺序表等 )；2．熟练掌握二叉排序树的构造方法和查找算法；3．了解和掌握其它查找方法。二、实验容1.实现顺序查找、折半查找等操作。2.二叉排序树和哈希查找的实现。1、实验题目[问题描述]以下题目根据自己兴趣和能力可选作一道作为实验题目：顺序查找、折半查找算法的实现；二叉排序树的构造与查找算法的实现；Hash表的查找算法实现。[基本要求]（1）按实验容编写完整的程序，并上机验证。（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;elselow=mid+1;}return0;}intmain(){intk,k1,x;recordlistl;printf("请输入数据长度：");scanf("%d",&x);printf("请输入%