<4D F736F F F696E74202D20536C FB5DAD2BBD5C220D0F7C2DBA3A831A3A92E BBCE6C8DDC4A3CABD5D>

Size: px

Start display at page:

Download "<4D F736F F F696E74202D20536C FB5DAD2BBD5C220D0F7C2DBA3A831A3A92E BBCE6C8DDC4A3CABD5D>"

臻罐庾
7 years ago
Views:

1 数据结构基础 FUNDAMENTALS OF DATA STRUCTURE 耿新学年第 2 学期

2 课程的主要内容数据结构和算法基础本质 : 如何用计算机高效地解决问题先修课程高等数学离散数学程序设计参考教材数据结构 ( 用面向对象方法与 C++ 描述 ) 清华大学出版社, 殷人昆主编 Fundamentals of Data Structures in C++ Ellis Horowitz, Sartaj Sahni, Dinesh P. Mehta

3 其他学时分配 : 成绩评定 : 平时 (10%) 实验/ 作业 (15%) 期中考试(35%) 及期末考试 (40%) 联系方式 :xgeng@seu.edu.cn 课件和作业 :

4 一基本概念

5 发展史 1 数据结构作为一门独立的课程在国外是从 1968 年才开始设立的年美国 Donald E. Knuth( 高德纳 ) 教授开创了数据结构的最初体系 3 计算机程序设计技巧第一卷基本算法 ( The Art Of Computer Programming - Vol.1 - Fundamental Algorithms) 是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作

6 地位 1 数据结构在计算机科学及其相关专业中是一门综合性的专业基础课 2 数据结构是介于数学计算机硬件和计算机软件三者之间的一门核心课程 3 数据结构是研究和解决非数值计算问题的重要基础理论, 因此也是软件系统设计与实现的重要基础

7 计算机解决具体问题时, 一般经过下列几个步骤 : 首先要对具体问题进行分析, 从中进行模型抽象, 然后设计算法, 最后编出程序进行测试调整直至得到最终解答问题分析模型抽象算法设计编程调试得到解答

8 计算机程序是用于对信息进行加工处理的一般而言, 这些信息并不是没有组织的, 信息之间往往具有重要的结构关系, 这就是数据结构需要研究的内容计算机算法与数据的结构密切相关, 算法无不依附于具体的数据结构, 数据结构直接关系到算法的选择和效率 Niklaus Wirth: Algorithm + Data Structures = Programs

9 概括地说, 数据结构研究的是描述现实世界实体的数学模型 ( 非数值计算 ) 及其上的操作在计算机中如何表示和实现

10 [ 例 1-1] 电话号码查询问题方法 1: 顺序存储, 顺序查找 ((a 1,b 1 ), (a 2,b 2 ), (a 3,b 3 ),, (a n,b n )) 姓名电话号码 a 1 b 1 a 2 b 2 a n b n 问题 : 效率低

11 方法 2: 有序顺序存储, 二分查找 ( 李 1, a 1 ), ( 李 2, a 2 ),, ( 王 1, a i ), ( 王 2, a i+1 ), ) 姓名电话号码李 1 a 1 李 2 a 2 王 1 a i 王 2 a i+1 张 1 问题 : 修改不方便 a k 张 2 a k+1

12 方法 3: 部分有序, 建立索引表李 1 a 1 李 2 a 2 姓李地址张 1 a k 张 2 a k+1 王王 1 a i 张王 2 a i+1

13 [ 例 1-2] 文件系统的组织 (UNIX 为例 )

14 [ 例 1-3] 计算机和人对弈

15 [ 例 1-4] 交叉路口的交通灯管理问题 1 有连线的顶点用不同的颜色标记, 表示不能同时通行 ; 2 要求使用的颜色尽可能少, 以减少等待时间 ; 3 图论中的着色问题

16 [ 例 1-5] 田径赛的时间安排问题姓名项目 1 项目 2 项目 3 丁 1 跳高跳远 100M 跳高跳远马 2 标枪铅球张 3 标枪 100M 200M 200 M 100 M 李 4 铅球 200M 跳高王 5 跳远 200M 铅球标枪 1 任一选手所选中的项目之间应该两两有边相连 ; 2 任一两个有边相连的顶点颜色 ( 时间 ) 不能相同

17 数据结构研究的具体内容数据结构研究的是计算机所处理的数据元素之间的结构关系及其操作实现的算法一个具体问题的逻辑数据结构是什么? 适宜选用什么样的存储结构? 采用什么样的操作实现算法?

