数据结构与算法_概论

1、数据结构与算法Data Structures and Algorithm第第1章章 概论概论 【定义定义】“数据结构是计算机中数据结构是计算机中存储、组织数据存储、组织数据的方式。的方式。精心选择的数据结构可以带来精心选择的数据结构可以带来最优效率的算法最优效率的算法。”1/251 引子引子例例1.1 该该如何摆放书如何摆放书，才能让读者很方便地找到你手里这本，才能让读者很方便地找到你手里这本数据结构？数据结构？第第1章章 概论概论 【分析分析】2/251 引子引子方法方法1 随便放随便放任何时候有新书进来，哪里有空就把书插到哪里任何时候有新书进来，哪里有空就把书插到哪里。方法方法2 按照书名

2、的按照书名的拼音字母顺序拼音字母顺序排放。排放。方法方法3 把书架把书架划分成几块区域划分成几块区域，每块区域指定摆放某种类别的图书；，每块区域指定摆放某种类别的图书；在每种类别内，按照书名的拼音字母顺序排放。在每种类别内，按照书名的拼音字母顺序排放。 查找效率极低！查找效率极低！ 有时插入新书很困难！有时插入新书很困难！ 可能造成空间的浪费！可能造成空间的浪费！第第1章章 概论概论 1 引子引子例例1.2 写程序实现一个函数写程序实现一个函数PrintN，使得传入一个正整，使得传入一个正整数为数为N的参数后，能顺序的参数后，能顺序打印从打印从1到到N的全部正整数。的全部正整数。 void P

3、rintN ( int N ) int i; for ( i=1; i=N; i+ ) printf(“%dn”, i ); return; void PrintN ( int N ) if ( !N ) return; PrintN( N 1 ); printf(“%dn”, N ); return; 3/25第第1章章 概论概论 1 引子引子例例1.3 多项式的标准表达式可以写为：多项式的标准表达式可以写为： f(x) = a0 + a1x + a2x2 + anxn现给定一个多项式的阶数现给定一个多项式的阶数 n，并将全体系数存放在数组，并将全体系数存放在数组 a 里。请写程序计算这个多

4、项式在里。请写程序计算这个多项式在给定点给定点 x 处的值处的值。方法方法1 计算多项式函数值的计算多项式函数值的直接法直接法 double f( int n, double a, double x ) /* 计算阶数为计算阶数为n，系数为，系数为a0.an的多项式在的多项式在x点的值点的值 */int i;double p = a0;for ( i=1; i0; i-)p = ai-1 + x*p;return p;4/25#include #include clock_t start, stop; /* clock_t是是clock()函数返回的变量类型函数返回的变量类型 */double

5、 duration; /* 记录被测函数运行时间，以秒为单位记录被测函数运行时间，以秒为单位 */int main () /* 不在测试范围内的准备工作写在不在测试范围内的准备工作写在clock()调用之前调用之前*/ start = clock(); /* 开始计时开始计时 */ function(); /* 把被测函数加在这里把被测函数加在这里 */ stop = clock(); /* 停止计时停止计时 */ duration = (double)(stop - start)/CLK_TCK;/* 计算运行时间计算运行时间 */ /* 其他不在测试范围的处理写在后面，例如输出其他不在测试

6、范围的处理写在后面，例如输出duration的值的值 */ return 0; 秦九韶算法的计算速度明显比秦九韶算法的计算速度明显比直接法直接法快了一个数量级快了一个数量级！为什么会这样？为什么会这样？第第1章章 概论概论 1 引子引子5/25代码代码1.6 测试函数测试函数function()的的运行时间运行时间 即使解决一个非常简单的问题，往往也有即使解决一个非常简单的问题，往往也有多种方法多种方法，且不同方法之间的且不同方法之间的效率可能相差甚远效率可能相差甚远 解决问题方法的解决问题方法的效率效率 跟数据的跟数据的组织方式组织方式有关（如例有关（如例1.1） 跟跟空间的利用效率空间的利

