第3章 算法与数据结构_c语言描述 3.1 计算机的问题求解模型 3.2 C语言基础 3.3 算法与数据结构的基本概念 3.4 线性结构 3.5 多维数组和广义表 3.6 树 3.7 图 3.8 查找 3.9 排序 3.10 文件

3.1 计算机的问题求解模型 本节内容： 3.1.1 计算机求解问题的过程 3.1.2 求解过程的概化－－算法 3.1.3 求解过程的实现－－程序

3.1.1 计算机求解问题的过程 有人认为计算机是万能的，只要把任务交给计算机，计算机就会自动完成一切，并且给出正确结果，其实这是一种误解。 计算机对问题的解决，实际上只是按照人们所指定的操作步骤工作的。 从人们拿到一个计算任务，到得到正确的结果，要经过下述的几个阶段的工作，其中的任何阶段出现问题，都会影响到结果的正确性。 (1) 分析问题 (2) 确定处理方案 (3) 设计处理步骤和数据结构 (4) 编写程序代码 (5) 调 试程序和结果检验 (6) 整理结果

3.1.2 求解过程的概化－－算法 (b) 描述要简明、准确，不能存在二义性的描述。 (c) 在详细的算法描述中，要充分考虑到任何处理细节。 当数据处理方案确定以后，算法的选择和设计是问题求解中很重要的一步。 所谓算法，就是问题求解的步骤设计。 (1) 算法的选择： 一个问题的求解，往往有多种方法。不同的方法之间，从处理的效率、结果的精度到程序设计人员的工作量、数学模型的难易程序都有很大的差别。这时就要权衡利弊得失，选择一种最为满意的算法。 (2) 对算法的描述： 可以选择自然语言、流程图、N－S图等多种方法描述算法。在算法的描述过程中应该注意以下几点： (a) 按问题的处理前后顺序描述。 (b) 描述要简明、准确，不能存在二义性的描述。 (c) 在详细的算法描述中，要充分考虑到任何处理细节。 (d) 要考虑到问题处理过程中任何可能发生的情况。 (e) 算法中的运算和处理应能够在有限的时间内结束。 (f) 对于采用模块化设计。模块的划分采用从上向下的顺序逐步细化。

3.1.2 求解过程的概化－－算法 下面看一个求解一元二次方程的根的算法设计过程： (1) 通过自然语言描述算法如下： (a) 输入方程的系数a、b和c； (b) 计算d＝b2-4ac； (c) 如果d小于0，转(g)； (d) 计算两个实根 x1=(-b+sqrt(d))/(2a)和x2=(-b+sqrt(d))/(2a)； (e) 输出两个实根x1和x2； (f) 转(i)； (g) 计算两个复根的实部u=-b/(2a) 和虚部v=sqrt(-d)/(2a)； (h) 输出两个复根x1=u+vi和x2=u-vi； (i ) 停止程序执行。

3.1.2 求解过程的概化－－算法 (2) 通过流程图描述算法如下：                                                                                                                                                                        

3.1.3 求解过程的实现－－程序 算法的实现只是问题解决的一个步骤，将算法用程序代码描述出来，并且输入到计算机中，让计算机按照设计好的程序完成指定的工作并且得到我们想要的结果，才是我们的目的之所在。 程序（Program）是指用某一种计算机语言编写的计算机可以直接或间接执行的代码序列。 如何才能将算法转换成计算机可能执行的程序呢？ 1. 计算机语言的分类和执行方式 2. 如何用计算机语言描述算法 3. 程序的调试与修改

3.1.3 求解过程的实现－－程序 1. 计算机语言的分类和执行方式 使用某一种语言编程时，这种语言的支持软件、编译程序或解释程序、内部库函数、用户支持环境、各种设计工具以及与编程和程序运行有关的软件，就构成了这种语言的程序设计环境。 程序设计语言可以分为以下三类： (1)机器语言 机器语言（Machine language）是一种面向计算机的程序设计语言，用它所设计的程序是一系列的指令。 计算机的CPU可以直接执行机器语言程序，这种程序称为目标程序（Object program）。 目标程序手工编写非常因难，需要编程者熟悉CPU的指令系统，熟悉CPU的内部结构。另外，机器语言作为面向机器的语言，在不同类型的处理器之间差别很大，即机器语言程序的可移植性较差。 机器语言程序直接用二进制代码组成（书写时常采用十六进制），目前很少人工编写，而是由高级语言程序通过软件生成机器语言程序。

3.1.3 求解过程的实现－－程序 (2)汇编语言 汇编语言（Assembly language）是一种接近机器语言的符号语言。它将机器语言的指令用便于人们记忆的符号来表示，通过这种语言系统所带的翻译程序翻译成目标程序后再执行。汇编程序执行效率很高。目前在实时控制等方面的编程中仍有不少应用。 汇编语言程序示例: 汇编语言程序示例:                                                                                                                                                                

3.1.3 求解过程的实现－－程序 编汇语言程序的执行方式:

3.1.3 求解过程的实现－－程序 (3)高级语言 高级语言（High-level language）是一种完全符号化的语言，其中采用自然语言（英语）中的词汇和语法习惯，容易为人们理解和掌握；它完全独立于具体的计算机，具有很强的可移植性。 用高级语言编写的程序称为源程序（Source program），源程序不能在计算机直接执行，必须将它翻译或解释成目标程序后，才能为计算机所理解和执行。

3.1.3 求解过程的实现－－程序 高级语言程序的两种执行方式： 解释方式: 编译方式:

1. 熟悉所要使用的计算机语言。 3.1.3 求解过程的实现－－程序 2. 如何用计算机语言描述算法 在通过算法编写程序代码时，应注意以下问题： 1. 熟悉所要使用的计算机语言。 2. 熟悉算法中所使用的模型与模型所适用的环境与条 件。 3. 根据算法中每一步的要求选择适当的语句和语句参数。 4. 选择和设计合适的数据结构。 5. 采用模块化设计，算法中的模块和程序中的模块相一致。 6. 为了增加程序的可读性，应增加必要的注释文字。

3.1.3 求解过程的实现－－程序 例如，前面求解一元二次方程的算法，可以写出如下的C语言程序： #include <stdio.h> #include <math.h> main() {   float a,b,c,d,x1,x2;   scanf("%f,%f,%f",&a,&b,&c);   d=b*b-4*a*c;   if (d>=0.0)   {     x1=(-b+sqrt(d))/(2*a);    x2=(-b-sqrt(d))/(2*a);     printf("x1=%f\n",x1);    printf("x2=%f\n",x2);   }   else     x1=-b/(2*a);     x2=sqrt(-d)/(2*a);     printf("x1=%f+i*%f\n",x1,x2);    printf("x2=%f-i*%f\n",x1,x2); }

3.1.3 求解过程的实现－－程序 3. 程序的调试与修改 在程序的试运行中，可能会出现各种错误，这些错误可以分为以下几种： 编译错误： 在程序的编译阶段发生的错误，一般是保留字的拼写不正确，或者语句不符合本语言的规则等，发生此类错误时一般会停止编辑工作。比较容易查到出错原因。 (2) 连接错误： 在连接各子程序和库函数时发生的错误，一般是程序模块的调用不对，如形式参数和实际参数不一致，程序调用库函数时错误（如参数不对、函数不存在等）。这类错误查错时检查相关的函数，也可以较快地解决。 (3) 警告性错误： 编译中发生这类错误时，不影响后面的工作，但是程序运行时可能会发生问题。 (4) 运行错误： 编译、连接工作都顺利完成，但是目标程序运行时出现问题如出现数据溢出的错误、负数开平方的错误、数组使用超界等等。这种情况要具体分析出错的原因和出错的位置，从算法、程序、数据不同的方面着手，必要时输出部分中间结果，逐步分析出出错的真正原因。 (5) 计算结果不正确。程序可以顺利地完成运行，但是输出结果经验证不正确，或者结果的精度达不到应有的精度。这类错误最难查找，应从任务的各个阶段分析，如数学模型中是否存在问题？有无漏洞？数据（包括数据的结构）是否正确是否正确？表达式的书写有无错误？程序代码有无错误？等等。必要时应在程序中增加大量输出中间结果的语句，以最终查到错误的原因所在。 程序的调试是一个繁杂的反复过程，需要编程者大量艰苦的工作，程序的通过就是这样在“运行－－查错－－排错－－再运行－－”的过程中逐步通过。

3.2 C语言基础 本节内容： 3.2.1 C语言程序结构 3.2.2 C语言基本符号 3.2.3 数据和数据类型 3.2.4 运算符、表达式、赋值运算和赋值表达式 3.2.5 赋值语句和输入输出 3.2.6 分支语句 3.2.7 循环控制语句 3.2.8 函数 3.2.9 预处理指令 3.2.10 文件操作

3.3 算法与数据结构的基本概念 本节内容： 3.3.1 概念和术语 3.3.2 数据的逻辑结构 3.3.3 数据的存储结构 3.3.4 算法分析与设计

3.3.1 概念和术语 1. 数据 2. 信息 3. 数据类型 4. 数据结构 5. 算法

3.3.1 概念和术语 数据 　　数据是对客观事物的符号表示，他是一组表示数量、行动和目标的非随机的可鉴别的符号。它可以是数字、字母等符号。在计算机中，数据通常是指一切可以输入到计算机中并能被计算机程序处理的所有符号的总称。在计算机科学中，通过数据编码技术，文本、声音、图形、图像都可以编码成计算机可处理的数据。

3.3.1 概念和术语 信息 　　信息和数据是一个经常容易引起混淆的概念，从信息论的角度讲，信息是加工后的数据，他对接收者的行为产生影响，对接收者的决策具有价值。如某城市的气侯情况（如海口12月份的气温一般在20度左右），对于要到该城市的人来说就表现为信息，它可能直接影响是否要到该城市来以及作何种准备（如：准备什么样的衣服）的决策。对于当地人来讲，12月份20度的气温更多地表现为数据。在计算机应用中，信息和数据常是等同的。

3.3.1 概念和术语 数据类型 　　 数据类型是程序设计中的概念，程序中的数据都属于某个特殊的数据类型。数据类型决定了数据的性质，如数据的取值范围、操作运算等。常用的数据类型有整数类型、实数类型、字符类型、布尔类型（逻辑类型）等。 数据类型还决定了数据在内存中占据的空间的大小，不同类型的数据在不同的操作系统下占用的内存大小不同。例如，整数类型数据在Windows 9x中一般占两个字节的空间。

3.3.1 概念和术语 数据结构 　　数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。 数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。 数据结构是数据存在的形式。 数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。

3.3.1 概念和术语------数据结构 　 数据结构是在整个计算机科学与技术领域上广泛数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。 主要有三个方面的内容：数据的逻辑结构； 数据的物理存储结构； 对数据的操作（或算法）。 通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。　 　　 数据结构反映数据内部的构成方式，它常常用一个结构图来描述:数据中的每一项成分数据被看作一个结点，并用方框或圆圈表示，成分数据之间的关系用相应的结点之间带箭号的连线表示。如果成分数据本身又有它自身的结构，则结构出现嵌套。这里嵌套还允许是递归的嵌套。

由于指针数据的引入，使构造各种复杂的数据结构成为可能。 按数据结构中的成分数据之间的关系，数据结构有线性与非线性之分。 3.3.1 概念和术语------数据结构 由于指针数据的引入，使构造各种复杂的数据结构成为可能。 按数据结构中的成分数据之间的关系，数据结构有线性与非线性之分。 在非线性数据结构中又有层次与网状之分。 由于数据类型是按照数据结构划分的，因此，一类数据结构对应着一种数据类型。数据类型按照该类型中的数据所呈现的结构也有线性与非线性之分，层次与网状之分。一个数据变量，在高级语言中的类型说明必须是读变量所具有的数据结构所对应的数据类型。

1.成分数据的个数固定，它们之间的逻辑关系由成分数据的序号(或叫数组的下标)来体现。这些成分数据按照序号的先后顺序一个挨一个地排列起来。 3.3.1 概念和术语------数据结构 最常用的数据结构是数组结构和记录结构。 数组结构的特点是： 1.成分数据的个数固定，它们之间的逻辑关系由成分数据的序号(或叫数组的下标)来体现。这些成分数据按照序号的先后顺序一个挨一个地排列起来。 2.每一个成分数据具有相同的结构(可以是简单结构，也可以是复杂结构)，因而属于同一个数据类型(相应地是简单数据类型或构造数据类型)。这种同一的数据类型称为基类型。 3.所有的成分数据被依序安排在一片连续的存储单元中。 概括起来，数组结构是一个线性的、均匀的、其成分数据可随机访问的结构。由于这种结构有这些良好的特性，所以最常被人们所采用。在高级语言中，与数组结构相对应的数据类型是数组类型，即数组结构的数据变量必须说明为<类型名> 数组名[i] ，其中i是数组结构的下标类型。

