1.4 树与二叉树 1.树的基本概念

树（tree）是一种简单的非线性结构。在树这种数据结构中，所有数据元素之间的关系具有明显的层次特性。

2.二叉树的定义及其存储结构 （1）二叉树的定义 二叉树具有以下两个特点： ①非空二叉树只有一个根结点；

②每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。 （2）二叉树的存储结构

在计算机中，二叉树通常采用链式存储结构。在二叉树中，由于每一个元素可以有两个后件（即两个子结点），因此，用于存储二叉树的存储结点的指针域有两个：一个用于指向该结点的左子结点的存储地址，称为左指针域；另一个用于指向该结点的右子结点的存储地址，称为右指针域。 3.二叉树的遍历

二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历可以分为： ①前序遍历（DLR）

首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。 ②中序遍历（LDR）

首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。 ③后序遍历（LRD）

首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。

1.5 查找技术和排序技术 1.查找技术

查找是数据处理领域中的一个重要内容，查找的效率将直接影响到数据处理的效率。 （1）顺序查找

在进行顺序查找过程中，如果线性表中的第一个元素就是被查找元素，则只需做一次比较就查找成功，查找效率最高；但如果被查的元素是线性表中的最后一个元素，或者被查元素根本不在线性表中，则为了查找这个元素需要与线性表中所有的元素进行比较，这是顺序查找的最坏情况。在平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中一半的元素进行比较。 （2）二分法查找

二分法查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列。对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较而顺序查找需要比较n次。 2.排序技术 （1）交换类排序法

交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序法与快速排序法都属于交换类的排序方法。假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-1)/2。在快速排序过程中，随着对各子表不断地进行分割，划分出的子表会越来越多，但一次又只能对一个子表进行再分割处理，需要将暂时不分割的子表记忆起来，这就要用一个栈来实现。 （2）插入类排序法

次，

插入排序是指将无序序列中的各元素依次插入到已经有序的线性表中。在简单插入排序法中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要n(n-1)/2次比较。 （3）选择类排序法

选择排序法的基本思想是扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置）；然后对剩下的子表采用同样的方法，直到子表空为止。简单选择排序法在最坏情况下需要比较n(n-1)/2次。

第2章 程序设计基础 2.1 程序设计方法与风格

程序设计是一门技术，需要相应的理论、技术、方法和工具来支持。就程序设计方法和技术的发展而言，主要经过了结构化程序设计和面向对象的程序设计阶段。程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。著名的“清晰第一，效率第二”的论点已成为当今主导的程序设计风格。要形成良好的程序设计风格，应注重和考虑这些因素：①源程序文档化；②数据说明的方法；③语句的结构；④输入和输出。

2.2 结构化程序设计 1.结构化程序设计的原则

结构化程序设计方法的主要原则可以概括为自顶向下，逐步求精，模块化，限制使用goto语句。

2.结构化程序设计的基本结构与方法的应用

结构化程序设计的三种基本结构分别是：顺序结构、选择结构和循环结构。 在结构化程序设计的具体实施中，要注意把握如下要素：①使用程序设计语言中的顺序、选择、循环等有限的控制结构表示 程序的控制逻辑；②选用的控制结构只准许有一个入口和一个出口；③程序语句组成容易识别的块，每块只有一个入口和一个出口；④复

杂结构应该用嵌套的基本控制结构进行组合嵌套来实现；⑤语言中所没有的控制结构，应该采用前后一致的方法来模拟；⑥严格控制goto语句的使用。

2.3 面向对象的程序设计 1.关于面向对象方法

面向对象方法的优点：①与人类习惯的思维方法一致；②稳定性好；③可重用性好；④易于开发大型软件产品；⑤可维护性好。 2.面向对象方法的基本概念

①面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。通常把对象的操作称为方法或服务。②属性即对象所包含的信息，它在设计对象时确定，一般只能通过执行对象的操作来改变。③对象的基本特征有：a.标识惟一性；b.分类性；c.多态性；d.封装性；e.模块独立性好。④继承是使用已有的类定义作为基础建立新类的定义技术。广义地说，继承是指能够直接获得已有的性质和特征，而不必重复定义它们。 继承分为单继承与多重继承。⑤多态性是指子类对象可以像父类对象那样使用，同样的消息既可以发送给父类对象也可以发送给子类对象。

第3章 软件工程基础 3.1 软件工程基本概念 1.软件定义与软件危机

（1）软件的定义：软件是与计算机操作相关的计算机程序、规程、规则，以及可能有的文件、文档及数据。软件的三个要素：程序、数据和文档。

（2）软件分类：软件按功能可分为应用软件、系统软件和支撑软件（或工具软件）三大类。