新書推薦：
《
药食同源中药鉴别图典
》
售價：NT$
305.0
《
设计中的比例密码：建筑与室内设计
》
售價：NT$
398.0
《
冯友兰和青年谈心系列：看似平淡的坚持
》
售價：NT$
254.0
《
舍不得星星：全2册
》
售價：NT$
356.0
《
汉字理论与汉字阐释概要 《说解汉字一百五十讲》作者李守奎新作
》
售價：NT$
347.0
《
汗青堂丛书144·决战地中海
》
售價：NT$
765.0
《
逝去的武林（十周年纪念版 武学宗师 口述亲历 李仲轩亲历一九三零年代武人言行录）
》
售價：NT$
250.0
《
唐代冠服图志（百余幅手绘插画 图解唐代各类冠服 涵盖帝后 群臣 女官 士庶 军卫等 展现唐代社会风貌）
》
售價：NT$
398.0
|
| 編輯推薦： |
|
本书为教育部高等学校电子信息类专业教学指导委员会规划教材，适用于电类非计算机专业，配套教学课件，下载地址为清华大学出版社网站本书页面。本书特色如下：（1） 系统性：涵盖了计算机软件技术基础课程中的经典内容；全书以数据结构为主体，兼顾介绍了软件开发中所需要的操作系统、软件工程和数据库等方面的知识。（2） 实用性：围绕软件开发实践展开全面论述，解决软件开发中的普遍技术问题，配备丰富的例题和练习题。（3） 针对性：简明扼要地论述基本概念，深入浅出地阐明软件开发涉及的基本技术；本书非常适合于电类非计算机专业的授课需求。
|
| 內容簡介： |
本书是根据高等学校电子信息类专业对计算机软件技术课程的基本要求，结合作者多年来的教学改革和教学实践，来组织编写的高等学校计算机软件技术基础课程。
本书内容主要包括计算机软件技术绪论、线性数据结构、非线性数据结构、排序和查找、资源管理、软件开发和数据库设计。每章都配有较多的习题，书后附有部分习题答案。
本书内容丰富、语言简明扼要、实用性强，可作为高等院校本科、专科计算机软件技术基础课程教材，也可作为广大从事计算机应用工作的技术人员的参考书。
|
| 目錄：
|
第1章绪论
1．1计算机软件
1．1．1计算机软件的概念
1．1．2计算机语言
1．1．3计算机软件的分类
1．1．4计算机软件的发展
1．2数据结构概述
1．2．1数据基本概念
1．2．2数据结构
1．2．3数据类型
1．3算法及算法分析
1．3．1算法
1．3．2算法的性能分析
1．4小结
1.5习题
第2章线性数据结构
2．1线性表的定义
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．5栈
2．5．1栈的基本概念
2．5．2栈的运算
2．5．3栈的应用
2．6队列
2．6．1队列的基本概念
2．6．2顺序循环队列及其运算
2．6．3链式队列及其运算
2．6．4队列的应用
2．7串
2．7．1串的定义
2．7．2串的运算
2.7.3串的存储方式
2．7．4串的模式匹配
2．8数组
2．8．1数组的定义
2．8．2数组的顺序存储
2．8．3矩阵的压缩存储
2．9小结
2.10习题
第3章非线性数据结构
3．1树的概念
3．2二叉树
3．2．1二叉树的定义
3．2．2二叉树的主要性质
3．2．3二叉树的存储结构
3．3二叉树的遍历
3．3．1遍历的概念
3．3．2二叉树遍历算法
3．3．3二叉树遍历算法的应用
3．4树和森林
3．4．1树和森林的存储结构
3．4．2树和森林与二叉树之间的转换
3．4．3树和森林的遍历
3．5二叉树的应用
3．5．1哈夫曼树及其应用
3．5．2二叉排序树
3．6图
3．6．1图的基本概念
3.6.2图的存储方法
3.6.3图的遍历
3.6.4图的应用
3.7小结
3.8习题
第4章排序和查找
4.1排序的基本概念
4.2插入排序
4.2.1直接插入排序
4.2.2折半插入排序
4.2.3希尔排序
4.3交换排序
4.3.1冒泡排序
4.3.2快速排序
4.4选择排序
4.4.1简单选择排序
4.4.2堆排序
4.5其他排序
4.5.1归并排序
4.5.2基数排序
4.6各种排序方法的比较和选择
4.7查找的基本概念
4.8静态查找表与算法
4.8.1顺序查找
4.8.2折半查找
4.8.3分块查找
4.9动态查找表
4.9.1二叉搜索树
4.9.2平衡二叉树
4.10哈希表及其查找
4.10.1哈希表的概念
4.10.2几种哈希函数
4.10.3处理冲突的方法
4.10.4哈希表的算法
4.10.5哈希表的应用
4.11小结
4.12习题
第5章资源管理
5.1操作系统的概念
5.1.1操作系统的定义
5.1.2操作系统的分类
5.1.3操作系统的特征
5.1.4操作系统的功能
5.2多道程序设计
5.2.1并发程序设计
5.2.2进程
5.2.3进程之间的通信
5.2.4多道程序的组织
5.3存储空间的管理
5.3.1内存储器的管理
5.3.2外存储器中文件的组织结构
5.4小结
5.5习题
第6章软件开发
6.1软件工程概述
6.1.1软件工程的概念
6.1.2软件生命周期
6.2软件的需求分析
6.2.1需求分析概述
6.2.2结构化分析方法
6.2.3数据流图
6.2.4数据字典
6.3软件的设计
6.3.1软件设计概述
6.3.2结构化设计方法
6.3.3详细设计方法
6.3.4面向对象的程序设计方法
6.4软件的编程
6.5软件的测试
6.5.1软件测试概述
6.5.2软件测试的过程
6.5.3测试用例的设计
6.6软件的调试
6.6.1软件调试的方法
6.6.2常用的调试策略
6.7软件维护
6.8小结
6.9习题
第7章数据库设计
7.1数据库基本概念
7.1.1数据库技术与数据库系统
7.1.2数据模型
7.1.3数据库系统的结构
7.2关系数据库语言SQL
7.2.1SQL语言概述
7.2.2数据定义功能
7.2.3数据查询功能
7.2.4数据更新功能
7.3数据库设计
7.3.1数据库设计概述
7.3.2需求分析
7.3.3概念设计
7.3.4逻辑设计
7.3.5物理设计
7.3.6数据库的实施
7.3.7数据库的运行和维护
7.4小结
7.5习题
附录部分习题参考答案
参考文献
|
| 內容試閱：
|
前言
随着计算机应用领域的扩大和深入，非计算机专业的工程技术人员掌握必要的计算机软件技术基础知识是提高计算机应用水平、利用计算机技术解决本专业工作中的具体问题的重要途径。非计算机类专业本科生既熟悉自己所从事的专业，又掌握计算机的应用知识是一个优势。事实上，许多应用软件都是由非计算机专业出身的计算机应用人员研发的。计算机软件基础是高等学校电子信息类专业的一门学科基础必修课，被一些高校列为电子类各专业的重点课程或核心课程。通过多年来对本课程的教学研究和教学改革，我们在教学内容、教学方法和考核方式上已基本形成一套比较完整的体系，以切实提高学生的程序设计能力。好的教材源于教学改革和教学实践，能体现出良好的成果。在多年教学经验的基础上，通过对已有教材的分析研究，结合自己的教研工作，编写此教材。本教材的特点是强调实用性，以应用为目的，含有丰富的实例； 可读性强，深入浅出，通俗易懂，力求概念准确，表述清楚，简明扼要； 所有算法采用C语言描述； 适合非计算机专业的学生阅读。全书内容以数据结构为主，同时包含操作系统、软件工程和数据库三部分内容。教学时可根据具体情况对讲授内容进行适当取舍。本书由汪友生编写线性表、栈和队列、串和数组、树等部分； 张新峰编写绪论、排序和软件开发等部分； 王众编写查找部分； 张小玲编写资源管理部分； 刘芳编写数据库设计部分； 郭民编写图部分。全书由汪友生统稿。本书在编写时，参考了大量的文献资料，对相关作者表示真诚的感谢！由于编者水平有限，书中难免存在疏漏和不妥之处，恳请各位读者批评指正。编者2016年6月
第3章非线性数据结构第2章介绍的是线性数据结构，线性数据结构中的每个元素有唯一的前驱元素和唯一的后继元素，即前驱元素和后继元素是一对一的关系。本章将介绍非线性数据结构，包括树和图，树的元素有唯一的前驱元素和多个后继元素，即前驱元素和后继元素是一对多的关系。树形结构是非常重要的一种数据结构，在实际应用中也非常广泛，它主要应用在文件系统、目录组织等大量的数据处理中。图是另一种非线性数据结构，是一种更为复杂的数据结构。在图中，数据元素之间是多对多的关系，即一个数据元素对应多个直接前驱元素和多个直接后继元素。图的应用领域十分广泛，例如工程设计、遗传学、人工智能等。3．1树的概念树是由n n 0个结点组成的有限集合。如果n = 0，称为空树； 如果n 0，则有且仅有一个特定的称之为根Root的结点，它只有直接后继，但没有直接前驱； 当n 1，除根以外的其他结点划分为m m 0个互不相交的有限集合T1, T2 ,, Tm，其中每个集合本身又是一棵树，并且称为根的子树SubTree。如图31所示。
T = { A，B，C，D，E，F，G，H，I，J }，其中A是根，其余结点可以划分为两个互不相交的集合，T1= { B，D，G，H，I }，T2 ={ C，E， F，G }，这两个集合本身又各是一棵树，它们是A的子树。对于T2，C是根，其余结点可以划分为两个互不相交的集合，T21 ={ E，J }，T22 ={ F }，T21，T22是C的子树。树的结构定义是一个递归的定义，即在树的定义中又用到了树的概念，它道出了树的固有特性。如图32中的子树T1和T2就是根结点A的子树， D,G,H,I组成的树又是B结点的子树，E,J组成的树是C结点的子树。
图31一般的树
图32两棵子树
对于树的定义还需要注意两点。1 n0时，根结点是唯一的，不可能存在多个根结点。2 m0时，子树的个数没有限制，但它们一定是互不相交的。如图33中的两个结构就不符合树的定义。
图33非树的表示
树的逻辑表示方法可以分为4种，分别是树形表示法、文氏图表示法、广义表表示法和凹入表示法。1 树形表示法。图31就是树形表示法。树形表示法是最常见的一种表示方法，它可以直观、形象地表示出树的逻辑结构，可以清晰地反映出树中结点之间的逻辑关系。2 文氏图表示法。文氏图表示法是利用数学中集合的图形化表示来描述树的逻辑关系。图31的树，可用文氏图表示如图34所示。3 广义表表示法。采用广义表的形式表示树的逻辑结构，广义表的子表表示结点的子树。图31的树，利用广义表表示为ABDG,H,I,CEJ,F。4 凹入表示法。凹入表示法类似于书的目录、章、节、条、款、项逐个凹入。图31的树，可用凹入表示法如图35所示。
图34树的文氏图表示法
图35树的凹入表示法
下面列出树结构中的一些术语。结点： 树的结点包含一个数据元素及若干指向其子树的分支。孩子结点： 结点的子树的根称为该结点的孩子。如图31中D是B的孩子。双亲结点： B结点是A结点的孩子，则A结点是B结点的双亲。如图31中B是D的双亲。兄弟结点： 同一双亲的孩子结点。如图31中G、H和I互为兄弟。堂兄结点： 其双亲结点互为兄弟的结点。如图31中D的双亲结点B与E的父结点C互为兄弟，则称D与E互为堂兄。祖先结点： 结点的祖先是从根到该结点所经分支上的所有结点。如图31中F的祖先为A、C。子孙结点： 以某结点为根的子树中的任一结点称为该结点的子孙。如图31中A的子孙为B、C、D、E、F等。结点的度： 结点拥有的子树的个数为结点的度。如图31中A结点的度为2。叶子： 度为0的结点为叶子或者终端结点。如图31的G,H,I,J。树的度： 树内各结点的度的最大值。如图31树的度为3。层次： 结点的层次Level从根开始定义起，根为第一层，根的孩子为第二层，以此类推。树中结点的最大层次为树的深度或高度，如图31所示的树的深度为4。若将树中每个结点的各子树看成是从左到右有次序的即不能互换，则称该树为有序树OrderedTree； 否则称为无序树UnorderedTree。若不特别指明，一般讨论的树都是有序树。森林Forest是mm0棵互不相交的树的集合。对树中每个结点，其子树的集合即为森林。树和森林的概念相近。删去一棵树的根，就得到一个森林； 反之，加上一个结点作树根，森林就变为一棵树。树的基本操作主要有1 初始化操作InitateT： 创建一棵空树T。2 销毁树操作DestoryT：销毁树T。3 构造树操作CreatT,definition：按definition构造树T，definition给出树的定义。4 清空树操作ClearT：将树T清为空树。5 求根函数RootT：求树T的根。6 插入操作InsertT,x,i,y： 将以y为根的子树插入到树T中作为结点x的第i棵子树。7 删除操作DeleteT,x,i：将树T中结点x的第i棵子树删除。8 遍历树操作TraverseT： 按某种次序对树T中的每个结点访问一次且仅一次。（9） 求双亲操作ParentT, x： 若x是T的非根结点，则返回它的双亲，否则函数值返回空。（10） 求右兄弟操作RightSiblingT, X： 若x有右兄弟结点，则返回它的右兄弟，否则返回空。（11） 求孩子操作ChildT, x, i： 若x是T的非叶子结点，则返回它的第i个孩子，否则返回空。3．2二叉树树结构中有一种应用较为广泛的树二叉树（Binary Tree）。二叉树的度为2，而且是一棵有序树，即树中结点的子树从左到右有次序。3．2．1二叉树的定义二叉树是一个有限元素的集合，该集合或者为空、或者由一个称为根root的元素及两个不相交的、分别称为左子树和右子树的二叉树组成。值得注意的是，度为2的有序树与二叉树是不同的。假设要在有两个孩子的结点中删除第一个孩子。在度为2的有序树中，删除了第一个孩子，原来第2个孩子改称为第1个孩子； 二叉树中，如果删除了左孩子，右孩子依然是右孩子。二叉树是另外一种树形结构，即不存在度大于2的结点，每个结点至多只有两棵子树，二叉树的子树有左右之分，左、右子树不能颠倒，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。另外，二叉树是递归结构，二叉树的定义中又用到了二叉树的概念。图36列出了二叉树的5种基本形态。
图36二叉树的5种基本状态
3．2．2二叉树的主要性质二叉树具有下列重要性质：（1） 性质1： 二叉树的第i层上至多有2i-1个结点i 1。［证明用归纳法］证明： 当i=1时，只有根结点，2i-1=20=1。假设对所有j， 1j1，则其双亲是结点i2。② 如果2in，则结点i为叶子结点，无左孩子； 否则，其左孩子是结点2i。③ 如果2i＋1n，则结点i无右孩子； 否则，其右孩子是结点2i＋1。证明： 此性质可采用数学归纳法证明。因为1与2、3是相对应的，所以只需证明2和3。当 i=1时，根据结点编号方法可知，根的左、右孩子编号分别是2和3，结论成立。假定i-1时结论成立，即结点i-1的左右孩子编号满足 lchildi-1=2i-1； rchildi-1=2i-1 1。通过完全二叉树可知，结点 i 或者与结点i-1同层且紧靠其右，或者结点i-1在某层最右端，而结点i在其下一层最左端。但是，无论如何，结点i的左孩子的编号都是紧接着结点i-1的右孩子的编号，故lchildi=rchildi-1 1=2i； rchildi=lchildi 1=2i 1命题成立。3．2．3二叉树的存储结构二叉树的存储结构有两种，分别是顺序存储表示和链式存储表示。1． 顺序存储结构所谓顺序存储结构，就是用一组连续的存储单元存储二叉树的数据元素，结点在这个序列中的相互位置能反映出结点之间的逻辑关系。二叉树中结点之间的关系就是双亲结点与左右孩子结点间的关系。因此，必须把二叉树的所有结点安排成为一个恰当的序列。C语言中，这种存储形式的类型定义如下所示。
#define MaxTreeNodeNum 100*二叉树的最大结点数*
typedef struct {
DataType data［MaxTreeNodeNum］; *0号结点存放根结点*
int n;
} QBiTree;
通常，按照二叉树结点从上至下、从左到右的顺序存储，但这样结点在存储位置上的前驱后继关系并不一定就是它们在逻辑上的邻接关系。依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。图38a为图37b所示的完全二叉树的顺序存储结构。对于一般的二叉树，则应将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应分量中，如图37c所示二叉树的顺序存储结构如图38b所示，图中以0表示不存在的结点。由此可见，这种顺序存储结构仅适用于完全二叉树。因为，在最坏的情况下，一个深度为k且只有k个结点的单支树树中不存在度为2的结点却需要长度为2k-1的一维数组。
图38二叉树的顺序存储结构
完全二叉树的编号特点为除最下面一层外，各层都充满了结点。每一层的结点个数恰好是上一层结点个数的2倍。从一个结点的编号就可推得其双亲，左、右孩子，兄弟等结点的编号。假设编号为i的结点是Ki1in，则有（1） 若i1，则Ki的双亲编号为i2； 若i=1，则Ki是根结点，无双亲。（2） 若2in，则Ki的左孩子编号为2i； 否则，Ki无左孩子，即Ki必定是叶子。（3） 若2i 1n，则Ki的右孩子编号为2i 1； 否则，Ki无右孩子。（4） 若i为奇数且不为1，则Ki的左兄弟编号为i-1； 否则，Ki无左兄弟。（5） 若i为偶数且小于n，则Ki的右兄弟编号为i 1； 否则，Ki无右兄弟。顺序存储的优缺点是适合于完全二叉树，既不浪费存储空间，又能很快确定结点的存放位置，以及结点的双亲和左右孩子的存放位置。但对一般二叉树，可能造成存储空间的浪费。2． 链式存储结构所谓链式存储是指用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常有下面两种形式。1 二叉链表存储链表中每个结点由3个域组成，即数据域和两个指针域。data域存放某结点的数据信息； lchild与rchild分别存放指向左孩子和右孩子的指针。当左孩子或右孩子不存在时，相应指针域值为空用符号或NULL表示。结点的存储结构如图39所示。
图39二叉链表存储结构
C语言中，这种存储形式的类型定义如下所示。
typedef char DataType； *用户可根据具体应用定义DataType的实际类型*
typedef struct bnode {
DataType data;
struct bnode *lchild, *rchild; *左右孩子指针*
} BiTree;
图310b给出了图310a所示的一棵二叉树的二叉链表存储结构。链头的指针指向二叉树的根结点。容易证得，在含有n个结点的二叉链表中有n 1个空链表域。
图310链表存储结构
2 三叉链表存储每个结点由4个域组成，具体结构如图311所示。
图311三叉链表存储结构
其中，data、lchild及rchild三个域的意义与二叉链表结构相同； parent域为指向该结点双亲结点的指针。这种存储结构既便于查找孩子结点，又便于查找双亲结点； 但是，相对于二叉链表存储结构，它增加了空间开销。图310c给出了图310a所示的一棵二叉树的三叉链表存储结构。尽管，在二叉链表中无法由结点直接找到其双亲，但由于二叉链表结构灵活，操作方便，对于一般情况的二叉树，甚至比顺序存储结构还节省空间。例如，深度为4的右单支二叉树共有4个结点，二叉链表的8个指针域3个非空，顺序存储24-1共15个元素空间仅使用了4个。因此，二叉链表是最常用的二叉树存储方式。本书后面涉及的二叉树的链式存储结构，如不加特别说明都是指二叉链表结构。3． 二叉树的基本操作采用二叉链表存储结构表示的二叉树的基本操作实现如下所示。1 二叉树的初始化操作二叉树的初始化需要将指向二叉树的根结点指针置为空，代码如下：
void InitBitTreeBiTree *T *二叉树的初始化操作*
{
T=NULL;
}
2 二叉树的销毁操作如果二叉树存在，将二叉树的存储空间释放。
void DestoryBitTreeBiTree *T*销毁二叉树*
{
ifT *如果是非空二叉树*
{
ifT-lchild
DestoryBitTreeT-lchild;
ifT-rchild
DestoryBitTreeT-rchild;
freeT;
T=NULL;
}
}
3 创建二叉树操作根据二叉树的递归定义，先生成二叉树的根结点，将元素值赋值给结点的数据域，然后递归创建左子树和右子树。其中#表示空。代码如下：
void CreateBitTreeBiTree *T*递归创建二叉树*
{
DataType ch;
scanf"%c", &ch;
ifch==#
T=NULL;
else
{
T=BiTree *mallocsizeofbnode;*生成根结点*
if!T
exit-1;
T-data=ch;
CreateBitTreeT-lchild;*构造左子树*
CreateBitTreeT-rchild;*构造右子树*
}
}
4 二叉树的左插入操作指针p指向二叉树T的某个结点，将子树c插入到T中，使c成为p指向结点的左子树，p指向结点的原来左子树成为c的右子树。代码如下：
int InsertLeftChildBiTree p,BiTree c*二叉树的左插入操作*
{
ifp *如果指针p不空*
{
c-rchild=p-lchild; *p的原来的左子树成为c的右子树*
p-lchild=c;*子树c作为p的左子树*
return 1;
}
return 0;
}
5 二叉树的右插入操作指针p指向二叉树T的某个结点，将子树c插入到T中，使c成为p指向结点的右子树，p指向结点的原来左子树成为c的右子树。代码如下：
int InsertReftChildBiTree p,BiTree c *二叉树的右插入操作*
{
ifp *如果指针p不空*
{
c-rchild=p-rchild;* p的原来的右子树成为c的右子树*
p-rchild=c; *子树c作为p的右子树*
return 1;
}
return 0;
}
6 二叉树的左删除操作二叉树中，指针p指向二叉树中的某个结点，将p所指向的结点的左子树删除。如果删除成功，返回1； 否则，返回0。代码如下：
Int DeleteLeftChildBiTree p *二叉树的左删除操作*
{
ifp
{
DestoryBiTreep-lchild; *删除p指向结点的左子树*
return 1;
}
return 0;
}
7 二叉树的右删除操作二叉树中，指针p指向二叉树中的某个结点，将p所指向的结点的右子树删除。如果删除成功，返回1； 否则，返回0。代码如下：
Int DeleteRightChildBiTree p*二叉树的右删除操作*
{
ifp
{
DestoryBiTree&p-rchild; *删除p指向结点的右子树*
return 1;
}
return 0;
}
8 返回二叉树的左孩子元素值基本操作如果元素值为e的结点存在，并且该结点的左孩子结点存在，则将该结点的左孩子结点的元素值返回。代码如下：
DataType LeftChildBiTree T, DataType e *返回二叉树的左孩子结点元素值操作*
{
BiTree p; *如果二叉树非空*
ifT
{
p=PointT, e;*p是元素值e的结点的指针*
ifp&&p-lchild*如果p不为空，且p的左孩子结点存在*
return p-lchild-data;*返回p的左孩子结点的元素值*
}
return;
}
9 返回二叉树的右孩子元素值基本操作如果元素值为e的结点存在，并且该结点的右孩子结点存在，则将该结点的右孩子结点的元素值返回。代码如下：
DataType LeftChildBiTree T, DataType e *返回二叉树的右孩子结点元素值操作*
{
BiTree p; *如果二叉树非空*
ifT
{
p=PointT, e;*p是元素值e的结点的指针*
ifp&&p-rchild*如果p不为空，且p的右孩子结点存在*
return p-rchild-data;*返回p的右孩子结点的元素值*
}
return;
}
3．3二叉树的遍历3．3．1遍历的概念
二叉树的遍历指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。这里提到的访问含义很广，可以是查询、修改、输出某元素的值，以及对元素做某种运算等，但要求这种访问不破坏它原来的数据结构。遍历一个线性结构很简单，只须从开始结点出发，顺序扫描每个结点。但对二叉树这样的非线性结构，每个结点可能有两个后继结点，因此需要寻找一种规律来系统访问树中的各结点。遍历是二叉树中经常用到的一种操作。因为在实际应用问题中，常常需要按一定顺序对二叉树中的每个结点逐个进行访问，查找具有某一特点的结点，然后对这些满足条件的结点进行处理。通过一次完整的遍历，可使二叉树中结点信息由非线性排列变为某种意义上的线性序列。也就是说，遍历操作可使非线性结构线性化。3．3．2二叉树遍历算法1． 二叉树的遍历方法及递归实现
由于二叉树的定义是递归的，它是由3个基本单元组成，即根结点、左子树和右子树。因此，遍历一棵非空二叉树的问题可以分解为3个子问题，即访问根结点、遍历左子树、遍历右子树，只要依次遍历这3部分，就可以遍历整个二叉树。由于实际问题一般都要求左子树较右子树先遍历，通常习惯先左后右的原则，放弃了先右后左的次序。于是，将根结点放在左、右子树的前、中、后，得到3种遍历次序，分别称为先序遍历、中序遍历和后序遍历。令L，R，T分别代表二叉树的左子树、右子树、根结点，则有TLR、LTR、LRT 3种遍历规则。1 先序遍历二叉树TLR先序遍历的递归过程为： 若二叉树为空，遍历结束。否则，（1） 访问根结点。（2） 先序遍历根结点的左子树。（3） 先序遍历根结点的右子树。先序遍历二叉树的递归算法如下：
void PreOrderBiTree *bt
{*先序遍历二叉树bt*
if bt==NULL return; *递归调用的结束条件*
Visitbt-data; *访问结点的数据域*
PreOrderbt-lchild; *先序递归遍历bt 的左子树*
PreOrderbt-rchild; *先序递归遍历bt 的右子树*
}
2 中序遍历二叉树LTR中序遍历的递归过程为： 若二叉树为空，遍历结束。否则，1 中序遍历根结点的左子树。2 访问根结点。3 中序遍历根结点的右子树。中序遍历二叉树的递归算法如下：
void InOrderBiTree *bt
{*中序遍历二叉树bt*
if bt==NULL return; *递归调用的结束条件*
InOrderbt-lchild; *中序递归遍历bt 的左子树*
Visitbt-data; *访问结点的数据域*
InOrderbt-rchild; *中序递归遍历bt 的右子树*
}
3 后序遍历二叉树LRT后序遍历的递归过程为： 若二叉树为空，遍历结束。否则，（1） 后序遍历根结点的左子树。（2） 后序遍历根结点的右子树。（3） 访问根结点。后序遍历二叉树的递归算法如下：
void PostOrderBiTree *bt
{*后序遍历二叉树bt*
if bt==NULL return; *递归调用的结束条件*
PostOrderbt-lchild; *后序递归遍历bt 的左子树*
PostOrderbt-rchild; *后序递归遍历bt 的右子树*
Visitbt-data; *访问结点的数据域*
}
图312二叉树
如图312所示的二叉树，若要先序遍历此二叉树，按访问结点的先后顺序将结点排列起来，可以得到该二叉树的先序序列ABDGCEF。类似地，中序遍历此二叉树，可以得到二叉树的中序序列DGBAECF。后序遍历此二叉树，可以得到二叉树的后序序列GDBEFCA。
2． 二叉树遍历的非递归实现先序、中序、后序遍历的非递归算法共同之处，即用栈来保存先前走过的路径，以便在访问完子树后,可以利用栈中的信息，回退到当前节点的双亲节点,进行下一步操作。1 先序遍历二叉树算法实现： 从二叉树根结点开始，沿左子树一直走到末端左子树为空为止，在走的过程中，访问所遇结点，并依次把遇到的结点进栈。当左子树为空时，从栈顶退出某结点，并将指针指向该结点的右子树。如此重复，直到栈为空或指针为空止。先序遍历非递归算法如下：
void PreOrder BiTree *t *非递归先序遍历二叉树t，对每个元素调用Visit函数*
{PSeqStackS;
bnode * p = t;
S=Init_SeqStack ;
while p ||!Empty_SeqStack S
{if p *二叉树非空*
{Visit p-data ; *访问结点的数据域*
Push_SeqStack S, p;
p = p-lchild;*遍历左子树*
}
else
{
Pop_SeqStack S,&p ;
p = p-rchild;*向右跨一步，以便遍历右子树*
}
}
}
2 中序遍历二叉树算法实现： 设根指针为p，可能有以下两种情况。（1） 若p！=NULL，则p入栈，遍历其左子树。（2） 若p==NULL，则返回。此时，① 若栈空，则整个遍历结束；② 否则，表明栈顶结点的左子树已遍历结束。此时，退栈，访问p，并遍历其右子树。中序遍历非递归算法如下：
void InOrder BiTree *t *非递归中序遍历二叉树t，对每个元素调用Visit函数*
{PSeqStackS;
bnode * p = t;
S=Init_SeqStack ;
while p ||!Empty_SeqStack S
{
if p *二叉树非空*
{
Push_SeqStack S, p;
p = p-lchild;
}
else
{
Pop_SeqStack S,&p ;
Visit p-data ;
p = p-rchild;
}
}
}
3 后序遍历二叉树算法实现： 利用栈来实现二叉树的后序遍历要比先序和中序遍历复杂得多。后序遍历中，当搜索指针指向某一个结点时，不能马上进行访问，而先要遍历左子树，所以此结点应先进栈保存，当遍历完它的左子树后，再次回到该结点，还不能访问它，还需先遍历其右子树，所以该结点必须再次进栈，只有等它的右子树遍历完后，再次退栈时，才能访问该结点。为了区分同一结点的两次进栈，引入一个栈次数的标志，元素第1次进栈标志为0，第2次进标志为1，当退出的元素标志为1时，访问结点。设根指针为p，可能有以下两种情况。（1） 若p！=NULL，则p及标志flag=0入栈，遍历其左子树。（2） 若p==NULL，则返回。此时，① 若栈空，则整个遍历结束；② 否则，表明栈顶结点的左子树或右子树已遍历结束。此时，若栈顶结点的flag=0，则修改为1，并遍历其右子树； 否则，访问栈顶结点并退栈，再转至（1）。后序遍历非递归算法如下：
typedef struct
{
bnode *node;
int flag;
} DataType;
void PostOrder BiTree*t *非递归后序遍历二叉树t，对每个元素调用Visit函数*
{
PSeqStack S;
DataType Sq;
bnode * p = t;
S=Init_SeqStack ;
while p ||!Empty_SeqStack S
{
if p
{
Sq.flag=0;
Sq.node=p;
Push_SeqStack S, Sq;
p = p-lchild; }
else
{
Pop_SeqStack S,&Sq;
p = Sq.node;
if Sq.flag==0
{
Sq.flag=1;
Push_SeqStack S,Sq;
p= p-rchild; }
else
{
Visit p-data ;
p=NULL; }
}
}
}
3． 二叉树的层次遍历所谓二叉树的层次遍历，就是指从二叉树的第1层根结点开始，从上到下逐层遍历，同一层中，则按照从左到右的顺序对结点逐个访问。对于图312所示的二叉树，按层次遍历所得到的结果序列为ABCDEFG。按层次遍历二叉树的算法描述： 使用一个队列结构完成这项操作。所谓记录访问结点就是入队操作； 取出记录的结点就是出队操作。1 访问根结点，并将根结点入队。2 当队列不空时，重复下列操作：① 从队列退出一个结点；② 若其有左孩子，则访问左孩子，并将其左孩子入队；③ 若其有右孩子，则访问右孩子，并将其右孩子入队。下面的层次遍历算法中，二叉树以二叉链表存放，一维数组Queue［MAXNODE］用以实现队列，变量front和rear分别表示当前队首元素和队尾元素在数组中的位置。
void LevelOrderBiTree *bt
*层次遍历二叉树bt*
{
BiTree Queue［MAXNODE］;
int front,rear;
if bt==NULL return;
front=-1;
rear=0;
queue［rear］=bt;
whilefront!=rear
{
front;
Visitqueue［front］-data; *访问队首结点的数据域*
if queue［front］-lchild!=NULL *将队首结点的左孩子结点入队列*
{
rear;
queue［rear］=queue［front］-lchild;
}
if queue［front］-rchild!=NULL *将队首结点的右孩子结点入队列*
{
rear;
queue［rear］=queue［front］-rchild;
}
}
}
二叉树遍历算法的时间和空间复杂度分析，由于遍历二叉树算法中的基本操作是访问结点，则不论按哪种次序进行遍历，对含有n个结点的二叉树，其时间复杂度均为On。所需辅助空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为n，则空间复杂度也为On。3．3．3二叉树遍历算法的应用二叉树的遍历应用很广泛，本书主要通过几个例子来说明二叉树遍历的典型应用。1． 编写求二叉树结点个数的算法算法1： 在中序或先序、后序遍历算法中对遍历到的结点进行计数count应定义成全局变量，初值为0。
void InOrder BiTree *t *将二叉树t中的结点数累加到全局变量count中，count的初值0*
{
if t
{InOrder t-lchild ;
count=count 1;
InOrder t-rchild ;
}
}
算法2： 将一棵二叉树看成由树根、左子树和右子树3个部分组成，所以总的结点数是这3部分结点数之和，树根的结点数或者是1或者是0为空时，而求左右子树结点数的方法和求整棵二叉树结点数的方法相同，可用递归方法。
int Count BiTree *t
{
int lcount,rcount;
if t==NULL return 0;
lcount=Countt-lchild;
rcount=Countt-rchild;
return lcount rcount 1; }
2． 设计算法求二叉树的高度算法1： 使用全局变量。
void High BiTree *bt
{*求二叉树bt的高度并存储到全局变量h中，h初值为0*
int hl;
ifbt==NULL h=0;*bt为空时，高度为0*
else{
Highbt-lchild;*求左子树的高度并存储到全局变量h中*
hl=h;
Highbt-rchild;*求右子树的高度并存储到全局变量h中*
h=hlh? hl：h 1;*若二叉树不空，其高度应是其左右子树高度的最大值再加1*
}
}
算法2： 使用带指针形参。
void High BiTree *bt, int *h
{*求二叉树bt的高度并存储到h所指向的内存单元*
int hl, hr;
ifbt==NULL *h=0;*bt为空时，高度为0*
else{
Highbt-lchild,&hl;*求左子树的高度并存储到局部变量hl中*
Highbt-rchild,&hr;*求右子树的高度并存储到局部变量hr中*
*h=hlhr? hl：hr 1;*若二叉树不空，其高度应是其左右子树高度的最大值再加1*
}
}
算法3： 通过函数值返回结点数。
int High BiTree *bt
{*求二叉树bt的高度并通过函数值返回*
int hl,hr,h;
ifbt==NULL h=0;*bt为空时，高度为0*
else{
hl=Highbt-lchild;*求左子树的高度并暂时存储到局部变量hl中*
hr=Highbt-rchild;*求右子树的高度并暂时存储到局部变量hr中*
h=hlh? hl：h 1;*若二叉树不空，其高度应是其左右子树高度的最大值再加1*
}
return h；
}
3． 创建二叉树的二叉链表存储结构由二叉树的先序、中序、后序序列中的任何一个序列是不能唯一确定一棵二叉树的，原因是不能确定左右子树的大小或者说不知其子树结束的位置。针对这种情况，做如下处理。将二叉树中每个结点的空指针处再引出一个孩子结点，其值为特定值，如用0标识其指针为空。例如，要建立如图312所示的二叉树，其先序输入序列应该是ABD0G00CE00F00。根据二叉树的递归定义，先生成二叉树的根结点，将元素值赋值给结点的数据域，然后递归创建左子树和右子树。
void CreateBinTreeBiTree *T
{*以加入结点的先序序列输入，构造二叉链表*
char ch;
scanf"＼n%c",&ch;
if ch==''0'' *T=NULL; *读入0 时，将相应结点置空*
else {*T=BinTNode*mallocsizeofbnode; *生成结点空间*
*T-data=ch;
CreateBinTree&*T-lchild; *构造二叉树的左子树*
CreateBinTree&*T-rchild; *构造二叉树的右子树*
}
}
void InOrderOutBiTree *T
{*中序遍历输出二叉树T 的结点值*
if T
{InOrderOutT-lchild; *中序遍历二叉树的左子树*
printf"%3c",T-data; *访问结点的数据*
InOrderOutT-rchild; *中序遍历二叉树的右子树*
}
}
main
{
BiTree bt;
CreateBinTree&bt;
InOrderOutbt;
}
4． 查找数据元素下面的算法Searchbt，x实现在非空二叉树bt中查找数据元素x。若查找成功，则返回该结点的指针； 若查找失败，则返回空指针。
BiTree SearchBiTree *bt, int x
{*先序查找，在以bt为根的二叉树中值为x的结点是不是存在*
BiTree *temp;
ifbt==NULL return NULL;
ifx==bt-data return bt;
temp=searchbt-lchild, x;*在bt-lchild为根的二叉树中查找数据x*
iftemp!=NULL return temp;
else return searchbt-rchild, x; *在bt-rchild为根的二叉树中查找数据x*
}
5． 设计算法求二叉树每层结点的个数算法思想： 先序或者中序遍历时，都是从一个结点向它的左孩子或者右孩子移动，如果当前结点位于L层，则它的左孩子或者右孩子肯定是在L 1层。在遍历算法中给当前访问到的结点增设一个指示该结点所位于的层次变量L，设二叉树高度为H,定义一个全局数组num［1H］,初始值为0，num［i］表示第i层上的结点个数。
void Levcount BiTree *t, int L
{if t
{
Visit t-data; num［L］;
Levcount t-lchild, L 1;
Levcount t-rchild, L 1;
}
}
}
3．4树和森林树、 森林和二叉树本身都是树的一种，它们之间都可以相互转换，本节将讨论树和森林的存储结构，并建立森林与二叉树的对应关系。3．4．1树和森林的存储结构1. 树的存储结构
在大量的应用中，人们曾使用多种形式的存储结构来表示树。这里，介绍3种常用的链表结构，分别是双亲表示法、孩子表示法和孩子兄弟表示法。1） 双亲表示法由树的定义可知，树中根结点无双亲，其他任何一个结点都只有唯一的双亲。根据这一特性，可以以一组连续的空间存储树的结点，通过保存每个结点的双亲结点位置，表示树中结点之间的结构关系，树的这种存储方法称为双亲表示法。双亲表示法的存储结构定义可以描述为
#define MaxNodeNum 100 *树中结点的最大个数*
typedef struct {*结点结构*
DataType data;
intparent;
} Parentlist;
typedef struct { *树结构*
Parentlist elem［MaxNodeNum］;
int r,n;*双亲结点的位置和结点个数*
} ParentTree;
图313所示的是一棵树及其双亲表示的存储结构。图313中用parent域的值为-1表示该结点无双亲结点，即该结点是一个根结点。
图313树的双亲表示法
树的双亲表示法对于实现ParentT,x操作和RootT操作很方便，但若求某结点的孩子结点，即实现ChildT,x,i操作时，则需要查询整个数组。此外，这种存储方式不能反映各兄弟结点之间的关系，所以实现RightSiblingT,x操作也比较困难。实际中，如果需要实现这些操作，可在结点结构中增设存放第一个孩子的域和存放右兄弟的域，就能较方便地实现上述操作。2） 孩子表示法由于每个结点可能有多棵子树，可以考虑使用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点，这种方法称为多重链表表示法。不过树的每个结点的度，也就是它的孩子个数是不同的，所以可以设计两种方案来解决。方案1： 根据树的度d为每个结点设置d个指针域，多重链表中的结点是同构的。由于树中很多结点的度小于d，所以链表中有很多空链域，造成存储空间浪费。不难推出，在一棵有n个结点，度为d的树中必有nd-1 1个空链域。不过，若树的各结点度相差很小时，就意味着开辟的空间都利用了，这时缺点反而变成了优点。其结构如图314所示。
图314方案1结构图
方案2： 每个结点指针域的个数等于该结点的度，专门取一个位置来存储结点指针域的个数。在结点中设置degree域，指出结点的度。其结构如图315所示：
图315方案2结构图
这种方法克服了浪费空间的缺点，对空间的利用率很高，但是各个结点的链表是不相同的结构，加上要维护结点的度的数值，运算上就会带来时间的损耗。那么有没有更好的方法呢？既可以减少空指针的浪费，又能使结点结构相同。那就是用孩子表示法。具体办法是，把每个结点的孩子排列起来，以单链表做存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。针对图313所示的树，其孩子表示法如图316所示。
图316树的孩子表示法
树的孩子表示法使得查找已知结点的孩子结点非常容易。通过查找某结点的链表，可以找到该结点的每个孩子。但是查找双亲结点不方便，为此可以将双亲表示法与孩子表示法结合起来使用，图317就是将两者结合起来的带双亲的孩子链表。
图317带双亲的孩子链表
树的孩子表示法的类型定义如下：
#define MAXNODE 100 *树中结点的最大个数*
struct ChildNode{*孩子结点*
int childcode;
struct ChildNode *nextchild;
}
typedef struct {
elemtype data;
struct ChildNode *firstchild; *孩子链表头指针*
}NodeType;
NodeType t［MAXNODE］;
3） 孩子兄弟表示法这种表示法又称为二叉树表示法，或二叉链表表示法。即以二叉链表作为树的存储结构，链表中结点的两个域分别指向该结点的第一个孩子和下一个兄弟，分别命名为firstchild和nextsibling域。树的孩子兄弟表示法的类型定义如下：
typedef struct tnode {
DataType data;
struct tnode *firstchild, *nextsibling;
} Tnode;
图313所示的树对应的孩子兄弟表示如图318。利用树的孩子兄弟链表这种存储结构便于实现各种树的操作。例如，找某结点的第i个孩子，则只要先从左指针域中找到第1个孩子结点，然后沿着孩子结点的nextsibling域连续走i-1步便可找到第i个孩子。如增加一个parent域，也能方便实现求双亲的操作。
图318树的孩子兄弟表示法
2. 森林的存储结构森林的存储方式也采用二叉链表的形式。森林实际上是多棵树结构的集合，而且在树的孩子兄弟表示法中表示每棵树的根结点的右指针必然为空。因此采用这样的方法，对于第N 1棵树将其根结点挂到表示第N棵树的根节点的右指针上即可。3．4．2树和森林与二叉树之间的转换
从树的孩子兄弟表示法可以看出，如果设定一定规则，就可以用二叉树结构表示树和森林。这样，对树的操作实现就可以借助二叉树存储，利用二叉树上的操作来实现。本节将讨论树和森林与二叉树之间的转换。1． 树与二叉树的相互转换1） 树转换为二叉树对于一棵无序树，树中结点的各孩子结点的次序无关紧要，而二叉树中结点的左、右孩子结点是有区别的。为避免发生混淆，约定树中每个结点的孩子结点按从左到右的次序编号。将一棵树转换成二叉树的方法是1 加线： 在兄弟之间加一连线。2 抹线： 对每个结点，除了其左孩子外，去除其与其余孩子之间的关系。3 旋转： 以树的根结点为轴心，将整树顺时针转45。图319展示了树转换为二叉树的过程。经过这种方法转换后，对应的二叉树是唯一的。
图319树转为二叉树的过程
由图319的转换可以看出，二叉树中，左分支上的各结点在原来的树中是父子关系，而右分支上的各结点在原来的树中是兄弟关系。由于树的根结点没有兄弟，所以变换后二叉树的根结点的右孩子必为空。2） 二叉树还原为树二叉树转换为树，就是将树转换为二叉树的逆过程。树转换为二叉树，二叉树的根结点一定没有右孩子，对于一棵缺少右子树的二叉树也有唯一的一棵树与之对应。将一棵二叉树还原为树的的步骤如下：1 加线： 若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来。2 抹线： 抹掉原二叉树中双亲与右孩子之间的连线。3 调整： 将结点按层次排列，形成树结构。图320展示了二叉树还原为树的过程。一棵没有右子树的二叉树经过这种方法还原后，对应的树也是唯一的。
图320二叉树还原成树的过程
2． 森林与二叉树的相互转换1） 森林转换为二叉树由森林的概念可知，森林是由若干棵树组成的集合，树可以转换为二叉树，那么森林也可以转换为二叉树。如果将森林中的每棵树转换为对应的二叉树，则再将这些二叉树按照规则转换为一棵二叉树，就实现了森林到二叉树的转换。森林转换为对应的二叉树的步骤如下：1 将森林中各棵树分别转换成二叉树。（2） 第1棵二叉树不动，从第2棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。
图321森林转化为二叉树的过程
2） 二叉树还原为森林将二叉树还原为森林的方法不难构造，具体还原过程如下：1 抹线： 将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树。2 还原： 将孤立的二叉树还原成树。3 调整： 将还原后的树的根结点排列成一排。图322展示了二叉树还原为森林的过程。一棵具有左子树和右子树的二叉树经过这种方法还原后，对应的森林是唯一的。
图322二叉树还原为森林的过程
3．4．3树和森林的遍历由树结构的定义可引出树的两种次序的遍历。一种是先根遍历树，即先访问树的根结点，然后依次先根遍历树的每棵子树； 另一种是后根遍历，即先依次后根遍历每棵子树，然后访问根结点。对图31的树进行先根遍历，可得到树的先根遍历序列为
ABDGHICEJF
若对此树进行后根遍历，则得到树的后根序列为
GHIDBJEFCA
按照森林和树相互递归的定义，可以推出森林的两种遍历方法。1． 先序遍历森林若森林非空，则可按下述规则遍历。1 访问森林中的第一棵树的根结点。2 先序遍历第一棵树中根结点的子树森林。3 先序遍历除去第一棵子树之后剩余的树构成的森林。2． 中序遍历森林若森林非空，则可按下述规则遍历。1 中序遍历森林中第一棵树中根结点的子树森林。2 访问第一棵子树的根结点。3 中序遍历除去第一棵子树之后剩余的树构成的森林。对图322中森林进行先序遍历，可得到森林的先序序列为
ABCDEFGHIJ
若对此森林进行中序遍历，则得到森林的中序序列为
BCDAFEHJIG
由3.4.2节森林与二叉树之间转换的规则可知，当森林转换成二叉树时，其第一棵树的子树森林转换成左子树，剩余树的森林转换为右子树，则上述森林的先序和中序遍历即为其对应的二叉树的先序和中序遍历。由此可见，当以二叉链表作为树的存储结构时，树的先根遍历和后根遍历可借用二叉树的先序遍历和中序遍历的算法来实现。
3．5二叉树的应用3．5．1哈夫曼树及其应用
哈夫曼树也称为最优二叉树。它是一种带权路径最短的树，应用非常广泛。本节主要介绍哈夫曼树的定义、哈夫曼编码及哈夫曼编码算法的实现。1． 哈夫曼树的定义先介绍几个基本概念和术语。一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。从根结点到该结点之间的路径长度与该结点的权的乘积称为结点的带权路径长度。树的带权路径长度Weighted Path Length of Tree，简记为WPL规定为所有叶子结点的带权路径长度之和：WPL=ni=1wi*li（31）其中n为叶子结点数目，wi为第i 个叶子结点的权值，li 为第i个叶子结点的路径长度。在一棵二叉树中，若树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。
【例31】有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树。由这4个叶子结点可以构造出形态不同的二叉树，如图323所示。
图323具有不同带权路径长度的二叉树
从带权路径长度最小，这一角度来看，完全二叉树不一定是最优二叉树。图323c树的WPL最小，此树就是哈夫曼树。由n个带权叶子结点所构成的二叉树中，满二叉树和完全二叉树不一定是最优二叉树。权值越大的结点离根结点越近的二叉树才是最优二叉树。2． 哈夫曼树的建立根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。哈夫曼依据这一特点提出了一种构造最优二叉树的方法，其基本思想如下：（1） 根据给定的n个权值w1，w2，，wn构成n棵二叉树的森林F={T1，T2，，Tn}。其中，每棵二叉树Ti中都只有一个权值为wi的根结点，其左右子树均空。（2） 在森林F中选出两棵根结点权值最小的树当这样的树不止两棵树时，可以从中任选两棵，将这两棵树合并成一棵新树，为了保证新树仍是二叉树，需要增加一个新结点作为新树的根，并将所选的两棵树的根分别作为新根的左右孩子谁左，谁右无关紧要，将这两个孩子的权值之和作为新树根的权值。（3） 对新的森林F重复（2），直到森林F中只剩下一棵树为止。这棵树便是哈夫曼树。例如，假设给定一组权值{7, 5, 2, 4}，按照哈夫曼树构造的算法，对集合的权重构造哈夫曼树的过程如图324所示。
图324哈夫曼树的构造过程
构造哈夫曼树时，可以设置一个结构数组HuffNode保存哈夫曼树中各结点的信息。根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，数组元素的结构形式如图325所示。
图325数组元素的结构形式
其中，weight域保存结点的权值，lchild和rchild域分别保存该结点的左右孩子结点在数组HuffNode中的序号，从而建立起结点之间的关系。为了判定一个结点是否已加入到要建立的哈夫曼树中，可以通过当初parent的值为-1，当结点加入到树中时，该结点parent的值为其双亲结点在数组HuffNode中的序号，就不会是-1了。构造哈夫曼树时，首先将由n个权值形成的n个叶子结点存放到数组HuffNode的前n个分量中，然后根据前面介绍的哈夫曼方法的基本思想，不断将两个小子树合并为一个较大的子树，每次构成的新子树的根结点顺序放在HuffNode数组中的前n个分量的后面。哈夫曼树的构造算法如下：
#define MAXVALUE 10000 *定义最大权值*
#define MAXLEAF 30 *定义哈夫曼树中叶子结点的最大个数*
#define MAXNODE MAXLEAF *2-1 *定义哈夫曼树中结点的最大个数*
typedef struct
{
int weight;
int parent;
int lchild;
int rchild;
}HNode, HuffmanTree［MAXNODE］;
void CrtHuffmanTreeHuffmanTree ht, int w［］, int n*数组w［］传递n个权值*
{
int i,j,m1,m2,x1,x2;
fori=0;i2*n-1;i{*ht初始化*
ht［i］.weight=0;
ht［i］.parent=-1;
ht［i］.lchild=-1;
ht［i］.rchild=-1;
}
fori=0;in;i ht［i］.weight=w［i］; *赋予n个叶子结点的权值*
fori=0;in-1;i *构造哈夫曼树*
{
m1=m2=MAXVALUE;
x1=x2=0;
forj=0;jn i;j *寻找权值最小和次小的两棵树*
{
ifht［j］.weightm1&&ht［j］.parent==-1
{
m2=m1; x2=x1; x1=j;
m1=ht［j］.weight;
}
else if htj,weightm2&&ht［j］.parent==-1
{
m2=ht［j］.weight;
x2=j;
}
}
*将两棵子树合并成一棵子树*
ht［x1］.parent=n i; ht［x2］.parent=n i;
ht［n i］.weight=ht［x1］.weight ht［x2］.lweight;
ht［n i］.lchild=x1; ht［n i］.rchild=x2;
}
}
3． 哈夫曼编码哈夫曼编码常应用在数据通信中，数据传送时，需要将字符转换为二进制的编码串。例如，假设传送的电文是ABDAACDA,电文中有A、B、C、D 4种字符，如果规定A、B、C、D的编码分别为00、01、10、11，则上面的电文代码为0001110000101100，总共16个二进制数。传送电文时，总是希望电文代码尽可能短，采用哈夫曼编码构造的电文的总长最短。通信中，可以采用0、1的不同排列来表示不同的字符，称为二进制编码。若每个字符出现的频率不同，可以采用不等长的二进制编码，频率较大的采用位数较少的编码，频率较小的字符采用位数较多的编码，这样可以使字符的整体编码长度最小，这就是最小冗余编码的问题。哈夫曼编码就是一种不等长的二进制编码，且哈夫曼树是一种最优二叉树，它的编码也是一种最优编码。利用哈夫曼树编码来构造编码方案，就是哈夫曼树的典型应用。具体做法如下：设需要编码的字符集合为D={d1，d2，，dn}，它们在电文中出现的次数或频率集合为{w1，w2，，wn}，以d1，d2，，dn作为叶结点，w1，w2，，wn作为它们的权值，构造一棵哈夫曼树，规定哈夫曼树中的左分支代表0，右分支代表1，则从根结点到每个叶结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，称之为哈夫曼编码。这样的哈夫曼树亦成为哈夫曼编码树。
按照以上构造方法，字符集合为{A,B,C,D}，各个字符相应的出现次数为{4,1,1,2}，这些字符作为叶子结点构成的哈夫曼树如图326所示，
图326哈夫曼编码树
字符A的编码为0，字符B的编码为110，字符C的编码为111，字符D的编码为10。
哈夫曼编码树中，树的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和，也就是报文的代码总长，所以采用哈夫曼树的编码是一种能够使报文代码总长最短的不定长编码。设计不等长编码时，必须使任何一个字符的编码都不是另外一个字符编码的前缀。例如，字符A的编码为10，字符B的编码是100，则字符A的编码就称为字符B编码的前缀。如果一个代码是10010，在进行译码时，无法确定是将前两位译为A，还是将前三位译为B。但是在利用哈夫曼树进行编码时，每个编码是叶子结点的编码，一个字符是不会出现在另一个字符前面的，也就不会出现一个字符的编码是另一个字符编码的前缀编码。任何一个字符的编码都不是另一个字符编码的前缀,这种编码称为前缀编码。哈夫曼编码的算法实现如下：前面已经给出了哈夫曼树的构造算法，为实现哈夫曼树，自然需要定义一个编码表的存储结构。定义如下：
typedef struct codenode
{ char ch; *存放要表示的符号*
char *code; *存放相应的代码*
}CodeNode
typedef CodeNode HuffmanCode［MAXLEAF］;
哈夫曼编码的算法思路是在哈夫曼树中，从每个叶子结点开始，一直往上搜索，判断该结点是其双亲结点的左孩子还是右孩子，若是左孩子，则相应位置上的代码为0，否则是1，直至搜索到根结点为止。算法如下：
void CrtHuffmanCodeHuffmanTree ht,HuffmanCode hc,int n
*从叶子结点到根，逆向搜索求每个叶子结点对应符号的哈夫曼编码*
{
char *cd;
int i,c,p,start;
cd=mallocn*sizeofchar;*为当前工作区分配空间*
cd［n-1］=＼0;*从右到左逐位存放编码，首先存放结束符*
fori=1;i=n;i*求n个叶子结点对应的哈夫曼编码*
{
start=n-1; *编码存放的起始位置*
c=i;p=ht［i］.parent;*从叶子结点开始往上搜索*
whilep!=0
{
- - start;
ifht［p］.lchild==c cd［start］=0 *左分支标0*
else cd［start］=1;*右分支标1*
c=p; p=ht［p］.parent;*向上倒推*
}
hc［i］=mallocn-start*sizeofchar; *为第i个编码分配空间*
scanf"%c",&hc［i］.ch;*输入相应待编码字符*
strcpyhc［i］,&ch［start］;*将工作区中编码复制到编码表中*
}
freecd;
}
3．5．2二叉排序树
图327二叉排序树
二叉排序树又称二叉查找树、二叉搜索树。它或者是一棵空树。或者是具有下列性质的二叉树： 若左子树不空，则左子树上所有结点的值均小于它根结点的值； 若右子树不空，则右子树上所有结点的值均大于等于它根结点的值； 左、右子树也分别为二叉排序树。二叉排序树的相关算法参见4.9.1节。
例如，图327所示的二叉排序树。
由给定的数据序列生成二叉排序树的过程是在二叉排序树上插入结点的过程，对于一个数据序列R1，R2，，Rn：（1） 设R1为二叉排序树的根。（2） 若R249，且7665，则应插入成为65的右子树根结点。以此类推，最后得到如图328i所示的二叉排序树。
图328由关键字生序列生成二叉排序树的过程
3．6图图Graph是一种比线性表和树更为复杂的非线性数据结构。图中元素的关系既不像线性表中的元素至多只有一个直接前趋和一个直接后继，也不像树形结构中的元素具有明显的层次关系。图中元素之间的关系可以是任意的，每个元素也称为顶点可以具有多个直接前趋和后继，所以图可以表达数据元素之间广泛存在着的更为复杂的关系。图在语言学、逻辑学、数学、物理、化学、通信和计算机科学等领域中得到了广泛的应用。3．6．1图的基本概念1. 图的定义
图G是一种非线性数据结构，它由两个集合VG和EG组成，形式上记为G=V, E。其中，VG是顶点Vertex的非空有限集合，EG是VG中任意两个顶点之间的关系集合，又称为边Edge的有限集合。当G中的每条边有方向时，称G为有向图。有向边使用一对尖括号将两个顶点组成的有序对括起来，记为。有向边又称为弧，因此弧的起始顶点就称为弧尾，终止顶点称为弧头。图329给出了一个有向图的示例，该图的顶点集和边集分别为
VG1={V1, V2, V3, V4}
EG1={, , , }
图329有向图示例
图330无向图示例
若G中的每条边是无方向时，称G为无向图。这时，两个顶点之间最多只存在一条边。无向图的一条边使用一对圆括号 将两个顶点组成的无序对括起来，记为顶点1，顶点2或顶点2，顶点1。图330给出了一个无向图的示例。该图的顶点集和边集分别为
VG2={V1, V2, V3, V4}
EG2={V1, V2, V1, V3, V1, V4, V3, V4}={V2, V1, V3, V1, V4, V1, V4, V3}
2. 基本术语1） 完全图、稀疏图和稠密图下面的讨论中，不考虑顶点到其自身的边，也不允许一条边在图中重复出现。在以上两条约束下，边和顶点之间存在以下关系。1 对一个无向图，它的顶点数n和边数e满足0enn-12的关系。如果e=nn-12，则该无向图称为完全无向图。2 对一个有向图，它的顶点数n和边数e满足0enn-1的关系。如果e=nn-1，则称该有向图为完全有向图。3 如果eEG，则称顶点Vi邻接到Vj或Vj邻接自Vi，并称弧关联于顶点Vi和Vj或称弧与顶点Vi和Vj相关联。例如，在图329中的顶点1邻接到顶点2和顶点3，或称顶点2或顶点3邻接自顶点1，而顶点4邻接到顶点1，或称顶点1邻接自顶点4。4） 度、入度和出度无向图中关联于某一顶点Vi的边的数目称为Vi的度，记为DVi。例如，图330中的顶点1的度为3。有向图中，把以顶点Vi为终点的边的数目称为Vi的入度，记为IDVi； 把以顶点Vi为起点的边的数目称为Vi的出度，记为ODVi； 把顶点Vi的度定义为该顶点的入度和出度之和。例如，图329中顶点1的入度为1，出度为2，度为3。
如果图G中有n个顶点，e条边，且每个顶点的度为DVi1in，则存在以下关系：
图332网（带权图）
e=ni=1Dvi2325） 权与网一个图中，如果图的边或弧具有一个与它相关的数时，这个数就称为该边或弧的权，这个数常用来表示一个顶点到另一个顶点的距离或耗费。如果图中的每一条边都具有权时，这个带权图称为网络，简称为网，如图332所示。
6） 路径与回路一个图中，若从顶点V1出发，沿着一些边经过顶点V1, V2, , Vn-1到达顶点Vn，则称顶点序列V1, V2, , Vn-1, Vn为从V1到Vn的一条路径。例如，图330中V4, V3, V1是一条路径。而在图329中，V4, V3, V1就不是一条路径。将无权图沿路径所经过的边数，称为该路径的长度。而对有权图，取沿路径各边的权之和作为此路径的长度。图331所示的G3中顶点1到顶点3的路径长度为2。若路径中的顶点不重复出现，则这条路径称为简单路径。起点和终点相同并且路径长度不小于2的简单路径称为简单回路或简单环。例如，图330的无向图中顶点序列V4, V3, V1是一条简单路径，而V4, V3, V1, V4是一个简单环。7） 图的连通性一个有向图中，若存在一个顶点V，从该顶点有路径可到达图中其他所有顶点，则称这个有向图为有根图，V称为该图的根。例如，图329就是一个有根图，该图的根是V1、V3和V4。无向图G中，若顶点Vi和Vjij有路径相通，则称Vi和Vj连通。如果VG中的任意两个顶点都连通，则称G是连通图，否则为非连通图，如图333 a 所示。无向图G中的极大连通子图称为G的连通分量。对任何连通图而言，连通分量就是其自身，对非连通图可有多个连通分量，如图333 b所示。有向图G中，若从Vi到Vjij、从Vj到Vi都存在路径，则称Vi和Vj强连通。若有向图VG中的任意两个顶点都是强连通的，则称该图为强连通图。有向图中的极大连通子图称作有向图的强连通分量。例如，图329中的顶点V1、V3和V4是强连通的，但该有向图不是一个强连通图。
图333无向图及其连通分量
3.6.2图的存储方法由于图的结构复杂，任意两个顶点之间都可能存在联系，所以无法以数据元素在存储区中的物理位置来表示元素之间的关系，但仍可以借助一个二维数组中各单元的数据取值或用多重链表来表示元素间的关系。无论采用什么存储方法，都需要存储图中各顶点本身的信息和存储顶点与顶点之间的关系。事先对图中的每个顶点进行顺序编号以后，各个顶点的数据信息即可保存在一个一维数组中，且顶点的编号与一维数组下标一一对应。因此，研究图的存储方法，主要是解决如何实现各个顶点之间关系的表示问题。图的存储方法很多，常用的有邻接矩阵存储方法、邻接表存储方法、十字链表存储方法和多重邻接表存储方法。选择存储方法的依据取决于具体的应用和所要施加的运算。这里仅介绍邻接矩阵存储方法和邻接表存储方法。1. 邻接矩阵存储方法根据图的定义可知，一个图的逻辑结构分两部分，一部分是组成图的顶点的集合； 另一部分是顶点之间的联系，即边或弧的集合。因此，计算机中存储图需要解决这两部分的存储表示。邻接矩阵存储方法中，使用一个一维数组来存放图中每个顶点的数据信息，而利用一个二维数组又称为邻接矩阵来表示图中各顶点之间的关系。对一个有n个顶点的图G而言，将使用一个nn的矩阵来表示其顶点间的关系，矩阵的每一行和每一列都顺序对应每一个顶点。矩阵中的元素A［i, j］可按以下规则取值。A［i, j］=1,若vi,vj或EG0，若vi,vj或EG0i,jn－133
一般情况下，大家不关心图中顶点的情况，若顶点编号为1～vtxnum，设弧上或边上无权值，则使用C语言可以将图的存储结构简化为一个二维数组，如下所示。
intadjmatrix［vtxnum］［vtxnum］;
如图330中的G2和图331中的G3，其邻接矩阵分别如图334中A1、A2所示。
图334图G2和G3的邻接矩阵
借助于邻接矩阵，可以很容易地求出图中顶点的度。从上例可以看出，邻接矩阵有如下结论。1 无向图的邻接矩阵是对称的，而有向图的邻接矩阵不一定对称。对无向图可考虑只存下三角或上三角元素。2对于无向图，邻接矩阵第i行或第i列的元素之和是顶点Vi的度。3对于有向图，邻接矩阵第i行元素之和为顶点Vi的出度； 第i列的元素之和为顶点Vi的入度。对于网络，邻接矩阵元素A［i, j］可按以下规则取值。A［i, j］=Wij,若vi,vj或EG
0或,若vi,vj或vi,vjEG0i,jn－134其中,Wij是边Vi, Vj或弧上的权值。当一个图用邻接矩阵表示时，使用C语言编写算法可用以下数据类型说明。
#define n* 图的顶点数 *
#define e* 图的边数*
typedef char vextype;* 顶点的数据类型 *
typedef float adjtype;* 顶点权值的数据类型 *
typedef struct {
vextype vexs［n］;* 顶点数组 *
adjtype arcs［n］［n］;* 邻接矩阵 *
} graph;
下面给出了一个无向网络邻接矩阵利用上述类型说明的建立算法。
CREATGRAPHgraph *g
{* 建立无向网络 *
int i, j, k;
float w;
fori=0; in; i
g-vexs［i］=getchar ;* 读入顶点信息，建立顶点表 *
fori=0; in; i
forj=0; jn; j
g-arcs［i］［j］=0;* 邻接矩阵初始化 *
fork=0; ke; k {
scanf"%d%d%f", &i, &j, &w;* 读入边Vi, Vj上的权w *
g-arcs［i］［j］=w;* 写入邻接矩阵 *
g-arcs［j］［i］=w;}
}
如果要建立无向图，可在以上算法中改变w的类型，并使输入值为1即可； 如果要建立有向网络，只需将写入矩阵的两个语句中的后一个语句去除即可。以上算法中，如果邻接矩阵是一个稀疏矩阵，则存在存储空间浪费现象。该算法的执行时间是On n2 e。通常e*e为图中边数的最大可能值*
typedef char vextype;* 定义顶点数据信息类型 *
struct arcnode {* 邻接链表结点 *
int adjvex; * 邻接点域 *
float data; * 权值无权图不含此项 *
struct arcnode *nextarc; * 链域 *
};
typedef struct arcnode ARCNODE;
struct headnode {
vextype vexdata; * 顶点域 *
ARCNODE *firstarc; * 指针域 *
}adjlist［VTXUNM］; * 顶点表 *
对于无向图，Vi的邻接链表中每个结点都对应与Vi相关联的一条边，第i个单链表的结点个数就是此结点的度，所以将无向图的邻接链表称为边表。对于有向图，Vi的邻接链表中每个结点都对应于以Vi为起始点射出的一条边，其邻接表中第i个单链表的结点个数就是此结点的出度，所以有向图的邻接链表也称为出边表。有向图还有一种逆邻接表表示法，这种方法的Vi邻接链表中的每个结点对应于以Vi为终点的一条边，其邻接表中第i个单链表的结点个数就是此结点的入度，因而称这种邻接链表为入边表。对于图335a的有向图和图336a的无向图，其邻接表存储结构分别如图335b和图336b所示。
图335有向带权图及其邻接表
图336无向图及其邻接表
邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点，但要判定任意两个顶点Vi和Vj之间是否有边或弧相连，则需搜索第i个或第j个链表，因此不及邻接矩阵方便。无论是无向图还是有向图，其邻接表的建立都比较简单，下面给出无向图邻接表的建立算法。
CREATADJLISTstruct headnode ga［ ］
{* 建立无向图的邻接表 *
int i, j, k;
ARCNODE *s;
fori=0; iVTXUNM; i
{
ga［i］. vexdata = getchar ;* 读入顶点信息和边表头指针初始化 *
ga［i］. firstarc = NULL;}
fork=0; kETXUNM; k
{* 建立边表 *
scanf"%d%d", &i, &j;* 读入边Vi, Vj的顶点序号 *
s=mallocsizeofARCNODE;* 生成邻接点序号为j的边表结点*s *
s-adjvex=j;
s- nextarc =ga［i］.firstarc;
ga［i］.firstarc =s;* 将*s插入顶点Vi的边表头部 *
s=mallocsizeofARCNODE;* 生成邻接点序号为i的边表结点*s *
s-adjvex=i;
s- nextarc =ga［j］.firstarc;
ga［j］.firstarc =s;}* 将*s插入顶点Vj的边表头部 *
}
如果要建立有向图的邻接表，则只需去除上述算法中生成邻接点序号为i的边表结点*s部分，仅仅保留生成邻接点序号为j的边表结点*s那一段语句组即可。若要建立网络的邻接表，只要在边表的每个结点中增加一个存储边上权值的数据域即可。该算法的执行时间是On e。邻接矩阵和邻接表是图中最常用的存储结构，它们各有所长，具体体现在以下几点：1 一个图的邻接矩阵表示是唯一的，而其邻接表表示不唯一，这是因为邻接链表中的结点的链接次序取决于建立邻接表的算法和边的输入次序。2 邻接矩阵表示中判定Vi, Vj或是否是图中的一条边，只需判定矩阵中的第i行第j列的元素是否为零即可。而在邻接表中，需要扫描Vi对应的邻接链表，最坏情况下需要的执行时间为On。3 求图中边的数目时，使用邻接矩阵必须检测完整个矩阵之后才能确定，所消耗的时间为On2； 而在邻接表中，只需对每个边表中的结点个数计数便可确定。当e*n为图中顶点个数的最大可能值*
typedef char vextype;* 定义顶点数据信息类型 *
struct arcnode {
int adjvex;
float data;
struct arcnode *nextarc;
};
typedef struct arcnode ARCNODE;
struct headnode {
vextype vexdata;
ARCNODE *firstarc;
};
struct headnode G［VTXUNM 1］;
int visited［VTXUNM 1］;
void DFSLstruct headnode G［］, int v {
ARCNODE *p;
printf''''%c-'''', G［v］.vexdata;
visited［v］=1;
p=G［v］.firstarc;
while p!=NULL {* 当邻接点存在时*
if visited［p-adjvex］==0
DFSLG, p-adjvex;
p=p-nextarc;* 找下一邻接点*
}
}
void traverstruct headnode G［］ {
int v;
forv=1;v= VTXUNM;v
visited［v］=0;
forv=1; v= VTXUNM;v
ifvisited［v］==0DFSLG, v;
}
如果采用深度优先搜索的非递归算法DFSL，则程序如下：
#define VTXUNM n
void traver_ DFSLstruct headnode G［］,int v {
int stack［VTXUNM］;
int top=-1;
int i;
ARCNODE *p;
printf''''%c-'''', G［v］.vexdata;
visited［v］=1;
top;
stack［top］=v;*访问过的顶点进栈*
p=G［v］.firstarc;
while top!= -1||p!=NULL {
whilep!=NULL {
if visited［p-adjvex］==1
p=p-nextarc;
else {
printf''''%c-'''', G［p-adjvex］.vexdata;
visited［p-adjvex］=1;
top;
stack［top］=p-adjvex;
p=G［p-adjvex］.firstarc;
}
}
iftop!= -1 {
v=stack［top］;
top--;
p=G［v］.firstarc;
p=p-nextarc;
}
}
}
因为搜索n个顶点的所有邻接点需要对边表各结点扫描一遍，而边表结点的数目为2e，所以算法的时间复杂度为O2e n，空间复杂度为On。选择邻接矩阵作为图的存储结构时，图337a所示的连通图G的邻接矩阵表示如图337c所示，其深度优先搜索遍历算法DFSA描述如下：
#define VTXUNM n*n为图中顶点个数的最大可能值*
typedef char vextype;* 顶点的数据类型 *
typedef int adjtype;* 顶点权值的数据类型 *
typedef struct {
vextype vexs［VTXUNM］;* 顶点数组 *
adjtype arcs［VTXUNM］［VTXUNM］;* 邻接矩阵 *
} graph;
graph g; * g为全局变量 *
int visited［VTXUNM］;
void DFSA int i {* 从Vi出发深度优先搜索图g，g用邻接矩阵表示 *
int j;
printf"node： %c＼n", g.vexs［i］;* 访问出发点Vi *
visited［i］=1;* 标记Vi已被访问 *
forj=0; jn; j* 依次搜索Vi的邻接点 *
if g.arcs［i］［j］==1&&visited［j］==0
DFSAj; * 若Vi的邻接点Vj未被访问过，则从Vj出发进行深度优先搜索遍历 *
}* DFSA *
上述算法中，每进行一次DFSAi的调用，for循环中v的变化范围都是0~n-1，而DFSAi要被调用n次，所以算法的时间复杂度为On2。因为是递归调用，需要使用一个长度为n-1的工作栈和长度为n的辅助数组，所以算法的空间复杂度为On。2. 广度优先搜索遍历对于一个图，按广度优先搜索遍历先后顺序得到的顶点序列称为该图的广度优先搜索BFS, BreadthFirst Search遍历序列，简称为BFS序列。图的广度优先搜索遍历类似于树的按层次遍历。一个图的BFS序列不是唯一的，它与算法、图的存储结构和初始出发点有关。当确定了有多个邻接点时，按邻接点的序号从小到大进行选择和指定初始出发点后，以邻接矩阵作为存储结构得到的BFS序列是唯一的，而以邻接表作为存储结构得到的BFS序列并不唯一，它取决于邻接表中边表结点的链接次序。假设初始状态是图中所有顶点都未被访问，BFS方法从图中某一顶点V0出发，先访问V0，然后访问V0的各个未被访问过的邻接点，再分别从这些邻接点出发广度优先搜索遍历图，以此类推，直至图中所有已被访问的顶点的邻接点都被访问到。如果是非连通图，则选择一个未曾被访问的顶点作为起始点，重复以上过程，直到图中所有顶点都被访问为止。具体遍历步骤如下：1访问V0。2从V0出发，依次访问V0的未被访问过的邻接点V1，V2，，Vt。然后依次从V1，V2，，Vt出发，访问各自未被访问过的邻接点。3重复步骤2，直到所有顶点的邻接点均被访问过为止。在这种方法的遍历过程中，先被访问的顶点，其邻接点也先被访问，具有先进先出的特性，实现算法时，使用一个队列来保存每次已访问过的顶点，然后将队头顶点出列，去访问与它邻接的所有顶点，重复上述过程，直至队空。为了避免重复访问一个顶点，使用一个辅助数组visited［n］来标记顶点的访问情况。针对图337所示的连通图G、邻接表及其邻接矩阵存储结构表示，假设从顶点V1出发，按广度优先搜索法先访问V1，然后访问V1的邻接点V2和V3，再依次访问V2和V3的未被访问的邻接点V4、V5、V6及V7，最后访问V4的邻接点V8。遍历序列描述如下：V0V1V2V3V4V5V6V7下面给出以邻接矩阵为存储结构时的广度优先搜索遍历算法BFSA。
#define VTXUNM n
graph g; * g为全局变量 *
int visited［VTXUNM］;
void BFSAint k
{* 从Vk出发广度优先搜索遍历图g，g用邻接矩阵表示 *
int queue［VTXUNM］;
int rear=VTXUNM-1; front=VTXUNM-1;* queue置为空队 *
int i, j;
printf"%c＼n", g.vexs［k］;* 访问出发点 Vk *
visited［k］=1;* 标记Vk已被访问 *
rear;
queue［rear］=k;* 访问过的顶点序号入队 *
whilefront!=rear
{* 队非空时执行下列操作 *
front;
i=queue［front］* 队头元素序号出队 *
forj=0; jn; j
ifg.arcs［i］［j］==1&&visited［j］!=1
{
printf"%c＼n", g.vexs［j］;* 访问Vi未被访问的邻接点Vj *
visited［j］=1;
rear;
queue［rear］=j;* 访问过的顶点入队 *
}
}
}* BFSA *
当选择邻接表作为图的存储结构时，图337a所示的连通图G的广度优先搜索遍历算法BFSL描述如下：
#define VTXUNM n
void BFSLstruct headnode G［］, int v
struct headnode G［VIXUNM 1］;
int Visited［VIXUNM 1］;
{
int queue［VTXUNM］;
int rear=-1; front=-1; * queue置为空队 *
int i;
ARCNODE *p;
printf''''%d-'''', G［v］.vexdata;
visited［v］=1;
rear;
queue［rear］=v;*访问过的顶点进队列*
while rear!=front
{
front;
v=queue［front］;
p=G［v］.firstarc;
whilep!=NULL {
if visited［p-adjvex］==0 {
printf''''%d-'''', G［p-adjvex］.vexdata;
visited［p-adjvex］=1;
rear;
queue［rear］=p-adjvex;
}
p=p-nextarc;
}
}
}* BFSL *
对于有n个顶点和e条边的连通图，BFSA算法的while循环和for循环都需执行n次，所以BFSA算法的时间复杂度为On2，同时BFSA算法使用了两个长度均为n的队列和辅助标志数组，所以空间复杂度为On； BFSL算法的外while循环要执行n次，而内while循环执行次数总计是边表结点的总个数2e，所以BFSL算法的时间复杂度为On 2e； 同时，BFSL算法也使用了两个长度均为n的队列和辅助标志数组，所以空间复杂度为On。3.6.4图的应用1. 生成树和最小生成树
图论中，树是指一个无回路存在的连通图。一个连通图G的生成树指的是一个包含了G的所有顶点的树。对于一个有n个顶点的连通图G，其生成树包含了n-1条边，从而生成树是G的一个极小连通的子图。所谓极小指该子图具有连通所需的最小边数，若去掉一条边，该子图就变成了非连通图； 若任意增加一条边，该子图就有回路产生。当给定一个无向连通图G后，可以从G的任意顶点出发，作一次深度优先搜索或广度优先搜索来访问G中的n个顶点，并将顺次访问的两个顶点之间的路径记录下来。这样，G中的n个顶点和从初始点出发顺次访问余下的n-1个顶点所经过的n-1条边就构成了G的极小连通子图，也就是G的一棵生成树。通常，将深度优先搜索得到的生成树称为深度优先搜索生成树，简称为DFS生成树； 而将广度优先搜索得到的生成树称为广度优先搜索生成树，简称为BFS生成树。对于前面所给的DFSA和BFSA算法，只需在if语句中的DFSA调用语句前或if语句中加入将vi, vj打印出来的语句，即构成相应的生成树算法。连通图的生成树不是唯一的，它取决于遍历方法和遍历的起始顶点。遍历方法确定后，从不同的顶点出发进行遍历，可以得到不同的生成树。对于非连通图，每个连通分量中的顶点集和遍历时走过的边一起构成一棵生成树，这些连通分量的生成树组成非连通图的生成森林。算法实现时，可通过多次调用由DFSA或BFSA构成的生成树算法求出非连通图中各连通分量对应的生成树，这些生成树构成了非连通图的生成森林。使用DFSA构成的生成树算法和BFSA构成的生成树算法，对图337a所示连通图G从顶点1开始进行遍历得到的深度优先生成树和广度优先生成树分别如图338a、b所示。
图338G从V1出发的两种生成树
图339所示为G图333a的深度优先生成森林，它由3棵深度优先生成树组成。
图339图G的深度优先生成森林
对一个连通网络构造生成树时，可以得到一个带权的生成树。把生成树各边的权值总和作为生成树的权，而具有最小权值的生成树构成了连通网络的最小生成树。也就是说，构造最小生成树就是在给定n个顶点所对应的权矩阵代价矩阵的条件下，给出代价最小的生成树。最小生成树的构造有实际应用价值。例如，要在n个城市之间建立通信网络，则连通n个城市只需n-1条线路。若以n个城市做图的顶点，n-1条线路做图的边，则该图的生成树就是可行的建造方案。而不同城市之间建立通信线路需要一定的花费相当于边上的权，所以对n个顶点的连通网可以建立许多不同的生成树，每棵生成树都可以是一个通信网，当然希望选择一个总耗费最小的生成树，即最小代价生成树。例如，图340a是个连通网，它的最小生成树如图340b所示。
图340连通网及其最小生成树
构造最小生成树的算法有多种，大多数算法都利用了最小生成树的一个性质，简称为MST性质。MST性质指出，假设G=V, E是一个连通网络，U是V中的一个真子集，若存在顶点uU和顶点vV-U的边u, v是一条具有最小权的边，则必存在G的一棵最小生成树包括这条边u, v。
图341含有u,v的回路
MST性质可用反证法加以证明，假设G中的任何一棵最小生成树T都不包含u, v，其中uU和vV-U。由于T是最小生成树，所以必然有一条边u, v其中uU和vV-U连接两个顶点集U和V-U。当u, v加入到T中时，T中必然存在一条包含了u, v的回路，如图341所示。如果在T中保留u, v，去掉u, v，则得到另一棵生成树T。因为u, v的权小于u, v的权，故T的权小于T的权，这与假设矛盾，因此MST性质得证。
下面介绍构造最小生成树的两种常用算法，Prim普里姆算法和Kruskal克鲁斯卡尔算法。1 Prim算法设GV, E是有n个顶点的连通网络，T=U, TE是要构造的生成树，初始时U={}，TE={}。首先，从V中取出一个顶点u0放入生成树的顶点集U中作为第一个顶点，此时T={u0}, {}； 然后从uU，vV-U的边u, v中找一条代价最小的边u*,v*，将其放入TE中并将v*放入U中，此时T={u0, v*}, {u0, v*}； 继续从uU, vV-U的边u, v中找一条代价最小的边u*, v*，将其放入TE中并将v*放入U中，直到U=V为止。这时T的TE中必有n-1条边，构成所要构造的最小生成树。显然，Prim算法的关键是如何找到连接U和V-U的最短边代价最小边来扩充T。设当前生成树T中已有k个顶点，则U和V-U中可能存在的边数最多为kn-k条，在如此多的边中寻找一条代价最小的边是困难的。注意在相邻的寻找最小代价的边的过程中，有些操作具有重复性，所以可通过将前一次寻找所得到的最小边存储起来，然后与新找到的边进行比较，如果新找到的边比原来已找到的边短，则用新找到的边代替原有的边，否则保持不变。为此设立以下边的存储结构。
typedef struct {
int fromvex, endvex;* 边的起点和终点 *
float length;* 边的权值 *
} edge;
edge T［n-1］;
float dist［n］［n］;* 连通网络的带权邻接矩阵 *
相应的Prim算法描述如下：
Primint i
{* i给出选取的第一个顶点的下标，最终结果保存在T［n-1］数组中 *
int j, k, m, v, min, max=100000;
float d;
edge e;
v=i;* 将选定顶点送入中间变量 *
forj=0; j=n-2; j
{* 构造第一个顶点 *
T［j］.fromvex=v;
ifj=v
{
T［j］.endvex=j 1;
T［j］.length=dist［v］［j 1］;}
else
{
T［j］.endvex=j;
T［j］.length=dist［v］［j］;}
}
fork=0; kn-1; k {* 求第k条边 *
min=max;
forj=k; jn-1; j* 找出最短的边并将最短边的下标记录在m中 *
ifT［j］.lengthmin {
min=T［j］.length;
m=j;}
e=T［m］; T［m］=T［k］; T［k］=e;* 将最短的边交换到T［k］单元 *
v=T［k］.endvex;* v中存放新找到的最短边在V-U中的顶点*
forj=k 1; jn-1; j
{* 修改所存储的最小边集 *
d=dist［v］［T［j］.endvex］;
ifdT［j］.length
{
T［j］.length=d;
T［j］.fromvex=v;}
}
}
} * Prim *
以上算法中构造第一个顶点所需的时间是On，求k条边的时间大约是n－2k=0n－2j=kO1 n－2j=k 1O12n－2k=0n－2j=kO135其中，O1表示某一正常数C，所以上述公式的时间复杂度是On2。下面结合图342所示的例子来观察算法（34）的工作过程。设选定的第一个顶点为2。首先将顶点值2写入T［i］.fromvex，并将其余顶点值写入相应的T［i］.endvex，然后从dist矩阵中取出第2行写入相应的T［i］.length中，得到图343a； 在该图中找出具有最小权值的边2, 1，将其交换到下标值为0的单元中，然后从dist矩阵中取出第1行的权值与相应的T［i］.length作比较，若取出的权值小于相应的T［i］.length，则进行替换，否则保持不变。由于边2, 0和2, 5的权值大于边1, 0和1, 5的权值，进行相应的替换可得到图343b； 在该图中找出具有最小权值的边2, 3，将其交换到下标值为1的单元中，然后从dist矩阵中取出第3行的权值与相应的T［i］.length作比较，可见边3, 4的权值小于边2, 4的权值，故进行相应的替换得到图343c； 在该图中找出具有最小权值的边1, 0，因其已在下标为2的单元中，故交换后仍然保持不变，然后从dist矩阵中取出第0行的权值与相应的T［i］.length作比较，可见边0, 4和0, 5的权值大于边3, 4和1, 5的权值，故不进行替换，得到图343d； 在该图中找出具有最小权值的边1, 5，将其交换到下标值为3的单元中，然后从dist矩阵中取出第5行的权值与相应的T［i］.length作比较； 因边5, 4的权值大于边3, 4的权值，故不替换，得到图343e。至此整个算法结束，得出了如图343f所示的最小生成树。
图342一个网络及其邻接矩阵
图343T数组变化情况及最小生成树
2 Kruskal算法Kruskal算法是从另一条途径来求网络的最小生成树。设G=V, E是一个有n个顶点的连通图，令最小生成树的初值状态为只有n个顶点而无任何边的非连通图T=V, {}，此时图中每个顶点自成一个连通分量。按照权值递增的顺序依次选择E中的边，若该边依附于T中两个不同的连通分量，则将此边加入TE中，否则舍去此边而选择下一条代价最小的边，直到T中所有顶点都在同一连通分量上为止。这时的T便是G的一棵最小生成树。对于图343所示的网络，按Kruskal算法构造最小生成树的过程如图344所示。
图344Kruskal算法构造最小生成树的过程
图344c中选择最短边2, 3时，也可以选择边1, 3，这样所构造出的最小生成树是不同的，即最小生成树的形式不唯一，但权值的总和相同。选择了最短边2, 3之后，在图344d中首先选择边1, 3，因其顶点在同一分量上，故舍去这条边而选择下一条代价最小的边。在图344f中也首先选择边3, 5，但因顶点3和5在同一个分量上，故舍去此边而选择下一条代价最小边3, 4。Kruskal算法中，每次都要选择所有边中最短的边，若用邻接矩阵实现，则每找一条最短的边就需要对整个邻接矩阵扫描一遍。这样，整个算法复杂度太高，而使用邻接表时，由于每条边都被连接两次，这也使寻找最短边的计算时间加倍，所以采用以下的存储结构来对图中的边进行表示。
typedef struct {
int fromvex, endvex;* 边的起点和终点 *
float length;* 边的权值 *
int sign;* 该边是否已选择过的标志信息 *
} edge;
edge T［e］;* e为图中的边数 *
int G［n］;* 判断该边的两个顶点是不是在同一个分量上的数组，n为顶点数 *
Kruskal算法中，如何判定所选择的边是否在同一个分量上，是整个算法的关键和难点。为此，设置一个G数组，利用G数组的每一个单元中存放一个顶点信息的特性，通过判断两个顶点对应单元的信息是否相同来判定所选择的边是否在同一个分量上。具体算法如下：
Kruskalint n, int e
{* n表示图中的顶点数目，e表示图中的边数目 *
int i, j, k, l, min, t;
fori=0; i=n-1; i* 数组G置初值 *
G［i］=i;
fori=0; i=e-1; i {* 输入边信息 *
scanf"%d%d%f", &T［i］.fromvex, &T［i］.endvex, &T［i］.length;
T［i］.sign=0;}
j=0;
whilejn-1
{
min=1000;
fori=0; i=e-1; i
{* 寻找最短边 *
ifT［i］.sign==0
ifT［i］.lengthmin
{
k=T［i］.fromvex;
l=T［i］.endvex;
T［i］.sign=l;}
ifG［k］==G［l］T［i］.sign=2;* 在同一分量上舍去 *
else {
j;
fort=0; tn; t* 将最短边的两个顶点并入同一分量 *
ifG［t］==lG［t］=k;}
}
}
}* Kruskal *
如果边的信息是按权值从小到大依次存储到T数组中，则Kruskal算法的时间复杂度约为Oe。一般情况下，Kruskal算法的时间复杂度约为Oelge，与网中的边数有关，故适合于求边稀疏网络的最小生成树； 而Prim算法的时间复杂度为On2，与网中的边数无关，适合于边稠密网络的最小生成树。2. 最短路径一个实际的交通网络在计算机中可用图的结构来表示。这类问题中经常考虑的问题有两个，一是两个顶点之间是否存在路径； 二是在有多条路径的条件下，哪条路径最短。由于交通网络中的运输路线往往有方向性，因此将以有向网络进行讨论，无向网络的情况与此相似。讨论中，习惯上称路径的开始点为源点Source，路径的最后一个顶点为终点Destination，而最短路径意味着沿路径的各边权值之和为最小。求最短路径时，为方便起见，规定邻接矩阵中某一顶点到自身的权值为0，即当i=j时，dist［i］［j］=0。最短路径问题的研究分为两种情况，一是从某个源点到其余各顶点的最短路径； 二是每一对顶点之间的最短路径。1 从某个源点到其余各顶点的最短路径迪杰斯特拉Dijkstra通过对大量的图中某个源点到其余顶点的最短路径的顶点构成集合和路径长度之间关系的研究发现，若按长度递增的次序来产生源点到其余顶点的最短路径，则当前正要生成的最短路径除终点外，其余顶点的最短路径已生成，即设A为源点，U为已求得的最短路径的终点的集合初态时为空集，则下一条长度较长的最短路径设它的终点为X或者是弧A, X或者是中间只经过U集合中的顶点，最后到达X的路径。例如，在图345中要生成从F点到其他顶点的最短路径。首先应找到最短的路径FB，然后找到最短的路径FBC。这里除终点C以外，其余顶点的最短路径FB已生成。迪杰斯特拉提出的按路径长度递增次序来产生源点到各顶点的最短路径的算法思想是，对有n个顶点的有向连通网络G=V, E，首先从V中取出源点u0放入最短路径顶点集合U中，这时的最短路径网络S={u0}, {}; 然后从uU和vV－U中找一条代价最小的边u*, v*加入到S中,此时S={u0, v*}, {u0, v*}。每往U中增加一个顶点，都需要对V－U中各顶点的权值进行一次修正。如果加进v*作为中间顶点，使得从u0到其他属于V－U的顶点vi的路径比不加v*时最短，则修改u0到vi的权值，即以u0, v*的权值加上v*, vi 的权值来代替原u0, vi 的权值，否则不修改u0到vi的权值。接着再从权值修正后的V－U中选择最短的边加入S中，如此反复，直到U=V为止。
图345有向网络G和F到其他顶点的最短距离
图346Dijkstra算法求最短路径示例
对图345中的有向网络按以上算法思想处理，所求得的从源点F到其余顶点的最短路径的过程如图346所示。其中，单圆圈表示U中的顶点，而双圆圈表示V－U中的顶点。连接U中两个顶点的有向边用实线表示，连接U和V－U中两个顶点的有向边用虚线表示。圆圈旁的数字为源点到该顶点当前的距离值。初始时，S中只有一个源点F，它到V－U中各顶点的路径如图346a所示； 选择图346a中最小代价边F, B，同时由于路径F, A大于F, B, A和F, C大于F, B, C，进行相应调整可得到图346b； 选择图346b中的最小代价边B, C，同时由于F, B, A大于F, B, C, A，进行相应调整可得到图346c； 选择图346c中最小代价边C, A即可得到图346d； 选择图346d中最小代价边F, D 即可得到图346eD; 最后选择F, E即可得到图346f。计算机上实现此算法时，需要设置一个用于存放源点到其他顶点的最短距离数组D［n］，以便于从其中找出最短路径; 因为不仅希望得到最短路径长度，而且也希望能给出最短路径具体经过那些顶点的信息，所以设置一个路径数组p［n］，其中p［i］表示从源点到达顶点i时，顶点i的前趋顶点； 为了防止对已经生成的最短路径进行重复操作，使用一个标识数组s［n］来记录最短路径生成情况，若s［i］=1表示源点到顶点i的最短路径已产生，而s［i］=0表示最短路径还未产生。当顶点A, B, C, D, E, F对应标号0, 1, 2, 3，4, 5时，具体算法描述如下：
float D［n］;
int p［n］, s［n］;
Dijkstraint v, float dist［］［］* 求源点v到其余顶点的最短路径及长度 *
{int i, j, k, v1, min, max=10000, pre;* Max中的值用以表示dist矩阵中的值 *
v1=v;
for i=0; in; i* 各数组进行初始化 *
{D［i］=dist［v1］［i］;
if D［i］ != max p［i］= v1 1;
elsep［i］=0;
s［i］=0;
}
s［v1］=1;* 将源点送U *
for i=0; in-1; i* 求源点到其余顶点的最短距离 *
{min=10001;* minmax,以保证值为的顶点也能加入U*
for j=0; jn-1; j
if !s［j］ &&D［j］min * 找出到源点具有最短距离的边 *
{min=D［j］;
k=j;
}
s［k］=1;* 将找到的顶点k送入U *
forj=0; jn; j
if !s［j］&&D［j］D［k］ dist［k］［j］ * 调整V－U中各顶点的距离值 *
{D［j］=D［k］ dist［k］［j］;
p［j］=k 1;* k是j的前趋 *
}
}* 所有顶点已扩充到U中 *
for i=0; in; i
{printf" %f %d ", D［i］, i;
pre=p［i］;
while pre!=0&&pre!=v 1
{printf " －%d ", pre-1;
pre=p［pre-1］;
}
printf" －%d ", v;
}
} * Dijkstra *
对图345中的有向网络G，以F点为源点，执行上述算法时,D、p、s数组的变化状况如表31所示。
表31Dijkstra算法动态执行情况
循环UkD［0］,, D［5］p［0］,, p［5］s［0］,, s［5］初始化{F}--24 5 max 25 max 06 6 0 6 0 60 0 0 0 0 11{F, B}123 5 12 25 max 02 6 2 6 0 60 1 0 0 0 12{F,B,C}221 5 12 25 max 03 6 2 6 0 60 1 1 0 0 13{F,B,C,A}021 5 12 25 max 03 6 2 6 0 61 1 1 0 0 14{F,B,C,A,D}321 5 12 25 max 03 6 2 6 0 61 1 1 1 0 15{F,B,C,A,D,E}421 5 12 25 max 03 6 2 6 0 61 1 1 1 1 1
打印输出的结果为
210 2 1 5
51 5
122 1 5
253 5
100004 5
05 5
Dijkstra算法的时间复杂度为On2，占用的辅助空间是On。
2 每一对顶点之间的最短路径求一个有n个顶点的有向网络G=V, E中的每一对顶点之间的最短路径，可以依次把有向网络的每个顶点作为源点，重复执行n次Dijkstra算法，从而得到每对顶点之间的最短路径。这种方法的时间复杂度为On3。弗洛伊德Floyd于1962年提出了解决这一问题的另一种算法，它形式比较简单，易于理解，而时间复杂度同样为On3。Floyd算法根据给定有向网络的邻接矩阵dist［n］［n］求顶点vi到顶点vj的最短路径。这一算法的基本思想是假设vi和vj之间存在一条路径，但这并不一定是最短路径，试着在vi和vj之间增加一个中间顶点vk。若增加vk后的路径vi, vk, vj 比vi, vj短，则以新的路径代替原路径，并且修改dist［i］［j］的值为新路径的权值； 若增加vk后的路径比vi, vj更长，则维持dist［i］［j］不变。在修改后的dist矩阵中，另选一个顶点作为中间顶点，重复以上操作，直到除vi和vj顶点的其余顶点都做过中间顶点为止。对初始的邻接矩阵dist［n］［n］，依次以顶点v1, v2, , vn为中间顶点实施以上操作时，将递推地产生出一个矩阵序列distk［n］［n］k=0, 1, 2, , n。这里初始邻接矩阵dist［n］［n］看作dist0［n］［n］，它给出每一对顶点之间的直接路径的权值; distk［n］［n］1kpath［n］［n］;* 路径矩阵 *
Floydfloat A［ ］［n］, dist［ ］［n］* A是路径长度矩阵, dist是有向网络G的带权邻接矩阵 *
{int i, j, k, next, max=10000;
for i=0; in; i* 设置A和path的初值 *
for j=0; jn; j
{if dist［i］［j］ !=max path［i］［j］=i 1;* i是j的前趋 *
else path［i］［j］=0;
A［i］［j］=dist［i］［j］;
}
for k=0; kn; k* 以0, 1, , n-1为中间顶点执行n次 *
for i=0; in; i
for j=0; jn; j
if A［i］［j］A［i］［k］ A［k］［j］
{A［i］［j］=A［i］［k］ A［k］［j］;* 修改路径长度 *
path［i］［j］=path［k］［j］;* 修改路径 *
}
for i=0; in; i* 输出所有顶点对i, j之间最短路径的长度和路径 *
for j=0; jn; j
{printf " %f%d ", A［i］［j］, j;
pre=path［i］［j］;
while pre!=0&&pre!=i 1 {
printf "-%d ", pre-1;
pre=path［i］［pre-1］;
}
printf "-%d＼n ", i;
}
} * Floyd *
对图345中的有向网络G执行以上算法，矩阵A和path的变化状况如下所示。A0=06810000180710901512040245250path0=110100222002303300004400005050660606
A1=0681807261091501512040245250path1=110100222102313300004400005050660606
A2=061381618072610915015251204023512250path2=112102
222102
313302
004400
005050
262606
A3=0613810000161607221091501525212712037131941902921512250path3=112102322302313302314402315352362606
A4=06138161607221091501525212712037131941902921512250
path4=112102322302313302314402315352362606
由于A4=A5=A6和path4=path5=path6，所以表中省略了A5, A6和path5, path6，打印输出的结果为
000
610
13210
830
1000040
16510
2535
1000045
055
3. AOV网与拓扑排序现实世界中，很多问题都由一系列的有序活动而构成。例如，一个工程项目的开展、一种产品的生产过程或大学期间所学专业的系列课程学习。这些活动可以是一个工程项目中的子工程、一种产品生产过程中的零部件生产或专业课程学习中的某一门课程。所有这些按一定顺序展开的活动，可以使用有向图表示。其中，顶点表示活动，顶点之间的有向边表示活动之间的先后关系，这种有向图称为顶点表示活动网络Activity On Vertex network，简称AOV网。AOV网中的顶点可以带有权值，该权值可以表示一项
图347表示课程先后关系的AOV网
活动完成所需要的时间或所需要投入的费用。AOV网中的有向边表示了活动之间的制约关系。例如，大学本科专业的学生必须学完一系列的课程才能毕业，其中一部分课程是基础课，无须先修其他课程便可学习； 另一部分课程则要求必须学完相关的基础先修课程后，才能进行学习。上述课程和课程之间关系的一个抽象表示示例如表32所示。该示例也可以用图347的AOV网表示，这里有向边＜Ci , Cj＞表示了课程Ci是课程Cj的先修课程。
表32专业课程设置及其关系
课程代号课程名称先修课程课程代号课程名称先修课程C1课程1无C7课程7C3,C5C2课程2C1C8课程8C3,C6C3课程3C1,C2C9课程9无
C4课程4C1C10课程10C9
续表
课程代号课程名称先修课程课程代号课程名称先修课程C5课程5C3,C4C11课程11C9C6课程6C11C12课程12C1,C9,C10
当限制各个活动只能串行进行时，如果可以将AOV网中的所有顶点排列成一个线性序列vi1, vi2, , vin； 并且这个序列同时满足如果在AOV网中从顶点vi到顶点vj存在一条路径，则在线性序列中vi必在vj之前，就称这个线性序列为拓扑序列。把对AOV网构造拓扑序列的操作称为拓扑排序。AOV网的拓扑排序序列给出了各个活动按顺序完成的一种可行方案，但并非任何AOV网的顶点都可排成拓扑序列。当AOV网中存在有向环时，就无法得到该网的拓扑序列。对于实际问题，AOV网中存在的有向环就意味着某些活动是以自己为先决条件，这显然不合理。例如，对于程序的数据流图，AOV网中存在环就意味着程序存在一个死循环。任何一个无环的AOV网中的所有顶点都可排列在一个拓扑序列里，拓扑排序的基本操作如表32所示。1从网中选择一个入度为0的顶点并且将其输出。2从网中删除此顶点及所有由它发出的边。3重复上述两步，直到网中再没有入度为0的顶点为止。以上操作会产生两种结果，一种结果是网中的全部顶点都被输出，整个拓扑排序完成； 另一种结果是网中顶点未被全部输出，剩余顶点的入度均不为0，此时说明网中存在有向环。用以上操作对图347的AOV网拓扑排序的过程如图348所示。这里得到了一种拓扑序列C1, C2 , C3, C4, C5, C7, C9, C10, C12, C11, C6, C8。
图348AOV网拓扑排序过程
从构造拓扑序列的过程中可以看出，许多情况下，入度为0的顶点可能有多个，这样就可以给出多种拓扑序列。若按所给出的拓扑序列顺序进行课程学习，可保证在学习任一门课程时，这门课程的先修课程已经学过。
拓扑排序可在有向图的不同存储结构表示方法上实现。下面针对图349a所给出的AOV网进行讨论。
图349AOV网G及其邻接表
邻接矩阵存储结构中，由于某个顶点的入度由这个顶点相对应列上的1的个数所确定，而它的出度由顶点所对应行上的1的个数所确定，所以在这种存储结构上实现拓扑排序算法的步骤是1 取1作为第一个序号。2 找一个还没有获得序号的全零元素的矩阵列，若没有则停止寻找。此时，如果矩阵中所有列都已获得了序号，则拓扑排序完成； 否则，说明该有向图中有环存在。3 把序号值赋给找到的列，并将该列对应的顶点输出。4 将找到列所对应的行中所有为1的元素清零。5 序号值增1，重复执行步骤2~5。
根据以上步骤，使用一个长度为n的数组来存放序号值时，可以给出如下的实现算法。
TOPOSORTAgraph *g，int n *对有n个顶点的有向图，使用邻接矩阵求拓扑排序*
{int i, j, k, t, v, D［n］=0;
v=1;* 序号变量置1 *
for k=0; kn; k {
for j=0; jn; j*寻找全零列*
if D［j］= =0 {
t=1;
for i=0; in; i
if g－arcs［i］［j］= =1 {
t=0;
break;
}* 若第j列上有1，则跳出循环 *
if t= =1 {
m=j;
break;
}*找到第j列为全0列*
}
if j!=n {
D［m］=v;* 将新序号赋给找到的列 *
printf " %d＼t ", g－vexs［m］;* 将排序结果输出 *
for i=0; in; i
g－arcs［m］［i］=0;*将找到的列的相应行置全0*
v;*新序号增1*
}
else break;
}
if v－1n printf " ＼n The network has a cycle ＼n ";
} * TOPOSORTA *
图349中G的邻接矩阵应用以上算法得到的拓扑排序序列为v1,v2, v4, v3, v5, v6, v7。利用邻接矩阵进行拓扑排序时，程序虽然简单，但效率不高，算法的时间复杂度约为On3。 而利用邻接表使寻找顶点入度为0的操作简化，从而提高拓扑排序算法的效率。邻接表存储结构中，为了便于检查每个顶点的入度，可在顶点表中增加一个入度域id。此时，只需要对由n个元素构成的顶点表进行检查就能找出入度为0的顶点。为避免对每个入度为0的顶点重复访问，可用一个链栈来存储所有入度为0的顶点。进行拓扑排序前，只要对顶点表进行一次扫描，便可将所有入度为0的顶点都入栈。以后，每次从栈顶取出入度为0的顶点，并将其输出即可。一旦排序过程中出现了新的入度为0的顶点，同样又将其入栈。入度为0的顶点出栈后，根据顶点的序号找到相应的顶点和以该顶点为起点的出边，再根据出边上的邻接点域的值使相应顶点的入度值减1，便完成了删除所找到的入度为0的顶点的出边的功能。邻接表存储结构中实现拓扑排序算法的步骤为1 扫描顶点表，将入度为0的顶点入栈。2 当栈非空时执行以下操作：① 将栈顶顶点vi的序号弹出，并输出之；② 检查vi的出边表，将每条出边表邻接点域所对应的顶点的入度域值减1，若该顶点入度为0，则将其入栈。3 若输出的顶点数小于n，则输出有回路，否则拓扑排序正常结束。具体实现时，链栈无须占用额外空间，只需利用顶点表中入度域值为0的入度域来存放链栈的指针（即指向下一个存放链栈指针的单元的下标），并用一个栈顶指针top指向该链栈的顶部即可。由此给出以下的具体算法。
typedef int datetype;
typedef int vextype;
typedef struct node {
int adjvex; * 邻接点域 *
struct node *next;* 链域 *
} edgenode;* 边表结点 *
typedef struct {
vextype vertex;*顶点信息 *
int id;*入度域 *
edgenode *link;* 边表头指针 *
} vexnode;*顶点表结点*
vexnode ga［n］;
TOPOSORTBvexnode ga［ ］ {* AOV网的邻接表 *
{int i, j, k, m=0, top=－1;* m为输出顶点个数计数器，top为栈指针 *
edgenode *p;
for i=0; in; i* 初始化，建立入度为0的顶点链栈 *
if ga［i］.id= =0 {
ga［i］.id=top;
top=i;
}
while top!=－1 {* 栈非空执行排序操作 *
j=top;
top=ga［top］.id;* 第j 1个顶点退栈 *
printf " %d＼t ", ga［j］.vertex;* 输出退栈顶点 *
m;* 输出顶点计数 *
p=ga［j］.link;
whilep {* 删去所有以vj 1为起点的出边 *
k=p－adjvex－1;
ga［k］.id--;* vk 1入度减1 *
if ga［k］.id= =0 {*将入度为0的顶点入栈*
ga［k］.id=top;
top=k;
}
p=p－next;* 找vj 1的下一条边 *
}
}
if mn* 输出顶点数小于n，有回路存在 *
printf " ＼n The network has a cycle＼n ";
}* TOPOSORTB *
对于图349中的邻接表执行以上算法时，入度域的变化情况如图350所示。这时得到的拓扑序列为v4, v5, v1, v3, v2, v7, v6。
图350排序过程中入度域变化示例
对一个具有n个顶点，e条边的AOV网来说，初始化部分执行时间是On； 排序中，若AOV网无回路，则每个顶点入栈和出栈各一次，每个边表结点检查一次，执行时间为On e，故总的算法时间复杂度为On e。
3.7小结本章介绍了两种非线性的数据结构树和图。树在存储结构中占据非常重要的地位，在树形结构中树是一种具有层次特征的数据结构，二叉树是一种非常重要、简单、典型的数据结构。二叉树的5个性质揭示了二叉树的主要特征。二叉树的存储结构有顺序存储结构和链式存储结构两种。采用顺序存储结构可能会浪费大量的空间，因此常常利用顺序存储结构存储满二叉树和完全二叉树，而一般二叉树大多采用链式存储结构。二叉树的遍历是对二叉树进行各种操作的基础，无论递归算法还是非递归算法都要很好掌握。二叉树的遍历是一种常用的操作。二叉树的遍历分为先序遍历、中序遍历和后序遍历。二叉树的遍历过程就是将二叉树这种非线性结构转换成线性结构。树和森林的存储有多种方法，和二叉树一样，对树和森林的遍历是对树结构操作的基础，通常有先根和后根两种遍历方法，分别对应于二叉树的先序和中序遍历，所以能利用二叉树的遍历来实现。树、森林和二叉树可以相互转化，树实现起来不是很方便，实际应用中，可以将问题转化为二叉树的相关问题加以实现。哈夫曼树是n个带权叶子结点构成的带权路径长度最短的二叉树。哈夫曼树是二叉树的应用之一，要掌握哈夫曼树的建立方法及哈夫曼编码生成算法，值得注意的是哈夫曼树通常采用静态链式存储结构。图的存储结构有4种，分别是邻接矩阵存储结构、邻接表存储结构、十字链表存储结构和邻接多重表存储结构。其中，最常用的是邻接矩阵存储和邻接表存储。图的遍历分为两种，分别是广度优先遍历和深度优先遍历。图的广度优先遍历类似于树的层次遍历，图的深度优先遍历类似于树的先根遍历。构造最小生成树的算法主要有两个，分别是普里姆算法和克鲁斯卡尔算法。最短路径是一个与实际关系密切的，最短路径表示完成工程的最短工期，通常用图的顶点表示事件，弧表示活动，权值表示活动的持续时间。树和图是数据结构中的难点，学好树和图的第一步就是要搞清楚树和图中的一些概念，然后多看算法，耐心研究算法，从多方面认真学习树和图。3.8习题1. 单项选择题
1 树形结构的特点是任意一个结点（）。
A. 可以有多个直接前趋B. 可以有多个直接后继C. 至少有1个前趋D. 只有一个后继2 将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为（）。A. 98B. 99C. 50D. 483 对具有100个结点的二叉树，若用二叉链表存储，则其指针域部分用来指向结点的左、右孩子，一共有（）个指针域为空。A. 55B. 99C. 100D. 1014 如果T1是由有序树T转换来的二叉树，则T中结点的后序排列是T1结点的（）排列。A. 先序B. 后序C. 中序D. 层序5 设有13个值，用它们组成一棵Huffman树，则该Huffman树中共有（）个结点。A. 13B. 12C. 26D. 256 若对一棵有20个结点的完全二叉树按层编号，则编号为5的结点x，它的双亲结点及左孩子结点的编号分别为（）。A. 2,11B. 2,10C. 3,9D. 3,107 将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为（）。A. 48B. 49C. 50D. 518 在有n个结点的二叉链表中，值为非空的链域的个数为（）。A. n-1B. 2n-1C. n 1D. 2n 19 由64个结点构成的完全二叉树，其深度为（）。A. 8B. 7C. 6D. 510 一棵含18个结点的二叉树的高度至少为（）。
A. 3B. 4C. 5D. 611 在一个无向图中，所有顶点的度之和等于边数的（）倍。A. 12B. 1C. 2D. 412 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A. 12B. 1C. 2D. 413 设有6个顶点的无向图，该图至少应有（）条边，才能确保它是一个连通图。A. 5B. 6C. 7D. 814 具有5个顶点的无向完全图共有条边。A. 5B. 10C. 15D. 2015 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）。A. nB. n-1n-1C. n-1D. nn16 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小是（）。A. nB. n 1C. e 1D. e17 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有邻接表中的结点总数是（）。A. e2B. eC. 2eD. n e18 无向图的邻接矩阵是一个（）。A. 对称矩阵B. 零矩阵C. 上三角矩阵D. 对角矩阵19 在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）。A. eB. 2eC. n2-eD. n2-2e20 假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是（）。A. OnB. OeC. On eD. On*e2. 填空题1 不考虑顺序的3个结点可构成种不同形态的树，种不同形态的二叉树。2 已知某棵完全二叉树的第4层有5个结点，则该完全二叉树叶子结点的总数为。3 已知一棵完全二叉树的第5层有3个结点，其叶子结点数是。4 已知一棵完全二叉树中共有768个结点，则该树中共有个叶子结点。5 一棵具有110个结点的完全二叉树，若i＝54，则结点i的双亲编号是； 结点i的左孩子结点的编号是，结点i的右孩子结点的编号是。6 一棵具有48个结点的完全二叉树，若i＝20，则结点i的双亲编号是； 结点i的左孩子结点编号是，右孩子结点编号是。7 一棵树T采用二叉链表存储，如果树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定。8 已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为。9 在有n个叶子结点的Huffman树中，总的结点数是。10 图是一种非线性数据结构，它由两个集合VG和EG组成，VG是的非空有限集合，EG是的有限集合。（11） 在无权图G的邻接矩阵A中，若vi,vj或＜vi,vj＞属于图G的边集合，则对应元素A［i］［j］等于。（12） 设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互为邻接点的条件是。13 图G有n个顶点和e条边，以邻接表形式存储，进行深度优先搜索的时间复杂度为。（14） 设无向图G中有n个顶点e条边，则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为。（15） 具有n个顶点的无向图，拥有最少的连通分量个数是，拥有最多的连通分量个数是。16 图的遍历基本方法中是一个递归过程。17 n个顶点的有向图最多有条弧。18 n个顶点的无向图最多有条边。19 在无向图G的邻接矩阵A中，若A［i,j］等于1，则A［j,i］等于。20 在一个具有n个顶点的无向图中，要连通全部顶点至少需要条边。3. 判断题1 （）非线性数据结构可以顺序存储，也可以链接存储。2 （）非线性数据结构只能用链接方式才能表示其中数据元素的相互关系。3 （）完全二叉树一定是满二叉树。4 （）平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。5 （）若一棵二叉树的任意一个非叶子结点的度为2，则该二叉树为满二叉树。6 （）度为1的有序树与度为1的二叉树等价。7 （）一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。8 （）二叉树的先序遍历序列中，任意一个结点均排列在其孩子结点的前面。9 （）若二叉树的叶子结点数为1，则其先序序列和后序序列一定相反。10 （）已知一棵二叉树的先序序列和后序序列，就一定能构造出该二叉树。11 （）邻接表表示法是采用链式存储结构表示图的一种方法。12 （）用邻接表表示图的方法优于用邻接矩阵表示图的方法。13 （）在边稀疏的情况下，用邻接表表示图要比用邻接矩阵节省存储空间。14 （）用邻接矩阵方法存储图比用邻接表方法存储图更容易确定图中任意两个顶点之间是否有边相连。15 （）在有向图中，逆邻接表表示法是指将原有邻接表所有数据按相反顺序重新排列的一种表示方法。16 （）在有向图中，采用逆邻接表表示法是为了便于确定顶点的入度。17 （）无向图的连通分量至少有一个。18 （）有向图的强连通分量最多有一个。19 （）简单路径是指图中所有顶点均不相同而形成的一条路径。20 （）简单回路是指一条起始点和终止点相同的简单路径所构成的回路。4. 综合题1 如图351所示的两棵二叉树，分别给出它们的顺序存储结构。
图351两棵叉树
2 已知一棵二叉树的中序、后序序列分别如下：中序D C E F B H G A K J L I M后序D F E C H G B K L J M I A要求① 画出该二叉树；
② 写出该二叉树的先序序列。3 将图352所示的树转换成二叉树，并写出转换后二叉树的先序、中序、后序遍历结果。
图352树
4 写出图353中的二叉树先序和后序遍历序列。
图353二叉树（1）
5 请画出与图354所示二叉树对应的森林。
图354二叉树（2）
6 从空树起，依次插入关键字40、8、90、15、62、95、12、23、56、32，构造一棵二叉排序树。要求① 画出该二叉排序树；
② 画出删去该树中结点元素值为90之后的二叉排序树。7 输入一个正整数序列{100，50，302，450，66，200，30，260}，建立一棵二叉排序树，要求① 画出该二叉排序树；
② 画出删除结点302后的二叉排序树。8 按给出的一组权值{4，5，7，8，11}，建立一个哈夫曼树，并计算出该树的带权路径长度WPL。
9 给出如图355所示无向图的邻接矩阵和邻接表。
图355无向图1
10 求出图356的一棵最小生成树。
图356无向图2
11 如图357所示的有向图，请给出它的① 每个顶点的入度和出度；② 邻接矩阵；③ 邻接表；④ 强连通分量。
图357有向图1
12 给出有向图358的邻接矩阵、邻接表形式的存储结构，并计算出每个顶点的入度和出度。
图358有向图2
13 已知图359所示，其顶点按a、b、c、d、e、f顺序存放在邻接表的顶点表中，请画出该图的邻接表，使得按此邻接表进行深度优先遍历时得到的顶点序列为acbefd，进行广度优先遍历时得到的顶点序列为acbdfe。
图359有向图3
14 已知一组数据序列D={d1, d2, , d9}，其数据间的关系为R={d1, d3, d1, d8, d2, d3, d2, d4, d2, d5, d3, d9, d5, d6, d8, d9, d9, d7, d4, d7, d4, d6}。请画出此数据序列的逻辑结构图，并说明该图属于哪种结构。15 已知数据结构的形式定义为DS={D,S}，其中
D={1,2,3,4}，S=={R}，R={1,2,1,3,2,3,2,4,3,4}
试画出此结构的图形表示。16 已知图G的邻接表如图360所示，顶点v1为出发点，完成以下要求：① 写出按深度优先搜索的顶点序列。② 写出按广度优先搜索的顶点序列。
图360邻接表（1）
17 已知某无向图的邻接表存储结构如图360所示，要求①画出此无向图； ②给出无向图的邻接矩阵表示。18 已知一带权连通图G=V,E的邻接表如图361所示。画出该图，并分别以BFS和DFS遍历，写出遍历序列，并画出该图的一个最小生成树。示意图362为表结点的结构图（以V1为初始点）。
图361邻接表（2）
图362示意图
|
|
購物車/收銀台(0) | 在線留言板
| 付款方式
| 聯絡我們
| 運費計算
| 幫助中心 |
加入書簽
HOME
新書上架
