数据结构C语言课程设计任务书完整版

《数据结构C语言课程设计任务书完整版》由会员分享，可在线阅读，更多相关《数据结构C语言课程设计任务书完整版（14页珍藏版）》请在装配图网上搜索。

1、目录1 需求分析 21.1目的 21.2功能 21.3结果展示 22 详细设计 22.1 数据类型 32.2 总体功能流程图 42.3伪码算法 53 调试分析 133.1 遇到的问题 133.2 算法的时空分析 133.3 改进设想 133.4 经验体会 134 测试结果 145 参考文献 151、需求分析1.1、 目的图的存储结构的建立、Prim、Kruskal、Dijkstra和拓扑排序算法。 熟练图数据结构算法 熟练掌握数据结构 复习 C 语言的各个知识点1.2、 功能(1) 将图的信息建立文件；(2) 从文件读入图的信息，建立邻接矩阵和邻接表；(3) 实现 Prim、 Kruskal、

2、 Dijkstra 和拓扑排序算法。2、详细设计2.1、数据类型2.1.1、 图的抽象数据类型ADT Graph数据对象：V： v是具有相同特性的数据元素的集合，称为顶点集。 数据关系： R=VRVR=v,wlv,wW V 且 P(v,w),vv,w表示从 v 到 w 的弧 谓词Pv,w定义了弧v,w的意义或信息 基本操作：int locateALG(ALGraph g,char v) 操作结果：得到某元素的位置 int convert(char *str) 操作结果：将字符转化为数字 int ReadFileBiao(ALGraph &g,FILE *fp) 操作结果：从文件中读取信息到邻接

3、表 void ReadFilejuzhen(MGraph &G,FILE *fp) 操作结果：从文件中读取信息到邻接矩阵 void MiniSpanTree_PRIM(MGraph G,char u) 操作结果：普里姆算法的实现 void SortEdge(MGraph G,Edge E) 操作结果：对图中的权值进行递增排序 void MiniSpanTree_Kruskal(Edge E,MGraph G,int n) 操作结果：克鲁斯卡尔算法的实现 void ppath(MGraph G,char path,int i,char v)操作结果：求图中某点最短距离所经过的顶点void Dis

4、Path(MGraph G,int dist,char path,int s,int n,char v) 操作结果：计算最短路径void ShortestPath_DIJ(MGraph G,char v) 操作结果：迪杰斯克拉算法的实现 int FindInDegree(ALGraph G,int indegree) 操作结果：求各顶点的入度 void TopologicalSort(ALGraph G) 操作结果：拓扑排序算法的实现ADT Graph2.1.2、栈的抽象数据类型ADT Stack数据对象：D=ailai w ElemSet,i=l,2,n,n=0数据关系：R1=vai-1,a

5、ilai-1,aiWD,i=2,.n 约定an端为栈顶，ai端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈 S DSestroyStack(&Ss) 操作结果：销毁栈 Push(&S， e)操作结果：插入元素 e 为新的栈顶元素 Pop(&S,&e)操作结果：删除S的栈顶元素，并用e返回其值StackEmpty(S) 操作结果:判断栈是否为空2.2、总体功能流程图1、功能模块2、主界面流程图Scanf(o)SprintMGra(lprintMGra(eMiniSpanT:-e ；eKruskal(E,G, vexnum)$hortestPath_DopologicalIJ

6、(G1,a)rtsystem(cls)(g)2.3、伪码算法1、普里姆算法伪代码及流程图void MiniSpanTree_PRIM(MGraph Gchar u)int M5050;int v,i,j,k;v=locateMG(G,u);for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)Mij=G.arcsij.adj;for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+)if(Mij=0)G.arcsij.adj=999;int lowcost50,min;for (i=0;iG.vexnum;i+)lowcosti=G.a

