《数据结构》课件附录A.ppt

既然要在求解过程中进行试探，则需要记录试探的中间状态：某顶点是否在当前试探的路径中，已经试探的各顶点的次序，当前正在试探的顶点等。(2)将所用到的变量及有关参数设置如下：①设图为g。②设当前试探路径中最后的顶点号为v。③?v在试探路径中的序号为k。④用int型数组visited[n+1]表示各顶点是否在当前试探的路径中(初值为全0)。⑤用数组B[n+1]存储当前路径中的各顶点(在前k个元素中，事实上应是栈)。(3)可能情况的处理：既然是试探型求解，则需对当前顶点v的每个邻接点(不妨用w表示)进行试探，试探由v经w往下是否可以得到解。每个w都可能有成功(指现在可以将该顶点放在路径上，这包括暂时的和最终的)与失败(指此路不通)两种情况，对此应分别作不同的处理：①若试探成功，则应将w放入路径中，并置相应的状态值。然后再由w往下求解。②若不成功，则应恢复w的有关信息，以使w在试探其它路径时成为可选顶点。为了能求出解以及所有可能的解，需要做如下两方面的工作：①选择起点：应以每个顶点为起点进行有哪些信誉好的足球投注网站。②有哪些信誉好的足球投注网站路径：在从v往下有哪些信誉好的足球投注网站时，应依次选择v的所有不在当前试探路径中的邻接点往下有哪些信誉好的足球投注网站。为此，需要有这方面的保证：应在试探某顶点w后并在换下一个试探顶点前恢复w的有关状态，以使其仍为可选择的顶点。(4)本算法的基本思想：①若k?=?n，则说明已经求得一解，因此可输出结果，并结束本次调用。②若k＜n，则依次选择v的所有不在当前试探路径中的邻接点w往下有哪些信誉好的足球投注网站，这包括以下的操作：试探：将w放到B[k?+?1]中，并置visited[w]为1，然后以w为起点往下有哪些信誉好的足球投注网站。恢复：将w恢复为不在当前路径中，以使其在试探其它路径时可用。(5)有关算法中的变量设置：可将上述讨论中所提及的变量k、v作为参数(仅提供值而不返回值)，将g作为地址传送型参数(虽然不会改变其值，但这种形式更节省时间和空间)，将数组B和visited作为全程变量，以便各调用层能共享，并节省时间、空间，同时使程序更清晰。3.程序实现为上机实现本题，还需要做一些工作。(1)添加功能：由算法可知，需要添加一些功能，如输入数据建图、输出路径，显示求解状态等。(2)结构及类型说明：图的存储结构可有多种，其中最常用的是邻接矩阵和邻接表两种，两者各有其特点。具体采用什么结构取决于问题本身的要求。考虑到本题的特点，为简单起见，采用邻接矩阵存储形式。为此，需要做必要的说明。在采用具体的存储结构后，算法可能也要随之发生变化。(3)输入图结构：为方便地调试算法，需要能方便地建图。若采用逐个输入元素的方式来建图，则需要输入n2个元素，这对调试算法来说是不便的。为此，可采用随机产生的方式来建图，即随机地产生邻接矩阵各元素的值(0或1)。此处需要注意的是矩阵中元素的特点：对角线上全0，其余元素满足a[i][j]?=?1-a[j][i]。(4)显示结构：合理地显示图结构，便于直观理解，是调试算法所必需的。(5)显示输出结果：输出结果也必须要以可接受的形式显示出来。此处每求解出一个结果输出一次。4.完整程序略。5.总结本设计可直接用C语言实现，如果采用邻接矩阵作为图的存储结构，则程序较为简洁。然而，邻接矩阵作为图的存储结构时要求在程序运行之前必须要知道其顶点数，这将是本设计的一个缺陷。解决的办法之一是将邻接矩阵设置得“足够大”，运行时输入顶点数，将实际图的邻接关系存储在矩阵的左上角部分，然后依此运行。另一解决的办法是采用邻接表作为存储结构，并将邻接表的表头指针也放到一个链表的各结点中，但随之而来的是程序设计量的加大，因为邻接表和“表头表”的建立、插入、查询、邻接点的查询等一系列功能的设计是较为麻烦的。*附录A课程设计指导附录A课程设计指导问题1：设计一程序，要求从键盘上输入一个只含加、减、乘、除等四种运算符的算术表达式，便可计算表达式的结果。解：本题的求解如下。1.相关知识要对一个表达式求值，首先要了解算术四则运算的规则。即：(1)先乘除，后加减。(2)同级运算，从左到右。(3)先括号内，后括号外。因此，例如求解表达式4?+?5?×?(6-2)?+?8，根据运算规则，这个表达式的计算顺序应为4?+?5?×?(6-2)?+?8=4?+?5?×?4?+?8=4?+?20?+?8=24?+?8=32这种根据运算符的优先关系来实现对表达式求值的