1.1 数据结构讨论的范畴 1.2 基本概念 1.3 算法和算法的量度.

Presentation on theme: "1.1 数据结构讨论的范畴 1.2 基本概念 1.3 算法和算法的量度."— Presentation transcript:

1 1.1 数据结构讨论的范畴 1.2 基本概念 1.3 算法和算法的量度

2 1.1 数据结构讨论的范畴 Niklaus Wirth： Algorithm + Data Structures = Programs
程序设计: 算法: 数据结构: 为计算机处理问题编制 一组指令集 处理问题的策略 问题的数学模型

3 例如: 数值计算的程序设计问题 结构静力分析计算 ─━ 线性代数方程组 全球天气预报 ─━ 环流模式方程 (球面坐标系)

4 非数值计算的程序设计问题 例一: 求一组(n个)整数中的最大值 算法: ? 模型：？ 基本操作是“比较两个数的大小” 取决于整数值的范围

5 例二：计算机对弈 算法：? 模型：? 对弈的规则和策略 棋盘及棋盘的格局

6 例三：足协的数据库管理 需要管理的项目？ 如何管理？ 用户界面？ 算法：? 模型：? 各种表格

7 概括地说： 数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。

8 1.2 基本概念 一、数据与数据结构 二、数据类型 三、抽象数据类型

9 一、数据与数据结构 数据: 所有能被输入到计算机中，且能被计算机处理的符号的集合。 是计算机操作的对象的总称。
是计算机处理的信息的某种特定的符号表示形式。

10 数据元素: 是数据（集合）中的一个“个体” 是数据结构中讨论的基本单位

11 数据项： 是数据结构中讨论的最小单位 数据元素可以是数据项的集合 例如： 描述一个运动员的数据元素可以是 称之为组合项

12 数据结构： 带结构的数据元素的集合 ≠ 则在数据元素 a1、a2 和 a3 之间存在着“次序”关系 a1,a2、a2,a3
假设用三个 4 位的十进制数表示一个含 12 位数的十进制数。 例如: 3214,6587,9345 ─ a1(3214),a2(6587),a3(9345) 则在数据元素 a1、a2 和 a3 之间存在着“次序”关系 a1,a2、a2,a3 ≠ 3214，6587，9345 a a a3 6587，3214，9345 a a a3

13 数据结构： 带结构的数据元素的集合 行的次序关系: 列的次序关系: a1 a3 a5 a2 a4 a6 a1 a2 a3 a4 a5 a6
中六个元素之间 存在两个关系: 行的次序关系: 列的次序关系: row = {<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>} col = {<a1,a4>,<a2,a5>,<a3,a6>} a1 a3 a5 a2 a4 a6 a1 a2 a3 a4 a5 a6

14 {<ai, ai+1>| i=1, 2, 3, 4, 5} 数据结构： 带结构的数据元素的集合
再例，在一维数组 {a1, a2, a3, a4, a5, a6} 的数据元素之间存在如下的次序关系: {<ai, ai+1>| i=1, 2, 3, 4, 5} 可见，不同的“关系”构成不同的“结构” 或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。

15 数据的逻辑结构可归结为以下四类: 线性结构 树形结构 图状结构 集合结构

16 Data_Structures = (D, S)
数据结构的形式定义为: 数据结构是一个二元组 Data_Structures = (D, S) 其中:D 是数据元素的有限集， S 是 D上关系的有限集。

17 数据的存储结构 —— 逻辑结构在存储器中的映象 “数据元素”的映象 ？ “关系”的映象 ？

18 数据元素的映象方法： 用二进制位(bit)的位串表示数据元素 (321)10 = (501)8 = (101000001)2
(321)10 = (501)8 = ( )2 A = (101)8 = ( )2

19 x y 关系的映象方法： （表示x, y的方法） 顺序映象 以相对的存储位置表示后继关系
例如:令 y 的存储位置和 x 的存储位置之间差一个常量 C 而 C 是一个隐含值，整个存储结构中只含数据元素本身的信息 x y

20 链式映象 以附加信息(指针)表示后继关系 需要用一个和 x 在一起的附加信息指示 y 的存储位置 y x