7、用效率有关（如例有关（如例1.2） 跟跟算法的巧妙算法的巧妙程度有关（如例程度有关（如例1.3）第第1章章 概论概论 1 引子引子6/25 数据结构基本概念数据结构的起源 早期人们把计算机理解为数值计算的工具 现实中，更多的不是解决数值计算的问题数据结构的起源 1968年Prof. Donald E. Knuth 数据的逻辑结构和存储结构及操作数据结构的起源 1968年数据结构作为独立的课程出现。从此计算机相关专业开始享受数据结构的“折磨”Live is just a chocolate ,enjoy it! 数据结构的起源 70年代初，出现大型程序，结构程序设计方法学受到追捧，出现了著名的公

8、式： 程序设计=数据结构+算法基本概念 数据是什么？ 描述客观事物的符号 计算机中可以操作的对象 能被计算机识别 输入给计算机处理的符号基本概念 数据 数值型：整数、实型等 非数值型：字符、声音、图像、视频基本概念 数据就是必须满足两个条件的符号： 可以输入到计算机中 能被计算机程序处理 数值型类型数据可以进行数值计算 字符型数据需要非数值处理 声音、图像、视频等其实可以通过编码的手段变成字符数据来处理。基本概念 数据元素是什么？ 组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。 在人类中，数据元素是指什么？ 畜类呢？基本概念 数据项是什么？ 一个数据元素可以由若干

9、个数据项组成。 人这样的数据元素包含的数据项？基本概念 数据项是数据不可分割的最小单位。 但在真正讨论问题时，数据元素才是数据结构中建立数据模型的着眼点。 例如：讨论一部电影时，是讨论电影的角色这样的“数据元素”，而不是角色的姓名或年龄这样的“数据项”。基本概念 数据对象是什么？ 性质相同的数据元素的集合，是数据的子集。 “性质相同” 数据元素具有相同数量和类型的数据项 人都有姓名、生日、性别等相同的数据项基本概念 数据结构是什么？ 相互之间存在一种或多种特定关系的数据元素的集合。基本概念数据数据对象数据元素数据元素数据元素数据元素数据项数据项数据项数据项数据项数据项数据项数据项逻辑结构与物理

10、结构 按视点不同，数据结构分为 逻辑结构 物理结构逻辑结构 逻辑结构 数据对象中元素之间的相互关系。 常见的逻辑结构 集合结构 线性结构 树型结构 图形结构逻辑结构 集合结构 除同属一集合相互之间无其他关系逻辑结构 线性结构 数据元素之间是一对一的关系。逻辑结构 树型结构 数据元素之间存在一对多的层次关系。逻辑结构 图形结构 数据元素之间是多对多的关系物理结构 物理结构：数据的逻辑结构在计算机中的存储形式 顺序存储结构 链式存储结构第第1章章 概论概论 数据对象数据对象： 计算机要处理的事物，如例计算机要处理的事物，如例1.1中中“图书图书” 。2.1 术语定义术语定义 操作操作：处理事物的动

11、作集合，如例处理事物的动作集合，如例1.1中的中的“查找查找”和和“插入插入”，例例1.2的函数的函数“求值求值”等。等。 算法算法： 操作的实现方法，如例操作的实现方法，如例1.1的按字母序排放的的按字母序排放的“查找查找”和和“插入插入”、例、例1.2的的“直接法直接法”和例和例1.3的的“秦九韶法秦九韶法”等。等。 通常一个算法用一个通常一个算法用一个函数函数来实现来实现。 逻辑结构逻辑结构：数据对象的逻辑组织关系。分为：数据对象的逻辑组织关系。分为“线性线性”、“树树”和和“图图”。例。例1.1中按方法中按方法1来处理，就是把图书集看成是线性的结构；按来处理，就是把图书集看成是线性的结

