数据结构——xxxxx学院课程设计书.doc

XXXXXXXXXXXX学院 课 程 设 计课程名称_数据结构课程设计_题目名称_单源结点最短路径问题_学生学部（系）_计算机与艺术设计学部_专业班级_ _学 号_学生姓名_ _指导教师_ _ 2010年 1 月 15 日广东工业大学华立学院课程设计任务书题目名称单源结点最短路径问题学生学部（系）计算机与艺术设计学部专业班级姓 名学 号一、课程设计的内容求从有向图的某一节点出发到其余各结点的最短路径。有向图采用邻接矩阵表示,应用狄克斯特拉算法，输出有向图中从源结点到其余结点的最短路径值。学习相关开发工具和应用软件，熟悉系统建设过程。二、课程设计的要求与数据分步实施：（1）初步完成总体设计，搭好框架；（2）完成最低要求：两种必须都要实现，写出画的思路；（3）进一步要求：画出图的结构，有兴趣的同学可以进一步改进图的效果。要求：（1）界面友好，函数功能要划分好（2）总体设计应画一流程图（3）程序要加必要的注释。（4）要提供程序测试方案（5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。三、课程设计应完成的工作(1)编写算法；(2)算法测试，并有具体测试结果；(3)撰写课程设计报告。四、课程设计（论文）进程安排序号设计（论文）各阶段内容地点起止日期1审题、搜集资料综合楼7022010-12-28至2010-1-12编写算法并测试综合楼7022010-1-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 许卓群，杨冬青，唐世渭，张铭. 数据结构与算法M.北京: 高等教育出版社,2004.发出任务书日期：2009 年 12 月 28 日 指导教师签名：计划完成日期： 2010 年 1 月 15 日 教学单位责任人签章：目 录1 设计内容12 算法思想描述53 算法及程序实现154 算法测试及结果155 总结15参考资料151设计内容单元结点最短路径问题。 问题描述：求从有向图中的某一结点出发到其余各结点的最短路径。 基本要求： （1）有向图采用邻接矩阵表示。 （2）单元结点最短路径问题采用狄克斯特拉算法。（3）输出有向图中从源结点到其余各结点的最短路径和最短路径值。测试数据：如下图有向带权图所示2算法思想描述狄克斯特拉算法思想：设置两个顶点的集合S和T，集合S中存放已找到最短路径的顶点，集合T中存放当前还未找到路径的顶点。初始状态时，集合S中包含源点，设为v0，然后从集合T中选择v0路径长度最短的顶点u加入到集合S中，集合S中每加入一个新的顶点u，都要修改源点v0到集合T中剩余顶点的当前最短路径的当前最短路径长度值，集合T中各顶点的新的当前最短路径长度值为原来的当前最短路径长度值与从源点过顶点u到达该顶点的路径长度中的较小者。此过程不断重复，直到集合T中的顶点全部加入到集合S中为止。3算法及程序实现#include #includetypedef char DataType; /定义顺序表的数据类型为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= 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); printf(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： 最短路径为（A，C，F，D，E），其距离为 29A到F： 最短路径为（A,C,F）,其距离为205总结课程设计对学生而言是其对所学课程内容掌握情况的一次自我验证，从而有着极其重要的意义。通过课程设计能提高学生对所学知识的综合应用能力，能全面检查并掌握所学内容；数据结构从课程性质上讲是一门专业基础课，它的目的和任务就是训练学生对计算机加工的数据对象进行分析的能力，选择适当的数据结构及相应算法的能力，训练学生的编码以及调试能力，进而增加其对学习和应用相关专业课的兴趣。 通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，将结论用于实践，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中当然遇到了问题，可以说得是困难重重，毕竟这是不可避免的，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固。由于编程水平有限，其中头文件和狄杰斯特拉算法的函数设计等是参考书上资料，我想在以后的学习中，要更注重实践这一环节。在设计的过程中遇到种种问题，同时在设计的过程中发现了自己的不足之处，对一些前面学过的知识理解得不够深刻，掌握得不够牢固，通过这次课程设计之后，我们把前面所学过的知识又重新温故了一遍。从设计过程看，在整整半个月的日子里，做到精益求精，学到了很多很多的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。从设计结果看，设计要求完成任务，达到了预期的目的，设计、演示效果较好。最主要是从中学到了知识。参考资料1 朱战立.数据结构-使用C语言M.北京：电子工业出版社,2009.2 Clifford A shaffer.数据结构与算法分析M.北京：电子工业出版社，20063 Sartaj Sahni.数据结构、算法与应用M.张小潘,译.北京：机械工业出版社,2006.4 梁田贵，张鹏. 算法设计与分析M北京: 冶金工业出版社,2004.5 广树健.C语言程序设计M.广东:华南理工大学出版社,2008.6 胡学刚. 算法与数据结构算法设计指导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(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-Vertices.size|v2G-Vertices.size)printf(参数v1或v2越界出错!n);return;G-edgev1v2=weight;G-numOfEdges+;void DeleteEdge(AdjMGraph *G,int v1,int v2)/在图G中删除边if(v1G-Vertices.size|v2G-Vertices.size|v1=v2)printf(参数v1或v2越界出错!n);return;if(G-edgev1v2=MaxWeight|v1=v2)printf(该边不存在!n);return;G-edgev1v2=MaxWeight;G-numOfEdges-;int GetFirstVex(AdjMGraph G,int v)/在图G中寻找序号为V的顶点的第一个邻接顶点/如果这样的邻接顶点存在，则返回该邻接顶点的序号；否则返回-1int col;if(vG.Vertices.size)printf(参数v1越界出错!n);return -1;for(col=0;col0&G.edgevcolMaxWeight)return col;return -1;int GetNextVex(AdjMGraph G,int v1,int v2)/在图G中寻找v1顶点的邻接顶点v2的下一个邻接顶点/如果这样的邻接顶点存在，则返回该邻接顶点的序号；否则返回-1/v1和v2都是相应顶点的序号int col;if(v1G.Vertices.size|v2G.Vertices.size)printf(参数v1或v2越界出错!n);return -1;for(col=v2+1;col0&G.edgev1colMaxWeight)return col;return -1;AdjMGraphCreate.h头文件typedef structint row; /行下标int col; /列下标int weight; /权值RowColWeight; /边信息结构体定义void CreatGraph(AdjMGraph *G,DataType V,int n,RowColWeight E,int e)/在图G中插入n个顶点信息V和e条边信息Eint i,k;Initiate(G,n); /顶点顺序表初始化for(i=0;in;i+)InsertVertex(G,Vi); /插入顶点for(k=0;ke;k+) InsertEdge(G,Ek.row,Ek.col,Ek.weight); /插入边Dijkstra.h头文件void Dijkstra(AdjMGraph G,int v1,int distance,int path)/带权图G从下标v0顶点到其他顶点的最短距离distance和最短路径下标path int n=G.Vertices.size; int *s=(int *)malloc(sizeof(int)*n); int minDis,i,j,u; /初始化for(i=0;in;i+)distancei=G.edgev1i;si=0;if(i !=v1 & distancei MaxWeight)pathi=v1;else pathi=-1;sv1=1; /标记顶点v0已从集合T加入到集合S中/在当前还未找到最短路径的顶点集中选取具有最短距离的顶点ufor(i=1;in;i+)minDis=MaxWeight;for(j=0;jn;j+)if(sj=0 & distancejminDis)u=j;minDis=distancej;/当已不再存在路径时，算法结束。此语句对非连通图是必需的if(minDis=MaxWeight) return;su=1; /标记顶点u已从集合T加入到集合S中/修改从v0到其他顶点的最短距离和最短路径for(j=0;jn;j+)if(sj=0 & G.edgeujMaxWeight & distanceu+G.edgeujsize=0; /定义初始数据元数个数int ListLength(SeqList L) /返回顺序表L的当前数据元数个数return L.size;int ListInsert(SeqList *L,int i,DataType x)/在顺序表L的第i(0=isize =MaxSize)printf(顺序表已满无法插入!n);return 0;else if(iL-size)printf(参数i不合法!n);return 0;else /从后向前依次后移数据，为插入做准备for(j=L-size;ji;j-)L-listj=L-listj-1;L-listi=x; /插入xL-size+; /元素个数加1return 1;int ListDelete(SeqList *L,int i,DataType *x)/删除顺序表L中位置i(0=isize =0)printf(顺序表已空无数据元素可删!n);return 0;else if(iL-size-1)printf(参数i合法!n);return 0;else *x=L-listi; /保存删除的元素到x中/从前向后依次前移for(j=i+1