算法与数据结构C语言描述(第2版)电子教案 第1章 绪论课件

算法与数据结构

——C语言描述（第二版）

张乃孝高等教育出版社2006年1月算法与数据结构

——C语言描述（第二版）

张乃孝高等教育1“算法＋数据结构＝程序”程序就是在数据的某些特定的结构和表示的基础上对于算法的描述。算法与数据结构是程序设计中相辅相成、不可分割的两个方面。“算法＋数据结构＝程序”程序就是在数据的某些特定的结构和表示2抽象数据类型有一定行为（操作）的抽象（数学）类型。抽象出数据类型的使用要求，而把它的具体表示方式和运算的实现细节都隐藏起来。支持数据类型的实现与使用分离的原则，是一种十分有效的对问题进行抽象与分解的思维工具。是面向对象技术与方法的主要理论基础。抽象数据类型有一定行为（操作）的抽象（数学）类型。3数据结构“数据结构是抽象数据类型的物理实现”。解决：1）如何具体表示抽象数据类型中的数学模型；2）如何具体实现抽象数据类型中操作。数据结构“数据结构是抽象数据类型的物理实现”。4学习目的理解数据结构和算法的概念；掌握设计数据结构与算法的主要原理和方法；比较不同数据结构和算法的特点。提高学生使用计算机解决问题的能力。

学习目的理解数据结构和算法的概念；5

第一章绪论

本章重点：理解从问题到程序的主要过程；体会抽象数据类型、数据结构和算法在问题求解过程中的作用；了解数据结构的主要概念和分类；了解算法的概念和主要设计、分析方法。

第一章绪论

本章重点：61.1从问题到程序

用计算机解决（一种）实际问题，就是在计算机中建立一个解决问题的模型。程序是使用程序设计语言精确描述的实现模型，它是问题求解的一个可以在计算机上运行的模型。程序中描述的数据用来表示问题中涉及的对象，程序中描述的过程表示了对于数据的处理算法；通过接受（具体）实际问题的输入，经过程序的运行，便可以得到实际问题的一个解。

1.1从问题到程序

用计算机解决（一种）实际问题，就是在计7问题求解（1）分析阶段。

弄清用户的需求是什么，设计者根据它进行深入分析，使用规范说明语言（或数学语言等工具）给出系统的需求模型（或数学模型）。

问题求解（1）分析阶段。8问题求解（2）设计阶段（本课讨论的重点）

。建立求解系统的实现模型，重点是算法的设计和数据结构的设计。对于大型的复杂的系统，还包括抽象数据类型或者模块的设计。一般而言，设计过程需要从粗到细，经过多次精化才能完成。

问题求解（2）设计阶段（本课讨论的重点）。9问题求解（3）编码阶段。

根据设计的要求，采用适当的程序设计语言（C语言、C++语言或Java语言），编写出可执行的程序。

问题求解（3）编码阶段。10问题求解（4）测试和维护。发现和排除在前几个阶段中产生的错误，经测试通过的程序便可投入运行，在运行过程中还可能发现隐含的错误和问题，因此还必须在使用中不断维护和完善。

问题求解（4）测试和维护。111.1.1问题分析与抽象

为了能正确地解决问题，必须首先深刻地理解需要解决的问题。只有在深刻地认识了这个问题以后，才能着手确定这个问题的解决方法。

1.1.1问题分析与抽象

为了能正确地解决问题，必须首先12信号灯问题：为这个路口设计一个安全有效的交通信号灯的管理系统。

信号灯问题：为这个路口设计一个安全有效的交通信号灯的管理系统13信号灯问题－分析

分析所有车辆的行驶路线的冲突问题。这个问题可以归结为对车辆的可能行驶方向作某种分组，对分组的要求：使任一个组中各个方向行驶的车辆可以同时安全行驶而不发生碰撞。信号灯问题－分析分析所有车辆的行驶路线的冲突问题。14信号灯问题－分析可以确定13个可能通行方向：A→B，A→C，A→D，B→A，B→C，B→D，D→A，D→B，D→C，E→A，E→B，E→C，E→D。信号灯问题－分析15

交叉路口行驶冲突的抽象（不能同时行驶的用线连接）交叉路口行驶冲突的抽象（不能同时行驶的用线连接）16信号灯问题－抽象要求将图1.2中的结点分组，使有线相连(互相冲突)的结点不在同一个组里。

这个问题的解有许多“可行解”。我们希望能够设计一个最佳（分组数最少）的方案。称作“最优解”。

