第一章 数据结构与算法
1.1.1 算法的基本概念
算法是指解题方案的准确而完整的描述。是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。 对于一个问题，如果可以通过一个计算机程序，在有限的存储空间内运行有限长的时间而得到正确的结果，则称这个问题是算法可解的。但算法不等于程序，也不等于计算方法。 程序的编制不可能优于算法的设计。 1．算法的基本特征
(1)可行性：算法中要执行的每一个步骤都可以在有限时间内完成，且正确，否则是不会得到满意结果的。
N=-10;
for( k=1;k<=n;k++ )
c=c+1;
(2)确定性：算法的确定性，是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。
X=a·b/c·d X=a·b/(c·d) X=a·(b/c)·d
(3)有穷性：算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。
算法的有穷性还应包括合理的执行时间的含义。 for( k=1;k<=n;k++ ) c=c+1;
下例是无限循环：
for( k=1;k<=-10;k++ ) c=c+1;
(4)拥有足够的情报：一个算法是否有效，还取决于为算法所提供的情报是否足够。 2，算法的基本要素
一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。
(1)算法中对数据的运算和操作
计算机算法就是计算机能处理的操作所组成的指令序列。
一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。
计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列。程序：是使用某种程序设计语言对一个算法或多个算法的具体实现。
在一般的计算机系统中，基本的运算和操作有以下四类： ①算术运算：主要包括加、减、乘、除等运算。 ②逻辑运算：主要包括“与”、“或”、“非”等运算。 ⑧关系运算：主要包括“大于”、“小于”、“等于”、“不等于”等运算。 ④数据传输：主要包括赋值、输入、输出等操作。
描述算法工具：如流程图，专门的算法描述语言，甚至用自然语言等来描述算法。 算法的主要特征着重于算法的动态执行，它区别于传统的着重于静态描述或按演绎方式求解问题的过程。
计算机算法则是使用一些最基本的操作，通过对已知条件一步一步的加工和变换，从而实现解题目标。
(2)算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构
算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。
描述算法的工具通常有传统流程图、N—S结构化流程图、算法描述语言等。 一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。 3．算法设计基本方法 (1)列举法 ，
列举法的基本思想是，根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。
列举法的特点是算法比较简单。但当列举的可能情况较多时，执行列举算法的工作量将会很大。
(2)归纳法
归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。 归纳法要比列举法更能反映问题的本质，并且可以解决列举量为无限的问题。归纳是一种抽象，即从特殊现象中找出一般关系。归纳得到的结论还只是一种猜测，还需要对这种猜测加以必要的证明。
(3)递推
所谓递推，是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简而确定。
递推关系式往往是归纳的结果。 (4)递归
将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。
递归分为直接递归与间接递归两种。
如果一个算法P显式地调用自己则称为直接递归。
如果算法P调用另一个算法Q，而算法Q又调用算法P，则称为间接递归调用。
递推与递归的实现方法是大不一样的。递推是从初始条件出发，逐次推出所需求的结果；而递归则是从算法本身到达递归边界的。
(5)减半递推技术
所谓分治法，就是对问题分而治之。工程上常用的分治法是减半递推技术。 所谓“减半”，是指将问题的规模减半，而问题的性质不变。 所谓“递推”，是指重复“减半”的过程。 (6)回溯法
通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解；若试探失败，就逐步回退，换别的路线再进行试探。这种方法称为回溯法。
1.1.2 算法复杂度
算法的复杂度主要包括时间复杂度和空间复杂度。 1．算法的时间复杂度 ·
所谓算法的时间复杂度，是指执行算法所需要的计算工作量。 一个程序在计算机上运算所消耗的时间主要取决下述因素： (1) 程序运行时所需要输入的数据总量消耗时间。 (2) 对源程序进行编译所需要的时间。 (3) 计算机执行每条指令所需要的时间。 (4) 计算机关键指令重复执行的次数。 分析算法的工作量。 (1)平均性态
所谓平均性态分析，是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。
设x是所有可能输入中的某个特定输入，p(x)是x出现的概率(即输入为x的概率)，t(x)是算法在输入为x时所执行的基本运算次数，则算法的平均性态定义为
A(n)=∑p(x)t(x)
当规模为n时，算法执行时所有可能输入的集合。p(x)必须由经验或用算法中有关的一些特定信息来确定。如果确定p(x)比较困难，则会给平均性态的分析带来困难。
(2)最坏情况复杂性(Worst-CaseComplexity)
所谓最坏情况分析，是指在规模为n时，算法所执行的基本运算的最大次数。它定义为
w(n)=max{t(x)} 算法分析 x=y+10 x=y*y+100
可是，在算法分析时，我们无论是计算拿一个x都认为是“一个操作步骤”，这样做是为了突出分析的重点，忽略细节。
为此，我们引入语句频度的概念（frequency count）。所谓语句频度即为“操作步骤”或“语句”重复执行的次数。为描述算法的时间复杂性，我们可以将复杂性用函数T(n)表示，n表示算法中处理数据对象的数量或问题的规模的度量，如一算法时间复杂性是： T(n)= 2n3+3n2+2n+1
当n足够大时，有T(n)≈2n3，或者g(n)=2n3
因为，当n足够大时，2n3的复杂度大大超过3n2+2n+1 ，或者说，T(n)数量级与n3数量级相同。所以，当n足够大时，可以忽略复杂性函数中复杂性较低的部分，而只用复杂度高的部分表示。
为此，我们进而引入渐进符号 “O”，用大写O字母表示函数T(n)的上限函数，即当n足够大时的函数，记为：O(g(n))= O(n3)
下面给出几种典型的复杂性函数的表示（a,b,c为已知数）： 线性函数：O(g(n))= O(a*n+b) =O(n) 平方函数：O(g(n))= O(a*n2+b*n)= O(n2)
指数函数：O(g(n))= O(an + b*n2+c*n)=O(an) 常数函数：O(g(n))= O(9+12)= O(1)
对数函数：O(g(n))= O((a*n*log2n +b*n)= O(n*log2n)
常数函数是指算法的复杂性与算法中处理数据对象的数量无关，比如，
T(n)= 15 T(n)= 20056
两个T(n)函数中，无论n的值如何，函数值始终为一常量，这时认为算法的复杂性是
O(1)，注意，不是T(n)函数的常量值。
例如，两个n×n的矩阵相乘，其算法可描述如下： void matrix-product（int a[][]，int b[][]，int c[][],int n）； { for( i=1;i<=n;i++ ) for ( j=1;j<=n;j++ ) { c[i][j] =0; for( k=1;k<=n;k++ ) c[i][j]=c[i][j]+a[i][k]*b[k][j]; } } 重复次数 n+1 n(n+1) n2 n2(n+1) n3 再如，下面有三个简单的程序段。 （a）x=x+1;
（b）for (i=1;i<=n;i++)
{ x=x+1;}
（c）for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
{ x=x+1;}
假定（a）中语句x=x+1不在任何的循环中，则语句频度为１，其执行时间是一个常数，因此，其时间复杂性是常量级，即O(1)。
在（b）中，同一语句x=x+1执行了n次，其频度为n，其时间复杂性依赖于n，所以，时间复杂性为O(n)。
在（c）中，语句x=x+1执行了n*n次，频度为n2 ，其时间复杂性依赖于n2 ，因此，时间复杂性为O(n2)。
通常情况下：
无循环结构，时间复杂性为量，记为：O（1） 单循环结构，时间复杂性为量，记为：O（n） 双循环结构，时间复杂性为量，记为：O（n2） 三层循环结构，时间复杂性为量，记为：O（n3） 2. 算法空间复杂性
算法执行所需要的内存空间 空间复杂性的组成 1) 程序空间
程序空间是指用来存储经过编译之后的程序指令所需的空间。指令空间一般不是数据结构所讨论的问题。
2) 数据空间
数据空间是指用来存储所有常量和变量所需要的空间。数据空间分成两部分： ? 存储常量和简单变量所需要的空间。 ? 存储复合变量所需要的空间。
这一部分空间又由两部分组成：一是数据结构定义的数据元素信息本身存储所需存储空间，二是动态分配的空间时存储链接空间。
1. 2 数据结构的基本概念
定义：数据结构就是研究计算机中大量数据存储的组织形式，并定义且实现对数据的相应的运算，以提高计算机的数据处理能力的一门科学。
数据结构相关事例
问题一：电话号码簿的使用及字典的使用。
党政机关 大学 企业 7 12 25 7 省委 市委 区委 55 127 224 55 省委办公厅一处 88060001 省委办公厅二处 88060002 · · · 市委办公二处 · · · 430 武汉大学 · · · · · · 127 市委办公一处 85800203 85800105 旅游 32 12 综合类大学 325 325 华中科技大学 理工大学 87870001 86880206 图1.1.1 电话号码簿
问题二：某省各城市之间要架设电话通信线路，要保证各城市间互通，又要使设成本最少。就是数据结构中讨论的图结构的应用－－最小生成树。
25 A B B A 45 12
25 12
7 11 5 E 7 5 E 11 34
78 C D C D 44
图1.1.3 城市连接及距离 图1.1.4 最小生成树
结构类型
数据结构中讨论的结构类型分为两个层面，一是逻辑层面的数据结构，简称逻辑结构；另一个是物理层面的数据结构，简称物理结构。