第一篇：数据结构课程设计报告
数据结构课程设计报告
数据结构课程设计报告
院系：计算机学院
班级：软件121班
姓名：程猛
学号：201200834122 题目：最小生成树
软件121 程猛 201200834122
数据结构课程设计报告
指导老师：杜献峰
一、引言..................................................................................................................4
二、设计题目..........................................................................................................4 1.问题描述...........................................................................................................4 2.系统要求...........................................................................................................4 3.测试数据...........................................................................................................5 4.实现提示...........................................................................................................5 5.参考文献...........................................................................................................5 6.运行环境...........................................................................................................6
三、需求分析..........................................................................................................6 1.如何选择存储结构去建立一个带权网络。...................................................6 2.如何在所选存储结构下输出这个带权网络。...............................................6 3.如何实现PRIM算法和Kruskal算法的功能。.............................................6 4.如何从每个顶点开始找到所有的最小生成树的顶点。...............................7 5.如何输出最小生成树的边及其权值。...........................................................7
四、概要设计..........................................................................................................7 2.图的存储结构...................................................................................................8 3.流程图...............................................................................................................8
五、详细设计..........................................................................................................9 1.主函数模块.......................................................................................................9 2.对路径权值进行排序.....................................................................................10
六、调试与分析....................................................................................................14
七、测试结果........................................................................................................17
软件121 程猛 201200834122 2
数据结构课程设计报告
八、设计心得体会................................................................................................17
附录（源代码）18
软件121 程猛 201200834122 3
数据结构课程设计报告
摘要
最小生成树是数据结构中图的一种重要应用，在图中对于n个顶点的连通网可以建立许多不同的生成树，最小生成树就是在所有生成树中总的代价最小的生成树。本课程设计是以邻接矩阵作为图的存储结构,分别采用Prim和Kruskal算法求最小生成树。Kruskal算法和Prim算法是求最小生成树的常用算法它们分别适用于稠密图和稀疏图。最小生成树的应用非常的广，如矿井通风设计和改造最优化方面以及如何搭建最短的网络线缆, 构建造价最低的通讯网络。
一、引言
本课程设计我们要解决的问题是图最小生成树问题。要用到图的先相关数据结构和求最小生成树的两种数据结构算法普里姆算法和克鲁斯卡尔算法，以及储存图的边和点的邻接矩阵。
本课程设计要解决的问题构造连通网的最小生成树 ,我们首先要做的是创建一个邻接矩阵，用以来存储图，然后我们要想好怎样利用普里姆算法和克鲁斯卡尔算法来构造最小生成树。把这两种算法写入主函数，调试好程序。最后写好报告。
二、设计题目 1.问题描述
若要在n个城市之间建设通信网络，只需要假设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。
2.系统要求
利用克鲁斯卡尔算法求网的最小生成树。利用普里姆算法求网的最小生成树。要求输出各条边及它们的权值。
软件121 程猛 201200834122 4
数据结构课程设计报告
3.测试数据
4.实现提示
通信线路一旦建成，必然是双向的。因此，构造最小生成树的网一定是无向图。设图的顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数，100则表示没有路径。
5.参考文献
[1] 严蔚敏.数据结构（C语言版）[M].北京：清华大学出版社,1997.[2] 谭浩强.C程序设计（第三版）[M].北京：清华大学出版社，2005.1.[3] 二霍红卫算法设计与分析〔」西安西安电子科技大学出版社，2005.113-127.[4] 陈杰.计算机专业课程设计中的需求分析[J].集美大学学报，2009，10(2)：89—92.[5] 高一凡.数据结构算法实现及解析[M ].西安:西安电子科技大学出版软件121 程猛 201200834122
数据结构课程设计报告
社, 2002 6.运行环境
VC++6.0
三、需求分析
1.如何选择存储结构去建立一个带权网络。
此问题的关键在于如何实现PRIM算法和Kruskal算法，实现的过程中如何得到构成最小生成树的所有顶点，此外输出也是一个关键问题所在，在此过程中经过了多次调试。
2.如何在所选存储结构下输出这个带权网络。
将图中的所有顶点存储到一个一维数组中，通过一个二维数组用邻接矩阵连实现对各边权值的存储
3.如何实现PRIM算法和Kruskal算法的功能。
首先我们对prim算法的问题进行大致的概要分析：
假设N=（V，{E}）是连通网，TE是N上最小生成树中边的集合。算法从U={u0}（u0∈V），TE={}开始，重复执行下述操作：在所有u∈U，v∈V-U的边（u，v）∈E中找一条代价最小的边（u0,v0）并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=(V,{TE})为N的最小生成树。
克鲁斯卡尔算法从另一种途径求网的最小生成树：
假设连通网N=(V,{E})，则另最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{})，图中每个顶点自成一个连通分量。在E中选择代价最小的边若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。以此类推直至T中的软件121 程猛 201200834122
数据结构课程设计报告
所有顶点都在同一连通分量上为止。
4.如何从每个顶点开始找到所有的最小生成树的顶点。
对于prim算法从图的点集中任取一个顶点作为起始顶点，然后找到依附于该顶点的所有边选取权值最小的，依次找下去直至图中所有顶点都在一个点集中为止。对于克鲁斯卡尔算法则通过对权值进行排序找出权值最小的顶点和边并把该边的顶点并入点集之中。
5.如何输出最小生成树的边及其权值。
通过访问数组来实现对最小生成树边和权值的输出。
四、概要设计
1、设定图的抽象数据类型: ADT Graph{ 数据对象V:V是具有相同特性的数据元素的集合,称为点集.数据关系R: R={VR} VR={(v,w)|v,w属于V,(v,w)表示v和w之间存在的路径} 基本操作P: CreatGraph(&G,V,VR)初始条件:V是图的顶点集,VR是图中弧的集合.操作结果:按V和VR是定义构造图G.Sort(edge* ,MGraph *)初始条件: 图G存在，各边权值已知； 操作结果:对权值进行排序； Find(int *, int)初始条件:前者为已存在的集合，后者为集合中的元素； 操作结果:查找函数，确定后者所属子集； Swapn(edge *, int, int)初始条件: 图G存在，各边权值已知； 操作结果:交换某两个边的权值；
软件121 程猛 201200834122
数据结构课程设计报告
2.图的存储结构
typedef struct {
int vexnum,arcnum;}ALGraph;typedef struct //边的结构体定义 {
int begin,end;//边的开始和结束顶点
int cost;//权值 }EDGE;typedef struct {
int edges[max][max];//
int n,e;}MGraph;3.流程图
软件121 程猛 201200834122
数据结构课程设计报告
五、详细设计
在该函数中有6个模块，分别是主函数模块、路径权值进行排序、交换顶点及权值模块、判断是否回环、prim算法的实现、Kruskal算法的实现。
1.主函数模块
ALGraph G;MGraph G2;int v,i,j;char a;do {
system(“cls”);
cout<<“t***********************************nn”;
cout<<“t
克鲁斯卡尔
n”;
cout<<“t
普
里
姆
n”;
cout<<“t
退
出
nn”;
cout<<“t***********************************n”;
cout<<“请输入序号：”;
cin>>a;
switch(a)
{
case '1': MiniSpanTree_Kruskal(G);system(“pause”);break;
case '2': cout<<“请输入结点数：”;
cin>>G2.n;
for(j=1;j<=G2.n;j++)
{
cout<<“请输入第”< for(i=1;i<=G2.n;i++) cin>>G2.edges[j][i]; } cout<<“请输入开始顶点:”; cin>>v; MiniSpanTree_PRTM(G2,v);system(“pause”);break;软件121 程猛 201200834122 数据结构课程设计报告 default : break; } }while(a!='3');return 0; 该模块包含菜单的设计以及通过一个switch语句来实现对prim算法和Kruskal算法的实现。进入主菜单后选择相应的序号执行相应的操作，每进行一步后，按任意键继续进行下一个操作可重复执行。 2.对路径权值进行排序 void Sort(EDGE *edges,ALGraph G)//对带权路径从小到大排序 { int i,j;for(i=1;i<=G.arcnum;i++)for(j=i;j<=G.arcnum;j++)if(edges[i].cost>edges[j].cost)Swapn(edges,i,j);} 在图中找到权值最小的边 3.交换顶点及权值 void Swapn(EDGE *edges,int i,int j)// 交换的两个顶点及权值 { int temp;temp=edges[i].begin;edges[i].begin=edges[j].begin;edges[j].begin=temp;temp=edges[i].end;edges[i].end=edges[j].end;edges[j].end=temp;temp=edges[i].cost;edges[i].cost=edges[j].cost;edges[j].cost=temp;软件121 程猛 201200834122 数据结构课程设计报告 } 该模块主要用于Kruskal算法，找到图中权值最小的一条边，然后交换它们的顶点和权值。 4.判断是否回环 int Find(int *parents,int f)//判断是否形成环 { while((parents[f])>0&&(f!=parents[f]))f=parents[f];return f;} 在Kruskal算法中初始parents[]为0来设置访问未访问标志，以此来判断图是否成环。 5.prim算法的实现 void MiniSpanTree_PRTM(MGraph &G,int v){ int closedge[max];int lowcost[max];int i,j,k,min;for(i=1;i<=G.n;i++){ lowcost[i]=G.edges[v][i]; closedge[i]=v;} for(i=1;i min=INF; for(j=1;j<=G.n;j++) if(lowcost[j]!=0&&lowcost[j] { min=lowcost[j]; k=j; } 软件121 程猛 201200834122 数据结构课程设计报告 } } printf(“边(%d,%d)权为:%dn”,closedge[k],k,min);lowcost[k]=0;for(j=1;j<=G.n;j++)if(G.edges[k][j]!=0&&G.edges[k][j] void MiniSpanTree_Kruskal(ALGraph &G)//MiniSpanTree_Kruskal()函数实现 { int i,s,v1,v2,value,bnf,edf; int parents[MAX_VERTEX_NUM]; EDGE edges[MAX_VERTEX_NUM]; cout< cin>>G.vexnum; //输入顶点数 cout<<“请输入边数: ”; cin>>G.arcnum; //输入边数 cout<<“请输入(V1和V2), 例如:(V1=1,V2=3),(V1=2,V2=4)...”; cout< //输入arc(v1,v2) for(i=1;i<=G.arcnum;++i) { cout< cin>>v1; //输入头顶点 cout<<“请输入第 ”< cin>>v2; //输入尾顶点 cout<<“请输入第 ”< : ”; cin>>value; //输入边的权值 edges[i].begin=v1; edges[i].end=v2; while(v1<1||v1>G.vexnum||v2<1||v2>G.vexnum) //如果输入的非法，重新输入 { 软件121 程猛 201200834122 数据结构课程设计报告 cout<<“输入不合法，请重新输入！”; cout< cin>>v1; cout<<“请输入第 ”< cin>>v2; cout<<“请输入第 ”< : ”; cin>>value; edges[i].begin=v1; edges[i].end=v2; } edges[i].cost=value;} Sort(edges,G); //调用Sort()函数 cout<<“按照排列好的序列逐个输出权值”< //初始化array parents[] cout< for(i=1,s=1;s<=G.vexnum&&i<=G.arcnum;i++) { bnf=Find(parents,edges[i].begin); edf=Find(parents,edges[i].end); if(bnf!=edf) { parents[bnf]=edf; cout< //输出最小生成树 cout< cout< s++; } } } 软件121 程猛 201200834122 13 数据结构课程设计报告 六、调试与分析 测试数据如下图 求该图的最小生成树 1.进入主页面 2.利用克鲁斯卡尔算法求最小生成树 选择序号1使用克鲁斯卡尔算法求图的最小生成树。 软件121 程猛 201200834122 14 数据结构课程设计报告 输入每条边的顶点和权值 对权值进行排序，并且输出最小生成树。 软件121 程猛 201200834122 15 数据结构课程设计报告 3.利用prim算法求最小生成树 选择序号2用prim算法求最小生成树。通过一个n阶的邻接矩阵来实现图的输入 输入起始顶点然后输出最小生成树的各边及其每一条边的权值。 4.退出程序 选择序号3退出程序 软件121 程猛 201200834122 16 数据结构课程设计报告 七、测试结果 克鲁斯卡尔算法求得的最小生成树为352146 Prim算法求得的最小生成树为125346 八、设计心得体会 在我的努力下，课程设计终于完成，由于我们对数据结构和c语言不是很了解，有时忽略了一些关键的细节，使得在编写程序的过程中出现了一些问题。对于打字有时粗心导致出现一些难以发现的小错误，在我的耐心，细致的调试下最终使得程序能够运行，课程设计圆满完工。 软件121 程猛 201200834122 数据结构课程设计报告 问题一：求出图中的最小值 现象：求出的最小值是0 原因：图中没有连通的两个顶点之间的权值赋值为0 问题二：求最小生成树时，else语句需再调用一个函数 现象：对某些二叉树能求出最小生成树，但不能普遍适应 原因：对于找最小生成树边的各种可能没有考虑全面，代码才没有广泛的适应性 问题三：两个顶点之间的边是否是最小生成树的边 现象：代码的功能不能分辨出是否是最小生成树的边 原因：把简单的代码写的很复杂，从而杂乱无章出现错误。 在课设过程中，遇到许多问题，通过查阅资料和课本。是我对数据结构有了更进一步的认识。当然，这中间也有其他人的帮助。我的同学，以及指导老师都给我提出了非常宝贵的意见。通过与同学和老师的交流，使我找到了数据结构这门课程的学习方法。但是，我感觉这不仅仅是数据结构的学习方法，他或许就是学习软件工程这门专业的方法，那就是多动手。的确如此，对于一个算法，你知道它的算法思想和用计算机实现它却是另外一回事。这门课程，不仅需要我们用心去理解每一种算法的思想，更需要我们去动手来实现它。 附录（源代码） #include “iostream” using namespace std;#define MAX_VERTEX_NUM 30 //定义最大顶点数 #define MAXQSIZE 100 #define max 20 #define INF 10 typedef struct { int vexnum,arcnum;}ALGraph; typedef struct //边的结构体定义 { 软件121 程猛 201200834122 数据结构课程设计报告 int begin,end;//边的开始和结束顶点 int cost;//权值 }EDGE; ////////////////////////////// typedef struct { int edges[max][max];// int n,e;}MGraph; void Swapn(EDGE *edges,int i,int j); // 交换的两个顶点及权值 void Sort(EDGE *edges,ALGraph G); //对带权路径从小到大排序 int Find(int *parents,int f); //判断是否形成环 void MiniSpanTree_Kruskal(ALGraph &G);//MiniSpanTree_Kruskal()函数实现 void Swapn(EDGE *edges,int i,int j)// 交换的两个顶点及权值 { int temp;temp=edges[i].begin;edges[i].begin=edges[j].begin;edges[j].begin=temp;temp=edges[i].end;edges[i].end=edges[j].end;edges[j].end=temp;temp=edges[i].cost;edges[i].cost=edges[j].cost;edges[j].cost=temp;} void Sort(EDGE *edges,ALGraph G)//对带权路径从小到大排序 { 软件121 程猛 201200834122 数据结构课程设计报告 int i,j;for(i=1;i<=G.arcnum;i++)for(j=i;j<=G.arcnum;j++)if(edges[i].cost>edges[j].cost)Swapn(edges,i,j);} int Find(int *parents,int f)//判断是否形成环 { while((parents[f])>0&&(f!=parents[f]))f=parents[f];return f;} void MiniSpanTree_Kruskal(ALGraph &G)//MiniSpanTree_Kruskal()函数实现 { int i,s,v1,v2,value,bnf,edf; int parents[MAX_VERTEX_NUM]; EDGE edges[MAX_VERTEX_NUM]; cout< cin>>G.vexnum; //输入顶点数 cout<<“请输入边数: ”; cin>>G.arcnum; //输入边数 cout<<“请输入(V1和V2), 例如:(V1=1,V2=3),(V1=2,V2=4)...”; cout< //输入arc(v1,v2) for(i=1;i<=G.arcnum;++i) { cout< cin>>v1; //输入头顶点 cout<<“请输入第 ”< cin>>v2; //输入尾顶点 cout<<“请输入第 ”< : ”; cin>>value; //输入边的权值 软件121 程猛 201200834122 数据结构课程设计报告 edges[i].begin=v1; edges[i].end=v2; while(v1<1||v1>G.vexnum||v2<1||v2>G.vexnum) //如果输入的非法，重新输入 { cout<<“输入不合法，请重新输入！”; cout< cin>>v1; cout<<“请输入第 ”< cin>>v2; cout<<“请输入第 ”< : ”; cin>>value; edges[i].begin=v1; edges[i].end=v2; } edges[i].cost=value;} Sort(edges,G); //调用Sort()函数 cout<<“按照排列好的序列逐个输出权值”< //初始化array parents[] cout< for(i=1,s=1;s<=G.vexnum&&i<=G.arcnum;i++) { bnf=Find(parents,edges[i].begin); edf=Find(parents,edges[i].end); if(bnf!=edf) { parents[bnf]=edf; cout< //输出最小生成树 cout< cout< s++; } } 软件121 程猛 201200834122 数据结构课程设计报告 } /////////////////////// void MiniSpanTree_PRTM(MGraph &G,int v){ int closedge[max];int lowcost[max];int i,j,k,min;for(i=1;i<=G.n;i++){ lowcost[i]=G.edges[v][i]; closedge[i]=v;} for(i=1;i min=INF; for(j=1;j<=G.n;j++) if(lowcost[j]!=0&&lowcost[j] { min=lowcost[j]; k=j; } printf(“边(%d,%d)权为:%dn”,closedge[k],k,min); lowcost[k]=0; for(j=1;j<=G.n;j++) if(G.edges[k][j]!=0&&G.edges[k][j] { lowcost[j]=G.edges[k][j]; closedge[j]=k; } } } int main(){ ALGraph G;软件121 程猛 201200834122 数据结构课程设计报告 MGraph G2;int v,i,j;char a;do { system(“cls”); cout<<“t***********************************nn”; cout<<“t 克鲁斯卡尔 n”; cout<<“t 普 里 姆 n”; cout<<“t 退 出 nn”; cout<<“t***********************************n”; cout<<“请输入序号：”; cin>>a; switch(a) { case '1': MiniSpanTree_Kruskal(G);system(“pause”);break; case '2': cout<<“请输入结点数：”; cin>>G2.n; for(j=1;j<=G2.n;j++) { cout<<“请输入第”< for(i=1;i<=G2.n;i++) cin>>G2.edges[j][i]; } cout<<“请输入开始顶点:”; cin>>v; MiniSpanTree_PRTM(G2,v);system(“pause”);break; default : break; } }while(a!='3');return 0;} 软件121 程猛 201200834122 23 数据结构课程设计 散列表的应用:插队买票 专业 计算机科学与技术（网络技术） 金玲 计算机131 1310704114 张静林 2015年1月23日 学生姓名 班学级 号 指导教师 完成日期 目录概述……………………………………………………………………………………1 1.1 课程设计目的……………………………………………………………………….1 1.2 课程设计内容……………………………………………………………………….1 2 系统需求分析……………………………………………………………………….1 2.1 主体功能…………………………………………………………………………....2 3系统概要设计…………………………………………………………………………2 3.1 系统流程图………………………………………………………………………….2 4 系统详细设计…………………………………………………………………………3 5 测试……………………………………………………………………………………5 5.1 测试方案…………………………………………………………………………….5 5.2 测试结果…………………………………………………………………………….5 6 小结……………………………………………………………………………………5 参考文献…………………………………………………………………………………5 附录………………………………………………………………………………………7 附录1 源程序清单……………………………………………………………………...7 概述 1.1 课程设计目的 数据结构课程设计是为数据结构课程独立开设的实践性教学环节。数据结构课程设计对于巩固数据结构知识，加强学生的实际动手能力和提高学生综合素质是十分必要的。课程设计的目的： 1．要求学生达到熟练掌握C语言的基本知识和技能。 2．了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。3．提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 4．培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。 5．初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。 1.2课程设计内容 本课程设计的任务是写一个程序模拟这种情况。每个队伍都允许插队。如果你在排队，有一个以上的朋友要求插队，则你可以安排他们的次序。每次一个人入队，并且如果这个入队的人发现队伍中有自己的朋友，则可以插入到这个朋友的后面；当队伍中的朋友不止一个的时候，这个人会排在最后一个朋友的后面；如果队伍中没有朋友，则他只能够排在这个队伍的最后面。每一个入队的人都先进行上述的判断。当队伍前面的人买到车票之后，依次出队。系统需求分析 2.1 主体功能 程序从“input.txt”文件读入测试用例，一个文件可包含多个测试用例。每个用例的第一行是朋友组的数目n（1<=n<=1000)。对于一个朋友组以朋友的数目j（1<=j<=1000）开始，由朋友的个数以及他们的名字组成，一个空格后接该组朋友的名字，以空格分开，并且每个人的名字都不同。每个名字不超过四个字母，由{A，B，...，Z，a，b，...，z}组成。一个朋友组最多有1000个人，每个人只属于一个朋友组。n=0时，测试数据结束。 下面是一些具体命令：.ENQUEUE——X入队;.DEQUEUE——排队头的人买票，离开队伍，即出队；.STOP——一个测试用例结束。 测试结果输出到“output.txt”文件中。每个测试用例第一行输出“Scenario#k”，k是测试用例的序号（从1开始）。对每一个出队命令，输出刚买票离开队伍的人名。两个测试试用例 之间隔一空行，最后一个用例结束不输出空行。系统概要设计 3.1 系统流程图 系统详细设计 本题目主要解决两个问题：一是怎么存放和查找大量数据（主要是姓名）；二是怎么操作“ENQUEUE”和“DEQUEUE”命令。 用散列表来存放和查找数据。由于最多有1000个朋友组，每组最多有1000人，使用平方探测法解决冲突，则表的大小是2*（1000*1000），所以选择TableSize=2000003（2000003是大于2000000的最小素数）。同一个组内的都是朋友，所以每个人除了记录他的名字name，还要记录他属于哪个组group，另外用info来表示该单元是否被占用，数据结构如图4.1所示。散列函数是根据Honer法则计算一个以64为阶的多项式，如图4.2所示。冲突解决方法采用平方探测法，如图4.3所示。 #define TabSize 2000003 typedef struct hashtab *PtrToHash;struct hashtab /*散列表数据结构*/ { char name[5]; /*名字*/ int group; /*属于哪个朋友组*/ char info; /*标志位，该单元是否被占用*/ };图4.1数据结构：散列表 Int Hash(char *key,int TableSize){ Int HashVal=0; While(key!=NULL) HashVal=(HashVal<<6)+*key; Return HashVal%TableSize;} 图4.2散列函数 Long int Find(PtrToHash hash,char *c){ key=c; CurrentPos=Hash(key,TableSize); CollisionNum=0; While((单元被占用)and(单元内的名字与查找的名字不同)) { CurrentPos+=2*(++CollisionNum)-1; If(CurrentPos>=TabSize) CurrentPos=TabSize; } Return CurrentPos;} 图4.3用平方探测法解决冲突 第二个问题是关于怎么操作“ENQUEUE”和“DEQUEUE”命令。这可以用队列来模拟。由于有插队现象的存在，不能单纯的用一个数组来表示队列，因为这样的话，插入一个朋友，则他后面的人都要往后移一个单位，删除一个人，则他后面的人都要前移一个，会降低效率。所以，采用一个Index标记来表示当前元素的后继元素，最后一个单元的后继元素是第0个，形成环，数据结构如图4.4所示。不用链表是因为链表存放指针也需要空间，并且链表插入、删除的效率没有数组高。 typedef struct Que *PtrToQue;struct Que /*队列数据结构*/ { long int HashVal; /*散列值*/ long int Index; /*在中的队列序号*/ };图4.4数据结构：队列 输入ENQUEUE命令，如果队伍里有朋友，则排在朋友后面；如果没有朋友，则排在队尾。入队时，用一个数组记录每个朋友组的最后一位，以便下一个朋友到来时排到他后面，这个数组被称为“插队数组”。 输入DEQUEUE命令，则根据“先进先出”，按照各个元素和它后继元素的先后顺序，每次删除队列重的第一个。程序结构如图4.5所示。 While(读测试文件){ if(输入”ENQUEUE”) { 读入名字； 插入散列表； 插入队列； } else if(输入”DEQUEUE”) { 删除队列第一个名字； 将该名字输出到文件； } else stop;} 图4.5入队、出队操作 测试 5.1 测试方案 按输入要求输入正常测试数据，测试程序是否能正确解决问题，得到正确答案。应注意边界测试。例如，将n，j分别取为1的用例和n为1000的用例。n，j比较大时需写程序生成测试用例。 不按输入要求输入数据，测试程序能否对输入内容进行数据合法性检测并进行相应的异常处理。例如，将n或j取为小于1或大于1000的数，名字超过4个字母等情况下的测试用例。5.2 测试结果 小结 在前面的学习过程中我们学到了很多知识而这次课程设计又是对我们所学的 一次总结，刚开始，可以说是没有头绪，于是就去图书馆找资料，找到了一些关于程序方面的，可这远远不够，这只是小小的开始。我们必须掌握很多已学的知识才能很好的完成本次的课程设计。在这次课程设计中，总的感觉是我遇到了很多困难这主要是由于我编写代码的经验不足，有时虽然是一个很小的问题但解决起来却花费了我不少的时间，值得欣慰的是，当自己苦思冥想或者和其它同学一起探讨把问题解决的时候我还是觉得获益非浅，这就是在摸索中寻求到的知识。在设计时也免不了存在着些不足，所以在今后的学习中我会努力取得更大的进步。虽然对着电脑做程序，有些累，可当看到劳动成果时，却有另一番滋味。 参考文献 [1]范策，周世平，胡晓琨.《算法与数据结构（C语言版）》[M].北京：机械工业出版社，2004 [2]严蔚敏.《数据结构（C语言版）》.北京：清华大学出版社，2004 [3]许卓群，杨冬青，唐世渭，张铭.《数据结构与算法》.北京：高等教育出版社，2004 [4]徐孝凯.《数据结构实用教程（第二版）》.北京：清华大学出版社，2006 附录 附录1 源程序清单 #include /*散列表大小TabSize 是大于表最大空间的素数*/ #define Max 1000001 /*队列空间最大值*/ struct hashtab;typedef struct hashtab *PtrToHash;struct hashtab /*散列表数据结构*/ { char name[5]; /*名字*/ int group; /*属于哪个朋友组*/ char info; /*标志位，该单元是否被占用*/ };struct Que;typedef struct Que *PtrToQue;struct Que /*队列数据结构*/ { long int HashVal; /*散列值*/ long int Index; /*在中的队列序号*/ }; int hashedx=0; /*标记元素是否已经在散列表里*/ long int Find(PtrToHash hash,char *c)/*查找在散列表中的位置*/ { char *key;long int CurrentPos,CollisionNum; key=c;for(CurrentPos=0;*key;++key) /*散列函数，计算散列值*/ CurrentPos=(CurrentPos<<6)+*key;CurrentPos%=TabSize; /*散列值*/ CollisionNum=0;/*如果当前单元被占用：单元内的元素与当前操作的名字不同，使用平方探测法解决冲突；与当前操作的名字相同，则直接返回在散列中的位置*/ while((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c))) { /*平方探测法*/ CurrentPos+=2*(++CollisionNum)-1; if(CurrentPos>=TabSize) CurrentPos-=TabSize;} if((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c)==0)) /*元素已经在散列表里*/ hashedx=1;else /*元素不在散列表里*/ hashedx=0;return CurrentPos;/*返回在散列表中的位置*/ } int main(){ long int Find(PtrToHash hash,char *c); /*查找在散列表中的位置*/ PtrToHash hash; /*散列表*/ PtrToQue queue; /*队列*/ int *grouppos; /*记录每个朋友组的最后一位，即插队数组*/ int n; /*测试用例数目*/ int num; /*当前测试用例序号*/ long int i,ii,j,key,temp;long int head,last; /*队列的头和尾*/ char c[8],tempc[8]; /*名字*/ FILE *fpin,*fpout; /*输入、输出文件指针*/ if(!(fpin=fopen(“input.txt”,“r”))) /*打开测试文件*/ { printf(“fopen error!”); /*文件打开错误*/ return-1;} if(!(fpout=fopen(“output.txt”,“w”))) /*打开输出文件*/ { printf(“fopen error!”); return-1;} hash=(PtrToHash)malloc(sizeof(struct hashtab)*TabSize);/*为散列表申请空间*/ queue=(PtrToQue)malloc(sizeof(struct Que)*Max);/*为队列申请空间*/ grouppos=(int *)malloc(sizeof(int)*1000);/*申请空间记录每个朋友组的最后一位*/ for(i=0,j=1;i queue[i].Index=j;queue[i-1].Index=0;/*最后一个单元的后继单元是第0个，形成环*/ num=0;for(fscanf(fpin,“%d”,&n);n;fscanf(fpin,“%d”,&n))/*输入当前测试用例的朋友组数*/ { if(n<1||n>1000) /*处理异常输入n*/ { fprintf(fpout,“n is out of rangen”); return-1; } num++; if(num!=1) /*两个测试用例间输入一空行*/ fprintf(fpout,“n”); for(i=0;i hash[i++].info=0; /*初始化散列表，标记位置0*/ for(i=0;i /*对每一组朋友*/ { fscanf(fpin,“%d”,&j); /*当前组里的人数*/ if(j<1||j>1000) /*处理异常输入j*/ { fprintf(fpout,“j is out of rangen”); return-1; } for(;j;--j) { fscanf(fpin,“%s”,c); /*输入名字*/ for(ii=0;ii tempc[ii]=' '; strcpy(tempc,c); ii=0; while(tempc[ii]!=' ') /* 是否由四个以内字母组成*/ { if(tempc[ii]<'A'||('Z' { fprintf(fpout,“Group %d: Nonstandard namen ”,i); return-1; } ii++; } key=Find(hash,c); /*找到在散列表中的位置*/ if(hashedx==1)/*重名*/ { fprintf(fpout,“repeated name %sn”,c); return-1; } strcpy(hash[key].name,c);/*插入散列表*/ hash[key].info=1; /*标记置1，该单元被占用*/ hash[key].group=i; /*记录他属于哪个组*/ } } for(i=0;i<1000;) grouppos[i++]=0;/*初始化插队数组*/ head=0; /*初始化队列头、尾标记*/ last=0;fprintf(fpout,“Scenario #%dn”,num);/*输出当前用例序号到文件*/ for(fscanf(fpin,“%s”,c);;fscanf(fpin,“%s”,c))/*输入命令*/ { if(*c=='E') /*入队命令*/ { fscanf(fpin,“%s”,c); /*输入名字*/ key=Find(hash,c); /*查找在散列表中的位置*/ if(hashedx==0)/*散列表里没这个人*/ { fprintf(fpout,“no %sn”,c); return-1;} temp=queue[0].Index; /*队列第0个位置记录队尾的后继单元*/ queue[0].Index=queue[temp].Index; /*在队列中申请一个新单元，队尾标记后移一个位置 */ queue[temp].HashVal=key;/*入队*/ if(!head)/*如果是队列里的第一个元素 */ last=head=temp;/*队头、队尾标记指向第一个元素*/ if(!grouppos[hash[key].group])/*如果队列里没朋友*/ { queue[temp].Index=0;/*队尾指向对头，形成环*/ queue[last].Index=temp;/*前一次队尾的后继元素是当前元素*/ last=temp; /*队尾标记指向当前元素*/ grouppos[hash[key].group]=temp;/*插队数组记录该朋友组里已入队的最后一位*/ } else/*如果队列中已经有他的朋友*/ { queue[temp].Index=queue[grouppos[hash[key].group]].Index; /*插队到朋友的后面*/ queue[grouppos[hash[key].group]].Index=temp; /*插队到朋友后面一位的前面*/ grouppos[hash[key].group]=temp; /*替换插队数组里该组的元素为当前元素*/ if(hash[queue[last].HashVal].group==hash[key].group) /*如果当前元素和前一元素是朋友，队尾标志指向当前元素*/ last=temp; } } else if(*c=='D')/*出队命令*/ { if(last==0) /*不能对空队列执行出队命令*/ { fprintf(fpout,“Empty queue!nCan't execute DEQUEUE!n”); return-1; } fprintf(fpout,“%sn”,hash[queue[head].HashVal].name); /*输出队头元素到文件*/ temp=head; head=queue[temp].Index; /*队列第一位出队，队头标记后移一位*/ queue[temp].Index=queue[0].Index; /*队列第0个元素后移一位*/ queue[0].Index=temp; /*释放空间*/ if(grouppos[hash[queue[temp].HashVal].group]==temp) /*当前删除的元素是该朋友组在队列里的最后一位*/ grouppos[hash[queue[temp].HashVal].group]=0; if(last==temp) /*出队后，队列为空*/ last=0; } else /*输入 “STOP”*/ break; /*测试结束*/ } } fprintf(fpout,“b”);fclose(fpin);fclose(fpout);return 1;} 正文要求：对每一个题目，正文必须包括以下几个方面 知识点回顾： 实验要求： 实验过程：包括设计思路，算法描述，程序清单，调试等等； 实验小结： 注意：（1）正文中字体用小四号宋体，行间距1.25倍行距； （2）页码居中； （3）A4纸双面打印，在纸的左侧装订。 （4）上交的课程设计报告控制在10页以内。 齐鲁工业大学 理学院 信计11-1 郑桥 一、提示：对于单窗口的服务系统知识点回顾如下： 1、什么是负指数分布？ 又称指数分布。泊松事件流的等待时间（相继两次出现之间的间隔）服从指数分布。用于描述非老化性元件的寿命（元件不老化，仅由于突然故障而毁坏）。常假定排队系统中服务器的服务时间和Petri网中变迁的实施速率符合指数分布。 2、用C语言如何产生随机序列？ double rd_MN1(double m,double n){ double r;if(m>n){r=n;n=m;m=r;};r =((double)rand()/((double)(RAND_MAX)+(double)(1)));r = m+ r*(n-m);return r;} 3、用C语言如何产生负指数分布的时间序列？ double expntl(double x){ double z;do { z =((double)rand()/ RAND_MAX);} while((z == 0)||(z == 1));return(-x * log(z));//z相当于1-x,而x相当于1/lamda。} 其中的x相当于1/λ 4、排队论简单叙述； 排队系统主要有：X/Y/Z，其中X表示到达时间间隔的分布，Y表示服务时间的分布，Z表示并列的服务设备的数目。表示相继到达的时间间隔或服务时间的分布的符号是： M——负指数分布，D——确定性，Ek——k阶Erlang，GI——相互独立的一般随机分布，G——一般的随机分布。 例如：M/M/1表示达到时间间隔为负指数分布，服务时间为负指数分布，单服务设备的排队系统。 这里我们用静态仿真的思想来实现M/M/1仿真。在排队系统中的每一个动态实体的状态可以有三个量来反映：与前一个实体到达的时间间隔，在排到自己服务前的等待时间以及服务时间。其中服务时间和到达时间间隔服从指数分布，不受别的因素的影响。开始服务前的等待时间则受到排在前面的动态实体的状态的影响。其更新算法如下： 即：如果某个实体到达以后，发现处在它前面的动态实体已经结束服务，所以这个实体就不用等待，直接接受服务；反之，处在它前面的动态实体如果没有结束服务（包括没有开始服务），则这个实体的等待时间就是它前一实体结束服务的时刻减去它到达的时刻。 5、如何得到每个顾客的到达时刻，服务时间，等待时间和离开时刻； 到达时间=前面各个到达时间之和； 服务时间就是负指数随机生成的时间； 等待时刻：如果前一个人的离开时间小于这个人的到达时间，等待时间=0； 如果不是，则等待时间=该人的离开时间-他的到达时间-服务时间 6、如何排队，排队的主要算法思想？ 排队就是来到的人数多于离开的人数； 如果下一个人到达时前一个人依旧在接受服务，则此人就要排队。 7、如何求队长？以及最大的队长？ 假设以5分钟为一个时间段，则在第5分钟时用这5分钟内来到的人数减去这5分钟内离开的人数即是排队人数 8、如何求平均等待时间？ 求平均等待时间首先要求出总的等待时间与接受服务的人数； 总的等待时间=每个人的等待时间之和；接受服务的人数由时间540分钟来控制，如果在540分钟之后才到达的人则不再算入接受服务的人数之内。 9、用C语言如何将得到的数据输出到文件？ 在C语言中用fopen函数打开文件，然后把数据输出比如用fprintf函数，最后fclose。 利用ofstream fcout(“d:arr_time.txt”);语句来实现C++中的输出文件 10、如何用已学的数学语言程序（如：Mathematica, Matlab）把C语言得到的数据文件画出其相应的图像？ 11、如果是两个窗口的服务系统，则该怎么修改程序？ 12、如果到达时间间隔，服务时间服从泊松分布或者其他分布，该程序该如何改进？ 二、数据结构课程设计题目 单窗口的排队模型的数值仿真（参考课本上第四章的离散事件模拟）要求如下：（1）要求相邻两个顾客的到达时间间隔服从负指数分布；且每个顾客接受服务的时间也服从负指数分布； （2）求出各个时刻的队长（以五分钟为一时间单位，即求零时刻的队长，五分钟时的队长，十分钟时的队长，依次类推）； （3）一个工作日内的顾客总数，约定8：30上班，17：30下班，中午不休息；（4）求平均等待时间（顾客总等待时间除以总人数）； （5）画出顾客的到达，离开图像（横坐标是顾客图，纵坐标是到达时刻，和离开时刻）； （6）画出队长变换图像（横坐标是时刻图，纵坐标是队长个数）；（7）求出一个工作日内的最大队长； 三、设计思路： 1）把8：:30记做第0分钟，17:30记做第540分钟。 2）首先利用C++随机生成200个服从负指数分布的到达时间与200个服务时间 然后根据随机生成的数计算到达的时刻，即到达时间的逐步加和，然后计算离开的时刻； 3）根据到达时刻与离开时刻来计算等待时刻，于是便可得到平均等待时间； 同时根据这两个时刻求出每5分钟到达人数与离开的人数，于是便得出每5分钟的队长，同时也可求出最大队长。4）再利用MATLAB画出相应的图像。 四、算法描述： 1）首先将8:30这个时刻化为0时刻，17:30化为第540分钟这个时刻，全体单位为分钟。 2）定义到达时间间隔arr_time[200]，服务时间ser_time[200]，到达时刻arr_time1[200],离开时间lea_time[200],等待时间sta_time[200],离开人数lea_num[200],到达人数arr_num[200]等变量。3）根据负指数函数 来利用C++程序生成随机到达时间间隔与服务时间。 4）利用到达时刻与离开时刻之间的关系来求出等待时间。同时将这540分钟划分为5分钟间隔的108个时间段来求出在每个时间段到达人数与离开人数，再求出队长。 5）利用已知的服务人数，平均到达时间与平均离开时间来做出图像。（借助MATLAB软件。） 五、总结 （1）求出各个时刻的队长（以五分钟为一时间单位，即求零时刻的队长，五分钟时的队长，十分钟时的队长，依次类推）；见程序清单中数据部分对长。（2）求平均等待时间（顾客总等待时间除以总人数）；根据程序可得，平均等待时间为21.6分钟。 （3）画出顾客的到达，离开图像（横坐标是顾客图，纵坐标是到达时刻，和离开时刻）； ***0100806040200 0Arrive curveleave curve***600 （6）画出队长变换图像（横坐标是时刻图，纵坐标是队长个数）； 25Queue Length Curve 20151050 ***0600 （7）求出一个工作日内的最大队长： 最大对长为16个人在排队。 六、程序清单： 求随机产生负指数 #include #include void main(){ long int i,k;double m,n;//m,n控制时间间隔 double r;double a,s,sum;//arr为到达时间，ser为服务时间 double LAM=1.2; //f(x)=LAM*exp(-LAM*x);double arr_time[200];double ser_time[200];ofstream fcout(“d:arr_time.txt”);ofstream fscout(“d:ser_time.txt”);m=2.0;n=5.0;srand((unsigned)time(NULL)); k=0;loop: r=((double)rand()/((double)(RAND_MAX)+(double)(1))); a =-log(r)/LAM;if(a >= m && a <= n){ arr_time[k]=a; k++;};if(k < 200)goto loop; // 产生200个指数分布随机数 for(i=0;i<200;i++){ fcout< //cout< if(i!=0 && i%5==0) //cout< fcout< s =-log(r)/LAM;if(s >= m && s <= n){ ser_time[k]=s;k++;};if(k < 100)goto loop1; // 产生200个指数分布随机数 m=3.0;n=5.5; srand((unsigned)time(NULL));k=100;loop2: r=((double)rand()/((double)(RAND_MAX)+(double)(1))); s =-log(r)/LAM;if(s >= m && s <= n){ ser_time[k]=s;k++;};if(k < 200)goto loop2; // 产生200个指数分布随机数 for(i=0;i<200;i++){ fscout< //cout< if(i!=0 && i%5==0) //cout< fscout< #include double sta_time[200];//等待时间 double arr_time[200];//随机生成到达时间 double ser_time[200];//随机生成服务时间 double arr_time1[200];//到达时间 ifstream fcin(“d:arr_time.txt”);ifstream fscin(“d:ser_time.txt”);ofstream fcout(“d:arr_time1.txt”);ofstream flcout(“d:lea_time.txt”);ofstream fscout(“d:sta_time.txt”); //求到达的时间 for(i=0;i<200;i++){ fcin>>arr_time[i]; arr_time1[i]=arr_time[i];} double sum=0.0;for(i=0;i<200;i++){ sum+=arr_time1[i]; arr_time1[i]=sum;} for(i=0;i<200;i++){ fcout< if(i!=0 && i%5==0) fcout< //求离开时间 fscin>>ser_time[0];lea_time[0]=arr_time1[0]+ser_time[0];for(i=1;i<200;i++){ fscin>>ser_time[i]; if(lea_time[i-1]>arr_time1[i]) {lea_time[i]=lea_time[i-1]+ser_time[i];} else {lea_time[i]=arr_time1[i]+ser_time[i];} } for(i=0;i<200;i++){ flcout< if(i!=0 && i%5==0) flcout< sta_time[i]=lea_time[i]-arr_time1[i]-ser_time[i];// if(sta_time[i]<0) { sta_time[i]=0; } } for(i=0;i<200;i++){ fscout< if(i!=0 && i%5==0) fscout< sta_sum+=sta_time[i];} //求平均等待时间 double ave;int peo_sum;for(i=0;i<200;i++){ if(lea_time[i]<540) peo_sum=i;} cout<<“总的服务人数为：”< 求离开人数和到达人数 #include #include int i,j; int arr_num[200];//到达人数arr int lea_num[200];//lea离开人数 int arr_jian=0;//时间间隔 double arr_time1[200];double lea_time[200];int peo_sum;int count=0;int count1=0;ifstream fcin(“d:arr_time1.txt”);ifstream flcin(“d:lea_time.txt”);ofstream fcout(“d:arr_num.txt”);ofstream flcout(“d:lea_num.txt”);for(i=0;i<200;i++){ fcin>>arr_time1[i]; flcin>>lea_time[i];} for(i=0;i<200;i++){ if(lea_time[i]<540) peo_sum=i;} while(arr_jian<540){ for(i=0;i { if(arr_time1[i]>arr_jian) { arr_num[count]=i; count++; //cout< break; } } for(j=0;j { if(lea_time[j]>arr_jian) { lea_num[count1]=j; count1++; break; } } arr_jian=arr_jian+5;} for(i=0;i<108;i++){ fcout< //cout< if(i!=0 && i%5==0) //cout< fcout< for(i=0;i<108;i++){ flcout< //cout< if(i!=0 && i%5==0) //cout< flcout< 求对长 #include int i;int max;int que[200];int arr_num[200];int lea_num[200];ifstream fcin(“d:arr_num.txt”);ifstream flcin(“d:lea_num.txt”);ofstream fcout(“d:que.txt”); for(i=0;i<200;i++){ fcin>>arr_num[i]; //cout< flcin>>lea_num[i]; //cout< for(i=0;i<200;i++){ que[i]=arr_num[i]-lea_num[i]; //cout< } for(i=0;i<200;i++){ fcout< if(i!=0 && i%5==0) { fcout< } } max=que[0];for(i=1;i<200;i++) { if(que[i]>max) { max=que[i]; //cout< } } cout<<“最大对长是”< 画图: function[maxque,mwait_t,mstay_t,queue_l,use_rate]=MM1queue(mean_arr,mean_lea,peo_num)status=zeros(3,peo_num); %用一个3行矩阵表示每个顾客的状态; %到达时间间隔，服务时间，等待时间;status(1,:)=exprnd(mean_arr,1,peo_num); %按照指数分布随机生成各顾客的到达间隔;status(2,:)=exprnd(mean_lea,1,peo_num); %按照指数分布随机生成各顾客的服务时间;for i=2:peo_num if status(1,i)<=status(2,i-1)+status(3,i-1) status(3,i)=status(2,i-1)+status(3,i-1)-status(1,i); else status(3,i)=0; end; %对状态进行更新； end;arr_time=cumsum(status(1,:));status(1,:)=arr_time;lea_time=sum(status);stairs([0 arr_time],0:peo_num); %绘出各顾客的到达时间图; hold on;stairs([0 lea_time],0:peo_num,'r'); %绘出各顾客的离去时间图;legend('Arrive curve','leave curve',0)hold off figure;plot(1:peo_num,status(3,:),'r:',1:peo_num,status(2,:)+status(3,:),'k-'); %绘出每个顾客的等待时间和停留时间;legend('Wait Time','Stay Time',0);n1=1;n2=1;mstay_t=(sum(status(2,:))+sum(status(3,:)))/peo_num;mwait_t=mean(status(3,:)); %求平均停留时间和等待时间;queue_num=zeros(1,2*peo_num+1);queue_time=zeros(1,2*peo_num+1);n3=1; %while循环求每个时间队列的长度;while n1<=peo_num n3=n3+1; if arr_time(n1) queue_num(1,n3)=n1-n2+1; queue_time(1,n3)=arr_time(n1); n1=n1+1; else queue_num(1,n3)=n1-n2-1; queue_time(1,n3)=lea_time(n2); n2=n2+1; end;end;while n2<=peo_num n3=n3+1; queue_num(1,n3)=peo_num-n2; queue_time(1,n3)=lea_time(n2); n2=n2+1;end;figure;stairs(queue_time,queue_num,'k'); %绘出队列长度的时间变化曲线, stairs 是Matlab的函数 legend('Queue Length Curve',0);hold off;temp=diff(queue_time);overtime=max(queue_time);queue_l=sum(temp.*queue_num(2:(2*peo_num+1)))/overtime;use_rate=sum(temp(find(queue_num)))/overtime;maxque=max(queue_num);% 最大队长 在MATLAB中命令窗口中输入MM1queue(2.86,3.22,175)数据结果： 随机到达时间arr_time 2.2218 2.91038 2.70151 3.20392 2.20729 2.23954 2.27037 2.12161 2.97105 2.59537 2.05195 2.33276 2.40885 2.54536 3.18395 4.34619 2.9621 4.03687 2.56005 4.3556 2.59767 2.6854 2.2156 2.35007 2.01546 3.16558 2.51725 2.4227 3.00499 2.68796 2.57445 2.29238 2.04275 3.56593 4.12181 3.14539 4.60806 2.85305 2.18215 4.15836 2.75386 2.45691 3.15095 3.84449 3.29556 2.35349 2.88082 2.96656 2.60517 3.09175 3.77562 2.12649 2.17347 2.28761 2.91709 2.59767 2.20084 3.64077 2.09167 2.30401 2.89137 2.78563 2.35564 2.60401 3.47721 2.31212 2.2892 2.26189 2.71001 3.23541 3.15543 4.04989 2.33905 2.60575 2.93069 2.63466 2.33025 2.67211 2.13304 2.46765 2.01119 2.66026 2.17867 4.26591 2.56115 2.84451 3.37485 2.22326 2.3109 3.08451 2.75872 3.02393 2.32155 2.37607 2.43489 3.70764 3.07631 2.56943 2.81941 2.81567 2.18215 3.78511 2.72393 2.02062 2.28013 2.03219 2.9324 4.02088 2.83606 2.01804 2.82241 2.23062 2.38448 2.15369 4.07996 2.02407 2.77847 2.93584 4.92381 4.07996 2.52143 2.10523 3.29291 2.34922 2.60807 2.83989 3.77091 2.4652 2.12096 2.36601 4.23257 2.29039 2.03278 3.42756 3.04233 2.80972 4.46149 2.04867 3.6673 2.04363 3.56409 4.8267 4.40435 3.60347 2.01375 4.41955 2.28406 2.49971 2.85853 2.11547 2.29079 2.2037 3.0078 2.43726 2.43963 3.82172 2.26189 3.14207 3.02297 2.39612 2.26381 3.59773 2.454 4.98197 3.60539 3.04233 3.21228 2.48553 2.16591 2.17244 2.25882 2.11773 3.77326 2.1113 3.15319 2.4011 2.66648 3.58261 3.36182 2.74012 2.16046 2.53464 2.21742 2.48754 2.86484 2.45837 2.4213 2.81047 4.02405 2.08667 2.24179 2.17971 3.1465 2.96925 2.07709 2.6139 3.48217 4.50565 3.25667 2.71528 随机服务时间ser_time 1.36266 1.25234 1.19953 1.81288 1.7025 1.49777 1.18475 1.2005 2.2218 2.91038 1.69353 1.06181 1.95277 1.86629 1.35603 1.36501 1.98628 1.05845 1.48635 2.70151 1.56285 1.7392 1.00964 1.69024 1.23548 1.68311 3.20392 2.20729 2.23954 1.0431 1.986 1.09644 2.27037 1.53367 2.12161 2.97105 1.68177 2.59537 2.05195 1.54594 1.24156 1.42946 2.33276 1.06994 2.40885 1.9069 2.54536 3.18395 4.34619 2.9621 1.09313 4.03687 2.56005 1.01332 1.97996 1.76143 1.26501 1.34689 1.66416 4.3556 1.6471 1.46631 2.59767 2.6854 1.92952 1.51985 1.85138 1.04044 2.2156 1.30726 1.1663 1.16661 5.21173 2.35007 1.3357 1.00973 2.01546 3.16558 2.51725 1.27905 2.4227 1.04284 1.69508 1.63761 1.13783 1.05052 1.94433 1.53127 3.00499 2.68796 2.57445 2.29238 1.40015 1.2112 1.64527 2.04275 1.29598 1.29286 3.56593 1.07538 3.20392 3.18395 4.34619 4.03687 4.3556 5.21173 3.16558 3.00499 3.56593 4.12181 3.14539 4.60806 4.15836 3.15095 3.84449 3.29556 5.29513 3.09175 3.77562 3.64077 3.47721 3.23541 3.15543 4.04989 4.26591 3.37485 3.08451 3.02393 3.70764 3.07631 3.78511 4.02088 4.07996 4.92381 4.07996 3.29291 3.77091 4.23257 3.42756 3.04233 4.46149 3.6673 3.56409 4.8267 4.40435 3.60347 4.41955 3.0078 3.82172 3.14207 3.02297 3.59773 4.98197 3.60539 3.04233 3.21228 3.77326 3.15319 3.58261 3.36182 5.0445 4.02405 3.1465 3.48217 4.50565 3.25667 4.85208 4.16211 4.13261 3.21952 3.46087 3.74548 4.5463 3.72969 3.29423 3.0804 3.08657 3.47556 4.09022 3.17586 5.29513 3.75694 3.74548 3.30222 3.01725 3.18627 3.40305 4.12539 3.49556 3.02777 3.87053 3.39703 3.51433 3.67983 3.27072 4.11115 4.22444 4.08337 3.37339 5.03375 到达时刻：arr_time1 2.2218 5.13218 7.83369 11.0376 13.2449 15.4844 17.7548 19.8764 22.8475 25.4428 27.4948 29.8276 32.2364 34.7818 37.9657 42.3119 45.274 49.3109 51.8709 56.2265 58.8242 61.5096 63.7252 66.0753 68.0907 71.2563 73.7736 76.1963 79.2012 81.8892 84.4637 86.756 88.7988 92.3647 96.4865 99.6319 104.24 107.093 109.275 113.434 116.187 118.644 121.795 125.64 128.935 131.289 134.17 137.136 139.741 142.833 146.609 148.735 150.909 153.196 156.113 158.711 160.912 164.553 166.644 168.948 171.84 174.625 176.981 179.585 183.062 185.374 187.664 189.925 192.635 195.871 199.026 203.076 205.415 208.021 210.952 213.586 215.917 218.589 220.722 223.189 225.201 227.861 230.039 234.305 236.867 239.711 243.086 245.309 247.62 250.705 253.463 256.487 258.809 261.185 263.62 267.327 270.404 272.973 275.793 278.608 280.79 284.575 287.299 289.32 291.6 293.632 296.565 300.586 303.422 305.44 308.262 310.493 312.877 315.031 319.111 321.135 323.913 326.849 331.773 335.853 338.374 340.48 343.773 346.122 348.73 351.57 355.341 357.806 359.927 362.293 366.525 368.816 370.849 374.276 377.318 380.128 384.59 386.638 390.306 392.349 395.913 400.74 405.144 408.748 410.762 415.181 417.465 419.965 422.823 424.939 427.23 429.433 432.441 434.878 437.318 441.14 443.402 446.544 449.567 451.963 454.227 457.824 460.278 465.26 468.866 471.908 475.12 477.606 479.772 481.944 484.203 486.321 490.094 492.205 495.359 497.76 500.426 504.009 507.371 510.111 512.271 514.806 517.023 519.511 522.376 524.834 527.255 530.066 534.09 536.176 538.418 540.598 543.744 546.714 548.791 551.405 554.887 559.393 562.649 565.364 离开时刻：lea_time 3.58446 6.38452 9.03322 12.8505 14.9474 16.9822 18.9396 21.0769 25.0693 28.3532 30.0467 31.1086 34.1892 36.6481 39.3217 43.6769 47.2603 50.3693 53.3573 58.928 60.4909 63.2488 64.7348 67.7655 69.3262 72.9394 76.9775 79.1848 81.4408 82.9323 86.4497 87.8525 91.0692 93.8984 98.6081 102.603 105.922 109.688 111.74 114.979 117.429 120.074 124.128 126.71 131.344 133.251 136.715 140.32 144.666 147.628 148.722 152.772 155.332 156.345 158.325 160.472 162.177 165.9 168.308 173.304 174.951 176.417 179.579 182.27 184.992 186.894 189.515 190.966 194.851 197.178 200.193 204.243 210.627 212.977 214.313 215.322 217.932 221.754 224.271 225.551 227.973 229.016 231.735 235.943 238.004 240.762 245.03 246.84 250.625 253.393 256.038 258.78 260.209 262.396 265.265 269.37 271.7 274.266 279.358 280.434 283.994 287.759 292.106 296.142 300.498 305.71 308.875 311.88 315.446 319.568 322.713 327.322 331.48 334.631 338.475 341.771 347.066 350.158 353.933 357.574 361.051 364.287 367.442 371.492 375.758 379.133 382.217 385.241 388.949 392.025 395.81 399.831 403.911 408.835 412.915 416.208 419.979 424.211 427.639 430.681 435.143 438.81 442.374 447.201 451.605 455.209 459.628 462.636 466.458 469.6 472.623 476.22 481.202 484.808 487.85 491.062 494.836 497.989 501.572 504.933 509.978 514.002 517.148 520.631 525.136 528.393 533.245 537.407 541.54 544.759 548.22 551.966 556.512 560.242 563.536 566.616 569.703 573.178 577.269 580.444 585.74 589.496 593.242 596.544 599.561 602.748 606.151 610.276 613.772 616.799 620.67 624.067 627.581 631.261 634.532 638.643 642.867 646.951 650.324 655.358 到达人数：peo_num 0 1 3 5 8 9 12 14 15 16 18 19 21 23 25 27 29 31 33 34 36 39 40 42 43 45 47 49 50 52 54 56 58 60 62 64 65 68 69 71 74 76 78 80 82 84 86 87 89 91 93 95 96 98 100 102 104 106 107 109 111 113 115 117 118 119 121 123 125 126 129 130 132 134 135 137 138 140 141 142 144 145 148 150 152 154 155 157 159 161 162 163 165 166 167 169 170 171 173174 175 177 离开人数：lea_num 0 1 3 5 7 8 10 13 15 16 17 19 20 23 25 26 28 30 32 34 35 38 40 41 43 44 46 47 49 51 52 55 57 59 61 63 65 67 69 70 72 75 77 79 82 83 85 86 88 90 92 94 96 98 99 101 102 103 104 105 107 108 110 111 112 114 115 116 117 119 120 122 123 124 127 129 130 132 133 134 135 137 138 139 140 142 143 144 147 148 150 151 152 154 155 157 158 160 161 162 队长que 0 0 0 0 1 1 2 1 0 0 1 0 1 0 0 1 1 1 1 0 1 1 1 0 1 0 1 2 1 1 2 1 1 1 1 1 0 1 0 1 0 2 1 1 1 0 1 1 1 1 1 1 0 0 1 1 2 3 3 4 4 5 5 6 6 5 6 7 8 7 9 8 9 10 0 10 9 10 9 9 10 10 11 12 13 14 13 14 15 16 15 15 15 15 0 0 0 0 0 0 0 0 605040302010Wait TimeStay Time***401601800 0 计算机科学与工程系 数据结构课程设计报告 课程设计题目 迷宫 航班信息查询系统 学 号 姓 名 班 级 专 业 网络工程 完 成 时 间 2013-1-4 指 导 教 师 数据结构课程设计 迷宫 题目一 1.设计内容 1.1问题描述 求迷宫从入口到出口的所有路径。1.2设计要求 1．迷宫中不能使用递归算法查找路径。2．试探方向限定为上、下、左、右四个方向。3．迷宫采用随机生成和手工生成两种方式。4．生成从迷宫入口到出口的最短和最长路径。5．迷宫的入口和出口由键盘输入。 1.3开发环境 Visual C++6.0的集成化环境 1.4研究思路 对这样的矩形迷宫，可以用N*M的矩阵来描述，N和M分别代表迷宫的行数和列数。这样，迷宫中的每一个位置都可以用行号和列号来指定。从入口到出口的路径则是由一个位置构成的，每个位置上都没有障碍，且每个位置（第一个除外）都是前一个位置的东、南、西或北的邻居。为了描述迷宫中位置（i,j）处有无障碍，规定：当位置（i,j）处有一个障碍时，其值为1，否则为0。 经分析，一个简单的求解方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行搜索，直到所有可能的通路都探索到为止。即所谓的回溯法。 2.设计步骤 2.1 需求分析 （1）题目：迷宫的生成与路由。生成一个N*M（N行M列）的迷宫，0和 1-1数据结构课程设计 迷宫 在该程序中，首先进入的是菜单选择，在菜单中有3种选择，选1是手动输入迷宫函数；选2是随机自动生成迷宫；选3是退出程序。在手动生成迷宫时，有两种输出方式，一是矩阵输出，二是图形输出。在矩阵输出时，直接将数组中的数进行输出，在图形输出时，则要判断该点的情况，然后输入迷宫的出入口，再调用mgpath（）函数进行判断是否存在路径，如果存在则将路径经过的点进行输出，并且将经过的点进入到辅助数组中（辅助数组是辅助图形界面的输出），并且将辅助数组初始为1，辅助数组中点为路径的重新赋值为0，然后根据情况输出图形界面。在自动生成迷宫时，用到了c语言随机函数，对于其它问题，和手动情况基本相同。 2.3 详细设计（1）主菜单伪代码： while(flag1){ } {shuru();//输入行列数 printf(“手动建立迷宫矩阵(0表示可通1表示障碍):n”);for(i=1;i<=m;i++) for(j=1;j<=n;j++)scanf(“%d”,&mg[i][j]);showplay(mg);// 迷宫输出 churukou();//迷宫出入口的输入 x=Mazepath(mg);// 判断路径函数 数据结构课程设计 迷宫 和“class ‘maze’has an illegal zero-sized array”两行错误。双击错误信息，找到出错的程序段，经过查阅资料发现，在利用顺序栈时，没有定义顺序栈的向量空间大小，导致程序出错。但不要对向量空间定义过大，否则会浪费空间。 （2）算法的时空分析： 由于链栈实际上是运算受限制的单链表。所以取栈顶元素运算的算法、置空栈运算的算法执行时间与问题的规模无关，则该算法的时间复杂度为O(1)；而其入栈运算的算法与出栈运算的算法相当于在链表的表尾进行插入和删除操作，不需要移动元素，时间复杂度也为O（1）。建立迷宫矩阵的时间复杂度为O（x*y）。在查找路径的过程中，最坏的情况下可能要考察每一个非障碍的位置。因此，查找路径的时间复杂度应为O（unblocked）。 链栈的入栈算法、出栈算法、取栈顶元素算法、置空栈算法执行时所需要的空间都是用于存储算法本身所用的指令、常数、变量，各个算法的空间性能均较好。只是对于存放顺序栈的向量空间大小的定义很难把握好，如果定义过大，会造成不必要的空间浪费。所以在定义时要慎重考虑。 3.用户使用说明 运行该程序，运行的界面的会出现菜单界面，然后用户可根据界面的提示进行相应的操作，生成迷宫的方式有两种方式，手动生成和自动生成，手动生成时、，用户可根据自己的要求输入迷宫的格式，还需输入相应的入出口，确认程序就会生成相应的路径图形；自动生成只需输入所需的行数和列数，就会生成迷宫，接下来的操作和手动操作相同了。 图数据结构课程设计 迷宫 图1-2 图1-3 退出 5.总结与心得体会 本次课程设计过程中由于掌握的知识不牢固，在编程序的过程中得到了同学的帮助和指导，在此表示感谢。课程设计的过程中，遇到了一些问题，大部分是课本中的知识掌握的不牢固，还有就是在以前学习C++的过程中相关的知识掌握的不够全面。在以后的学习过程中，自己一定要把各种知识掌握牢固。 { } mg[i][j]=1;//初始化 矩阵,将最外围置为1 printf(“n输入迷宫入口：n”);scanf(“%d%d”,&x1,&y1);printf(“输入迷宫出口：n”);scanf(“%d%d”,&x2,&y2); }mlink;mlink *stack;//定义一个栈 int m,n,x1,x2,y1,y2;//定义全局变量 } void showplay(int mg[][M+2])//迷宫输出 { n“); for(i=1;i<=m;i++){ printf(”n“);for(j=1;j<=n;j++) printf(”%d “,mg[i][j]); int i,j; printf(”迷宫矩阵如下(0可通)：printf(“输入行数：n”);scanf(“%d”,&m);printf(“输入列数：n”);scanf(“%d”,&n);数据结构课程设计 迷宫 } } printf(“n迷宫图形如下(白色for(i=1;i<=m;i++){ } printf(”n“);for(j=1;j<=n;j++){ } if(mg[i][j]==0)printf(” if(mg[i][j]==1)printf(“ if(mg[stack->row][stack->col+1]== p->next=stack; stack=p;{ p=(mlink 可通)：n”);0)//下面位置可通 *)malloc(sizeof(mlink)); p->row=stack->row;p->col=stack->col+1;□“);//为0的输出□ ■”);//为1的输出■ //入栈 mg[stack->row][stack->col]=1;//将 } else 访问过的标记为1 int Mazepath(int mg[][N+2]){ mlink *p;if(mg[x1][y1]==0){ p=(mlink p->row=x1;p->col=y1;p->next=NULL;stack=p; //将入口 mg[stack->row][stack->col]=1;/while((!(stack->row==NULL& if(mg[stack->row][stack->col-1]==0)//上面可通 //入栈 stack=p; p->next=stack; { p=(mlink *)malloc(sizeof(mlink)); *)malloc(sizeof(mlink)); p->row=stack->row;p->col=stack->col-1;放入堆栈 /标志入口已访问 &stack->col==NULL))&&(!(stack->row==x2&&stack->col==y2)))//循环条件直到找到输入的出口 { mg[stack->row][stack->col]=1;//将 访问过的标记为1 数据结构课程设计 迷宫 void tonglu()//将坐标的顶点输出 { 始化 printf(“(%d%3d)n”,q->row,q->col); 情况 else printf(“□”);//0的 } q=stack;{ } for(i=0;i for(j=0;j = while(q!=NULL)//循环条件 q=q->next;for(j=0;j 情况 } void create(int mg[][N+2])//创建和菜单 { int i,j,x,choice,flag1=1;chushi();while(flag1){ } printf(“n”);printf(“所有通道为（由下而q=stack;{ 上）：n”);while(q!=NULL)//循环条件 printf(“ ## printf(”# n“); *********选择菜单********** #n”); printf(“ ## printf(”输入选项：“);scanf(”%d“,&choice);switch(choice){ case 1://手动建立迷宫 { shuru(); printf(”手动建立for(i=1;i<=m;i++) n“); printf(”# 1-手动生成迷 宫 2-自动生成迷宫 3-退出 #n“);0;//将路径中的点赋给辅助数组a 形的界面输出 迷宫矩阵(0表示可通1表示障碍):n”); for(j=1;j<=n;j++)scanf(“%d”,&mg[i][j]); 数据结构课程设计 航班信息查询与检索系统 题目二 1.设计内容 1.1问题描述 设计一个航班信息查询系统，提供信息的管理和使用功能，管理包括更新、添加、删除功能。 1.2设计要求 （1）原始信息存储在文件中，记录不少于50条。（2）用户界面至少包括以下功能： 创建 修改（插入、添加、删除、更新） 查询 浏览 退出管理系统（3）航班信息包括： 航班号：字符序列，具体字符表达的意思上网查询 起点站和终点站：字符串 班期：指一周中哪些天有航班 起飞时间：可将时间定义成一个时、分组成的序列 到达时间：可将时间定义成一个时、分组成的序列 机型：字符序列，具体字符表达的意思上网查询 票价：整型数，具体值可上网查询 （4）创建是指从文件中读取数据，并存入所定义的顺序表中。 （5）可按航班号、起点站、终点站、起飞时间、到达时间等进行查询。查询时要用到顺序查找、二分查找方法。输出查询结果时必须排序。 （6）可按航班号、起点站、起飞时间、票价进行删除和更新操作，删除的记录存入另外的文件中，作为日志文件保存。 （7）作插入操作前，先对信息按起点站进行排序。新记录插入为起点站相同的最后一条记录。 数据结构课程设计 航班信息查询与检索系统 typedef struct node { Time rh;Time lv;}Pnode;（2）飞机结构体： struct Plane { };（3）静态链表： typedef struct Sqlist { int length;struct Plane *plane;char key[10],sted[20],sche[10];Time rh,lv;int price;}Sqlist;2.3 详细设计（1）主函数： do{printf(“* * * * * * * * * * * * * 航班查询系统* * * * * * * * * * * * *n”); printf(“* 1.创建 2.修改 3.查询 4.浏览 5.表长 6.文件 0.退出 *n”); printf(“* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *n”); scanf(“%d”,&opt);switch(opt){ case 1:Initlist(L);break; case 2:handle(L);break; case 3:search(L);break; case 4:print(L);break;case 5:Get_Sq(L);break;case 6:File(L);break; 数据结构课程设计 航班信息查询与检索系统 } }while(opt!=0);} （4）文件操作： void File(Sqlist &L){ int ch;do{ printf(“* * * * * * * * * * * * * * * * * * * * * * * * *n”); printf(“* *n”); printf(“* 1.保存信息到文件 2.从文件读取信息 0 退出 *n”); printf(“* *n”); printf(“* * * * * * * * * * * * * * * * * * * * * * * * *n”); printf(“请输入选项n”); scanf(“%d”,&ch); switch(ch) { case 1:SaveList(L);break; } }while(ch!=0);case 2:ReadList(L);break; case 0:printf(“退出！n”);break;} （5）浏览信息：就是循环使用输出函数，在此就不必多说了 2.4 调试分析 （1）在课设过程中，遇到问题时，通过与同学、老师交流，在图书馆查阅资料，使问题得以解决。 （2）算法中有许多不是很优化的地方。3.用户使用说明 程序运行后用户根据提示输入要进行的操作选项（应先选择创建选项，这样可以直接读取保存好的文件），然后选择要进行的操作选项。由于主菜单中有修改、查询和浏览项目，每个项目又有各自的子菜单，所以在进行管理和使用时要注意输入的元素是否正确，需按照提示输入。输入操作元素时，元素之间以空格隔开。程序将按输入的操作元素找到相应的算法，然后进行处理，然后将结果打 数据结构课程设计 航班信息查询与检索系统 图2-2 查询信息 图2-3插入 图2-4删除 数据结构课程设计 航班信息查询与检索系统 时就需要重新写出一个子函数，哪怕这个子函数就是在原有的一个子函数的基础上改那么一丁点的地方，例如航班信息查询系统中的查询函数，其实每个子函数只是改了一下关键码而已。 6.附录 #include { } void search_key(Sqlist L)//按航班号查找 { 号：“); Time rh;Time lv; scanf(”%s“,n);int i; printf(”此航班的航班号，起点char n[20]; printf(“请输入要查找的航班 printf(”%dn“,L.length);//表长 }Time;typedef struct node { }Pnode;struct Plane { };typedef struct Sqlist { int length;struct Plane *plane;char key[10],sted[20],sche[10];Time rh,lv;int price; 终点，班期，起飞时间，到达时间，票价：n”); if(strcmp(L.plane[i].key,n)==0) ted，L.plane[i].sche,L.plane[i].lv.hour,L.{ for(i=L.length-1;i>=0;i--){ printf(“%s %s %s %d:%d % d:%d %dn”,L.plane[i].key,L.plane[i].s}Sqlist;int get_Sq(Sqlist &L){ } void Get_Sq(Sqlist &L)return L.length; plane[i].lv.min,L.plane [i].rh.hour,L.plane[i].rh.min,L.plane [i].price); 0数据结构课程设计 航班信息查询与检索系统 printf(“此航班的航班号，起点 ted，{ 终点，班期，起飞时间，到达时间，票价：n”); if(L.plane[i].lv.hour<=hour) ted，L.plane[i].sche,L.plane[i].lv.hour,L.{ for(i=L.length-1;i>=0;i--){ printf(“%s %s %s %d:%d % d:%d %dn”,L.plane[i].key,L.plane[i].s L.plane[i].sche,L.plane[i].lv.hour,L.plane[i].lv.min,L.plane [i].rh.hour,L.plane[i].rh.min,L.plane } void search(Sqlist L){ int i;do { printf(“* * * * * * * * * * * } } printf(”%s %s %s %d:%d %d:%d %dn“,L.plane[i].key,L.plane[i].s[i].price);plane[i].lv.min,L.plane [i].rh.hour,L.plane[i].rh.min,L.plane } void search_rh(Sqlist L){ int hour;printf(”请输入你所要求的最scanf(“%d”,&hour);printf(“此航班的航班号，起点 } } [i].price); * * * * * * * * * * * * * ** * * * * * * * * * * * * * * *n”); printf(“* 1.航班号查询 2.起点终点查询 3.班期查询 4.起飞时间查询 5.到达时间查询 0.退出 *n”); printf(“* * * * * * * * * * * * * * * * * * * * * * * * ** * * * * * * * * * * * * * * *n”); scanf(“%d”,&i); switch(i) { case 晚时间：“);终点，班期，起飞时间，到达时间，票价：n”); if(L.plane[i].rh.hour<=hour)for(int i=L.length-1;i>=0;i--){ 1:search_key(L);break; 2数据结构课程设计 航班信息查询与检索系统 n“); } else { } printf(”查找不成功。 i--;if(i==0) { char c[20]; printf(“输入修改后的scanf(”%s“,c); 内容：”); strcpy(L.plane[i].sche,c); printf(“修改成功！n”);}break;{ int a,b; printf(“输入修改后的int opt;printf(”选择修改对象：“);scanf(”%d“,&opt);switch(opt){ case 1: printf(”修改成功！n“);printf(”修改成功！n“);{ char a[10];printf(”输入修改后的scanf(“%s”,a); case 4: 内容：“); char b[20];printf(”请输入修改后scanf(“%s”,b); scanf(“%d:%d”,&a,&b); L.plane[i].lv.hour=a;L.plane[i].lv.min=b;printf(“修改成功！n”);航班号：“); }break;{ int a,b; printf(”输入修改后的strcpy(L.plane[i].key,a);}break;{ case 5: case 2: 内容：“); scanf(”%d:%d“,&a,&b); L.plane[i].rh.hour=a;L.plane[i].rh.min=b;printf(”修改成功！n“);的内容：”);strcpy(L.plane[i].sted,b);}break; }break;{ int a; case 6: case 3: 4数据结构课程设计 航班信息查询与检索系统 *n“); printf(”* * * * * * * * * * * * * * * * * * * * * * * * *n“); printf(”请输入选项n“); scanf(”%d“,&ch); switch(ch) { case 1:SaveList(L);break;case 2:ReadList(L);break; L.plane[i].sche,&L.plane[i].lv.hour，&L.plane[i].lv.min,&L.plane [i].rh.hour,&L.plane[i].rh.min,&L.pl } void delet_Sq1(Sqlist &L){ char n[10];int i,j; printf(”请输入您要删除的航scanf(“%s”,n);if(L.length==0){ printf(“没有选项！n”);for(i=0;i L.length++; ane[i].price); case 0:printf(“退出！n”);break; } void Initlist(Sqlist &L)//插入存储 { “); 容：”);价n“); scanf(”%s%s%s%d:%d%d:%d%d“,L.plane[i].key,L.plane[i].sted, for(i=0;i 班期 起飞时间 到达时间 票scanf(”%d“,&n);L.length=0;L.plane=(Plane if(!L.plane)exit(0);printf(”请输入顺序表中的内 int i,n;printf(“输入表中航班的数量： } }while(ch!=0); 班号：”); if(strcmp(L.plane[i].key,n)==0) { printf(“所删除的班机*)malloc((n+10000)*sizeof(Plane));的信息：n”); printf(“n航班号 起点终点 printf(”%s %s %s %d:%d %d:% d %dn“,L.plane[i].key,L.plane[i].sted，L.plane[i].sche,L.plane[i].lv.hour,L.plane[i].lv.min,L.plane [i].rh.hour,L.plane[i].rh.min,L.plane [i].price); 6数据结构课程设计 航班信息查询与检索系统 n”);} printf(“无法打开文件！} }while(opt!=0); void insert_Sq(Sqlist &L){ 数量 价n”); for(i=0;i printf(“* * * * * * * * * * * scanf(”%s%s%s%d:%d%d:%d%d“,&L.plane[L.length].key,&L.plane[L.length].sted，&L.plane[L.length].sche,&L.plane[ { int a=get_Sq(L); printf(”请输入要添加班机的scanf(“%d”,&n); printf(“请输入要添加的班机printf(”n航班号 起点终点 int i,n; //n表示添加的fprintf(fp,“航班号：%sn起点站：%s 终点站：%sn班期：%dn起飞时间：%d:%d 到达时间：%d:%dn价格：%dnn”, p.key,p.sted,p.sche,p.lv.hour,p.lv.mi n“);} void delet_Sq(Sqlist &L){ int opt;do { fclose(fp);printf(”保存删除的信息成功。n,p.rh.hour,p.rh.min,p.price); 数量：“); 信息：n”); 班期 起飞时间 到达时间 票* * * * * * * * * *n“); printf(”* 1.航班号删除 printf(“* * * * * * * * * * printf(”输入你的选择：“);2.路线删除 0.退出 *n”);* * * * * * * * * * *n“); scanf(”%d“,&opt); switch(opt){ case 1:delet_Sq1(L);break; case 2:delet_Sq2(L);break; case 0:printf(”退出。} L.length].lv.hour,&L.plane[L.length].lv.min，&L.plane[L.length].rh.hour,&L.plan e[L.length].rh.min,&L.plane[L.length].price); } void handle(Sqlist &L){ } L.length++; n");break; 《数据结构》课程设计 哈希表实现电话号码查询系统一目的 利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目，利用C/C++语言进行程序设计，并规范地完成课程设计报告。通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。 二需求分析 1、程序的功能 1)读取数据 ① 读取原电话本存储的电话信息。 ② 读取系统随机新建电话本存储的电话信息。2)查找信息 ① 根据电话号码查询用户信息。② 根据姓名查询用户信息。3)存储信息 查询无记录的结果存入记录文档。 2、输出形式 1)数据文件“old.txt”存放原始电话号码数据。 2)数据文件“new.txt”存放有系统随机生成的电话号码文件。3)数据文件“out.txt”存放未查找到的电话信息。4)查找到相关信息时显示姓名、地址、电话号码。 3、初步测试计划 1)从数据文件“old.txt”中读入各项记录，或由系统随机产生各记录，并且把记录保存到“new.txt”中。 2)分别采用伪随机探测再散列法和再哈希法解决冲突。3)根据姓名查找时显示给定姓名用户的记录。4)根据电话号码查找时显示给定电话号码的用户记录。 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 1 《数据结构》课程设计 5)将没有查找的结果保存到结果文件Out.txt中。 6)系统以菜单界面工作，运行界面友好，演示程序以用户和计算机的对话方式进行。 三概要设计 1、子函数功能 int Collision_Random(int key,int i)//伪随机数探量观测再散列法处理冲突 void Init_HashTable_by_name(string name,string phone,string address)//以姓名为关键字建立哈希表 int Collision_Rehash(int key,string str)//再哈希法处理冲突 void Init_HashTable_by_phone(string name,string phone,string address)//以电话号码为关键字建立哈希表 void Outfile(string name,int key)//在没有找到时输出未找到的记录，打开文件out.txt并将记录储存在文档中 void Outhash(int key)//输出哈希表中的记录 void Rafile()//随机生成数据，并将数据保存在new.txt void Init_HashTable(char*fname,int n)//建立哈希表 int Search_by_name(string name)//根据姓名查找哈希表中的记录 int Search_by_phone(string phone)//根据电话号码查找哈希表中的记录 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 2 《数据结构》课程设计 2、函数调用图 main()Refile()init-hashtable()init-hashtable-by-name()init-hashtable-by-phone()Seach-by-name()Seach-by-phone()Coiiision-random()Collision-rehash()Outhash()xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 3 《数据结构》课程设计 四详细设计 1、主函数流程图 开始选择数据来源21建“new.txt”选择查找方式12姓名查找电话号码查找12021输入姓名显示哈希表0显示哈希表输入电话号码无此记录显示信息无此记录显示信息0写入“out.txt”写入“out.txt”结束 2、“伪随机探测再散列处理冲突”伪代码 若对应位置上已经存在其他数据，则新的关键字=（原关键字+伪随机数）%哈希表长。若新的位置上也存在其他数据，则用伪随机序列的下一个数求新的关键字，直到找到合适的位置。 3、“再哈希法处理冲突”伪代码 用“折叠法”将电话号码的ASCII码值定义为关键字，分别为前四位、中四位、后三位。 再用“除留余数法”求的新的关键字=原关键字%哈希表长。 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 《数据结构》课程设计 4、“以姓名为关键字建立哈希表”伪代码 用“除留余数法”将姓名的ASCII码值定义为关键字。 若对应位置上存在其他数据，则调用伪随机处理冲突，然后将数据存入哈希表。 5、“以电话号码为关键字建立哈希表”伪代码 用“除留余数法”将电话号码的ASCII码值定义为关键字。若对应位置上存在其他数据，则调用再哈希处理冲突。然后将数据存入哈希表。 五调试分析 1、程序的关键是掌握文件的相关操作、哈希函数的创建和运用、伪随机法处理冲突、再哈希法处理冲突等。在编程的过程中，出现了很多问题，如文件无法正常打开、程序进入死循环、无法实现文件的写入操作、忘了添加头文件等错误。修改后程序运行正确。 2、创建“new.txt”内容用子函数来实现，但是原数据是从“old.txt”文件中读取的，刚开始不知道怎样实现二者之间的选择，在同学和参考书的帮助下终于得到解决。 3、关于伪随机和再哈希的相关内容觉得很难懂，看了很久参考书才有所了解 六测试结果 1、根据姓名查找 1)姓名查找成功 2)姓名查找失败 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 5 《数据结构》课程设计 3)哈希表 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 6 《数据结构》课程设计 2、根据电话号码查找 1)电话号码输入错误 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 7 《数据结构》课程设计 2)电话号码查询成功 3)电话号码查询失败 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 8 《数据结构》课程设计 4)哈希表 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 9 《数据结构》课程设计 七用户使用说明 1、选择数据来源 根据提示信息进行操作，选择已存在的“old.txt”文件中的数据或系统当前自动生成的“new.txt”文件。 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 10 《数据结构》课程设计 2、选择查找方式 根据提示信息进行操作，选择“根据姓名查找”或“根据电话号码查找”两种查找方式。 3、选择功能 根据提示信息进行操作，选择输入已知信息或查看哈希表。 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 11 《数据结构》课程设计 4、显示结果 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 《数据结构》课程设计 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 13 《数据结构》课程设计 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 14 《数据结构》课程设计 5、查看文件 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 15 《数据结构》课程设计 八课程设计总结 1、收获 学会了C++的跟踪。更进一步了解和熟悉了关于哈希表的运用和文件的读取与写入操作。同时锻炼了对话形式的菜单的创建和熟练运用。 2、心得体会 在这次数据结构设计中遇到了很多实际性的问题，在实际设计中才发现，书本上理论性的东西与在实际运用中的还是有一定的出入的，所以有些问题要不断地更正以前的错误思维。通过这次设计，我懂得了学习的重要性，了解到理论知识与实践相结合的重要意义，xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 16 《数据结构》课程设计 学会了坚持、耐心和努力，这将为自己今后的学习和工作做出了最好的榜样。我觉得作为一名计科专业的学生，这次课程设计是很有意义的。更重要的是如何把自己平时所学的东西应用到实际中。虽然自己对于这门课懂的并不多，很多基础的东西都还没有很好的掌握，觉得很难，也没有很有效的办法通过自身去理解，但是靠着学习，渐渐对这门课逐渐产生了些许的兴趣，自己开始主动学习并逐步从基础慢慢开始弄懂它。 xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 《数据结构》课程设计 附录：源程序 #include using namespace std; ifstream in_file;ofstream out_file; int D[10]={1,3,5,8,13,15,17,21,27,34};//伪随机数序列 int count;//当前数据元素个数 int sizeindex;//哈希表的长度 char *sign;//冲突的标志 struct Data { string name;string phone;string address;};Data *intermediate_data; int Collision_Random(int key,int i)//伪随机数探量观测再散列法处理冲突{ int Re_key;if(sign[key]=='1'){ xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 18 《数据结构》课程设计 } Re_key=(key+D[i])%sizeindex;return Re_key;//归回新的要害码 return-1;} void Init_HashTable_by_name(string name,string phone,string address)//以姓名为关键字建立哈希表 { int i=0;int key;char*p;for(key=0,p=&name[0];*p;p++)key=key+*p;key=key%42;while(sign[key]=='1'){ } if(key==-1)exit(1);key=Collision_Random(key,i+1);count++;intermediate_data[key].name=name;//将数据存入哈希表 intermediate_data[key].address=address;intermediate_data[key].phone=phone;sign[key]='1';//设置冲突标志 } xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 19 《数据结构》课程设计 int Collision_Rehash(int key,string str)//再哈希法处理冲突 { int Re_key;int num1=(str[0]-'0')*1000+(str[1]-'0')*100+(str[2]-'0')*10+(str[3]-'0');int num2=(str[4]-'0')*1000+(str[5]-'0')*100+(str[6]-'0')*10+(str[7]-'0');int num3=(str[8]-'0')*100+(str[9]-'0')*10+(str[10]-'0');Re_key=num1+num2+num3;Re_key=(Re_key+key)%sizeindex;return Re_key;} void Init_HashTable_by_phone(string name,string phone,string address)//以电话号码为关键字建立哈希表 { int key;char*p;for(key=0,p=&phone[0];*p;p++)key=key+*p;key=key%42;while(sign[key]=='1'){ } count++;intermediate_data[key].name=name;intermediate_data[key].address=address;intermediate_data[key].phone=phone;key=Collision_Rehash(key,phone);xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 20 《数据结构》课程设计 sign[key]='1';} void Outfile(string name,int key)//在没有找到时输出未找到的记录，打开文件out.txt并将记录储存在文档中 { if((key==-1)||(sign[key]=='0')){ out_file.open(“out.txt”); if(out_file.fail()) { cout<<“n”<<“文件打开失败！!n”< exit(1); } out_file< out_file.close();} } void Outhash(int key)//输出哈希表中的记录 { unsigned i;if((key==-1)||(sign[key]=='0')){ cout<<“n”<<“无此记录！!n”< } else xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 21 《数据结构》课程设计 { for(i=0;i cout< for(i=0;i<8;i++) cout<<“ ”; cout< for(i=0;i<8;i++) cout<<“ ”; cout< void Rafile()//随机生成数据，并将数据保存在new.txt { int i,j;out_file.open(“new.txt”);if(out_file.fail()){ cout<<“n”<<“文件打开失败！!n”< exit(1);} for(j=0;j<30;j++){ string name=“"; for(i=0;i<20;i++) name+=rand()%26+'a';out_file< 《数据结构》课程设计 string phone=”“; for(i=0;i<11;i++) phone+=rand()%10+'0'; out_file< string address=”“; for(i=0;i<29;i++) address+=rand()%26+'a'; address+=','; out_file< void Init_HashTable(char*fname,int n)//建立哈希表{ string name=”“;string phone=”“;string address=”“;int i,j;in_file.open(fname);if(in_file.fail()){ cout<<”n“<<”文件打开失败！!n“< exit(1);} while(!in_file.eof()){ xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 23 《数据结构》课程设计 字 键字 } char* str=new char[100];name=”“;phone=”“;address=”“;in_file.getline(str,100,'n');//按行读入数据 if(str[0]=='*')//判断数据结束 i=0;while(str[i]<=97||str[i]>=122)i++;break;for(;str[i]!=' ';i++)name+=str[i];while(str[i]==' ')i++;for(j=0;str[i]!=' ';j++,i++)phone+=str[i];while(str[i]==' ')i++;for(j=0;str[i]!=',';j++,i++)address+=str[i];if(n==1)Init_HashTable_by_name(name,phone,address);//以姓名为关键else Init_HashTable_by_phone(name,phone,address);//以电话号码为关delete str;in_file.close();} xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 《数据结构》课程设计 int Search_by_name(string name)//根据姓名查找哈希表中的记录 { int i=0;int j=1;int key;char*p;for(key=0,p=&name[0];*p;p++)key=key+*p;key=key%42;while(sign[key]=='1'&&(intermediate_data[key].name!=name)){ key=Collision_Random(key,i+1); j++; if(j=count) return-1;} return key;} int Search_by_phone(string phone)//根据电话号码查找哈希表中的记录{ int key;char*p;for(key=0,p=&phone[0];*p;p++)key=key+*p;key=key%42;int j=1;xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 25 《数据结构》课程设计 while(sign[key]=='1'&&(intermediate_data[key].phone!=phone)){ key=Collision_Rehash(key,phone); j++; if(j=count) return-1;} return key;} void main(){ count=0;sizeindex=50;int i,k;int ch;char *Fname; sign=new char[sizeindex]; intermediate_data=new Data[sizeindex]; for(i=0;i for(i=0;i 《数据结构》课程设计 { } cout<<”§**********************************************************§“< *§”< *§“< *§”< *§“< *§”< *§“< cout<<”§**********************************************************§“< do { switch(k)cout<<”n“<< ” 请输入选择 : n“;cin>>k;cout<<”§* 0.退 出 程 序 cout<<“§* 2.随 机 生 成 cout<<”§* 1.old.TXT cout<<“§* cout<<”§* 请选择用于查找的数据来源 cout<<“§* intermediate_data[i].name=”“;intermediate_data[i].phone=”“;intermediate_data[i].address=”“;xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 27 《数据结构》课程设计 { case 0: return;case 1: Fname=”old.txt“;break;case 2: Rafile();Fname=”new.txt“;break;default: } while((k!=1)&&(k!=2)&&(k!=0)); //system(”cls“); cout<<”§**********************************************************§“< *§”< *§“< *§”< *§“< *§”< cout<<”输入序号有误，请重新输入！!n“< 《数据结构》课程设计 *§”< cout<<”§**********************************************************§“< //system(”cls“); endl; *§”< } while((ch!=1)&&(ch!=2));cout<<”n“<< ” 请输入选择 : n“;cin>>ch;if(ch!=1&&ch!=2){ } cout<<” 输入序号有误，请重新输入！!n“< 《数据结构》课程设计 *§”< cout<<”§* *§“< *§”< *§“< *§”< *§“< cout<<”§**********************************************************§“< do { cout<<”n“<< ” 请输入选择 : n“; cin>>choice;cout<<”§* cout<<“§* 0.退 出 程 序！!cout<<”§* 2.显 示 哈 希 表 cout<<“§* 1.输 入 姓 名 查 找 数 据 switch(choice){ case 1: { int key1;string name; cout<<”n“<<” 请输入姓名: n“; cin>>name; key1=Search_by_name(name);xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 30 《数据结构》课程设计 Outfile(name,key1);cout<<”n“<<”查找结果:n“< Outhash(key1); } break; case 2: { cout<<”n“<<” 哈希表: n“< for(i=0;i { if(sign[i]!='0') { cout<<”* “; Outhash(i); } } cout<<”* *“< } break; case 0: return;default: xxxx大学xxxx学院xxxx专业学号：xxxxxxx姓名：jenery6 31 《数据结构》课程设计 cout<<” 输入序号有误，请重新输入！!n“< endl; *§”< *§“< *§”< *§“< *§”< *§“< cout<<”§**********************************************************§“<第二篇：数据结构课程设计报告
第三篇：数据结构课程设计报告
第四篇：数据结构课程设计报告
第五篇：数据结构课程设计报告