新書推薦：
《
生活中的民法典实用全书：应知应懂的法律常识
》
售價：HK$
106.8
《
饲渊
》
售價：HK$
47.8
《
现金为王：把利润留下来，把成本降下去
》
售價：HK$
82.8
《
经纬度丛书·巴勒斯坦人的故事：流亡者的悲情、绝望与抗争
》
售價：HK$
105.6
《
改变世界的哲学家们
》
售價：HK$
105.6
《
将军
》
售價：HK$
57.6
《
墓志的生成及其在唐代的衍变研究
》
售價：HK$
117.6
《
理解中国经济：在大变局中读懂新机遇
》
售價：HK$
54.0
|
| 編輯推薦： |
|
系统地介绍了计算机软件基础的基本内容，包括数据结构、数据库技术、计算机操作系统和软件工程。? 在注重理论讲解的同时给出了程序的仿真实例和仿真结果，有利于帮助相关读者更加深入的理解相关知识。? 以现代教育理念为指导，在讲授方式上注意结合应用开发实例，注重培养学生理解面向对象程序设计思想，以提高分析问题和解决实际问题的能力。? 书中的所有程序都是在VC 6.0环境下编译调试通过的。
|
| 內容簡介： |
|
本书可作为高等院校非计算机专业本科生的基础理论课程教材，也可作为工程技术人员的参考书，还可作为全国计算机等级考试（二级）的参考教材以及成人教育和职业教育的培训教材。
|
| 目錄：
|
目录
第1章绪论
1.1计算机与计算机系统
1.1.1计算机的特点与发展历史
1.1.2计算机的应用
1.1.3计算机系统的组成
1.2计算机软件技术
1.2.1计算机软件的特点
1.2.2计算机软件的分类
1.2.3计算机软件的发展历史
习题
第2章线性数据结构
2.1数据及数据结构概述
2.1.1数据及数据结构定义
2.1.2数据结构相关名词和术语
2.1.3数据结构的研究内容
2.2线性表
2.2.1线性表的逻辑定义和特征
2.2.2线性表的顺序存储与运算
2.2.3线性表的链式存储与运算
2.2.4线性表的顺序存储和链式存储方法的比较
2.3栈和队列
2.3.1栈的定义、存储与运算
2.3.2队列的定义、存储与运算
2.4字符串和数组
2.4.1字符串的定义、存储与运算
2.4.2数组的定义与存储
习题
第3章非线性数据结构
3.1树与二叉树
3.1.1树的基本概念
3.1.2二叉树及其性质
3.1.3二叉树的存储结构
3.1.4二叉树的遍历方法
3.1.5树的存储结构和遍历
3.1.6树、森林与二叉树
3.1.7哈夫曼树及其应用
3.2图
3.2.1图的逻辑定义
3.2.2图的存储结构
3.2.3图的遍历方法
3.2.4图的连通性与最小生成树
习题
第4章查找与排序技术
4.1查找的基本概念
4.2静态查找
4.2.1顺序查找
4.2.2折半查找
4.2.3分块查找
4.3动态查找
4.3.1二叉排序树的定义
4.3.2二叉排序树的插入与生成操作
4.3.3二叉排序树的查找操作
4.4哈希查找
4.4.1哈希表相关基本概念
4.4.2哈希函数的构造
4.4.3冲突的处理方法
4.4.4哈希查找方法
4.5排序技术
4.5.1直接插入排序
4.5.2简单选择排序
4.5.3交换排序
4.5.4几种排序方法比较
习题
第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.3关系数据库标准语言SQL
5.3.1SQL的定义
5.3.2数据定义
5.3.3数据查询
5.3.4数据更新
5.3.5数据视图
5.4数据库的设计流程
5.4.1数据库设计概述
5.4.2需求分析
5.4.3概念设计
5.4.4逻辑设计
5.4.5物理设计
5.4.6数据库的实施和维护
习题
第6章操作系统
6.1操作系统概述
6.1.1操作系统的概念与发展
6.1.2操作系统的功能与分类
6.2中央处理器管理
6.2.1中央处理器的概念
6.2.2进程及其实现
6.2.3线程及其实现
6.2.4作业调度方法
6.2.5进程调度方法
6.2.6并行程序设计方法
6.3存储管理
6.3.1存储管理的功能及概念
6.3.2连续存储管理
6.3.3分页式存储管理
6.3.4分段式存储管理
6.3.5虚拟存储管理
6.4设备管理
6.4.1设备管理的任务、功能及设备的分类
6.4.2缓冲技术
6.4.3虚拟设备
6.5文件管理
6.5.1文件概述
6.5.2文件的结构和存取
6.5.3文件目录
6.5.4文件的保护
6.6常见操作系统
6.6.1DOS操作系统
6.6.2Windows操作系统
6.6.3UNIX操作系统
6.6.4开源软件与Linux操作系统
习题
第7章软件工程
7.1软件工程概述
7.1.1软件与软件危机
7.1.2软件工程的基本原理
7.1.3软件的生命周期
7.2软件开发过程
7.2.1软件的需求分析
7.2.2详细设计
7.2.3软件编程
7.2.4软件测试
7.2.5软件维护
7.3软件开发过程中的系统分析与设计方法
7.3.1结构化的分析与设计方法
7.3.2面向对象的分析与设计方法
习题
参考文献
|
| 內容試閱：
|
前言
在当今社会，计算机技术已经渗透到生产和生活的方方面面，掌握基本的计算机软硬件技术已经成为工科非计算机专业大学生求职的必备要求。本书针对工科非计算机专业本科生的需要，是一本有关计算机软件知识及开发技术的基础教材，主要讲授计算机软件的基本概念、方法及实用技术，书中内容涉及数据结构、数据库技术、操作系统和软件工程。本书除了理论知识的介绍外，还注重读者实际编程和动手能力的提高，注重理论和实践的联系，主要特色如下。1 在算法理论之后附带可运行的程序示例。本书中的大部分程序都经过作者亲自在C语言编程环境下运行调试。学生可以在学习理论知识之后直接上机运行相应程序，获得直观感受，从而巩固学习效果，提高学习兴趣。2 理论联系实际。书中附有精选的课后习题作为补充，这些习题很多是实际中可能会遇到的情况，在数据库章节也给出了实际数据库的示例，这些都能够使学生更好地把学到的理论与实际结合起来。本书共分7章，各章安排如下。第1章主要介绍计算机系统及计算机软件的概念及发展。第2章主要介绍数据结构和线性数据结构的基本概念，包括线性表、栈、队列和数组等线性数据结构的逻辑概念和存储结构，以及在相应存储结构下的查找、删除、插入等算法，并给出了算法运行的结果示例。第3章主要介绍非线性数据结构树和图的基本概念和存储结构，以及在相应存储结构下的算法，重点介绍了二叉树的存储结构与算法。第4章介绍几种常用的查找和排序算法，给出了各种算法的设计思想和实际例程，并对各种查找和排序算法进行了比较。第5章介绍数据库设计的基本概念、基本原理、方法及技术，并简要介绍实体联系模型ER模型、关系模型、关系运算、关系数据库设计理论、数据库语言SQL和数据库的设计流程等知识，为开发数据库应用系统打下一定的基础。第6章主要介绍系统软件中最靠近硬件的一层软件操作系统，给出了操作系统的基本概念、发展历程以及操作系统的基本功能： 中央处理器管理、存储管理、设备管理、文件管理，最后介绍了几种常见的操作系统。第7章介绍软件工程的基本概念以及软件开发过程中的系统分析方法与设计方法。本书在编写过程中参考了计算机软件技术和数据结构方面的经典教材，取长补短，力争做到深入浅出，注重实践。本书由北京信息科技大学杨飞主编，北京信息科技大学许晓飞、王军茹副主编。书中第1~4章由杨飞编写，第5、7章由许晓飞编写，第6章由王军茹编写。由于编者水平有限，书中难免存在疏漏和不妥之处，恳请广大读者批评指正。作者2016年9月
第3章非线性数据结构
在计算机科学中，除了前面章节介绍的线性数据结构之外，还存在许多线性数据结构描述不了的问题，如数据元素之间的层次关系、分支关系等，这些复杂关系需要靠非线性数据结构来进行描述。树和图就是两种最广泛使用的非线性结构，本章将介绍树和图的定义以及基本操作。3.1树与二叉树〖*2〗3.1.1树的基本概念1. 树的定义
在数据结构中，树的定义最常用的方式是一种递归定义。树Tree是包含nn0个结点的有穷集合。N=0时称为空树，否则任何一个非空树都满足如下条件：（1） 有且仅有一个特定结点被称为根结点Root；（2） 除根结点之外的其余数据元素被分为mm0个互不相交的集合T1，T2，,Tm-1，其中每一个集合本身也是一棵树，被称作子树。很显然，在上面树的定义当中又用到了树的概念，因此这是一个递归定义，它显示了树的固有特性，这在本章后续的算法当中会有充分的体现。
图31树形结构示意图
图31是包含了9个结点的树，即T{A, B, C ,, H, I}，其中A为树T的根结点，除根结点A之外的其余结点分为两个不相交的集合： T1{B, D, E, F, H, I}和T2{C, G}，T1和T2本身也是一棵树，分别称为根结点A的两棵子树，而两棵子树T1和T2的根结点分别为B和C。其余结点又分为三个不相交的集合： T11{D}，T12{E, H, I}和T13{F}。T11，T12和T13又构成了T1子树的三棵子树。如此继续向下分为更小的子树，直到每棵子树只有一个根结点为止。
下面结合图31给出树的一些基本术语，通过这些术语能够更好的理解树形结构。2. 树的基本术语（1） 结点的度： 一个结点具有的子树的个数称为该结点的度。图31中，该树根结点A的度是2，结点B的度是3，而结点D没有子树，因此结点D的度为0。（2） 叶子： 度为0的结点称为叶子或终端结点。图31中树的叶子结点是D、H、I、F、G。（3） 树的度： 树中所有结点度的最大值称为树的度。图31中树的度为3。（4） 分支结点： 与叶子相对应，树中度大于0的结点称为分支结点，分支结点有时也称非终端结点。一棵树的结点除叶子结点外，其余的都是分支结点。（5） 孩子结点： 树中某结点子树的根称为该结点的孩子结点。（6） 双亲结点： 与孩子相对应，如果一个结点存在孩子结点，则这个结点就称为孩子结点的双亲。双亲结点有时也称父亲结点，图31中A结点的孩子结点是B和C，同时结点A又是B和C的双亲结点。（7） 兄弟结点： 具有同一双亲的结点互称为兄弟结点。图31中结点D、E、F是兄弟结点。（8） 堂兄弟结点： 双亲在同一层的结点互称为堂兄弟结点。图31中结点D和G是堂兄弟结点。（9） 子孙结点： 一个结点的所有子树中的结点称为该结点的子孙结点。（10） 结点层数： 规定树的根结点层数为1，其孩子结点为第2层。以此类推，结点层数等于其双亲结点加1，由此可得到每个结点的层数。
（11） 树的深度： 树中所有结点的最大层数称为树的深度。如图31所示，该树的深度为4。（12） 有序树： 如果一棵树中结点的各子树从左到右是有次序的，即若交换了某结点各子树的相对位置，则构成不同的树，则称这棵树为有序树。（13） 森林： 有限棵不相交的树的集合称为森林。通常情况下，在计算机中表示一棵树时，本身就隐含了一种确定的相对次序，因此后面本书中所讨论的树默认都是有序树。3.1.2二叉树及其性质在介绍树形结构的算法之前，先来学习一种特殊形态的树二叉树。二叉树是树形结构的一个重要类型，许多实际问题可以抽象出来的数据结构往往满足二叉树的形式，且二叉树和普通树之间也存在相互转换的关系。1. 二叉树的定义二叉树是特殊形态的树，因此其定义可以参照普通树的定义，顾名思义与普通树的最主要区别在于二叉树中每个结点的儿子至多有两个，即每个结点最多有两个向下的分叉，并由此而得名，其定义如下。二叉树Binary Tree是个有限元素的集合，该集合或者为空，或由一个根结点和两棵互不相交的、分别被称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。很显然这也是一个递归定义，由定义可得到二叉树的两个基本特点，具体如下。1 二叉树中不存在度大于2的结点，即每个结点至多有两个孩子。2 二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。因此二叉树具有五种基本形态，如图32所示。
图32二叉树的5种基本形态
思考： 根据树和二叉树的定义，读者可以自己试着画出具有3个结点的树和二叉树的形态。2. 二叉树的性质【性质3.1】一棵非空二叉树的第i层结点数最多为2i－1i1。证明： 该性质可由数学归纳法，根据二叉树的定义来证明。【性质3.2】一棵深度为k的二叉树中，最多具有2k－1k1个结点。证明： 在深度为k的二叉树中，只有当每层的结点数都为最大值时，树的总结点数才为最大值，因此根据性质3.1可以得到深度为k的二叉树中结点数最多为：
20 21 2k－1=2k－1
【性质3.3】在一棵非空二叉树中，如果其叶子结点数为n0，度数为2的结点为n2，则有：
n0=n2 1
证明： 1 设M为二叉树的结点总数，n1为二叉树中度为1的结点数，则有： M=n0 n1 n2；2 此外，根据二叉树的定义，度为1的结点有1个孩子，度为2的结点有2个孩子，因此二叉树中的孩子结点数为n12n2；3 而在二叉树中，只有根结点不是任何结点的孩子，所以二叉树的总结点树又可表示为M=n1 2n2 1。由此得到M=n0 n1 n2=n1 2n2 1，最终推导出n0=n2 1。【性质3.4】具有n个结点的完全二叉树的深度为lbn 1。在证明性质3.4之前先来介绍两种特殊形态的二叉树完全二叉树和满二叉树。一棵深度为k且有2k－1个结点的二叉树称为满二叉树，即该满二叉树中的结点数为最大值。图33a给出了一棵深度为4的满二叉树，这种二叉树的特点是所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上。
图33深度为4的满二叉树
可以对满二叉树的结点自上而下、自左而右进行连续编号，约定编号从根结点起，编号结果如图33b所示。由此可引出完全二叉树的定义如下： 深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。图34给出了一个深度为4的完全二叉树。
图34深度为4的完全二叉树
由此可以总结出完全二叉树和满二叉树的特点如下。（1） 完全二叉树的叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。（2） 一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。下面证明性质3.4： 设一棵完全二叉树的深度为k，结点个数为n，则根据完全二叉树的定义和性质3.2可知，结点的个数n要位于深度为k-1层和k层的最大结点数之间，即
2k－1n1，则序号为i的结点的双亲结点序号为i2。2 如果2in，则结点i无左孩子，否则其左孩子结点的序号为2i。3 如果2i 1n，则结点i无右孩子，否则其右孩子结点序号为2i 1。此性质可采用数学归纳法证明。3.1.3二叉树的存储结构二叉树的存储方式主要有顺序存储和链式存储两种方式，下面进行详细介绍。1. 二叉树的顺序存储所谓二叉树的顺序存储，就是用一组连续的存储单元，按照从上至下、从左到右的顺序依次存放二叉树中的结点。因此，依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系。图34中的完全二叉树的顺序存储结构如图35所示。
123456789101112
ABCDEFGHIJKL
图35完全二叉树的顺序存储结构
从图35中可以出，完全二叉树的顺序存储结构能够很好地反映出二叉树结构的线性序列，这样既能够最大地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。但是对于一般的二叉树而言，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系。这时，需要对二叉树进行改造，增添一些空结点，使之成为一棵形式上的完全二叉树，然后再用一维数组顺序存储，空结点在存储时用0表示，如图36所示。
图36一般二叉树的顺序存储结构
显然，这种存储方式会造成存储空间的大量浪费，尤其是图36a中的右单支树，需要补足的空结点非常多，因此对于一般的二叉树而言，采用顺序的存储方式不太合适。下面介绍二叉树的链式存储结构。2. 二叉树的链式存储所谓二叉树的链式存储是指用链表来表示一棵二叉树，根据二叉树的定义，二叉树中每个结点最多拥有左右两个孩子，因此在构建链表节
lchilddatarchild
图37结点结构1
点时，每个结点由三个域组成： 数据域、左孩子指针域和右孩子指针域，这种形式在数据结构中又称为二叉链表。结点结构如图37所示。其中，data域存放某结点的数据信息； lchild与rchild分别存放指向左孩子和右孩子的指针，当左孩子或右孩子不存在时，相应指针域值为空。二叉树的二叉链表的C语言描述如下。
typedef struct BiTNode{
elemtype data;
struct BiTNode * lchild;* rchild;
}BiTNode, * BiTree;
在上述的二叉链表中，可以比较方便地从某一个结点出发找到它的子结点，但是没法找到其父结点，也就是说二叉链表是单方向的。有时为了便于对链表中的结点进行查找，在结点结构中增加一个指向其父结点的指针域，这种结构又称三叉链表。结点结构如图38所示。
lchilddataparentrchild
图38结点结构2
图39给出了图36a所示的二叉树的二叉链表和三叉链表存储结构，图39中T表示该二叉树根结点的指针。
图39图36中二叉树的链式存储结构
3.1.4二叉树的遍历方法二叉树的遍历是指按照一定次序访问二叉树中的所有结点，且每个结点仅被访问一次。遍历是二叉树中经常要用到的一种操作，通过一次完整的遍历，可使二叉树中结点由非线性序列变为某种意义上的线性排列。由二叉树的定义可知，一棵二叉树由根结点、左子树和右子树三部分组成，因此，只要依次遍历这三部分，就可以遍历整个二叉树，常用的遍历方式主要有先序遍历、中序遍历和后序遍历。如果用D操作表示访问根结点，用L操作表示遍历根结点的左子树，用R操作表示遍历根结点的右子树，则三种常用的遍历方式可以表示为： 先序遍历DLR、中序遍历LDR和后序遍历LRD。从中我们可以看出，这三种遍历方式的共同点在于都是先访问左子树，再访问右子树，即L操作总是在R操作之前，而不同的地方在于D操作位于不同的位置。下面给出三种遍历方式的递归算法思路，该思路是基于二叉树的递归定义给出的。1. 先序遍历DLR若二叉树为空，遍历结束，否则按如下步骤进行操作：① 访问根结点的数据域；② 先序遍历根结点的左子树；③ 先序遍历根结点的右子树。先序遍历二叉树的C语言递归算法如下。算法31： 先序遍历二叉树的递归算法
void PreorderBiTNode *bt
{
ifbt !=NULL
{
printf"%d", bt-data;*访问根结点的数据域*
Preorderbt-lchild;*先序递归遍历bt的左子树*
Preorderbt-rchild; *先序递归遍历bt的右子树*
}
}
2. 中序遍历LDR若二叉树为空，遍历结束，否则按如下步骤进行操作：① 中序遍历根结点的左子树； ② 访问根结点的数据域；③ 中序遍历根结点的右子树。中序遍历二叉树的C语言递归算法如下。算法32： 中序遍历二叉树的递归算法
void Inorder BiTNode *bt
{
ifbt !=NULL
{
Inorderbt-lchild;*中序递归遍历bt的左子树*
printf"%d", bt-data;*访问根结点的数据域*
Inorderbt-rchild; *中序递归遍历bt的右子树*
}
}
3. 后序遍历LRD若二叉树为空，遍历结束，否则按如下步骤进行操作：① 后序遍历根结点的左子树；② 后序遍历根结点的右子树；③ 访问根结点的数据域。后序遍历二叉树的C语言递归算法如下。算法33： 后序遍历二叉树的递归算法
void PosorderBiTNode *bt
{
ifbt !=NULL
{
Posorderbt-lchild;*后序递归遍历bt的左子树*
Posorderbt-rchild; *后序递归遍历bt的右子树*
printf"%d", bt-data;*访问根结点的数据域*
}
}
4. 二叉树遍历的非递归算法上面介绍的二叉树先序遍历、中序遍历和后序遍历三种算法都是递归算法。这种递归算法程序简洁，易于实现，但是并非所有程序设计语言都允许递归，另外递归算法可读性一般不好，执行效率也不高，因此下面将分析二叉树遍历的非递归算法。分析上述三种遍历算法可以发现，如果将访问根结点的D操作，即把三个算法中的printf语句去掉，那么三个算法的结构是完全一致的。也就是说对二叉树进行先序、中序和后序遍历都是从根结点开始的，且在遍历过程中经过结点的路线是一样的，只是访问的时机不同而已。先序遍历是在深入时遇到结点就访问，中序遍历是在从左子树返回时遇到结点访问，后序遍历是在从右子树返回时遇到结点访问。遍历过程中，返回结点的顺序与深入结点的顺序相反，既后深入先返回，正好符合栈结构后进先出的特点。因此，可以用栈来帮助实现这一遍历路线。其过程如下： 在沿左子树深入时，深入一个结点入栈一个结点，若为先序遍历，则在入栈之前访问之，当沿左分支深入不下去时，则返回，即从堆栈中弹出前面压入的结点； 若为中序遍历，则此时访问该结点，然后从该结点的右子树继续深入； 若为后序遍历，则将此结点再次入栈，然后从该结点的右子树继续深入，与前面类同，仍为深入一个结点入栈一个结点，深入不下去再返回，直到第二次从栈里弹出该结点，才访问之。下面以先序遍历为例给出非递归算法。该算法中，二叉树以二叉链表存放，一维数组stack［MAXNODE］用于实现栈，变量top用来表示当前栈顶的位置，算法的具体步骤如下：1 当树非空时，将指针p指向根结点，p为当前结点指针；（2） 先访问当前结点p，并将p压入栈stack中；（3） 令p指向其左孩子；（4） 重复执行步骤2和3，直到p为空为止；（5） 从栈stack中弹出栈顶元素，将p指向此元素的右孩子；（6） 重复执行步骤2~5，直到p为空并且栈也为空；（7） 遍历结束。算法34： 先序遍历二叉树的非递归算法
void NRPreOrderBiTree bt *非递归先序遍历二叉树*
{
BiTree stack［MAXNODE］, p;
int top;
ifbt==NULL return;
top=0;
p=bt;
while!p==NULL&&top==0
{
whilep!=NULL
{
printf"%d", p-data; *访问结点的数据域*
iftoplchild;*指针指向p的左孩子*
}
iftoprchild;*指针指向p的右孩子结点*
}
}
}
3.1.5树的存储结构和遍历对于一棵普通的树而言，既可以采用顺序存储结构，也可以采用链式存储结构，但无论采用何种存储方式，除了准确存储各结点本身的数据信息外，还要唯一反映树中各结点之间的逻辑关系，常见的树的存储表示方法有双亲表示法、孩子表示法、孩子兄弟表示法等。在此仅介绍一种常用的链式存储结构孩子兄弟表示法，这种方法又称树的二叉链表表示法。1. 树的二叉链表表示法在该二叉链表中，每个结点除其信息域外，还包含两个指针域，分别指向该结点的第一个孩子结点和下一个兄弟右邻兄弟结点。图310给出了图31所示的树的二叉链表存储结构。
图310图31中树的二叉链表存储结构
2. 树的遍历对普通树的遍历只有先序和后序两种，但没有中序遍历之说，中序遍历只有二叉树才有。（1） 先根遍历： 首先访问根结点，然后按照从左到右的顺序先根遍历根结点的每一棵子树。（2） 后根遍历： 首先按照从左到右的顺序后根遍历结点的每一棵子树，然后访问根结点。3.1.6树、森林与二叉树由分析树和二叉树的二叉链表表示法可知，树和二叉树的存储表示结构本质上是一致的，两者都是用二叉链表作为其存储结构，只是解释不同而已。因此我们能够以二叉链表作为媒介推导出树与二叉树之间的一个对应关系，也就是说，给定一棵树，可以找到唯一的一棵二叉树与之对应。下面给出树与二叉树之间的这种对应关系。1. 树转化为二叉树将树转化成二叉树就是将树首先用兄弟孩子链表表示法进行存储，然后根据该二叉链表存储结构推导出对应的二叉树。具体步骤如下。1 加线： 亲兄弟之间加一虚连线。2 抹线： 抹掉除最左一个孩子外该结点到其余孩子之间的连线。3 旋转： 新加上去的虚线改实线且均向右斜rchild，原有的连线均向左斜lchild。图311给出了一棵普通树转化为二叉树的具体步骤。
图311普通树转化为二叉树的具体步骤
由上面的转化过程可以看出，在最终得到的二叉树中，左分支上的各结点在原来的树中是父子关系，而右分支上的各结点在原来的树中是兄弟关系。由于树的根结点没有兄弟，因此变换后的二叉树根结点的右孩子必然为空。根据树与二叉树表的转换关系以及树与二叉树遍历的操作定义可知，树的遍历序列与由树转换成的二叉树的遍历序列之间有如下对应关系：1 树的先序遍历二叉树的先序遍历；2 树的后序遍历二叉树的后序遍历。2. 森林转换为二叉树顾名思义，森林指的是树的有限集合。森林中每棵树又可以用二叉树表示，然后将森林中各棵树的根视为兄弟，这样，森林也同样可以用二叉树表示。森林转换为二叉树的方法如下：1 将各棵树分别转换为二叉树。2 由于变换后的二叉树根结点的右孩子必然为空，因此按森林中树的次序，依次将后一棵二叉树作为前一棵二叉树根结点的右子树连接在一起形成最终的二叉树。森林转换成对应的二叉树的具体过程如图312所示。
图312森林转换成对应的二叉树的具体过程
3. 二叉树转换为树和森林树和森林都可以转换为二叉树，二者不同的是树转换成的二叉树，其根结点无右孩子，而森林转换后的二叉树，其根结点有右孩子。显然这一转换过程是可逆的，即可以依据二叉树的根结点有无右孩子，将一棵二叉树还原为树或森林。具体过程如下：1 若某结点x是其双亲y的左孩子，则把结点x的右孩子，右孩子的右孩子都与该结点的双亲结点y用线连起来。2 删去原二叉树中所有的双亲结点与右孩子结点的连线。3 整理由1，2两步所得到的树或森林，使之结构层次分明。3.1.7哈夫曼树及其应用1. 哈夫曼树的定义及构成方法
最优二叉树，也称哈父曼Haffman树，是指对于一组带有确定权值的终端结点，构造具有最小带权路径长度的二叉树。该树在数据编码等算法中有着非常广泛的应用。从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数称为这两个结点之间的路径长度。对于一整棵树而言，从根结点到树中每一个结点的路径长度之和称为树的路径长度。根据该定义可知在结点数目相同的二叉树中，完全二叉树具有最小的路径长度。在二叉树中还可以为结点赋以权值，称为带权二叉树。如果二叉树中的叶子结点都具有一定的权值，则可以把树的路径长路加以推广，将从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和叫做二叉树的带权路径长度，记为：
WPL=nk=1WkLk
其中，Wk为第k个叶子结点的权值，Lk为第k个叶子结点的路径长度。【例31】图313中三棵二叉树的叶子结点的权值分别为2，4，6，8，求其带权路径长度。
图313具有不同带权路径长度的二叉树
解： 根据带权路径长度的定义，可算得图313中的三棵树的带权路径长度分别为：a WPL=2*2 4*2 6*2 8*2=40b WPL=4*2 6*3 8*3 2*1=52c WPL=8*1 6*2 4*3 2*3=38分析上述结果，图313a树是完全二叉树，但是带权路径最小的树是图313c，因此带权路径长度最小的二叉树不一定是完全二叉树。观察图313c中树的特点可以发现，在带权路径长度最小的二叉树中，权值越大的终端结点离二叉树的根越近。而哈夫曼树就是这种带权路径长度最小的二叉树，下面介绍哈夫曼树的构造方法。其基本思想如下。1 设给定一组权值为{W1，W2，，Wn}的结点，据此构成包含n棵二叉树的森林F={T1，T2，，Tn}，F中的每棵二叉树Ti只有一个带权为Wi的根结点i = 1，2，，n，其左右子树皆为空。2 在森林F中选取两棵根结点的权值最小和次小的二叉树作为左、右子树构造一棵新的二叉树，新二叉树根结点的权值为其左、右子树根结点的权值之和。3 在森林F中删除这两棵权值最小和次小的二叉树，同时将新生成的二叉树加入森林F中。4 重复步骤2和3，直到森林F中只有一棵二叉树为止，此树便是哈夫曼树。例如，给定一组权值{1，3，5，7}，图314给出了构造相应哈夫曼树的过程。
图314哈夫曼树的构造过程
2. 哈夫曼树的应用哈夫曼树的应用很广，在不同的应用中叶子结点的权值可以有不同的解释。哈夫曼树应用到信息编码中，权值可看成是某个符号出现的频率； 应用到判定过程中，权值可看成是某类数据出现的频率； 应用到排序过程中，权值可看成是已排好次序而待合并的序列的长度等。其中最典型的就是在编码技术上的应用，利用哈夫曼树可以得到平均长度最短的编码。本书以数据通信中电文的传送为例来分析说明。在数据通信中，经常需要将传送的文字转换成由二进制0和1组成的码字，称为编码。这些二进制编码往往是针对英文字符进行的，而字符集中的每个字符使用的频率是不等的，如果能让使用频率较高的字符的编码尽可能短，这样就可以缩短整个信息通信过程中所需传送的二进制编码序列的长度，从而达到节省通信资源的目的。具体做法如下： 设需要编码的字符集合为D={d1, d2, , dn}，它们在电文中出现的次数或频率集合为W={w1,w2,,wn}，以d1, d2, , dn作为叶子结点，w1,w2,,wn作为它们的权值，构造一棵哈夫曼树，规定哈夫曼树中的左分支代表0，右分支代表1，则从根结点到每个叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，称为哈夫曼编码。【例32】给出一个字符文本： huff full luff lluhf，请给出该文本的哈夫曼编码。
图315哈夫曼树和对应的哈夫曼编码
解： 分析该文本得到字符集D={h, u, l, f}，对应的权值分别为W={2, 4, 5, 6 }，由此可得到哈夫曼树和哈夫曼编码，如图315所示。这种编码的优点是： 对于给出的文本，其编码长度是最短的； 任一字符的编码均不可能是另一字符编码的开始部分前缀。这样，两个字符之间就不需要分隔符，但是，两个词之间仍需要留空格，以起到分隔作用。其缺点是： 每个字符的编码长度不相等，译码时较困难。哈夫曼树不但可以用来编码，还可以用来解码，其解码过程正好与编码过程相反。其解码过程为： 从哈夫曼树的根结点出发，依次识别电文中的二进制编码，如果为0，则走向左孩子，否则走向其右孩子，走到叶子结点时，就可以得到相应的解码字符。具体的解码过程读者可参阅相关参考书，这里不再做深入介绍。3.2图图形结构是一种比树形结构更复杂的非线性数据结构。在树形结构中，结点中具有分支层次关系，每一层上的结点只能和上一层中的最多一个结点相关，但可能和下一层的多个结点相关。而在图形结构中，结点之间的联系是任意的，每个结点都可以与其他的结点相联系。因此，图形结构被用于描述各种复杂的数据对象，应用极为广泛，特别是近年来发展迅速，已渗入到诸如语言学、逻辑学、物理、化学、电信工程、计算机、数学及其他分支中。3.2.1图的逻辑定义下面介绍图Graph的定义及其相关术语。1. 图图G是由两个集合VG和EG组成的，记为G=V, E，其中，VG是顶点的非空有限集，EG是边的有限集合，是顶点的无序对或有序对，反映的是顶点之间的关系。根据边E的不同，图又可分为无向图和有向图。2. 无向图和边如果图中每条边都是顶点的无序对，则称此图为无向图。无向边用圆括号括起的两个相关顶点来表示。图316a所示的G1为无向图，在该图中，集合V1={v1, v2, v3, v4}，集合E1={v1, v2,v2, v3,v3, v4,v1, v4}。对于无向图而言，v1, v2与v2, v1表示同一条边。
图316图形结构示例
3. 有向图和弧如果图中每条边都是顶点的有序对，即每条边都用箭头表明了方向，则此图为有向图。有向图中的边也称弧，用尖括号括起一对顶点表示。图316b所示的G2为有向图，在该图中，V2={v1, v2, v3, v4}，集合E2={, , , , }。对于有向图而言，与表示不同的弧。4. 子图对于图G=V, E，G=V, E，若存在V是V的子集，且E是E的子集，则称图G是G的一个子图。图317分别给出了G2的三个子图。
图317图与子图
5. 带权图与边或者弧有关的数据信息称为权Weight。在实际应用中，可以为权值赋以某种具体含义。例如，在一个反映城市交通线路的图中，边
图318边上带有权值的网
上的权值可以表示该线路的长度或者等级； 对于一个电子电路图，边上的权值可以表示两个端点之间的电阻、电流或电压值等。边上带权的图称为网Network，如图318所示。6. 顶点的度在无向图中，顶点的度就是和该顶点相关联的边的数目，通常记为TDv，图316中G1图中TDv1=2。在有向图中，顶点的度具有入度与出度的区别。顶点v的入度是指以顶点为终点的弧的数目。记为IDv； 顶点v出度是指以顶点v为始点的弧的数目，记为ODv。该顶点的度ID则是此顶点的入度与出度之和，即TDv=IDv ODv。如图316中的G2，IDv1=1，ODv1=2，TDv1=IDv1 ODv1=3。7. 路径在无向图中，从顶点vi到顶点vj的路径Path是指一个顶点序列vi, vp1, vp2,, vpk, vj。其中，vi，vp1，vp1，vp2，，vpk，vj分别为图中的边，且1 k n。如果G是有向图，则路径也是有向的。路径上边的数目称为路径长度。8. 连通图与强连通图在无向图中，如果从一个顶点vi到另一个顶点vjij存在路径，则称顶点vi和vj是连通的。如果无向图中任意两个顶点都是连通的，则称该图是连通图。在有向图中，若每一对顶点vi和vj之间都存在vi到vj及vj到vi的路径，则称此图为强连通图。9. 邻接点在无向图中，如果边vi, vjE，则vi和v互为邻接点，即vi是vj的邻接点，vj也是vi的邻接点。在有向图中，如果弧E，则vj是vi的邻接点。称vi邻接到vj，或顶点vj邻接自顶点vi。3.2.2图的存储结构图是一种复杂的数据结构，主要表现在顶点之间的逻辑关系错综复杂。从图的定义可知，一个图的信息包括两部分，即图中顶点的信息以及顶点之间的联系边或者弧的信息。因此无论采用什么样的存储结构，都要完整、准确地反映这两方面的信息。所以，图存储的方法很多，需要根据具体图形和所要做的运算选取适当的存储结构。这里只讨论两种最常用的表示方法： 邻接矩阵和邻接表。1. 邻接矩阵所谓邻接矩阵储存结构就是用一个一维数组存放图中所有顶点的信息； 用一个二维数组来存放数据元素之间关系的信息即边或弧，这个二维数组称为邻接矩阵。所以这种存储形式的关键在于二维数组的构建，下面介绍该邻接矩阵的构建方法。设图G=V，E，具有n个顶点，即V={v0,v1,，vn-1}，表示G中各顶点相邻关系的邻接矩阵是一个nn的矩阵A，表示如下：
A［i,j］=1若vi,vj或是EG中的边
0若vi,vj或不是EG中的边
图319给出了图316中无向图和有向图的邻接矩阵A1和A2。
A1=0101101001011010A2=0101001000011000
图319图316中G1和G2的邻接矩阵
从图的邻接矩阵存储方法容易看出这种表示具有以下特点。1 无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上三角或下三角矩阵元素即可。2 对于无向图，邻接矩阵的第i行或第i列非零元素或非元素的个数正好是第i个顶点的度TDvi。3 对于有向图，邻接矩阵的第i行或第i列非零元素或非元素的个数正好是第i个顶点的出度ODvi［或入度IDvi］。4 用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连； 但是要确定图中有多少边，则必须按行、按列对每个元素进行检测，所花费时间代价很大； 同时，使用两个数组分别存储图的顶点信息和关系信息，空间消耗也比较大，这是用邻接矩阵存储图的局限性。若G是网，则邻接矩阵可定义为：
A［i,j］=Wij若vi,vj或是EG中的边
0或若vi,vj或不是EG中的边
其中，Wij表示边vi，vj或上的权值； 表示一个计算机允许的、大于所有边上权值的数。2. 邻接表邻接表是一种顺序分配和链式分配相结合的存储结构。它包括两个部分： 一部分是链表； 另一部分是向量。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点包含了顶点vi的所有邻接顶点。在邻接表中一般首先为每个顶点都附设一个顶点结点，作为链表的起始结点，顶点结点的结构如图320a所示。而每个链表除了顶点结点外，还需要普通的链表结点，普通的链表结点结构如图320b所示。
顶点域边头指针域
vexdatafirstarc
（a） 顶点结点结构
邻接点域数据域指针域
adjvexdatanextarc
（b） 表结点结构
图320邻接表的结点结构
图320中，顶点结点由顶点域vertex，该域给出的是顶点的信息和指向第一个邻接点的指针域firstarc构成； 另一种是表结点，它由邻接点域adjvex，给出的是邻接点在图中的位置和指向下一条邻接边的指针域next构成。对于网的边表需要再增设一个存储边上权值的数据域data，该域存储权值信息，如果权值为1，该域可以省略。因此，图316中的无向图G1和有向图G2的邻接表存储结构如图321所示。
图321图316中G1和G2的邻接表
从邻接表的存储结构中可以发现，若无向图中有n个顶点、e条边，则它的邻接表中含有n个顶点结点和2e个表结点。在无向图的邻接表中，顶点v1的度恰为第i个链接表中的结点数； 而在有向图中，第i个链接表中的结点个数只是顶点v1的出度，而要求入度，必须遍历整个邻接表。在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点，若要判定任意两个顶点之间是否有边或弧相连，则需搜索第i个或第j个链表，这一点不及邻接矩阵方便。3.2.3图的遍历方法与树的遍历操作功能相似，图的遍历是指从图中的任一顶点出发，访问图中所有顶点，且保证每个顶点仅访问一次。图的遍历是图的一种基本操作，图的许多其他操作都是建立在遍历操作的基础之上的。由于图本身结构的复杂性，因此图的遍历操作也较复杂，主要表现在以下几个方面。（1） 在图中，没有一个确定的首结点，任意一个顶点都可以作为遍历的第一个结点。（2） 在图中，一个顶点可以和其他多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。（3） 在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点，因此需要着重考虑如何保证每个顶点仅访问一次。（4） 在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中其余的连通分量。图的遍历通常有深度优先搜索Depth_First Search, DFS和广度优先搜索（Breadth_First Search，BFS）两种方式，下面分别介绍。1. 深度优先搜索深度优先搜索遍历类似于树的先序遍历，是树的先序遍历的推广，其基本思想为假设初始状态是图中所有顶点未曾被访问，则深度优先所搜可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径的顶点都被访问，然后重复上述过程，直到图中所有顶点都被访问到为止。具体的遍历步骤如下。1 访问图G的指定起始点v1。2 从v1出发，访问一个与v1邻接的顶点w1后，再从w1出发，访问与w1邻接且未被访问过的顶点w2。从w2出发，重复上述过程，直到遇到一个所有与之邻接的顶点均被访问过的顶点为止。3 沿着刚才访问的次序，反向回退到尚有未被访问过的邻接点的顶点，从该顶点出发，重复步骤2、3，直到所有被访问过的顶点的邻接点都已被访问过为止； 若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。【例33】已知图的邻接表存储结构如图322所示，以顶点v1为始点，按深度优先搜索遍历该图中，写出顶点的遍历序列。
图322图的邻接表及其深度优先搜索序列
解： 先访问v1，再访问v1的第一个邻接点v2，再访问v2的第一个邻接点v4，再访问v4的第一个邻接点v2，因v2已被访问过，则访问v4的下一个邻接点v3，然后依次访问v7，v6。这时，与v6相邻接的顶点均已被访问，于是反向回到v4去访问与v4相邻接且尚未被访问的v5，至此，全部顶点均被访问。相应的访问序列为： v1v2v4v3v7v6v5。显然，这是一个递归的过程，需要递归遍历当前访问顶点的所有邻接点。而遍历规定，每个顶点只能被访问一次，因此，为了在遍历过程中便于区分顶点是否已被访问，需附设访问标志数组visited［n］，其初值为0，一旦某个顶点被访问，则其相应的分量置为1。下面给出图的深度优先搜索的C语言算法，该算法假设图采用的是邻接表的存储结构。算法35： 以图的邻接表为存储结构的深度优先搜索算法该算法分为两部分，一部分是深度优先搜索算法DFS函数； 另一部分是遍历函数DFSTraver，在遍历函数中调用了DFS函数
#defineVTXUNM 10 *假设图中顶点个数的最大可能值为10*
struct arcnode
{*定义表结点结构*
int adjvex;
float data;
struct arcnode *nextarc;
} arcnode;
typedef struct arcnode ARCNODE;
struct headnode
{*定义顶点结点结构*
int vexdata;
ARCNODE *firstarc;
} headnode;
struct headnode G［VTXUNM］;
int visited［VTXUNM］;
void dfs struct headnode G［］, int v
{
struct arcnode *p;
printf"%d-", G［v］.vexdata; *访问顶点v*
visited［v］=1;*标记顶点v已经被访问*
p=G［v］.firstarc;*读取顶点v的第一个邻接点的指针*
while p!=NULL*当邻接点存在时*
{
if visited［p-adjvex］==0
dfsG, p-adjvex;
p=p-nextarc;*找下一个邻接点*
}
}
void DFSTraverstruct headnode G［］
{
int v;
forv=0;v", G［v］.vexdata;
visited［v］=1;
rear=rear 1% VTXUNM;
queue［rear］=v;*访问过的顶点进队列*
while rear!=front
{
front=front 1% VTXUNM;
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=rear 1% VTXUNM;
queue［rear］=p-adjvex;
}
p=p-nextarc;
}
}
}
分析上述算法，每个顶点至多进一次队列，因此广度优先搜索遍历图的过程实质是通过边或弧找邻接点的过程，因此广度优先遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。3.2.4图的连通性与最小生成树前面介绍的图的遍历算法是解决图的应用问题的基础，本节将介绍利用图的遍历算法来判断一个图的连通性问题，重点讨论无向图的连通性、有向图的连通性、由图得到其生成树或生成森林以及连通图的最小生成树（Minimum Spanning Tree，MST）问题。1. 图的连通性根据图的连通性的定义，对于连通图，仅需从图中任一顶点出发，进行深度优先搜索或广度优先搜索只需调用一次DFS或BFS算法，便可访问到图中所有顶点； 而对非连通图，则需从多个顶点出发进行搜索需调用多次DFS或BFS算法。每次从一个新的顶点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。图323中的无向图G21是由两个连通分量构成的非连通图，按照深度优先搜索遍历需要从顶点v1和v4出发，调用两次DFS算法。
图323非连通无向图及其连通分量
对于有向图而言，深度优先搜索是求其强连通分量的一个有效方法，求有向图的强连通分量的算法主要有Kosaraju算法、Gabow算法和Tarjan算法，其中Kosaraju算法要对原图和逆图都进行一次DFS，另外两种只要一次DFS就可以，具体的算法思想读者可以参阅相关文献，本书不再做详细介绍。2. 生成树和生成森林生成树： 若图是连通图，从图中的某一个顶点出发进行遍历时，可以系统地访问图中所有顶点，此时图中所有的顶点加上遍历时经过的边所构成的子图，称为连通图的生成树。并且称由深度优先搜索得到的生成树为深度优先生成树； 由广度优先搜索得到的生成树为广度优先生成树。由此可以得到图322中的图的深度优先生成树和广度优先生成树如图324所示。
图324图322中所示图的生成树
对于非连通图，遍历过程会得到多个连通分量，每个连通分量中的顶点集和遍历时走过的边一起构成若干棵生成树，这些生成树组成非连通图的生成森林。生成树和生成森林具有如下特点：1 有n个顶点的连通图，其生成树有n-1条边；2 生成树中不含回路；3 对于给定的图，其生成树或者生成森林不是唯一的，因为起点不同，访问的路径也不同。3. 最小生成树最后我们来讨论如何在一个带有权值的无向图中找出其最小生成树。生成树各边上的权值之和，称为生成树的代价，使代价最小的生成树，称为最小代价生成树，简称最小生成树。图325给出了一个最小生成树的示例。
图325最小生成树示例
最小生成树在实际生活中应用非常广泛。例如，要用最少的电线给一个房子安装电路，求解电路安装图的过程就是一个求解最小生成树的过程； 再如要建n个城市之间的通信联络网，若以n个城市做图的顶点，n-1条线路做图的边，每条线路建造需付出一定代价相当于边上的权，那么对n个顶点的连通网可以建立许多不同的生成树，每棵生成树都可以是一个通信网，我们当然希望选择一个总耗费最小的生成树就是一个可行的方案。最小生成树具有如下最基本的性质： 设G=V, E是一个连通图，U是顶点集V的一个真子集，若u, v是一条具有最小权值的边，其中uU，vV-U，则一定存在G的一棵最小生成树包含边u, v。而构造最小生成树的原则如下。1 尽可能选权值小的边，但不构成回路。2 在网中选n-1条边以连接网中的n个顶点。通常求最小生成树的算法有两种： Prim算法和Kruskal算法，这里不再介绍，有兴趣的读者可参阅相关参考书。习题31试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
图326题32图
32已知二叉树如图326所示，试用顺序存储和二叉链表两种方式给出存储结构，并分别给出该二叉树的先序、中序和后序遍历序列。33现有以下按先序和中序遍历二叉树的结果，问这样能否唯一地确定这棵二叉树的形状？为什么？如果能请画出该二叉树。如果给出的是先序和后序遍历能否唯一确定该二叉树？先序： ABCDEFGHI中序： BCAEDGHFI34假设二叉树采用二叉链表作为存储结构，编写计算二叉树中叶子终端结点数目的递归算法。35假设二叉树采用二叉链表作为存储结构，试编写一个判断该二叉树是否为完全二叉树的算法。36请画出图327中三棵树所对应的二叉树，并给出该森林所对应的二叉树，并给出该二叉树的先序和后序遍历序列。37什么叫哈夫曼树？给出一组权值{6，9，2，5，4，8}，请建立一棵哈夫曼树，并给出按照该哈夫曼树得到的哈夫曼编码。38有向图如题图328所示，请给出该图的邻接矩阵和邻接表，并求出各个顶点的度。
图327题36图
图328题38图
39已知某无向图的邻接矩阵为0110000100100010010010110110000100000010010010010，请画出该无向图，给出各个顶点的度，并画出该图的邻接表，分别给出从第一个结点出发的广度和深度优先生成树。
|
|
購物車/收銀台(
0
) | 在線留言板
| 付款方式
| 運費計算
| 聯絡我們
| 幫助中心 |
加入書簽
HOME
新書上架
