《数据结构——xxxxx学院课程设计书》由会员分享，可在线阅读，更多相关《数据结构——xxxxx学院课程设计书（16页珍藏版）》请在金锄头文库上搜索。
1、XXXXXXXXXXXX学院 课 程 设 计课程名称_数据结构课程设计_题目名称_单源结点最短路径问题_学生学部（系）_计算机与艺术设计学部_专业班级_ _学 号_学生姓名_ _指导教师_ _ 2010年 1 月 15 日广东工业大学华立学院课程设计任务书题目名称单源结点最短路径问题学生学部（系）计算机与艺术设计学部专业班级姓 名学 号一、课程设计的内容求从有向图的某一节点出发到其余各结点的最短路径。有向图采用邻接矩阵表示,应用狄克斯特拉算法，输出有向图中从源结点到其余结点的最短路径值。学习相关开发工具和应用软件，熟悉系统建设过程。二、课程设计的要求与数据分步实施：（1）初步完成总体设计，搭好
2、框架；（2）完成最低要求：两种必须都要实现，写出画的思路；（3）进一步要求：画出图的结构，有兴趣的同学可以进一步改进图的效果。要求：（1）界面友好，函数功能要划分好（2）总体设计应画一流程图（3）程序要加必要的注释。（4）要提供程序测试方案（5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。三、课程设计应完成的工作(1)编写算法；(2)算法测试，并有具体测试结果；(3)撰写课程设计报告。四、课程设计（论文）进程安排序号设计（论文）各阶段内容地点起止日期1审题、搜集资料综合楼7022010-12-28至2010-1-12编写算法并测试综合楼7022010-1-
3、4至2010-1-83撰写课程设计报告综合楼7022010-1-11至2010-1-15五、应收集的资料及主要参考文献1 朱战立.数据结构-使用C语言M.北京：电子工业出版社,2009.2 Clifford A shaffer.数据结构与算法分析M.北京：电子工业出版社，20063 Sartaj Sahni.数据结构、算法与应用M.张小潘,译.北京：机械工业出版社,2006.4 梁田贵，张鹏. 算法设计与分析M北京: 冶金工业出版社,2004.5 广树健.C语言程序设计M.广东:华南理工大学出版社,2008.6 胡学刚. 算法与数据结构算法设计指导M.北京: 清华大学出版社,20007 许卓群
4、，杨冬青，唐世渭，张铭. 数据结构与算法M.北京: 高等教育出版社,2004.发出任务书日期：2009 年 12 月 28 日 指导教师签名：计划完成日期： 2010 年 1 月 15 日 教学单位责任人签章：目 录1 设计内容12 算法思想描述53 算法及程序实现154 算法测试及结果155 总结15参考资料151设计内容单元结点最短路径问题。 问题描述：求从有向图中的某一结点出发到其余各结点的最短路径。 基本要求： （1）有向图采用邻接矩阵表示。 （2）单元结点最短路径问题采用狄克斯特拉算法。（3）输出有向图中从源结点到其余各结点的最短路径和最短路径值。测试数据：如下图有向带权图所示2算法
5、思想描述狄克斯特拉算法思想：设置两个顶点的集合S和T，集合S中存放已找到最短路径的顶点，集合T中存放当前还未找到路径的顶点。初始状态时，集合S中包含源点，设为v0，然后从集合T中选择v0路径长度最短的顶点u加入到集合S中，集合S中每加入一个新的顶点u，都要修改源点v0到集合T中剩余顶点的当前最短路径的当前最短路径长度值，集合T中各顶点的新的当前最短路径长度值为原来的当前最短路径长度值与从源点过顶点u到达该顶点的路径长度中的较小者。此过程不断重复，直到集合T中的顶点全部加入到集合S中为止。3算法及程序实现#include #includetypedef char DataType; /定义顺序表
6、的数据类型为char#define MaxSize 10 /定义顺序表数组的最大个数#define MaxVertices 10 /定义顶点的最大个数#define MaxWeight 10000 /定义权值的具体最大值#include AdjMGraph.h /包含AdjMGraph.h头文件#include AdjMGraphCreate.h /包含AdjMGraphCreate.h头文件#include Dijkstra.h /包含Dijkstra.h函数的文件void main(void)AdjMGraph g;char a=A,B,C,D,E,F;RowColWeight rcw=
7、0,1,10,0,2,12,1,3,16,1,4,25,2,0,4,2,1,3,2,3,12,2,5,8,3,4,7,5,3,2,5,4,10;int i,n=6,e=11;int distance6,path6;CreatGraph(&g,a,n,rcw,e);Dijkstra(g,0,distance,path); printf(nt从顶点%c到其余各顶点的最短路径值分别为:n,g.Vertices.list0); for(i=1;in;i+)printf(t%c到%c 的最短路径值为:%dn, g.Vertices.list0,g.Vertices.listi,distancei); p
8、rintf(nt从顶点%c到其余各顶点的最短路径的前一顶点为:n,g.Vertices.list0); for(i=1;in;i+)if(pathi !=-1) printf(t%c到%c 的最短路径的前一顶点为%cn,g.Vertices.list0, g.Vertices.listi,g.Vertices.listpathi);4算法测试及结果从程序的运行结果，再结合测试数据的有向带权图，可以得出，从顶点A到其余各顶点的最短路径及距离如下。A到B： 最短路径为（A，B），其距离为 10A到C： 最短路径为（A，C），其距离为 12A到D： 最短路径为（A，C，F，D），其距离为 22A到E
9、： 最短路径为（A，C，F，D，E），其距离为 29A到F： 最短路径为（A,C,F）,其距离为205总结课程设计对学生而言是其对所学课程内容掌握情况的一次自我验证，从而有着极其重要的意义。通过课程设计能提高学生对所学知识的综合应用能力，能全面检查并掌握所学内容；数据结构从课程性质上讲是一门专业基础课，它的目的和任务就是训练学生对计算机加工的数据对象进行分析的能力，选择适当的数据结构及相应算法的能力，训练学生的编码以及调试能力，进而增加其对学习和应用相关专业课的兴趣。 通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中
10、得出结论，将结论用于实践，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中当然遇到了问题，可以说得是困难重重，毕竟这是不可避免的，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固。由于编程水平有限，其中头文件和狄杰斯特拉算法的函数设计等是参考书上资料，我想在以后的学习中，要更注重实践这一环节。在设计的过程中遇到种种问题，同时在设计的过程中发现了自己的不足之处，对一些前面学过的知识理解得不够深刻，掌握得不够牢固，通过这次课程设计之后，我们把前面所学过的知识又重新温故了一遍。从设计过程看，在整整半个月的日子里，做到精益求精，学到了很多很多的东西，同
11、时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。从设计结果看，设计要求完成任务，达到了预期的目的，设计、演示效果较好。最主要是从中学到了知识。参考资料1 朱战立.数据结构-使用C语言M.北京：电子工业出版社,2009.2 Clifford A shaffer.数据结构与算法分析M.北京：电子工业出版社，20063 Sartaj Sahni.数据结构、算法与应用M.张小潘,译.北京：机械工业出版社,2006.4 梁田贵，张鹏. 算法设计与分析M北京: 冶金工业出版社,2004.5 广树健.C语言程序设计M.广东:华南理工大学出版社,2008.6 胡学刚. 算法与数据结
12、构算法设计指导M.北京: 清华大学出版社,20007 许卓群，杨冬青，唐世渭，张铭. 数据结构与算法M.北京: 高等教育出版社,2004.附件：AdjMGraph.h头文件#include SeqList.h /包含顺序表头文件typedef structSeqList Vertices; /存放顶点的顺序表int edgeMaxVerticesMaxVertices; /存放边的邻接矩阵int numOfEdges; /边的条数AdjMGraph; /图的结构体定义void Initiate(AdjMGraph *G,int n) /初始化int i,j;for(i=0;in;i+)for(
13、j=0;jedgeij=0;else G-edgeij=MaxWeight; /MaxWeight表示无穷大G-numOfEdges=0; /边的条数置为0ListInitiate(&G-Vertices); /顺序表初始化void InsertVertex(AdjMGraph *G,DataType vertex) /在图G中插入顶点vertexListInsert(&G-Vertices,G-Vertices.size,vertex); /顺序表尾插入void InsertEdge(AdjMGraph *G,int v1,int v2,int weight) /在图G中插入边,边的权为weightif(v1G
