算法与数据结构

算法与数据结构

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

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

1.1从问题到程序

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

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

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

问题求解〔3〕编码阶段。

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

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

1.1.1问题分析与抽象

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

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

分析所有车辆的行驶路线的冲突问题。这个问题可以归结为对车辆的可能行驶方向作某种分组，对分组的要求：使任一个组中各个方向行驶的车辆可以同时平安行驶而不发生碰撞。信号灯问题－分析可以确定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。

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

这个问题的解有许多“可行解〞。我们希望能够设计一个最正确〔分组数最少〕的方案。称作“最优解〞。

着色问题－经典问题把上图中的一个结点理解为一个国家，结点之间的连线看作两国有共同边界，上述问题就变成著名的“着色问题〞：即求出〔最少〕要几种颜色可将图中所有国家着色，使得任意两个相邻的国家颜色都不相同。

1.1.2程序的设计与实现

一个问题的解决可以有许多方法，由于使用的工具是计算机，所以在选择方法时必须充分考虑到计算机的特点和条件，才能找到比较巧妙的方法，比较快而且准确地计算出需要的结果。选择算法－穷举法具体做法：从分为1、2、3…组开始考察，逐个列举出所有可能的着色方案，检查这样的分组方案是否满足要求。首先满足要求的分组，自然是问题的最优解。

穷举法的分析这类穷举法对结点少的问题(称为“规模小的〞问题)还可以用；对规模大的问题，由于求解时间会随着实际问题规模的增长而指数性上升，使计算机无法承受。

贪心法先用一种颜色给尽可能多的结点上色；然后用另一种颜色在未着色结点中给尽可能多的结点上色；如此反复直到所有结点都着色为止。

贪心法的一个解(1)红色：ABACADBADCED

(2)蓝色：BCBDEA

(3)绿色：DADB

(4)白色：EBEC

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

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

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

置NEW为空集合;

for每个vV1do

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

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

假设〔ADT〕集合和图支持下面行为：判断元素v是否属于集合V1表示为v

V1；从集合V1中去掉一个元素v表示为remove(V1,v)；向集合NEW里增加一个元素v用add(NEW,v)表示，判断集合V1是否空集合表示为isEmpty(V1)

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

抽象的着色算法intcolorUp(GraphG){ intcolor=0;//记录使用的颜色数 setV1=G.V;//V1初始化为图G的结点集V setNEW; while(!isEmpty(V1)) { NEW={}; while(v

V1.notAdjacentWith(NEW,v,G)) { add(NEW,v);remove(V1,v); } ++color; } returncolor;//返回使用的颜色数}数据结构的设计如果集合和图是程序设计语言中预定义的类型，那么colorUp中用到的remove(V1,v)和add(NEW,v)等就应该是语言中预定义的内部函数，该程序就几乎可以直接上机运行。否那么程序员需要自己用语言所提供的〔类型〕机制实现这些抽象数据类型〔集合、图等〕，这些正是数据结构设计要讨论的内容。算法的精化在数据结构确定以后，算法的描述可以进一步根据设计的数据结构进行精化。如果这个问题仍然是个比较复杂的问题，就还需要选择算法，也可能存在需要新抽象数据类型和数据结构。经过这种反复的精化过程，最后将算法中所有局部都细化为能用程序设计语言描述的成分，得到的就是我们希望的程序。1.2抽象数据类型

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

例1－抽象数据类型圆

ADTCircleis

operations area 计算圆的面积 circumference 计算圆的周长 getRadius 获取圆的半径 setRadius 设置圆的半径endADTCircle例2－集合抽象数据类型ADTSetis

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

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

逻辑结构B=<K，R>K是结点的有穷集合，R是K上的一个关系。K上的一个关系就是K上的一些二元组组成的集合K上的二元组是K中元素的有序对.假设k,k’K,<k,k’>R，那么称k为k’的前驱，k’为k的后继。没有前驱的结点称为开始结点，没有后继的结点称为终端结点。

K上不同的二元组集合构成不同的关系。逻辑结构的概念按逻辑结构分类

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

按逻辑结构分类举例

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

复杂结构举例

