数据结构课程设计示例.pdfVIP

数据结构课程设计示范 下面给出两个课程设计示范，其中一个给出了完整的设计描述。 例题1：在有n 个选手P ,P ,P ,… ,P 参加的单循环赛中，每对选手之间非胜即负。 1 2 3 n 现要求求出一个选手序列P ’,P ’,P ’,…,P ’,使其满足P ’胜P ’(i=1,… ,n-1)。 1 2 3 n i i+1 解：本题的求解如下： （1）模型表示： 由于仅涉及到n 个选手，并且这些选手之间的关系仅是胜负关系，因此可用图来表示： ①用顶点表示选手。 ②用弧表示选手之间的胜负关系：当且仅当P 胜P 时，有从顶点i 到j 的一条弧。 i j 在这种表示下，本题问题变成了如下的问题： 在有向图中求解出一条包含所有顶点的简单路径的问题。 图1 所示为一个有8 个选手的问题的一个示例。其中的一个解为1,2,3,4,8,6,5,7。 ① ② ⑧ ③ ⑦ ④ ⑥ ⑤ 图1 例1 所对应的图结构 （2 ）算法设计： 设计本题算法的构思如下： ①为有哪些信誉好的足球投注网站出符合条件的简单路径，需按深度优先有哪些信誉好的足球投注网站方式进行遍历。因此求解算法应是 深度遍历算法的变形形式，也应是递归形式的算法。 ②由于要求遍历序列中的各结点按次序构成一条简单路径，因此算法与深度遍历算法有 明显的不同：并非任意选择的起点和访问次序都能得到解。而这些又是事先难以确定的。这 就要求在求解过程中进行试探：试探起点以及访问次序。 ③既然要在求解过程中进行试探，则需要记录试探的中间状态：某顶点是否在当前试探 的路径中，已经试探的各顶点的次序，当前正在试探的顶点等。将所用到的变量及有关参数 设置如下： 设图为g ；设当前试探路径中最后的顶点号为v ；v 在试探路径中的序号为k ； 用布尔型数组visited[n+1]表示各顶点是否在当前试探的路径中（初值为全FALSE ）； 用数组B[n+1]存储当前路径中的各顶点（在前k 个元素中，事实上应是栈）。 ④既然是试探型求解，则需对当前顶点v 的每个邻接点(不妨用w 表示)进行试探，试探 由v 经w 往下是否可以得到解。每个w 都可能有成功（指现在可以将该顶点放在路径上， 这包括暂时的和最终的）与失败（指此路不通）两种情况，对此应分别作不同的处理： a. 若试探成功，则应将w 放入路径中，并置相应的状态值。然后再由w 往下求解。 b. 若不成功，则应恢复w 的有关信息，以使w 在试探其它路径时成为可选顶点。 ⑤为了能求出解以及所有可能的解，需要作如下两方面的工作： a. 选择起点：应以每个顶点为起点进行有哪些信誉好的足球投注网站。 b. 有哪些信誉好的足球投注网站路径：在从v 往下有哪些信誉好的足球投注网站时，应依次选择v 的所有不在当前试探路径中的邻接点 往下有哪些信誉好的足球投注网站。 为此，需要有这方面的保证：应在试探某顶点w 后并在换下一个试探顶点前恢复w 的 有关状态，以使其仍为可选择的顶点。 ⑥由上述讨论得本算法的基本思想： a.若k=n ，则说明已经求得一解，因此可输出结果，并结束本次调用。 b.若kn ，则依次选择v 的所有不在当前试探路径中的邻接点w 往下有哪些信誉好的足球投注网站，这包括以下 的操作： 试探：将w 放到B[k+1] 中，并置visited[w]为TRUE，然后以w 为起点往下有哪些信誉好的足球投注网站。 恢复：将w 恢复为不在当前路径中，以使其在试探其它路径时可用。 ⑦有关算法中的变量设置：可将上述讨论中所提及的变量k 、v 作为参数（仅提供值而 不返回值），将g 作为地址传送型参数（虽然不会改变其值，但这种形式更节省时间和空间）， 将数组B 和visited 作为全程变量，以便各调用层能共享，并节省时间、空间，同时使程序 更清晰。 算法描述如下： void getcc(in