记录结构是另一种常用的数据结构。它的特点是: 3.3.1 概念和术语------数据结构 记录结构是另一种常用的数据结构。它的特点是: 1.与数组结构一样，成分数据的个数固定。但成分数据之间没有自然序，它们处于平等地位。每一个成分数据被称为一个域并赋予域名。不同的域有不同的域名。 2.不同的域允许有不同的结构，因而允许属于不同的数据类型。 3.与数组结构一样，它们可以随机访问，但访问的途径靠的是域名。

算法 3.3.1 概念和术语 一个算法应该具有以下五个重要的特征： 1. 有穷性： 一个算法必须保证执行有限步之后结束； 　　 算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。 一个算法应该具有以下五个重要的特征： 　1. 有穷性： 一个算法必须保证执行有限步之后结束； 　2. 确切性： 算法的每一步骤必须有确切的定义； 　3. 输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件； 　4. 输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的； 　5. 可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成

3.3.2 数据的逻辑结构 数据结构描述了数据以及数据之间的逻辑关系，数据之间的逻辑关系称为数据的逻辑结构。 数据的逻辑结构一般分成四种类型： （1）集合 数据元素的关系非常松散，他只描述数据元素是否同在一个集合中。例如： （2）线性结构 数据元素之间存在线性关系，每个元素都有一个惟一的前导元素和一个惟一的后继元素，第一个元素没有前导，最后一个元素没有后继。例如：

数据元素之间呈现层次关系，在树形结构中，每一个元素通常称为一个节点，每个节点（根节点除外）有一个父节点，一个节点可以有多个子节点。 3.3.2 数据的逻辑结构 （3）树形结构 数据元素之间呈现层次关系，在树形结构中，每一个元素通常称为一个节点，每个节点（根节点除外）有一个父节点，一个节点可以有多个子节点。 （4）图状结构 元素呈多对多的关系，在图状结构中每个元素称为一个节点，图状结构又称网状结构。例如：

3.3.3 数据的存储结构 研究数据结构的目的是要在计算机中实现对数据的操作，要实现对数据的操作必须将数据在计算机中表示。对数据不同的存储，对数据操作的实现将不相同。 我们把对数据结构在计算机中的表示称为数据的存储结构，又称物理结构。存储结构不但要表示数据，还必须表示出数据的逻辑结构。 在计算机中，数据都转换为二进制串来进行存储，不同类型的数据占用的存储空间不同。 数据之间的关系在计算机的表示一般分成顺序存储和链式存储两种。 在顺序存储中，借助于数据在存储器中的相对位置表示数据之间的关系，例如: 用数组来存储一个线性结构数据对象。 在链式存储中，每个数据元素存储为一个节点，每个节点有一个或多个指针，指向其他的节点，指针表示了节点（数据元素）之间的关系 股安息

3.3.3 数据的存储结构 1.顺序存储结构的特点 在计算机中，所谓顺序存储是指用一组地址连续的存储单元依次存储数据集合中的元素。 顺序存储结构非常适合存储线性表，例如：设线性表中每个元素占用l个存储单元，线性表的第一个元素存储位置为LOC(a0)，则第i个元素的存储位置为： LOC(ai) = LOC(a0)+(i-1)*l 存储位置表示了元素之间的关系，这样可以使得该数据结构下的许多算法容易实现，并且效率较高。 顺序存储结构虽然可以用元素的存储位置表示元素之间的关系，但是如果元素集合很大，顺序存储要求一块很大的连续的内存空间，这在操作系统的存储管理上可能无法满足。 (顺序表)

3.3.3 数据的存储结构 2. 链式存储结构的特点 链式存储最大的特点是无法用元素的存储位置表示元素之间的关系，它需要增加指针，通过指针表示元素之间的关系。 利用指针表达元素之间的关系，增加了数据结构的存储空间要求。另外，对元素的许多操作算法，在实现上也变得较为麻烦，效率较低。 但是，链式存储大大的增加了数据结构的灵活性，对于有些数据结构，链式存储比顺序存储更好。 ( 单链表)

3.3.4算法分析与设计 算法具有五个重要的特性： （1）有穷性：一个算法必须在执行有穷步后结束，每一步必须在有穷的时间内完成。 在数据结构中，对数据的操作往往用算法来描述。所谓算法（Algorithm）,就是指对特定问题求解过程的描述，他由一系列的指令组成，每个指令表示一个或多个操作。 算法具有五个重要的特性： （1）有穷性：一个算法必须在执行有穷步后结束，每一步必须在有穷的时间内完成。 （2）确定性：算法中的每一条指令必须有确定的含义，不能产生二义性。 （3）可行性：算法描述的步骤在计算机上是可行的 （4）输入：一个算法可以有零个或多个输入，这个取决于算法要实现的功能。 （5）输出：一个算法执行过程中或结束后要有输出结果，或者产生相应的动作指令。 所谓算法分析，就是对设计的算法进行正确性、时间复杂性和空间复杂性的分析，从而来评价算法的优劣，或估计算法实现后的运行效果。　 股安息

3.3.4算法分析与设计 1．算法的正确性 算法设计首先要保证其正确性，只有在保证算法正确性的前提下，才可以讨论算法的好坏。为了方便对算法正确性的描述，假设设计一个求三角形面积的算法，三角形的三条边分别为a,b,c，面积表示为area，如果求面积的算法简单的设计为： step1 read(a,b,c) step2 s:=(a+b+c)/2 step3 area=s*sqrt(s*(s-a)*(s-b)*(s-c)) step4 write(area) 该算法正确性的描述可以分成下面几个层次： （1）对于一组数据能够得出正确的结果，该算法没有考虑三角形中两边之和大于第三边的基本数学原理，因此如果输入的三条边可以构成一个三角形，则该算法是正确的。 （2）对于精心挑选的、苛刻的测试用例算法可以得到正确的结果。在某些情况下，上述求三角形面积的算法就不正确了，如当输入的三条边包含负数或者有一条边大于另外两条边的长度之和时，上述算法将得到错误的结果。 （3）对于一切合法的输入数据，算法得到的结果都是正确的。这是一种理想的情况，随着算法求解问题复杂度的增加，一个算法在不同的输入数据下会有大量不同的执行路径，因此要验证算法的完全正确是很困难的。我们只能精心设计测试用例，用较少的数据去发现更多的错误，然后进行修改，以期达到算法最大程度上的正确性。

3.3.4算法分析与设计 2．时间复杂性分析 一般情况下，一个算法中基本操作重复执行的次数与求解问题的规模（问题长度）n呈某个函数关系f(n)，记作： T(n) = O(f(n)) 我们把T(n)称为算法的时间复杂度。如果算法的执行时间与问题的长度无关，则该算法的时间复杂度记为O(1)，表示常数时间复杂度。 例如：求长度为n的数组a[1..n]中,中间一个元素的值a[n/2]，时间消耗与问题长度n无关。 算法的实现即程序，一般有三种结构：顺序结构、分支结构和重复结构。三种结构中语句的执行次数构成算法的时间消耗。 常用的算法时间复杂度有下述几种o(n)、o(nlog2n)、o(n2)、o(n3)、o(2n)，假设计算机执行一次基本操作需要的时间为1ms，五种算法时间复杂度与求解问题的长度关系见表3-7。

3.3.4算法分析与设计 表3-7 算法时间复杂度与求解问题的长度关系 在上述表格中，可解问题的最大长度是指在某个时间内n的值。例如对于算法A2，1秒钟可以解决的问题长度为n，又因为计算机执行一次基本操作需要的时间为1ms，因此有nlog2n = 1000，可以计算得到n≈140。 算法 时间复杂度 可解问题最大长度（n） 1秒 1分钟 1小时 A1 o(n) 1000 60000 3.6*106 A2 o(nlog2n) 140 489 32.0*105 A3 o(n2) 31 240 1987 A4 o(n3) 10 33 153 A5 o(2n) 9 15 21

3.3.4算法分析与设计 表3-8计算机速度对求解问题长度的影响 算法 时间复杂度 可解问题最大长度（n） 计算机速度提高前 可见，时间复杂度越大，在时间消耗的增加带来的求解问题长度的增加会变慢。下面我们看计算机速度的提高对不同算法求解问题长度带来的影响，见表3-8。 表3-8计算机速度对求解问题长度的影响 算法 时间复杂度 可解问题最大长度（n） 计算机速度提高前 计算机速度提高10倍 A1 o(n) S1 10s1 A2 o(nlog2n) S2 10s2 A3 o(n2) S3 3.16s3 A4 o(n3) S4 2.15s4 A5 o(2n) s5 S5+3.3

3.3.4算法分析与设计 3. 空间复杂性 算法的空间复杂度是指算法运行中对存储空间的需求，记作： S(n)=O(f(n)) 分析一个算法的时间复杂度，除了考察数据所占用的空间外，应该分析可能用到得额外空间。随着计算机存储器容量的增加，人们对算法空间复杂度的分析的重视程度要小于时间复杂度的分析。

3.4 线性结构 在四种数据结构中，线性结构是较为简单、但又是用非常广泛的结构，线性结构具有如下特点： （1）存在一个惟一的称为“第一个”的数据元素，存在一个惟一的称为“最后一个”数据元素； （2）除了“第一个”元素以外，集合中的每一个元素都有一个惟一的前导元素，第一个元素没有前导；除“最后一个”数据元素外，每一个元素都有一个惟一的后继元素，最后一个元素没有后继。 本节内容： 3.4.1 线性表 3.4.2 堆栈 3.4.3 队列 3.4.4 串

n>0时，线性标记作：（a1,a2,…,an） 3.4.1 线性表 线性表（linear list）是一个具有n（n ≥ 0）个数据元素的有序序列。在不同的应用情况下，数据元素的含义不同，它可以是一个数、字符或一个对象。 线性表的形式定义如下： linear_list = (D,R) 其中，D={ai | ai€D0,i=1,2,…,n,n≥0}； R={N},N={<ai-1,ai> |ai-1,ai€D0,i=2,3,…, n,n ≥ 0}。 D0 为性质相同的数据元素的集合。关系R是有序偶的集合，它表示元素集中数据元素之间的相邻关系，元素ai-1,是ai的前导，ai是ai-1的后继。线性表中数据元素的个数n称为线性表的长度。 n=0时，线性表称为空表。 n>0时，线性标记作：（a1,a2,…,an）

线性表是一个非常灵活的结构，对线性表的常用操作包括： 1）Length(L)：求线性表的长度函数，返回线性表中数据元素的个数。 3.4.1 线性表 1.线性表的基本操作 线性表是一个非常灵活的结构，对线性表的常用操作包括： 1）Length(L)：求线性表的长度函数，返回线性表中数据元素的个数。 2）Get(L,i)：取元素函数，返回线性表L的第i个数据元素的值，0<i<Length(L)。 3）Locate(L,x)：定位函数，给定值x，判断线性表中是否有和x值相等的元素。 如果存在，返回第一个和x相等的元素在线性表中的位序，否则，返回0。 4）Prior(L,e): 前导函数，返回线性表L中元素e的前导元素。如果e为第一个元素，返回空。 5）Next(L,e)：后继函数，返回线性表L中元素e的后继元素。如果e为最后一个元素，返回空。 6）Insert(L,i,e)：插入操作，在线性表L的第i个元素的前面插入一个元素e。成功插入后，线性表的长度加一。 例如：插入前的线性表为：L=（a1,a2,…ai-1,ai,…an）。则执行插入操作后线性表L变为：L=（a1,a2,…ai-1,e,ai,…an），元素ai-1和ai之间的相邻关系被改变。 7）Delete(L,i)：删除操作，将线性表L的第i个元素删除。 例如：删除前的线性表为：L=（a1,a2,…ai-1,ai, ai+1…an）。则执行删除操作后线性表L变为：L=（a1,a2,…ai-1,ai+1,…an），元素ai-1 和ai+1成为相邻的元素，线性表的长度减一。