存储结构的概念存储结构:数据的逻辑结构在计算机中的存储(表示)。通常包括结点的表示和关系的表示。同一种逻辑结构，可以采用不同的表示方式。例如，线性表既可以用顺序〔一维数组〕的方式来表示〔顺序表〕，也可以用链接的方式〔使用指针〕来表示〔单链表或双链表〕。存储结构的设计目标，是使用比较少的空间记录逻辑结构的必要信息，还能够有效实现(抽象数据类型中)要求的操作。根据存储结构分类：顺序表示：用一个连续的空间，顺序存放数据结构中的各个结点。〔结点的关系需要另外存储或者隐含其中〕链接表示：结点的存放位置是任意的，结点之间的关系通过与结点关联的指针〔或者引用〕方式显式表达出来。散列表示：又称为关键码——地址转换法。即选择适当的散列〔杂凑〕函数，根据关键码的值将结点映射到给定的存储空间〔散列表〕中。索引表示：索引与散列一样，都给出一种从关键码到存储地址的映射方法。不同的是，散列法的映射是通过函数定义；而索引法是通过建立辅助的索引结构解决。1.3.3结点与结构在数据结构的讨论中重点研究的是“结构〞，而把组成结构的那些元素抽象成一个“结点〞。结点是数据结构中的根本单位，在实际应用中一个结点可以是一个字符、一个整数〔初等类型〕，也可以是一个结构〔组合类型〕。1.3.4外存数据的组织

简单介绍常用的外存设备及其特点，讨论文件的结构和处理。掌握这些知识，对于理解涉及到外存上的数据结构〔例如B/B+树〕与算法〔例如归并排序〕会有帮助.根本概念文件是逻辑记录的集合。逻辑记录〔简称记录〕是应用程序需要进行内外存交换的逻辑单位。每个记录可以包含假设干数据项，其中能够唯一标识该记录的数据项称为关键码。对外存的数据必须按页块存取。页块又称物理记录，是内存与外存进行交换的物理单位。外存设备目前广泛使用的外存储器有磁带、磁盘、光盘和优盘等。其中以磁带和磁盘最具代表性。

外存的存取外存储器上的逻辑记录的地址由两局部表示：逻辑记录所在物理记录的地址；逻辑记录在物理记录内的相对位置。节省外存的存取时间的关键在于减少访外的次数。由于缓冲区的大小受到内存容量的限制，所以减少访外次数的有效方法是精心设计文件的结构，使外存中存放的记录，相互关联，以便于处理。1.4算法本课是以数据结构为主线，算法为辅线组织内容。因为每种数据结构上的操作，都需要一定算法。对于不同存储结构的选择与评价，算法的好坏起着决定的因素。所有算法的实现也都需要数据结构的支持。算法与数据结构是程序设计的两大支柱。它们相辅相成，互相依赖。

