第第1章概论章概论 目录目录 1. 数据结构概述数据结构概述 2. 什么是什么是数据结构数据结构 3. 算法算法 二十世纪四十年代，电子数字计算机问世就是解二十世纪四十年代，电子数字计算机问世就是解决复杂的计算问题。早期，电子计算机的应用范围，决复杂的计算问题。早期，电子计算机的应用范围，也只局限于科学和工程的计算，其处理的对象是纯数也只局限于科学和工程的计算，其处理的对象是纯数值性的信息，通常，人们把这类问题称为数值计算。值性的信息，通常，人们把这类问题称为数值计算。 随随着着计计算算机机科科学学技技术术的的迅迅猛猛发发展展，计计算算机机的的应应用用已已从从传传统统的的数数值值计计算算领领域域发发展展到到各各种种非非数数值值计计算算领领域域。当当前前，计计算算机机已已广广泛泛地地应应用用于于情情报报检检索索、企企业业管管理理、系系统统工工程程等等各各个个领领域域；与与此此相相应应，计计算算机机的的处处理理对对象象也也从从简简单单的的纯纯数数值值性性数数据据发发展展到到一一般般的的符符号号和和具具有有一一定定结构的结构的数据。数据。1.1 数据结构概述数据结构概述 问题问题：对于每一种应用领域的处理对象，如何选择合对于每一种应用领域的处理对象，如何选择合适的数据表示，适的数据表示，如何有效地组织计算机存储如何有效地组织计算机存储，并在此基并在此基础上又如何有效地实现对象之间的础上又如何有效地实现对象之间的“运算运算”关系。关系。传统传统的解决数值计算的许多理论、方法和技术已不能满足解的解决数值计算的许多理论、方法和技术已不能满足解决非数值计算问题的需要，必须进行新的探索。决非数值计算问题的需要，必须进行新的探索。方法方法：数据结构就是研究和解决这些问题的重要基础数据结构就是研究和解决这些问题的重要基础理论。理论。 数据结构是一门研究非数值计算的程序设计问题中数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的计算机的操作对象以及它们之间的关系和操作等等的学科。学科。“数据结构数据结构”课程已成为计算机类专业的一门课程已成为计算机类专业的一门重要专业基础课。重要专业基础课。相关术语相关术语 1.2什么是数据结构什么是数据结构数据数据(Data)是信息的载体，它能够被计算机识别、存是信息的载体，它能够被计算机识别、存储和加工处理。它是计算机程序加工的储和加工处理。它是计算机程序加工的“原料原料”，而，而电子计算机则是加工处理数据（信息）的工具。电子计算机则是加工处理数据（信息）的工具。 数据元素数据元素(Data Element)是数据的基本单位。有些是数据的基本单位。有些情况下，数据元素也称为结点、顶点、元素、记录。情况下，数据元素也称为结点、顶点、元素、记录。 数据项数据项(Data Item)数据的不可分割的具有独立含义数据的不可分割的具有独立含义的最小单位，数据元素是数据项的集合的最小单位，数据元素是数据项的集合。 数据对象数据对象(Data Object)是具有相同性质的数据元素是具有相同性质的数据元素的集合。的集合。 数据结构数据结构(Data Structure)是研究数据元素之间的相是研究数据元素之间的相互关系，即数据的组织形式。虽然至今还没有一个关于互关系，即数据的组织形式。虽然至今还没有一个关于数据结构的标准定义，但它一般包括以下三方面的内容：数据结构的标准定义，但它一般包括以下三方面的内容： 数数据据元元素素之之间间的的逻逻辑辑关关系系，也也称称为为数数据据的的逻逻辑辑结结构构(Logical Structure)。 数数据据元元素素及及其其关关系系在在计计算算机机存存储储器器内内的的表表示示，也也称称为为数据的存储结构数据的存储结构(Storage Structure)。 数据的运算，即对数据施加的操作数据的运算，即对数据施加的操作(operation)。数据的逻辑结构是指数据元素和数据元素之间的逻辑数据的逻辑结构是指数据元素和数据元素之间的逻辑关系，它与数据的存储无关，是从具体问题抽象出来关系，它与数据的存储无关，是从具体问题抽象出来的数学模型。的数学模型。 数据的存储结构是指逻辑结构在计算机存储器里的数据的存储结构是指逻辑结构在计算机存储器里的实现（亦称为映象），它是依赖于计算机的，我们只实现（亦称为映象），它是依赖于计算机的，我们只在高级语言的层次上讨论存储结构。在高级语言的层次上讨论存储结构。 数据的运算是定义在数据的逻辑结构上的，每种逻数据的运算是定义在数据的逻辑结构上的，每种逻辑结构都有一个运算的集合。例如，最常用的运算有：辑结构都有一个运算的集合。例如，最常用的运算有：检索、插入、删除、更新、排序等。这些运算实际上检索、插入、删除、更新、排序等。这些运算实际上是在抽象的数据上所施加的一系列抽象的操作。是在抽象的数据上所施加的一系列抽象的操作。 所谓抽象的操作，是指我们只知道这些操作是所谓抽象的操作，是指我们只知道这些操作是“做什做什么么”，而无须考虑，而无须考虑“如何做如何做”。只有确定了存储结构。只有确定了存储结构之后，我们才考虑如何具体实现这些运算。换句话说，之后，我们才考虑如何具体实现这些运算。换句话说，算法的设计取决于数据的逻辑结构，算法的实现取决算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。于数据的物理存储结构。根据数据元素根据数据元素之间关系的不之间关系的不同，可将数据同，可将数据的逻辑结构分的逻辑结构分为集合、线性为集合、线性结构、树、图结构、树、图四类四类 数据类型数据类型(Data Type)是指程序设计语言中各变量可取是指程序设计语言中各变量可取的数据种类。是在程序设计语言中已经实现了的数据的数据种类。是在程序设计语言中已经实现了的数据结构。结构。 抽象数据类型抽象数据类型(Abstract Data TypeAbstract Data Type)是指由用户定义，是指由用户定义，用以表示应用问题的数据模型。抽象数据类型由基本用以表示应用问题的数据模型。抽象数据类型由基本的数据类型构成，并包括一组相关的服务（操作）的数据类型构成，并包括一组相关的服务（操作）;抽象数据类型简写做抽象数据类型简写做 ADT。 算法与数据结构密切相关，因为数据算法与数据结构密切相关，因为数据的运算是通过算法描述的，算法就是解决的运算是通过算法描述的，算法就是解决问题的策略、规则与方法。所以讨论算法问题的策略、规则与方法。所以讨论算法是数据结构课程的重要内容之一。是数据结构课程的重要内容之一。 1.3 算法算法 简单地说算法就是解决特定问题的方法。确切地说，就是简单地说算法就是解决特定问题的方法。确切地说，就是对于某一类特定的问题，算法规定了一个运算过程（一系列对于某一类特定的问题，算法规定了一个运算过程（一系列操作），它必须满足下述准则：操作），它必须满足下述准则： 输入：具有零个或多个输入的外界量，它们是算法开始输入：具有零个或多个输入的外界量，它们是算法开始 前对算法最初给出的量。前对算法最初给出的量。 输出：至少产生一个输出，它们是同输入有某种关系的输出：至少产生一个输出，它们是同输入有某种关系的 量。量。 有穷性：一个算法必须在执行有穷步之后结束，且每一有穷性：一个算法必须在执行有穷步之后结束，且每一 步都可在有限时间内完成。步都可在有限时间内完成。 确确定定性性：算算法法的的每每一一操操作作的的含含义义都都必必须须明明确确，无无二二义义性性。 可行性：算法中每一操作，都是能够由计算机执行的。可行性：算法中每一操作，都是能够由计算机执行的。1.3.1 什么是算法什么是算法 求求解解同同一一类类问问题题，可可以以有有许许多多不不同同的的算算法法，那那么么如如何何来来评评价价这些算法的优劣呢？通常可从以下几个方面来衡量：这些算法的优劣呢？通常可从以下几个方面来衡量： 正确性正确性（算法应该是算法应该是“正确的正确的”，即对任何合法的输入，即对任何合法的输入， 算法都能够得到正确的输出。算法都能够得到正确的输出。 可读性可读性）算法应易于理解，即在正确性满足的前提下，算法应易于理解，即在正确性满足的前提下， 越简单越好。越简单越好。 健壮性健壮性（算法应能识别非法的输入并能做出处理，而不算法应能识别非法的输入并能做出处理，而不 是产生误动作或者陷入瘫痪。是产生误动作或者陷入瘫痪。 时间复杂度（时间复杂度（time complexity）执行算法所耗费的时间执行算法所耗费的时间 的的 度量，即算法的时间性能。度量，即算法的时间性能。 空间复杂度（空间复杂度（space complexity） 执行算法所耗费的存执行算法所耗费的存 储空间的度量，主要考虑辅助存储空间。储空间的度量，主要考虑辅助存储空间。 1.3. 2 算法的评价算法的评价 语句频度（语句频度（frequency count）是指语句被重复执行的是指语句被重复执行的 次数。即在算法中某一语句被重复执行了次数。即在算法中某一语句被重复执行了n次，则次，则 其语句频度为其语句频度为n。 算算法法中中各各语语句句的的频频度度是是问问题题规规模模n的的某某个个函函数数f (n)，算算法的时间量度记作：法的时间量度记作： T(n) = O (f (n) ) （1.1） 它表示随问题规模它表示随问题规模n的增大，算法执行时间的增长的增大，算法执行时间的增长率和率和f(n)的增长率相同，称为算法的渐近时间复杂度的增长率相同，称为算法的渐近时间复杂度(asymptotic time complexity)，简称时间复杂度。简称时间复杂度。 void MatrixMult( int n, float amaxmax, float bmaxmax,float cmaxmax ) int i,j,k; float x; for(i=1; i=n; i+) / n+1 for(j=1;j=n;j+) / n(n+1) x=0; / n2 for(k=1;k=n;k+) / n2(n+1) x=x+aik*bkj; / n3 /end_for j cij=x; / n2 /end_for i 该算法中所有语句的频度之和（即算法的时间耗费）为：该算法中所有语句的频度之和（即算法的时间耗费）为： T(n)=2n3+3n2+2n+1 （1.2） 由此可知，算法由此可知，算法MatrixMult的时间耗费的时间耗费T(n)是矩阵是矩阵 阶数阶数n的函数。的函数。 该算法的时间复杂度该算法的时间复杂度T(n)当当n趋向无穷大时，有：趋向无穷大时，有：即，当即，当n充分大时，充分大时，T(n)和和n3之比是一个不等于零的常之比是一个不等于零的常数、即数、即T(n)和和n3是同阶的，或说是同阶的，或说T(n)和和n3的数量级相的数量级相同，记作同，记作T(n)=O(n3)。我们称我们称T(n)=O(n3)是算法是算法MatrixMult的的渐近时间复杂度渐近时间复杂度。记号记号“O”是数学符号，其严格的数学定义是：是数学符号，其严格的数学定义是： 当我们评价一个算法的时间性能时，主要标当我们评价一个算法的时间性能时，主要标准是算法时间复杂度的数量级，即算法的渐近准是算法时间复杂度的数量级，即算法的渐近时间复杂度。时间复杂度。 若若T(n)和和f (n)是是定定义义在在正正整整数数集集合合上上的的两两个个函函数数，当当存存在在两两个个正正的的常常数数c和和n0，使使得得对对所所有有的的nn0，都有都有T(n)cf(n)成立，则成立，则T(n)=O(f(n)。 设有两个算法设有两个算法A A1 1和和A A2 2，求解同一问题，它们求解同一问题，它们的时间复杂度分别是的时间复杂度分别是T T1 1(n)=100n(n)=100n，T T2 2(n)=n(n)=n2 2。 当输入量当输入量n100nT(n)T2 2(n)(n)，后者花后者花费的时间较少。但是，随着问题规模费的时间较少。但是，随着问题规模n n的增大，的增大，两个算法的时间开销之比两个算法的时间开销之比n n2 2/100n/100n亦随着增大。亦随着增大。也就是说，当问题规模较大时，算法也就是说，当问题规模较大时，算法A A1 1比算法比算法A A2 2要有效得多，它们的渐近时间复杂度要有效得多，它们的渐近时间复杂度O(n)O(n)和和O(nO(n2 2) )，正是从宏观上评价了这两个算法在时间正是从宏观上评价了这两个算法在时间方面的质量。方面的质量。 在在算算法法分分析析时时，往往往往对对算算法法的的时时间间复复杂杂度度和和渐渐近近时时间间复复杂杂度度不不予予区区分分，而而经经常常是是将将渐渐近近时时间间复复杂杂度度T(n)=O(f(n)简简称称为为时时间间复复杂杂度度，其其中中的的f (n)一一般般是是算算法法中中频频度度最最大大的的语语句句频频度度。例例如如，我我们们说说：算算法法MatrixMult的的时时间间复复杂杂度度是是T(n)=O(n3)，这这里里的的f(n)= n3是是该该算算法法中中语语句句的的频频度。度。 按数量级递增排列，常见的时间复杂度有按数量级递增排列，常见的时间复杂度有 ： 常数阶常数阶O(1)，对数阶对数阶O(log2n)，线性阶线性阶O(n)，线性对数阶线性对数阶O(nlog2n )，平方阶平方阶O(n2)，立方阶立方阶O(n3)，k次方阶次方阶O(nk)，指数阶指数阶O(2 n)。即下面的即下面的(1.3) O(1) O(log2n) O(nlog2n) O(n2) O(n3) O(nk) O(2 n) 类类似似于于算算法法的的时时间间复复杂杂度度，本本书书中中以以空空间间复复杂杂度度(space complexity)作作为为算算法法所所需需存存储储空空间间的的量量度度，记作记作 S(n)= O(f(n) （1.4） 其中其中n为问题的规模为问题的规模(或大小或大小)。 一一个个上上机机执执行行的的程程序序除除了了需需要要存存储储空空间间来来寄寄存存本本身身所所用用指指令令、常常数数、变变量量和和输输入入数数据据外外，也也需需要要一一些些对对数数据据进进行行操操作作的的工工作作单单元元和和存存储储一一些些为为实实现现计计算算所所需需信信息息的的辅辅助助空空间间。如如果果输输入入数数据据所所占占空空间间只只取取决决于于问问题题本本身身，和和算算法法无无关关，则则只只需需要要分分析析除除输输入入和和程程序序之之外外的的额额外外空空间间；否否则则应应同同时时考考虑虑输输入入本本身身所所需需空空间间（和和输输入入数数据据的的表示形式有关）。表示形式有关）。 设设计计一一个个算算法法后后，要要对对它它进进行行描描述述，可可以以用用自自然然语语言言、数数字字语语言言或或约约定定的的符符号号来来描描述述，也也可可以以用用计计算算机机高高级级程程序语言来描述。序语言来描述。 1.3. 3 算法的描述算法的描述 我我们们用用C+语语言言描描述述数数据据结结构构及及算算法法；对对每每种种数数据据结结构构先先用用抽抽象象数数据据类类型型（ADT）简简单单给给出出这这种种数数据据结结构构的的定定义义及及基基本本运运算算，并并用用类类C语语言言讲讲解解一一些些典典型型的的基基本本运运算算（操操作作），在在每每章章的的末末尾尾用用C+的的类类声声明明给给出出该该数数据据结结构构的的数数据据及及操操作作（接接口口部部分分），并并且且给给出出典典型型操操作作的的实实现现代代码码（经经过过调调试试的的算算法法）；ADT是是在在概概念念层层上上描描述述问问题题；类类是是在在实实现现层层上上描描述述问问题题；在在应应用用层层上上操操作作对对象象（类类的的实实例）解决问题。例）解决问题。