《迪杰斯特拉算法实验报告(共9篇)》由会员分享，可在线阅读，更多相关《迪杰斯特拉算法实验报告(共9篇)（21页珍藏版）》请在金锄头文库上搜索。
1、为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划迪杰斯特拉算法实验报告(共9篇)青岛理工大学琴岛学院课题名称：数据结构课程设计青岛理工大学琴岛学院教务处XX年6月29日数据结构课程设计报告迪杰斯特拉算法的实现班级：软件1408学号：31姓名：齐瑞征指导教师：石锋完成时间：要求：基于邻接矩阵存储结构，使用迪杰斯特拉算法，计算并输出指定源点到其余各顶点的最短路径及长度。程序的输入：顶点的个数、边的个数、各个边的起点编号、终点编号和权值，源点编号。程序输出：源点到各顶点最短路径及长度。例如对于教材P141图6-16，输入数据的形式为：顶
2、点个数：6边的个数：8第1条边的起点、终点编号及权值：0,2,10第2条边的起点、终点编号及权值：0,4,30源点编号：0以上为程序运行时输入的数据。程序输出结果如下：0号到1号的最短路径为：null，长度为无穷大0号到2号的最短路径为：0,2长度为10以上为程序输出数据。实现过程：1、在VC中建立源程序，名称为：，保存在工作文件夹中；2、在中输入以下内容：#include#include#include#include#defineMAX_NAME5/顶点字符串的最大长度+1#defineMAX_INFO20/相关信息字符串的最大长度+1typedefintVRType;/顶点关系的数据类型
3、#defineINFINITYINT_MAX/用整型最大值代替#defineMAX_VERTEX_NUM20/最大顶点个数typedefcharInfoType;/信息的类型typedefcharVertexTypeMAX_NAME;/顶点数据类型及长度typedefenumDG,DN,AG,ANGraphKind;typedefstructVRTypeadj;InfoType*info;ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedefstructVertexTypevexsMAX_VERTEX_NUM;/顶点向量AdjMatrixar
4、cs;/邻接矩阵intvexnum,/图的当前顶点数arcnum;/图的当前边数GraphKindkind;/图的种类标志MGraph;#include#defineMAX100/顶点最大个数#defineINFINITY99999/99999代表无穷大typedefstructintn,e;/顶点个数，边的个数intedgesMAXMAX;/存放邻接矩阵Mgraph;3、在中完成如下函数，功能是从键盘接收图的数据，存放在*g中。voidCreatemgraph(MGraph*G)inti,j,k,w,IncInfo=0;charsMAX_INFO,*info;VertexTypeva,vb;
5、printf(请输入顶点数,边数:(空格隔开)n);scanf(%d%d%d%*c,&(*G).vexnum,&(*G).arcnum,&IncInfo);printf(请输入%d个顶点的值()t算法。算法的输入是；输出记录为文件：；同时记录运行时间为TimeIS。3.实现快速排序算法.要求：实现QuickSort算法。算法的输入是；输出记录为文件：；同时记录运行时间为TimeQS。算法的基本思想直接插入排序：假设待排序的n个记录R0，R1，Rn顺序存放在数组中，直接插入法在插入记录Ri(i=1，2，n-1)时，记录被划分为两个区间R0,Ri-1和Ri+1,Rn-1,其中，前一个子区间已经排好
6、序，后一个子区间是当前未排序的部分，将关键码Ki与Ki-1Ki-2，K0依次比较，找出应该插入的位置，将记录Ri插，然后将剩下的i-1个元素按关键词大小依次插入该有序序列，没插入一个元素后依然保持该序列有序，经过i-1趟排序后即成为有序序列。每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。快速排序：快速排序是基于分治模式的。假设待排序数组Ap.r。分解：数组Ap.r被划分成两个子数组Ap.q-1和Aq+1.r,使得Ap.q-1中的每个元素都小于等于A(q)，而且，小于等于Aq+1.r中的元素。小标q也在这个划分过程中进行计算。解决：通过
7、递归调用快速排序，对子数组Ap.q-1和Aq+1.r排序。合并：因为两个子数组是就地排序的，将它们合并不需要操作：整个数组Ap.r已排序。算法实现直接插入排序：voidinsert_sort(ElemTypea,intn)/待排序元素用一个数组a表示，数组有n个元素inti,j;ElemTypet;for(i=1;i=0)&(tlength-1);intmid=0;mid=partition(list,low,hight);/endifQsort(list,low,mid-1);/对左边的无序数列进行排序Qsort(list,mid+1,hight);/对右边的无序数列进行排序intparti
8、tion(SqList*list,intlow,inthight)ElemTypemid=list-arraylow;while(lowarrayhight=mid)swap(list,low,hight);while(lowarraylowarraylow;list-arraylow=list-arrayhight;list-arrayhight=temp;快速排序的时间复杂度是O(nlog2n)。实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。三、程序流程图1.直接插入排序程序流程图数据结构课程设计报告迪杰斯特拉算法的实现班级：软件学号：姓名：马宏伟指导
9、教师：石老师完成时间：XX年7月5日题目:Dijkstra算法的实现一、问题分析和任务定义题目：对任意图，选择合适的数据结构表示图，在此基础上实现求解最短路径的Dijkstra算法。要求：对所设计的图的数据结构，提供必要的基本功能。具体任务：建立图的表示模块，顶点的插入和删除操作模块；在建立图之后从单源点开始求最短路径，并显示出最短路径长度及路径途径！2、实现功能：建立有向图在建立好的有向图中，显示出来从源点到其他各个顶点的最短路径长度及路径途径。3、测试用例：正确数据：a）顶点：3；边值信息：012；103；125；216；000；b）顶点：0；边值信息：000；错误数据：a）顶点：#；b）
10、顶点：3；边值信息：01#；参考用图：图1图1.有向图问题分析:题目要求选择合适的数据结构表示图，本程序邻接矩阵存储结点和弧等图的有关信息对用邻接矩阵表示的有向图，从某一顶点出发(称为源点)到该图其他各顶点(称为终点)有无路径？最短路径是什么？路径长为多少？问题要求写一个程序从有向网中的某一顶点出发找出该顶点到其余各顶点的最短路径。对邻接矩阵arscnn中的每一个元素只能有三种情况：当顶点i到j无边时，distancej=MAX;当顶点i到j有边且权值为edgesij时，distancej=edgesij;当顶点i到就经过t有最短路径时，distancej=distancet+edgestj;
11、由于题目中没有规定输出格式，本程序以顶点序号的形式将最短路径输出到终端上去，并输出该最短路径的长度及路径途径。二、数据结构的选择和概要设计1)数据存储结构以邻接矩阵存储有向图，如图2中有向图G所示，其邻接矩阵为图3edges。2020500201015045103500图2.有向图图3.矩阵edges有向图的邻接矩阵arcsij定义为intedgesMAX_VERTEX_NUMMAX_VERTEX_NUM;2)概要设计对用邻接矩阵表示的有向图，从某一顶点出发(称为源点)到该图其他各顶点(称为终点)有无路径？最短路径是什么？路径长为多少？问题要求写一个程序从有向网中的某一顶点出发找出该顶点到其余
12、各顶点的最短路径。对邻接矩阵edgesMAX_VERTEX_NUMMAX_VERTEX_NUM中的每一个元素只能有三种情况：当顶点i到j无边时，distance=MAX;当顶点iedgesMAX_VERTEX_NUMMAX_VERTEX_NUM时到j有边且权值为，distancej=edgesMAX_VERTEX_NUMMAX_VERTEX_NUM.当顶点i到就经过t有最短路径时，distancej=distancet+edgestj;建立图的表示模块，顶点的插入和删除操作模块；在建立图之后从单源点开始求最短路径，并显示出来！流程图如图4图4.程序流程图结点类型和指针类型typedefstru
13、ct/定义顶点类型.河南科技大学课程设计说明书课程名称数据结构课程设计题目哈夫曼编/译码器的设计与实现院系信息工程学院班级物联网141班学生姓名沈成龙指导教师黎蔚、刘中华日期弗洛伊德算法实验报告一、实验目的：利用图的最短路径原理为用户提供路径咨询，掌握求最短路径的算法并编程实现。二、实验要求：学习了解图的存储结构，掌握求最短路径的两种算法。1.算法设计思想：弗洛伊德算法是用邻接矩阵cost表示带权有向图。如果从顶点Vi到Vj有弧，则从到Vj存在一条长度为costij的路径，该路径不一定是最短路径，需要进行n次试探。首先考虑路径是否存在是否存在），如果存在，则比较和的路径长度，取较短者为从vi到vj的中间顶点序号不大于1的最短路径、在路径上再增加一个顶点v2，若和分别是当前找到的中间顶点序号不大于1的最短路径，则就有可能是从vi到vj的中间顶点的序号不大于2的最短路径。将他和已经得到从vi到vj中间顶点序号不大于1的最短路径比较，从中选出长度较短者作为从vi到vj中间顶点序号不大于2的最短路径之后，再增加一个顶点v3，继续进行试探，依次类推。在一般情况下，若和分别是从vi到vk和vk到vj的中间顶点序号不大于k-1的最短路径，则将和已经得到的vi到vj且中间顶点序号不大于k-1的最短路径
