本书另有在线教学版：（十二五”普通高等教育本科国家级规划教材）
如果希望加入教师微信交流群，请加微信：itbook8
如果希望加入教师QQ交流群，请加QQ：883604
加入时，请写明：“学校+姓名”，并写明“加入教师群”，只限教师。
第1章概论1.1数据结构概述1.1.1什么是数据结构1.1.2逻辑结构1.1.3存储结构1.1.4数据运算1.1.5数据结构、数据类型和抽象数据类型1.2算法和算法分析1.2.1算法及其描述1.2.2算法分析1.3数据结构程序设计1.3.1数据结构程序设计步骤1.3.2应用程序的结构小结练习题1上机实验题1第2章线性表2.1线性表的基本概念2.1.1线性表的定义2.1.2线性表的基本运算2.2顺序表2.2.1顺序表的定义2.2.2线性表基本运算在顺序表上的实现2.2.3顺序表的插入和删除算法分析2.2.4顺序表的应用示例2.3单链表2.3.1单链表的定义2.3.2线性表基本运算在单链表上的实现2.3.3循环单链表2.4双链表2.4.1双链表的定义2.4.2线性表基本运算在双链表上的实现2.4.3循环双链表2.5线性表的应用2.5.1设计线性表应用程序的一般步骤2.5.2线性表应用示例小结练习题2上机实验题2第3章栈和队列3.1栈3.1.1栈的基本概念3.1.2栈的顺序存储结构3.1.3栈的链式存储结构3.1.4栈的应用示例3.2队列3.2.1队列的基本概念3.2.2队列的顺序存储结构3.2.3队列的链...
直属事业部
扫描关注官方微博
扫描关注官方微信
版权所有(C)2014 清华大学出版社有限公司 京ICP备号 京公网安备48号线性表是一种常用的。在实际应用中，线性表都是以、队列、、等特殊线性表的形式来使用的。由于这些特殊线性表都具有各自的特性，因此，掌握这些特殊线性表的特性，对于数据运算的可靠性和提高操作效率都是至关重要的。　　线性表是一个线性结构，它是一个含有n≥0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。
1．集合中必存在唯一的一个“第一元素”；
2．集合中必存在唯一的一个 “最后元素” ；
3．除最后一个元素之外，均有 唯一的后继(后件)；
4．除第一个元素之外，均有 唯一的前驱(前件)。
java中的List接口，就是线性表。ArrayList就是顺序线性表，LinkedList就是链表线性表。
一般使用数组(C语言中的数组采用顺序存储方式。即连续地址存储)来描述。
优点：在于随机访问元素，
缺点：插入和和删除的时候，需要移动大量的元素。
c语言实现代码：
一般使用链表来描述。
优点：对于新增和删除操作add和remove和方便。不需要移动元素。
缺点：不方便随机访问元素，LinkedList要移动指针
代码实现：
1.1&栈的定义
栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示：
结论：后进先出（Last In First Out），简称为LIFO线性表。
栈的基本运算有六种：
构造空栈：InitStack(S)、
判栈空: StackEmpty(S)、
判栈满：&StackFull(S)、
进栈：&Push(S,x)、可形象地理解为压入，这时栈中会多一个元素
退栈：&Pop(S) 、 可形象地理解为弹出，弹出后栈中就无此元素了。
取栈顶元素：StackTop(S),不同与弹出，只是使用栈顶元素的值，该元素仍在栈顶不会改变。
& & 由于栈也是线性表，因此线性表的存储结构对栈也适用，通常栈有顺序栈和链栈两种存储结构，这两种存储结构的不同，则使得实现栈的基本运算的算法也有所不同。
我们要了解的是，在顺序栈中有&上溢&和&下溢&的概念。顺序栈好比一个盒子，我们在里头放了一叠书，当我们要用书的话只能从第一本开始拿(你会把盒子翻过来吗?真聪明^^)，那么当我们把书本放到这个栈中超过盒子的顶部时就放不下了(叠上去的不算，哼哼)，这时就是&上溢&,&上溢&也就是栈顶指针指出栈的外面，显然是出错了。反之，当栈中已没有书时，我们再去拿，看看没书，把盒子拎起来看看盒底，还是没有，这就是&下溢&。&下溢&本身可以表示栈为空栈,因此可以用它来作为控制转移的条件。
链栈则没有上溢的限制，它就象是一条一头固定的链子，可以在活动的一头自由地增加链环(结点)而不会溢出，链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要在头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。
1.2 栈的顺序存储
使用c++的面向对象封装：
结论：由于栈的插入和删除操作具有它的特殊性，所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题，但栈容量难以扩充的弱点仍就没有摆脱。
1.3 栈的链式存储
若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作&链栈&。链栈通常用一个无头结点的单链表表示。如图所示：
栈的操作是线性表操作的特例。
简单用c实现：
1.4 栈的应用
1) &数制转换
2）语法词法分析
3）表达式求值等
1.5 栈的递归和实现
汉诺塔的问题：
1）如果有一个盘子，直接从X移到Z即可。
2）如果有n个盘子要从X移到Z，Y作为辅助。问题可以转化为，先将上面n-1个从X移动到Y，Z作为辅助，然后将第n个从X移动到Z，最后将剩余的n-1个从Y移动到Z，X作为辅助。
完整实现代码，包括栈的实现：
1.1 队列定义&
队列(Queue)也是一种运算受限的线性表，它的运算限制与栈不同，是两头都有限制，插入只能在表的一端进行(只进不出)，而删除只能在表的另一端进行(只出不进)，允许删除的一端称为队尾(rear)，允许插入的一端称为队头&(Front)
,队列的操作原则是先进先出的，所以队列又称作FIFO表(First In First Out)
队列的基本运算也有六种：
置空队 ：InitQueue(Q)
判队空：&QueueEmpty(Q)
判队满：&QueueFull(Q)
入队 ：&EnQueue(Q,x)
出队 ：&DeQueue(Q)
取队头元素：&QueueFront(Q),不同与出队，队头元素仍然保留。
队列也有顺序存储和链式存储两种存储结构，前者称顺序队列，后者为链队。
对于顺序队列，我们要理解&假上溢&的现象。
我们现实中的队列比如人群排队买票，队伍中的人是可以一边进去从另一头出来的，除非地方不够，总不会有&溢出&的现象，相似地，当队列中元素完全充满这个向量空间时，再入队自然就会上溢，如果队列中已没有元素，那么再要出队也会下溢。
那么&假上溢&就是怎么回事呢?
因为在这里，我们的队列是存储在一个向量空间里，在这一段连续的存储空间中，由一个队列头指针和一个尾指针表示这个队列，当头指针和尾指针指向同一个位置时，队列为空，也就是说，队列是由两个指针中间的元素构成的。在队列中，入队和出队并不是象现实中，元素一个个地向前移动，走完了就没有了,而是指针在移动，当出队操作时，头指针向前(即向量空间的尾部)增加一个位置，入队时，尾指针向前增加一个位置，在某种情况下，比如说进一个出一个，两个指针就不停地向前移动，直到队列所在向量空间的尾部，这时再入队的话，尾指针就要跑到向量空间外面去了，仅管这时整个向量空间是空的，队列也是空的，却产生了&上溢&现象，这就是假上溢。
为了克服这种现象造成的空间浪费，我们引入循环向量的概念，就好比是把向量空间弯起来，形成一个头尾相接的环形，这样，当存于其中的队列头尾指针移到向量空间的上界(尾部)时，再加1的操作(入队或出队)就使指针指向向量的下界，也就是从头开始。这时的队列就称循环队列。
通常我们应用的大都是循环队列。由于循环的原因，光看头尾指针重叠在一起我们并不能判断队列是空的还是满的，这时就需要处理一些边界条件，以区别队列是空还是满。方法至少有三种，一种是另设一个布尔变量来判断(就是请别人看着，是空还是满由他说了算)，第二种是少用一个元素空间，当入队时，先测试入队后尾指针是不是会等于头指针，如果相等就算队已满，不许入队。第三种就是用一个计数器记录队列中的元素的总数，这样就可以随时知道队列的长度了，只要队列中的元素个数等于向量空间的长度，就是队满。
2.2 队列的顺序存储
顺序存储如图：
由于是顺序存储结构的存储空间是静态分配的，所以在添加数据的时，有可能没有剩余空间的情况。
解决这种“假溢出”情况，使用循环队列。在c语言中，不能用动态分配的一维数组来实现循环队列。若使用循环队列，必须设置最大队列长度，若无法估计最大长度，就使用链式队列。
注意：InitQueue(QUEUE *&Q) 传的是指针的地址。
2.3 链式队列：
2. 4．队列的应用
【举例1】银行排队
【举例2】模拟打印机缓冲区。
在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这样会降低主机的使用效率。为此人们设想了一种办法：为打印机设置一个打印数据缓冲区，当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的事情，而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印数据的正确性，又提高了主机的使用效率。由此可见，打印机缓冲区实际上就是一个队列结构。
【举例3】CPU分时系统
在一个带有多个终端的计算机系统中，同时有多个用户需要使用CPU运行各自的应用程序，它们分别通过各自的终端向操作系统提出使用CPU的请求，操作系统通常按照每个请求在时间上的先后顺序，将它们排成一个队列，每次把CPU分配给当前队首的请求用户，即将该用户的应用程序投入运行，当该程序运行完毕或用完规定的时间片后，操作系统再将CPU分配给新的队首请求用户，这样即可以满足每个用户的请求，又可以使CPU正常工作。
Brute-Force算法的思想
Brute-Force算法的基本思想是：
1) 从目标串s 的第一个字符起和模式串t的第一个字符进行比较，若相等，则继续逐个比较后续字符，否则从串s 的第二个字符起再重新和串t进行比较。
2) 依此类推，直至串t 中的每个字符依次和串s的一个连续的字符序列相等，则称模式匹配成功，此时串t的第一个字符在串s 中的位置就是t 在s中的位置，否则模式匹配不成功。
Brute-Force算法的实现 &&
c语言实现：
2.1 算法思想：
每当一趟匹配过程中出现字符比较不等时，不需要回溯I指针，而是利用已经的带的“部分匹配”的结果将模式向右滑动尽可能远的一段距离后，继续进行比较。
即尽量利用已经部分匹配的结果信息，尽量让i不要回溯，加快模式串的滑动速度。
需要讨论两个问题：
①如何由当前部分匹配结果确定模式向右滑动的新比较起点k？
② 模式应该向右滑多远才是高效率的?
现在讨论一般情况:
假设 主串：s: ‘s(1)& s(2)&s(3) ……s(n)’ ; &模式串 ：p: ‘p(1)& p(2)&p(3)…..p(m)’
现在我们假设 主串第i个字符与模式串的第j(j&=m)个字符‘失配’后，主串第i个字符与模式串的第k(k&j)个字符继续比较。
此时，s(i)≠p(j)：
由此，我们得到关系式：即得到到1 到&&j -1&的&部分匹配&结果:
&‘P(1)& P(2)&P(3)…..P(j-1)’&& =&&& ’ S(i-j+1)……S(i-1)’
&从而推导出k 到 j- 1位的“部分匹配”：即P的j-1～j-k＝S前i-1～i-
(k -1))位&& & & & & &&
&&‘P(j - k + 1) …..P(j-1)’ &=&&’S(i-k+1)S(i-k+2)……S(i-1)’
由于s(i)≠p(j)，接下来s(i)将与p(k)继续比较，则模式串中的前(k-1)个字符的子串必须满足下列关系式，并且不可能存在& k’&k& 满足下列关系式：(k&j)
有关系式：&即(P的前k- 1 ~ 1位＝ S前i-1～i-(k-1) )位 )&,：
‘P(1)&P(2)& P(3)…..P(k-1)’&= ’S(i-k+1)S(i-k+2)……S(i-1)’
现在我们把前面总结的关系综合一下,有：
由上，我们得到关系：
‘p(1)& p(2)& p(3)…..p(k-1)’ &= &&‘p(j - k + 1) …..p(j-1)’&
& & & 反之，若模式串中满足该等式的两个子串，则当匹配过程中，主串中的第i 个字符与模式中的第j个字符等时，仅需要将模式向右滑动至模式中的第k个字符和主串中的第i个字符对齐。此时，模式中头k-1个字符的子串‘p(1)&
p(2)& p(3)…..p(k-1)’&&必定与主串中的第i 个字符之前长度为k-1 的子串&
’s(j-k+1)s(j-k+2)……s(j-1)’相等，由此，匹配仅需要从模式中的第 k 个字符与主串中的第 i 个字符比较起 继续进行。& & & 若令 next[j] = k ,则next[j] 表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需要重新和主串中该字符进行的比较的位置。由此可引出模式串的next函数：
根据模式串P的规律：&&‘p(1)& p(2)& p(3)…..p(k-1)’ &= &&‘p(j - k + 1) …..p(j-1)’&
由当前失配位置j(已知) ，可以归纳计算新起点k的表达式。
由此定义可推出下列模式串next函数值：
模式匹配过程:
KMP算法的实现:
第一步，先把模式T所有可能的失配点j所对应的next[j]计算出来；
第二步：执行定位函数Index_kmp（与BF算法模块非常相似）
完整实现代码：
2.2 &求串的模式值next[n]
k值仅取决于模式串本身而与相匹配的主串无关。
我们使用递推到方式求next函数：
1）由定义可知：
& & &next[1] = 0;
2) &设&next[j] = k&,这个表面在模式串中存在下列关系：
& &&‘P(1) &….. P(k-1)’ &= &&‘P(j
- k + 1) ….. P(j-1)’&
& & 其中k为满足1& k &j的某个值，并且不可能存在k` & 满足:
& &&‘P(1) &….. P(k`-1)’ &= &&‘P(j - k` + 1) ….. P(j-1)’&
& & 此时next[j+1] = ?可能有两种情况：
& &（1） 若Pk = Pj，则表明在模式串中：
….. P(k)’ &= &&‘P(j - k + 1) ….. P(j)’&
& & & & & 并且不可能存在k` & 满足：&&‘P(1) ….. P(k`)’ &= &&‘P(j
- k` + 1) ….. P(j)’&
& & & & & 即next[j+1] = k + 1&推到=》：
& & & & &next[j+1] = next[j] + 1;
& &&&&(2) &若PkPj&则表明在模式串中：
& & & & &&‘P(1)
….. P(k)’ &&&&‘P(j - k + 1) ….. P(j)’&
& & &此时可把next函数值的问题看成是一个模式匹配的问题，整个模式串即是主串又是模式串，
& & &而当前匹配的过程中，已有：
& & & Pj-k+1 = P1， Pj-k+2 = P2，... Pj-1 = Pk-1.
& & &则当PkPj时应将模式向右滑动至以模式中的第next[k]个字符和主串中的第&j&个字符相比较。
& & &若next[k] = k`,且Pj= Pk`, 则说明在主串中的第j+1 个字符之前存在一个长度为k` (即next[k])的最长子串，和模式串
& & &从首字符其长度为看k`的子串箱等。即
& & &&&‘P(1) ….. P(k`)’ &=&&‘P(j - k` + 1) ….. P(j)’&
& & &也就是说next[j+1] = k` +1&即
& &&&next[j+1] = next[k] + 1
& & &同理，若Pj&Pk`&,则将模式继续向右滑动直至将模式串中的第next[k`]个字符和Pj对齐，
& & &... ,一次类推，直至Pj和模式中某个字符匹配成功或者不存在k`(1& k` & j)满足，则:
& & &next[j+1] =1;
next&函数值究竟是什么含义，前面说过一些，这里总结。
设在字符串S中查找模式串T，若S[m]!=T[n],那么，取T[n]的模式函数值next[n],
1.&&&&&&&next[n] = 0&表示S[m]和T[1]间接比较过了，不相等，下一次比较&S[m+1]&和T[1]
2.&&&&&&&next[n] =1&表示比较过程中产生了不相等，下一次比较&S[m]&和T[1]。
3.&&&&&&&next[n] = k &1&但k&n,&表示,S[m]的前k个字符与T中的开始k个字符已经间接比较相等了，下一次比较S[m]和T[k]相等吗？
4.&&&&&&&其他值，不可能。
（1）k值仅取决于模式串本身而与相匹配的主串无关。
（2）k值为模式串从头向后及从j向前的两部分的最大相同子串的长度。
（3）这里的两部分子串可以有部分重叠的字符，但不可以全部重叠。
next[j]函数表征着模式P中最大相同前缀子串和后缀子串（真子串）的长度。
可见，模式中相似部分越多，则next[j]函数越大，它既表示模式T字符之间的相关度越高，也表示j位置以前与主串部分匹配的字符数越多。
即：next[j]越大，模式串向右滑动得越远，与主串进行比较的次数越少，时间复杂度就越低（时间效率）。
　　若二叉树非空，则依次执行如下操作：
　　(1) 访问根结点；
　　(2) 遍历左子树；
　　(3) 遍历右子树。
2．中序遍历的递归算法定义：
　　若二叉树非空，则依次执行如下操作：
　　(1)遍历左子树；
　　(2)访问根结点；
　　(3)遍历右子树。
3．后序遍历得递归算法定义：
　　若二叉树非空，则依次执行如下操作：
　　(1)遍历左子树；
　　(2)遍历右子树；
　　(3)访问根结点。
4．层次遍历：层序遍历（level traversal）二叉树的操作定义为：
& & &若二叉树为空，则退出，否则，
& & & 按照树的结构，从根开始自上而下，自左而右访问每一个结点，从而实现对每一个结点的遍历&
例子：表达式a + b × (c-&d)-&e/ f
先序遍历：-&+ a * b&-&c d / e f
中序遍历：a + b * &c&-&d-&e / f
后续遍历：a b c d&-&× + &e f /-
二叉树遍历
平衡树——特点：所有结点左右子树深度差≤1
排序树——特点：所有结点“左小右大
字典树——由字符串构成的二叉排序树
判定树——特点：分支查找树（例如12个球如何只称3次便分出轻重）
带权树——特点：路径带权值（例如长度）
最优树——是带权路径长度最短的树，又称 Huffman树，用途之一是通信中的压缩编码。
1.1 二叉排序树：
或是一棵空树；或者是具有如下性质的非空：
&（1）若左子树不为空，左子树的所有结点的值均小于根的值；
&（2）若右子树不为空，右子树的所有结点均大于根的值；
&（3）它的左右子树也分别为二叉排序树。
例：二叉排序树 如图9.7：
& & & & & & & & &
& & & 二叉排序树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉排序树的存储结构。中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索,插入,删除的复杂度等于树高，期望O(logn),最坏O(n)(数列有序,树退化成线性表).
虽然二叉排序树的最坏效率是O(n),但它支持动态查询,且有很多改进版的二叉排序树可以使树高为O(logn),如SBT,AVL,红黑树等.故不失为一种好的动态排序方法.
2.2&二叉排序树b中查找
在二叉排序树b中查找x的过程为：
若b是空树，则搜索失败，否则：若x等于b的根节点的数据域之值，则查找成功；否则：若x小于b的根节点的数据域之值，则搜索左子树；否则：查找右子树。
2.3 在二叉排序树插入结点的算法
向一个二叉排序树b中插入一个结点s的算法，过程为：
若b是空树，则将s所指结点作为根结点插入，否则：若s-&data等于b的根结点的数据域之值，则返回，否则：若s-&data小于b的根结点的数据域之值，则把s所指结点插入到左子树中，否则：把s所指结点插入到右子树中。
2.4 在二叉排序树删除结点的算法
在二叉排序树删去一个结点，分三种情况讨论：
若*p结点为叶子结点，即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。若*p结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双亲结点*f的左子树即可，作此修改也不破坏二叉排序树的特性。若*p结点的左子树和右子树均不空。在删去*p之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整，可以有两种做法：其一是令*p的左子树为*f的左子树，*s为*f左子树的最右下的结点，而*p的右子树为*s的右子树；其二是令*p的直接前驱（或直接后继）替代*p，然后再从二叉排序树中删去它的直接前驱（或直接后继）。在二叉排序树上删除一个结点的算法如下：
2. 5二叉排序树性能分析
每个结点的Ci为该结点的层次数。最坏情况下，当先后插入的关键字有序时，构成的二叉排序树蜕变为单支树，树的深度为n，其平均查找长度为&（和顺序查找相同），最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log2(n)成正比
（O(log2(n))）。
2.6 二叉排序树的优化
& & Size Balanced Tree(SBT)
& & 红黑树
& & Treap(Tree+Heap)
这些均可以使查找树的高度为O(logn)
1. 1 平衡二叉树（Balanced Binary Tree）
性质：& 左右子树都是平衡且所有结点左、右子树深度之差的绝对值 ≤&1。
若定义结点的“平衡因子”&&BF（Balance Factor）&= 左子树深度 –右子树深度&则：平衡二叉树中所有结点的BF&∈[ -1, 0, 1 ]
例：判断下列二叉树是否AVL树？
常用算法有红黑树、AVL、Treap、伸展树等。在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O（log2n），大大降低了操作的时间复杂度。
平衡二叉树是二叉排序树的另一种形式。
我们希望由任何初始序列构成的二叉排序树都是平衡二叉树。因为平衡二叉树上任何结点的左右子树的深度之差都不超过1，则可以证明它的深度和logN是同数量级的（其中N是结点的个数）。由此，它的平均查找长度也和logN同数量级。
C语言描述:
构造二叉平衡（查找）树的方法是：在插入过程中，采用平衡旋转技术。
插入算法 :
算法思想：
在平衡二叉排序树BBST上插入一个新的数据元素e的递归算法可描述如下：
1．若BBST为空树，则插入一个数据元素为e的新结点作为BBST的根结&&&&& 点，树的深度增1；&
2．若e的关键字和BBST的根结点的关键字相等，则不进行插入；&
3．若e的关键字小于BBST的根结点的关键字，而且在BBST的左子树中不存在和e有相同关键字的结点，则将e插入在BBST的左子树上，并且当插入之后的左子树深度增加（＋1）时，分别就下列不同情况处理之：
& & i．BBST的根结点的平衡因子为－1（右子树的深度大于左子树的深度）：则将根结点的平衡因子更改为0，BBST的深度不变；
& & ii．BBST的根结点的平衡因子为0（左、右子树的深度相等）：则将根结点的平衡因子更改为1，BBST的深度增1；&
& & iii．BBST的根结点的平衡因子为1（左子树的深度大于右子树的深度）：
& & & & &a.&若BBST的左子树根结点的平衡因子为1，则需进行单向右旋平衡处理，并且在右旋处理之后，将根结点和其右子树根结点的平衡因子更改为0，树的深度不变；
& & & & &b.&若BBST的左子树根结点的平衡因子为－1，则需进行先向左、后向右的双向旋转平衡处理，并且在旋转处理之后，修改根结点和其左、右子树根结点的平衡因子，树的 & & & & & & & &深度不变。
4．若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和e有相同关键字的结点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加（＋1）时，分别就不同情况处理之。其处理操作和上述3．中描述相对称。
& & &&二分查找过程可用来描述：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树(Decision
Tree)或比较树(Comparison Tree)。
&&& 　判定树的形态只与表结点个数n相关，而与输入实例中R[1..n].keys的取值无关。
【例】具有11个结点的有序表可用下图所示的判定树来表示。
举例：12个球如何用天平只称3次便分出轻重？
分析：12个球中必有一个非轻即重，即共有24种“次品”的可能性。每次天平称重的结果有3种，连称3次应该得到的结果有33=27种。说明仅用3次就能找出次品的可能性是存在的。
思路：首先，将12个球分三组，每组4个，任意取两组称。会有两种情况：平衡，或不平衡。其次，一定要利用已经称过的那些结论；即充分利用“旧球”的标准性作为参考。
二分查找判定树的查找
二分查找就是将给定值K与二分查找判定树的根结点的关键字进行比较。若相等，成功。否则若小于根结点的关键字，到左子树中查找。若大于根结点的关键字，则到右子树中查找。
　　【例】对于有11个结点的表，若查找的结点是表中第6个结点，则只需进行一次比较；若查找的结点是表中第3或第9个结点，则需进行二次比较；找第1，4，7，10个结点需要比较三次；找到第2，5，8，11个结点需要比较四次。
&&& 　由此可见，成功的二分查找过程恰好是走了一条从判定树的根到被查结点的路径，经历比较的关键字次数恰为该结点在树中的层数。若查找失败，则其比较过程是经历了一条从判定树根到某个外部结点的路径，所需的关键字比较次数是该路径上内部结点的总数。
&&& 【例】待查表的关键字序列为：(05，13，19，21，37，56，64，75，80，88，92)，若要查找K=85的记录，所经过的内部结点为6、9、10，最后到达方形结点&9-10&，其比较次数为3。
&&& 　实际上方形结点中&i-i+1&的含意为被查找值K是介于R[i].key和R[i+1].key之间的，即R[i].key&K&R[i+1].key。
二分查找的平均查找长度
&&&& 　设内部结点的总数为n=2h-1，则判定树是深度为h=lg(n+1)的满二叉树(深度h不计外部结点)。树中第k层上的结点个数为2k-1，查找它们所需的比较次数是k。因此在等概率假设下，二分查找成功时的平均查找长度为：
&&&&&&&&&& ASLbn≈lg(n+1)-1
　　二分查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。即为：
&&&&&&& &&
　　二分查找的最坏性能和平均性能相当接近。
二分查找的优点和缺点
　　虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费O(nlgn)的时间。
　　二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。
　　对那些查找少而又经常需要改动的线性表，可采用链表作存储结构，进行顺序查找。链表上无法实现二分查找。
即路径带有权值。例如：
赫夫曼树：给定n个权值作为n个叶子结点，构造一棵，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为赫夫曼树(Huffman
tree)。即带权路径长度最短的树。
赫夫曼树构造算法：
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为{ w1、w2、…、wn}，则哈夫曼树的构造规则为：　　(1) 将{w1、w2、…，wn}看成是有n 棵树的森林(每棵树仅有一个结点)；　　(2)
在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；　　(3)从森林中删除选取的两棵树，并将新树加入森林；　　(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
赫夫曼编码：是通信中最经典的压缩编码.
stdafx.h文件：
test.cpp文件：
& & & & 回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
1、回溯法适用：有许多问题，当需要找出它的解集（全部解）或者要求回答什么解是满足某些约束条件的最优解时，往往要使用回溯法。
2、有组织的穷举式搜索：回溯法的基本做法是搜索或者有的组织穷尽搜索。它能避免搜索所有的可能性。即避免不必要的搜索。这种方法适用于解一些组合数相当大的问题。
3、搜索解空间树：回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含（剪枝过程），则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
为了实现回溯，我们先弄明白以下两个问题：
1）首先应该明确问题的解空间。
2）其次是组织解空间以便它能用以被搜索到。
& & & & 这个空间必须至少包含一个解（可能是最优的）。 一个复杂问题的解决往往由多部分构成，即，一个大的解决方案可以看作是由若干个小的决策组成。很多时候它们构成一个决策序列。解决一个问题的所有可能的决策序列构成该问题的解空间。解空间中满足约束条件的决策序列称为可行解。一般说来，解任何问题都有一个目标，在约束条件下使目标值达到最大（或最小）的可行解称为该问题的最优解。在解空间中，前k项决策已经取定的所有决策序列之集称为k定子解空间。0定子解空间即是该问题的解空间。
& & &&问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。
&& &解空间的确定与我们对问题的描述有关。如何组织解空间的结构会直接影响对问题的求解效率。这是因为回溯方法的基本思想是通过搜索解空间来找到问题所要求的解。一般地，可以用一棵树来描述解空间，称为解空间树。
& & & &当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集合树。此时，解空间有个元素，遍历子集树的任何算法均需的计算时间。
如例:定和子集问题： 已知一个正实数的集合P= {W1,w2, ... Wn}和另一个正实数M．试求P的所有子集S，使得S中的数之和等于M。这个问题的解可以表
示成0/1数组{x1,x2,…,xn}，依据W1是否属于S， X1分别取&#。故解空间中共有个元素。它的树结构是一棵完整二叉树。&
当所给的问题是确定n个元素的满足某种性质的排列时，相应的解空间树称为排列树，此时，解空间有个元素。遍历排列树的任何算法均需的计算时间，均需的计算时间。
我们把这个例子逐一解析：
问题的解向量：问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。
显约束：对分量xi的取值限定。
隐约束：为满足问题的解而对不同分量之间施加的约束。
解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。
注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。
下面是n=3时的0-1背包问题用完全二叉树表示的解空间：
& & & &为了叙述方便，引进一些关于解空间树结构的术语。解空间树上的每个节点确定求解问题的一个问题状态，它由一条从根到该节点的路径描述。由根到所有其它节点的路径描述了这个问题的状态空间。解状态是这样一些问题状态S，对于这些问题状态，由根到S的那条路径确定了解空间的一个元组。即答案状态是这样的一些解状态S，对于这些解状态而言，由根到S的这条路径确定了这个问题的一个解（即可行解），解空间的树结构称为状态空间树。
& & &&确定了解空间的组织结构后，回溯法就从初始节点（解空间树的根节点）出发，以深度优先的方式搜索整个解空间。这个开始节点就成为一个活节点，同时也成为当前的扩展节点。在当前扩展节点处，搜索向纵深方向移至一个新节点。这个新节点就成为一个新的活节点，并且成为当前的扩展节点。如果在当前的扩展节点处不能再向纵深方向搜索，则当前的扩展节点就成为死节点。此时应往回移动（回溯）至最近一个活节点处，并使这个活节点成为当前扩展节点。如此继续。回溯法就是以这种工作方式递归地在解空间中搜索，直至找到要求的解或解空间中已无活节点时为止。&
& & & &事实上，当我们将问题的有关数据以一定的数据结构存储好以后（例如，旅行商问题存储赋权图的邻接矩阵、定和子集问题是存储已知的n+1个数、4皇后问题用整数对(i,j)表示棋盘上各个位置，不必先建立一个解空间树），就搜索生成解空间树的一部分或全部，并寻找所需要的解。也就是说，对于实际问题不必生成整个状态空间树，然后在整个解空间中搜索，我们只需有选择地搜索。为了使搜索更加有效，常常在搜索过程中加一些判断以决定搜索是否该终止或改变路线。通常采用两种策略来避免无效的搜索，提高回溯法的搜索效率：
其一是使用约束函数，在扩展节点处剪去不满足约束的子树；
其二是用限界函数， “剪去”不能达到最优解的子树。
这两种函数统称为剪枝函数。
扩展结点:一个正在产生儿子的结点称为扩展结点
活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点
死结点:一个所有儿子已经产生的结点称做死结点
深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）
宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点。
回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死(剪枝)那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法。（回溯法&=&穷举&+　剪枝）。
描述问题：
定义可用回溯法求解的问题P：对于已知的由n元组（x1，x2，…，xn）组成的一个状态空间E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域，且 |Si| 有限，i=1，2，…，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。
解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但显然，其计算量是相当大的。
基本思路：
若已有满足约束条件的部分解，不妨设为（x1,x2,x3,……xi），I&n,则添加x(i+1)属于s(i+2)，检查 (x1,x2,……,xi,x(i+1))是否满足条件，满足了就继续添加x(i+2)、s(i+2)，若所有的x(i+1)属于s(i+1)都不能得到 部分解，就去掉xi，回溯到(xi,x2,……x(i- 1))，添加那些未考察过的x1属于s1，看其是否满足约束条件，为此反复进行，直至得到解或证明无解。
这个回溯法明显提高算法效率。
总结起来，运用回溯法解题通常包括以下三个步骤&
1).确定问题的解空间 ：针对所给问题，定义问题的解空间；&
&子集树问题：装载问题、符号三角形问题、0-1背包问题、最大团问题
排列树问题：批处理作业调度、n后问题、旅行售货员问题、圆排列问题、电路板排列问题
其他：图的m着色问题
2).确定易于搜索的解空间结构：
找出适当的剪枝函数，约束函数和限界函数。
3).以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效的搜索。
4）利用限界函数避免移动到不可能产生解的子空间
&1. 递归回溯：
回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。
void backtracking (int t)
&&& if (t & n) {
&&&&&& // 到达叶子结点，将结果输出
&&&&&& output (x);
&&& else {
&&&&&& // 遍历结点t的所有子结点，即枚举t所有可能的路径 &&
& & & // f(n,t)=下界;g(n,t)=上界;
&&&&&& for (int i = f(n,t); i &= g(n,t); i ++ ) {//
&&&&&&&&&& x[t] = h[i];//满足界限函数和约束函数
&&&&&&&&&& // 如果不满足剪枝条件，则继续遍历，进入下一层
&&&&&&&&&& if (constraint (t) && bound (t))&
&&&&&&&&&&&&& backtrack (t + 1);
t是递归深度；
n是深度控制，即解空间树的的高度；
可行性判断有两方面的内容：不满约束条件则剪去相应子树；若限界函数越界，也剪去相应子树；两者均满足则进入下一层；
2. 迭代回溯
采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。
// 针对N叉树的迭代回溯方法
void iterativeBacktrack ()
&&& int t = 1;
&&& while (t & 0) { //有路可走
&&&&&& if (f(n,t) &= g(n,t)) {
&&&&&&&&&& //& 遍历结点t的所有子结点
&&&&&&&&&& for (int i = f(n,t); i &= g(n,t); i ++) {
&&&&&&&&&&&&& x[t] = h(i);
&&&&&&&&&&&&& // 剪枝
&&&&&&&&&&&&& if (constraint(t) && bound(t)) {
&&&&&&&&&&&&&&&&& // 找到问题的解，输出结果
&&&&&&&&&&&&&&&&& if (solution(t)) {
&&&&&&&&&&&&&&&&&&&& output(x);
&&&&&&&&&&&&&&&&& }
&&&&&&&&&&&&&&&&& else // 未找到，向更深层次遍历
&&&&&&&&&&&&&&&&&&&& t ++;
&&&&&&&&&&&&& }
&&&&&&&&&& }
&&&&&& else {
&&&&&&&&&& t--;
回溯法通常在解空间树上进行搜索，一般依赖的两种数据结构：子集树和排列树
子集树（遍历子集树需O(2^n)计算时间）：
一般有装载问题、符号三角形问题、0-1背包问题、最大团问题
void backtrack (int t)
&&& if (t & n)
&&&&&& // 到达叶子结点
&&&&&& output (x);
&&&&&& for (int i = 0;i &= 1;i ++) {
&&&&&&&&&& x[t] =
&&&&&&&&&& // 约束函数
&&&&&&&&&& if ( legal(t) )
&&&&&&&&&&&&& backtrack( t+1 );
排列树（遍历排列树需要O(n!)计算时间）：
一般有批处理作业调度、n后问题、旅行售货员问题、圆排列问题、电路板排列问题
void backtrack (int t)
&&& if (t & n)
&&&&&& output(x);
&&&&&& for (int i =i &=i++) {
&&&&&&&&&& // 完成全排列
&&&&&&&&&& swap(x[t], x[i]);
&&&&&&&&&& if (legal(t))
&&&&&&&&&&&&& backtrack(t+1);
&&&&&&&&&& swap(x[t], x[i]);
其中f(n,t),g(n,t)表示当前扩展结点处未搜索过的子树的起始标号和终止标号, h(i)表示当前扩展节点处，x[t]第i个可选值constraint(t)和bound(t)是当前 扩展结点处的约束函数和限界函数。constraint(t)返回true时，在当前扩展结点 x[1:t]取值满足约束条件，否则不满足约束条件，可减去相应的子树。bound(t)返
回的值为true时，在当前扩展结点x[1:x]处取值未使目标函数越界，还需要由backtrack(t+1) 对其相应的子树进一步搜索。
应用回溯法有：
1）装载问题
2）批处理作业调度
3）符号三角形问题
4）n后问题
5）0-1背包问题
6）最大团问题
7）图的m着色问题
8）旅行售货员问题
9）圆排列问题
10）电路板排列问题
11）连续邮资问题
n皇后问题：
1.问题表述：在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。求不同的解的个数。
复杂问题从简单问题入手，我们先分析四皇后的问题，四叉树展示了求解的过程：
2. 问题分析：&
(1) 解空间：一组n元一维向量(x1, x2, x3, ... , xn),搜索空间是：1&=xi&=n， i=1,2,3,...,n
(2) 约束条件：
1)不同列：xi != xj
2)不处于同一正、反对角线：|i-j| != |x(i)-x(j)|
3. 代码实现：
定和0/1背包问题
问题表述：给定n种物品和一背包。第i件物品的重量是wi，其价值为pi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
0-1背包问题是一个数规划问题：确定一个向量：x=（x1,x2,...,xn）满足：
例如：n=3但是时候：
W = (10, 8,5)
p = (5,5,1)
最优解为：(1,01),此时价值为：6
0/1背包问题用完全二叉树表示的解空间：
问题分析：
(1) 解空间：一组n元一维向量(x1, x2, x3, ... , xn),搜索空间是：1&=xi&=n， i=1,2,3,...,n
(2) 约束条件：
&可行性约束函数：
上界函数：
考虑一个右子树的时候，设
r：是当前未考虑的剩余物品的总价值(remainder)
cp：是当前的价值(current price)
bestp：是当前得到的最优价值(best price)
那么，满足：
但是，上界r太松。
一个更加紧的上界：
将剩余物品按照单位重量价值排序，然后依次装入物品，直到装不下，再将剩余物品的一部分放入背包。(r_n &&= &r)
c语言实现：
c++实现：
图的遍历是指从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作，图的其它算法如求解图的连通性问题，拓扑排序，求关键路径等都是建立在遍历算法的基础之上。
由于图结构本身的复杂性，所以图的遍历操作也较复杂，主要表现在以下四个方面：
① 在图结构中，没有一个“自然”的首结点，图中任意一个顶点都可作为第一个被访问的结点。
② 在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中其余的连通分量。
③ 在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。
④ 在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。
图的遍历通常有深度优先搜索和广度优先搜索两种方式，他们对无向图和有向图都适用。
深度优先搜索（Depth_Fisrst Search）遍历类似于树的先根遍历，是树的先根遍历的推广。
&假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点发v 出发，访问此顶点，然后依次从v 的未被访问的邻接点出发深度优先遍历图，直至图中所有和v 有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
以如下图的无向图G5为例，进行图的深度优先搜索：
搜索过程：
假设从顶点v1 出发进行搜索，在访问了顶点v1 之后，选择邻接点v2。因为v2 未曾访问，则从v2 出发进行搜索。依次类推，接着从v4 、v8 、v5 出发进行搜索。在访问了v5 之后，由于v5 的邻接点都已被访问，则搜索回到v8。由于同样的理由，搜索继续回到v4，v2 直至v1，此时由于v1 的另一个邻接点未被访问，则搜索又从v1 到v3，再继续进行下去由此，得到的顶点访问序列为：
显然，这是一个递归的过程。为了在遍历过程中便于区分顶点是否已被访问，需附设访问标志数组visited[0:n-1], ，其初值为FALSE ，一旦某个顶点被访问，则其相应的分量置为TRUE。
1）邻接矩阵的存储方式实现：
2） 邻接表的表示实现方式
分析上述算法，在遍历时，对图中每个顶点至多调用一次DFS 函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间为O(n2) ，其中n 为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为O(e)，其中e 为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为O(n+e) 。
广度优先搜索（Breadth_First Search） 遍历类似于树的按层次遍历的过程。
假设从图中某顶点v 出发，在访问了v 之后依次访问v 的各个未曾访问过和邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程中以v 为起始点，由近至远，依次访问和v 有路径相通且路径长度为1,2,…的顶点。
对图如下图所示无向图G5 进行广度优先搜索遍历：
广度搜索过程：
首先访问v1 和v1 的邻接点v2 和v3，然后依次访问v2 的邻接点v4 和v5 及v3 的邻接点v6 和v7，最后访问v4 的邻接点v8。由于这些顶点的邻接点均已被访问，并且图中所有顶点都被访问，由些完成了图的遍历。得到的顶点访问序列为：
v1→v2 →v3 →v4→ v5→ v6→ v7 →v8
和深度优先搜索类似，在遍历的过程中也需要一个访问标志数组。并且，为了顺次访问路径长度为2、3、…的顶点，需附设队列以存储已被访问的路径长度为1、2、… 的顶点。
分析上述算法，每个顶点至多进一次队列。遍历图的过程实质是通过边或弧找邻接点的过程，因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。
最小生成树——无向连通图的所有生成树中有一棵边的权值总和最小的生成树
拓扑排序&——由偏序定义得到拓扑有序的操作便是拓扑排序。建立模型是AOV网
关键路径——在AOE-网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度，路径长度最长的路径叫做关键路径(Critical Path)。
最短路径——最短路径问题是图研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。
1.1 问题背景：
&&&&假设要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。n个城市之间，最多可能设置n(n-1)/2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢?
1.2 分析问题（建立模型）：
可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。即无向连通图的生成树不是唯一的。连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。
图 G5无向连通图的生成树&为(a)、(b)和(c)图所示：
& & & & & & & & & & & & & & & & & &&&G5
& &G5的三棵生成树：
可以证明，对于有n 个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n－1 条边。
1.3最小生成树的定义：
如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树，简称为最小生成树。
最小生成树的性质：
假设N=(V,{ E}) 是个连通网，U是顶点集合V的一个非空子集，若（u,v）是个一条具有最小权值(代价)的边，其中，
则必存在一棵包含边（u,v）的最小生成树。
1.4 解决方案：
两种常用的构造最小生成树的算法：普里姆（Prim）和克鲁斯卡尔（Kruskal）。他们都利用了最小生成树的性质
1.普里姆（Prim）算法：有线到点，适合边稠密。时间复杂度O(N^2)
假设G＝（V，E）为连通图，其中V 为网图中所有顶点的集合，E 为网图中所有带权边的集合。设置两个新的集合U 和T，其中
集合U（顶点集）&用于存放G 的最小生成树中的顶点，
& && 集合T& （边集合）存放G 的最小生成树中的边。
& &&&T ，U的初始状态：令集合U 的初值为U＝{u1}（假设构造最小生成树时，从顶点u1 出发），集合T 的初值为T＝{}。
& &&&Prim 算法的思想是：从所有u∈U，v∈V－U 的边中，选取具有最小权值的边（u，v）∈E，将顶点v 加入集合U 中，将边（u，v）加入集合T 中，如此不断重复，直到U＝V 时，最小生成树构造完毕，这时集合T 中包含了最小生成树的所有边。
Prim 算法可用下述过程描述，其中用wuv 表示顶点u 与顶点v 边上的权值。
（1）U＝{u1},T={};
（2）while (U≠V)do
& & & & & &(u，v)＝min{wuv；u∈U，v∈V－U }
& & & & & T＝T＋{(u，v)}
& & & & & U＝U＋{v}
（3）结束。
按照Prim 方法，从顶点1 出发，该网的最小生成树的产生过程如图：
为实现Prim 算法，需设置两个辅助closedge，用来保存U到集合V－U 的各个顶点中具有最小权值的边的权值。对每个Vi∈（V-U ）在辅助数组中存在一个相应的分量closedge[i-1],它包括两个域：
typedef&struct&ArcNode
初始状态时，U＝{v1}(u1 为出发的顶点),则到V-U 中各项中最小的边，即依附顶点v1的各条边中，找到一条代价最小的边（u0，v0）= （1，3）为生成树上一条边。
同时将v0（=v3）并入集合U中。然后修改辅助数组的值。
1）将closedge[2].lowcost = 0；//表示顶点V3三已经并入U
2) 由于边（v2,v3）的权值小于closedge[1].lowcost，故需修改closedge[1]为边（v2,v3）及其权值，同理修改closedge[4]，closedge[5].
& &closedge[1].adjvex& = 3.
& &closedge[1].lowcost = 5.
& &closedge[4].adjvex& = 1.
& &closedge[4].lowcost = 5.
&&& closedge[5].adjvex& = 3.
& &closedge[5].lowcost = 6.
以此类推，直至U = V;
下图 给出了在用上述算法构造网图7.16的最小生成树的过程中：
Prim 算法实现：
按照算法框架:
（1）U＝{u1},T={};
（2）while (U≠V)do
& & & & & &(u，v)＝min{wuv；u∈U，v∈V－U }
& & & & & T＝T＋{(u，v)}
& & & & & U＝U＋{v}
（3）结束。
当无向网采用二维数组存储的邻接矩阵存储时，Prim 算法的C 语言实现为：
&&&&&& 假设网中有n个顶点，则第一个进行初始化的循环语句的频度为n，第二个循环语句的频度为n-1。其中有两个内循环：其一是在closedge[v].lowcost中求最小值，其频度为n-1；其二是重新选择具有最小代价的边，其频度为n。 由此，普里姆算法的时间复杂度为O(n2)，与网中的边数无关，因此适用于求边稠密的网的最小生成树。
2.克鲁斯卡尔（Kruskal） :由点到线，适合边稀疏的网。时间复杂度：O(e * loge)
Kruskal 算法是一种按照网中边的权值递增的顺序构造最小生成树的方法。
基本思想是：
1) 设无向连通网为G＝（V，E），令G 的最小生成树为T，其初态为T＝（V，{}），即开始时，最小生成树T 由图G 中的n 个顶点构成，顶点之间没有一条边，这样T 中各顶点各自构成一个连通分量。
2) 在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量，则将此边加入到T中，否则舍弃此边而选择下一条边（若该边依附的两个顶点属于同一个连通分量，则舍去此边，以免造成回路）。依此类推，当T 中的连通分量个数为1 时，此连通分量便为G 的一棵最小生成树。
按照Kruskal 方法构造最小生成树的过程如图所示：
在构造过程中，按照网中边的权值由小到大的顺序，不断选取当前未被选取的边集中权值最小的边。依据生成树的概念，n 个结点的生成树，有n－1 条边，故反复上述过程，直到选取了n－1 条边为止，就构成了一棵最小生成树。
Kruskal 算法的实现：
算法的框架：
构造非连通图T＝（V，{}）
k = i= 0；//k为边数
while（k《& n-1） {
&&&& i++;
&&& 检查边E中第i条边的权值
&&& 最小边（u，v）
&&& 若（u，v） 加入T不是T产生回路，
&&& 则（u，v）加入T，且k++
&c语言实现：
C 语言实现Kruskal 算法，其中函数Find 的作用是寻找图中顶点所在树的根结点在数组father 中的序号。需说明的是，在程序中将顶点的数据类型定义成整型，而在实际应用中，可依据实际需要来设定。
2.&1．AOV网(Activity on vertex network)&&&&&
&&&&& 所有的工程或者某种流程可以分为若干个小的工程或阶段，这些小的工程或阶段就称为活动。若以图中的顶点来表示活动，有向边（弧）表示活动之间的优先关系，则这样活动在顶点上的有向图称为AOV 网（Activity On Vertex Network）。在AOV 网中，若从顶点i到顶点j之间存在一条有向路径，称顶点i是顶点j的前驱，或者称顶点j是顶点i的后继。若&i,j&是图中的弧，则称顶点i是顶点j
的直接前驱，顶点j 是顶点i 的直接后驱。
&&&&& AOV 网中的弧表示了活动之间存在的制约关系。例如，计算机专业的学生必须完成一系列规定的基础课和专业课才能毕业。学生按照怎样的顺序来学习这些课程呢？这个问题可以被看成是一个大的工程，其活动就是学习每一门课程。这些课程的名称与相应代号如表所示。
课程之间的优先关系图：
该图的拓扑有序系列：
&&&&在AOV-网中不应该出现有向环，因为存在环意味着某项活动应以自己为先决条件。若设计出这样的流程图，工程便无法进行。而对程序的数据流图来说，则表明存在一个死循环。因此，对给定的AOV-网应首先判定网中是否存在环。检测的办法是对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV-网中必定不存在环。
2.2．拓扑排序
离散数学基础知识：
首先复习一下离散数学中的偏序集合与全序集合两个概念。
若集合A 中的二元关系R 是自反的、非对称的和传递的，则R 是A 上的偏序关系。集合A 与关系R 一起称为一个偏序集合。
若R 是集合A 上的一个偏序关系，如果对每个a、b∈A 必有aRb 或bRa ，则R 是A上的全序关系。集合A 与关系R 一起称为一个全序集合。
直观地看，偏序指集合中仅有部分成员之间可比较，而全序指集合中全体成员之间均可比较。
[例如]，图7.25所示的两个有向图，图中弧(x,y)表示x≤y，则(a)表示偏序，(b)表示全序。若在(a)的有向图上人为地加一个表示v2≤v3的弧(符号“≤”表示v2领先于v3)，则(a)表示的亦为全序，且这个全序称为拓扑有序(Topological Order)，而由偏序定义得到拓扑有序的操作便是拓扑排序。
3.3& 拓扑排序算法
对AOV 网进行拓扑排序的方法和步骤是：
1、从AOV 网中选择一个没有前驱的顶点（该顶点的入度为0）并且输出它；
2、从网中删去该顶点，并且删去从该顶点发出的全部有向边；
3、重复上述两步，直到剩余的网中不再存在没有前驱的顶点为止。
这样操作的结果有两种：一种是网中全部顶点都被输出，这说明网中不存在有向回路；另一种就是网中顶点未被全部输出，剩余的顶点均不前驱顶点，这说明网中存在有向回路。
以下图(a)中的有向图为例，图中v1，和v6没有前驱，则可任选一个。假设先输出v6, 在删除v6及弧&v6，v4&，&v6，v5&之后，只有顶点v1没有前驱，则输出vl且删去vl及弧&v1，v2&、&v1，v3&和&v1, v4&，之后v3和v4都没有前驱。依次类推，可从中任选一个继续进行。最后得到该有向图的拓扑有序序列为：
v6 - v1 - v4 - v3 - v2 - v5
&&&&&&&&&&& 图AOV-网及其拓扑有序序列产生的过程
(a)AOV-网；(b)输出v6之后；(c)输出v1之后；(d)输出v4之后；(e)输出v3之后；(f)输出v2之后&
为了实现上述算法，对AOV 网采用邻接表存储方式，并且邻接表中顶点结点中增加一个记录顶点入度的数据域，即顶点结构设为：
顶点表结点结构的描述改为：
typedef struct vnode{ /*顶点表结点*/
int count /*存放顶点入度*/
VertexT /*顶点域*/
EdgeNode * /*边表头指针*/
当然也可以不增设入度域，而另外设一个一维数组来存放每一个结点的入度。算法中可设置了一个堆栈，凡是网中入度为0 的顶点都将其入栈。为此，拓扑排序的算法步骤为：
1、将没有前驱的顶点（count 域为0）压入栈；
2、从栈中退出栈顶元素输出，并把该顶点引出的所有有向边删去，即把它的各个邻接顶点的入度减1；
3、将新的入度为0 的顶点再入堆栈；
4、重复②～④，直到栈为空为止。此时或者是已经输出全部顶点，或者剩下的顶点中没有入度为0 的顶点。
为了避免重复检测入度为零的顶点，可另设一栈暂存所有入度为零的顶点。
3.1AOE网：（Activity on edge network）
& & & AOE网示意图若在带权的有向图中，以顶点表示事件，以有向边表示活动，边上的权值表示活动的开销（如该活动持续的时间），则此带权的有向图称为AOE网。
3.2 实际问题：
&&&&& 如果用AOE网来表示一项工程，那么，仅仅考虑各个子工程之间的优先关系还不够，更多的是关心整个工程完成的最短时间是多少；哪些活动的延期将会影响整个工程的进度，而加速这些活动是否会提高整个工程的效率。因此，通常在AOE网中列出完成预定工程计划所需要进行的活动，每个活动计划完成的时间，要发生哪些事件以及这些事件与活动之间的关系，从而可以确定该项工程是否可行，估算工程完成的时间以及确定哪些活动是影响工程进度的关键。
如图是一个假想的有11项活动的AOE-网：
其中有9个事件v1，v2，v3，…，v9，每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如v1表示整个工程开始，v9表示整个工程结束，v5表示a4和a5已经完成，a7和a8可以开始。与每个活动相联系的数是执行该活动所需的时间。比如，活动a1需要6天，a2需要4天等。
&和AOV-网不同，对AOE-网有待研究的问题是：
&&&&(1)完成整项工程至少需要多少时间?
&&&&(2)哪些活动是影响工程进度的关键?
3.3 关键路径
由于在AOE-网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度(这里所说的路径长度是指路径上各活动持续时间之和，不是路径上弧的数目)。路径长度最长的路径叫做关键路径(Critical Path)。
AOE网有关的概念：
1)路径长度：路径上各个活动的持续时间之和
2)完成工程的最短时间：由于AOE网中有活动是并行进行的，所以完成工程的最短时间就是从开始点到完成点的最长路劲长度。
3)活动最早开始时间(earlist time)(e(i))：从开始点到顶点vi的最长路径称为事件vi的最早发生时间。这个时间决定了以vi为尾的弧表示的活动的最早开始时间.
4)活动最晚开始时间(latest time)(l(i))：在不推迟整个工程完成的前提下，活动最迟开始的时间
5)完成活动的时间余量：该活动的最迟开始时间减去最早开始时间
6)关键路径(critical path)：路径长度最长的路径称为关键路径
7)关键活动(critical activity):关键路径上的活动称为关键活动，关键活动的特点是:e(i)=l(i)分析关键路径的目的就是辨别在整个工程中哪些是关键活动，以便争取提高关键活动的工作效率，缩短整个工程的工期。
3.4& 解决方案：
&&&&由上分析可知，辨别关键活动就是要找e(i)=l(i)的活动。为了求得AOE-网中活动的e(i)和l(i)， 首先求事件的最早发生时间ve(j)和最迟发生时间vl(j)。如果活动ai由弧&j,k&表示，其持续时间记为dut(&j,k&),则有如下关系：
&&&&& e(i ) = ve(j)&&&&&&&&&&&&&&
&&&& l(i) = vl(k)-dut(&j,k&)
&&&&求ve(j)和vl(j)需分两步进行：
&&&&（1）从ve(0)开始向前递推
&&&&&&&&其中，T是所有以第j个顶点为头的弧的结合。
&&&&（2）从vl(n-1)=ve(n-1)起向后递推
&&&&&&&&其中，S是所有以第i个顶点为尾的弧的集合。&
&&&&这两个递推公式的计算必须分别在拓扑有序和逆拓扑有序的前提下进行。也就是说ve(j-1)必须在vj的所有前驱的最早发生时间求得之后才能确定，而vl(j-1)则必须在vj的所有后继的最迟发生时间求得之后才能确定。因此，可以在拓扑排序的基础上计算ve(j-1)和vl(j-1)。
3.5 关键路径的算法：
&&&&(1)输入e条弧&j，k&，建立AOE-网的存储结构；&
&&&&(2)从源点v0出发，令ve[0]=0，按拓扑有序求其余各顶点的最早发生时间ve[i] (1≤i≤n-1)。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤(3)。
&&&&(3)从汇点vn出发，令vl[n-1]=ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间vl[i](n-2≥i≥0)；
&&&&(4)根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间 l(s)。若某条弧满足条件e(s)=l(s)，则为关键活动。&
&先将拓扑排序算法：TopologicalOrder（）
CriticalPath便为求关键路径的算法：
图(a)所示网的关键路径：可见a2、a5和a7为关键活动，组成一条从源点到汇点的关键路径，如图(b)所示。
图(a)所示网的计算结果:
& & &最短路径问题是图的又一个比较典型的应用问题。例如，某一地区的一个公路网，给定了该网内的n 个城市以及这些城市之间的相通公路的距离，能否找到城市A 到城市B 之间一条举例最近的通路呢？
如果将城市用点表示，城市间的公路用边表示，公路的长度作为边的权值，那么，这个问题就可归结为在网图中，求点A 到点B 的所有路径中，边的权值之和最短的那一条路径。这条路径就是两点之间的最短路径，并称路径上的第一个顶点为源点（Sourse），最后一个顶点为终点（Destination）。
单源点的最短路径问题：给定带权有向图G＝（V，E）和源点v∈V，求从v 到G 中其余各顶点的最短路径。在下面的讨论中假设源点为v0。
解决问题的迪杰斯特拉算法：
即由迪杰斯特拉（Dijkstra）提出的一个按路径长度递增的次序产生最短路径的算法。首先求出长度最短的一条最短路径，然后参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。
算法的基本思想是：
设置两个顶点的集合S 和T＝V－S，集合S 中存放已找到最短路径的顶点，集合T 存放当前还未找到最短路径的顶点。
初始状态时，集合S 中只包含源点v0，然后不断从集合T 中选取到顶点v0 路径长度最短的顶点u 加入到集合S 中，集合S 每加入一个新的顶点u，都要修改顶点v0 到集合T 中剩余顶点的最短路径长度值，集合T 中各顶点新的最短路径长度值为原来的最短路径长度值与顶点u 的最短路径长度值加上u 到该顶点的路径长度值中的较小值。此过程不断重复，直到集合T 的顶点全部加入到S 中为止。
Dijkstra 算法的实现:
首先，引进一个辅助向量D，它的每个分量D[i] 表示当前所找到的从始点v 到每个终点vi 的最短路径的长度。它的初态为：若从v 到vi 有弧，则D[i]为弧上的权值；否则置D[i]为∞。显然，长度为：
D[j]=Min{D[i]| vi∈V}
的路径就是从v 出发的长度最短的一条最短路径。此路径为（v ,vj）。
那么，下一条长度次短的最短是哪一条呢？假设该次短路径的终点是vk ，则可想而知，这条路径或者是（v, vk），或者是（v, vj, vk）。它的长度或者是从v 到vk 的弧上的权值，或者是D[j]和从vj 到vk 的弧上的权值之和。
依据前面介绍的算法思想，在一般情况下，下一条长度次短的最短路径的长度必是：
D[j]=Min{D[i]| vi∈V-S}
其中，D[i] 或者弧（v, vi）上的权值，或者是D[k]( vk∈S 和弧（vk, vi）上的权值之和。
根据以上分析，可以得到如下描述的算法：
（1）假设用带权的邻接矩阵edges 来表示带权有向图，edges[i][j] 表示弧〈vi, vj〉上的权值。若〈vi, vj〉不存在，则置edges[i][j]为∞（在计算机上可用允许的最大值代替）。S 为已找到从v 出发的最短路径的终点的集合，它的初始状态为空集。那么，从v 出发到图上其余各顶点（终点）vi 可能达到最短路径长度的初值为：
D[i]= edges[Locate Vex(G,v)][i] vi∈V
（2）选择vj，使得
D[j]=Min{D[i]| vi∈V-S}
vj 就是当前求得的一条从v 出发的最短路径的终点。令
（3）修改从v 出发到集合V-S 上任一顶点vk 可达的最短路径长度。如果
D[j]+ edges[j][k]&D[k]
则修改D[k]为
D[k]=D[j]+ edges[j][k]
重复操作（2）、（3）共n-1 次。由此求得从v 到图上其余各顶点的最短路径是依路径长度递增的序列。
如图8.26 所示一个有向网图G8 的带权邻接矩阵为：
有向网图G8 的带权邻接矩阵
用C 语言描述的Dijkstra 算法：
几种查找算法:顺序查找，折半查找，分块查找，散列表
一、顺序查找的基本思想：
&从表的一端开始，向另一端逐个按给定值kx 与关键码进行比较，若找到，查找成功，并给出数据元素在表中的位置；若整个表检测完，仍未找到与kx 相同的关键码，则查找失败，给出失败信息。
说白了就是，从头到尾，一个一个地比，找着相同的就成功，找不到就失败。很明显的缺点就是查找效率低。
【适用性】：适用于线性表的顺序存储结构和链式存储结构。
平均查找长度=（n+1）/2.
【顺序查找优缺点】：
缺点:是当n 很大时，平均查找长度较大，效率低；
优点:是对表中数据元素的存储没有要求。另外，对于线性链表，只能进行顺序查找。
二、有序表的折半查找基本思想：
在有序表中，取中间元素作为比较对象，若给定值与中间元素的关键码相等，则查找成功；若给定值小于中间元素的关键码，则在中间元素的左半区继续查找；若给定值大于中间元素的关键码，则在中间元素的右半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，查找失败。
① low=1；high=length； // 设置初始区间
② 当low&high 时，返回查找失败信息// 表空，查找失败
③ low≤high，mid=(low+high)/2; //确定该区间的中点位置
& & & a. 若kx&tbl.elem[mid].key，high = mid-1；转② // 查找在左半区进行
& & & b. 若kx&tbl.elem[mid].key，low& = mid+1； 转② // 查找在右半区进行
& & & c. 若kx=tbl.elem[mid].key，返回数据元素在表中位置// 查找成功
有序表按关键码排列如下：
7，14，18，21，23，29，31，35，38，42，46，49，52
在表中查找关键码为14 的数据元素:
&【算法实现】
【性能分析】
平均查找长度=Log2(n+1)-1
&从折半查找过程看，以表的中点为比较对象，并以中点将表分割为两个子表，对定位到的子表继续这种操作。所以，对表中每个数据元素的查找过程，可用二叉树来描述，称这个描述查找过程的二叉树为判定树。
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& (7，14，18，21，23，29，31，35，38，42，46，49，52)折半查找的判定树
可以看到，查找表中任一元素的过程，即是判定树中从根到该元素结点路径上各结点关键码的比较次数，也即该元素结点在树中的层次数。对于n 个结点的判定树，树高为k，则有2k-1 -1&n≤2k-1，即k-1&log2(n+1)≤k，所以k= 。因此，折半查找在查找成功时，所进行的关键码比较次数至多为。
接下来讨论折半查找的平均查找长度。为便于讨论，以树高为k 的满二叉树(n=2k-1)为例。假设表中每个元素的查找是等概率的，即Pi= ，则树的第i 层有2i-1 个结点，因此，折半查找的平均查找长度为：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
所以，折半查找的时间效率为O(log2n)。
虽然折半查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算，所以二分法比较适用于顺序存储结构。为保持表的有序性，在顺序结构中插入和删除都必须移动大量的结点。因此，折半查找特别适用于那种一经建立就很少改动而又经常需要查找的线性表。
三、分块查找（索引查找）的基本思想：
分块查找又称索引顺序查找，是对顺序查找的一种改进。分块查找要求将查找表分成 若干个子表，并对子表建立索引表，查找表的每一个子表由索引表中的索引项确定。索引 项包括两个字段：关键码字段(存放对应子表中的最大关键码值) ；指针字段(存放指向对 应子表的指针) ，并且要求索引项按关键码字段有序。查找时，先用给定值kx 在索引表中 检测索引项，以确定所要进行的查找在查找表中的查找分块(由于索引项按关键码字段有序，可用顺序查找或折半查找)
，然后，再对该分块进行顺序查找。
如关键码集合为：
&&&&&&&&&&&&&&&&&&&&&&&&&& （22，12，13，9，20，33，42，44，38，24，48，60，58，74，49，86，53）
按关键码&#，88 分为三块建立的查找表及其索引表如下：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
设表共n个结点，分b块，s=n/b
(分块查找索引表)平均查找长度=Log2（n/s+1）+s/2
(顺序查找索引表)平均查找长度=(S2+2S+n)/(2S)
分块查找的优点是在表中插入或删除一个记录时，只要找到该记录所属块，就在该块中进行插入或删除运算（因块内无序，所以不需要大量移动记录）。它主要代价是增加一个辅助数组的存储控件和将初始表分块排序的运算。
它的性能介于顺序查找和二分查找之间。
看过本文的人也看了：
我要留言技术领域：
取消收藏确定要取消收藏吗？
删除图谱提示你保存在该图谱下的知识内容也会被删除，建议你先将内容移到其他图谱中。你确定要删除知识图谱及其内容吗？
删除节点提示无法删除该知识节点，因该节点下仍保存有相关知识内容！
删除节点提示你确定要删除该知识节点吗？}