什么是算法算法是由有穷规那么构成〔为解决某一类问题〕的运算序列。算法可以有假设干输入(初始值或条件)；算法通常又有假设干个输出(计算结果〕。算法应该具有有穷性。一个算法必须在执行了有穷步之后结束。算法应该具有确定性。算法的每一步，必须有确切的定义。算法应该具有可行性。算法中的每个动作，原那么上都是能够由机器或人准确完成的。算法的正确性如果一个算法以一组满足初始条件的输入开始，那么该算法的执行一定终止，并且在终止时得到满足要求的〔输出〕结果。算法设计的方法贪心法分治法回溯法动态规划法分枝界限法贪心法根本思想是：当追求的目标是一个问题的最优解时，设法把对整个问题的求解工作分成假设干步骤来完成。在其中的每一个阶段都选择从局部看是最优的方案，以期望通过各阶段的局部最优选择到达整体的最优。算法1.1解着色问题时就是采用的贪心法。贪心法实际上不能保证都成功地产生一个全局性最优解，但是通常可以得到一个可行的较优解。〔举例〕分治法根本思想是:把一个规模较大的问题分成两个或多个较小的与原问题相似的子问题。首先对子问题进行求解，然后设法把子问题的解合并起来，得出整个问题的解，即对问题分而治之。如果一个子问题的规模仍然比较大，不能很容易地求得解，就可以对这个子问题重复地应用分治策略。二分法检索就是用分治策略的典型例子。回溯法根本思想是:有一些问题，需要通过彻底搜索所有可能情况寻找一个满足某些预定条件的最优解。由于彻底搜索的运算量通常非常大，所以采取一步一步向前试探，当有多种选择时可以任意选择一种，只要目前可行就继续向前，一旦发现问题或失败就后退，回到上一步重新选择，借助于回溯技巧和中间增加判断，这样常常可以大大地减少搜索时间。常见的迷宫问题以及八皇后问题都可以用回溯方法来解决。动态规划法与分治法相似都是把一个大问题分解为假设干较小的子问题，通过求解子问题而得到原问题的解。不同点是：分治法每次分解的子问题数目比较少，子问题之间界限清楚，处理的过程通常是自顶向下进行；动态规划法分解的子问题可能比较多，而且子问题相互包含，为了重用已经计算的结果，要把计算的中间结果全部保存起来，通常是自底向上进行。在带权图中，求所有结点之间最短路径的Floyd算法〔见第9章〕就属于动态规划法。分枝界限法与回溯法相似，也是一种在表示问题解空间的树上进行系统搜索的方法。所不同的是，回溯法使用了深度优先策略，而分枝界限法一般采用广度优先策略或者采用最大收益〔或最小损耗〕策略，并且利用最优解属性的的上下界来控制搜索的分枝。最后一章，在讨论背包问题时，介绍了一个用分枝界限法设计的算法。1.4.3算法的精化实现一个算法，就是要把设计者头脑中的算法思想转化成计算机中可以执行的程序。对于一个比较复杂的算法，其实现的过程往往需要经过屡次细化才能完成。习惯上，把这个过程称为算法的精化。排序问题假设有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都成立直接选择排序的思想1从a中选出一个最大的整数放到一个空的数组a'中，作为a'中的第一个元素。2从a中剩下的元素中再选出最大的整数放到a'中，接在前一个已放入元素的后面。反复执行步骤2，直到a中所有整数都放到排好序的数组a'中。第一步精化:将排序后的数据仍然存储在排序前的数组里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,故这步可省〕。第二步精化:把上面执行n次重复的工作，精化成一个循环。i以1为步长，从0到n-2，循环执行：(1)从a[i]到a[n-1]中选出最大的整数，设为a[j]。(2)把a[i]与a[j]进行交换。第三步精化循环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使用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; }}1.4.4算法分析分析一个算法主要是看这个算法的执行需要花费多少机器资源。在进行算法分析时人们最关心的就是运行算法所要花费的时间和算法中使用的各种数据占有的空间。在文献中习惯称之为算法的时间代价和空间代价。根本概念算法的空间代价(或称空间复杂性)：当被解决问题的规模(以某种单位计算)由1增至n时，解该问题的算法所需占用的空间也以某种单位由f(1)增至f(n)，这时我们称该算法的空间代价是f(n)。算法的时间代价(或称时间复杂性)：当问题规模以某种单位由1增至n时，对应算法所消耗的时间也以某种单位由g(1)增至g(n)，这时我们称该算法的时间代价是g(n)。问题的规模、

空间单位和时间单位问题的规模一般可以根据问题本身的提法确定。例如对n个记录进行排序，这里n即可以作为问题的规模。空间单位和时间单位没有统一的规定，通常取算法描述中的初等数据占用的空间和根本操作消耗的时间为单位。大O表示法在描述算法分析的结果时，人们通常采用大O表示法：说某个算法的时间代价(或者空间代价)为O(f(n))，如果存在正的常数c和n0，当问题的规模n≥n0后，该算法的时间(或空间)代价T(n)≤c·f(n)。这时也称该算法的时间(或空间)代价的增长率为f(n)。最坏情况下代价的数量级每个算法的实际运行时的代价并不是固定不变的。由于不同的输入参数，可能使一个算法的实际代价出现很大差异。要全面分析一个算法，应该考虑它在最坏情况下的代价、最好情况下的代价和平均情况下的代价等。本书不是专门讨论算法分析的教材，所以在分析算法时主要考虑它们在最坏情况下的代价，而且仅仅要求计算它们的数量级。大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)。但从分析的精度来看，前一结论给出的是上确界(上界中最小的)，后者给出的仅是一般上界中的一个。计算规那么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)。c<log2n<