3.4.1 线性表 2.线性表的存储结构 在任何逻辑结构上定义的操作算法，必须在特定的存储结构下才能够实现。存储结构必须将逻辑结构中的数据和数据之间的关系表示出来。 1）线性表的顺序存储结构 顺序结构通过元素之间的物理存储位置表示了线性表中元素之间的关系，对线性表中的数据元素可以随机存取。这使得线性表的许多操作变得简单和高效。如：取元素函数Get(L,i)在实现上将只需要一个函数返回语句，而无需数据结构的遍厉过程。 线性表的顺序存储结构可以用数组来表示，用C语言描述如下： #define MAXSIZE 100   //设线性表的最大长度为100 typedef float ElementType;   //ElementType为元素类型，为了操作方便，假设为实数 typedef struct { ElementType elements[MAXSIZE];  // 元素数组    int length;  // 线性表的实际长度 } SqList 在此结构下可以进行线性表的各种操作运算。 顺序表的实现.

线性表可以采用单链表结构，定义如下： 3.4.1线性表 2）线性表的链式存储结构 typedef struct Node{       ElementType data; struct Node *next; } Node ； Node *SqListHead;

3.4.2 栈 堆栈（stack）是一种限定只在表尾进行插入和删除操作的线性表，他在递归算法、面向对象程序设计等许多方面有着重要应用。从数据结构的角度讲，栈是一种操作受限的线性表，它的插入和删除只能在表的一端进行。我们把以进行查入和删除操作的一端称为“栈顶”，另一端称为“栈尾”。堆栈结构如图3-8所示。

栈是一种操作受限的线性表，对栈的操作主要包括： （1）InitStack(S)：初始化操作，将栈S设为空。 3.4.2 栈 1.栈的基本操作 栈是一种操作受限的线性表，对栈的操作主要包括： （1）InitStack(S)：初始化操作，将栈S设为空。 （2）PUSH(S,x)：入栈操作，将元素x压入栈S，成为新的栈顶元素。 （3）POP(S)：出栈函数，S为堆栈，若S不为空，返回S的栈顶元素， 且从栈中删除该栈顶元素（退栈）。如果堆栈为空，则 函数返回值为NULL。 （4）GETTOP(S)：取栈顶元素函数，S为堆栈，若S不为空，返回S的 栈顶元素。如果堆栈为空，则函数返回值为NULL。 2. 栈的存储结构 一般地，栈有两种实现方法：顺序实现和链接实现，这和线性表类似。

3.4.2 栈 1）栈的顺序存储结构 栈的顺序存储结构称为顺序栈。 3.4.2 栈 1）栈的顺序存储结构 栈的顺序存储结构称为顺序栈。 顺序栈通常由一个一维数组和一个记录栈顶位置的变量组成。因为栈的操作仅在栈顶进行，栈底位置固定不变，所以可将栈底位置设置在数组两端的任意一个端点上。习惯上将栈底放在数组下标小的那端。另外需使用一个变量top记录当前栈顶下标值。即表示当前栈顶位置，通常称top为栈顶指针(注意它并非指针类型变量) 顺序栈类型定义如下： #define sqstack_maxsize 6 /*顺序栈的容量*/ 　 typedef struct 　　 {ElementType data[sqstack_maxsize]; 　　　int top; 　　 } sqstack; 　顺序栈被定义为一个结构类型，它有两个域data和top。 data为一个一维数组，用于存储栈中元素，ElementType为栈元素的数据类型（有待设定）。 top为int型，它的取值范围为-1,0..sqstack_maxsize-1。top==-10表示栈空，top=sqstack_maxsize-1表示栈满。 栈的基本运算在顺序栈上的实现

链栈类型定义如下： typedef struct node 3.4.2 栈 2）栈的链式存储结构 栈的链接实现是以某种形式的链表作为栈的存储结构，并在这种存储结构上实现栈的基本运算。 栈的链式存储结构称为链栈，其组织形式与单链表类似。由于只在链栈的头部进行操作，故链栈没有必要设置头结点。单链表的第一个结点就是链栈栈顶结点。ls称为栈顶指旬，它相当于单链表的头指针。类似地，链栈由栈顶指针ls唯一确定。栈中的其它结点通过它们的next域链接起来。栈底结点的next域为null。因链栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况。 链栈类型定义如下： typedef struct node　 { ElementType data; 　　 struct node *next; 　 } node； node *LStackTp; 　 栈的基本运算在链栈上的实现

3.4.3 队列 和堆栈不同，队列（queue）是一种先进先出（First In First Out，FIFO）的线性表。只能在表的一端进行插入操作，在另一端进行删除操作。允许插入的一端称为队尾（rear）,允许删除的一端称为队首（front）。 假设队列为q=（a1,a2,…an）,队列中的元素按照a1,a2,…an的顺序依次进入队列，有按照相同的顺序依次从队列中删除。如图3-9所示。   图3.9 队列示意图

（1）InitQueue(Q)：初始化操作，设置一个空的队列Q。 3.4.3 队列 1.队列的基本操作 队列也是一种操作受限的线性表，对队列的操作主要包括： （1）InitQueue(Q)：初始化操作，设置一个空的队列Q。 （2）EntQueue(Q,x)：入队操作，将元素x插入到队列Q的尾，成为对 列新的队尾元素。 （3）DelQueue(S)：出队列函数，Q为队列，若Q不为空，返回Q的队 首元素，且将队首元素从队列中删除。如果队列Q 为空，则函数返回值为NULL。 （4）GetHead(S)：取队首元素函数，Q为队列，若Q不为空，返回Q的 队首元素。如果队列为空，则函数返回值NULL。 （5）CurrentSize(Q)：队列大小函数，返回队列Q当前所包含的元素个 数。 2. 队列的存储结构 与栈类似，队列通常有两种实现方法，即顺序实现和链接实现。