12、构；按方法方法3来处理，就是把图书集看成是树形的结构。来处理，就是把图书集看成是树形的结构。 物理物理结构结构：数据对象信息在计算机内存中的存储组织关系。一般分：数据对象信息在计算机内存中的存储组织关系。一般分为为“顺序存储顺序存储”和和“链链式式存储存储”。7/25第第1章章 概论概论 数据数据类型：类型： 数据对象的类型确定了其数据对象的类型确定了其“操作集操作集”和和“数据定数据定义域义域”。2.2 抽象数据类型抽象数据类型 抽象抽象数据数据类型：类型： “抽象抽象”的意思，是指我们描述数据类型的的意思，是指我们描述数据类型的方法是不依赖于具体实现的，即数据对象集和操作集的描述与方法是不

13、依赖于具体实现的，即数据对象集和操作集的描述与存放数据的存放数据的机器无关、与数据存储的物理结构无关、与实现操机器无关、与数据存储的物理结构无关、与实现操作的算法和编程语言均无关作的算法和编程语言均无关。简而言之，抽象数据类型只描述。简而言之，抽象数据类型只描述数据对象集和相关操作集数据对象集和相关操作集“是什么是什么”，并不涉及，并不涉及“如何做到如何做到”的问题。的问题。8/25第第1章章 概论概论 例例1.4“矩阵矩阵”的抽象数据类型定义的抽象数据类型定义2.2 抽象数据类型抽象数据类型类型名称类型名称：Matrix数据对象集：数据对象集：一个一个M N的矩阵的矩阵 A。操作集操作集：对

14、于任意矩阵：对于任意矩阵A、B、C Matrix，以及，以及正正整数整数i、j、M、N，以下以下仅列出几项有代表性的操作。仅列出几项有代表性的操作。1）Matrix Create( int M, int N )：返回一个返回一个M N的空矩阵；的空矩阵；2） int GetMaxRow( Matrix A )：返回矩阵：返回矩阵A的总行数；的总行数；3）int GetMaxCol( Matrix A )：返回矩阵：返回矩阵A的总列数；的总列数；4）ElementType GetEntry( Matrix A, int i, int j )：返回矩阵：返回矩阵A的第的第i行、行、第第j列的元素；

15、列的元素；5）Matrix Add( Matrix A, Matrix B )：如果：如果A和和B的行、列数一致，则的行、列数一致，则返回矩阵返回矩阵C=A+B，否则返回错误标志；，否则返回错误标志；6） Matrix Multiply( Matrix A, Matrix B )：如果：如果A的列数等于的列数等于B的行数，的行数，则返回矩阵则返回矩阵C = AB，否则返回错误标志；，否则返回错误标志；7）9/25【定义定义】一个一个算法算法是解决某一类问题的步骤的描述。是解决某一类问题的步骤的描述。一般一般而言，而言，算法应该符合以下五项要求：算法应该符合以下五项要求：(1) 输入输入：它接受

16、一些输入（有些情况下不需要输入）它接受一些输入（有些情况下不需要输入）；(2) 输出输出：至少：至少产生产生一个一个输出输出；(3) 确定性确定性：算法的每一算法的每一步步必须有充分明确的必须有充分明确的含义含义，不可以有歧义，不可以有歧义；(4) 有限性有限性：算法是一个有限指令集，并一定在有限步骤之后终止算法是一个有限指令集，并一定在有限步骤之后终止；(5) 可行性可行性：算法的每一步：算法的每一步必须在计算机能处理的范围之内必须在计算机能处理的范围之内。第第1章章 概论概论 3.1 算法定义算法定义 另外，另外，算法的算法的描述描述可以可以不依赖于任何一种计算机语言以及具体的不依赖于任何

