计算机文化基础-第7章程序设计基础与基本数据结构

1、计算机基础南京信息工程大学滨江学院南京信息工程大学滨江学院计算机系计算机系计算机基础课程组计算机基础课程组第7章 程序设计基础与基本数据结构南京信息工程大学滨江学院南京信息工程大学滨江学院计算机系计算机系南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系程序设计方法学教 学 目 标1结构化程序设计方法和面向对象程序设计方法2程序的本质3简单数据结构-线性表、树4查找与排序53 通过学习能初步具备程序设计相关的理论知识和目前主流的程序方法；理解程序的本质“算法+数据结构”，初步掌握简单基本的线性和非线性数据结构，以及在查找和排序上的简单应用。南京信息工程大学滨江学院计算机系南京信息

2、工程大学滨江学院计算机系教学重点和难点算法的描述流程图12二叉树的表示及遍历3简单查找与二分法查找4基本排序算法与堆排序54栈和队列的操作及简单应用南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系5章节安排l 7.1 程序设计基础l 7.1.1 程序设计方法学与风格l 7.1.2 结构化程序设计l 7.1.3 面向对象的程序设计l 7.2 基本数据结构l 7.2.1 算法与数据结构l 7.2.2 基本线性数据结构l 7.2.3 基本非线性数据结构l 7.2.4 基本数据结构的应用l 7.3 小结l 7.4 习题7.1 程序设计基础南京信息工程大学滨江学院计算机系南京信息工程大学

3、滨江学院计算机系72022-5-262022-5-267.1.1. 程序设计方法学与风格l 程序是用来控制计算机操作的一系列代码。而程序设计目的是利用计算机对现实问题进行求解。l 计算机科学家、图灵奖获得者尼克劳斯威茨教授对程序进行了经典定义：程序=算法+数据结构l 随着软件产业的迅猛发展和软件开发的工程化日趋完善，程序与软件开发环境的关系越来越紧密，开发工具的选择对程序的开发效率有着非常大的影响，有时会起到事半功倍的效果。对程序的定义进行了扩充： 程序=算法+数据结构+开发环境南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系82022-5-262022-5-261. 程序设计

4、方法学与风格l 程序设计方法学是探讨程序设计的理论和方法的学科。用以指导程序设计各阶段工作的原理和原则，以及依此提出的设计技术。l 程序设计方法学的目标是能设计出可靠、高效、易读而且代价合理的程序。更通俗地说，什么样的程序是一个“优秀”的程序，怎样才能设计出“优秀”的程序。l 程序设计的一般过程应包括：分析实际问题并抽象，利用数学建模技术构建问题的数学模型，借助计算方法和数据模型构造合适数据结构，进而设计算法，最后借助计算机语言实现算法形成程序。南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系2. 源程序编写的一般规范l 良好的程序设计风格可以使程序结构清晰合理，使程序代码易于

5、测试和维护。l 程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路，为了测试和维护程序，往往还要阅读和跟踪程序，因此程序设计的风格总体而言应该强调简单和清晰。92022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系2. 源程序编写的一般规范1）标识符命名及书写规则（1）规范的基本要求（2）特殊约定（3）源代码文件标识符命名规则2）注释及格式要求3）缩进规则4）代码的排版布局 102022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系7.1.2 结构化程序设计l 迪克斯特拉（E. W. Dijkst

6、ra）在1969年提出了结构化程序设计方法，是以模块化设计为中心，将待开发的软件系统划分为若干个相互独立的模块，这样使每一个模块的完成变得简单且明确，为设计一些较大的软件打下了良好的基础。l 程序的顺序、选择和循环三种控制流程，这就是结构化程序设计方法强调使用的三种基本结构。l 结构化程序设计的基本思想是采用“自顶向下，逐步求精”的程序设计方法和“单入口单出口”的控制结构。112022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 结构化程序设计具有以下优点：整体思路清楚，目标明确。设计工作中阶段性非常强，有利于系统开发的总体管理和控制。在系统分