18 数据结构 (data structure) 具体来说, 数据结构包含三个方面的内容 : (1) 逻辑结构一个数据结构是由数据元素依据某种逻辑联系组织起来的对数据元素间逻辑关系的描述称为数据的逻辑结构 (2) 物理结构 ( 存储结构 ) 数据必须在计算机内存储, 数据的存储结构是数据结构的实现形式, 是其在计算机内的表示 (3) 运算此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义

19 对每一个数据结构而言, 必定存在与它密切相关的一组操作若操作的种类和数目不同, 即使逻辑结构相同, 数据结构能起的作用也不同不同的数据结构其操作集不同, 但下列操作必不可缺结构的生成 ; 结构的销毁 ; 在结构中查找满足规定条件的数据元素 ; 在结构中插入新的数据元素 ; 删除结构中已经存在的数据元素 ; 遍历

20 基本概念和术语数据 : 数据是信息的载体, 是描述客观事物的数字符以及所有能输入到计算机中被计算机程序识别和处理的符号的集合例如 : 数字字母汉字图形图像声音都称为数据数值型数据非数值型数据数据元素 ( 示例样本 ): 数据元素是组成数据的基本单位, 在计算机中作为一个整体进行考虑和处理数据元素是一个数据整体中相对独立的单位, 但它还可以分割成若干个具有不同属性的项 ( 数据项或字段 ), 故不是组成数据的最小单位

21 基本概念和术语 ( 续 ) 数据项 ( 属性特征 ): 具有独立含义的最小标识单位, 用于组成数据元素 ( 初等项组合项 ) 姓名学号性别班号出生日期入学成绩年月日关键字 : 指的是能识别一个或多个数据元素的数据项若能起唯一识别作用, 则称之为主关键字, 否则称之为次关键字

22 基本概念和术语 ( 续 ) 数据对象 : 具有相同性质的数据成员 ( 数据元素 ) 的集合, 是数据的子集如 : 整数实数等整数数据对象 N = { 0, 1, 2, } 学生数据对象 : 初等项 ( 不可分割 ) 组合项 ( 可再划分 ) 数据类型 : 具有相同性质的计算机数据集合 ( 值的集合 ) 及在这个集合上的一组操作例如, 高级语言中用到的整数数据类型, 是指由到中值构成的集合及一组操作 ( 加减乘除乘方等 ) 的总称

23 基本概念和术语 ( 续 ) 抽象数据类型 (ADT): 由一组数据结构和在该组数据结构上的一组操作所组成抽象数据类型的格式定义 : ADT Name Data 构造该抽象数据类型所必须的基本数据项 Operation 构造函数 End ADT Name

24 基本概念和术语 ( 续 ) ADT 有两个重要特征 : 数据抽象用 ADT 描述程序处理的实体时, 强调的是其本质的特征其所能完成的功能以及它和外部用户的接口 ( 即外界使用它的方法 ) 数据封装将实体的外部特性和其内部实现细节分离, 并且对外部用户隐藏其内部实现细节抽象数据类型可用 (D,R,P) 三元组表示其中,D 是数据对象,R 是 D 上的关系集,P 是对 D 的基本操作集

25 数据逻辑结构是对数据元素之间存在的逻辑关系的描述, 它可以用一个数据元素的集合和定义在此集合上的若干关系表示集合线性结构元素之间为一对一的线性关系, 第一个元素无直接前驱, 最后一个元素无直接后继, 其余元素都有一个直接前驱和直接后继 ( 表串栈队列 )

26 非线性结构元素之间为一对多或多对多的非线性关系, 每个元素有多个直接前驱或多个直接后继 ( 树图 )

27 数据的物理结构逻辑结构在计算机存储器中的实现, 故又称数据 " 存储结构 " (1) 顺序 ( 向量 ) 所有元素存放在一片连续的存贮单元中, 逻辑上相邻的元素存放到计算机内存仍然相邻 (2) 链式所有元素存放在可以不连续的存贮单元中, 但元素之间的关系可以通过地址确定, 逻辑上相邻的元素存放到计算机内存后不一定是相邻的

28 数据的物理结构 ( 续 ) (3) 索引存放元素的同时, 还建立附加的索引表, 索引表中的每一项称为索引项, 索引项的一般形式是 :( 关键字, 地址 ), 其中的关键字是能唯一标识一个结点的那些数据项 (4) 散列通过构造散列函数, 用函数的值来确定元素存放的地址

29 小结数据结构逻辑结构存储结构运算 ( 操作 ) 线性结构非线性结构集合顺序存储链接存储索引存储散列存储

