数据结构与算法.docx
《数据结构与算法.docx》由会员分享，可在线阅读，更多相关《数据结构与算法.docx（26页珍藏版）》请在冰点文库上搜索。
数据结构与算法
数据结构与算法
本章知识要点：
•算法的基本概念；
•数据结构的定义；
•线性表的定义和存储；
•树、二叉树的定义和存储；
•查找与排序算法。
1.1算法
1.1.1算法的基本概念
算法（algorithm）是一组有穷的规则，规定了解决某一特定类型问题的一系列运算，是对解题方案的准确与完整的描述。
算法是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。
在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。
算法+数据结构=程序，求解一个给定的可计算或可解的问题，不同的人可以编写出不同的程序，来解决同一个问题，这里存在两个问题：
一是与计算方法密切相关的算法问题；二是程序设计的技术问题。
算法和程序之间存在密切的关系。
1．算法的基本特征
作为一个算法，一般应具有以下几个基本特性。
1）确定性
算法的每一种运算必须有确定的意义，该种运算执行某种动作应无二义性，目的明确；这一性质反映了算法与数学公式的明显差别。
在解决实际问题时，可能会出现这样的情况：
针对某种特殊问题，数学公式是正确的，但按此数学公式设计的计算过程可能会使计算机系统无所适从，这是因为根据数学公式设计的计算过程只考虑了正常使用的情况，而当出现异常情况时，此计算过程就不能适应了。
2）可行性
要求算法中有待实现的运算都是基本的，每种运算至少在原理上能由人用纸和笔在有限的时间内完成；针对实际问题设计的算法，人们总是希望能够得到满意的结果。
但一个算法又总是在某个特定的计算工具上执行的，因此，算法在执行过程中往往要受到计算工具的限制，使执行结果产生偏差。
3）输入
一个算法有0个或多个输入，在算法运算开始之前给出算法所需数据的初值，这些输入取自特定的对象集合。
4）输出
作为算法运算的结果，一个算法产生一个或多个输出，输出是同输入有某种特定关系的量。
5）有穷性
一个算法总是在执行了有穷步的运算后终止，即该算法是可达的。
数学中的无穷级数，在实际计算时只能取有限项，即计算无穷级数值的过程只能是有穷的。
因此，一个数的无穷级数表示只是一个计算公式，而根据精度要求确定的计算过程才是有穷的算法。
算法的有穷性还应包括合理的执行时间的含义。
因为，如果一个算法需要执行千万年，显然失去了实用价值。
满足前四个特性的一组规则不能称为算法，只能称为计算过程，操作系统是计算过程的一个例子，在一个算法中，有些指令可能是重复执行的，因此指令的执行次数可能远远大于算法中的指令条数。
由有穷性可知，对于任何输入，一个算法在执行了有限类指令后一定要终止并且必须在有限的时间内完成，因此，一个程序如果对任何输入都不会陷入无限循环时，即是有穷的，则它就是一个算法。
操作系统用来管理计算机资源，控制作业的运行，没有作业运行时，计算过程并不停止，而是处于等待状态。
2．算法的描述
算法的描述方法可以归纳为以下几种：
（1）自然语言。
（2）图形，如N-S图、流程图，图的描述与算法语言的描述对应。
（3）算法语言，即计算机语言、程序设计语言、伪代码。
（4）形式语言。
用数学的方法，可以避免自然语言的二义性。
用各种算法描述方法所描述的同一算法，该算法的功用是一样的，允许在算法的描述和实现方法上有所不同。
人们的生产活动和日常生活离不开算法，都在自觉不自觉地使用算法，例如，人们要购买物品，会首先确定购买哪些物品，准备好所需的钱，然后确定到哪些商场选购、怎样去商场、行走的路线，若物品的质量好如何处理，对物品不满意又怎样处理，购买物品后做什么等。
以上购物的算法是用自然语言描述的，也可以用其他描述方法描述该算法。
图1-1所示的是用流程图描述算法的例子，其函数为：
图1-1流程图
3．算法设计基本方法
计算机解题的过程实际上是在实施某种算法，这些算法可称为计算机算法。
计算机算法不同于人工处理的方法。
在实际应用时，各种方法之间往往存在着一定的联系。
1）列举法
列举法的基本思想是根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。
因此，列举法常用于解决“是否存在”或“有多少种可能”等类型的问题，例如求解不定方程的问题。
列举法的特点是算法比较简单，但当列举的可能情况较多时，执行列举算法的工作量将会很大。
因此，在用列举法设计算法时，使方案优化，尽量减少运算工作量，是应该重点注意的。
通常，在设计列举算法时，只要对实际问题进行详细的分析，将与问题有关的知识条理化、完备化、系统化，从中找出规律；或对所有可能的情况进行分类，引出一些有用的信息，是可以大大减少列举量的。
列举原理是计算机应用领域中十分重要的原理。
许多实际问题，若采用人工列举是不可想象的，但由于计算机的运算速度快，擅长重复操作，可以很方便地进行大量列举。
列举算法虽然是一种比较笨拙而原始的方法，其运算量比较大，但在有些实际问题中（如寻找路径、查找、搜索等问题），局部使用列举法却是很有效的，因此，列举算法是计算机算法中的一个基础算法。
2）归纳法
归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。
显然，归纳法要比列举法更能反映问题的本质，并且可以解决列举量为无限的问题。
但是，从一个实际问题中总结归纳出一般的关系，并不是一件容易的事情，尤其是要归纳出一个数学模型更为困难。
从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。
归纳是一种抽象，即从特殊现象中找出一般关系。
但由于在归纳的过程中不可能对所有的情况进行列举，因此，最后由归纳得到的结论还只是一种猜测，还需要对这种猜测加以必要的证明。
实际上，通过精心观察而得到的猜测得不到证实或最后证明猜测是错的，也是常有的事。
3）递推法
所谓递推，是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。
其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简而确定。
递推本质上也属于归纳法，工程上许多递推关系式实际上是通过对实际问题的分析与归纳而得到的，因此，递推关系式往往是归纳的结果。
递推算法在数值计算中是极为常见的。
但是，对于数值型的递推算法必须要注意数值计算的稳定性问题。
4）递归法
人们在解决一些复杂问题时，为了降低问题的复杂程度（如问题的规模等），一般总是将问题逐层分解，最后归结为一些最简单的问题。
这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。
由此可以看出，递归的基础也是归纳。
在工程实际中，有许多问题就是用递归来定义的，数学中的许多函数也是用递归来定义的。
递归在可计算性理论和算法设计中占有很重要的地位。
递归分为直接递归与间接递归两种。
如果一个算法P显式地调用自己则称为直接递归。
如果算法P调用另一个算法Q，而算法Q又调用算法P，则称为间接递归调用。
递归是很重要的算法设计方法之一。
实际上，递归过程能将一个复杂的问题归结为若干个较简单的问题，然后将这些较简单的问题再归结为更简单的问题，这个过程可以一直做下去，直到最简单的问题为止。
有些实际问题，既可以归纳为递推算法，又可以归纳为递归算法。
但递推与递归的实现方法是大不一样的。
递推是从初始条件出发，逐次推出所需求的结果；而递归则是从算法本身到达递归边界的。
通常，递归算法要比递推算法清晰易读，其结构比较简练。
特别是在许多比较复杂的问题中，很难找到从初始条件推出所需结果的全过程，此时，设计递归算法要比递推算法容易得多。
但递归算法的执行效率比较低。
5）减半递推技术
实际问题的复杂程度往往与问题的规模有着密切的联系。
因此，利用分治法解决这类实际问题是有效的。
所谓分治法，就是对问题分而治之。
工程上常用的分治法是减半递推技术。
所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。
6）回溯法
前面讨论的递推和递归算法本质上是对实际问题进行归纳的结果，而减半递推技术也是归纳法的一个分支。
在工程上，有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤，并且也不能进行无限的列举。
对于这类问题，一种有效的方法是“试”。
通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。
这种方法称为回溯法。
回溯法在处理复杂数据结构方面有着广泛的应用。
1.1.2算法复杂度
算法的复杂度主要包括时间复杂度和空间复杂度。
1．时间复杂度
一个算法的时间复杂度是该算法的时间耗费，它是该算法所求解问题规模n的函数，当问题的规模n无穷大时，我们把时间复杂度T（n）的数量级称为算法的渐进时间复杂度。
为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。
为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。
基本运算反映了算法运算的主要特征，因此，用基本运算的次数来度量算法工作量是客观的也是实际可行的，有利于比较同一问题的几种算法的优劣。
例如，在考虑两个矩阵相乘时，可以将两个实数之间的乘法运算作为基本运算，而对于所用的加法（或减法）运算忽略不计。
又如，当需要在一个表中进行查找时，可以将两个元素之间的比较作为基本运算。
算法所执行的基本运算次数还与问题的规模有关。
例如，两个20阶矩阵相乘与两个10阶矩阵相乘，所需要的基本运算（即两个实数的乘法）次数显然是不同的，前者需要更多的运算次数。
因此，在分析算法的工作量时，还必须对问题的规模进行度量。
综上所述，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即
算法的工作量=f（n）
其中n是问题的规模。
例如，两个n阶矩阵相乘所需要的基本运算（即两个实数的乘法）次数为n，即计算工作量为n3，也就是时间复杂度为n3。
在具体分析一个算法的工作量时，还会存在这样的问题：
对于一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关，而实际上又不可能将所有可能情况下算法所执行的基本运算次数都列举出来。
例如，“在长度为n的一维数组中查找值为x的元素”，若采用顺序搜索法，即从数组的第一个元素开始，逐个与被查值x进行比较。
显然，如果第一个元素恰为x，则只需要比较1次。
但如果x为数组的最后一个元素，或者x不在数组中，则需要比较n次才能得到结果。
因此，在这个问题的算法中，其基本运算（即比较）的次数与具体的被查值x有关。
下面举几个例子，说明如何求算法的时间复杂度。
例1.1交换a和b的内容。
Temp=i;
i=j;
j=temp;
以上3条单个语句的执行次数均为1，该程序段的执行时间是一个与问题规模n无关的常数，因此，算法的时间复杂度为常数阶，记作T（n）=O
（1）。
事实上，只要算法的执行时间按不随着问题规模n的增加而增加，即使算法中有上千条语句，其执行时间也不过是一个较大的常数，此时，算法的时间复杂度也只是O
（1）。
例1.2变量计数之一。
x=0;y=0;
For（k=1;k<=n;k++）
x++;
For（i=1;i<=n;i++）
For（j=1;j<=n;j++）
y++;
一般情况下，对步进循环语句只需考虑循环体中语句的执行次数。
因此，以上程序段中执行次数最大的语句是第6条，其执行次数为f（n）=n2，所以该程序段的时间复杂度为T（n）=O（n2）。
由此可见，当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的执行次数f（n）决定的。
2．算法的空间复杂度
一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。
一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。
其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间（例如，在链式结构中，除了要存储数据本身外，还需要存储链接信息）。
如果额外空间量相对于问题规模来说是常数，则称该算法是原地（inplace）工作的。
在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。
1.2数据结构的基本概念
数据结构是在整个计算机科学与技术领域上广泛被使用的术语。
它用来反映一个数据的内部构成，即一个数据由哪些成分数据构成，以什么方式构成，呈什么结构。
数据结构有逻辑上的数据结构和物理上的数据结构之分。
逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。
数据结构是数据存在的形式。
利用计算机进行数据处理是计算机应用的一个重要领域。
在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。
显然，杂乱无章的数据是不便于处理的。
而将大量的数据随意地存放在计算机中，实际上也是“自找苦吃”，对数据处理更是不利。
1.2.1数据结构概念
计算机已被广泛用于数据处理，实际问题中的各数据元素之间总是相互关联的，所谓数据处理，是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。
在数据处理领域中，建立数学模型有时并不十分重要，事实上，许多实际问题是无法表示成数学模型的。
人们最感兴趣的是知道数据集合中各数据元素之间存在什么关系，应如何组织它。
简单地说，数据结构是指相互有关联的数据元素的集合。
例如，向量和矩阵就是数据结构，在这两个数据结构中，数据元素之间有着位置上的关系。
又如，图书馆中的图书卡片目录，则是一个较为复杂的数据结构，对于列在各卡片上的各种书之间，可能在主题、作者等问题上相互关联，甚至一本书本身也有不同的相关成分。
数据元素具有广泛的含义。
一般来说，现实世界中客观存在的一切个体都可以是数据元素。
例如表示数值的各个数18、11、35、23、16、……可以作为数值的数据元素；表示家庭成员的各成员名父亲、儿子、女儿可以作为家庭成员的数据元素。
一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。
在数据处理领域中，通常把数据元素之间这种固有的关系简单地用前后继关系（或直接前驱与直接后继关系）来描述。
数据结构作为计算机的一门学科，主要研究和讨论以下三个方面。
1．数据的逻辑结构
数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。
数据的逻辑结构有两个要素：
一是数据元素的集合，通常记为D；二是D上的关系，它反映了D中各数据元素之间的前后继关系，通常记为R。
即一个数据结构可以表示成
B=（D,R）
其中B表示数据结构。
为了反映D中各数据元素之间的前后继关系，一般用二元组来表示。
例如，假设a与b是D中的两个数据，则二元组（a,b）表示a是b的前件，b是a的后继。
这样，在D中的每两个元素之间的关系都可以用这种二元组来表示。
2．数据的存储结构
数据处理是计算机应用的一个重要领域，在实际进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，并且，各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的，而且一般也不可能相同。
数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。
由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系（即前后继关系），在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后继关系的信息。
一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。
而采用不同的存储结构，其数据处理的效率是不同的。
因此，在进行数据处理时，选择合适的存储结构是很重要的。
3．数据的运算
数据的存储不同决定了运算不同。
通常，一个数据结构中的元素结点可能是在动态变化的。
根据需要或在处理过程中，可以在一个数据结构中增加一个新结点也可以删除数据结构中的某个结点（称为删除运算）。
插入与删除是对数据结构的两种基本运算。
除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改等。
在对数据结构的处理过程中，不仅数据结构中的结点（即数据元素）个数在动态地变化，而且，各数据元素之间的关系也有可能在动态地变化。
例如，一个无序表可以通过排序处理而变成有序表；一个数据结构中的根结点被删除后，它的某一个后继可能就变成了根结点；在一个数据结构中的终端结点后插入一个新结点后，则原来的那个终端结点就不再是终端结点而成为内部结点了。
有关数据结构的基本运算将在后面讲到具体数据结构时再介绍。
如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。
在一个空的数据结构中插入一个新的元素后就变为非空；在只有一个数据元素的数据结构中，将该元素删除后就变为空的数据结构。
1.2.2数据结构分类
根据数据结构中各数据元素之间前后继关系的复杂程度，一般将数据结构分为两大类型：
线性结构与非线性结构。
如果一个非空的数据结构满足下列两个条件：
（1）有且只有一个根结点；
（2）每一个结点最多有一个前件，也最多有一个后继。
则称该数据结构为线性结构，线性结构又称线性表。
由此可以看出，在线性结构中，各数据元素之间的前后继关系是很简单的，如n维向量数据结构，它们都属于线性结构。
特别需要说明的是，在一个线性结构中插入或删除任何一个结点后还应是线性结构。
如果一个数据结构不是线性结构，则称之为非线性结构。
显然，在非线性结构中，各数据元素之间的前后继关系要比线性结构复杂，因此，对非线性结构的存储与处理比线性结构要复杂得多。
线性结构与非线性结构都可以是空的数据结构。
一个空的数据结构究竟是属于线性结构还是属于非线性结构，这要根据具体情况来确定。
如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构，否则属于非线性结构。
1.3线性表
1.3.1线性表概念
线性表（linelist）是最简单、最常用的一种数据结构。
线性表由一组数据元素构成。
数据元素的含义很广泛，在不同的具体情况下，它可以有不同的含义。
例如，英文小写字母表（a,b,c,…,z）是一个长度为26的线性表，其中的每一个小写字母就是一个数据元素。
再如，一年中的四个季节（春、夏、秋、冬）是一个长度为4的线性表，其中的每一个季节名就是一个数据元素。
矩阵也是一个线性表，只不过它是一个比较复杂的线性表。
在矩阵中，既可以把每一行看成是一个数据元素（即一个行向量为一个数据元素），也可以把每一列看成是一个数据元素（即一个列向量为一个数据元素）。
其中每一个数据元素（一个行向量或一个列向量）实际上又是一个简单的线性表。
数据元素可以是简单项（如上述例子中的数、字母、季节名等）。
在稍微复杂的线性表中，一个数据元素还可以由若干个数据项组成。
例如，某班的学生情况登记表是一个复杂的线性表，表中每一个学生的情况就组成了线性表中的每一个元素，每一个数据元素包括姓名、学号、性别、年龄和成绩数据项，在这种复杂的线性表中，由若干数据项构成的数据元素称为记录（record），而由多个记录构成的线性表又称为文件（file）。
综上所述，线性表是由n（n³0）个数据元素a1,a2,a3,…组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后继。
即线性表或是一个空表，或可以表示为（a1,a2,…,ai,…,an），其中ai（i=1,2,…,n）是属于数据对象的元素，通常也称其为线性表中的一个结点。
显然，线性表是一种线性结构。
数据元素在线性表中的位置只取决于它们自己的序号，即数据元素之间的相对位置是线性的。
1.3.2线性表的顺序存储
1．顺序存储特点
在计算机中存放线性表，一种最简单的方法是顺序存储，也称为顺序分配。
线性表的顺序存储结构具有以下两个基本特点：
（1）线性表中所有元素所占的存储空间是连续的；
（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
由此可以看出，在线性表的顺序存储结构中，其前后继两个元素在存储空间中是紧邻的，某元素一定存储在后继元素的前面。
在线性表的顺序存储结构中，如果线性表中各数据元素所占的存储空间（字节数）相等，线性表中查找某一个元素是很方便的。
假设线性表中的第一个数据元素的存储地址（指第一个字节的地址，即首地址）为ADR，一个数据元素占k个字节，则线性表中第i个元素在计算机存储空间中的存储地址为ADR+（i–1）•k，即在顺序存储结构中，线性表中每一个数据元素在计算机存储空间中的存储地址由该元素在线性表中的位置序号唯一确定。
一般来说，长度为n的线性表在计算机中的顺序存储结构如图1-2所示。
在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。
因为程序设计语言中的一维数组与计算机中实际的存储空间结构是类似的，这就便于用程序设计语言对线性表进行各种运算处理。
在用一维数组存放线性表时，该一维数组的长度通常要定义得比线性表的实际长度大一些，以便对线性表进行各种运算，特别是插入运算。
在一般情况下，如果线性表的长度在处理过程中是动态变化的，则在开辟线性表的存储空间时要考虑到线性表在动态变化过程中可能达到的最大长度。
如果开始时所开辟的存储空间太小，则在线性表动态增长时可能会出现存储空间不够而无法再插入新的元素；但如果开始时所开辟的存储空间太大，而实际上又用不着那么大的存储空间，则会造成存储空间的浪费。
在实际应用中，可以根据线性表动态变化过程中的一般规模来决定开辟的存储空间量。
2．顺序表上的运算
在线性表的顺序存储结构下，可以对线性表进行各种处理。
主要的运算有以下几种：
1）顺序表中插入运算
在长度为n的线性表中插入一个结点x，其插入过程如下：
首先从最后一个元素开始直到第i个元素，将其中的每一个元素均依次往后移动一个位置，然后将新元素x插入到第i个位置。
插入一个新元素后，线性表的长度变成了n+1，如图1-3所示。
maxsize为向计算机内存申请的最大存储空间，last为线性表中指向最后一个元素的指针
图1-3线性表在顺序存储结构下的插入
在一般情况下，要在第i个元素之前插入一个新元素时，首先要从最后一个（即第n个）元素开始，直到第i个元素之间共n+1个元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入到第i项。
插入结束后，线性表的长度就增加了1。
显然，在线性表采用顺序存储结构时，如果插入运算在线性表的末尾进行，即在第n个元素之后（可以认为是在第n+1个元素之前）插入新元素，则只要在表的末尾增加一个元素即可，不需要移动表中的元素；如果要在线性表的第1个元素之前插入一个新元素，则需要移动表中所有的元素。
在一般情况下，如果插入运算在第i个元素之前进行，则原来第i个元素之后（包括第i个元素）的所有元素都必须移动。
在平均情况下，要在线性表中插入一个新元素，需要移动表中一半的元素。
因此，在线性表顺序存储的情况下，要插入一个新元素，其效率是很低的，特别是在线性表比较大的情况下更为突出，由于数据元素的移动而消耗较多的处理时间。
2）顺序表删除运算
一个长度为n的线性表顺序存储在长度为maxsize的存储空间中。
现在要求删除线性表中的第i个元素。
其删除过程如下：
从第i个元素开始直到最后一个元素，将其中的每一个元素均依次往前移动一个位置。
此时，线性表的长度变成了
升级会员 