搜索
数据结构课程设计实验报告班级：10010706姓名：杨德刚学号：2007302415电话：15891480939日期：2008.11.4第一部分：求最短路径◎实验题目:求最短路径◎实验目的：通过编写程序，加强对网的结构建立和最短路径算法◎实验内容：已知n个顶点的有向网的顶点为V1,V2,V3,…,Vn,其代价矩阵定义为Dn×n=dij,描述如下：dij表示顶点i到顶点j的距离。编写程序，找出任意两个顶点之间的最短路径并输出路径及路径长度。能够建立有向网的储存结构，输入任意两个顶点，均能找出它们之间的最短路径。一、程序形式1．本演示程序中，进入运行界面，程序提示输入操作和数据存放文件名及起终点，然后程序读入数据后建立有向网数据结构，输入完毕后输出结果。2．程序执行的命令包括：（1）输入要进行的操作和数据存放文件名（2）构造有向网（3）输入起终点并求得最短路径（4）输出结果（5）结束。3．程序数据存储格式：6（顶点个数）v0v1v2v3v4v5（顶点名）05010-145-1（边）-10155010-120-1015-1-1-120-1035-1-1-1-1300-1-1-1-13-104．运行界面：二概要设计为了实现上述操作，可以以图为数据结构并以邻接矩阵为其存储结构1.图定义typedefcharvnode;//顶点的名字typedefstruct{vnode**vex;//图的顶点intvexnum,arcnum;//图的顶点数和弧数int**arc;//图的弧}ALGraph;2.各函数及其作用1).求得顶点在图中顶点数组中的下标函数intlocatevex(ALGraph*G,char*v1)初始条件：图的顶点数组已经输入操作结果：得到v1在图中顶点数组中的下标,并返回2).构造图函数（三元组）voidcreatGraph(ALGraph*G,char*fi)操作结果：输入各个顶点及弧的信息构造图(三元组)3).构造图函数（矩阵）VoidcreatGraphm(ALGraph*G,char*fi)操作结果：输入各个顶点及弧的信息构造图（矩阵）4).打印输出最短路径函数voidprintpath(ALGraph*G,inti,int**p,long*d)初始条件：图已经建立并且已求得最短路径操作结果：输出以数组下标i为起点的最短路径5).求最短路径函数voidshortestpath(ALGraph*G,char*sou)初始条件：图已经构造完毕，即各个顶点和狐的信息已经输入操作结果：得到从sou始的所有顶点的最短路径6).主函数voidmain()初始条件：各个基本操作已经实现，图已建立操作结果：求得图的最短路径并输出3．本程序包含五个模块：（1）主程序模块：main()（2）求得顶点在图中顶点数组中的下标模块:locatevex()（3）构造图模块:creatGraph()或creatGraphm()（4）打印输出最短路径模块（5）求最短路径模块4.模块调用图：详细设计见源码。三、主要算法迪杰斯特拉算法，每次求得从i到某个顶点v的最短路径，直到求得到终点的最短路径。for(k=1;kG-vexnum;++k){v=-1;min=Maxint;for(w=0;wG-vexnum;++w)if(!final[w])if(d[w]min){v=w;min=d[w];}//w离起点更近final[v]=TRUE;if(v==-1)continue;//与已经访问的顶点间无路径else//有路径,更新{for(w=0;wG-vexnum;++w)//更新当前最短路径及最近距离{if(!final[w]&&((min+G-arc[v][w])d[w])){d[w]=min+G-arc[v][w];for(j=0;jG-vexnum;++j){p[w][j]=p[v][j];p[w][w]=TRUE;}}}}if(final[de]==TRUE)break;//已经求得最短路径}四、实验总结1.本次实验体会：主程序模块Main()构造图模块creatGraph()或creatGraphm()求最短路径模块shortestpath()求得顶点在图中顶点数组中的下标模块locatevex()locatevex()打印输出最短路径模块printpath()1）.程序要不断修改，即使是经典算法，但因为人的不同也会有不一样的效率。2）.努力使程序增强对特殊情况的处理能力。3）.尽量对不同情形提供多的应对策略。4).很多算法都有其特殊适用性，很少有完美的的算法。2．算法设计思想：本算法为贪心算法，贪心算法一般地分阶段求解一个问题，在每个阶段它都把当前出现的当作是最好去处理,即局部的最优。3.算法的时空分析和改进设想：本程序算法所用空间为图的邻接矩阵存储结构空间及辅助运算空间。求最短路径时间复杂度为O(n*n)。当用邻接表作存储结构时，可以缩短一些时间，但时间复杂度仍为0(n*n)。对于路径的记录方法，可以采用只记录每个顶点前面点的方法，这样可以倒推求得路径，同时可以节省存储空间和缩短程序运算时间。但是根本上时间复杂度仍不变为0(n*n)。本程序也可以用弗洛伊德算法，对于同一个图的最短路径问题，弗洛伊德算法O(n*n*n)可以一次求得所有点间的最短路径，可以不必像迪杰斯特拉算法那样对于同一个图每次都要重新求最短路径，但对于不同图两者都要重新执行，而且迪杰斯特拉算法时间复杂度要更小，所以对于同一个图求多个路径可能弗洛伊德算法要好一些，但对于不同图则迪杰斯特拉算法要优。4．调试算法过程中出现的问题及改进方法：1）.程序中有判断路径最大值（不通）与一个数相加后是否大于最大值的语句，如果定义最大值为0x7fffffff（整型最大正值），则与一个正数相加后变为负数，结果比最大值小的到错误结果，改进是以整型最大正值的一半视为不通的临界点，大于其则视为不通。当然可视具体情况将路径长度类型改为long或unsignedint类型，但同样的问题依然会存在。2）.当两点间无路径时若要求得最短路径时出错，可能是没有处理特殊情况的语句。一定要将特殊异常情况考虑在内。第二部分：排序算法验证及评价◎实验题目:排序算法验证及评价（排序器）◎实验目的：通过编写内部排序算法程序，加深排序算法的理解和掌握，同时对这四种算法在特定数据条件下的效率进行分析和评判，理解各个算法的效率优劣。◎实验内容：实现以下六种排序算法，将给定的不同规模大小的数据文件（data01.txt，data02.txt，data03.txt，data04.txt）进行排序，并将排序结果分别存储到sorted01.txt，sorted02.txt，sorted03.txt和sorted04.txt文件中。1）、Shell排序；2）、Quick排序3）、锦标赛排序；4）、堆排序5）、归并排序；6）、基数排序在实现排序算法1）~4）时，统计数据元素比较的次数和交换的次数，进而对这四种算法在特定数据条件下的效率进行分析和评判。一、程序形式1．本演示程序中，进入运行界面，程序提示输入操作（排序方式）和数据存放文件名，然后程序读入数据后建立顺序表，输入完毕后程序进行排序并输出到文件，同时统计比较和交换次数。2．程序执行的命令包括：（1）输入要进行的操作和数据存放文件名（2）读入数据构造顺序表（3）进行排序（4）输出结果到文件（5）结束。3．程序数据存储格式：45(1)（数据及出现次数）4．运行界面：二概要设计为了实现排序操作，可以以顺序表为数存储结构（各个不同的排序算法使用同样的顺序表）。1.顺序表定义typedefstruct//存放数据及其出现次数{intdata;charc[5];//出现次数最大999次}node;2.各函数及其作用1).希尔排序驱动及增量数组求解函数voiddlta(node*d,intnum,int&jc,int&bc)初始条件：存储数据顺序表已经建立操作结果：求得增量数组和驱动希尔排序程序2).希尔排序函数voidshellsort(node*d,intnum,intdlt[],intt,int&jc,int&bc)初始条件：存储数据顺序表已经建立和已经求得增量数组操作结果：以递减增量进行shell排序3).固定增量排序函数voidshellinsert(node*d,intnum,intinc,int&jc,int&bc)初始条件：存储数据顺序表已经建立和增量已给定操作结果：以给定增量inc作一趟希尔排序4).快速排序函数voidquicksort(node*d,intlow,inthigh,int&jc,int&bc)初始条件：存储数据顺序表已经建立操作结果：对顺序表d中的从low到high的子列作快速排序5).交换枢轴两边数据函数intpartition(node*d,intlow,inthigh,int&jc,int&bc)初始条件：存储数据顺序表d已经建立操作结果：交换顺序表d中的从low到high的子表记录，使枢轴记录到位，并返回其所在位置，此时在它之前（后）的记录均不大（小）于它6).锦标赛排序函数voidtreesort(node*&d,node*r,intnum,int&jc,int&bc)初始条件：存储数据顺序表d已经建立操作结果：将顺序表d中数据按树形选择进行排序7).建立初始排序树函数voidtreejust(node**t,node*d,inti,intnum,int&jc,int&bc)初始条件：存储数据顺序表d已经建立操作结果：以d中数据建立最初的排序树，除叶子结点外，树的第i层存储在t[i]中8).堆排序函数voidheapsort(node*d,intnum,int&jc,int&bc)初始条件：已经读入数据建立顺序表d操作结果：对顺序表d进行堆排序9).调大顶堆函数voidheapadjust(node*d,ints,intm,int&jc,int&bc)初始条件:已知d[s...m]中记录的关键字除之d[s]外均满足堆的定义操作结果：调整d[s]的关键字，使成为一个大顶堆10）.归并排序驱动函数voidmergesort(node*&d,intnum)初始条件：已经读入数据建立顺序表d操作结果：对顺序表d作归并排序11).归并排序递归函数voidmsort(node*d,node*p,ints,intt)初始条件：已经读入数据建立顺序表d操作结果：将d[s...t]归并为p[s...t]12).归并函数voidmerge(node*rs,node*d,inti,intm,intn)初始条件：rs[s...m]和rs[m+1...t]已经按关键字有序操作结果：将有序rs[s...m]和rs[m+1...t]归并为有序的d[s...t]13).基数排序函数voidradixsort(node*d,intnum,int*r,intmax)初始条件：存储数据顺序表d和顺序号数组r已经建立操作结果：对d作基数排序，其顺序号存储于r数组中，r[0]为头结点14).关键字映射函数intord(intp,inti,node*d)操作结果：将d[p]中第i个关键字映射到[0...9]15).基数排序分配函数voiddistribute(int*r,inti,int*f,int*e,node*d)初始条件：存储数据顺序表d已经建立操作结果：按d中各个数据第i个关键字建立RADIX各个子表，使同一子表中记录的第i个关键字相同16).基数排序收集函数voidcollect(int*r,inti,int*f,int*e)初始条件：已按d中各个数据第i个关键字建立RADIX各个子表操作结果：按第i个关键字自小至大地将f[0...9]所指各个子表依次链接成一个链表17).主函数voidmain()初始条件：各个基本排序操作已经实现操作结果：驱动各个排序函数3．本程序包含十七个模块：（1）主程序模块：main()（2）希尔排序驱动及增量数组求解函