3.4.3 队列 顺序队列的类型定义如下： (1）队列的顺序存储结构 3.4.3 队列 (1）队列的顺序存储结构 队列的顺序实现称为顺序队，它由一个一维数组(用于存储队列中元素)及两个分别指示队头和队尾的变量组成，这两个变量分别称为“队头指针”和“队尾指针”(注意它们并非指针型变量)。通常约定队尾指针指示队尾元素在一维数组中的当前位置，队头指针指示队头元素在一维数组中的当前位置的前一个位置，如图所示。 　　 顺序队列的类型定义如下： # define maxsize  20 　　typedef struct 　　　{ElementType data[maxsize]; 　　　　int　front,rear; 　　　}SqQueue; 　　

初看起来，入队操作可用sq.rear=sq.rear+1;data[sq.rear]=x 实现. 3.4.3 队列 顺序队定义为一个结构类型，它有三个域：data、front、rear。其中data为存储队中元素的一维数组，队头指针front和队尾指针rear定义为整型类型变量，取值范围是0..maxsize-1。 　　初看起来，入队操作可用sq.rear=sq.rear+1;data[sq.rear]=x 实现. 出队操作可用一条语句实现sq.front=sq.front+1。但实际上这不是一个好办法。 在图3-8(e)的状态下，显然按上述方法不能再进行入队运算。但是在数组的低端仍有空闲位置，亦即顺序队的存储空间并没有被占满。因此，这是一种“假溢出”。为了充分利用存储空间，克服“假溢出”，可采用循环队的办法。

把队列设想成一个循环表， 3.4.3 队列 即设想数组的首尾相连：sq.data[0]接在sq.data[maxsize-1]之后。 3.4.3 队列 把队列设想成一个循环表， 即设想数组的首尾相连：sq.data[0]接在sq.data[maxsize-1]之后。 这种存储结构称为循环队。当sq.rear=maxsize-1时，只要数组的低下标端有空闲空间，在循环队上仍可做入队运算。此时只需令sq.rear=0，即把sq.data[0]作为新的队尾，并将入队元素置入此位置。这样就解决了“假溢出”问题。循环队的示意图见图3-9。图中阴影部分为当前队列占用空间，其余为当前空闲空间。 循环队上的入队操作： 　　　sq.rear=(sq.rear+1)% maxsize; sq.data[sq.rear]=x; 　出队操作： 　　　sq.front=(sq.front+1)% maxsize; 　　

接下来必须解决的一个问题是，循环队的队满和队空的条件是什么？也就是说，如何判断一个循环队是满的或空的？ sq.rear==sq.front 3.4.3 队列 循环队列的类型定义： 　　typedef struct { 　　　　　{ElementType data[maxsize]; 　　　　　   int rear,front; 　　　　　} Cycqueue; Cycqueue sq; 接下来必须解决的一个问题是，循环队的队满和队空的条件是什么？也就是说，如何判断一个循环队是满的或空的？ 　sq.rear==sq.front 解决方法： 1）约定循环队的队头指针指示队头元素在数组中实际位置，队尾指针指示队尾元素在数组中的实际位置的后一个位置 。其次，为简化判断，我们“牺牲”一个存储结点，即约定队头指针指示的结点不用于存储队列元素，只起标志作用。这样，当队尾指针“绕一圈”后赶上队头指针时，视为队满。 故队满条件为： 　　　　((sq.rear+1)% maxsize)==sq.front 相应地，队空条件为： 　　　 　sq.rear==sq.front 队列的基本运算的实现

3.4.3 队列

队满条件为： sq.count== maxsize 相应地，队空条件为： sq.count== 0 3.4.3 队列 2）增加一个计数器域 循环队列的类型定义： 　　typedef struct { 　　　　　{ElementType data[maxsize]; 　　　　　   int rear,front; int count； 　　　　　} Cycqueue; Cycqueue sq; 队满条件为： 　　　　sq.count== maxsize 相应地，队空条件为： 　　　　 sq.count== 0 队列的基本运算的实现

3.4.3 队列 (2）队列的链式存储结构 队列的链接存储结构称为链队，它实际上是一个同时带有头指针和尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点即单链表的最后一个结点。

当lq.front==null 或lq.rear==null时，队中无元素，此时队空。 3.4.3 队列 链队的类型定义如下： Typedef struct node 　{ElementType data; 　Struct node *next; 　}Lqueuenode; (链队结点类型) typedef struct { 　　Lqueuenode *front,*rear; 　}linkqueue; 链队在一定范围内不会出现队满的情况。 当lq.front==null 或lq.rear==null时，队中无元素，此时队空。 队列的基本运算的实现

本节内容： 3.5.1 多维数组及其存储 3.5.2 矩阵的压缩存储 3.5.3 广义表 3.5 多维数组与广义表 线性表中的数据元素往往属于相同的数据类型，且一般是不可分割的原子项。若放宽对元素性质的上述约束，线性表就扩展为多维数组或广义表。 本节内容： 3.5.1 多维数组及其存储 3.5.2 矩阵的压缩存储 3.5.3 广义表

3.5.2 矩阵的压缩存储 1.特殊矩阵 特殊矩阵是指一些具有特定性质的矩阵，包括: 一般情况下，对于多维数组采用行优先或列优先的顺序为每一个元素分配一个存储空间。但是在特殊情况下，这样的存储会造成大量的空间浪费，可以采用特定的压缩方式来存储。 1.特殊矩阵 特殊矩阵是指一些具有特定性质的矩阵，包括: 对称矩阵、下（上）三角矩阵、对角矩阵等。 1） 对称矩阵的存储 若一个n阶矩阵A中元素满足性质：aij = aji ,1≤i,j ≤ n，则称A为n阶对称矩阵。 在传统的存储策略下，每一个元素分配一个存储空间，需要n2个存储空间。实际上，我们可以只存储下三角（包括对角线）中的元素，对于其他的元素可以通过特定的映射关系来从存储的元素中得到。 要保存下三角中的所有元素需要(n2-n)/2+n = n(n+1)/2个存储空间， 假设我们用一个一维数组sa[1..n(n+1)/2]按照行优先的顺序来存储下三角中的每一个元素，形式如下： a11 a21 a22 a31 a32 a33 … an1 ann

根据上述的存储结构，数组A中的每一个元素aij和一维数组sa的下标k之间的关系为： 3.5.2 矩阵的压缩存储 根据上述的存储结构，数组A中的每一个元素aij和一维数组sa的下标k之间的关系为： 对于数组sa中的任意一个元素sa[k]，1≤k≤n(n+1)/2，其在二维数组A中对应的元素为Aij。首先确定元素的行下标i，i应该满足：1+2+…+r≤k的最大的r值加1。如当k=4时，最大的r=2，因为此时有1+2<k，则r=2，故行下标i=r+1=3。然后求列下标j，j=k-i（i+1）/2。因此得出sa[4]中存储的是二维数组A中的第3行第1列的元素

#define MAXSIZE = 1000 //最多的可能的非0 元素的个数 3.5.2 矩阵的压缩存储 2．稀疏矩阵 稀疏矩阵是指含有大量0元素的矩阵。 一个m×n的矩阵A，在正常的情况下需要m×n个存储空间。如果A中含有大量的0元素，即非零元素的个数k<< m×n 。此种情况下，我们可以采用压缩存储，即只保存非零元素的值，同时还需要存储对应的行列坐标。因此需要3k个存储空间，如果k<< m×n ，则3k<< m×n 。此时可以节省较大的存储空间。 1）三元组表 按照压缩存储的思想，对稀疏矩阵A，只存储每个非0元素的值aij及其行列坐标(i,j),记作三元组形式(i,j, aij)。将三元组构成一个线性表，线性表采用顺序存储结构。结构定义如下： #define MAXSIZE = 1000   //最多的可能的非0 元素的个数 typedef int ElementType;    //为了实现方便，设元素类型ElementType为int typedef struct {        int i,j;    // 行列坐标       ElementType e; //非0的元素值 } Triple;      int row,col,num; //矩阵的行数和列数及非0个数      Triple data[MAXSIZE+1]; } SparsemMatrix;

3.5.2 矩阵的压缩存储 例如，对于一个5行6列的稀疏矩阵A，包含5个非0元素，如图所示。在三元组存储中，需要15+3共18个存储单元，比压缩存储前需要的30个存储单元要小。矩阵越大（如800×600），压缩的比例将越高。

3.5.2 矩阵的压缩存储 row col value down right 2）十字链表 用顺序存储结构存储稀疏矩阵可以有效的节省存储空间。缺点是，在非0元素增加和减少时，插入和删除不便。为此，用称为“十字链表”的链式存储结构来存储。具体的结构是： 第一，对稀疏矩阵的每一行和每一列都建立一个具有头节点的循环链表，将该行中或该列中的所有非0元素都连接起来。连接顺序为：在行链表中，按列的次序连接；在列链表中，按行的次序连接。 第二，对每个非0元素建立一个节点，该节点即处于该元素所在行的行链表中，也处于该元素所在列的列链表中。结点结构如下： 其中，row、col和value分别为非零元素所在的行、列坐标和元素值，down和right为两个指针字段，分别指向该列或该行中下一个非0 元素对应的结点。 第三，每个行（列）链表的头结点的结构形式与非0元素结点相同，但节点含义不同。其中，row=col=0（不用），down和right分别指向该列或该行中第一个非0 元素对应的结点。value为指针字段，指向下一个表头节点，即所有的表头节点构成一个循环链表。编号相同的行列链表公用一个头节点。因此，表头结点的个数为max{m,n}。 第四，对所有的行（列）表头结点构成的链表建立一个头结点A，结构同上，具体含义是：row记录矩阵的行数，col纪录矩阵的列数，down=right=0（不用），value为指针字段，指向第一个行列表头结点。 row col value down right

3.5.2 矩阵的压缩存储

3.6  树 在线性表、堆栈、队列等线性结构中，元素之间的关系是线性的，描述了元素之间的先后次序。但在大量的实际问题中，对象之间的关系是错综复杂的。例如，人类社会的家族族谱、各种社会组织机构、一本书的章节目录等等，它们都无法用线性结构来描述。 在计算机科学中，树型结构是一类重要的非线性数据结构，它可以很好的表达元素之间的层次关系。 本节内容： 3.6.1 树的基本概念及存储结构 3.6.2 二叉树 3.6.3 常用操作及算法

在计算机科学中，树结构是指元素间具有层次关系的非线性结构，元素之间用分支来连接，非常类似于自然界中的树。下面是树的严格定义： 3.6.1 树的基本概念及存储结构 在计算机科学中，树结构是指元素间具有层次关系的非线性结构，元素之间用分支来连接，非常类似于自然界中的树。下面是树的严格定义： 树（tree）是n（n≥0）个结点的有限集。在一棵非空树中：（1）有且仅有一个特殊的结点，称为树根（root）； （2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1,T2,…,Tm，且其中的每一个集合也是一棵树。T1,T2,…,Tm称为根的子树。 上述树的定义是一个递归定义，递归是树的固有特性。

3.6.1 树的基本概念及存储结构 a) 只包含根结点 (b) 一般的树 (a) 树的嵌套集合表示 (b) 树的凹入表示 图3-19一般的树型结构 图3-20 树型结构的其它表示形式

3.6.1 树的基本概念及存储结构 1．常用术语 树是由一系列的结点构成的，每个结点都包含一个数据元素及若干指向其子树的分支。 结点的度：任一结点V拥有的子树的个数称为结点的度（degree），记作d（V）。 叶子（叶结点）：度为0的结点称为叶子（leaf）或终端结点。 分支结点：度不为0的结点称为非终端结点或分支结点。除根结点外，分支结点又称为 内部结点。 树的度：树中所有结点度的最大值称为树的度。 结点的层数（level）：树描述了数据的层次结构，从树的根开始，称为树的第一层，根的孩子结点为第二层，以此类推。 树的深度：树种结点层数的最大值称为树的深度（depth）。 森林（forest）：是m（m≥0）棵互不相交的树的集合。 。 结点间的关系： 结点的子树的根称为该结点的孩子（child），该结点称为孩子的双亲（parent）。 同一双亲的孩子结点称兄弟（sibling）。 双亲在同一层的结点互为堂兄弟。 结点的祖先是从根结点到该结点所经分支上的所有分支结点。 以某结点为根的所有的子树结点中的任一结点都成为该结点的子孙。

3.6.1 树的基本概念及存储结构 2．树的存储结构 树最自然的存储结构为链式存储。由于树中每个结点的度数不同，可以用多重链表来实现，即每个结点有多个指针域，每个结点的指针字段根据结点的度来决定，每个指针指向一棵子树的根 。 在上述的多重链表结构中，结点是异构的，各个结点具有不同的长度，这在程序设计中难以实现。还可以定义下面的节点结构：

3.6.1 树的基本概念及存储结构 几种常用的链表结构： 1 ）双亲表示法 用一组连续的空间存储树的结点，每个结点包括两个字段，一个维信息域，另一个为指针域，指向该结点的父结点。形式说明如下： #define MAXNODENUM 100 typedef char ElementType;     typedef struct{ ElementType data;  //结点类型     int parent;         //父结点指针 } TreeNode;  TreeNode  tree[MAXNODENUM] ; 图3-21所示树的双亲表示法对应的存储结构如图3-22所示。 在双亲存储结构中，求结点的双亲、结点的子结点等操作比较简单。

3.6.1 树的基本概念及存储结构 孩子表示法是指用一个连续的存储空间存储每一个结点，结点结构如下所示： 2）孩子表示法 孩子表示法是指用一个连续的存储空间存储每一个结点，结点结构如下所示： 其中，data为结点数据，next指向孩子结点构成的一个链表。形式定义如下： #define MAXNODENUM 100 typedef char ElementType; //为了讨论方便，设元素类型为char typedef struct cn{       int child;   // 孩子节点在数组中的序号       struct cn *next; } ChildNode; typedef struct c {      ElementType data;      ChildNode *firstchild; } TreeNode; TreeNode  tree[MAXNODENUM]; 图3-19(b)树对应的孩子表示法如图3-23所示。 data next

fch data nsib 3.6.1 树的基本概念及存储结构 孩子兄弟表示法又称二叉树表示法，或二叉链表表示法。结点结构如下所示： 3）孩子兄弟表示法 孩子兄弟表示法又称二叉树表示法，或二叉链表表示法。结点结构如下所示： fch和nsib为指针域，指向该结点的第一个孩子和其下一个兄弟结点。形式定义如下： typedef  struct tn { ElementType  data;         struct tn *fch;         struct tn *fnsib } TreeNode,*Tree; 图3-19(b)所示树对应的孩子兄弟表示法如图3-24所示。 fch data nsib

3.6.2 二叉树 图3-25二叉树的五种形态 二叉树（binary tree）是另一种类型的树型结构。 3.6.2 二叉树 二叉树（binary tree）是另一种类型的树型结构。 二叉树：是n（n≥0）个结点的有限集合，或者是空集，或者是由一个根和称为左右 子树的两个不相交的二叉树构成。 根据上面的定义，二叉树和树是两个不同的概念，二叉树不是树的特例。 他们的区别包括（1）树的子树没有顺序，二叉树的两棵子树有左右之分。 （2）树中结点的度是任意的，二叉树中每个结点的度不能大于2。由此，二叉树共有5种不同的形态，如图3-25所示。 （1）空二叉树 （2）只包含根 （3）右子树空 （4）左子树空 （5）左、右子树不空 图3-25二叉树的五种形态

3.6.2 二叉 树 二叉树具有下列重要的特性： 性质一： 在二叉树的第i（i≥1）层上的结点数最多为2i-1。 下面用递归法证明该性质。 i=1时，只有一个根结点。显然，2i-1=21-1=1，命题成立。 假定对所有的1≤j<i命题成立，即在j层的结点数最多为2j-1。现证明j=i时命题成立。 由归纳假设，第i-1层上结点的最大数目为2i-2。由于二叉树中每个结点的度最大为2， 因此，第i层上结点的最大数目为第i-1层上结点数目的2倍，即为2×2i-2=2i-1。 故，性质一得证。 性质二： 深度为k的二叉树至多有2k-1个结点。 由性质一可知，在二叉树的第i（i≥1）层上的结点数最多为2i-1。 深度为k的二叉树的结点数最多为： 至多有2k-1个结点。

3.6.2 二叉 树 性质三： 对于任意二叉树T，假设终端结点树为n0，度为2的结点树为n2，则有n0=n2+1。 下面我们来看二叉树中的分支，在二叉树中，每一个结点引出的分支数目为该结点的度， 因此总的分枝数为： B = n1 + 2 n2        （3.2） 另外，在一棵二叉树中，除了根结点以外，每一个结点都是有一个分支引出， 因此有 B = n -1               （3.3） 根据（3.2）和（3.3），n1 + 2 n2 = n –1，n = n1 + 2 n2+ 1。代入（3.1）得： n1 + 2 n2+ 1 = n0 + n1 + n2，得n0=n2+1。 两种特殊的二叉树—满二叉树和完全二叉树。 满二叉树：若深度为k的二叉树且结点个数恰好为2k-1，则称它为深度为k的满二叉树。 完全二叉树：深度为k并且具有n个结点的二叉树是一棵完全二叉树，当且仅当其每一个结点都与 深度为k的满二叉树中编号为1~n的结点一一对应。否则为非完全二叉树。

3.6.2 二叉 树 性质四 ：具有n个结点的完全二叉树其深度为└log2n┘ + 1 或┌log2（n + 1)┐ 。 图3-26 深度为4的满二叉树 图3-27 深度为4的完全二叉树            图3-28 深度为4的非完全二叉树 性质四 ：具有n个结点的完全二叉树其深度为└log2n┘ + 1 或┌log2（n + 1)┐ 。 证明：设具有n个结点的完全二叉树其深度为k，则有：2k-1-1<n≤2k -1 其中，2k-1-1和2k–1分别为深度为k-1和深度为k的满二叉树结点的数目。 因此有： 2k-1≤n<2k 取对数后，即：k-1≤log2n<k。 因为k为整数，因此有：k=└log2n┘ + 1。命题得证。 性质五 :对一棵具有n个结点的完全二叉树的结点，从根开始，按照从上到下，自左至 右的顺序连续编号为1~ n，则对于任意结点i（1≤i≤n）有： （1）如果i=1，则结点i是二叉树的根。若i>1，则结点i的父节点的编号为[i/2]。 （2）若2i≤n，则结点i左孩子的编号为2i；否则无左子树。 （3）若2i+1≤n，则结点i右孩子的编号为2i+1；否则无右子树。

3.6.2 二叉 树 证明：首先证明（2）和（3）,由（2）和（3）可以推出（1）。归纳证明如下： ①对于i=1：结点i=1为根结点，根据编号原则，如果存在左右儿子，编号应该分别为2和3。 若n≥2，则结点i（i=1）的左孩子编号为2（2i=2），否则无左子树； 若n ≥ 3 则结点i（i=1）的右孩子编号为3 （2i+1=3）， 否则无右子树。 性质（2）、（3）成立。 ② 对于i>1：假设对于所有序号为j（1<j<i）的结点性质（2）、（3）成立， 即：结点j的左孩子编号为2j（2j≤n），右孩子编号为2j+1（2j+1≤n）。 ③下面证明j=i时命题成立 对于任意两个编号连续的节点i-1和i，存在下面两种情况： （a）结点i-1和结点i在同一层(图3-29(a))； （b）结点i-1和结点i在相邻的两层，其中结点i-1为上一层的最后一个结点，结点i为 下一层的第一个结点（图3-29(b)）。

3.6.2 二叉 树 结点j（1<j<i）的左孩子编号为2j（2j≤n），右孩子编号为2j+1（2j+1≤n）， 因此结点i-1的左孩子结点编号为2(i-1)，右孩子结点编号为2(i-1)+1=2i-1。 设结点i是二叉树的j层上的第一个结点，由性质二知：i=2j-1， 则i结点的左孩子必为j+1层的第一个结点其编号为2j=2（2j-1）=2i，若2i≥n则无左孩子； i结点的右孩子必为j+1层的第二个结点其编号为2i+1，若2i+1≥n则无右孩子； 设结点i是二叉树的j层上的一个结点，且2i+1 ≤n，则其左孩子为2i，右孩子为2i+1 结点i+1为结点i的右兄弟或堂兄弟，若其有左孩子，其编号必2i+1+1=2（i+1） 若其有右孩子，其编号必2（i+1）+1 即当j=i时性质(2)、(3)成立。 ④由性质（2）和性质（3）可知，对于任意结点i其父节点的编号为└ i/2 ┘ 。

3.6.3 常用操作及算法 二叉树的遍厉算法 由于二叉树的子树右左右之分，因此二叉树的遍理分成下面三种情况： 3.6.3 常用操作及算法 关于树的操作及算法大多基于树的遍历算法，本小节主要介绍二叉树的遍历算法。其他复杂的算法，如线索二叉树、树与森林的转换等请读者参考文献 。 树的遍历算法： 根据树的递归定义，树的遍历可以分成两大类： （1）先根遍历，即先访问根，然后遍厉每一棵子树； （2）后根遍历，即先遍厉每一棵子树，最后再访问根。 这里所说的“访问”具有广泛的含义，可以是对结点信息的任意操作。 二叉树的遍厉算法 由于二叉树的子树右左右之分，因此二叉树的遍理分成下面三种情况： 1．二叉树的中序遍厉 2．二叉树的前序遍厉 3．二叉树的后序遍厉 若二叉树为空，返回； 若二叉树为空，返回； 若二叉树为空，返回； 否则: (1) 中序遍厉左子树 否则: (1)访问根结点 否则:(1)后序遍厉左子树 (2)访问根结点 (2)前序遍厉左子树 (2)后序遍厉右子树 (3)中序遍厉右子树 (3)前序遍厉右子树 (3)访问根结点

3.6.3 常用操作及算法 二叉树采用链式存储结构，具体定义如下： typedef struct bt {     ElementType data;     // 元素类型ElementType可以定义成int、char等     Struct bt *lchild, *rchild;  // 指向左右儿子的指针 } BinaryTreeNode,*BTRoot; 中序遍厉二叉树算法的表述如下： // 二叉树中序遍厉算法 InOrder(BinaryTreeNode *root) {   if (!root) return 0;   else {       InOrder(root->lchild);       printf("%c",root.data);   // 访问根结点 InOrder(root->rchild);         } }

3.6.3 常用操作及算法 前序遍厉二叉树算法的表述如下： // 二叉树前序遍厉算法 BeOrder(BinaryTreeNode *root) {  if (!root) return 0;   else {    printf("%c",root.data);   // 访问根结点 BeOrder(root->lchild);        BeOrder(root->rchild);         } } 后序遍厉二叉树算法的表述如下： // 二叉树后序遍厉算法 AfOrder(BinaryTreeNode *root)   else { AfOrder(root->lchild);        AfOrder(root->rchild); printf("%c",root.data);   // 访问根结点

3.6.3 常用操作及算法 例如 二叉树如图 其存储结构如图: 则其前序遍历的结果：A、B、C、D、E、F 其中序遍历的结果：C、B、D、A、E、F 其后序遍历的结果：C、D、B、F、E、A

/* 先根遍历根指针为t的二叉树以计算其叶子数count;假定count的初值为0*/ 3.6.3 常用操作及算法 例：求二叉树的叶子数。 　　可以将此问题视为一种特殊的遍历问题，这种遍历中“访问一个结点”的具体内容为判断该结点是不是叶子，若是则将叶子数加1。显然可以采用任何遍历方法，这里用前序遍历。 算法如下： void countleaf(BinaryTreeNode *t，int *count) /* 先根遍历根指针为t的二叉树以计算其叶子数count;假定count的初值为0*/ { if(t!=NULL) 　{ if((t->lchild==NULL)&&(t->rchild==NULL)) 　　 *count++; /*若t所指的结点是叶子，计数器加1*/ 　　countleaf(t->lchild,count); /*累计左子树上的叶子数 */ 　　countleaf(t->lchild,count); /*累计右子树上的叶子数 */ 　} }

3.7 图 本节内容： 3.7.1 图的基本概念 3.7.2 图的存储 3.7.3 图的遍历算法 3.7.4 图的应用 3.7 图 图（Graph）是比线性表和树更为复杂的数据结构，图本身有其完整的理论—图论。图论是近几年发展较快的数学分支，在许多领域有着广泛的应用。在数学、计算机科学等学科领域，图论本身就是一门独立的课程，在数据结构中，我们重点介绍图的基本概念、存储结构和基本算法。 本节内容： 3.7.1 图的基本概念 3.7.2 图的存储 3.7.3 图的遍历算法 3.7.4 图的应用

3.7.1 图的概念 在线性结构中，数据元素之间是一种线性关系（次序关系），每一个元素都有一个惟一的前驱结点和一个后继结点（第一个元素没有前驱，最后一个元素没有后继）。在树形结构中，元素之间是一种层次关系，除根以外的每个结点都有一个惟一的父结点（根结点没有父结电）和零个或多个子结点。而在图结构中，元素之间的关系是任意的，图中任意的两个元素之间都可能相关。 1．图和有向图的定义 图G是由两个集合V(G)和E(G)构成的，记作G=(V(G)，E(G))，或简记作G=(V,E)，其中V(G)是顶点的非空有穷集合， E(G)是边的有穷集合，边表示元素之间的关系。 图通常用图形来形象的描述，用圆圈来表示顶点， 连接两个顶点的线段来表示边。图的图形表示如图所示。 G1和G2是无向图，G3和G4为有向图。

3.7.1 图的概念 无向图，其边是顶点的无序对，即边没有方向性。若顶点x和顶点y之间有一条边，记作（x,y）。 有向图，其边是顶点的有序对，即边有方向性，又称为“弧”（Arc）。为了与无向图的边相区别，从顶点x到顶点y的有向边（弧）用<x,y>来表示，且称x为“弧尾”（Tail），y为“弧首”（Head）。 若一条边（或弧）的两个顶点相同，则称其为“圈”。 若图G不存在圈，也没有两边（或弧）连接同样两个顶点，则称这样的图为“简单图”。 对于简单图，n个顶点的无向图最多有n(n-1)/2条边，其中任意的两个顶点之间都有边相连，称为“完全图”。 有向图具有n(n-1)条弧的的简单图称为“有向完全图”。 注意：在图的图形表示中，两条边的交点不一定是图的顶点。对于一个图，若存在一种画法，使其边仅在顶点处相交，则称其为“平面图”。图3-31中的G1、G2、G3和G4均为平面图，图3-33所示为一个非平面图的例子。

3.7.1 图的概念 2．子图 若图G={V,E}和G’={V’,E’}满足条件：（1）V’V；(2) E’E，则称G’为图G的“子图”（Subgraph），记作G’G。由定义可知，任何图G都是它本身的子图。如果G’G，但G’G，则称G’为图G的“真子图”，记作G’G。 若G’G，且V’=V，E’E，即两个图的顶点集相同，而G’的边集是G的边集的子集，则称G’是图G的“支撑子图”。 图G1的部分子图如图所示 3．关联与邻接 关联是顶点和边（或弧）之间的关系，一条边和它所连接的顶点是相关联的。一个顶点可以和多条边关联。 邻接是顶点和顶点之间、边和边之间的关系，和同一条边（或弧）相关联的两个顶点是邻接的，有共同顶点的两条边也是邻接的。 4．顶点的度 图中顶点v的度（degree）是指和顶点v相关联的边的条数，记作d(v)。 对于有向图，度又分为“入度”（Indegree）和“出度”（Outdegree）。顶点v的“入度”是指以v为终点（弧头）的弧的条数，记作ID(v)；v的“出度”是指以v为始点（弧尾）的弧的条数，记作OD(v)。有向图顶点v的度记作TD(v)，有TD(v)= ID(v)+ OD(v)。

3.7.1 图的概念 5．路径、通路和回路 6．连通图和图的连通分量 图G=(V,E)中从顶点v到顶点v’的一条路经是一个有穷非空序列 若图中有n个顶点，e条边，每个顶点vi的度为di，则存在下列关系： 5．路径、通路和回路 图G=(V,E)中从顶点v到顶点v’的一条路经是一个有穷非空序列 w=（v=vi0, vi1,…vik=v’），其中（vij-1, vij）E，1≤j≤m。顶点v和v’分别为路径w的起点和终点。路径中边的数目k称为路径的“长度”。起点和终点相同的路径称为“回路”或“环”（Cycle）。序列中顶点不重复出现的路径称为“简单路径”。顶点v到v’存在一条路经，则称v到v’有一条“通路”。 6．连通图和图的连通分量 在无向图中，定点vi和vj之间存在一条通路，则成vi和vj之间是连通的。若图G中，任意两个不同的顶点vi和vj之间都是连通的，则称G为“连通图”。 在有向图中，若顶点vi和vj之间存在一条从vi到vj的通路或从vi到vj的通路，则称vi和vj之间是连通的。若有向图G中，任意两个不同的顶点vi和vj之间都存在一条从vi到vj和一条从vj到vi通路，则称有向图G为“强连通图”。

3.7.1 图的概念 有向图中，极大的强连通子图称为它的“强连通分量”。无向图的“连通分量”是它的极大连通子图。所谓极大，是指再加入一个顶点或边，将不满足图的连通性。一个图G的连通分量可以有多个，每一个连通分量都是图G的连通子图（G的子图，且是连通图）。图3-35为一个图G5和它的连通分量。 7．网与图的权 在实际应用中，图中的边或弧往往给定一个权（Weight），这种带权的图即是网。 例如可以用图表示城市之间的交通网，边的权可以表示两个城市之间的距离、时间，甚至是从一个城市到达另一个城市所需要的费用等。 8．生成树 一个连通图G的生成树是图G的极小连通子图， 它含有图中全部顶点，但只有足以构成一棵树的n-1条边。 如果在生成树上添加一条边，必定构成一个环。因为这条边关联的两个顶点之间有了第二条路经。如果减少一条边，他一定是非连通的。因为，要连接n个顶点，至少需要n-1条边。但是，有n-1条边的图不一定是生成树。

3.7.2 图的存储 图的结构比较复杂，任意的两个顶点之间都可能存在关系，因此图的存储结构也很多。无论采用什么形式的存储结构，都离不开静态存储（顺序存储）和动态存储（链式存储）的范畴。在定义具体的存储结构时，应该根据具体的应用来决定采用的存储结构，从而便于算法的实现。 1. 邻接矩阵（顺序存储） 设图G=（V,E）具有n个顶点V1,V2,…,Vn和m条边e1，e2,…,em，则G的邻接矩阵是一个nn阶矩阵，记作A(G)，其每一个元素定义如下： 图G1和G4的邻接矩阵

CreateAM(MGraph *G) // 构造图Ｇ的邻接矩阵 { int I,j,k,q; 3.7.2 图的存储 图的邻接矩阵定义： #define MAX 100000 // 表示极大值 #define MAX_VERTEX_NUM 100 // 最多的顶点个数 typedef char VertexType ； // 图的顶点类型 typedef int EdgeType； //图的边的权值类型。 typedef struct { VertexType vexs[MAX_VERTEX_NUM]; // 顶点信息类型，由具体应用而定义 EdgeType AdjMatrix[MAX_VERTEX_NUM, MAX_VERTEX_NUM]; // 图的邻接矩阵 int vexnum,arcnum; // 图的实际顶点数和弧（边）数 ｝MGraph; 图的邻接矩阵建立算法： CreateAM(MGraph *G) // 构造图Ｇ的邻接矩阵 { int I,j,k,q; scanf(“%d%d”,&G->vexnum,&G->arcnum); //输入图Ｇ的实际顶点数和边（或弧）数目 for (i=0;i<G->vexnum;i++) scanf(“%c”,&G->vex[i]) ；//输入顶点信息，建立顶点表 for (i=0;i<G->vexnum;i++) // 图的邻接矩阵初始化 for (j=0;j<G->vexnum;j++) G->AdjMatrix[i,j)=0; for (k=0;k<G->arcnum;k++) // 图的邻接矩阵的边值 {scanf(“%d%d%d”,&I,&j,&q); G->AdjMatrix[i,j)=q; G->AdjMatrix[j, i)=q;} }

3.7.2 图的存储 2. 邻接表 与逆邻接表（链式存储） 邻接表存储结构的定义： 3.7.2 图的存储 2. 邻接表 与逆邻接表（链式存储） 所谓“邻接表”（adjacency list）就是对图中的每个顶点与它相关联的所有边建立一个单链表，每个链表的头结点保存该顶点的有关信息，链内其它结点，保存与该顶点向关联的边的信息。对于有向图，第i个 单链表存储以顶点Vi为尾的弧。结构形式定义如下： 邻接表存储结构的定义： #define MAX_VERTEX_NUM 100 typedef struct ArcNode{ int adjvex; // 按需定义边或弧的其他信息arcinfo struct ArcNode *nextarc; } ArcNode; typedef struct VexNode { // 按需定义顶点信息 VertexType vertex； //顶点域 ArcNode *firstarc; //指向第一条向关联的边或弧 } VexNode； typedef struct { int vexnum,arcnum; //图的顶点数和边或弧的数目 VexNode vertices [MAX_VERTEX_NUM]; //图的顶点数组 } AdjListGraph

3.7.2 图的存储 G1和G4对应的邻接表与逆邻接表 (a) 图G1邻接表 (b) 图G4邻接表 (c) 图G4逆邻接表

3.7.2 图的存储 3. 邻接多重表（链式存储） 在无向图的邻接表表示中，每条边（Vi,Vj）对应了第i和第j个单链表中的两个结点，不仅浪费了空间，而且增加了算法实现上的复杂性。. 对于无向图，可以用邻接多重表（adjacency multilist）来表示。在邻接多重表中，头结点和邻接表相同，每条边用一个结点来表示，表示边的结点可以被多个链表所共用。 链内结点: 无向图邻接多重表的定义: #define MAX_VERTEX_NUM 100 typedef EdgeNode { int vi,vj; // 顶点Vi和Vj在头结点数组中的位置（下标） struct EdgeNode *ilink, *jlink; //按需定义边的其它信息，例如：带权图中边的权值等。 } EdgeNode； typedef struct Vnode { VertexType vertex； //按需定义顶点的有关信息 EdgeNode * firstedge; }VNode; typedef struct { int vexnum,arcnum; VNode vertices[MAX_VERTEX_NUM]; } AdjMultiListGraph; vi vj ilink jlink

3.7.2 图的存储 G1对应的邻接多重表 图G1邻接多重表

#define MAX_VERTEX_NUM 100 3.7.2 图的存储 4. 十字链表（链式存储） 十字链表（orthogonal list）是有向图的另一种链式存储结构，它是有向图的邻接表和逆邻接表的结合。在十字链表中，对应于有向图的每个顶点和每一条弧都有一个结点，所有的顶点结点存储在一个连续的数组中。顶点结点和弧结点结构定义如下： 有向图十字链表存储结构定义形式 #define MAX_VERTEX_NUM 100 typedef struct ArcNode { int vi,vj; struct ArcNode * taillink, *headlink; //按需定义弧的其他信息，如带权图中弧的权等 } ArcNode; typedef struct Vnode { VertexType vertex； //按需定义顶点的有关信息 ArcNode *firstin, *firstout; } VNode; typedef struct { int vexnum,arcnum; VNode vertices[MAX_VERTEX_NUM]; //图的顶点数组 } OLGraph

3.7.2 图的存储 G4对应的十字链表 G4对应的十字链表

3.7.3 图的遍历 图的遍历通常分成深度优先搜索和广度优先搜索两种，两种搜索均适用于无向图和有向图的遍历。 1. 深度优先搜索 当给定图G=(V,E)后，一个最基本的问题就是对于顶点集中的任意顶点V0，从V0出发访问图中的所有顶点，且每一个顶点只访问一次。这一过程称为图的遍历（Traversing Graph），又称图的扫描。图的遍历算法是解决图的连通性问题、拓扑排序以及关键路经等算法的基础。 图的遍历通常分成深度优先搜索和广度优先搜索两种，两种搜索均适用于无向图和有向图的遍历。 1. 深度优先搜索 深度优先搜索递归算法描述如下： 设 从V0出发，V0为图中任意给定的顶点。 (1) 访问V0，对V0作已访问标记。 (2) 找出与V0邻接未被访问的顶点W，按深度优先搜索与W邻接的未作标记的顶点。 (3) 若与V0邻接顶点皆已作访问标记，则返回；否则，找出与V0邻接的未被访问的所有顶点W，按深度优先搜索与W邻接的未作标记的顶点。 #define MAX_VERTEX_NUM 100 typedef struct ArcNode{ int adjvex; // 按需定义边或弧的其他信息arcinfo struct ArcNode *nextarc; } ArcNode; typedef struct VexNode { // 按需定义顶点信息 VertexType vexdata； //顶点域 int Visited ArcNode *firstarc; //指向第一条相关联的边或弧 } VexNode,AdjList[MAX_VERTEX_NUM]； typedef struct { int vexnum,arcnum; //图的顶点数和边或弧的数目 VexNode vertices [MAX_VERTEX_NUM]；; //图的顶点数组 } AdjListGraph;

深度优先搜索算法: void GraphDFSTraverse(AdjListGraph *G) // 图G采用邻接表存储，深度优先搜索G 3.7.3 图的遍历 深度优先搜索算法: void GraphDFSTraverse(AdjListGraph *G) // 图G采用邻接表存储，深度优先搜索G { int v; ArcNode *arc; for (v=0;v<G->vexnum;v++) G->vertices[v].Visited=0; if (!G->vertices[v].Visited) DFS(G,v); }  void DFS(AdjListGraph *G,int v) { G->vertices[v].Visited =1; // 对顶点v作访问标记 printf(“%c”,G->vertices[v].vexdata); // 访问顶点v，例如：输出顶点信息 for (arc=G->vertices[v].firstarc; arc; arc= arc-> nextarc) { w = arc->adjvex if (!G->vertices[w].Visited) DFS(G,w);

3.7.3 图的遍历 广度优先搜索算法: void GraphDFSTraverse(AdjListGraph *G) // 图G采用邻接表存储，深度优先搜索G { int v,u; ArcNode *arc; for (v=0;v<G->vexnum;v++) G->vertices[v].Visited=0; initQueue（&Q）； if (!G->vertices[v].Visited) { G->vertices[v].Visited =1; // 对顶点v作访问标记 printf(“%c”,G->vertices[v].vexdata); // 访问顶点v，例如：输出顶点信息 enterqueue（&Q, v）； while（ ！emptyqueue（&Q）） { delQueue（&Q，&u）； for (arc=G->vertices[u].firstarc; arc; arc= arc-> nextarc) { w = arc->adjvex if (!G->vertices[w].Visited) printf(“%c”,G->vertices[v].vexdata); enterqueue（&Q, v）； } } } } }

3.7.3 图的遍历 深度优先搜索： 广度优先搜索： v1 v2 v4 v8 v5 v3 v6 v7 v1 v2 v3 v4 v5 v6 v7 v8

3.7.4 图的应用 图结构在许多方面有着重要的应用，在介绍了图的概念和图的遍历算法后，我们将概要的列出图的一些重要应用。 3.7.4 图的应用 图结构在许多方面有着重要的应用，在介绍了图的概念和图的遍历算法后，我们将概要的列出图的一些重要应用。 1. 生成树和最小生成树 当G为连通图时，G的具有下属性质的子图T称为G的生成树（又称支撑树）： (1) T包含G的所有顶点； (2) T为连通图； (3) T包含的边数最少。 图G的生成树T是包含G的所有顶点的最小连通子图。 对于给定的连通图G，可从G的任一顶点出发，作深度优先或广度优先遍历，即可将图G中的所有 顶点都访问到，而经过的G的边集即可构成生成树的边集。 图G的最小生成树T是各条边的权值总合最小的生成树

3.7.3 图的应用 2. 最短通路问题 图也常常用于表示城市之间的交通网，用顶点表示城市，边表示城市之间的道路，可以带权（表示公路 段的长度或沿公路段行驶需要花费的时间）。上述问题可以归结为图的最短通路问题。对于图的最短通路问题，Dijksta于1956年提出了图的最短通路算法Short-Path。 如果要求任意两个顶点之间的最短通路，可以反复的执行Dijkstra算法，Floyd提出了另外一个概念上更简单的算法—所有顶点对之间的最短通路算法。 3. AOV网络与拓扑排序 除了最简单的情况外，几乎所有的工程都可以分为若干个称作活动（Activity）的子过程，完成了这些子过程便导致整个工程的结束。 对于整个工程或系统，人们往往关心两个问题， 一是工程能否顺利进行，二是估算工程完成必需的最短时间。 第一个问题，称为拓扑排序问题，第二个问题为图的关键路经问题。 如果有向图为非赋权图，图中的顶点表示活动，有向边表示活动之间的优先关系，这样的有向图称为AOV网络。 在AOV网络中，若<vi,vj>是G中的有向边，则vi是vj的直接前驱，vj是vi的直接后继。所谓拓扑排序问题就是产生这样的顶点序列：若网络中，vi是vj的前驱，则在序列中，vi在vj的之前。有这种特性的序列称为拓扑有序。 进行拓扑分类的算法可以简单描述如下： (1) 在网络中选一个没有先驱的顶点输出； (2) 从网络中删除该顶点和从他引出的所有弧； (3) 重复上述过程直至全部顶点被输出或者网络中没有无先驱的顶点位置。前者说明网落实拓扑有序的，后一种情况说明网络中存在环。存在环的工程将无法顺利进行。

3.7.3 图的应用 拓扑排序：V1， v2 ，v3，v4，v8，v5，v6，v7，v8 4．AOE网络与关键路径问题 若有向图G为含权图，顶点表示事件，有向边表示活动，权标是活动的持续时间，此有向图称为AOE网络。 在AOE网络中，顶点表示事件，事件可以表示某些活动的完成，有顶点出发的边表示某项活动，这项活动只有在该顶点所代表的事件发生后才能够开始，而事件只有当进入它的边代表的全部活动都已经完成后才能发生。除了正常的活动外，为了描述问题的需要，还可以增加持续事件为0的虚拟活动。

3.7.3 图的应用 在AOE网络中，某些活动可以并行进行，完成工程的最短时间是从开始顶点（也称源点）到结束顶点（又称终点）最长路径的长度（路径上所有活动的时间和）。最长路经又称为关键路经（或临界路径）。加速关键路径上的关键活动（最早和最迟时间相等的活动），可以缩短整个工程的期限。

3.8 查找 本节内容： 3.8.1 基本概念 3.8.2 顺序查找 3.8.3 折半查找 3.8.4 二叉排序树和二叉平衡树 3.8 查找 随着计算机的发展，计算机开始应用于事务处理，如会计、企业管理等非数值计算领域，这就是所说的“数据处理”。数据处理的特点是，面对的数据量巨大，对数据的处理不是数学计算，主要是查询、排序、统计分析等。 在计算机的数据处理中，查找和排序是两类主要的操作，两者密切相关。 本节内容： 3.8.1 基本概念 3.8.2 顺序查找 3.8.3 折半查找 3.8.4 二叉排序树和二叉平衡树 3.8.5 B－树和B＋树 3.8.6 哈希表

3.8.1 基本概念 文件（file）是若干条结构相同的记录构成，文件一般存储在外存储器中，用于永久的保存信息。 3.8.1 基本概念 文件（file）是若干条结构相同的记录构成，文件一般存储在外存储器中，用于永久的保存信息。 记录（record）是由若干个相关的字段构成。 字段（field）是最小的不可分割的数据单位，每个字段都有一个特定的数据类型。 关键字是记录中的一个字段，用它来标志和控制一个记录。 能够惟一的标志与控制一个记录的关键字称为主关键字，其它的称为辅关键字（次关键字）。 查找（Searching）问题的一般描述： 给定一个文件（或表）F={R1, R2,…, Rn}，其中Ri是以Ki（i=1,2,…,n）为主关键字的记录。现给定一个主关键字K，在文件F中确定具有主关键字K的记录R的地址或序号i，使得Ki=K。 查找问题通常又称为“检索”。查找（或检索）的结果有两种可能： 1) 找到了具有主关键字值K的记录Ri，称为查找成功； 2) 没有找到主关键字值为K的记录，称为“查找失败”。

3.8.2 顺序查找 typedef int ElementType; // 设元素类型为整数 3.8.2 顺序查找 一、顺序查找（Sequential Serach）的基本步骤 从最后一条记录开始，按照记录的逻辑次序，将给定的关键字K和当前记录的关键字逐个比较，若某个记录的关键字和给定值相等，则查找成功，返回成功记录的序号；反之，直到比较完第一条记录，找不到与给定值相等的记录，则查找失败，返回一个特殊标记。 顺序查找是一种最基本、最简单的检索方法，他对于文件（或表）的组织没有限制。 二、线性表静态顺序存储数据结构和查找算法 顺序表的数据结构定义： typedef int ElementType; // 设元素类型为整数 typedef struct { ElementType elements[maxsize]; // 从1号单元开始存储数据元素， int length; // 表的实际长度（数据元素个数） } SearchTable; 顺序查找算法的C语言描述如下： int Search_Sequential(SerachTable *st，ElementType k) // 在线性表st中查找关键字k，若成功返回位置，否则返回0 { i=st->length; st->elements[0] = k; // 设置“哨兵” while (st->element[i] != k) i -= 1; return i }

3.8.3 折半查找 一、折半查找（Binary Search）的思想 如果文件（或表）中的记录是按照关键字有序的，查找问题可以用效率较高的折半查找（Binary Search）。 假定关键字值K1< K2<…< Kn，要查找关键字值为K的记录，折半查找的基本思想是： 首先选取表的中间元素，设序号为m= (1+n)/2，元素Rm将数据表分成大致相等的两部分{R1, R2,…, Rm-1}和{Rm+1, Rm+2,…, Rn}。先对Km和K作比较，比较结果分三种情况： (1) K=Km：查找成功，返回元素序号m。 (2) K<Km：折半查找子表{R1, R2,…, Rm-1}。 (3) K=Km：折半查找子表{Rm+1, Rm+2,…, Rn}。 对子表的查找按照上述原则进行，直到查找成功或要查找的子表的长度为0。 二、折半查找算法 int Serach_Binary(SerachTable *st,Element k) // 在线性表st中折半查找关键字k { int low ，high; low = 1; high = st->length; while (low<high) { m = (low+high)/2; if (k = = st->elements[m] ) return m; else if (k >st->elements[m] ) low = m+1; else high = m-1; } return 0; }

3.8.3 折半查找 三、折半查找过程示例： 下标 1 2 3 4 5 6 7 8 9 10 11 第一次比较 [5 13 19 21 37 56 64 75 80 88 92] ↑ 第二次比较 [5 13 19 21 37] 56 64 75 80 88 92 第三次比较 5 13 19 [21 37] 56 64 75 80 88 92 （1） 查找K=21的过程（三次比较后查找成功） 下标 1 2 3 4 5 6 7 8 9 10 11 第二次比较 5 13 19 21 37 56 [64 75 80 88 92 ] 第三次比较 5 13 19 21 37 56 64 75 80 [88 92 ] 当前表已空 5 13 19 21 37 56 64 75 80] [88 92 （2）查找K=85的过程（三次比较后查找失败）

3.8.3 折半查找 四、折半查找树 折半查找过程可用二叉树描述，把当前查找区间的中间位置上的结点作为根，左子表和右子表中的分别作为根的左子树和右子树，由此得到的二叉树称为折半查找树或二叉判定树。 如有序表：[2 5 6 10 15 21 26 30 56 78] 在二叉判定树中，查找结点时比较的最大次数为判定树的深度：h =└log2n┘ + 1

3.8.4 二叉排序树和平衡二叉树 在表的顺序查找和折半查找过程中，数据表本身是不变的，因此又称为静态查找。对于有些查找算法，数据表结构是在查找过程中动态构建的，称为动态查找。本小节介绍主要的动态查找算法的基本思想。 1．二叉排序树 二叉排序树（Binary Sort Tree）或者是一棵空树；或者是具有下列性质的二叉树： (1) 若左子树不空，则左子树中所有节点的值均小于它的根节点的值； (2) 若右子树不空，则右子树中所有节点的值均大于它的根节点的值； (3) 它的左子树和右子树均为二叉排序树。 和折半查找树不同，二叉检索树是一个真正存在的二叉树结构，可以用链式结构来存储。折半查找树是描述了静态有序数据表的查找比较过程，并不是一个真正的数据结构。

AVL树的定义： 若二叉查找树T非空，则它为AVL树的充要条件为： 3.8.4 二叉排序树和平衡二叉树 2．平衡二叉树 我们已经知道，二叉排序树是动态构造的，如果构造的二叉树是完全二叉树或拟完全二叉树，则平均查找长度和最大查找长度都可以达到极小值。但是，按照二叉排序树的思想，得到的二叉树不一定是平衡的，二叉树的结构是由输入数据的顺序决定的。 在二叉排序树不平衡的情况下，检索效率将会降低。为了提高二叉排序树的查找效率，Adelson-Velskii-Landis于1962年提出了构造动态平衡二叉检索树的方法，这种树称为AVL树。AVL树又称为平衡二叉树（Balanced Binary Tree）或均高树（High Balanced Tree）。 （1）平衡因子与AVL树的定义 首先引入平衡因子（Balanced Factor）的概念。 设a为二叉查找树中的任一结点，a的左子树的高度为Hl, 右左子树的高度为Hr，则节点a的平衡因子BF(a)定义为： BF(a) = Hl - Hr AVL树的定义： 若二叉查找树T非空，则它为AVL树的充要条件为： T中任意节点a的平衡因子满足|BF(a)|<=1。 （2）平衡二叉树示例： 输入顺序为 {25,28,30,67,86,95}时构造的平衡二叉树：

3.8.5 B-树和B+树 B树是R.Bayer和E.Mccreight于1970年提出的。实质上它是一种多叉查找树（检索树），在系统的运行过程中，随着数据的插入和删除，通过调整来保持树的平衡。 1． B-树 B-树是一棵平衡多路查找树，一棵m阶B-树或者为空树，或为满足下列特性的m叉树： （1）树中每个结点至多有m棵子树； （2）根节点或为叶子结点（树只包含一个根结点），否则根结点至少有两颗子树； （3）除根结点以外的所有非叶结点至少有m/2棵子树； （4）所有的非叶结点包含如下信息：（n,P0,K1, P1, K2,P2,…, Kn Pn） （5）所有叶子结点均出现在同一层次上，且不带信息（标志查找失败结点，指向这些结点的指针为空，即叶子结点实际上并不存在）。 B-树举例

3.8.5 B-树和B+树 2. B+树 B+树是应用非常广泛的B-树的一种变形。它特别适合于大型文件的索引组织，即使文件中的记录数目非常大，B+树索引的层数也非常低。 一棵m阶B+树和m阶B-树的不同在于： （1）有n个关键字的节点中有n棵子树（B-树中有n+1颗子树）； （2）所有的叶子结点中包含了全部关键字的信息，即指向这些关键字记录的指针，叶子结点本身按照关键字由小到大顺序连接； （3）所有的非叶子结点为索引部分，结点只含有其子树结点的最大（或最小）关键字值。 B+树举例

3.9 排序 本节内容： 3.9.2 插入排序 3.9.3 交换排序 3.9.4 选择排序 3.9.5 归并排序 3.9.6 基数排序 3.9 排序 查找和排序是计算机数据处理中的两类重要操作，从上节我们已经看到对于有序数据表，可以采用效率较高的折半查找，而如果数据表没有顺序，只能使用顺序查找，效率较低。下面我们介绍数据的排序问题及其算法。 本节内容： 3.9.1 基本概念 3.9.2 插入排序 3.9.3 交换排序 3.9.4 选择排序 3.9.5 归并排序 3.9.6 基数排序

3.9.1基本概念 所谓排序（Sorting），就是把任意文件（或表）按照指定的关键字排列成一个有序文件（或表）的过程，有时又称作“分类”。下面是排序问题的形式描述： 　　 　 假如给定一个记录序列（或表）F={R1, R2,…, Rn}，其中Ri（i=1,2,…,n）为序列中的第i个记录，关键字为Ki。所谓排序就是对记录序列中的记录重新排序成一个新的序列F‘ = {R1’ ,R2‘,…, Rn’}，使得它们的关键字值满足非减（或非增）的顺序。即对任意的i<j（i,j=1,2,…,n），有Ki‘Kj’（或Ki‘Kj’）。 如果序列中有两个或多个关键字相同的记录，排序的次序将是不惟一的。因此，我们规定：如果排序结果满足：当初始时序列中Ki=Kj，且i<j时，排序后记录Ri仍然在记录Rj前，这样的排序称为稳定排序。 内部排序是指被排序的记录较少，在整个排序过程中，所有的记录和中间结果都放在内存中。 外部排序是指当被排序的记录数量较大时，记录不能一次全部放在内存中，在整个排序过程中，必须对记录在内存和外存之间来回传递和交换。 内部排序的方法很多，每种方法都有各自的优缺点，性能的好坏与记录序列的初始状态有关。按照功能效率来分，排序可分为（1）简单排序，时间复杂度为O(n2)； （2）高效排序，时间复杂度为O(nlogn)； （3）基数排序，时间复杂度为O(d·n)。 按照排序过程所依据的原则不同，排序可以分为五类： （1）插入排序（2）交换排序（3）选择排序（4）归并排序（5）基数排序。 无论什么样的排序方法，排序算法的基本操作都是“比较”和“移动”（包括记录“交换”操作），因此，比较和移动记录次数的多少是衡量一个排序算法好坏的基本标准。

3.9.1 基本概念 排序的记录序列结构定义： #define MAXSIZE 20 // 用于排序算法说明的记录个数 typedef int KeyType; // 关键字类型，假设为int typedef struct r{ KeyType key; //记录的关键字项 // 记录的其他信息，按照实际需要定义 } RecType; typedef struct s{ RecType elements[MAXSIZE+1]； int length; // 元素序列的实际长度 } SeqList;

3.9.2 插入排序 int InsertSort(SeqList *F) // 对顺序表F作直接插入排序 所谓插入排序，是指将一个记录插入到一个已经排序好的有序序列中，从而得到一个新的、记录个数加1的有序序列。 对于n个记录的序列进行排序，插入排序的基本思想是： (1) 初始序列为{R1}，只有一个元素的序列一定是有序的。 (2) 依次将R2，R3，…，Rn插入到上次的有序序列中，分别得到长度为2,3,..,n的有序序列，从而实现长度为n的记录序列的排序。 直接插入排序算法： int InsertSort(SeqList *F) // 对顺序表F作直接插入排序 { int i； for (i=2; i<= F->length; i++) InsertR(F,i-1,F->elements[i])； } int InsertR(SeqList *F, int i, KeyType R) // 将记录R插入到长度为i的有序表中，得到长度为i+1的有序表 { int j; j = i; F->elements[0] = R；// 设置“哨兵” While (R<F->elements[j]) { F->elements[j+1] = F->elements[j]; j--; } F->elements[j+1] = R; } // Insert

3.9.3 交换排序 交换类排序两两元素进行比较，如果发生逆序，即Ri>Rj（i<j），则将两个元素交换，最后的到一个非递减的序列（正序）。常见的交换分类有标准交换、成对交换和穿梭交换三种，比较著名的交换类排序包括冒泡排序和快速排序。 1. 冒泡排序 冒泡排序（Bubbles Sort）属于标准的交换分类，基本思想是： 第1遍：首先将Rn和Rn-1进行比较，若发生逆序，则交换；否则，比较Rn-1和Rn-2，直到R2和R1比较。这样，第一遍结束后，将把关键值最小的元素移到了第一个单元。最小的元素就像“气泡”一样冒到了顶上，共比较n-1次。 第2遍：和第1遍一样，依次将Rn和Rn-1进行比较、Rn-1和Rn-2，直到R3和R2比较。这样，第2遍结束后，将把关键值次小的元素移到了第2个单元。共比较n-2次。 继续上述过程，逐遍进行，在进行i遍时，在前i-1遍得到的结果中，Rn,Rn-1,Rn-2,…,Ri+1和Ri依次两两比较，如发生逆序，则交换位置。 冒泡排序算法描述： int BubbleSort(SeqList *F) // 对表F进行冒泡排序 { int i，J, flag； for (i=1; i<F-> length; i++) { flag = True; for (j=F-> length; j>i; j--) { if (F->elements[j].key< F->elements[j-1].key) { temp = F->elements[j-1].key; F->elements[j-1].key = F->elements[j].key; F->elements[j].key = temp; } if flag break; } } }

3.9.3 交换排序 2 快速排序 快速排序（Quick Sort）方法是由Hoare于1962年提出的，后来又有许多人提出了修正方案，这类方法统称为快速排序（分类）。快速排序是最好的排序方法，其基本思想是： 按照一定原则选择某个元素作为控制记录（轴元素），首先把控制元素移动到其正确的位置，使得元素序列中所有比它小的元素都在它的前面，所有比它大的元素都在它的后面。这样，控制元素把整个元素序列分成了两部分（子序列），左边的部分都比它小，右边的部分都比它大。然后，按照同样的原则处理左右两个子序列，控制记录不再移动位置。 快速排序基本步骤： （1）选取中心记录作为控制记录，如序列中第一个记录的序号为l,最后一个记录的序号为u，则选取第m=(l+u)/2个记录作为控制记录。 （2）从第一个记录开始自左向右搜索比控制记录大的记录（用指针i标出）；从最后一个记录开始自右向左搜索比控制记录小的记录（用指针j标出）；若i<j，交换Ri和Rj。继续搜索，直到j<i为止。 （3）j<i，停止搜索。此时，如果jm，则控制记录Rm和Rj交换位置（即j所标记位置位轴元素的正确位置）；否则，即j<m，则Rm和Ri交换位置（即i所标记位置位轴元素的正确位置）。这样，Rm被放到了其正确的位置。 （4）Rm把原序列分成左右两个子序列，对两个子序列，再按照上述过程处理，直到被分成的子序列的长度都为1，整个排序过程结束。

3.9.3 交换排序 快速排序算法描述： int QuickSort(SeqList *F，int l，int u) // 对表F进行快速排序,l,u分别为被排序子表的第一个和最后一个记录的序号 { int i，j，m； if (l>=u) return 1; // 长度为1结束 i= l; j = u; m = l；//用表的第一个元素作为轴元素 do { pivotkey = F->elements[m].key; while (F->elements[i].key < pivotkey && i<=j) i++; while (F->elements[j].key > pivotkey && j>=i) j--; if (i<j) RiRj ; // Ri和Rj交换 else Break; } while True; if (j>=m) { Rm  Rj ; // Rm和Rj交换 m=j;} // 位置j为轴元素的正确位置 else { Rm  Ri ; // Rm和Ri交换 m=i; }// 位置i为轴元素的正确位置 QuickSort(F,l,m-1); // j为轴元素被放置的正确位置，将表分成子表 QuickSort(F,m+1,u); // （Rl,…,Rj-1）和子表（Rj+1,…,Ru）两个部分 }

3.9.4 选择排序 选择分类（Selection Sort）是一种最简单、平均性能最低的排序方法。 其基本思想是：从被排序的文件（或表）中依次选出关键字最小、次小、…的记录，从而实现排序。选择分类包括简单选择排序、树形选择排序（锦标赛排序）和堆排序（Heap Sort）等。 简单选择排序的步骤： （1）从1..n个记录中选出关键字最小的记录，和R1交换，最小的记录放到第1个单元。 （2）从2..n个记录中选出关键字最小的记录，和R2交换，次小的记录放到第2个单元。 依次进行，共需要n-1遍，最大的记录留在第n个单元，完成排序操作。 简单选择排序算法描述： int SimpleSelectionSort(SeqList *F) //对表F进行简单选择排序 {int i，j； for (i=1;i<F->length;i++) { j = SelectionMin(F,I, F->length); // 从i..n个元素中 //选择最小的元素，序号为j if (i!=j) F->lelments[i]F->elements[j]; }

3.9.5 归并排序 把两个或多个有序文件（或表）合并成一个有序文件（或表）的过程称归并（Merge）。当归并文件（或表）有两个时，称2路归并，三个时称3路归并，…，一般地，当归并文件有k个时，称为k路归并。 重复利用归并思想对任意文件（或表）进行排序的过程即归并排序（Merge Sort）。这里我们只讨论二路归并，多路归并的思想和二路归并相同。 二路归并的基本步骤： （1）将文件（或表）F={R1, R2,…, Rn}中的每一个记录看作一个文件（或表），他们都是有序的 （仅含一个记录）。 （2）把子文件（或子表）按照相邻的位置分成若干对（如果文件或子表个数时奇数，最后一个 单独一组）。 （3）对每对中的子文件（或子表）进行二路归并。归并后，每个子文件都是有序的，且子文件 的个数减少一半。 （4）重复步骤（2）--（4）,直到归并成一个有序文件为止。 二路归并示例

int Merge2(SeqList *A, SeqList *B, SeqList *C) 3.9.5 归并排序 二路归并排序算法描述： int Merge2(SeqList *A, SeqList *B, SeqList *C) // A、B为两个有序序列，长度分别为m和n，将他们合并成一个长度为m+n的有序序列C { int m，n，i，j，k； m = A->Length; n = B->Length; i=1; j=1; k=1; while (i<=m && j<=n) { if (A->elements[i].key<B->elements[j].key) C->elements[k].key = A->elements[i++].key; else C->elements[k].key = B->elements[j++].key; k++; } if (i<=m) // 将A中剩余的记录写到C中 while (i <= m) C->elements[k++].key = A->elements[i++].key; if (j<=n) // 将B中剩余的记录写到C中 while (j<= n) C->elements[k++].key = B->elements[j++].key; }

3.9.6 基数排序 基数排序（Radix Sorting）是和上面的四类排序完全不同的排序方法。在上述的排序中，是通过关键字值的比较和记录的移动来实现排序的，而基数排序不需要进行关键字间的比较。基数排序是一种借助于多关键字排序的思想实现的对单个逻辑关键字进行排序的方法。 用十进制基数分类说明多关键字排序的思想： 假定被分类的关键字值是十进制整数，将每位数字视为一个关键字，个位为最低关键字，十位为此低关键字，以此类推。按照LSD法进行十进位基数分类的过程是：把输出区分成10个桶（0桶，1桶，…，9桶），整个分类过程分成D遍（D位被分类数字的最多位数）。 第一遍：首先对最低关键字（个位）、进行桶分类，对序列中的每一个数由前向后将最低位数字相同的数字依次放在对应的上述10个桶中（如个位为6的放在6桶中），直到所有数字都分完。 第二遍：把上一遍各桶内的数字，按照从0桶,1桶，…，9桶的编号次序，同一桶内按由上倒下的次序收集起来，作为第二遍的输入。然后，再按次关键字（十位）的状态把各个数分别放入0,1,2,…,9对应的桶内，然后再把各个桶内的数字收集起来作为第三遍的输入。 继续上述过程，直到按照最高关键字的状态把所有数再分到队应得桶内。最后，按照0桶，1桶，2桶，…，9桶的顺序把各桶内的数据收集起来（同一桶内按由上倒下的次序收集）就得到所要的结果。

设要分类的记录的关键字值为{26，56，11，68，80，34，75，52，86}。 采用基数分类方法，分类过程如下： 3.9.6 基数排序 基数排序举例: 设要分类的记录的关键字值为{26，56，11，68，80，34，75，52，86}。 采用基数分类方法，分类过程如下： （1）按照最低位（个位）进行桶分类，结果如下: (2)再按照次低位（十位）进行桶分类，结果如下： (3)按照0桶，…，9桶的顺序把各桶内的数据收集起来即位最后的排序结果： 11，26，34，52，56，68，80，86

本节内容： 3.10 文件 3.10.1 文件的类别 3.10.2 文件的物理结构 3.10.3 文件的操作 3.10 文件 计算机处理的对象为数据，随着计算机的应用范围越来越广泛，数据之间 的关系也越来越复杂，数据量越来越大。计算机处理的初始数据、中间数据和 处理结果，甚至程序本身，都要按照一定的规则和组织方式存储在某种存储介 质上，这些被存储的信息称为文件（File）。简单地说，文件是储存在外存储 器（二级存储器）上信息的集合。 文件和表类似，都是由一系列记录构成。习惯上称存储在内存中（主存储 器）的记录的集合为表，储存在外存储器（二级存储器）上记录的集合为文件。 本节内容： 3.10.1 文件的类别 3.10.2 文件的物理结构 3.10.3 文件的操作

3.10.1 文件的类别 按照记录有无结构: 文件可分成1)操作系统文件 2)数据库文件。 根据文件的应用特性: 文件分成 1)命令文件 文件是有大量性质相同的记录构成的集合。 按照记录有无结构: 文件可分成1)操作系统文件 2)数据库文件。 根据文件的应用特性: 文件分成 1)命令文件 2)数据文件。 根据记录的组织和存储结构: 文件又可以分成 1)顺序文件 2)索引文件 3)散列文件（Hash文件）