7、析时可诊断出原系统中存在的问题和结构上的缺陷。l 程序设计步骤：（1）分析问题。（2）建立数学模型。（3）选择算法。（4）编写程序。（5）调试运行。（6）分析结果。（7）写出程序的文档。l 【例7-1】输出2到N之间的素数（质数）。122022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系7.1.3 面向对象的程序设计l 面向对象就是基于对象概念，以对象为中心，以类和继承为构造机制，来认识、理解、刻画客观世界和设计、构建相应的软件系统。l 对象（Object）是一个现实实体的抽象。一个对象可被认为是一个将数据（属性）和程序（方法）封装在一起的实体，

8、程序用来刻画该对象的动作或对它接收到的外界信号的反应，这些对象操作有时称为方法。132022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 类是构成面向对象程序设计的基础，它把数据和函数封装在一起，是具有相同操作功能和相同数据格式（属性）的对象抽象，它可以被看作抽象数据类型的具体实现。l 类与对象的关系：类是用户自定义的数据类型，是用来描述只有相同属性和方法的对象集合，它定义了该集合中每个对象所共有的属性和方法，对象是类的实例。例如，苹果是一个类，而放在桌上的那个苹果则是一个对象。142022-5-262022-5-26南京信息工程大学滨江学院计

9、算机系南京信息工程大学滨江学院计算机系l 面向对象的基本特征（1）对象唯一性（2）抽象性（3）封装性（4）继承性（5）多态性152022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 与结构化程序设计方法的比较： 结构化设计方法中，程序被划分成许多个模块，这些模块被组织成一个树型结构；并且数据和对数据的操作（函数或过程）是完全分离的。 在面向对象程序设计中，倒转这种依赖关系，创建的抽象不依赖于任何细节，而细节则高度依赖于上层的抽象；更为重要的是将数据与对数据的操作封装在一起构成一个整体。 162022-5-262022-5-26南京信息工程大学滨

10、江学院计算机系南京信息工程大学滨江学院计算机系172022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 面向对象的程序设计过程，应包括基本步骤：（1）分析问题 （2）建立数学模型（3）类的构建 （4）编写程序（5）调试运行 （6）分析结果（7）写出程序的文档。l 【例7-2】时钟类182022-5-262022-5-267.2 基本数据结构南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系202022-5-262022-5-267.2.1.算法与数据结构l 算法提出了计算机对数据的操作过程或步骤，程序就是设计什么算法对数据进行处理

11、，而数据通过其数据结构剖析其内在关系与存储方式，也就是说，程序是对按一定存储方式和具有某些相关关系的数据，用某种操作方式进行处理的一系列步骤。l 算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程（计算的方法）。其具备的四个基本特征为：（1）可行性。（2）确定性。（3）有穷性。（4）拥有足够的情报。南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系1. 流程图及其表示l 算法的基本要素： 一是对数据对象的运算和操作； 二是算法的控制结构。l 算法的表示是指有效、简洁地描述一个计算机求解过程。常见的算法表示方法有：自然语言表示方法、传统流程图、

12、N-S 结构化流程图、算法描述语言等。212022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系222022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 顺序结构232022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 选择(分支)结构242022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 循环结构252022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机

13、系 2. N-S图及其表示l N-S流程图，是对传统流程图的改造。与上节传统流程图的最大区别是不允许使用流程线，带来的好处是使流程更加规范，流程更清晰，避免了频繁使用流程线导致流程凌乱的弊端。特别是当求解问题相对复杂时，必然导致传统流程图复杂和凌乱，此时建议采用N-S流程图更为合适；简单的流程图两者皆可，依程序员的喜好而定。262022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 顺序结构 选择结构272022-5-262022-5-26l 循环结构南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系3. 算法设计方法l 【例7-3

14、】写一个算法输入南京市2014年7月份每天的平均气温，求出这个月的平均气温并输出。l 算法设计的基本方法l （1）枚举法：根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。枚举法也称穷举法或列举法，虽然有点笨但也是一种有效且可靠的方法，有时可以解决常规方法不易解决的问题。282022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l （2）归纳法：通过列举少量的特殊情况，经过分析，最后找出一般的关系。l （3）递推：指从已知的初始条件出发，依次推出所要求的各中间结果和最后结果。l （4）递归：将问题层分解的过程

