在当今社会，计算机技术已经渗透到生产和生活的方方面面，掌握基本的计算机软硬件技术已经成为工科非计算机专业大学生求职的必备要求。本书针对工科非计算机专业本科生的需要，是一本有关计算机软件知识及开发技术的基础教材，主要讲授计算机软件的基本概念、方法及实用技术，书中内容涉及数据结构、数据库技术、操作系统和软件工程。本书除了理论知识的介绍外，还注重读者实际编程和动手能力的提高，注重理论和实践的联系，主要特色如下。
(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)是包含n(n≥0)个结点的有穷集合。N=0时称为空树，否则任何一个非空树都满足如下条件：
（1） 有且仅有一个特定结点被称为根结点(Root)；
（2） 除根结点之外的其余数据元素被分为m(m≥0)个互不相交的集合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－1(i≥1)。
证明： 该性质可由数学归纳法，根据二叉树的定义来证明。
【性质3.2】一棵深度为k的二叉树中，*多具有2k－1(k≥1)个结点。
证明： 在深度为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个孩子，因此二叉树中的孩子结点数为n1 +2n2；
(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个结点的二叉树称为满二叉树，即该满二叉树中的结点数为*大值。图33(a)给出了一棵深度为4的满二叉树，这种二叉树的特点是所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上。
图33深度为4的满二叉树
可以对满二叉树的结点自上而下、自左而右进行连续编号，约定编号从根结点起，编号结果如图33(b)所示。由此可引出完全二叉树的定义如下： 深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。图34给出了一个深度为4的完全二叉树。
图34深度为4的完全二叉树
由此可以总结出完全二叉树和满二叉树的特点如下。
（1） 完全二叉树的叶子结点只能出现在*下层和次下层，且*下层的叶子结点集中在树的左部。
（2） 一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。
下面证明性质3.4： 设一棵完全二叉树的深度为k，结点个数为n，则根据完全二叉树的定义和性质3.2可知，结点的个数n要位于深度为k-1层和k层的*大结点数之间，即
2k－1≤n<2k
对不等式两边同取对数可得
k－1≤lbn
又因为k-1和k是相邻的两个整数，所以
k－1=lbn
由此性质3.4得证，即k=lbn+1。
【性质3.5】对于具有n个结点的完全二叉树，如果按照从上至下，同一层按照从左到右的顺序对二叉树的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有如下性质。
(1) 如果i=1，则结点i是二叉树的根，该结点无双亲； 如果i>1，则序号为i的结点的双亲结点序号为i/2。
(2) 如果2i>n，则结点i无左孩子，否则其左孩子结点的序号为2i。
(3) 如果2i+1>n，则结点i无右孩子，否则其右孩子结点序号为2i+1。
此性质可采用数学归纳法证明。
3.1.3二叉树的存储结构
二叉树的存储方式主要有顺序存储和链式存储两种方式，下面进行详细介绍。
1. 二叉树的顺序存储
所谓二叉树的顺序存储，就是用一组连续的存储单元，按照从上至下、从左到右的顺序依次存放二叉树中的结点。因此，依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以*地反映出结点之间的逻辑关系。图34中的完全二叉树的顺序存储结构如图35所示。
……
新书资讯