3.10.2 文件的物理结构 文件在物理存储介质上的组织方式称为文件的物理存储结构。 基本组织方式有三种：顺序组织、链式组织和随机组织。 一个特定文件的具体组织形式由具体的应用系统来决定，应该综合考虑相关的因素，如存储介质的类型（顺序存储介质，如磁带，直接存储介质，如磁盘等）、记录的类型、关键字以及未来对文件的常用操作等。 文件在物理存储介质上的组织方式称为文件的物理存储结构。基本组织方式有三种：顺序组织、链式组织和随机组织。一个特定文件的具体组织形式由具体的应用系统来决定，应该综合考虑相关的因素，如存储介质的类型（顺序存储介质，如磁带，直接存储介质，如磁盘等）、记录的类型、关键字以及未来对文件的常用操作等。 1）顺序文件 顺序文件（Sequential File）记录按其在文件中的逻辑顺序依次存储在物理介质中，在顺序文件中，记录的物理顺序和逻辑顺序一致。 顺序文件的特点是： （1）记录的读取必须顺序进行，即要读取第i个记录，必须先读取第i-1个记录。 （2）文件的插入操作只能在文件的结尾处进行，即只能添加记录。 （3）若要更新某条记录必须复制整个文件。 2） 索引文件 当文件中的记录数量较大时，为了提高文件的检索效率，对文件建立一张指示逻辑记录和物理记录一一对应关系的索引表，文件记录本身称为数据区。这类包含文件数据区和索引表的文件称为索引文件。 索引表是在文件上建立的索引结构，在索引表中的每一项称为索引项，每一个索引项都包括两个基本的部分：记录关键字值和对应记录在数据文件中的物理记录号。不论数据文件是否有序，索引表总是按照关键字值有序排列的，从而保证查找的高效率。