信号灯问题－抽象要求将图1.2中的结点分组，使有线相连(互17着色问题－经典问题把上图中的一个结点理解为一个国家，结点之间的连线看作两国有共同边界，上述问题就变成著名的“着色问题”：即求出（最少）要几种颜色可将图中所有国家着色，使得任意两个相邻的国家颜色都不相同。

着色问题－经典问题把上图中的一个结点理解为一个国家，结点之间181.1.2程序的设计与实现

一个问题的解决可以有许多办法，由于使用的工具是计算机，所以在选择方法时必须充分考虑到计算机的特点和条件，才能找到比较巧妙的办法，比较快而且准确地计算出需要的结果。1.1.2程序的设计与实现

一个问题的解决可以有许多办法19选择算法－穷举法具体做法：从分为1、2、3…组开始考察，逐个列举出所有可能的着色方案，检查这样的分组方案是否满足要求。首先满足要求的分组，自然是问题的最优解。

选择算法－穷举法具体做法：从分为1、2、3…组开始考察，逐个20穷举法的分析这类穷举法对结点少的问题(称为“规模小的”问题)还可以用；对规模大的问题，由于求解时间会随着实际问题规模的增长而指数性上升，使计算机无法承受。

穷举法的分析这类穷举法对结点少的问题(称为“规模小的”问题)21贪心法先用一种颜色给尽可能多的结点上色；然后用另一种颜色在未着色结点中给尽可能多的结点上色；如此反复直到所有结点都着色为止。

贪心法先用一种颜色给尽可能多的结点上色；然后用另一种颜色在未22贪心法的一个解(1)红色：ABACADBADCED

(2)蓝色：BCBDEA

(3)绿色：DADB

(4)白色：EBEC

贪心法的一个解(1)红色：ABACADBADCE23抽象数据类型的选择为了便于给出上述算法的实现，可以按照抽象数据类型的观点，先把被处理的对象加以抽象。在着色问题中具体解决：使用什么抽象数据类型来表示地图，以及使用什么样的抽象数据类型表示一组国家等。

抽象数据类型的选择为了便于给出上述算法的实现，可以按照抽象数24抽象数据类型的选择使用一个图（图是图论研究的对象，也是一种重要的抽象数据类型。）表示地图。使用国名（图中结点名）的集合表示国家的分组。

抽象数据类型的选择使用一个图（图是图论研究的对象，也是一种重25假设需要着色的图是G，G中所有结点的集合记为G.V，集合V1存放图中所有未被着色的结点，集合NEW存放可以用某颜色着色的所有结点。假设需要着色的图是G，26贪心法的描述

从V1中找出可用新颜色着色的结点集的工作可以用下面的伪码描述：

置NEW为空集合;

for每个vV1do

ifv与NEW中所有结点间都没有边

从V1中去掉v;将v加入NEW;这个伪码如果能执行，集合NEW中就得到一组可以用新颜色着色的结点。着色程序可以反复调用这段伪码，直到V1为空，每次调用选择一种新颜色，这段伪码执行的次数就是需要的不同颜色个数。

贪心法的描述

从V1中找出可用新颜色着色的结点集的工作可以用27假设（ADT）集合和图支持下面行为：判断元素v是否属于集合V1表示为vV1；从集合V1中去掉一个元素v表示为remove(V1,v)；向集合NEW里增加一个元素v用add(NEW,v)表示，判断集合V1是否空集合表示为isEmpty(V1)

检查结点v与结点集合NEW中各结点之间在图G中是否有边连接，用函数notAdjacentWith(NEW,v,G)表示。

假设（ADT）集合和图支持下面行为：判断元素v是否属于集合V28抽象的着色算法intcolorUp(GraphG){ intcolor=0;//记录使用的颜色数 setV1=G.V;//V1初始化为图G的结点集V setNEW; while(!isEmpty(V1)) { NEW={}; while(vV1.notAdjacentWith(NEW,v,G)) { add(NEW,v);remove(V1,v); } ++color; } returncolor;//返回使用的颜色数}抽象的着色算法intcolorUp(GraphG)29数据结构的设计如果集合和图是程序设计语言中预定义的类型，则colorUp中用到的remove(V1,v)和add(NEW,v)等就应该是语言中预定义的内部函数，该程序就几乎可以直接上机运行。否则程序员需要自己用语言所提供的（类型）机制实现这些抽象数据类型（集合、图等），这些正是数据结构设计要讨论的内容。数据结构的设计如果集合和图是程序设计语言中预定义的类型，则c30算法的精化在数据结构确定以后，算法的描述可以进一步根据设计的数据结构进行精化。如果这个问题仍然是个比较复杂的问题，就还需要选择算法，也可能存在需要新抽象数据类型和数据结构。经过这种反复的精化过程，最后将算法中所有部分都细化为能用程序设计语言描述的成分，得到的就是我们希望的程序。算法的精化在数据结构确定以后，算法的描述可以进一步根据设计的311.2抽象数据类型

抽象数据类型的概念最早出现在20世纪70年代，它是面向对象方法的重要理论基础。本书在内容的组织中仅仅使用了抽象数据类型的概念，而没有严格采用面向对象的程序设计语言的描述机制（例如class）。1.2抽象数据类型

抽象数据类型的概念最早出现在20世纪732基本概念－类型类型（type）是一组值（或者对象）的集合。例如：布尔作为一种类型是由真（true）和假（false）两个值组成的集合；布尔向量也可以作为一种类型，它的每个值是一个由true或false构成的向量。基本概念－类型类型（type）是一组值（或者对象）的集合。33基本概念－数据类型数据类型（datatype）通常是指在计算机（语言）中可以使用的一个类型，它不但包括这个类型的值的集合，还包括定义在这个类型上的一组操作。例如：整数作为一个数据类型是指在计算机上所能表示的（不是数学意义上任意大小的）所有整数和语言中定义的对于这些整数的全部操作（整数的加、减、乘、除、取余等）。基本概念－数据类型数据类型（datatype）通常是指在计34基本概念－抽象数据类型抽象数据类型（AbstractDataType简称为ADT）可以定义作具有一定行为(操作)的抽象（数学）类型。它不关心类型中值的具体表示方式和数据类型中定义的各种操作的具体实现方法，是所有可能的值的具体表示和各种操作的具体实现的抽象。基本概念－抽象数据类型抽象数据类型（AbstractDat35意义和作用（1）抽象数据类型的实质是抽象出了数据类型的使用要求，而把它的具体表示方式和运算的实现细节都隐藏起来。抽象数据类型仅仅规定了数据类型应该具有的行为（操作）。一旦抽象数据类型被正确实现，就好像程序设计语言中所提供的数据类型那样，可以被自由使用。意义和作用（1）抽象数据类型的实质是抽象出了数据类型的使用要36意义和作用（2）抽象数据类型支持数据类型的实现与使用分离的原则，允许独立地考虑数据类型的外部接口和内部的实现。这使应用程序只要按抽象数据类型的接口统一其使用界面；可以不管其是否已经实现，也不管它是如何实现的。对于系统的分解、设计、维护和修改均十分有利。

意义和作用（2）37

例1－抽象数据类型圆

ADTCircleis

operations area 计算圆的面积 circumference 计算圆的周长 getRadius 获取圆的半径 setRadius 设置圆的半径endADTCircle

例1－抽象数据类型圆 ADTCirclei38例2－集合抽象数据类型ADTSetis

Operations isEmpty 判断集合是否是空集合 add 给集合增加一个元素 remove 删除集合中的一个元素 isIn 判断一个元素是否在当前集合中end

ADTSet例2－集合抽象数据类型ADTSetis391.3数据结构关于数据结构的研究，可以追溯到1972年C.A.R.Hoare奠基性的论文《数据结构笔记》；而现代计算机所大量采用的基本数据结构，最早的系统论述应归功于1973年D.E.Knuth的名著《计算机程序设计技巧》的问世。为了学习和研究的方便，计算机科学家把常用的数据进行分类，总结出许多典型的数据结构。1.3数据结构关于数据结构的研究，可以追溯到1972年C.401.3.1什么是数据结构（通常）可以把数据结构理解为：计算机中表示（存储）的、具有一定（逻辑）关系和行为的一组数据。其中的每个数据(元素)称为这个结构的一个结点。（根据面向对象的观点）可以把数据结构理解成为抽象数据类型的物理实现。主要解决两个问题：如何具体表示抽象数据类型中的数学模型；如何给出抽象数据类型中需要操作的实现。1.3.1什么是数据结构（通常）可以把数据结构理解为：41数据结构三要素：逻辑结构:指数学模型中的基本元素（结点）和元素之间的相互关系。存储结构:指数学模型的具体表示方式，包括结点的表示和关系的表示。操作:指抽象数据类型关心的各种行为在存储结构上的具体实现（算法）。数据结构三要素：42例子－集合从集合抽象数据类型的定义出发，将讨论它的实现——集合数据结构：根据数学的概念，集合中的元素是各不相同而且无序的（逻辑结构）；将介绍使用顺序表、单链表、散列表等等许多不同的集合表示方法（存储结构）；并且在这些不同的表示基础上，给出各自的行为实现算法（操作）。

例子－集合从集合抽象数据类型的定义出发，将讨论它的实现——集431.3.2数据结构的分类主要根据逻辑结构和存储结构进行分类

1.3.2数据结构的分类主要根据逻辑结构44逻辑结构B=<K，R>K是结点的有穷集合，R是K上的一个关系。K上的一个关系就是K上的一些二元组组成的集合K上的二元组是K中元素的有序对.若k,k’K,<k,k’>R，则称k为k’的前驱，k’为k的后继。没有前驱的结点称为开始结点，没有后继的结点称为终端结点。

K上不同的二元组集合构成不同的关系。逻辑结构的概念逻辑结构B=<K，R>逻辑结构的概念45按逻辑结构分类

根据R的特点可以将数据结构分为以下三类：线性结构：K中每个结点最多只有一个前驱和一个后继的结构。树形结构：K中每个结点最多只有一个前驱，但可有多个后继的结构。复杂结构：K中结点的前驱、后继结点个数都不作限制的结构。*集合：它可以看成R为空的情况，即结点之间没有任何关系。

按逻辑结构分类根据R的特点可以将数据结构分为以下三类：46按逻辑结构分类举例

线性结构举例树形结构举例

复杂结构举例

按逻辑结构分类举例线性结构举例47存储结构的概念存储结构:数据的逻辑结构在计算机中的存储(表示)。通常包括结点的表示和关系的表示。同一种逻辑结构，可以采用不同的表示方式。例如，线性表既可以用顺序（一维数组）的方式来表示（顺序表），也可以用链接的方式（使用指针）来表示（单链表或双链表）。存储结构的设计目标，是使用比较少的空间记录逻辑结构的必要信息，还能够有效实现(抽象数据类型中)要求的操作。

存储结构的概念存储结构:数据的逻辑结构在计算机中的存储(表示48根据存储结构分类：顺序表示：用一个连续的空间，顺序存放数据结构中的各个结点。（结点的关系需要另外存储或者隐含其中）链接表示：结点的存放位置是任意的，结点之间的关系通过与结点关联的指针（或者引用）方式显式表达出来。

散列表示：又称为关键码——地址转换法。即选择适当的散列（杂凑）函数，根据关键码的值将结点映射到给定的存储空间（散列表）中。

索引表示：索引与散列一样，都给出一种从关键码到存储地址的映射方法。不同的是，散列法的映射是通过函数定义；而索引法是通过建立辅助的索引结构解决。根据存储结构分类：顺序表示：用一个连续的空间，顺序存放数据结491.3.3结点与结构在数据结构的讨论中重点研究的是“结构”，而把组成结构的那些元素抽象成一个“结点”。结点是数据结构中的基本单位，在实际应用中一个结点可以是一个字符、一个整数（初等类型），也可以是一个结构（组合类型）。1.3.3结点与结构在数据结构的讨论中重点研究的是“结构501.3.4外存数据的组织

简单介绍常用的外存设备及其特点，讨论文件的结构和处理。掌握这些知识，对于理解涉及到外存上的数据结构（例如B/B+树）与算法（例如归并排序）会有帮助.1.3.4外存数据的组织

简单介绍常用的外存设备及其特点51基本概念文件是逻辑记录的集合。逻辑记录（简称记录）是应用程序需要进行内外存交换的逻辑单位。每个记录可以包含若干数据项，其中能够唯一标识该记录的数据项称为关键码。对外存的数据必须按页块存取。页块又称物理记录，是内存与外存进行交换的物理单位。基本概念文件是逻辑记录的集合。52外存设备目前广泛使用的外存储器有磁带、磁盘、光盘和优盘等。其中以磁带和磁盘最具代表性。

外存设备目前广泛使用的外存储器有磁带、磁盘、光盘和优盘等。53磁带磁带上的信息以页块为单位顺序存放，页块与页块之间留有间隙，间隙上不存放数据，但有被硬件识别的带标。一个页块就是一个物理记录。要读写一个页块，首先要定位，即通过磁带的移动使磁头对准被读页块的前沿，然后才能读写。磁带存储器的读写速度与(磁带的存储密度和)走带速度有关，因为属于机械动作，比内存数据的读写时间长得多。在读写前需要定位，定位需要的时间与当前磁头位置与需要定位的位置之间的距离成正比，最坏情况可能需要花费若干分钟。磁带磁带上的信息以页块为单位顺序存放，页块与页块之间留有间隙54磁盘磁盘类似于多碟的CD，若干盘片（比如６片）串在一根主轴上形成一个盘组，当主轴旋转时带动各个盘片旋转。每个盘面上包含大小不同的许多同心圆。每个圆圈称为一个磁道，各个盘面的半径相同的磁道合在一起构成一个柱面。一个磁道又可分为若干段，每段是一个页块（物理记录）。一个盘组上从大到小的存储地址为：柱面、磁道和页块。在磁盘上读写信息:１．选定柱面，这是机械动作，所以比较慢。２．选定磁道，由电子线路实现，所以比较快。３．找物理记录，这是机械动作，较慢。实际读写信息的时间比定位时间少得多，目前访问磁盘中的数据比访问内存慢5－6个数量级。

磁盘磁盘类似于多碟的CD，若干盘片（比如６片）串在一根主轴55缓冲区与访外主机对外存储器上的数据不能直接按字(或者字节)存取。读外存上的数据:1,把外存上一个或者多个物理记录读到内存的指定的区域，这个区域叫作缓冲区。2,在缓冲区中找到需要的逻辑记录进行处理。写的过程则相反，先写到缓冲区中，然后通过主机与外存的接口，把缓冲区中的数据写到外存储器的物理记录中。这种读写过程，通常称为访外。缓冲区与访外主机对外存储器上的数据不能直接按字(或者字节)存56外存的存取外存储器上的逻辑记录的地址由两部分表示：逻辑记录所在物理记录的地址；逻辑记录在物理记录内的相对位置。节省外存的存取时间的关键在于减少访外的次数。由于缓冲区的大小受到内存容量的限制，所以减少访外次数的有效方法是精心设计文件的结构，使外存中存放的记录，相互关联，以便于处理。外存的存取外存储器上的逻辑记录的地址由两部分表示：57文件的分类

顺序文件.文件中的记录可以按某种顺序（例如按放入文件的先后或者按关键码的大小）定义次序，并且在外存储器上是按同样的次序存放的，则这种文件叫做顺序文件。

散列文件.

通过某种函数关系（称为散列函数）作用到记录的关键码上来确定记录的外存地址。索引文件.对于文件中的记录也可以建立索引。对于大型的文件，其索引往往也是很大的，需要存放在外存上。这样索引也是一种文件。本书把索引和主文件总称为索引文件。对于索引文件，其主文件如果是一个顺序文件，又可以叫作索引顺序文件。倒排文件.对于需要对属性建立的索引，称为倒排索引．带有倒排索引的文件称为倒排索引文件，简称倒排文件。

文件的分类顺序文件.文件中的记录可以按某种顺序（例如按放入58文件的处理

检索。在文件中查找满足一定条件的记录。最常见的是，查找关键码为一指定值的记录，此时，成功的检索只能找出唯一的记录。插入。在文件中增加一个新的记录。删除。删去文件中的一个记录。插入和删除操作常常需要通过检索，先找到被插入或删除记录的位置。修改。把记录中某些属性的值改为新值。若被修改的属性包括关键码，则相当于删除一个老记录并插入一个新记录。排序。按照关键码或者某属性的值，从小到大（或从大到小）的次序，把文件的全部记录重新进行排列。这种排序叫做外排序。文件的处理检索。在文件中查找满足一定条件的记录。最常见的是591.4算法本课是以数据结构为主线，算法为辅线组织内容。因为每种数据结构上的操作，都需要一定算法。对于不同存储结构的选择与评价，算法的好坏起着决定的因素。所有算法的实现也都需要数据结构的支持。算法与数据结构是程序设计的两大支柱。它们相辅相成，互相依赖。

1.4算法本课是以数据结构为主线，算法为辅线组织内容。60什么是算法算法是由有穷规则构成（为解决某一类问题）的运算序列。算法可以有若干输入(初始值或条件)；算法通常又有若干个输出(计算结果）。算法应该具有有穷性。一个算法必须在执行了有穷步之后结束。算法应该具有确定性。算法的每一步，必须有确切的定义。算法应该具有可行性。算法中的每个动作，原则上都是能够由机器或人准确完成的。什么是算法算法是由有穷规则构成（为解决某一类问题）的运算序列61算法的正确性如果一个算法以一组满足初始条件的输入开始，那么该算法的执行一定终止，并且在终止时得到满足要求的（输出）结果。算法的正确性62算法设计的方法贪心法分治法回溯法动态规划法分枝界限法算法设计的方法贪心法63贪心法基本思想是：当追求的目标是一个问题的最优解时，设法把对整个问题的求解工作分成若干步骤来完成。在其中的每一个阶段都选择从局部看是最优的方案，以期望通过各阶段的局部最优选择达到整体的最优。算法1.1解着色问题时就是采用的贪心法。贪心法实际上不能保证都成功地产生一个全局性最优解，但是通常可以得到一个可行的较优解。（举例）贪心法基本思想是：当追求的目标是一个问题的最优解时，设法把对64分治法基本思想是:把一个规模较大的问题分成两个或多个较小的与原问题相似的子问题。首先对子问题进行求解，然后设法把子问题的解合并起来，得出整个问题的解，即对问题分而治之。如果一个子问题的规模仍然比较大，不能很容易地求得解，就可以对这个子问题重复地应用分治策略。二分法检索就是用分治策略的典型例子。分治法基本思想是:把一个规模较大的问题分成两个或多个较小的与65回溯法基本思想是:有一些问题，需要通过彻底搜索所有可能情况寻找一个满足某些预定条件的最优解。由于彻底搜索的运算量通常非常大，所以采取一步一步向前试探，当有多种选择时可以任意选择一种，只要目前可行就继续向前，一旦发现问题或失败就后退，回到上一步重新选择，借助于回溯技巧和中间增加判断，这样常常可以大大地减少搜索时间。常见的迷宫问题以及八皇后问题都可以用回溯方法来解决。回溯法基本思想是:有一些问题，需要通过彻底搜索所有可能情况寻66动态规划法与分治法相似都是把一个大问题分解为若干较小的子问题，通过求解子问题而得到原问题的解。不同点是：分治法每次分解的子问题数目比较少，子问题之间界限清楚，处理的过程通常是自顶向下进行；动态规划法分解的子问题可能比较多，而且子问题相互包含，为了重用已经计算的结果，要把计算的中间结果全部保存起来，通常是自底向上进行。在带权图中，求所有结点之间最短路径的Floyd算法（见第9章）就属于动态规划法。动态规划法与分治法相似都是把一个大问题分解为若干较小的子问题67分枝界限法与回溯法相似，也是一种在表示问题解空间的树上进行系统搜索的方法。所不同的是，回溯法使用了深度优先策略，而分枝界限法一般采用广度优先策略或者采用最大收益（或最小损耗）策略，并且利用最优解属性的的上下界来控制搜索的分枝。

最后一章，在讨论背包问题时，介绍了一个用分枝界限法设计的算法。

分枝界限法与回溯法相似，也是一种在表示问题解空间的树上进行系681.4.3算法的精化实现一个算法，就是要把设计者头脑中的算法思想转化成计算机中可以执行的程序。对于一个比较复杂的算法，其实现的过程往往需要经过多次细化才能完成。习惯上，把这个过程称为算法的精化。1.4.3算法的精化实现一个算法，就是要把设计者头脑69排序问题假设有n≥1个不同的整数a0，a1，…，an-1，要求把这些整数从大到小进行排序。排序算法可以明确地用下面的输入和输出关系来描述其功能：输入：是含n个元素的整数数组，记为a，其中的元素依次为：a[0],a[1],…,a[n-1]。输出：是输入数组a中元素重新排列，记为a'，其中的元素依次为：a'[0],a'[1],…,a'[n-1]，满足a'[i]≥a'[i+1]，对所有的0≤i<n-1都成立排序问题假设有n≥1个不同的整数a0，a1，…，an-1，要70直接选择排序的思想1从a中选出一个最大的整数放到一个空的数组a'中，作为a'中的第一个元素。2从a中剩下的元素中再选出最大的整数放到a'中，接在前一个已放入元素的后面。反复执行步骤2，直到a中所有整数都放到排好序的数组a'中。直接选择排序的思想1从a中选出一个最大的整数放到一个空的71第一步精化:将排序后的数据仍然存储在排序前的数组里1从a[0]到a[n-1]中选出最大整数，设为a[j]，把a[0]与a[j]进行交换。2从a[1]到a[n-1]中选出最大整数，设为a[j]，把a[1]与a[j]进行交换。…………n从a[n-1]到a[n-1]中选出最大整数，设为a[j]，把a[n-1]与a[j]进行交换（因为j=n-1,故这步可省）。第一步精化:将排序后的数据仍然存储在排序前的数组里1从72第二步精化:把上面执行n次重复的工作，精化成一个循环。i以1为步长，从0到n-2，循环执行：(1)从a[i]到a[n-1]中选出最大的整数，设为a[j]。(2)把a[i]与a[j]进行交换。第二步精化:把上面执行n次重复的工作，精化成一个循环。i73第三步精化循环i以1为步长，从0到n-2，执行(1)j←i(2)循环k以1为步长，从i+1到n-1，执行：

若a[k]>a[j]，则j←k(3)t←a[i]；a[i]←a[j]；a[j]←t第三步精化74使用C语言的函数形式描述的算法voidsortIntArray(int[]a，intn){ inti,j,k,t; for(i=0;i<n-1;i=i+1){ j=i;/*把a[i]作为最大整数的初值*/ for(k=i+1;k<n-1;k=k+1)/*从a[i]到a[n-1]中选出最大整数*/ if(a[k]>a[j]) j=k; t=a[i];a[i]=a[j];a[j]=t; }}使用C语言的函数形式描述的算法voidsortIntAr751.4.4算法分析分析一个算法主要是看这个算法的执行需要花费多少机器资源。在进行算法分析时人们最关心的就是运行算法所要花费的时间和算法中使用的各种数据占有的空间。在文献中习惯称之为算法的时间代价和空间代价。1.4.4算法分析分析一个算法主要是看这个算法的执行需要花76基本概念算法的空间代价(或称空间复杂性)：当被解决问题的规模(以某种单位计算)由1增至n时，解该问题的算法所需占用的空间也以某种单位由f(1)增至f(n)，这时我们称该算法的空间代价是f(n)。算法的时间代价(或称时间复杂性)：当问题规模以某种单位由1增至n时，对应算法所耗费的时间也以某种单位由g(1)增至g(n)，这时我们称该算法的时间代价是g(n)。基本概念算法的空间代价(或称空间复杂性)：当被解决问题的规模77问题的规模、

空间单位和时间单位问题的规模一般可以根据问题本身的提法确定。例如对n个记录进行排序，这里n即可以作为问题的规模。空间单位和时间单位没有统一的规定，通常取算法描述中的初等数据占用的空间和基本操作耗费的时间为单位。在本书中，空间单位选择为一个简单变量(如整型或者实型等)所占存储空间的大小；时间单位则选择为执行一个简单语句(如赋值语句或者判断语句等)所用时间。选择排序的时间代价(n-1)+(n-2)+…+1=n

(n-1)/2问题的规模、

空间单位和时间单位问题的规模一般可以根据问题本78大O表示法在描述算法分析的结果时，人们通常采用大O表示法：说某个算法的时间代价(或者空间代价)为O(f(n))，如果存在正的常数c和n0，当问题的规模n≥n0后，该算法的时间(或空间)代价T(n)≤c·f(n)。这时也称该算法的时间(或空间)代价的增长率为f(n)。大O表示法79最坏情况下代价的数量级每个算法的实际运行时的代价并不是固定不变的。由于不同的输入参数，可能使一个算法的实际代价出现很大差别。要全面分析一个算法，应该考虑它在最坏情况下的代价、最好情况下的代价和平均情况下的代价等。本书不是专门讨论算法分析的教材，所以在分析算法时主要考虑它们在最坏情况下的代价，而且仅仅要求计算它们的数量级。最坏情况下代价的数量级每个算法的实际运行时的代价并不是固定不80大O表示法说某个算法的时间代价(或者空间代价)为O(f(n))，如果存在正的常数c和n0，当问题的规模n≥n0后，该算法的时间(或空间)代价T(n)≤c·f(n)。也称该算法的时间(或空间)代价的增长率为f(n)。例如，如果有T(n)=3n3，很容易证明T(n)=O(n3)。当然我们也可以证明T(n)=O(n4)。但从分析的精度来看，前一结论给出的是上确界(上界中最小的)，后者给出的仅是一般上界中的一个。大O表示法说某个算法的时间代价(或者空间代价)为O(f(n)81计算规则1)加法规则T(n)=T1(n)+T2(n)=O(f1(n))+O(f2(n))=O(max(f1(n),f2(n)))2)乘法规则T(n)=T1(n)×T2(n)=O(f1(n))×O(f2(n))=O(f1(n)×f2(n))

对于大O表示法，以非零正常数c形成的复杂性度量O(c)都居于同一个量级，人们习惯把它们统一记为O(1)。计算规则1)加法规则82c<log2n<n<nlog2n<n2<n3<10nc<log2n<n<nlog2n<n2<83例子1：考虑如下程序：{action1(….);action2(….);}其中action1的时间代价是T1(n)=O(n2)，action2的时间代价是T2(n)=O(n3)。按照加法规则，计算整个程序的时间代价为：T(n)=T1(n)+T2(n)=O(max(n2,n3))=O(n3)例子1：考虑如下程序：84例子2for(i=1;i<=n;i++)action3(…);/*假设action3(…)的执行中不改变i的值*/以操作action3的执行时间为单位，显然这里for循环的时间代价可以看作是T1(n)=O(n)；假设action3的时间代价是T2(n)=O(f(n))，根据乘法规则整个程序实际的时间复杂性应当是：T(n)=T1(n)×T2(n)=O(n)×O(f(n))=O(n×f(n))例子2for(i=1;i<=n;i++)85小结1－抽象数据类型

用计算机对于实际问题求解，就是在计算机中建立一个解决该问题的模型。程序是使用程序设计语言精确描述的实现模型。抽象数据类型是具有一定行为的抽象类型，它抽象掉了类型中值的具体表示方式和数据类型中定义的各种操作的实现方法。在问题求解、数据结构和算法的研究中，抽象数据类型的地位和作用越来越受到重视。小结1－抽象数据类型

用计算机对于实际问题求解，就是在计算机86小结2－数据结构数据结构是抽象数据类型的物理实现。数据结构主要应解决两个问题：一个是选择存储结构；另一个是实现抽象数据类型中的各种操作。抽象类型中元素间内在的相互依赖关系称为逻辑结构。逻辑结构和存储结构是研究数据结构的两个重要方面，也是划分不同数据结构的主要依据。线性结构、树形结构和复杂结构是三种主要的逻辑结构；顺序、链接、索引和散列是四种主要的存储结构。小结2－数据结构数据结构是抽象数据类型的物理实现。数据结构主87小结3－算法算法是由有穷规则构成的，为解决某一特定类型问题确定的运算序列。常见的算法根据其设计方法可以分为贪心法、分治法、回溯法、动态规划法和分枝界限法等。评价一个算法或程序的重要依据是它们运行时所要花费的时间代价和空间代价。实现一个算法，就是要把设计者头脑中的算法思想转化成计算机中可以执行的程序。对于一个比较复杂的算法，其实现的过程往往需要经过多次算法的精化才能完成。小结3－算法算法是由有穷规则构成的，为解决某一特定类型问题确88小结4－文件外存上的数据结构一般都组织成文件的形式，一个文件由若干记录组成。把数据从外存读到内存或从内存写到外存需要执行访外操作，由于每次访问外存可能要花费许多时间来定位，为了减少访外的次数，在内外存交换时，采用缓冲区和分块存取技术。小结4－文件外存上的数据结构一般都组织成文件的形式，一个文件89算法与数据结构

——C语言描述（第二版）

张乃孝高等教育出版社2006年1月算法与数据结构

——C语言描述（第二版）

张乃孝高等教育90“算法＋数据结构＝程序”程序就是在数据的某些特定的结构和表示的基础上对于算法的描述。算法与数据结构是程序设计中相辅相成、不可分割的两个方面。“算法＋数据结构＝程序”程序就是在数据的某些特定的结构和表示91抽象数据类型有一定行为（操作）的抽象（数学）类型。抽象出数据类型的使用要求，而把它的具体表示方式和运算的实现细节都隐藏起来。支持数据类型的实现与使用分离的原则，是一种十分有效的对问题进行抽象与分解的思维工具。是面向对象技术与方法的主要理论基础。抽象数据类型有一定行为（操作）的抽象（数学）类型。92数据结构“数据结构是抽象数据类型的物理实现”。解决：1）如何具体表示抽象数据类型中的数学模型；2）如何具体实现抽象数据类型中操作。数据结构“数据结构是抽象数据类型的物理实现”。93学习目的理解数据结构和算法的概念；掌握设计数据结构与算法的主要原理和方法；比较不同数据结构和算法的特点。提高学生使用计算机解决问题的能力。

学习目的理解数据结构和算法的概念；94

第一章绪论

本章重点：理解从问题到程序的主要过程；体会抽象数据类型、数据结构和算法在问题求解过程中的作用；了解数据结构的主要概念和分类；了解算法的概念和主要设计、分析方法。

第一章绪论

本章重点：951.1从问题到程序

用计算机解决（一种）实际问题，就是在计算机中建立一个解决问题的模型。程序是使用程序设计语言精确描述的实现模型，它是问题求解的一个可以在计算机上运行的模型。程序中描述的数据用来表示问题中涉及的对象，程序中描述的过程表示了对于数据的处理算法；通过接受（具体）实际问题的输入，经过程序的运行，便可以得到实际问题的一个解。

1.1从问题到程序

用计算机解决（一种）实际问题，就是在计96问题求解（1）分析阶段。

弄清用户的需求是什么，设计者根据它进行深入分析，使用规范说明语言（或数学语言等工具）给出系统的需求模型（或数学模型）。

问题求解（1）分析阶段。97问题求解（2）设计阶段（本课讨论的重点）

。建立求解系统的实现模型，重点是算法的设计和数据结构的设计。对于大型的复杂的系统，还包括抽象数据类型或者模块的设计。一般而言，设计过程需要从粗到细，经过多次精化才能完成。

问题求解（2）设计阶段（本课讨论的重点）。98问题求解（3）编码阶段。

根据设计的要求，采用适当的程序设计语言（C语言、C++语言或Java语言），编写出可执行的程序。

问题求解（3）编码阶段。99问题求解（4）测试和维护。发现和排除在前几个阶段中产生的错误，经测试通过的程序便可投入运行，在运行过程中还可能发现隐含的错误和问题，因此还必须在使用中不断维护和完善。

问题求解（4）测试和维护。1001.1.1问题分析与抽象

为了能正确地解决问题，必须首先深刻地理解需要解决的问题。只有在深刻地认识了这个问题以后，才能着手确定这个问题的解决方法。

1.1.1问题分析与抽象

为了能正确地解决问题，必须首先101信号灯问题：为这个路口设计一个安全有效的交通信号灯的管理系统。

信号灯问题：为这个路口设计一个安全有效的交通信号灯的管理系统102信号灯问题－分析

分析所有车辆的行驶路线的冲突问题。这个问题可以归结为对车辆的可能行驶方向作某种分组，对分组的要求：使任一个组中各个方向行驶的车辆可以同时安全行驶而不发生碰撞。信号灯问题－分析分析所有车辆的行驶路线的冲突问题。103信号灯问题－分析可以确定13个可能通行方向：A→B，A→C，A→D，B→A，B→C，B→D，D→A，D→B，D→C，E→A，E→B，E→C，E→D。信号灯问题－分析104

交叉路口行驶冲突的抽象（不能同时行驶的用线连接）交叉路口行驶冲突的抽象（不能同时行驶的用线连接）105信号灯问题－抽象要求将图1.2中的结点分组，使有线相连(互相冲突)的结点不在同一个组里。

这个问题的解有许多“可行解”。我们希望能够设计一个最佳（分组数最少）的方案。称作“最优解”。

信号灯问题－抽象要求将图1.2中的结点分组，使有线相连(互106着色问题－经典问题把上图中的一个结点理解为一个国家，结点之间的连线看作两国有共同边界，上述问题就变成著名的“着色问题”：即求出（最少）要几种颜色可将图中所有国家着色，使得任意两个相邻的国家颜色都不相同。

着色问题－经典问题把上图中的一个结点理解为一个国家，结点之间1071.1.2程序的设计与实现

一个问题的解决可以有许多办法，由于使用的工具是计算机，所以在选择方法时必须充分考虑到计算机的特点和条件，才能找到比较巧妙的办法，比较快而且准确地计算出需要的结果。1.1.2程序的设计与实现

一个问题的解决可以有许多办法108选择算法－穷举法具体做法：从分为1、2、3…组开始考察，逐个列举出所有可能的着色方案，检查这样的分组方案是否满足要求。首先满足要求的分组，自然是问题的最优解。

选择算法－穷举法具体做法：从分为1、2、3…组开始考察，逐个109穷举法的分析这类穷举法对结点少的问题(称为“规模小的”问题)还可以用；对规模大的问题，由于求解时间会随着实际问题规模的增长而指数性上升，使计算机无法承受。

穷举法的分析这类穷举法对结点少的问题(称为“规模小的”问题)110贪心法先用一种颜色给尽可能多的结点上色；然后用另一种颜色在未着色结点中给尽可能多的结点上色；如此反复直到所有结点都着色为止。

贪心法先用一种颜色给尽可能多的结点上色；然后用另一种颜色在未111贪心法的一个解(1)红色：ABACADBADCED

(2)蓝色：BCBDEA

(3)绿色：DADB

(4)白色：EBEC

贪心法的一个解(1)红色：ABACADBADCE112抽象数据类型的选择为了便于给出上述算法的实现，可以按照抽象数据类型的观点，先把被处理的对象加以抽象。在着色问题中具体解决：使用什么抽象数据类型来表示地图，以及使用什么样的抽象数据类型表示一组国家等。

抽象数据类型的选择为了便于给出上述算法的实现，可以按照抽象数113抽象数据类型的选择使用一个图（图是图论研究的对象，也是一种重要的抽象数据类型。）表示地图。使用国名（图中结点名）的集合表示国家的分组。

抽象数据类型的选择使用一个图（图是图论研究的对象，也是一种重114假设需要着色的图是G，G中所有结点的集合记为G.V，集合V1存放图中所有未被着色的结点，集合NEW存放可以用某颜色着色的所有结点。假设需要着色的图是G，115贪心法的描述

从V1中找出可用新颜色着色的结点集的工作可以用下面的伪码描述：

置NEW为空集合;

for每个vV1do

ifv与NEW中所有结点间都没有边

从V1中去掉v;将v加入NEW;这个伪码如果能执行，集合NEW中就得到一组可以用新颜色着色的结点。着色程序可以反复调用这段伪码，直到V1为空，每次调用选择一种新颜色，这段伪码执行的次数就是需要的不同颜色个数。

贪心法的描述

从V1中找出可用新颜色着色的结点集的工作可以用116假设（ADT）集合和图支持下面行为：判断元素v是否属于集合V1表示为vV1；从集合V1中去掉一个元素v表示为remove(V1,v)；向集合NEW里增加一个元素v用add(NEW,v)表示，判断集合V1是否空集合表示为isEmpty(V1)

检查结点v与结点集合NEW中各结点之间在图G中是否有边连接，用函数notAdjacentWith(NEW,v,G)表示。

假设（ADT）集合和图支持下面行为：判断元素v是否属于集合V117抽象的着色算法intcolorUp(GraphG){ intcolor=0;//记录使用的颜色数 setV1=G.V;//V1初始化为图G的结点集V setNEW; while(!isEmpty(V1)) { NEW={}; while(vV1.notAdjacentWith(NEW,v,G)) { add(NEW,v);remove(V1,v); } ++color; } returncolor;//返回使用的颜色数}抽象的着色算法intcolorUp(GraphG)118数据结构的设计如果集合和图是程序设计语言中预定义的类型，则colorUp中用到的remove(V1,v)和add(NEW,v)等就应该是语言中预定义的内部函数，该程序就几乎可以直接上机运行。否则程序员需要自己用语言所提供的（类型）机制实现这些抽象数据类型（集合、图等），这些正是数据结构设计要讨论的内容。数据结构的设计如果集合和图是程序设计语言中预定义的类型，则c119算法的精化在数据结构确定以后，算法的描述可以进一步根据设计的数据结构进行精化。如果这个问题仍然是个比较复杂的问题，就还需要选择算法，也可能存在需要新抽象数据类型和数据结构。经过这种反复的精化过程，最后将算法中所有部分都细化为能用程序设计语言描述的成分，得到的就是我们希望的程序。算法的精化在数据结构确定以后，算法的描述可以进一步根据设计的1201.2抽象数据类型

抽象数据类型的概念最早出现在20世纪70年代，它是面向对象方法的重要理论基础。本书在内容的组织中仅仅使用了抽象数据类型的概念，而没有严格采用面向对象的程序设计语言的描述机制（例如class）。1.2抽象数据类型

抽象数据类型的概念最早出现在20世纪7121基本概念－类型类型（type）是一组值（或者对象）的集合。例如：布尔作为一种类型是由真（true）和假（false）两个值组成的集合；布尔向量也可以作为一种类型，它的每个值是一个由true或false构成的向量。基本概念－类型类型（type）是一组值（或者对象）的集合。122基本概念－数据类型数据类型（datatype）通常是指在计算机（语言）中可以使用的一个类型，它不但包括这个类型的值的集合，还包括定义在这个类型上的一组操作。例如：整数作为一个数据类型是指在计算机上所能表示的（不是数学意义上任意大小的）所有整数和语言中定义的对于这些整数的全部操作（整数的加、减、乘、除、取余等）。基本概念－数据类型数据类型（datatype）通常是指在计123基本概念－抽象数据类型抽象数据类型（AbstractDataType简称为ADT）可以定义作具有一定行为(操作)的抽象（数学）类型。它不关心类型中值的具体表示方式和数据类型中定义的各种操作的具体实现方法，是所有可能的值的具体表示和各种操作的具体实现的抽象。基本概念－抽象数据类型抽象数据类型（AbstractDat124意义和作用（1）抽象数据类型的实质是抽象出了数据类型的使用要求，而把它的具体表示方式和运算的实现细节都隐藏起来。抽象数据类型仅仅规定了数据类型应该具有的行为（操作）。一旦抽象数据类型被正确实现，就好像程序设计语言中所提供的数据类型那样，可以被自由使用。意义和作用（1）抽象数据类型的实质是抽象出了数据类型的使用要125意义和作用（2）抽象数据类型支持数据类型的实现与使用分离的原则，允许独立地考虑数据类型的外部接口和内部的实现。这使应用程序只要按抽象数据类型的接口统一其使用界面；可以不管其是否已经实现，也不管它是如何实现的。对于系统的分解、设计、维护和修改均十分有利。

意义和作用（2）126

例1－抽象数据类型圆

ADTCircleis

operations area 计算圆的面积 circumference 计算圆的周长 getRadius 获取圆的半径 setRadius 设置圆的半径endADTCircle

例1－抽象数据类型圆 ADTCirclei127例2－集合抽象数据类型ADTSetis

Operations isEmpty 判断集合是否是空集合 add 给集合增加一个元素 remove 删除集合中的一个元素 isIn 判断一个元素是否在当前集合中end

ADTSet例2－集合抽象数据类型ADTSetis1281.3数据结构关于数据结构的研究，可以追溯到1972年C.A.R.Hoare奠基性的论文《数据结构笔记》；而现代计算机所大量采用的基本数据结构，最早的系统论述应归功于1973年D.E.Knuth的名著《计算机程序设计技巧》的问世。为了学习和研究的方便，计算机科学家把常用的数据进行分类，总结出许多典型的数据结构。1.3数据结构关于数据结构的研究，可以追溯到1972年C.1291.3.1什么是数据结构（通常）可以把数据结构理解为：计算机中表示（存储）的、具有一定（逻辑）关系和行为的一组数据。其中的每个数据(元素)称为这个结构的一个结点。（根据面向对象的观点）可以把数据结构理解成为抽象数据类型的物理实现。主要解决两个问题：如何具体表示抽象数据类型中的数学模型；如何给出抽象数据类型中需要操作的实现。1.3.1什么是数据结构（通常）可以把数据结构理解为：130数据结构三要素：逻辑结构:指数学模型中的基本元素（结点）和元素之间的相互关系。存储结构:指数学模型的具体表示方式，包括结点的表示和关系的表示。操作:指抽象数据类型关心的各种行为在存储结构上的具体实现（算法）。数据结构三要素：131例子－集合从集合抽象数据类型的定义出发，将讨论它的实现——集合数据结构：根据数学的概念，集合中的元素是各不相同而且无序的（逻辑结构）；将介绍使用顺序表、单链表、散列表等等许多不同的集合表示方法（存储结构）；并且在这些不同的表示基础上，给出各自的行为实现算法（操作）。

例子－集合从集合抽象数据类型的定义出发，将讨论它的实现——集1321.3.2数据结构的分类主要根据逻辑结构和存储结构进行分类

1.3.2数据结构的分类主要根据逻辑结构133逻辑结构B=<K，R>K是结点的有穷集合，R是K上的一个关系。K上的一个关系就是K上的一些二元组组成的集合K上的二元组是K中元素的有序对.若k,k’K,<k,k’>R，则称k为k’的前驱，k’为k的后继。没有前驱的结点称为开始结点，没有后继的结点称为终端结点。

K上不同的二元组集合构成不同的关系。逻辑结构的概念逻辑结构B=<K，R>逻辑结构的概念134按逻辑结构分类

根据R的特点可以将数据结构分为以下三类：线性结构：K中每个结点最多只有一个前驱和一个后继的结构。树形结构：K中每个结点最多只有一个前驱，但可有多个后继的结构。复杂结构：K中结点的前驱、后继结点个数都不作限制的结构。*集合：它可以看成R为空的情况，即结点之间没有任何关系。

按逻辑结构分类根据R的特点可以将数据结构分为以下三类：135按逻辑结构分类举例

线性结构举例树形结构举例

复杂结构举例

按逻辑结构分类举例线性结构举例136存储结构的概念存储结构:数据的逻辑结构在计算机中的存储(表示)。通常包括结点的表示和关系的表示。同一种逻辑结构，可以采用不同的表示方式。例如，线性表既可以用顺序（一维数组）的方式来表示（顺序表），也可以用链接的方式（使用指针）来表示（单链表或双链表）。存储结构的设计目标，是使用比较少的空间记录逻辑结构的必要信息，还能够有效实现(抽象数据类型中)要求的操作。

存储结构的概念存储结构:数据的逻辑结构在计算机中的存储(表示137根据存储结构分类：顺序表示：用一个连续的空间，顺序存放数据结构中的各个结点。（结点的关系需要另外存储或者隐含其中）链接表示：结点的存放位置是任意的，结点之间的关系通过与结点关联的指针（或者引用）方式显式表达出来。

散列表示：又称为关键码——地址转换法。即选择适当的散列（杂凑）函数，根据关键码的值将结点映射到给定的存储空间（散列表）中。

索引表示：索引与散列一样，都给出一种从关键码到存储地址的映射方法。不同的是，散列法的映射是通过函数定义；而索引法是通过建立辅助的索引结构解决。根据存储结构分类：顺序表示：用一个连续的空间，顺序存放数据结1381.3.3结点与结构在数据结构的讨论中重点研究的是“结构”，而把组成结构的那些元素抽象成一个“结点”。结点是数据结构中的基本单位，在实际应用中一个结点可以是一个字符、一个整数（初等类型），也可以是一个结构（组合类型）。1.3.3结点与结构在数据结构的讨论中重点研究的是“结构1391.3.4外存数据的组织

简单介绍常用的外存设备及其特点，讨论文件的结构和处理。掌握这些知识，对于理解涉及到外存上的数据结构（例如B/B+树）与算法（例如归并排序）会有帮助.1.3.4外存数据的组织

简单介绍常用的外存设备及其特点140基本概念文件是逻辑记录的集合。逻辑记录（简称记录）是应用程序需要进行内外存交换的逻辑单位。每个记录可以包含若干数据项，其中能够唯一标识该记录的数据项称为关键码。对外存的数据必须按页块存取。页块又称物理记录，是内存与外存进行交换的物理单位。基本概念文件是逻辑记录的集合。141外存设备目前广泛使用的外存储器有磁带、磁盘、光盘和优盘等。其中以磁带和磁盘最具代表性。

外存设备目前广泛使用的外存储器有磁带、磁盘、光盘和优盘等。142磁带磁带上的信息以页块为单位顺序存放，页块与页块之间留有间隙，间隙上不存放数据，但有被硬件识别的带标。一个页块就是一个物理记录。要读写一个页块，首先要定位，即通过磁带的移动使磁头对准被读页块的前沿，然后才能读写。磁带存储器的读写速度与(磁带的存储密度和)走带速度有关，因为属于机械动作，比内存数据的读写时间长得多。在读写前需要定位，定位需要的时间与当前磁头位置与需要定位的位置之间的距离成正比，最坏情况可能需要花费若干分钟。磁带磁带上的信息以页块为单位顺序存放，页块与页块之间留有间隙143磁盘磁盘类似于多碟的CD，若干盘片（比如６片）串在一根主轴上形成一个盘组，当主轴旋转时带动各个盘片旋转。每个盘面上包含大小不同的许多同心圆。每个圆圈称为一个磁道，各个盘面的半径相同的磁道合在一起构成一个柱面。一个磁道又可分为若干段，每段是一个页块（物理记录）。一个盘组上从大到小的存储地址为：柱面、磁道和页块。在磁盘上读写信息:１．选定柱面，这是机械动作，所以比较慢。２．选定磁道，由电子线路实现，所以比较快。３．找物理记录，这是机械动作，较慢。实际读写信息的时间比定位时间少得多，目前访问磁盘中的数据比访问内存慢5－6个数量级。

磁盘磁盘类似于多碟的CD，若干盘片（比如６片）串在一根主轴144缓冲区与访外主机对外存储器上的数据不能直接按字(或者字节)存取。读外存上的数据:1,把外存上一个或者多个物理记录读到内存的指定的区域，这个区域叫作缓冲区。2,在缓冲区中找到需要的逻辑记录进行处理。写的过程则相反，先写到缓冲区中，然后通过主机与外存的接口，把缓冲区中的数据写到外存储器的物理记录中。这种读写过程，通常称为访外。缓冲区与访外主机对外存储器上的数据不能直接按字(或者字节)存145外存的存取外存储器上的逻辑记录的地址由两部分表示：逻辑记录所在物理记录的地址；逻辑记录在物理记录内的相对位置。节省外存的存取时间的关键在于减少访外的次数。由于缓冲区的大小受到内存容量的限制，所以减少访外次数的有效方法是精心设计文件的结构，使外存中存放的记录，相互关联，以便于处理。外存的存取外存储器上的逻辑记录的地址由两部分表示：146文件的分类

顺序文件.文件中的记录可以按某种顺序（例如按放入文件的先后或者按关键码的大小）定义次序，并且在外存储器上是按同样的次序存放的，则这种文件叫做顺序文件。

散列文件.

通过某种函数关系（称为散列函数）作用到记录的关键码上来确定记录的外存地址。索引文件.对于文件中的记录也可以建立索引。对于大型的文件，其索引往往也是很大的，需要存放在外存上。这样索引也是一种文件。本书把索引和主文件总称为索引文件。对于索引文件，其主文件如果是一个顺序文件，又可以叫作索引顺序文件。倒排文件.对于需要对属性建立的索引，称为倒排索引．带有倒排索引的文件称为倒排索引文件，简称倒排文件。

文件的分类顺序文件.文件中的记录可以按某种顺序（例如按放入147文件的处理

检索。在文件中查找满足一定条件的记录。最常见的是，查找关键码为一指定值的记录，此时，成功的检索只能找出唯一的记录。插入。在文件中增加一个新的记录。删除。删去文件中的一个记录。插入和删除操作常常需要通过检索，先找到被插入或删除记录的位置。修改。把记录中某些属性的值改为新值。若被修改的属性包括关键码，则相当于删除一个老记录并插入一个新记录。排序。按照关键码或者某属性的值，从小到大（或从大到小）的次序，把文件的全部记录重新进行排列。这种排序叫做外排序。文件的处理检索。在文件中查找满足一定条件的记录。最常见的是1481.4算法本课是以数据结构为主线，算法为辅线组织内容。因为每种数据结构上的操作，都需要一定算法。对于不同存储结构的选择与评价，算法的好坏起着决定的因素。所有算法的实现也都需要数据结构的支持。算法与数据结构是程序设计的两大支柱。它们相辅相成，互相依赖。

1.4算法本课是以数据结构为主线，算法为辅线组织内容。149什么是算法算法是由有穷规则构成（为解决某一类问题）的运算序列。算法可以有若干输入(初始值或条件)；算法通常又有若干个输出(计算结果）。算法应该具有有穷性。一个算法必须在执行了有穷步之后结束。算法应该具有确定性。算法的每一步，必须有确切的定义。算法应该具有可行性。算法中的每个动作，原则上都是能够由机器或人准确完成的。什么是算法算法是由有穷规则构成（为解决某一类问题）的运算序列150算法的正确性如果一个算法以一组满足初始条件的输入开始，那么该算法的执行一定终止，并且在终止时得到满足要求的（输出）结果。算法的正确性151算法设计的方法贪心法分治法回溯法动态规划法分枝界限法算法设计的方法贪心法152贪心法基本思想是：当追求的目标是一个问题的最优解时，设法把对整个问题的求解工作分成若干步骤来完成。在其中的每一个阶段都选择从局部看是最优的方案，以期望通过各阶段的局部最优选择达到整体的最优。算法1.1解着色问题时就是采用的贪心法。贪心法实际上不能保证都成功地产生一个全局性最优解，但是通常可以得到一个可行的较优解。（举例）贪心法基本思想是：当追求的目标是一个问题的最优解时，设法把对153分治法基本思想是:把一个规模较大的问题分成两个或多个较小的与原问题相似的子问题。首先对子问题进行求解，然后设法把子问题的解合并起来，得出整个问题的解，即对问题分而治之。如果一个子问题的规模仍然比较大，不能很容易地求得解，就可以对这个子问题重复地应用分治策略。二分法检索就是用分治策略的典型例子。分治法基本思想是:把一个规模较大的问题分成两个或多个较小的与154回溯法基本思想是:有一些问题，需要通过彻底搜索所有可能情况寻找一个满足某些预定条件的最优解。由于彻底搜索的运算量通常非常大，所以采取一步一步向前试探，当有多种选择时可以任意选择一种，只要目前可行就继续向前，一旦发现问题或失败就后退，回到上一步重新选择，借助于回溯技巧和中间增加判断，这样常常可以大大地减少搜索时间。常见的迷宫问题以及八皇后问题都可以用回溯方法来解决。回溯法基本思想是:有一些问题，需要通过彻底搜索所有可能情况寻155动态规划法与分治法相似都是把一个大问题分解为若干较小的子问题，通过求解子问题而得到原问题的解。不同点是：分治法每次分解的子问题数目比较少，子问题之间界限清楚，处理的过程通常是自顶向下进行；动态规划法分解的子问题可能比较多，而且子问题相互包含，为了重用已经计算的结果，要把计算的中间结果全部保存起来，通常是自底向上进行。在带权图中，求所有结点之间最短路径的Floyd算法（见第9章）就属于动态规划法。动态规划法与分治法相似都是把一个大问题分解为若干较小的子问题156分枝界限法与回溯法相似，也是一种在表示问题解空间的树上进行系统搜索的方法。所不同的是，回溯法使用了深度优先策略，而分枝界限法一般采用广度优先策略或者采用最大收益（或最小损耗）策略，并且利用最优解属性的的上下界来控制搜索的分枝。

最后一章，在讨论背包问题时，介绍了一个用分枝界限法设计的算法。

分枝界限法与回溯法相似，也是一种在表示问题解空间的树上进行系1571.4.3算法的精化实现一个算法，就是要把设计者头脑中的算法思想转化成计算机中可以执行的程序。对于一个比较复杂的算法，其实现的过程往往需要经过多次细化才能完成。习惯上，把这个过程称为算法的精化。1.4.3算法的精化实现一个算法，就是要把设计者头脑158排序问题假设有n≥1个不同的整数a0，a1，…，an-1，要求把这些整数从大到小进行排序。排序算法可以明确地用下面的输入和输出关系来描述其功能：输入：是含n个元素的整数数组，记为a，其中的元素依次为：a[0],a[1],…,a[n-1]。输出：是输入数组a中元素重新排列，记为a'，其中的元素依次为：a'[0],a'[1],…,a'[n-1]，满足a'[i]≥a'[i+1]，对所有的0≤i<n-1都成立排序问题假设有n≥1个不同的整数a0，a1，…，an-1，要15