算法与数据结构课程项目设计方案

- 0 - 算法与数据结构课程项目设计方案 一、课设目的与要求 本次课设主要是图的基本操作与应用，共包括四个部分：有向图的基本操作与应用、无向图的基本操作与应用、有向网的基本操作与应用、无向网的基本操作与应用。 测试文件 (给出 。 * # n; n) : G); : : n; LG,n); : n; LG,n); n!=5) n; n) : G); : : G); n; G,n); : G); G); n!=5) n; n) : G); : : n!=4) n; n) : G); : : : G); n; G,n); : G); G); n!=6) n; n) : ; : ; : ; : ; n!=5) ,p- p=p- 算法运行结果如下图所示： 在遍历时，对图中每个顶点至多访问一次 为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。对于 当用邻接矩阵作其存储结构时，深度遍历图 的时间复杂度为 O(而当以邻接表作其存储结构时，深 - 8 - 度优先遍历图的时间复杂度为 O(n+e)。 广度优先遍历 类似于树的层次遍历。其基本思想是：从图中某顶点 访问了 后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直到图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起点，重复上述过程，直到图中所有顶点都被访问到 为止。 以邻接表作为图的存储结构的广度 优先遍历算法如下： ,v) ; p; ); v=1; %d,%c,v,v ,v); ) , p=p) if(p-=1) p-1; %d,%c,p-p- ,p- p=p- 算法运行结果如下图所示： - 9 - * #G) i,j,c; 请输入顶点 :); i=1;ii; i=1;iij; ij=1; ji=1; i=1;iii i=1;终点序号 :,i); sd; p=(); q=(); p-d; q-s; p-s /*sp; - 11 - q-d /*dq; 算法运行结果如下图所示： ) i; p; 图 的邻接表表示如下 :n); i=1;i,i,i p=ip!= %d ,p- p=p- n); 0; ,v) p; v=1; %d,%c,v,v p=vp) p- ,p- - 12 - p=p- ,v) ; p; ); v=1; %d,%c,v,v ,v); ) , p=p) if(p-=1) p-1; %d,%c,p-p- ,p- p=p- 三 、无向网的基本操作与应用 无向图的基本操作与应用包括用邻接矩阵和邻接表创建无向网以及以邻接矩阵为存储结构的 两种算法求最小生成树 (。 计方案 用 与构造无向图相似的的方式可以构造出邻接矩阵和邻接表。无向网的邻接矩阵可定义为： A i j = 中的边或弧是或或若（反之G,i ,),(v j )v i , 其中， vi,弧 上的权值；表示 一个计算机允许的、大于所有边上权值的数。 邻接矩阵存储结构定义如下： #0 /*最大顶点数设为 20*/ /*顶点类型设为字符型 */ /*顶点表 */ /*邻接矩阵 */ - 13 - /*图中顶点数和边数 */ /*邻接矩阵存储的图类型 */ 无向网的邻接表构造方法与无向图的构造方法相似，只需要在 表结点中加入权值 代码如下： /邻接点序号 w; /边或狐上的权 /顶点信息 /指向下一个边结点 现过程 其实现过程同无向图的实现过程类 似，其边的输入由由边的两个顶点和边上的权组成 。用邻接矩阵创建无向网的函数为 G)，用邻接表创建无向网的函数为G)，其代码参见头文件 构造最小生成树可以有多种算法， 以下是 普里姆算法，克鲁斯卡尔算法 的说明。 假设 N=(V,E)是连通网， T=(U, 的顶点集合， 的边集合。普里姆算法 的基本思想是：首先从集合 假设为 入集合 时 U=，然后所有 u U， v u,v) 取具有最小权值的边 (u0,入集合 时将顶点 中。重复上述操作， 直到 U=时 T=(U, 为实现 设置一个辅助数组 录从 每个顶点 辅助数组中存在一个相应分量 它包括两个域： 中 中的顶点， /*该边依附于集合 ; /*该边的权值 */ 算法中将第 设为 )并入集合 i实现 (即用 i表示顶点 在 i表示 在 ；选取 最小权值的边，通过在所有 i0(的 i选择最小的值来实现。 不妨设无向网采用邻接矩阵存储 ()，若存在分量 i0，ii，表示顶点 j已并入 (i, j)是最小 - 14 - 生成树中的一条边。 初始状态时， U= (，初始 ，数 组的其他各分量的 ui,U,每选取一条边，设置 表示顶点 中。由于顶点 后，这两个集合的内容发生了变化，就需依据具体情况更新数组 后 当无向网采用邻接矩阵存储时， ,v) i,j,k,i=1;i请输入顶点 :); i=1;ii; i=1;iijw; ij=w; ji=w; i=1;iii i=1;终点序号，权值 :,i); sdw; p=(); q=(); p-d; q-s; p-w=w; q-w=w; p-s /*sp; q-ddq; 算法运行结果如下图所示： ,v) - 19 - i,j,k,i=1;i; p=p- s); i=1; k=p-kks,k); if(请输入顶点 :); i=1;ii; i=1;iij; ij=1; i=1;iii i=1;终点序号 :,i); sd; p=(); p-d; p-s /*sp; 算法运行结果如下图所示： - 24 - ) i,k,v,; s; p; i=1; p=p- s); i=1; k=p-kk - 25 - s,k); if(表示一个计算机允许的、大于所有边上权值的数。 用邻接表创建有向图时仅创建一个结点，其前驱为弧尾顶点，后记为弧头顶点。输入时还应加上弧上的权 w。 用邻接矩阵创建有向网的函数为 G)，用邻接表创建有向网的函数为 G)，其代码参见头文件 向网应用的实现 从一个顶点到其余各顶点的最短路径 从某个源点到其余各顶点的最短路径又称为单源最短路径。迪杰斯特拉提出了一个按路径长度递增的次序产生最短路径的算法，又称“贪心”算法。 算法的基本思想是：把图中的顶点分成两个集合 ，集合 合 最短路径长度递增的次序逐个将 中，直到从源点出发可以到达的所有顶点都在 为实现算法，引入一个辅助结构数组 来存放源点 有两个域：存储该顶点当 前最短路径长度的 从 i则为。而i(i!=0)。显然长度为 iii=1,2, ,路径就是从 路径为 (v0, 假设下一条最短路径的终点为 么该路径或者是弧 (v0,或者是中间只经过集合为假若此路径上除 顶点不在集合 明存在一条终点不在 与我们按路径长度递增的顺序产生最短路径的前提相矛盾。因此，一般情况下，下一条长度次短的最短路径的长度必是jiT 另引入一个数组 来标识顶点是否已经确定最短路径。 i=1,表明 26 - 短路径已经确定，即 S。 i=0，表明 T。当从集合 中，需要更新顶点 中任一顶点 如果jjk%c:%dn,v,i,i s); s,i); j=ij!= s,j); j=j s) s,k); ik+Dkj) Dij=Dik+Dkj; ij=k; ,D, ,i,j) k; k=ij; if(k=-1),i,k); T 其中， 为弧 上的权。 vli vli是指在不推迟整个工期的前提下 (即保证事件 ve(n)时刻发生的前提下 ),事件于 ve(n)减去 vln=ven - 31 - vli=vlj S 其中 eek 若活动 示，只有事件 动 以，活动 eek=eli e1k 在不推迟整个工程完成 的前提下，活动 由弧 表示活动 vlj减去活动 ： elk=vlj 把 elk=eek的活动 elii表示完成活动 即在不延迟工期的前提下活动 关键路径的算法步骤为： (1)输入 建立 (2)从源点 =0,按拓扑有序求其余各顶点的最早发生时间 vei(1 i如果得到的拓扑有序序列中顶点个数 小于网中顶点数 n，则说明网中存在环，不能求关键路径，算法终止：否则执行步骤 (3). (3)从汇点 vlve按逆拓扑有序求其余各顶点的最迟发生时间vli(i 2)。 (4)根据各顶点的 每条 弧 ee(s)和最迟开始时间 el(s)。若某条弧满足条件 ee(s)=el(s),则为关键活动。 用头结点中增加一个存储相应顶点的入度值域的特殊邻接表作 关键路径的算法如下： ,T) s; i,v,k,; p; s); i=1; p=p- i=1; k=p-kks,k); if(vev+p-wvek) vek=vev+p-w; ) j,k,v,ee,p; ; ); if(,&T)!= k=p-p-w; if(vlk k=p- - 33 - p-w; ee=vej; el=vlkif(%d,%d,%d,%d,%dn,j,k,ee, %c,%cn,jk 算法运行结果如下图所示： 设 求关键路径的时间复杂度为 O(n+e)。 * G) i,j,c,w; 请输入顶点 :); i=1;ii; i=1;iijw; ij=w; i=1;iii i=1;终点序号，权值 :,i); sdw; p=(); p-d; - 35 - p-w=w; p-s /*sp; 算法运行结果如下图所示： ,v) i,j,k,s; i=1;i%c:%dn,v,i,i s); s,i); j=ij!= s,j); j=j s) s,k); ik+Dkj) Dij=Dik+Dkj; ij=k; ,D, ,i,j) k; k=ij; if(k=-1),i,k); ; p=p- i=1; k=p-kks,k); if(vev+p-wvek) vek=vev+p-w; ) j,k,v,ee,p; ; ); if(,&T)!= k=p-p-w; if(vlk k=p-p-w; ee=vej; el=vlkif(%d,%d,%d,%d,%dn,j,k,ee, %c,%cn,jk 六 、难点与收获 我的模版是数据结构老师给的，对于图的基本操作，我是按她的思路进行扩展编写而成的。 其他的程序是按书上的程序编写的，由于存储图的数组的下标是从 1开始的， 所以之后的程序大多都要修改，在调试程序的过程中也遇到很多 问题 。 有些错误编译器有提示，有的错误它根本不提示，你不知道错在哪里，编译能通过，连接也能通过，但就是不能输出正确结果。因此需要不断地调试才能找出问题所在。 以下列出的就是我遇到的 这样的 问题以及我的解决方法。 （ 1） 3 - Q is 是一个指向队列的指针，在调用队列的初始化函数 )时就出现了这个错误，其大意是 针 不初始化就不能使用。于是我加了这样一条语句： Q=();这样运行通过了，但新的问题又出现了，广度遍历的时候程序只输出第一个结点，后面的结点就不输 出了，我调试的时候发现 元素的确入队了但出队时显示队空，于时我判断队列的头文件有问题。 于是我更换了队列的头文件，运行之后发现错误排除了。 (2)图的基本操作及应用 的 0未处理的异常 : 0读取位置 0发生访问冲突 . 在进行拓扑排序的时候出现了以上的错误。程序运行到语句 p=ip;p=p-终止。经调试发现 开始取的，而图的顶点列表中 0号单元没有值，因此无法读取数据 。 （ 3） 2664: “ : 不能将参数 2 从“ ”转换为“ ” - 40 - 这是运行关键路径的程序时出现的错误。在调用函数 ,&T)时不能入 定义的栈是指针类型， 为了解决这个问题，我重载了入栈函数 s,e)之后程序能正常运行了。 （ 4） 无法解析的外部符号 _ (?)， 1 个无法解析的外部命令。这两个错误是在每对顶点最短路径问题时出现的开始看了根本不知道是什么意思，最后仔细比较程序发现， 。 除此之外，还有一些问题也很棘手，那就是程序编译和连接都能通过但不能输出正确结果，这样的错误最难缠，经过调试后发现这些错误都出在一些小问题上，比如说循环语句的判断语句不对造成死循环，或者循环的起始条件不对 ，仅循环一次就退出。又或者 在头文件之后造成程序出现“未定义的标识符 的错误，头文件包含 会出现函数重定义，函数已有一个文体的错误。总之，一切的不小心都会造成程序运行出错。 通过这次课设，提高了我的编程能力，尤其是调试程序的能力。 我很少向老师求助，并不是我没有问题，而是我习惯了自己解决问题。我相信通过自己实际操作更能够提高能力，体会更深刻。 编程是 需要很好的耐心和极认真的态度，不认真 就会出现各种小错误，当然细微的小错误是无法避免的，比如敲代码时