3.10.2 文件的物理结构 3）接存取文件（散列文件） 直接存取文件是利用杂凑（Hash）技术进行组织的文件，又称散列文件。他类似于哈希表，散列文件通过散列结构对数据文件进行组织，通过构造一个散列函数H(x)，对数据文件中的任意数据记录，以其主关键字值X作为自变量，求函数值H(x)，在将H(x)转换成存储地址，从而直接访问相应的纪录。使用散列结构，需要解决两个问题，一个为找一个好的散列函数H(x)，尽量减少冲突；其次，确定一个好的解决冲突的办法。 4） 多关键字索引和倒排文件 多关键字文件的特点是，在对文件进行检索时，除了可以按照主关键字进行检索外，还经常按次关键字进行检索。如果文件中只有主关键字索引，则查询只能顺序进行，效率很低。为此，可以建立多个次关键字索引，此关键字索引表项应该包含次关键字值、具有同一次关键字值的多个记录的主关键字值或物理记录号等。 多关键字索引有多重表文件和到排文件。对于多重表文件，记录按主关键字的顺序构成一个串联文件，并建立主关键字的索引（称为主索引）；对每一个次关键字建立一个次关键字索引，所有具有同一次关键字的记录构成一个链表。 到排文件和多重文件类似，区别在于次关键字索引的结构不同，具有相同次关键字的记录之间不设指针连接。在次关键字索引表（称为倒排表）中，在该关键字的项中，存放这些记录的物理记录号。倒排表的好处在于检索速度快，它不用和多关键字索引一样读取记录来获取下一个具有相同次关键字的记录。

3.10.3 文件的操作 对文件的常用操作： 1）插入：向文件中增加一条新的纪录。 2）删除：从文件中删除一条指定的纪录。 3）修改：在文件中修改特定的纪录。 4）检索：在文件中检索满足特定条件的纪录，又称查找。 5）排序：对文件记录按照一定的关键字重新排列文件或建立索引文件，从而提高检索效率。

Thanks!