第一篇：数据结构上机实验--图
数据结构上机实验六
实验内容:图的基本操作
实验要求:
1)图的遍历与基本操作要作为函数被调用.2)把自己使用的图结构明确的表达出来.3)基本上实现每个实验题目的要求.分组要求：可单独完成，也可两人一组。
实验目的:
1)熟悉C/C++基本编程,培养动手能力.2)通过实验,加深对图的理解.评分标准：
1)只完成第一和第二题，根据情况得4，5分；
2）完成前3题，根据情况得5至7分；
3）在2）基础上，选做四）中题目，根据情况得8至10分。
题目:
一)建立一个无向图+遍历+插入
(1)以数组表示法作为存储结构，从键盘依次输入顶点数、弧数与各弧信息建立一个无向图；
(2)对（1）中生成的无向图进行广度优先遍历并打印结果；
(3)向（1）中生成的无向图插入一条新弧并打印结果；
二)建立一个有向图+遍历+插入+删除
(1)以邻接表作为图的存储结构，从键盘输入图的顶点与弧的信息建立一个有向图；
(2)对（1）中生成的有向图进行深度优先遍历并打印结果；
(3)在（1）中生成的有向图中，分别插入与删除一条弧并打印其结果；
(4)在（1）中生成的有向图中，分别插入与删除一个顶点并打印结果；
(5)在（1）中生成的有向图中,各顶点的入度与出度并打印结果；
三）基本应用题
（1）编写算法，判断图中指定的两个顶点是否连通。
（2）编写算法，判断图的连通性。如果不连通，求连通分量的个数
（3）编写算法，判断图中任意两个顶点的连通性
（4）编写算法，判断图中是否存在回路。
（5）实现图的广度优先搜索算法。
四）高级应用题
（1）实现Prim算法
（2）实现Kruskal算法
（3）实现迪杰斯特拉算法
（4）实现拓扑排序算法
（5）实现关键路径算法
第二篇：数据结构 实验一 图[推荐]
北京邮电大学信息与通信工程学院
数据结构实验报告
实验名称： 实验二——图 学生姓名： 佘晨阳 班
级： 2014211117 班内序号： 20 学
号： 2014210491 日
期： 2015年12月05日
1．实验要求
根据图的抽象数据类型的定义，使用邻接矩阵或邻接表实现一个图。图的基本功能：
1、图的建立
2、图的销毁
3、深度优先遍历图
4、广度优先遍历图
5、使用普里姆算法生成最小生成树
6、使用克鲁斯卡尔算法生成最小生成树
7、求指定顶点到其他各顶点的最短路径
8、其他：比如连通性判断等自定义操作
编写测试main()函数测试图的正确性
2.程序分析
本实验要求掌握图基本操作的实现方法，了解最小生成树的思想和相关概念，了解最短路径的思想和相关概念，学习使用图解决实际问题的能力。
2.1 存储结构
存储结构：1.不带权值的无向图邻接矩阵
2.带权值的无向图邻接矩阵
3.带权值的有向图邻接矩阵
1．不带权值的无向图邻接矩阵
第1页 北京邮电大学信息与通信工程学院
2带权值的无向图邻接矩阵.3.带权值的有向图邻接矩阵
[备注]：
1.在使用打印元素、BFS、DFS 采用无权值的无向图邻接矩阵存储方式 2.在使用PRIM、KRUSKAL、3.在使用最短路径的算法时采用具有权值的有向图邻接矩阵存储方式
2.2 关键算法分析
第2页 北京邮电大学信息与通信工程学院
一．图的邻接矩阵构造函数：
1.关键算法： template
//带权值的图的构造函数 { int i, j, k, height;f s1, s2;vnum = n;arcnum = e;for(k = 0;k < n;k++){ vertex[k] = a[k];}
//初始化顶点
for(k = 0;k for(i = 0;i < n;i++) { arc[k][i] =-1; if(i == k)arc[k][i] = 0; //初始化权值的大小 } visited[k] = 0;} cout << endl;for(k = 0;k //初始化边 { cout << “请输入线性链接节点:”; cin >> s1 >> s2 >> height; arc[convert(s1)][convert(s2)] = height; arc[convert(s2)][convert(s1)] = arc[convert(s1)][convert(s2)];//采用无向图带权值的邻接矩阵 } cout << endl;cout << “所得邻接矩阵为：” << endl; for(k = 0;k for(i = 0;i < n;i++) { if(arc[k][i] ==-1) cout << “∞” << “ ”; else cout << arc[k][i] << “ ”; //打印邻接矩阵的格式 } cout << endl; } cout << endl 2.算法的时间复杂度 第3页 北京邮电大学信息与通信工程学院 有构造可知，初始化时其时间复杂度：O(n2) 二．深度优先便利DFS: 1.关键算法 ①从某顶点v出发并访问 ②访问v的第一个未访问的邻接点w，访问w的第一个未访问的邻接点u，…… ③若当前顶点的所有邻接点都被访问过，则回溯，从上一级顶点的下一个未访问过的顶点开始深度优先遍历 ④直到所有和v路径相通的顶点都被访问到； 2.代码图解： 深度优先遍历示意图 3.代码详解： template for(int j = 0;j < vnum;j++) //连通图 if((visited[j] == 0)&&(arc[v][j] >= 1))DFS(j);//当存在回路时，则连通深一层遍历 } 4.时间复杂度 时间复杂度：O(n2) 空间复杂度：栈的深度O(n) 辅助空间O(n) 第4页 北京邮电大学信息与通信工程学院 三．广度遍历BFS 1.关键算法 ①访问顶点v ②依次访问v的所有未被访问的邻接点v1,v2,v3… ③分别从v1,v2,v3…出发依次访问它们未被访问的邻接点 ④反复①②③，直到所有和v路径相通的顶点都被访问到； 2.代码图解 3.代码详解 1.初始化队列Q 2.访问顶点v，visited[v]=1 3.while(队列非空) 3.1 v=队头元素出队 3.2 访问队头元素的所有未访问的邻接点 4.时间复杂度 时间复杂度：O(n2) 空间复杂度：辅助空间O(n) 四.最小生成树——普里姆算法 1,关键思路 一般情况下，假设n个顶点分成两个集合：U(包含已落在生成树上的结点)和V-U(尚未落在生成树上的顶点)，则在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。主数据结构： 邻接矩阵 辅助数据结构： int adjvex[MAXSIZE];// U集中的顶点序号 第5页 北京邮电大学信息与通信工程学院 int lowcost[MAXSIZE]; // U(V-U)的最小权值边 2.代码图解 第6页 北京邮电大学信息与通信工程学院 第7页 北京邮电大学信息与通信工程学院 3;代码详解 template //辅助数组存储所有到的V0边 { adjvex[i] = 0;lowcost[i] = arc[0][i]; } lowcost[0] = 0;for(int j = 1;j < vnum;j++) //循环n-1次 { int k = Mininum(lowcost); //求下一个顶点 cout << vertex[adjvex[k]] << “->” << vertex[k] << endl; lowcost[k] = 0; //U=U+{Vk} for(int j = 0;j < vnum;j++) //设置辅助数组 { if((lowcost[j]!= 0 && arc[k][j] < lowcost[j])) { lowcost[j] = arc[k][j]; adjvex[j] = k; } } 第8页 北京邮电大学信息与通信工程学院 } } 4,时间复杂度： 时间复杂度O(n2)，适合稠密图 五.最小生成树----克鲁斯卡尔算法 1,关键思路 先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。2.代码图解： 3.代码详解 template //最小生成树—kruskal算法 { cout<<“Krusal算法结果为：”< int k = 0, j = 0; while(k < vnum-1){ int m = vedgelist[j].fromv, n = vedgelist[j].endv; int sn1 = vset[m]; int sn2 = vset[n]; //两个顶点分属 第9页 北京邮电大学信息与通信工程学院 不同的集合 if(sn1!= sn2) { cout << vertex[m] << “->” << vertex[n] << endl; k++; for(int i = 0;i < vnum;i++) { if(vset[i] == sn2) vset[i] = sn1; //集合sn2全部改成sn1 } } j++;} } 4.时间复杂度 时间复杂度O(nlogn)，适合稀疏图 六．最短路径——Dijkstra算法 1.关键代码 • 按路径长度递增的次序产生源点到其余各顶点的最短路径。• 1)设置集合s存储已求得的最短路径的顶点，• 2)初始状态：s=源点v • 3)叠代算法： • 直接与v相连的最近顶点vi,加入s • 从v经过vi可以到达的顶点中最短的，加入s …… 2.代码图解 第10页 北京邮电大学信息与通信工程学院 3.代码详解 emplate //关于最短路径的初始化 { int v=convert(x); for(int i = 0;i < vnum;i++) //初始化路径和点 { s[i]=0; disk[i] = arc[v][i]; if(disk[i]!= maxs)path[i] = v; else path[i] =-1;} s[v] = 1;disk[v] = 0;path[v]=-1;for(int i = 0;i < vnum;i++) //反复经过从该点到其他点的路径 { if((v = FindMin())==-1)continue; s[v] = 1; for(int j = 0;j < vnum;j++) if(!s[j] &&(disk[j]>arc[v][j] + disk[v])) { 第11页 北京邮电大学信息与通信工程学院 disk[j] = arc[v][j] + disk[v]; path[j] = v; } } Print(); //打印路径长度和遍历 } 4.时间复杂度 时间复杂度为：n^2 七．判断连通图算法 template { cout<<“该图为连通图！*******输入成功！”< return false; } else { cout<<“该图不为连通图！*******请重新输入”< return true; } } 时间复杂度：n^2 3.程序运行结果 1.测试主函数流程： 第12页 北京邮电大学信息与通信工程学院 函数流程图： 1.输入图的连接边并打印 构造下面所示图的邻接矩阵： 第13页 北京邮电大学信息与通信工程学院 2.判断图连通是否成功 3.BFS DFS PRIM算法的实现 第14页 北京邮电大学信息与通信工程学院 4.克鲁斯卡尔算法实现过程 4.有向图邻接矩阵的构建 第15页 北京邮电大学信息与通信工程学院 插入V0位置后打印距离并开始回溯 总结 1.调试时出现的问题及解决的方法 问题一：prim算法中 解决方法：调整循环条件，修正函数体注意有无Next的区别 第16页 北京邮电大学信息与通信工程学院 问题二：BFS和DFS同时在一个类里作用时会输出错误 解决方案：每次BFS/DFS使用时都把visited数组初始化一遍 问题三：在最短路径，经常出现了停止输入的情况 解决方法：改return为continue，并修改打印算法 2.心得体会 通过本次实验，基本熟练掌握了c++基本语句，尤其对图的结构及应用有了较深了解；调试代码时尽量做到完成一个代码段调试一次，可以最快检测出错误所在；类的封装和调用，类的共有成员和私有成员的设置。 3.下一步的改进 第一，设置增加图节点和边的函数 第二，实现图形化输出图的路径的功能 第三，主函数设计简单，不要过于累赘 4.程序中出现的亮点 1)利用dfs算法衍生生成判断是否为连通图的连通算法 2)采用graph类实现所有图的所有算法，所需的数据类型均在私有成员内，封装 3)利用convert函数采取象意输入，采用ABCD的节点输入方式而并非转化成01234再输入。 4)BFS中采用c++标准库的。 5)打印邻接矩阵时，打印出非链接的∞符号和与自身路径的0距离 6)判断图为非连通图后，提示输入错误，重新输入图元素 第17页 《数据结构》上机实验的目的和要求 通过上机实验加深对课程内容的理解，增加感性认识，提高软件设计、编写及调试程序的能力。 要求所编的程序能正确运行，并提交实验报告。实验报告的基本要求为： 1、需求分析：陈述程序设计的任务，强调程序要做什么，明确规定： （1）输入的形式和输出值的范围； （2）输出的形式； （3）程序所能达到的功能； （4）测试数据：包括正确的输入输出结果和错误的输入及输出结果。 2、概要设计：说明用到的数据结构定义、主程序的流程及各程序模块之间的调用关系。 3、详细设计：提交带注释的源程序或者用伪代码写出每个操作所涉及的算法。 4、调试分析： （1）调试过程中所遇到的问题及解决方法； （2）算法的时空分析； （3）经验与体会。 5、用户使用说明：说明如何使用你的程序，详细列出每一步操作步骤。 6、测试结果：列出对于给定的输入所产生的输出结果。若有可能，测试随输入规模的增长所用算法的实际运行时间的变化。 数据结构实验报告 课程 数据结构 _ 院 系 专业班级 实验地点 姓 名 学 号 实验时间 指导老师 数据结构上机实验报告1 一﹑实验名称： 实验一——链表 二﹑实验目的： 1.了解线性表的逻辑结构特性； 2.熟悉链表的基本运算在顺序存储结构上的实现，熟练掌握链式存储结构的描述方法； 3.掌握链表的基本操作（建表、插入、删除等）4.掌握循环链表的概念，加深对链表的本质的理解。5.掌握运用上机调试链表的基本方法 三﹑实验内容： （1）（2）（3）（4）创建一个链表 在链表中插入元素 在链表中删除一个元素 销毁链表 四﹑实验步骤与程序 #include LinkList p,q;L=(LinkList)malloc(sizeof(Lnode));L->next=NULL;q=L; cout<<“请输入一个链表：”< for(int i=0;i { p=(LinkList)malloc(sizeof(Lnode)); cin>>p->data; p->next=q->next; q->next=p; q=p; } } int PrintLinkList(LinkList &L){//输出链表L的数据元素 LinkList p; } void LinkListLengh(LinkList &L){//计算链表L的数据元素个数。int i=0;p=L->next;if(L->next==NULL){ } cout<<“链表的数据元素为:”;while(p) { cout< data<<“ ”; p=p->next;} cout<<“链表没有元素!”< } LinkList p;p=L->next;while(p){ i++; p=p->next; } cout<<“链表的数据元素个数为:”< LinkList p,s;int j=0;p=L; while(p&&j } if(!p||j>i-1){ p=p->next;++j; } } cout<<“插入元素的位置不合理!”;return 0;s=(LinkList)malloc(sizeof(LNode));s->data=x;s->next=p->next;p->next=s;return 1;int DeleteLinkList(LinkList &L,int i){//删除链表L的第I个数据元素。 LinkList p,q;int j=0;p=L;while(p->next&&j } if(!(p->next)||j>i-1){ p=p->next;++j; } } cout<<“删除元素的位置不合理!”;return 0;q=p->next;p->next=q->next;i=q->data;free(q);return 1;void DestroyLinkList(LinkList &L){//销毁链表L。 LinkList p,q;p=L->next;while(L->next!=NULL){ q=p->next;L->next=q; free(p);} p=q; free(L); cout<<“链表已经被销毁!”< LinkList L; int i,j,x;cout<<“第一次数据结构上机实验—链表”< CreatLinkList(L,j); LinkListLengh(L); PrintLinkList(L); cout<<“在第几个元素前插入:”;cin>>i;cout<<“输入插入的元素:”;cin>>x; InsertLinkList(L,i,x); LinkListLengh(L); PrintLinkList(L); cout<<“输入删除元素的位置:”;cin>>i; DeleteLinkList(L,i); LinkListLengh(L); PrintLinkList(L); cout<<“销毁程序后为:”< DestroyLinkList(L);} 五﹑实验结果 六﹑实验心得体会： 链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址。 实验的程序设计规划（实现的功能、分几个模块、子函数）（1）编写链表创建子函数void CreatLinkList(L,j)（2）编写链表插入子函数 int InsertLinkList(LinkList &L, int i, int x)（3）链表的打印int PrintLinkList(LinkList &L)（4）编写链表删除子函数 int DeleteLinkList(LinkList &L,int i)（5）编写链表销毁子函数void DestroyLinkList(LinkList &L)（6）编写主函数Main()，通过功能菜单调用子函数（7）编译调试程序 经过多次的调试，修改，实验结果终于正确了，在这个过程中，经历了不知道怎么进行声明区的编写如包含文件，宏定义，函数声明，全局变量声明，结构体等的定义等的结合，到学会了使用先把程序主要规划为四个部分来写就简单多了，第一，定义；第二，写所要调用的子函数；第三，写主函数，调用子函数；第四就是程序的编译与调试，修改。数据结构实验需要我们对每个程序的算法有深刻的理解，才能应用到实际中去，因此我们需要在做实验之前要熟悉实验的内容，且先把所要实验的程序写出来，在实验中就可以查找错误并加以改正，这是一个成长的过程。 数据结构上机实验报告一﹑实验名称： 实验二—队列 二﹑实验目的： 1.掌握队列这种抽象数据类型的特点, 掌握栈与队列在实际问题中的应用和基本编程技巧,并能在相应的问题中选用它;2.熟练掌握循环队列和链队列的基本操作实现算法，特别是队满和队空的描述方法； 3．掌握栈与队列的数据类型描述及特点； 4.掌握栈的顺序和链式存储存表示与基本算法的实现； 5.掌握队列的链式存储表示与基本操作算法实现;6.按照实验题目要求，独立完成实际程序的编写编写、调试和运行，并通过用例数据的运行过程抓获相关屏面验证程序设计的正确性； 7.认真书写实验报告，并按时提交。 三﹑实验内容： 对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当前的対尾位置下标，对头指针用于指示当前的対头位置下标。现要求： （1）掌握栈和队列的特点，即后进先出和先进先出的原则。（2）设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空； （3）编写主函数进行测试。 四﹑实验步骤与程序 #include #define OK 1 #define ERROR 0 #define OVERFLOW 0 typedef struct QNode { int data;struct QNode *next;}QNode,*QueuePtr;typedef struct { QueuePtr front;QueuePtr rear;}LinkQueue;int InitQueue(LinkQueue &Q){ } Q.rear=Q.front=(QueuePtr)malloc(sizeof(QNode));if(!Q.rear)exit(OVERFLOW);Q.front->next=NULL;return OK;void QueueEmpty(LinkQueue Q){ } void EnQueue(LinkQueue &Q,int e){ } int EnnQueue(LinkQueue &Q,int e){ QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));if(!p)printf(“error”);if(Q.front==Q.rear)printf(“该链队为空:”);else printf(“该链队不为空:”);p->data=e;Q.rear->next=p;Q.rear=p;printf(“元素%d入队成功”,e); } if(!p)return ERROR;p->data=e;Q.rear->next=p;Q.rear=p; return OK;void DeQueue(LinkQueue &Q){ } void GetHead(LinkQueue &Q){ QueuePtr p;QueuePtr p;if(Q.front==Q.rear)printf(“该链队为空”);p=Q.front->next;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);printf(“队首元素删除成功”); } if(Q.front==Q.rear)printf(“该链队为空”);p=Q.front->next;printf(“队首元素为:%d”,p->data);void OutQueue(LinkQueue &Q){ } void LengthQueue(LinkQueue &Q){ int f=0;QueuePtr p;if(Q.front==Q.rear)QueuePtr p;if(Q.front==Q.rear)printf(“该链队为空”);p=Q.front->next;while(p!=Q.rear->next){ } printf(“%d%,”,p->data);p=p->next; } printf(“该队列的长度为:%d”,f);else { } p=Q.front->next;while(p!=Q.rear->next){ } printf(“该队列的长度为:%d”,f);p=p->next;f++;void main(){ system(“cls”);int flag=1,i;LinkQueue Q;InitQueue(Q);printf(“************************链队列功能菜单***********************n”);printf(“1:初始化链队列，2:判断链队列是否为空, 3:进入队列，4:取出队首元素n”);printf(“5:输出该队列的所有元素,6:输出该队列的长度，7:结束程序，8:清屏n”); while(flag){ printf(“n请输入操作符:”);scanf(“%d”,&i);switch(i){ case 1: int e,n,k;printf(“请输入队列的长度:”);scanf(“%d”,&n);printf(“请输入队列的元素:”);for(e=1;e<=n;e++){ } printf(“初始化链队成功”);break;scanf(“%d”,&k);EnnQueue(Q,k);case 2: QueueEmpty(Q); break;case 3: int j;printf(“请输入要进入队列的元素”);scanf(“%d”,&j);EnQueue(Q,j);break;case 4: GetHead(Q);break;case 5: printf(“该队列的元素为:”);OutQueue(Q);break; case 6: LengthQueue(Q);break;case 7: flag=0;break;case 8: system(“cls”);} break; } } 五﹑实验结果 六﹑实验心得体会： 程序主要构造了主函数main（）和 InitQueue（），QueueEmpty（）EnQueue()，OutQueue()等调用函数，实现了队列的创立，队列是否为空的判断，入队和出队等功能。 通过此次实验，加深了对队列的存储结构的了解，同时也对程序设计能力有了提高，加深了对队列先进先出性质的理解，它允许在表的一端进行插入，在另一端删除元素，这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。我们往往写不出程序，这其中的原因我觉得是对程序的结构不是很了解，对实验的内容也不熟练的结果，数据结构给我们许多程序的算法和模型，对我们写程序的思维有很大的锻炼，我们应珍惜每次上机实验的机会去实践课堂上所学的东西并从中发现问题，从而达到提升写程序的能力。 数据结构上机实验报告一﹑实验名称： 实验三—二叉树的遍历 二﹑实验目的： 1、熟悉二叉树的结构特性，了解相应的证明方法； 2、掌握二叉树的生成，掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法； 3、理解二叉树的三种遍历方法：先序遍历、中序遍历和后序遍历； 4、学会编写实现树的各种操作的算法。 二、实验内容： 1、使用类定义实现二叉树，补充完整所缺的函数，并实现创建和遍历二叉树的基本操作； 2、编程实现在二叉链表这种存储方式下，实现二叉的遍历，可采用递归或者非递归实现，遍历算法为在先序、中序和后序遍历算法。 三、实验步骤与程序： #include void PreOrder(BiTree T)//先序 { if(T!=NULL){ printf(“%c”,T->data);PreOrder(T->lchild);PreOrder(T->rchild);} } void InOrder(BiTree T)//中序 { if(T!=NULL){ InOrder(T->lchild);printf(“%c”,T->data);InOrder(T->rchild);} } void PostOrder(BiTree T)//后序 { if(T!=NULL){ PostOrder(T->lchild);PostOrder(T->rchild);printf(“%c”,T->data);} } void main()//主函数 { printf(“------------二叉树的遍历-------------n”);printf(“请输入要遍历的数：”);BiTree Ta;Ta=CreateBiTree();printf(“先序遍历:”);printf(“n”);PreOrder(Ta);printf(“n”);printf(“中序遍历:”);printf(“n”);InOrder(Ta);printf(“n”);printf(“后序遍历:”);printf(“n”);PostOrder(Ta);} 五﹑实验结果 六﹑实验心得体会： 实验的程序设计规划（实现的功能、分几个模块、子函数）（1）先序遍历递归算法函数：void PreOrder(BiTree T)（2）中序遍历递归算法函数：void InOrder(BiTree T)（3）后续遍历递归算法函数：void PostOrder(BiTree T)（4）主函数的实现：void main() 在实验前我认真阅读关于二叉树的实现的内容，为编程实现第一步，本次实验通过按上述的实验步骤一步步实现的，实验过程中出现了一些错误，经过一步步的调试，修改错误，得到了二叉树的遍历用递归运算的方法的程序。通过这个实验，我体会到了理解数据结构的重要性，这有真正理解了定义数据类型的好处，才能用好这样一种数据结构。二叉树的先序，中序与后序的输出都用了递归的算法，而且用起来不是很复杂，这使我更进一步理解了函数递归调用并得到灵活运用；在实现算法上，从算法的效率看，递归方法书写形式较为简洁，更为直观，一般具有较好的空间效率。 总之，不管做什么实验，我们在做实验前都要先预习，对所做的实验有较深的理解，在做实验的时候需要很严谨，仔细的查找错误，从而能在实验中收获知识，提升自己。 数据结构上机实验报告4 一﹑实验名称： 实验四—查找 二﹑实验目的： 1、熟悉掌握顺序表的查找方法； 2、熟练掌握二叉排序树的构造方法和查找算法 3、掌握描述查找过程的判定树的构造方法，以及按照定义计算各种查找方法在等概率情况下查找成功时的平均查找长度； 4、学会定义线性表的储存类型，实现C++程序的基本结构对线性表的一些基本操作和具体的函数定义； 5、掌握顺序表的基本操作，实现顺序表的查找的等基本运算； 6、掌握对于多函数程序的输入，编辑，调试和运算过程。 二、实验内容： 1、实现顺序表的查找算法 2、关于衡量查找的主要操作—查找的查找平均效率的平均长度的讨论。 三、实验步骤与程序： #include element list[MAX_SIZE]; int seqsearch(element list[],int searchnum,int num);int main(){ int i,num,searchnum,k; printf(“---------------数据结构查找实验-------------n”);printf(“请输入数据元素的个数：”);scanf(“%d”,&num);printf(“请输入数据的元素：n”);for(i=0;i printf(“请输入要查询的数据元素:”);scanf(“%d”,&searchnum);k=seqsearch(list,searchnum,num);if(k!=-1){ printf(“所查询元素的下标为：”);printf(“%dn”,k);} else printf(“查询元素不存在。n”);} return 0;} int seqsearch(element list[],int searchnum,int num){ int j; list[num].key=searchnum; for(j=0;list[j].key!=searchnum;j++);return j 六﹑实验心得体会： 实验的程序设计规划为先写一个主函数int main()，再写一个查找的子函数int seqsearch(element list[],int searchnum,int num)，主函数通过调用子函数的方法实现程序的设计。 所谓“查找”即为在一个众多的数据元素（或记录）的查找表中找出某个“特定的”数据元素（或记录），通过本次实验，我更进一步的了解数据结构程序实验设计实现算法的基本模型，和算法实现等基本内容，学会了顺序表的查找方法。 数据结构上机实验报告5 一﹑实验名称： 实验五—内部排序 二﹑实验目的： 1、通过实现下述实验内容，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况，并加以灵活应用。 2、掌握各种排序时间复杂度的分析方法。 二、实验内容： 1、插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。 2、快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成。 3、讨论各种内部排序方法的基本思路，算法特点，排序过程及它们的时间复杂度的分析。 三、实验步骤与程序： #include } int x;void charu();void kuaisu();printf(“----------内部排序---------n”);printf(“ 1、插入排序：n”);printf(“ 2、选择排序：n”);printf(“请根据序号选择：”);scanf(“%d”,&x);if(x==1)charu();else kuaisu();void charu(){ int a[7],j,i,m; printf(“插入排序n”); printf(“请输入个您想排序的数据:n”); for(i=0;i<7;i++)scanf(“%d”,&a[i]); for(j=1;j<7;j++) { m=a[j]; for(i=j-1;i>=0;i--) { if(a[i] break; else a[i+1]=a[i]; } a[i+1]=m; } printf(“排序成功:”); for(i=0;i<7;i++) printf(“ %d”,a[i]); printf(“n”);} quick(int first,int end,int L[]){ int left=first,right=end,key; key=L[first]; while(left { while((left right--; if(left L[left++]=L[right]; while((left left++; if(left L[left]=key; return left; } quick_sort(int L[],int first,int end) { int split; if(end>first) { split=quick(first,end,L); quick_sort(L,first,split-1); quick_sort(L,split+1,end); } } void kuaisu(){ int a[7],i; printf(“快速排序n”); printf(“请输入个您想排序的数据:n”); for(i=0;i<7;i++) scanf(“%d”,&a[i]); quick_sort(a,0,9); printf(“排序成功:”); for(i=0;i<7;i++) printf(“ %d”,a[i]); printf(“n”);} 五﹑实验结果： 六﹑实验心得体会： 排序的功能是将一个数据元素（或记录）的任意序列，从新排成按关键字有序的序列；直接插入排序的稳定性比快速排序高，且算法较简单。本次实验运用到的是插入排序和快速排序。 实习报告 题 目 : 实现一个约瑟夫环程序 班级：031021姓名：王帅学号：03102076 一、需求分析 1． 本演示程序中，利用单向循环链表存储结构存储约瑟夫环数据（即n个人的编号和密码）。 2． 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中需要输入的数据，运算结果显示在其后。 3． 程序执行的命令包括： 1)构造单向循环链表；2）进行数值的输入，并作判断分析；3）约瑟夫算法的实现与结果输出；4）结束。 4． 测试数据 m 的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，（正确的出列顺序为6，1，4，7，2，1，3，5）。 二、概要设计 1．单向循环链表的抽象数据类型定义为： ADT List｛ 数据对象：D=｛ai | ai↔正整数，I=1，2，......，n,n≥0｝数据关系：R1=｛< ai-1，ai > |，ai-1，ai↔D,I=1，2，......，n｝基本操作： Init List(&L) 操作结果：构造一个空的线性表L。 List Insert(&L,i,e) 初始条件：线性表L已存在，1≤i≤List Length(L)+1.操作结果：在L中第i个位置之前插入新的数据元素e，L长度加1。List Delete(&L,i,&e) 初始条件：线性表L存在非空，1≤i≤List Length(L).操作结果：删除L的第i个元素，并用e返回其值，L长度减1。 2． 程序包含四个模块： 1）主程序模块： void main() { 初始化； for（;;） {} while（命令=开始） { 接受命令； 处理命令； } for（;;） { } } 2）有序表单元模块——实现有序表的抽象数据类型； 3）节点结构单元模块——定义有序表的节点结构； 4）数据输入分析模块——判断输入数据正确有效； 各模块之间的调用关系如下： 主程序模块 ↓ 有序表结构模块 ↓ 节点结构单元模块 ↓ 数据输入分析模块 三、详细设计 1、结点类型，指针类型 TypedefstructLNode{ int code,date;//code 为人所在位置 date为人持有的密码 struct LNode *next; };// 结点类型，指针类型 2、构造单向循环链表 struct LNode *p,*head,*q;//定义头节点，和指针 for(i=2;i<=n;i++) { struct LNode *s=(struct LNode *)malloc(sizeof(struct LNode));//分配 新结点空间 s->code=i; input(s->date); p->next=s; p=p->next; } p->next=head;//根据输入的人数，进行单项循环链表的创建，p指向最后一个结点，并与头节点链接，形成单项循环链表 3、约瑟夫环的程序实现部分 while(n!=1)//判断输入人数，如为1则直接输出结果，不循环 { for(i=1，m=m%n;i { p=p->next; } q=p->next;//找到要删除节点 p->next=q->next;//找到要删除节点的后继，并连接新环m=q->date;//找到下一个密码 printf(“%d”,q->code); free(q);//释放已删除节点空间 n--;//链表长度减一 } printf(“%d”,p->code);//约瑟夫环的结果输出 4、其他函数代码 数值的输入限制 int input() { int y,k,z=0; char c;//元素类型 char a[4];//数组初始化 if(!z)//输入判断，确定位数字或控制字符且位置和密码不为零 { for(y=0;y<4;y++) { c=getch(); if(c>=48&&c<=57)//确定为输入数字 {a[y]=c; putch(c); } else { y--; if(c=='r')//确定输入为控制字符 即回车或者删除 break; else if(c==8) {a[y]='n'; y--;} continue; } } k=atoi(a);//确定最终输入数字的值 printf(“n”); z=k; if(z==0) printf(“ERROR!The number couldn't be 0!n”);// 输入为零，重新输入 } return(k);//数值的返回 5、函数的调用关系图反映程序层次结构 Main→input 四、调试分析 1、早期程序只写了约瑟夫环的实现部分，没有对输入数据进行筛选，调试的时候会经常出错。比如是输入字母，或者输入0，大于32767溢出； 2、早期的循环过程中没有进行优化，导致循环次数过多，浪费时间； 3、为了输出时美观，分别在input和main函数主体内做了两次，输入非零的判断，浪费了资源； 4、算法的时空分析 为了限制在输入过程中不会上溢，只在输入中限定为四个不全为零的数字，但是做的是do……while循环，复杂度为o（1）; 当n大于1时： 在数据输入中，链表的创建是for循环，时间复杂度为o（n-1） 在约瑟夫环实现程序中，为for循环。时间复杂度为o（m%n-1） 当n=1时，复杂度为o（1）。 五、用户手册 用户根据提示，先输入起始密码m，然后输入人数n，再根据人数，分别输入每个人的密码date，数值均不能为0，否则会提示重新输入，输入为字母则自动丢弃，输入错误可用删除键进行修改，输入完成后按回车键确定本次输入完毕（若输入数字大于9999，则第五位自动转换为下一个数字的起始位，依此类推）。 当n个数字全部输入完毕，则自动显示结果，按任意键则退出本程序。 六、测试结果 第一组：m 的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，出列顺序为6，1，4，7，2，1，3，5。 第二组： m 的初值为30；n=8，7个人的密码依次为：5，1，6，9，4，7，2，3，出列顺序为6，5，2，3，7，1，4，8。 第三组 : m 的初值为15；n=6，7个人的密码依次为：5，3，4，7，6，9，出列顺序为3，1，2，6，4，5。 七、附录 源程序头文件名清单： #include “malloc.h”//内存空间分配头文件 #include “stdio.h”//输入输出函数头文件 #include “stdlib.h”//input函数中字符串转短整形函数的头文件 #include “conio.h”//最后显示结果、清屏函数头文件第三篇：《数据结构》上机实验的目的和要求
第四篇：数据结构上机实验报告
第五篇：数据结构上机实验报告
点击咨询 