21 在不同的编程环境中， 存储结构可有不同的描述方法。 当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。

22 typedef int Long_int [3]
例如: 以三个带有次序关系的整数表示一个长整数时，可利用 C 语言中提供的整数数组类型。 定义长整数为: typedef int Long_int [3]

23 二、数据类型 在用高级程序语言编写的程序中， 必须对程序中出现的每个变量、 常量或表达式，明确说明它们所 属的数据类型。

24 例如，C 语言中提供的基本数据类型有: 整型 int 浮点型 float 实型（ C++语言） 双精度型 double 字符型 char 逻辑型 bool （ C++语言）

25 不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。
数据类型 是一个 值的集合 和定义在此集合上的 一组操作 的总称。

26 是指一个数学模型以及定义在此数学模型上的一组操作。
三、抽象数据类型 (Abstract Data Type 简称ADT) 是指一个数学模型以及定义在此数学模型上的一组操作。

27 例如，抽象数据类型复数的定义： ADT Complex { 数据对象： D＝{e1,e2｜e1,e2∈RealSet } 数据关系：
R1＝{<e1,e2> | e1是复数的实数部分 | e2 是复数的虚数部分 }

28 AssignComplex( &Z, v1, v2 ) 基本操作： 操作结果：构造复数 Z,其实部和虚部
DestroyComplex( &Z) 操作结果：复数Z被销毁。 GetReal( Z, &realPart ) 初始条件：复数已存在。 操作结果：用realPart返回复数Z的实部值。

29 GetImag( Z, &ImagPart ) } ADT Complex 初始条件：复数已存在。
操作结果：用ImagPart返回复数Z的虚部值。 Add( z1,z2, &sum ) 初始条件：z1, z2是复数。 操作结果：用sum返回两个复数z1, z2 的 和值。 } ADT Complex

30 假设:z1和z2是上述定义的复数 则 Add(z1, z2, z3) 操作的结果 即为用户企求的结果 z3 = z1 + z2

31 ADT 有两个重要特征: 数据抽象 用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。 将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。 数据封装

32 抽象数据类型的描述方法 其中：D 是数据对象； S 是 D 上的关系集； P 是对 D 的基本操作集。
抽象数据类型可用（D，S，P）三元组表示。 其中：D 是数据对象； S 是 D 上的关系集； P 是对 D 的基本操作集。

33 ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名 其中基本操作的定义格式为: 基本操作名（参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉

34 赋值参数 只为操作提供输入值。 引用参数 以&打头，除可提供输入值外， 还将返回操作结果。 初始条件 描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。 操作结果 说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。

35 抽象数据类型的表示和实现 抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。 例如，对以上定义的复数。

36 typedef struct { float realpart； float imagpart； }complex；
// -----存储结构的定义 typedef struct { float realpart； float imagpart； }complex； // -----基本操作的函数原型说明 void Assign( complex &Z, float realval, float imagval )； // 构造复数 Z,其实部和虚部分别被赋以参数 // realval 和 imagval 的值

37 float GetReal( cpmplex Z )；
float Getimag( cpmplex Z )； // 返回复数 Z 的虚部值 void add( complex z1, complex z2, complex &sum )； // 以 sum 返回两个复数 z1, z2 的和