30 二算法及其分析

31 什么是算法? 顾名思义, 算法就是计算的办法或法则这里的计算不只是加减乘除, 而是广义的做任何事情的计算, 而办法和法则意味着使用它就可以解决需要解决的问题

32 算法的定义算法通常被定义为一个有穷的指令集, 这些指令为解决某一特定问题规定了一个运算序列 ( 算法是一个定义良好的计算过程, 这个过程以一组值作为输入, 同时, 以一组值作为输出因此, 算法可以看成是将输入转换为输出的一个计算步骤的序列 )

33 算法的范畴一般包含两方面内容 : 算法设计与算法分析前者指根据实际问题制定出有效的算法 ; 后者即是对算法的各种性质进行定性或定量分析从而能够择优选择某种算法

34 算法是对问题求解过程的一种描述, 是为解决一个或一类问题给出的一个确定的有限长的操作序列严格说来, 一个算法必须满足以下五个重要特性 : ( 1 ) 输入作为算法加工对象的量值, 通常体现为算法中的一组变量但有些算法的字面上可以没有输入, 实际上已被嵌入算法之中 ( 2 ) 输出它是一组与输入有确定关系的量值, 是算法进行信息加工后得到的结果, 这种确定关系即为算法的功能

35 ( 3 ) 确定性对于每种情况下所应执行的操作, 在算法中都有确切的规定, 使算法的执行者或阅读者都能明确其含义及如何执行 ( 4 ) 有穷性对于任意一组合法的输入值, 在执行有穷步骤之后一定能结束 ( 5 ) 有效性 ( 可行性 ) 算法中的所有操作都必须足够基本, 都可以通过已经实现的基本操作运算有限次实现之算法的描述 : 自然语言伪码 (pseudo code) 公式图形表格程序设计语言

36 算法设计的要求 ( 1 ) 正确性 a. 程序中不含语法错误 ; b. 对多个输入能达到满足要求的结果 ; c. 对特定 ( 典型苛刻刁难性 ) 的输入能得到满足要求的结果 ; d. 对一切合法的输入都能得到满足要求的结果 ( 2 ) 可读性易于理解, 便于调试 ( 编程和调试维护分开 ) ( 3 ) 健壮性输入非法数据时, 作出恰当反应或相应处理 ( 4 ) 高效性

37 为什么学习算法? 算法是计算机的灵魂算法是数学机械化的一部分, 能够帮助我们解决复杂的计算问题算法作为一种思想, 能锻炼我们的思维, 使思维变得更清晰更有逻辑性算法还能帮助人们理解什么是可行的, 什么是不可行的最重要的, 算法本身很有意思, 很有趣味

38 算法设计的设计过程方法 : 自顶向下, 逐步求精过程 : 把一个具体问题的解决思路转变成一个算法

39 [ 例 1-6] 选择排序问题 Scanning direction