15、，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。递归分为直接递归与间接递归两种。292022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 递归是一种很重要的算法设计方法之一。实际上，递归过程能将一个复杂的问题归结为若干个较简单的问题，然后将这些较简单的每一个问题再归结为更简单的问题，这个过程可以一直做下去，直到最简单的已知问题为止。l 递推与递归的实现方法是大不一样的。递推是从初始条件出发，逐次推出所需求的结果；而递归则是从未知出发，一直推到递归出口为止。通常，递归算

16、法要比递推算法清晰易读，其结构更加简练。302022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l （5）减半递推技术 ：对问题分而治之的方法称为分治法。工程上常用分治法是减半递推技术。l （6）回溯法：通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再逐步试探。312022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系4. 算法的度量l 算法的复杂度：包括算法的时间复杂度和算法的空间复杂度两个方面。l （1）算法的时间

17、复杂度：是指执行算法所需要的计算工作量。 算法的时间复杂度=T(n)，n为问题的规模。 常用量级相同的函数f(n)来表示，并记为T(n)=O(f(n)。常见的f(n)函数有1、log2n、n、nlog2n、n2、n3和2n不同情况，且量级关系如下：O(1) O(log2n ) O(n ) O(nlog2n )O(n2) O(n3) O(2n)；其中O(1)表示常量时间，与问题规模n无关。322022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系332022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l

18、 （2）算法的空间复杂度 一个算法在计算机存储器上所占用的存储空间是指执行这个算法所需要的存储空间，包括输入输出数据所占用的存储空间、算法程序占用的存储空间及算法执行过程中所需要的额外空间。 所谓算法的空间复杂度算法通常被定义为在执行过程中临时占用的存储空间。算法的空间复杂度也用数量级的形式给出，常记为： S(n)O(f(n)，其中，n为问题的规模。342022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系5. 数据结构l 数据结构是指相互有关联的数据元素的集合。l 数据结构是研究数据和数据之间关系的一门学科，它包括三个方面内容：数据集合中各数据元

19、素之间所固有的逻辑关系，即数据的逻辑结构；在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；对各种数据结构进行的运算。352022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构，而不管其在计算机中的存储表示方式。数据的逻辑结构通常以（D，R）二元组来表示：D表示数据元素的信息；R表示各数据元素之间的逻辑关系。数据的逻辑结构按数据间对应关系可分为：线性结构（一对一关系）、树型结构（一对多关系）和图型结构（多对多关系）；通常后两种又统称为非线性结构。362022-5-26202

20、2-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 3）存储结构 ：是指数据结构在计算机存储空间中的具体实现。计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，并且各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的，而且一般也不可能相同。l 常见的存储结构有：顺序存储结构、链式存储结构和索引存储结构。372022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 4）数据的运算 数据的运算是定义在数据的逻辑结构上的，但运算的具体实现要在存储结构上进行。数据的各种逻辑结构有相应的各种

21、运算，每种逻辑结构都有一个运算的集合。常用的运算有检索、插入、删除、更新、排序等。数据的运算是数据结构的一个重要方面，讨论任何一种数据结构时，都离不开对该结构上的数据运算及实现算法的讨论。382022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系7.2.2 基本线性数据结构l 介绍一种最简单且最常用的线性数据结构，包括线性表和特殊线性表两部分；其中特殊线性表是线性表的特例，包括栈和队列。首先分别给出各自的概念；然后介绍它们的存储结构及其主要运算。392022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系

22、1.线性表l 线性表是由n(n0)个数据元素组成的一个有限序列，常记为： （a1，a2，a3，ai-1，a i，a i+1，an）l 一般地，线性表的逻辑结构（D，R）二元组如下：D ai | ai ElemSet, i=1,2,.,n, n0 ；R |ai-1 ,aiD, i=2,.,n 。【例7-7】某班级C语言程序设计课程的考试成绩组成的一个线性表： (50，73，65，97，79，58，87，80，91，85)其中：每个数据元素为考生的成绩，成绩的线性表中共有10个数据元素。402022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 线性

23、表的存储结构按存储方式进行划分，线性表的存储结构可分为顺序存储结构和链式存储结构两种。（1）线性表的顺序存储结构l 将线性表存储在计算机中，最简单最常用的方法是占用一块连续的内存存储单元区，将表中的各数据元素依次存入一块连续存储区中。线性表顺序存储所需的存储空间取决于线性表的长度以及每个数据元素所占的字节数。412022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系422022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l （2）线性表的链式存储结构链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻

24、，而且各数据元素的存储顺序也是任意的，各数据元素的先后关系是由各结点的指针域指示，线性表的链式存储结构又称为线性链表。链式存储结构的特点是每一个存储结点不仅存储结点的值，而且存储结点之间的前后关系。432022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系442022-5-262022-5-26l 为了增加链表方式线性表的访问灵活性，引入循环链表、双向链表、双向循环链表等。南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 线性表的操作：包括线性表的创建、更新、查找和遍历等。因线性表的存储方式不同，各操作的实现方式也不尽相同。下面针

25、对线性表更新操作类中的插入和删除两个重要操作，分别就不同的存储方式进行一一介绍。l （1）顺序存储方式下的插入与删除操作首先，介绍顺序存储方式下的插入操作。插入操作是指在现有线性表中添加一个新的数据元素到指定的位置，形成一个新的线性表。452022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l （2）链式存储方式下的插入与删除操作 考虑到线性表的链式存储方式除了单链表之外，还有循环链表、双向链表、双向循环链表等；在此，仅讨论单链表方式的线性表，其它类似处理。l 线性表的应用 比如建立一个含有多人的通信录，可采用之前介绍的顺序存储和链式存储都可以实

26、现，考虑到通讯录不可避免的要经常进行插入和删除等操作，因此优先采用链式存储方式。除此之外，像多项式的相加和相乘运算、两个数据序列的合并、集合的运算以及计算机的事务处理都可采用线性表来实现。462022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系 2. 栈和队列l 栈（Stack）和队列（Queue）是只能进行特殊存取、插入、删除操作的线性表。在物理存储上，通常采用连续内存空间存储。当然，也可用链式存储，但对其进行操作时，却不能向顺序存储线性表那样任意操作。因此，栈和队列是两种特殊的操作受限的线性表。l 1）栈 栈是一种满足“后进先出（Last I

27、n First Out，简称LIFO）”特性的特殊线性表，是使用最为广泛的线性数据结构之一。472022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 栈是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶（top），表头称为栈底（bottom）。表中无元素时称为空栈。元素按a1，a2，a3，ai，an的顺序依次入栈，a1为栈底元素。再有新元素入栈要置于an之上，删除或出栈必须先对an进行操作。栈顶减去栈底加1为栈的长度。栈的物理存储可采用顺序存储结构，也可采用链表存储结构。482022-5-262022-5-26南京信息工程大学滨江学院计算机

28、系南京信息工程大学滨江学院计算机系l 栈的基本操作 包括：创建空栈、判定栈是否为空、入栈、出栈以及读取栈顶元素等。由于栈的本身特性，决定了栈的入栈和出栈等基本操作不需要移动栈中其他数据元素；因此，不难得出，栈常使用顺序存储方式进行物理存储。下面以顺序存储实现的栈（简称顺序栈）来介绍最为重要的入栈、出栈、取栈顶元素三个基本操作。492022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 2）队列队列是一种满足“先进先出（First In First Out，简称FIFO）”特性的特殊线性表，又一使用最为广泛的数据结构之一。l （1）队列的概念队列（

29、Queue）是限定所有的插入只能在表的一端进行，而所有的删除都是在表的另一端进行的线性表。表中允许插入的一端称为队尾（Rear），允许删除的一端称为队头（Front）。502022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 如图7-15所示的队列中，a1是队头元素，an是队尾元素，队列中元素以a1，a2，a3，ai，an的次序依次进入队列，则a1是第一个出队列的元素，即队列的操作是按“先进先出”的原则进行的。队尾减去队头加1为队列的长度。队列的物理存储可采用顺序存储结构，也可采用链表存储结构。512022-5-262022-5-26南京信息工

30、程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l （2）队列的基本操作 包括：创建空队、判定队列是否为空、入队、出队以及读取队头元素等。由于队列的本身特性，决定了队列的入队和出队等基本操作不需要移动队列其他数据元素；因此，不难得出，队列也常使用顺序存储方式进行物理存储。下面以顺序存储实现的队列（简称顺序队列）来介绍最为重要的入队、出队、取队头元素三个基本操作。522022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l （3）循环队列及其基本运算由于顺序队列的入队和出队操作是在两端进行的，若顺序队列不做特殊的处理和考虑，队列长度的设置就变得

31、非常困难。当队列进行删除操作时，由于只能在队头进行，因而删除后的元素所占存储单元就被空置了，而进行入队时，只能在队尾进行，这样当频繁地进行入队和出队操作时，在队头由于多次删除数据，因而空了许多存储单元，而在队尾进行插入时，可能最后没有空间了，这就出现无法再入队新元素，而此时在队头又有许多出队后留下的可用空间，即所谓的队列假溢出情况。532022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系542022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系7.2.3 基本非线性数据结构l 基本非线性数据结构包括树

32、和图两大类。树表示的是事物间的层次关系，一对多的关系；而图表示的是事物间的网状关系，多对多的关系。l 根据大纲要求，仅介绍基本非线性数据结构中的树形结构。l 树型结构是一类应用十分广泛和重要的非线性数据结构。它很像自然界中的树，有根、叶和枝。例如家谱以及行政组织等，都是常见的树结构实例。树中的每一个结点可以有n（n0）个直接后继结点，除根以外任一结点有且仅有一个直接前趋结点，树型结构是以结点间分支关系定义的层次结构。552022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系1. 树的定义l 树（tree）是n（n0）个结点的有限结合T。当n=0时，

33、称为空树。否则，在任一非空树中，它满足以下两个条件：有且仅有一个特定的结点称为根结点；其余结点分为m（m0）个互不相交的有限集合T1、T2、Tm，其中每个结合Ti（0im）又都是一棵树，并称其为根的子树。 这是一个递归定义，即在树的定义中又引用了树的定义，这种定义符合树的固有特性。树中每一个结点都是该树中某一棵子树的根。562022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 下面给出树结构中的一些基本术语。结点的度：树中每个结点的子树个数称为结点的度（degree）。树的度：树中各结点度的最大值称为树的度。叶子：度为0的结点称为叶子或终端结点

34、。分支结点：度不为0的结点，称为分支结点或非终端结点。孩子结点和双亲结点：结点的子树的根又可称为该结点的孩子结点（child）；相应地，该结点称为孩子的双亲结点（parent）。572022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系兄弟结点：同一个双亲的孩子之间互称兄弟结点。祖先结点：一个结点的祖先是从根到该结点所经分支上所有结点。子孙结点：一个结点的子孙是其子树中的所有结点。结点的层次：结点的层次从根开始定义，根为第一层，根的孩子为第二层，以此类推。树的深度或高度：树中结点的最大层次称为树的深度或高度。582022-5-262022-5-26

35、南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系592022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 森林（forest）是m（m0）棵互不相交的树的集合。森林的概念与树非常接近。只要把一棵树的根结点去掉，就可以改变成森林。反之，如果要把由m棵互不相交的树组成森林，则加上一个结点，使这m棵树的根作为该结点的孩子，则使森林变成树。602022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系2.二叉树的定义及其存储结构l 二叉树（binary tree）是有限个结点的集合，它或者为空集

36、，或者是由一个根结点以及两棵互不相交且分别称为根的左子树和右子树的二叉树组成的。这是二叉树的递归定义。若二叉树为空集，则称之为空二叉树。二叉树的每个结点至多只有二棵子树（即二叉树中各结点的度不大于2），且其子树有左右之分，同时这种次序是不能任意颠倒的。612022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 2）二叉树的性质性质1：位于二叉树第i层上的结点最多为2i-1个（i1）。性质2：深度为K的二叉树的结点总数最多为2K-1个（K1）。性质3：对于任一非空二叉树BT，如果其叶子数（度数为0）为n0个，度为2的结点数为n2个，则有n0=n2+

37、1成立。622022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 满二叉树：一棵深度为K且有2K-1个结点的二叉树为满二叉树。这种树的特点是每一层上的结点数都是最多结点数。若对满二叉树的结点进行顺序编号，顺序编号的方法是：由根结点开始，从上至下；同层结点从左至右。2K-1个结点的满二叉树，依次用1、2、2K-1顺序编号。l 完全二叉树：深度为K，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1到n的结点一一对应时，称之为完全二叉树。632022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨

38、江学院计算机系642022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系652022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 二叉树的存储结构（1）二叉树的顺序存储结构二叉树的顺序存储是指用一组连续的存储单元存储二叉树的数据元素，即用一个一维数组bTreen来表示一棵二叉树。（2）二叉树的链式存储结构由二叉树的定义可知，二叉树中的每个结点至多有两个孩子，且分别称为左孩子和右孩子，因此表示二叉树的链表中的结点至少应包含三个域：数据域和左、右孩子指针域，其结点结构为：662022-5-262022-

39、5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系3. 二叉树的遍历l 一棵非空二叉树由三部分构成：根结点、左子树和右子树；而每个子树又是由这三部分构成的。l 无论以何种规则来遍历一棵二叉树，都应包括这样三个步骤：访问根结点、遍历这个根结点的左子树和遍历这个根结点的右子树。假如以D表示访问根结点，以L和R分别表示遍历这个根的左子树和右子树，若限定对于根的两棵树按先左子树后右子树的次序进行遍历，则只有DLR、LDR、LRD这三种遍历规则，分别称它们为先根次序遍历、中根次序遍历和后根次序遍历，简称为先序、中序和后序遍历。672022-5-262022-5-26南京信息工程大学

40、滨江学院计算机系南京信息工程大学滨江学院计算机系l 1）先序遍历（根左右，DLR）先序遍历二叉树的递归算法定义为：若二叉树为空，则返回；否则，执行下列操作：访问根结点；先序遍历左子树；先序遍历右子树。l 2）中序遍历（左根右，LDR）中序遍历二叉树的递归算法定义为：若二叉树为空，则返回；否则，执行下列操作：中序遍历左子树；访问根结点； 中序遍历右子树。682022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 3）后序遍历（左右根，LRD）后序遍历二叉树的递归算法定义为：若二叉树为空，则返回；否则，执行下列操作：后序遍历左子树； 后序遍历右子树；

41、访问根结点。692022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 对右图的二叉树分别进行先序、中序和后序遍历，访问结点时输出其值，则得到结点的线性遍历序列分别为： ABCDEGF，CBEGDFA和CGEFDBA。702022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系7.2.4 基本数据结构的应用l 围绕基本数据结构的应用问题，重点介绍常用的数据查找和数据的排序等两大类问题。具体来说，查找又分为顺序查找和二分法查找算法；基本排序算法又分为插入类排序，选择类排序，交换类排序等。712022-5-

42、262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系1. 查找l 查找（Searching）又称为检索，是对数据进行处理并大量使用的一种基本运算，也是像插入、删除、更新等各种操作的基础，其是根据给定的某个值在待查数据集中确定是否存在一个关键字等于给定值的记录。在查找时，若待查数据中存在符合要求的记录，则称查找成功。此时，查找的结果给出整个记录的信息或指出该记录在待查数据集中的位置。若在待查数据集中不存在关键字等于给定值的记录，则称查找失败（或查找不成功），此时查找结果给出相应的信息。722022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信

43、息工程大学滨江学院计算机系1）顺序查找l 顺序查找（Sequential Search）又称线性查找，是一种最简单的查找方法。如果顺序表中有n个记录，这n个记录按某种顺序存放在顺序表中，则进行顺序查找的过程为：从顺序表的第一个记录的开始，逐个顺序地进行记录的关键字和给定值的比较，若某个记录的关键字和给定值相等，则表明查找成功；反之，直到最后一个记录也没找到其关键字和给定值相等的记录，则表明查找关败。当得到查找成功或失败的结论后，查找结束。当然也可采取从后向前查的方法。可见顺序查找适用于表中记录无序的情况。732022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨

44、江学院计算机系l 在下面数据中顺序查找”85”742022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系2）二分法查找l 如果查找表是有序表形式，而且采用顺序存储结构，此时可采用效率更高的二分法查找（Binary Search），又称为折半查找方法。l 二分法查找是一种有序表上的效率较高的查找方法。其查找思路是：首先确定待查记录所在的范围，然后逐步缩小范围，直到查找成功或失败为止。752022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 在下面有序数据中二分查找”85”762022-5-262022

45、-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系772022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系2. 基本排序算法l 排序（Sorting）是将一个由若干数据元素（或记录）的组成的任意序列，重新排列成一个按关键字有序的序列。l 一般地，设有一个含有n个数据元素的序列D为：D= D1、D2、Di、Dn，及相应的关键字序列K为：K= K 1、K 2、K i、K n，确定1、2、i、n的一种排列P1、P2、Pi、Pn，使相应的关键字满足如下的递增（或递减）关系：KP1KP2KPiKPn（KP1KP2KPiKPn）。78

46、2022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l792022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系1）插入类排序l 插入排序法是一种由初始空集合开始，不断地把记录插入到适当位置的排序方法。下面介绍两种常用的插入排序方法。（1）简单插入排序 简单插入排序又称直接插入排序，是一种最简单的排序方法，它的基本思想是顺序地把待排序中的各数据按其关键字值非递减（或非递增）次序插入到已排序的序列的适当位置。802022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院

47、计算机系812022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l （2）希尔排序希尔排序（Shells Sort）又称缩小增量排序，是Shell在1959年提出的一种排序方法。希尔排序的基本思想是：不断地把待排序的数据集分成若干个小组，对同一组内的数据进行简单插入排序，在分组时，始终保证当前组内的数据个数超过前一次分组排序时组内的数据个数。待整个序列中的记录“基本有序”的，再对全体数据进行一次简单插入排序。822022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系832022-5-262022-5-

48、26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系2）选择类排序l 选择排序（Selection Sort）的基本思想是：每一次排序都是从待排序的数据序列中选取关键字最小的数据按顺序放到已排序的数据序列的后面，直到待排序序列中所有数据都已排序为止。842022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系（1）简单选择排序简单选择排序（Simple Selection Sort）是最简单的一种排序方法之一，这种方法的排序操作步骤为：首先从n个待排序数据中找出关键字值最小的数据，然后将这个数据与第一个位置上的数据对调，这样就是关键字

49、值最小的数据找到了它应占据的位置上。然后再从剩下的n-1个数据中找关键字值最小的记录，并把它与第二个位置上的数据进行对调。一般的，从剩余的n-i+1（1in-1）个数据中选取关键字值最小的数据。并和第i（1in）个位置上的数据进行对调，依此类推，直到所有的数据都处在它应占据的位置上，便完成了简单选择排序。852022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系862022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l （2）堆排序堆排序（Heap Sort）是对简单选择排序法的改进，是借助于完全二叉

50、树结构形成的一种排序方法。由于在简单选择排序中，当选出排序序列中的第i个数据时，就需要从n-i+1个数据中比较n-i（1in）次，从而得到一个关键字值最小的数据。而事实上，在前面排出i-1个数据时，有些数据的关键字间已进行过比较，只是这些比较信息没有被保存。如果能利用这些比较信息，就会使排出第i个数据时可能并不需要进行n-i次比较，从而可以减少各次排序中的总比较次数。872022-5-262022-5-26南京信息工程大学滨江学院计算机系南京信息工程大学滨江学院计算机系l 堆的定义：n个数据元素的序列D为：D= D1、D2、Di、Dn，及相应的关键字序列K为：K= K 1、K 2、K i、K n，都满足下列关系：若2in时，K iK 2i（或K