17、一种计算机语言以及具体的实现手段。实现手段。可以用可以用自然语言、流程图自然语言、流程图等方法来描述。等方法来描述。 但是，但是，用某一种计算机语言进行用某一种计算机语言进行伪码描述伪码描述往往使算法容易被理解，往往使算法容易被理解，本书即采用本书即采用C语言的部分语法作为描述算法的工具。语言的部分语法作为描述算法的工具。10/25例例 选择法排序选择法排序：把：把n个整数从小到大排序。个整数从小到大排序。思想：从余下的未排序的部分整数中，挑选最小整数放在前思想：从余下的未排序的部分整数中，挑选最小整数放在前面已排序部分的后面面已排序部分的后面.如何进行排序如何进行排序? 哪里哪里?void

18、SelectionSort ( int List, int N ) /* 将将N个整数个整数List0.ListN-1进行非递减排序进行非递减排序 */ for ( i = 0; i 0, n0 0 ， 使得当使得当 n n0 时有时有 T (n) c f(n) 例例1.3 中秦九韶算法的时间复杂度是中秦九韶算法的时间复杂度是O(n) ， 而简单直接法的时间复杂度是而简单直接法的时间复杂度是O(n2) 。定义定义1.2 T (n) = (g(n) 表示存在常数表示存在常数c 0, n0 0 ， 使得当使得当 n n0 时有时有 T (n) c g(n)3.3 复杂度的渐进表示法复杂度的渐进表示

19、法定义定义1.3 T (n) = (h(n) 表示表示 T (n) = O(h(n) 同时同时T (n) = (h(n)16/25第第1章章 概论概论 常用函数增长表常用函数增长表3.3 复杂度的渐进表示法复杂度的渐进表示法输入规模输入规模n函数函数124816321111111log2 n012345n12481632n log2 n0282464160n21416642561024n318645124096327682n2416256655364294967296n!122440326 209227898800026313 103317/25012345678910010203040506

20、02nn2n log nnlog nfn第第1章章 概论概论 3.3 复杂度的渐进表示法复杂度的渐进表示法18/25 s = 微秒微秒 = 10-6 秒秒ms = 毫秒毫秒 = 10-3 秒秒 sec = 秒秒min = 分分 yr = 年年hr = 小时小时 d = 天天n第第1章章 概论概论 3.3 复杂度的渐进表示法复杂度的渐进表示法19/25第第1章章 概论概论 对给定的算法做渐进分析时，有几个小窍门：对给定的算法做渐进分析时，有几个小窍门：(1)若两段算法分别有复杂度T1(n) = O(f1(n) 和 T2 (n) = O(f2(n) ，那么两段算法串联在一起的复杂度: T1(n)+

21、T2 (n) = max( O(f1(n), O(f2(n) ) 那么两段算法嵌套在一起的复杂度: T1(n) T2 (n) = O( f1(n) f2(n) )3.3 复杂度的渐进表示法复杂度的渐进表示法(2) 若 T(n)是关于n的k阶多项式，那么T(n) = (nk) (3) 一个循环的时间复杂度等于循环次数乘以循环体代码的复杂度。例如下面循环的复杂度是O(N)： for ( i=0; iN; i+ ) x = y*x + z; k+; (1) 若干层若干层嵌套循环嵌套循环的时间复杂度等于的时间复杂度等于各层循环次数的乘积各层循环次数的乘积再乘以循环体再乘以循环体代码的复杂度。代码的复杂

22、度。例如下列例如下列2层嵌套循环的复杂度是层嵌套循环的复杂度是O(N2)：for ( i=0; iN; i+ ) for ( j=0; jN; j+ ) x = y*x + z; k+; (2) if-else 结构的复杂度取决于结构的复杂度取决于if的条件判断复杂度和两个分枝部分的复的条件判断复杂度和两个分枝部分的复杂度，总体复杂度杂度，总体复杂度取三者中最大取三者中最大。即对结构：。即对结构： if (P1) /* P1的复杂度为的复杂度为 O(f1) */ P2; /* P2的复杂度为的复杂度为 O(f2) */ else P3; /* P3的复杂度为的复杂度为 O(f3) */总复杂度

23、为总复杂度为 max( O(f1), O(f2), O(f3) ) 。20/25问题问题给定给定 n个整数个整数(可以是负数可以是负数)的序列的序列a1, a2, , an , 求函数求函数 f(i, j) = max( 0, ) 的最大值。的最大值。 .jikka若全部整数都是若全部整数都是负数，则最大子负数，则最大子列和为列和为0.算法算法1int MaxSubseqSum1 (int List , int N ) int ThisSum, MaxSum, i, j, k; /* 1*/ MaxSum = 0; /* 初始化最大子列和初始化最大子列和 */* 2*/ for( i = 0;

24、 i N; i+ ) /* i是子列左端位置是子列左端位置 */* 3*/ for( j = i; j N; j+ ) /* j是子列右端位置是子列右端位置*/* 4*/ ThisSum = 0; /* ThisSum是从是从Listi到到Listj的子列和的子列和 */* 5*/ for( k = i; k MaxSum ) /* 如果刚得到的这个子列和更大如果刚得到的这个子列和更大 */* 8*/ MaxSum = ThisSum; /*则更新结果则更新结果*/ /* i， j 循环结束循环结束 */* 9*/ return MaxSum; T( N ) = O( N3 )第第1章章 概论

25、概论 4 应用实例：最大子列和问题应用实例：最大子列和问题21/25精确计算：算法算法 2int MaxSubseqSum2 (int List , int N ) int ThisSum, MaxSum, i, j; /* 1*/ MaxSum = 0; /* 初始化最大子列和初始化最大子列和 */* 2*/ for( i = 0; i N; i+ ) /* i是子列左端位置是子列左端位置 */* 3*/ ThisSum = 0; /* ThisSum是从是从Listi到到Listj的子列和的子列和 */* 4*/ for( j = i; j MaxSum ) /* 如果刚得到的这个子列和更

26、大如果刚得到的这个子列和更大 */* 7*/ MaxSum = ThisSum; /* 则更新结果则更新结果 */ /* j循环结束循环结束 */ /* i循环结束循环结束 */* 8*/ return MaxSum; T( N ) = O( N2 )第第1章章 概论概论 4 应用实例：最大子列和问题应用实例：最大子列和问题22/25算法算法 3分治法分治法4 35 2 126 2治治分分45626811T ( N/2 )T ( N/2 )O( N )T ( N ) = 2 T( N/2 ) + c N , T(1) = O(1)= 2 2 T( N/22 ) + c N/2 + c N= 2

27、k O(1) + c k N 此处此处 N/2k = 1 = O( N log N )第第1章章 概论概论 4 应用实例：最大子列和问题应用实例：最大子列和问题23/25int DivideAndConquer(int List , int Left, int Right ) int MaxLeftSum, MaxRightSum; int MaxLeftBorderSum, MaxRightBorderSum; int LeftBorderSum, RightBorderSum; int Center, i;/* 1*/ if( Left = Right ) /* Base case */*

28、 2*/ if(List Left 0 )/* 3*/ return List Left ; else/* 4*/ return 0;/* 5*/ Center = ( Left + Right ) / 2;/* 6*/ MaxLeftSum = DivideAndConquer (List, Left, Center );/* 7*/ MaxRightSum = DivideAndConquer (List, Center + 1, Right );Algorithm 3/* 8*/ MaxLeftBorderSum = 0; LeftBorderSum = 0;/* 9*/ for( i

29、= Center; i = Left; i- ) /*10*/ LeftBorderSum += List i ;/*11*/ if( LeftBorderSum MaxLeftBorderSum )/*12*/ MaxLeftBorderSum = LeftBorderSum; /*13*/ MaxRightBorderSum = 0; RightBorderSum = 0;/*14*/ for( i = Center + 1; i MaxRightBorderSum )/*17*/ MaxRightBorderSum = RightBorderSum; /*18*/ return Max3( MaxLeftSum, MaxRightSum,/*19*/ MaxLeftBorderSum + MaxRightBorderSum );int MaxSubseqSum3(int List , int N ) return DivideAndConquer (List, 0, N - 1 ); Algorithm 3该算法的核