数据结构实验报告
一．题目要求
1）编程实现二叉排序树，包括生成、插入，删除；
2）对二叉排序树进行先根、中根、和后根非递归遍历；
3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。
4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么?
二．解决方案
对于前三个题目要求，我们用一个程序实现代码如下
#include
#include
#include
#include "Stack.h"//栈的头文件，没有用上
typedefintElemType; //数据类型
typedefint Status; //返回值类型
//定义二叉树结构
typedefstructBiTNode{
ElemType data; //数据域
structBiTNode *lChild, *rChild;//左右子树域
}BiTNode, *BiTree;
intInsertBST(BiTree&T,int key){//插入二叉树函数
if(T==NULL)
{
T = (BiTree)malloc(sizeof(BiTNode));
T->data=key;
T->lChild=T->rChild=NULL;
return 1;
}
else if(key
InsertBST(T->lChild,key);
}
else if(key>T->data){
InsertBST(T->rChild,key);
}
else
return 0;
}
BiTreeCreateBST(int a[],int n){//创建二叉树函数
BiTreebst=NULL;
inti=0;
while(i InsertBST(bst,a[i]); i++; } returnbst; } int Delete(BiTree&T) { BiTreeq,s; if(!(T)->rChild){ //右子树为空重接它的左子树 q=T; T=(T)->lChild; free(q); }else{ if(!(T)->lChild){ //若左子树空则重新接它的右子树q=T; T=(T)->rChild; }else{ q=T; s=(T)->lChild; while(s->rChild){ q=s; s=s->rChild; } (T)->data=s->data; //s指向被删除结点的前驱 if(q!=T) q->rChild=s->lChild; else q->lChild=s->lChild; free(s); } } return 1; } //删除函数，在T中删除key元素 intDeleteBST(BiTree&T,int key){ if(!T) return 0; else{ if(key==(T)->data) return Delete(T); else{ if(key<(T)->data) returnDeleteBST(T->lChild,key); else returnDeleteBST(T->rChild,key); } } } intPosttreeDepth(BiTree T){//求深度 inthr,hl,max; if(!T==NULL){ hl=PosttreeDepth(T->lChild); hr=PosttreeDepth(T->rChild); max=hl>hr?hl:hr; return max+1; } else return 0; } void printtree(BiTreeT,intnlayer){//打印二叉树 if(T==NULL) return ; printtree(T->rChild,nlayer+1); for(inti=0;i printf(" "); } printf("%d\n",T->data); printtree(T->lChild,nlayer+1); } void PreOrderNoRec(BiTree root)//先序非递归遍历{ BiTree p=root; BiTreestack[50]; intnum=0; while(NULL!=p||num>0) { while(NULL!=p) { printf("%d ",p->data); stack[num++]=p; p=p->lChild; } num--; p=stack[num]; p=p->rChild; } printf("\n"); } void InOrderNoRec(BiTree root)//中序非递归遍历{ BiTree p=root; intnum=0; BiTreestack[50]; while(NULL!=p||num>0) { while(NULL!=p) { stack[num++]=p; p=p->lChild; } num--; p=stack[num]; printf("%d ",p->data); p=p->rChild; } printf("\n"); } void PostOrderNoRec(BiTree root)//后序非递归遍历{ BiTree p=root; BiTreestack[50]; intnum=0; BiTreehave_visited=NULL; while(NULL!=p||num>0) { while(NULL!=p) { stack[num++]=p; p=p->lChild; } p=stack[num-1]; if(NULL==p->rChild||have_visited==p->rChild) { printf("%d ",p->data); num--; have_visited=p; p=NULL; } else { p=p->rChild; } } printf("\n"); } int main(){//主函数 printf(" ---------------------二叉排序树的实现-------------------"); printf("\n"); int layer; inti; intnum; printf("输入节点个数:"); scanf("%d",&num); printf("依次输入这些整数（要不相等）"); int *arr=(int*)malloc(num*sizeof(int)); for(i=0;i scanf("%d",arr+i); } BiTreebst=CreateBST(arr,num); printf("\n"); printf("二叉树创建成功!"); printf("\n"); layer=PosttreeDepth(bst); printf("树状图为:\n"); printtree(bst,layer); int j; int T; int K; for(;;){ loop: printf("\n"); printf(" ***********************按提示输入操作符************************:"); printf("\n"); printf(" 1:插入节点2:删除节点3:打印二叉树4:非递归遍历二叉树5:退出"); scanf("%d",&j); switch(j){ case 1: printf("输入要插入的节点:"); scanf("%d",&T); InsertBST(bst,T); printf("插入成功!"); printf("树状图为:\n"); printtree(bst,layer); break; case 2: printf("输入要删除的节点"); scanf("%d",&K); DeleteBST(bst,K); printf("删除成功!"); printf("树状图为:\n"); printtree(bst,layer); break; case 3: layer=PosttreeDepth(bst); printtree(bst,layer); break; case 4: printf("非递归遍历二叉树"); printf("先序遍历:\n"); PreOrderNoRec(bst); printf("中序遍历:\n"); InOrderNoRec(bst); printf("后序遍历:\n"); PostOrderNoRec(bst); printf("树状图为:\n"); printtree(bst,layer); break; case 5: printf("程序执行完毕!"); return 0; } goto loop; } return 0; } 对于第四小问，要储存学生的三个信息，需要把上面程序修改一下，二叉树结构变为typedefintElemType; //数据类型 typedefstring SlemType; typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ SlemType name; ElemType score; ElemType no; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree; 参数不是key,而是另外三个 intInsertBST(BiTree&T,intno,intscore,string name){//插入二叉树函数 if(T==NULL) { T = (BiTree)malloc(sizeof(BiTNode)); T->no=no;T->name=name;T->score=score; T->lChild=T->rChild=NULL; return 1; } else if(no InsertBST(T->lChild,no,score,name); } else if(key>T->data){ InsertBST(T->rChild,no,score,name); } else return 0; } 其他含参函数也类似 即可完成50个信息存储 用数组存储50个信息，查看以往代码 #include #include using namespace std; class student{ private: intnum; string name; int ob1; int ob2; intara; public: void set(inta,stringb,intc,int d); void show(); int average(); }; void student ::set(inta,stringb,intc,int d){ num=a; name=b; ob1=c; ob2=d; ara=(c+d)/2; } void student::show(){ cout<<"学号："< int student::average(){ returnara;} int main(){ cout<<" 欢迎来到学生管理系统"< cout<<" 0.查询学号信息："< cout<<" 1.删除学号信息："< cout<<" 2.添加学号新信息"< cout<<" 3.按平均分降序显示所有学生信息"< cout<<" 4. 退出"< student *ptr=new student[21]; ptr[1].set(1,"小明",88,67);//已存入的学生信息 ptr[2].set(2,"小李",68,82); ptr[3].set(3,"小王",68,62); ptr[4].set(4,"小陈",79,82); ptr[5].set(5,"小张",63,82); ptr[6].set(6,"小红",68,73); ptr[7].set(7,"小木",62,77); ptr[8].set(8,"小添",65,86); ptr[9].set(9,"小天",68,82); ptr[10].set(10,"张三",88,82); ptr[11].set(11,"李四",98,82); ptr[12].set(12,"王五",88,81); ptr[13].set(13,"小月",58,82); ptr[14].set(14,"小鑫",78,80); ptr[15].set(15,"小良",68,92); ptr[16].set(16,"小成",68,82); ptr[17].set(17,"小敏",98,92); ptr[18].set(18,"小问",88,88); ptr[19].set(19,"小文",48,82); ptr[20].set(20,"小瑞",98,62);//已存入的学生信息 intnumlock; int j=0; inti,k,m; intq,e,r; string w; while(1){ cout<<" 按0,1,2,3,4进行操作"< cin>>numlock; switch(numlock){ case 0: cout<<"输入想查询的学号"< cin>>i; if(i==j){ cout<<"该学号信息已被删除"< break;} ptr[i].show(); break; case 1: cout<<"输入想删除的学号"< cin>>j; delete[j]ptr; cout<<"删除成功"< break; case 2: cout<<"输入想添加的学号信息"< cin>>k; if(k!=j){ cout<<"该学号信息已经存在，添加失败"< break; } cout<<"重新输入添加的学号"< cin>>q; cout<<"输入姓名"< cin>>w; cout<<"输入科目一的成绩"< cin>>e; cout<<"输入科目二的成绩"< cin>>r; ptr[k].set(q,w,e,r); break; case 3: for( m=1;m<20;m++){ for(int n=m+1;n<20;n++){ if(ptr[m].average() student a; a=ptr[m]; ptr[m]=ptr[n]; ptr[n]=a; }} ptr[m].show(); } break; case 4: cout<<"谢谢使用"< return 0; default: cout<<"number out of 0 to 4"< break; }} return 0; } 三．测试结果 二叉排序树储存数据界面（储存学生信息略）创建二叉树： 插入节点： 删除节点： 非递归遍历： 退出： 数组储存学生信息界面 分析查找效率： 因为二叉树查找要创建二叉树，而数组查找只创建一个数组，二叉树的创建时间比较长，所以对于数据量较少的情况下数组的查找效率比较高。但当数据量增加时，二叉树的查找优势就显现出来。所以数据量越大的时候，二叉树的查找效率越高。 四．总结与改进 这个实验工作量还是很大的，做了很久。树状图形输出还是不美观，还需要改进。 一开始打算用栈实现非递归，但是根据书里面的伪代码发现部分是在C++编译器里运行不了的（即使补充了头文件和数据的定义），所以之后参考了网上的数组非递归，发现其功能和栈相似。 递归遍历的实现比非递归的遍历真的简单很多。 开始时只看到前三问，所以没有写到储存学生数据的代码，里面还可以用 clock（）函数加一个计算查找所要数据时间的代码，让二叉树查找与数组查找到效率比较更加直观。 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时） 实验一顺序表问题 【实验报告】 《数据结构与算法》实验报告一 学院：计算机与信息学院班级： 学号：姓名： 日期：程序名： 一、上机实验的问题和要求： 顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求： 1.从键盘输入10个整数，产生顺序表，并输出结点值。 调试数据：9 8 7 6 5 4 3 2 1 2.从键盘输入1个整数，在顺序表中查找该结点。若找到，输出结点的位置；若找不到， 则显示“找不到”。 调试数据：第一次输入11，第二次输入3 3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插 入在对应位置上，输出顺序表所有结点值，观察输出结果。 调试数据：第一次insert "11" after "6" ，第二次insert "86" at "2" 4.从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。 调试数据：第一次delete the number at "2" ，第二次delete value "9" 注意：顺序表输出表现形式如下（实验报告上为截图）： 顺序表： 第一题 Initially Seq: head -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null 第二题 找不到 6 第三题 insert "11" after "6": head -> 9 -> 8 -> 7 -> 6 -> 11 -> 5 -> 4 -> 3 -> 2 -> 1 -> null insert"86"at"2":head -> 9 -> 8 -> 86 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null 第四题 delete the number at "2":head -> 9 -> 8 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 ->null delete value "9": head -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null 数据结构实验报告全集 实验一线性表基本操作和简单程序 1 ．实验目的 （1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法； （2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求 （1 ）认真阅读和掌握和本实验相关的教材内容。 （2 ）认真阅读和掌握本章相关内容的程序。 （3 ）上机运行程序。 （4 ）保存和打印出程序的运行结果，并结合程序进行分析。 （5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"< 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 图实验一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template #include 华北电力大学 实验报告| | 实验名称数据结构实验 课程名称数据结构 | | 专业班级：学生姓名： 学号：成绩： 指导教师：实验日期：2015/7/3 实验报告说明： 本次实验报告共包含六个实验，分别为：简易停车场管理、约瑟夫环（基于链表和数组）、二叉树的建立和三种遍历、图的建立和两种遍历、hash-telbook和公司招工系统。 编译环境：visual studio 2010 使用语言：C++ 所有程序经调试均能正常运行 实验目录 实验一约瑟夫环（基于链表和数组） 实验二简易停车场管理 实验三二叉树的建立和三种遍历 实验四图的建立和两种遍历 实验五哈希表的设计 实验一：约瑟夫环 一、实验目的 1.熟悉循环链表的定义和有关操作。 二、实验要求 1.认真阅读和掌握实验内容。 2．用循环链表解决约瑟夫问题。 3.输入和运行编出的相关操作的程序。 4.保存程序运行结果 , 并结合输入数据进行分析。 三、所用仪器设备 1.PC机。 2.Microsoft Visual C++运行环境。 四、实验原理 1.约瑟夫问题解决方案： 用两个指针分别指向链表开头和下一个，两指针依次挪动，符合题意就输出结点数据，在调整指针，删掉该结点。 五、代码 1、基于链表 #include 实验项目名称：图的遍历 一、实验目的 应用所学的知识分析问题、解决问题，学会用建立图并对其进行遍历，提高实际编程能力及程序调试能力。 二、实验容 问题描述：建立有向图，并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。 三、实验仪器与设备 计算机，Code::Blocks。 四、实验原理 用邻接表存储一个图，递归方法深度搜索和用队列进行广度搜索，并输出遍历的结果。 五、实验程序及结果 #define INFINITY 10000 /*无穷大*/ #define MAX_VERTEX_NUM 40 #define MAX 40 #include typedef struct ArCell{ int adj; }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char name[20]; }infotype; typedef struct { infotype vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; int LocateVex(MGraph *G,char* v) { int c = -1,i; for(i=0;i 2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList [内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template 学期：2010-2011学年第一学期指导教师：杨华莉成绩： 实验一顺序表的基本操作 一、实验目的 1．掌握使用VC++6.0调试程序的基本方法； 2．掌握线性表的顺序存储结构的类型定义； 3．掌握顺序表的基本操作的实现,如：插入、删除、遍历、查找、排序、修改、合并等； 4．掌握顺序表的应用。 二、实验要求 1．认真阅读和掌握本实验的示例程序。 2．上机运行示例程序，打印出程序的运行结果，并作必要的说明。 3．对示例程序，按照对线性表的操作需要，在程序中至少添加2个顺序表的相关操作。如： i.查找并显示分数在区间[a，b）的学生信息； ii.查找并显示最高分或最低分学生信息； iii.统计不及格或及格人数及所占比例； iv.将信息表按学号、姓名或分数升序或降序排列； v.按学号顺序进行数据元素的插入； vi.删除指定学号或姓名的学生信息； vii.修改某个学生的信息； viii.其它。 4．重新改写主函数（要求必需调用自己添加的操作），打印出文件清单（自己添加的函数、修改后的主函数和运行结果）。 5．对修改后的程序，分析每一个算法（函数）的时间复杂度。 6．根据上述要求撰写实验报告，并简要给出算法设计小结和心得。 三、实验环境 1．台式计算机每人一台； 2．软件：Visual C++6.0 四、实验内容和实验结果 一．示例程序运行结果及说明 二．自己添加的新函数(至少2个)，要求加必要的注释。 SqList Delete_SqList(SqList &L)//删除学生信息 { Elemtype x; int i=0; int choice=DMenu(); char name[25]; int num,k; if(!L.length) { printf("表为空，无法删除!"); exit(0); } switch(choice) { case 1: //按姓名删除 printf("\n请输入要删除的学生的姓名\n"); scanf("%s",&name); k=strcmp(name,L.data[i].name);//比较姓名 if(k==0) { x=L.data[i-1]; for(int m=L.length-1;m>=i-1;--m) L.data[i-1]=L.data[i]; --L.length; break; } case 2: //按学号删除 printf("\n请输入要删除学生的学号\n"); scanf("%d",&num); if(num==L.data[i].num) { for(int m=L.length-1;m>=i-1;--m) L.data[i-1]=L.data[i]; --L.length; break; } case 3:break; } return L; 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 云南大学软件学院数据结构实验报告 （本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度： A □ B □ C □ 学期：2010秋季学期 任课教师: 实验题目: 查找算法设计与实现 姓名: 王辉 学号: 20091120154 电子邮件: 完成提交时间： 2010 年 12 月 27 日 云南大学软件学院2010学年秋季学期 《数据结构实验》成绩考核表 学号：姓名：本人承担角色： 综合得分：（满分100分） 指导教师：年月日（注：此表在难度为C时使用，每个成员一份。） （下面的内容由学生填写，格式统一为，字体: 楷体, 行距: 固定行距18，字号: 小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%) 1 哈希表查找。根据全年级学生的姓名，构造一个哈希表，选择适当的哈希函数和解决冲突的方法，设计并实现插入、删除和查找算法。 熟悉各种查找算法的思想。 2、掌握查找的实现过程。 3、学会在不同情况下运用不同结构和算法求解问题。 4 把每个学生的信息放在结构体中： typedef struct //记录 { NA name; NA tel; NA add; }Record; 5 void getin(Record* a)函数依次输入学生信息 6 人名折叠处理，先将用户名进行折叠处理折叠处理后的数，用除留余数法构造哈希函数，并返回模值。并采用二次探测再散列法解决冲突。 7姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。将初始班级的通讯录信息存入文件。 二、【实验设计(Design)】(20%) （本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系） 1抽象数据类型的功能规格说明和结构体： #include 《数据结构》实验报告 ◎实验题目: 无向图的建立与遍历 ◎实验目的：掌握无向图的邻接链表存储，熟悉无向图的广度与深度优先遍历。 ◎实验内容：对一个无向图以邻接链表存储，分别以深度、广度优先非递归遍历输出。 一、需求分析 1.本演示程序中，输入的形式为无向图的邻接链表形式，首先输入该无向图的顶点数和边数，接着输入顶点信息，再输入每个边的顶点对应序号。 2.该无向图以深度、广度优先遍历输出。 3.本程序可以实现无向图的邻接链表存储，并以深度、广度优先非递归遍历输出。 4.程序执行的命令包括：（1）建立一个无向图的邻接链表存储（2）以深度优先遍历输出（3）以广度优先遍历输出（4）结束 5.测试数据： 顶点数和边数：6,5 顶点信息：a b c d e f 边的顶点对应序号： 0,1 0,2 0,3 2,4 3,4 深度优先遍历输出： a d e c b f 广度优先遍历输出： a d c b e f 二概要设计 为了实现上述操作，应以邻接链表为存储结构。 1.基本操作： void createalgraph(algraph &g) 创建无向图的邻接链表存储 void dfstraverseal(algraph &g,int v) 以深度优先遍历输出 void bfstraverseal(algraph &g,int v) 以广度优先遍历输出 2.本程序包含四个模块： （1）主程序模块 （2）无向图的邻接链表存储模块 （3）深度优先遍历输出模块 （4）广度优先遍历输出模块 3.模块调用图： 三详细设计 1.元素类型，结点类型和指针类型：typedef struct node { int adjvex; struct node *next; }edgenode; typedef struct vnode { char vertex; edgenode *firstedge; }vertxnode; typedef vertxnode Adjlist[maxvernum]; typedef struct { Adjlist adjlist; int n,e; }algraph; edgenode *s; edgenode *stack[maxvernum],*p; 2.每个模块的分析： （1）主程序模块 int main() 2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨 实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。 三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template 《数据结构实验》的实验题目及实验报告模板 实验一客房管理（链表实验） ●实现功能：采用结构化程序设计思想，编程实现客房管理程序的各个功能函数，从而熟练 掌握单链表的创建、输出、查找、修改、插入、删除、排序和复杂综合应用等操作的算法 实现。以带表头结点的单链表为存储结构，实现如下客房管理的设计要求。 ●实验机时：8 ●设计要求： #include 本科实验报告 课程名称：数据结构（C语言版） 实验项目：线性表、树、图、查找、内排序实验地点：明向校区实验楼208 专业班级：学号： 学生姓名： 指导教师：杨永强 2019 年 1 月10日 #include 数据结构实验报告 第 6 次实验 学号：20141060106 姓名：叶佳伟 一、实验目的 1、复习图的逻辑结构、存储结构及基本操作； 2、掌握邻接矩阵、邻接表及图的创建、遍历； 3、了解图的应用。 二、实验内容 1、（必做题）假设图中数据元素类型是字符型，请采用邻接矩阵或邻接表实现图的以下基本操作： （ 1）构造图（包括有向图、有向网、无向图、无向网）； （ 2）根据深度优先遍历图； （ 3）根据广度优先遍历图。 三、算法描述 （采用自然语言描述） 四、详细设计 （画出程序流程图） 五、程序代码 （给出必要注释） #include int adj;/*顶点关系类型,对无权图,用1(是)或0(否)表示相邻否;对带权图,则为权值*/ char *info;/*弧相关信息指针*/ }AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char vexs[MAX_VERTEX_NUM][5];/*顶点向量*/ AdjMatrix arcs; /*邻接矩阵*/ int vexnum, arcnum;/*图的当前顶点数和弧数*/ int kind; }MGraph; void CreateDG(MGraph *G); void CreateDN(MGraph *G); void CreateUDG(MGraph *G); void CreateUDN(MGraph *G); int LocateVex(MGraph *G, char v[]); void print(MGraph *G); int main(void) { MGraph *G; G = (MGraph *)malloc(sizeof(MGraph)); printf("请选者0-有向图,1-有向网,2-无向图,3-无向网: "); scanf("%d", &G->kind); switch(G->kind) { case DG : CreateDG(G); print(G); break; case DN : CreateDN(G); print(G); break; case UDG : CreateUDG(G); print(G); break; case UDN : CreateUDN(G); 数据结构(C语言版) 实验报告 专业班级学号姓名 实验1 实验题目：单链表的插入和删除 实验目的： 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 实验要求： 建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。 实验主要步骤： 1、分析、理解给出的示例程序。 2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序 的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。 3、修改程序： （1）增加插入结点的功能。 （2）将建立链表的方法改为头插入法。 程序代码: #include"stdio.h" #include"string.h" #include"stdlib.h" #include"ctype.h" typedef struct node //定义结点 { char data[10]; //结点的数据域为字符串 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自定义LinkList单链表类型 LinkList CreatListR1(); //函数，用尾插入法建立带头结点的单链表 LinkList CreatList(void); //函数，用头插入法建立带头结点的单链表 ListNode *LocateNode(); //函数，按值查找结点 void DeleteList(); //函数，删除指定值的结点 void printlist(); //函数，打印链表中的所有值 void DeleteAll(); //函数，删除所有结点，释放内存 数据结构教程 上机实验报告 实验七、图算法上机实现 一、实验目的： 1.了解熟知图的定义和图的基本术语，掌握图的几种存储结构。 2.掌握邻接矩阵和邻接表定义及特点，并通过实例解析掌握邻接 矩阵和邻接表的类型定义。 3.掌握图的遍历的定义、复杂性分析及应用，并掌握图的遍历方 法及其基本思想。 二、实验内容： 1.建立无向图的邻接矩阵 2.图的深度优先搜索 3.图的广度优先搜索 三、实验步骤及结果： 1.建立无向图的邻接矩阵： 1)源代码： #include "" #include "" #define MAXSIZE 30 typedef struct { char vertex[MAXSIZE]; ertex=i; irstedge=NULL; irstedge; irstedge=p; p=(EdgeNode*)malloc(sizeof(EdgeNode)); p->adjvex=i; irstedge; irstedge=p; } } int visited[MAXSIZE]; ertex); irstedge; ertex=i; irstedge=NULL; irstedge;irstedge=p; p=(EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex=i; irstedge; irstedge=p; } } typedef struct node { int data; struct node *next; }QNode; ertex); irstedge;ertex); //输出这个邻接边结点的顶点信息 visited[p->adjvex]=1; //置该邻接边结点为访问过标志 In_LQueue(Q,p->adjvex); //将该邻接边结点送人队Q }数据结构实验报告格式
数据结构实验一顺序表问题及实验报告模板 - Copy
(完整版)数据结构实验报告全集
数据结构实验报告
数据结构实验报告图实验
数据结构实验报告完整
数据结构图的遍历实验报告
数据结构实验报告模板
数据结构实验报告模板(验证型)
数据结构实验报告图实验
数据结构实验报告七查找、
数据结构实验报告无向图
数据结构实验报告及心得体会
数据结构实验报告图实验
《数据结构实验》实验题目及实验报告模板
数据结构实验报告
数据结构实验报告
数据结构实验报告 - 答案汇总
数据结构图实验报告
相关主题
文本预览