38 { 其它省略 } // -----基本操作的实现 void add( complex z1, complex z2,
complex &sum ) { // 以 sum 返回两个复数 z1, z2 的和 sum.realpart = z1.realpart + z2.realpart; sum.imagpart = z1.imagpart + z2.imagpart; } { 其它省略 }

39 1.3 算法和算法的衡量 一、算法 二、算法设计的原则 三、算法效率的衡量方法和准则 四、算法的存储空间需求

40 一、算法 算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性： 1．有穷性 2．确定性 3．可行性 4．有输入 5．有输出

41 1．有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：
算法中的每个步骤都能在有限时间内完成。 2．确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。

42 3．可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。
4．有输入 作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。

43 5．有输出 它是一组与“输入”有确 定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。

44 二、算法设计的原则 设计算法时，通常应考虑达到以下目标： 1．正确性 2. 可读性 3．健壮性 4．高效率与低存储量需求

45 1．正确性 首先，算法应当满足以特定的“规格说明”方式给出的需求。 其次，对算法是否“正确”的理解可以有以下四个层次：
a．程序中不含语法错误； b．程序对于几组输入数据能够得出满足要求的结果；

46 通常以第 c 层意义的正确性作为衡量一个算法是否合格的标准。
d．程序对于一切合法的输入数据都能得出满足要求的结果； 通常以第 c 层意义的正确性作为衡量一个算法是否合格的标准。

47 2. 可读性 算法主要是为了人的阅读与交流， 其次才是为计算机执行，因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。

48 3．健壮性 当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。

49 4．高效率与低存储量需求 通常，效率指的是算法执行时间； 存储量指的是算法执行过程中所需的 最大存储空间，两者都与问题的规模 有关。

50 三、算法效率的 衡量方法和准则 通常有两种衡量算法效率的方法: 事后统计法 缺点：1．必须执行程序 2．其它因素掩盖算法本质 事前分析估算法

51 和算法执行时间相关的因素： 1．算法选用的策略 2．问题的规模 3．编写程序的语言 4．编译程序产生的机器代码的质量
5．计算机执行指令的速度

52 一个特定算法的“运行工作量” 的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。

53 T (n) = O(f(n)) 假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，则可记作：

54 如何估算 算法的时间复杂度？

55 算法的执行时间 = 算法的执行时间 与 原操作执行次数之和 成正比 算法 = 控制结构 + 原操作 （固有数据类型的操作）
原操作(i)的执行次数×原操作(i)的执行时间 算法的执行时间 与 原操作执行次数之和 成正比

56 从算法中选取一种对于所研究的问题来说是 基本操作 的原操作，以该基本操作 在算法中重复执行的次数 作为算法运行时间的衡量准则。

57 void mult(int a[], int b[], int& c[] ) { for (i=1; i<=n; ++i)
例 一 两 个 矩 阵 相 乘 void mult(int a[], int b[], int& c[] ) { // 以二维数组存储矩阵元素，c 为 a 和 b 的乘积 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] += a[i,k]*b[k,j]; } //for } //mult 基本操作: 乘法操作 时间复杂度: O(n3)

58 void select_sort(int& a[], int n) { // 将 a 中整数序列重新排列成自小至大有序的整数序列。
例 二 选 择 排 序 for ( i = 0; i< n-1; ++i ) { if ( j != i ) a[j] ←→ a[i] } j = i; // 选择第 i 个最小元素 for ( k = i+1; k < n; ++k ) if (a[k] < a[j] ) j = k; 基本操作: 比较(数据元素)操作 时间复杂度: O(n2)

59 基本操作: 赋值操作 时间复杂度: O(n2) 例 void bubble_sort(int& a[], int n) { 三
起 泡 排 序 void bubble_sort(int& a[], int n) { // 将 a 中整数序列重新排列成自小至大有序的整数序列。 for (i=n-1, change=TRUE; i>1 && change; --i) } // bubble_sort { change = FALSE; // change 为元素进行交换标志 for (j=0; j<i; ++j) if (a[j] > a[j+1]) { a[j] ←→ a[j+1]; change = TRUE ;} } // 一趟起泡 基本操作: 赋值操作 时间复杂度: O(n2)

60 算法的空间复杂度定义为: S(n) = O(g(n)) 四、算法的存储空间需求 表示随着问题规模 n 的增大， 算法运行所需存储量的增长率

61 算法的存储量包括: 1．输入数据所占空间 2．程序本身所占空间 3．辅助变量所占空间

62 若输入数据所占空间只取决于问题 若所需额外空间相对于输入数据量 本身，和算法无关，则只需要分析除 输入和程序之外的辅助变量所占额外 空间。
来说是常数，则称此算法为原地工作。 若所需存储量依赖于特定的输入， 则通常按最坏情况考虑。

63 本章学习要点 1. 熟悉各名词、术语的含义，掌握基本概念。 2. 理解算法五个要素的确切含义。
3. 掌握计算语句频度和估算算法时间复杂度的方法。