40 明确问题 : 非递减排序解决方案 : 逐个选择最小数据算法框架 : for ( int i=0; i<n-1; i++ ) { //n-1 趟从 a[i] 检查到 a[n-1]; 若最小的整数在 a[k], 交换 a[i] 与 a[k]; } 细化程序 : 程序 SelectSort

41 void sort(int *a, const int n) // sort the n integers a[0] to a[n-1] into // nondecreasing order { for(inti=0;i<n-1;i++) { int j = i; //find smallest integer in a[i] to a[n-1] for (int k = i+1; k < n; k++) if (a[k] < a[j]) j = k; int temp = a[i]; a[i] = a[j]; a[j] = temp ; //interchange } } Program Selection sort

42 [ 例 1-7] 二分查找明确问题 : 假定有 n 1 个不同的整数已经按从小到大的顺序存放在数组元素 a[0],,a[n-1] 中我们需要做的是判断整数 x 是否存放在某个数组元素中, 如果是, 即 x=a[j], 则返回 j( 被找到元素的下标 ); 否则返回 -1

43 解决方案 : 确定搜索区间的左右边界 left 和 right, 不断缩小搜索的区间初始边界设定为 left = 0 和 right = n-1 令 middle = (left + right)/2 为搜索区间的中心位置元素如果我们将 a[middle] 与 x 比较, 其结果有三种可能 : 1. x<a[middle] 以 middle 左半部分作为搜索区间, 继续搜索 ; 2. x=a[middle] 找到存放 x 的位置, 返回 middle; 3. x>a[middle] 以 middle 右半部分作为搜索区间, 继续搜索算法有两个任务 :1. 决定搜索区间 ;2. 将 x 与中间元素 a[middle] 比较

44 int BinarySearch(int *a, const int x, const int n) //Search the sorted array a[0],,a[n-1] for x { for ( initialize left and right; while there are more elements;){ let middle be the middle element; switch (compare(x, a[middle])){ case > : set left to middle +1;break; case < : set right to middle 1;break; case = : found x; } // end of switch }//endoffor not found; } // end of BinarySearch Program Algorithm for binary search

45 int BinarySearch(int *a, const int x, const int n) //Search the sorted array a[0],,a[n-1] for x { for(int left =0,right = n 1; left <= right;){ // while more elements int middle = (left + right)/2; switch(compare(x, a[middle])){ case > : left = middle +1;break;//x>a[middle] case < : right = middle 1;break;//x<a[middle] case = : return middle; // found x, x == a[middle] } // end of switch }//endoffor return 1; // not found } // end of BinarySearch Program: C++ function for binary search

46 算法和程序的区别 ( 1 ) 表现形式不同 ( 2 ) 是否具备有穷性实现数据结构操作的程序总是可结束的, 因此, 后面将不再严格区分算法和程序这两个术语

47 递归算法概念 : 对数据对象而言 : 若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的 ; 对算法而言 : 若一个算法直接地或间接地调用自己, 则称这个算法是递归的算法一个递归的算法一般包含两个部分 : 一个基本部分 ( 不需要递归就可以解决问题 ) 和一个一次或多次递归调用自己的部分递归调用自己的部分解决与原问题具有相同属性特征的问题, 只是问题的规模变小了递归算法的基本思想就是分而治之

48 递归算法有四个特性 : (1) 必须有可最终达到的终止条件, 否则程序将陷入无穷递归 ; (2) 子问题在规模上比原问题小, 或更接近终止条件 ; (3) 子问题可通过再次递归调用求解或因满足终止条件而直接求解 ( 原问题和其子问题采用同样的方法求解 ); (4) 子问题的解应能组合为整个问题的解

49 在解决以下三类问题时, 常常需要用到递归算法 1 定义是递归的 [ 例 1-8] 求阶乘 n! 1 n ( n 1)! 当 n 当 n 1 1 long Factorial ( long n ) { if ( n = = 1 ) return 1; else return n*factorial ( n-1); } // 终止条件 // 递归步骤

50 用参数 n = 5 调用 Fact 的过程如下 : Fact(5) = (5* Fact (4)) = (5* (4* Fact (3))) = (5* (4* (3* Fact (2)))) = (5* (4* (3* (2* Fact (1))))) = (5* (4* (3* (2* 1)))) = (5* (4* (3* 2))) = (5* (4* 6)) = (5* 24) = 120

51 采用递归的算法求解阶乘问题似乎并不能够充分说明其必要性, 因为用迭代的算法同样可以简单地解决同一问题 long Factorial(long n){ int s=1; for (int i=1; i<=n; i++) s = s * i; return s; }

52 不过, 下面的例子可以说明与迭代算法相比较, 在解决某些问题时, 递归算法具有优越性 [ 例 1-9] 求斐波那契数列 long Fib(long n){ if (n<=1) return n; // base case else return Fib(n-1)+Fib(n-2); // recursive call for n > 1 }

53 3 f(4) 2 f(3) f(2) 1 1f(2) f(1) 1 f(1) 1 f(0) 0 1 f(1) f(0) 0 用迭代的方式求解???

54 用迭代的方式求解 long Fib(long n){ if (n<=1) return n; else { long twoback = 0, oneback = 1, Current; for (i=2; i<=n; i++) { Current = twoback + oneback; twoback = oneback; oneback = Current; } return Current; } }

55 2 数据结构是递归的 3 问题的解法是递归的 [ 例 1-10] 求解汉诺塔 (tower of hanoi) 问题限制条件 : 一次只能移动一个金盘, 移动过程中大金盘不能放在小金盘上面解法, 将移动 n 个盘子的汉诺塔问题归结为移动 (n-1) 个盘子的汉诺塔问题以此类推, 移动 (n-1) 个盘子的汉诺塔问题又可归结为移动 (n-2) 个盘子的汉诺塔问题,, 最后总可以归结到只移动一个盘子的汉诺塔, 这样问题就解决了

56 Example: the recursive Towers of Hanoi algorithm Void TOH(int n, start, goal, temp) { if (n == 0 ) return; // base case TOH(n-1, start, temp, goal); // recursive call MOVE(start, goal); // move one disk TOH(n-1, temp, goal, start); // recursive call }

57 许多数据结构是自然递归的 ( 可以递归定义 ), 这样, 在这类数据结构上的操作也常常表现为递归算法此外, 许多排序和查找算法也是基于分而治之思想, 即其解决方案是将问题分解为更小 ( 但与原问题是类似的 ) 子问题先解决子问题, 然后将子问题的解决方案合并为原问题的解决方案

58 递归算法的特点 : 易编程可读性好易检验效率低保证其效率的前提是 : 不重复求解子问题

59 [ 例 1-11] 递归的二分查找 int BinarySearch(int *a, const int x, const int left, const int right) //Search the sorted array a[left],,a[right] for x { if(left <= right){ int middle = (left + right)/2; switch(compare(x, a[middle])){ case > : return BinarySearch(a, x, middle +1,right); // x > a[middle] case < : return BinarySearch(a, x, left, middle -1); // x < a[middle] case = : return middle;//x==a[middle] }//endofswitch }//endofif return 1; // not found } // end of BinarySearch Program: Recursive implement of binary search

60 [ 例 1-12] 全排列生成器给定 n 1 个元素的集合, 输出这个集合中所有元素的排列例如 : 如果集合是 {a, b, c}, 那么, 这个集合元素的全排列为 :{(a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a)}

61 容易看出, 如果给定的集合中有 n 个元素, 那么就有 n! 个不同的排列通过下面的例子可以看出算法的简单思路 : 集合有四个元素,(a,b,c,d), 答案可以这样构造 : 1. a 后接 (b, c, d) 的排列 2. b 后接 (a, c, d) 的排列 3. c 后接 (a,b,d) 的排列 3. d 后接 (a, b, c) 的排列可见, 如果能生成 n 1 个元素的全排列, 就能生成 n 个元素的全排列

62 设定 3 个参数, 分别是存放元素的数组参与排列的第一个元素的位置以及数组中元素的个数 : perm(a, k, n), 初始时调用参数 :A,0,n void perm (char *A, const int k,const int n) { // n 是数组 A 的元素个数, 生成 A[k],, A[n-1] 的全排列 int i; if (k = = n-1) { // 终止条件, 输出排列 for ( i=0; i<n; i++) cout << A[i] << ; // 输出包括前 // 缀, 以构成整个问题的解 cout << endl; }

63 else { // k 不是最后一个元素, 递归生成 A[k],, A[n-1] 的排列 for ( i = k; i < n; i++) { char temp = A[k]; A[k] = A[i]; A[i] = temp; // 交换 A[k] 和 A[i] perm(a, k+1, n); // 生成 a[k+1],,a[n-1] 的全排列 temp = A[k]; A[k] = A[i]; A[i] = temp; // 再次交换 A[k] 和 A[i], 恢复原顺序 } } // else 结束 } // perm 结束

64 当 n=4,a[4]={a, b, c, d} 时,perm(char *a, 0, 4) 调用的循环部分为 : for i = 0 to 3 { 交换位置为 0 和 i 的元素 ; k=k+1, 递归调用 perm 函数 ; 交换位置为 i 和 0 的元素 ;} 循环交换数组 A 的内容递归调用 i=0 0-0 (a, b, c, d) Perm(A, 1, 3) 计算 (b, c, d) 的全排列 i=1 0-1 (b, a, c, d) Perm(A, 1, 3) 计算 (a, c, d) 的全排列 i=2 0-2 (c, b, a, d) Perm(A, 1, 3) 计算 (b, a, d) 的全排列 i=3 0-3 (d, b, c, a ) Perm(A, 1, 3) 计算 (b, c, a) 的全排列

65 用 n=3 和 A[3]=(a, b, c) 调用 perm 的示意如下 :

66 小结算法的定义算法的特性输入输出确定性有穷性有效性算法设计的要求正确性可读性健壮性高效性算法实例选择排序二分查找递归算法

C++ 程序设计告别 OJ1 - 参考答案 MASTER 2019 年 5 月 3 日 1

C++ 程序设计告别 OJ1 - 参考答案 MASTER 2019 年 5 月 3 日 1 C++ 程序设计告别 OJ1 - 参考答案 MASTER 2019 年月 3 日 1 1 INPUTOUTPUT 1 InputOutput 题目描述用 cin 输入你的姓名 ( 没有空格 ) 和年龄 ( 整数 ), 并用 cout 输出输入输出符合以下范例输入 master 999 输出 I am master, 999 years old. 注意 "," 后面有一个空格,"." 结束,