数据结构课程设计范例

《数据结构课程设计范例》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《数据结构》课程设计范例下面给出一个完整的课程设计示范。问题:在有n个选手P1,P2,P3,・・・，Pn参加的单循环赛中，每对选手之间非胜即负。现要求求岀一个选手序列P1',P2',P3'，…，Pn使其满足Pi'胜Pi+1'(i二1,・・・,n-l)o解:木题的求解如下：(1)模型表示:由于仅涉及到n个选手，并且这些选手之间的关系仅是胜负关系，因此可用图来表示：用顶点表示选手。用弧表示选手之间的胜负关系：当且仅当Pi胜Pj时，有从顶点i到j的一条弧。在这种表示下，木题问题变成了如下的问题：在有向图屮求解出一条包含所有顶点的简单路径的问题。

2、下图所示为一个有8个选手的问题的一个示例。其屮的一个解为1,2,3,4,&6,5,7o(2)算法设计：设计本题算法的构思如下:为搜索岀符合条件的简单路径，需按深度优先搜索方式进行遍历。因此求解算法应是深度遍历算法的变形形式，也应是递归形式的算法。由于要求遍历序列中的各结点按次序构成一条简单路径，因此算法与深度遍历算法有明显的不同：并非任意选择的起点和访问次序都能得到解。而这些又是事先难以确定的。这就要求在求解过程中进行试探：试探起点以及访问次序。既然要在求解过程中进行试探，则需要记录试探的中间状态:某顶点是否在当前试探的路径中，已经试探的

3、各顶点的次序，当前正在试探的顶点等。将所用到的变量及有关参数设置如下：设图为g；设当前试探路径中最后的顶点号为V；V在试探路径中的序号为k；用布尔型数组visited[n+l]表示各顶点是否在当前试探的路径中（初值为全FALSE）；用数组B[n+1]存储当前路径中的各顶点（在前k个元素中，事实上应是栈）。既然是试探型求解，则需对当前顶点v的每个邻接点（不妨用w表示）进行试探，试探由v经w往下是否可以得到解。每个w都可能有成功（指现在可以将该顶点放在路径上，这包括暂时的和最终的）与失败（指此路不通）两种情况，对此应分别作不同的处理：a.若试

4、探成功，则应将w放入路径中，并置相应的状态值。然后再由w往下求解。b.若不成功，则应恢复w的有关信息，以使w在试探其它路径时成为可选顶点。为了能求岀解以及所有可能的解，需要作如下两方面的工作：a.选择起点：应以每个顶点为起点进行搜索。b.搜索路径：在从v往下搜索吋，应依次选择v的所有不在当前试探路径中的邻接点往下搜索。为此，需要有这方而的保证：应在试探某顶点w后并在换下一个试探顶点前恢复w的有关状态，以使其仍为可选择的顶点。由上述讨论得本算法的基本思想：a.若k=n,则说明已经求得一解，因此可输出结果，并结束本次调用。b.若k

5、选择v的所有不在当前试探路径屮的邻接点w往下搜索，这包括以下的操作：试探：将w放到B[k+1]中，并置visitedM为TRUE,然后以w为起点往下搜索。恢复：将w恢复为不在当前路径屮，以使其在试探其它路径时可用。有关算法中的变量设置：可将上述讨论中所提及的变量k、V作为参数（仅提供值而不返回值），将g作为地址传送型参数（虽然不会改变其值，但这种形式更节省吋间和空间）,将数组B和visited作为全程变量，以便各调用层能共享，并节省时间、空间，同时使程序更清晰。算法描述……。（3）程序实现:为上机实现本题，还需要做一些工作：添加功能：由算

6、法可知，需要添加一些功能，如输入数据建图、输出路径，显示求解状态等。结构及类型说明：到目前为止，还没有提及图的存储结构。若采用《数据结构实验工具》，则可借助于实验工具中的存储结构，因此可省掉诸如类型说明、建图、显示图等许多麻烦。若要自己设计存储结构，由教科书可知，图的存储结构可有多种，其中最常用的是邻接矩阵和邻接表两种，两者各有其特点。具体采用什么结构取决于问题木身的要求。考虑到本题的特点，为简单起见，采用邻接矩阵存储形式。为此，需要做必要的说明。在采用具体的存储结构后，算法可能也要随之发生变化。输入图结构：为方便地调试算法，需耍能方便地

7、建图。若采用逐个输入元素的方式来建图，则需要输入n2个元素，这对调试算法来说是不便的。为此，可采用随机产牛的方式来建图，即随机地产牛邻接矩阵各元素的值。此处需要注意的是矩阵屮元素的特点：对角线上全0,其余元素满足a[I][j]=l-a[j][I]。显示结构：合理地显示结构是调试算法所必需的。在此，采用工具系统屮的图结构、数组等有关功能，以方便地显示结构。显示输出结果：输出结果也必须要以可接受的形式显示出来。此处毎求解出一个结果输出一次。完整程序……（4）总结：本题主要部分是直接用C语言实现的一个设计，由于釆用邻接矩阵作为图的存储结构，因此

8、程序较为简洁。若完全借助于实验工具，程序将更为简洁。然而，邻接矩阵作为图的存储结构的要求在程序运行之前必须要知道其顶点数。这是木设计的一个缺陷。解决的办法之一是将邻接矩阵设置得“足够大”，运行