7、rcsvi.adj;lowcostv=0;for (i=1;iG.vexnum;i+) min=999;for (j=0;jG.vexnum;j+)if (lowcostj!=0 & lowcostjmin) min=lowcostj; k=j;printf(” 边(c,%c)权为:dn,closestk,G.vexsk,min); lowcostk=0;for (j=0;jG.vexnum;j+)tif (G.arcskj.adj!=0 & G.arcskj.adjlowcostj) lowcostj=G.arcskj.adj;离 closestj=G.vexsk;(UHE 三.U;VHE

8、三mlILocaieMG(GU)；m2HocaieMG(GV)八sn 1H vse 二 m 1；SI12H vse 二 m2；if (Snlllsn2) ( primf(=&(p%c)tz %dn=uvmsw)；k+; for (iHO;穴 n;i+) ( if (vse=inHsn2) )开始1=05NIvnYKvnYXNSnl!=sn2YNininNY-Yu=Ej.u;v=Ej.v; ml=locateMG(G,u); m2=locateMG(G, sn1=vsetm1; sn2=vsetm2;Vseti=iK+i=0vseti=sn1结束3、迪杰斯特拉算法的 伪代码及流程图void Sh

9、ortestPath_DIJ(MGraph G,char v) int M5050;int v0=locateMG(G,v);for(int i=0;iG.vexnum;i+)for(int j=0;jG.vexnum;j+)Mij=G.arcsij.adj; for(int i=0;iG.vexnum;i+)for(int j=0;jG.vexnum;j+) if(Mij=0)G.arcsij.adj=999; elseMij=G.arcsij.adj int dist20;char path20;int s20;int mindis,i,j,u,n=G.vexnum;for (i=0;in

10、;i+)disti=G.arcsij.adj;si=0;if (G.arcsv0i.adj999) pathi=G.vexsv0;else pathi=-1; sv0=1;pathv0=a;for (i=0;in;i+) mindis=999;u=-1;for (j=0;jn;j+)if (sj=0 & distjmindis) u=j; mindis=distj;su=1;for (j=0;jn;j+)if (sj=0)if (G.arcsuj.adj999 & distu+G.arcsuj.adjdistj) distj=distu+G.arcsuj.adj;pathj=G.vexsu;

11、DisPath(G,dist,path,s,n,v); 开始1=0NIvnYYI=0IvnYI=04yIIvnNdistj=distu+G.arcsuj.adj; pathj=G.vexsu;G.arcsuj.adj999 & distu+G.arcsuj.adjvdistj . -i+J+结束Mij=G.arcsij.adjG.arcsij.adj=999G.arcsv0i.adj .：- . 999DisPath(G,dist,path,s,n,v);disti=G.arcsij.adj; si=0;pathi=G.vexs v0pathi=-1mindis=999 u=-1;J=0J=0

12、4、拓扑排序的伪代码及流程图void TopologicalSort(ALGraph G)SqStack S;ArcNode *p;int indegreeG.vexnum;char tuopoxulieG.vexnum;int i,k,count;FindInDegree(G,indegree);InitStack(S);for(i=1;inextarc) k=p-adjvex;if(!(-indegreek) Push(S,k);printf(n);if(count0)printf(“你所给的有向图的拓扑序列为：n();for(i=1;icount;i+) printf(%c,G.vert

13、icesi.data);printf(%c)n,G.verticescount.data);if(countG.vexnum)printf(“，但该有向图中存在回路！ n);elseprintf(你所给的有向图不存在拓扑序列n);开始Iadjvex;J=03、调试设计3.1、遇到的问题1、不晓得怎么去从文件里面读中文。2、在迪杰斯特拉算法还不是很了解其逻辑思路。3.2、算法的时空分析T(n)=O(n2)3.3、改进设想在进入某个功能模块时，或者某个功能的某个步骤时，可以允许出现输入错 误，因此，要实现进入某个步骤时实现撤销操作.3.4、经验体会虽说此次是任选题，实质上是必选题，此次的题目比较难

14、。我前面的一位同 学的题目是我 7 大小题中的一个小题。表示鸭梨很大。由于第一次接触到 C 语 言的操作文件，在探索过程中有点枯燥繁琐。弄好了文件，接下来的就更难了。 什么普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、拓扑排序。不是数据结构 书就可以搞定的。这些算法需要的辅助很多。因此要狠清楚的了解她们的逻辑关 系。不过，虽然有4点、难。但测在编试程上结有了果很大的飞跃欢迎使用图的操作系统出岀岀岀岀岀曹息息 蠶果 inw UBS flu 邻邻書卡特序 图图图姆面 向向向里备杲心扑界 有无直曰脣拓、王作者：刘文辉青选择您需要的菜单项：4.1 输出有向图邻接矩阵信息请选择您需要的菜单项：1邻接矩阵无

15、向图中有9个顶点条弧邻接矩阵无向图中的顶点为5 b c d e f g h i邻接矩阵表示为：0645000 0 00 0 00 0 00 0 00 0 00 0 00 0 00 0 00 100 100 0 20 0 00 0 00 0 00 0 00 0 00 00 00 00 09 70 40 00 00 00000002404.2 输出有向图邻接表信息4.3 输出普里姆算法的结果P屮塑算法得到的最小生成树为: 边5叹为：4 边c,eJ：y为：1 边叹为 边ga又为汚 边5冲収为汐 边叹为：4 边hi叹为：4 边“心权为汐4.4 输出克鲁斯卡尔算法的结果4.6 输出拓扑排序算法的结果5、参考文献1、数据结构（C语言版）严蔚敏、吴伟民2、C 程序设计（第三版）谭浩强