数据结构C语言课程设计任务书完整版--图的算法

1 1.1 1.2 1.3 2

需求分析 .................................................................................................................................................. 2 目的 .......................................................................................................................................................... 2 功能 .......................................................................................................................................................... 2 结果展示 .................................................................................................................................................. 2

详细设计 ....................................................................................................................................................... 2

数据类型 ............................................................................................................................................... 3 总体功能流程图 .................................................................................................................................. 4 伪码算法 ............................................................................................................................................... 5

2.1 2.2 2.3 3

调试分析........................................................................................................................................................ 13 3.1 3.2 3.3 3.4

遇到的问题 ............................................................................................................................................ 13

算法的时空分析 ................................................................................................................................ 13

改进设想 ................................................................................................................................................ 13 经验体会 ................................................................................................................................................ 13

4 5

测试结果........................................................................................................................................................ 14

参考文献 ..................................................................................................................................................... 15

1

1、 需求分析

1.1、 目的

图的存储结构的建立、Prim、Kruskal、Dijkstra和拓扑排序算法。 ① 熟练图数据结构算法 ② 熟练掌握数据结构

③ 复习C语言的各个知识点

1.2、 功能

（1）将图的信息建立文件；

（2）从文件读入图的信息，建立邻接矩阵和邻接表； （3）实现Prim、Kruskal、Dijkstra和拓扑排序算法。

2、详细设计

2.1、数据类型

2.1.1、 图的抽象数据类型

ADT Graph{ 数据对象：V：v是具有相同特性的数据元素的集合，称为顶点集。 数据关系：R={VR} VR={v,w}|v,w∈V且P(v,w),表示从v到w的弧 谓词P{v,w}定义了弧的意义或信息

基本操作：

int locateALG(ALGraph g,char v)

操作结果：得到某元素的位置

int convert(char *str)

操作结果：将字符转化为数字

int ReadFileBiao(ALGraph &g,FILE *fp)

操作结果：从文件中读取信息到邻接表

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)

2

操作结果：求图中某点最短距离所经过的顶点

void DisPath(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 Graph

2.1.2、栈的抽象数据类型

ADT Stack{

数据对象：D={ai|ai∈ElemSet,i=1,2,………,n,n>=0} 数据关系：R1={|ai-1,ai∈D,i=2,…n} 约定an端为栈顶，ai端为栈底。 基本操作： InitStack(&S) 操作结果：构造一个空栈S DSestroyStack(&Ss) 操作结果：销毁栈 Push（&S，e） 操作结果：插入元素e为新的栈顶元素 Pop（&S,&e） 操作结果：删除S的栈顶元素，并用e返回其值 StackEmpty（S） 操作结果:判断栈是否为空

}

2.2、总体功能流程图

1、功能模块

主模块无向图邻接矩阵普里姆算法生成树有向图邻接表有向图邻接矩阵克鲁斯卡尔生成树迪杰斯特拉最小路径拓扑排序 3

2、主界面流程图

i=1Scanf(o)O=1O=2O=3O=4O=5O=6O=7O=8printMGra(G1)printMGra(G)printALGra(g)MiniSpanTree_PRIM(G,'a')MiniSpanTree_Kruskal(E,G,G.vexnum)ShortestPath_DIJ(G1,'a')TopologicalSort(g)system(\"cls\")

2.3、伪码算法

1、普里姆算法伪代码及流程图

void MiniSpanTree_PRIM(MGraph G,char u){ int M[50][50]; int v,i,j,k; v=locateMG(G,u);

for(i=0;i}

4

}

int lowcost[50],min; for (i=0;ilowcost[v]=0; for (i=1;i{

min=999;

for (j=0;j}

} }

}

5

2、克鲁斯卡尔的伪代码及流程图

void MiniSpanTree_Kruskal(Edge E[],MGraph G,int n) {int i,j,m1,m2,sn1,sn2,k,vset[100]; char u,v; for (i=0;i{ u=E[j].u;v=E[j].v; m1=locateMG(G,u);m2=locateMG(G,v); sn1=vset[m1];sn2=vset[m2]; if (sn1!=sn2) { printf(\" 边 (%c,%c)权为：%d\\n\ for (i=0;i6

开始I=0NI3、迪杰斯特拉算法的伪代码及流程图

void ShortestPath_DIJ(MGraph G,char v) { int M[50][50];

int v0=locateMG(G,v); for(int i=0;ichar path[20]; int s[20]; int mindis,i,j,u,n=G.vexnum; for (i=0;is[v0]=1;path[v0]='a'; for (i=0;i} DisPath(G,dist,path,s,n,v); }

8

开始I=0NI4、拓扑排序的伪代码及流程图

void TopologicalSort(ALGraph G){ SqStack S; ArcNode *p;

int indegree[G.vexnum]; char tuopoxulie[G.vexnum]; int i,k,count;

FindInDegree(G,indegree); InitStack(S); for(i=1;i<=G.vexnum;++i) if(!indegree[i]) Push(S,i); count=0;

while(!StackEmpty(S)){ Pop(S,i); tuopoxulie[count++]=G.vertices[i].data; for(p=G.vertices[i].firstarc;p;p=p->nextarc){ k=p->adjvex; if(!(--indegree[k])) Push(S,k); } }

printf(\"\\n\"); if(count>0){ printf(\"你所给的有向图的拓扑序列为：\\n(\"); for(i=1;i10

开始I=1NIadjvex;!(--indegree[k]YN输出G.vertices[i].data结束11

3、 调试设计

3.1、遇到的问题

1、不晓得怎么去从文件里面读中文。

2、在迪杰斯特拉算法还不是很了解其逻辑思路。

3.2、算法的时空分析

T(n)=O(n2)

3.3、改进设想

在进入某个功能模块时，或者某个功能的某个步骤时，可以允许出现输入错

误，因此，要实现进入某个步骤时实现撤销操作…..

3.4、经验体会

虽说此次是任选题，实质上是必选题，此次的题目比较难。我前面的一位同

学的题目是我7大小题中的一个小题。表示鸭梨很大。由于第一次接触到C语言的操作文件，在探索过程中有点枯燥繁琐。弄好了文件，接下来的就更难了。什么普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、拓扑排序。不是数据结构书就可以搞定的。这些算法需要的辅助很多。因此要狠清楚的了解她们的逻辑关系。不过，虽然有点难。但在编程上有了很大的飞跃

4、 测试结果

4.1输出有向图邻接矩阵信息

12

4.2输出有向图邻接表信息

4.3输出普里姆算法的结果

4.4输出克鲁斯卡尔算法的结果

13

4.6输出拓扑排序算法的结果

5、 参考文献

1、数据结构（C语言版）——严蔚敏、吴伟民 2、C程序设计（第三版）——谭浩强

14