《数据结构与算法分析》由会员分享，可在线阅读，更多相关《数据结构与算法分析（59页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法分析数据结构与算法分析( ( Data Structure and Algorithm AnalysisData Structure and Algorithm Analysis) )第一章 绪论n数据结构？n数据结构有几种？基本特征？n数据结构的相关的基本概念n在计算机内，基本的存贮结构n抽象数据类型ADTn算法及其度量什么是数据结构？计算机的应用范围扩大，已经从最初的科学计算发展到控制，管理，数据处理等非数值计算等方面。 科学计算：天气预报 控制：飞机，数控机床 数据处理：图象，语音 管理：数据库，办公自动化 计算机可以处理的信息多样化 数，字符串，语音图象等。 学生信息查询
2、系统中的数据结构 学号姓名性别 专 业年 级 980001吴承志男计算机科学与技术 98级 980002李淑芳女信息与计算科学 98级 990301刘 丽女数学与应用数学 99级 990302张会友男信息与计算科学 99级 990303石宝国男计算机科学与技术 99级 000801何文颖女计算机科学与技术 2000级 000802赵胜利男数学与应用数学 2000级 000803崔文靖男信息与计算科学 2000级 010601刘 丽女计算机科学与技术 2001级 010602魏永鸣男数学与应用数学 2001级学生信息查询系统中的数据结构 崔文靖8 何文颖6 李淑芳2 刘 丽3，9 石宝国5 魏永
3、鸣10 吴承志1 赵胜利7 张会友4计算机科学与技术 1，5，6，9 信息与计算科学 2，4，8 数学与应用数学 3，7，10 2000级 6，7，8 2001级 9，10 98级 1，2，3 99级 4，5 非数值计算的例子oooxxxoooxoox x ooxxxooxoooxxooo xxoooxxxoox ooxoo教学计划编排问题 课程编号课程名称先修课程 C1计算机导论无 C2数据结构C1，C4C3汇编语言C1 C4C程序设计语言C1 C5计算机图形学C2，C3，C4 C6接口技术C3 C7数据库原理C2，C9 C8编译原理C4 C9操作系统C2教学计划编排问题的数据结构数据结构定
4、义由以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。因此，可以说数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构历史n数据结构作为一门独立的课程在国外是从1968年才开始 的。n1968年美国唐.欧.克努特教授开创了数据结构的最初体 系，他所著的计算机程序设计技巧第一卷基本算法 是第一本较系统地阐述数据的逻辑结构和存储结构及其 操作的著作。n20世纪60年代末到70年代初，出现了大型程序，软件 也相对独立，结构程序设计成为程序设计方法学的主要内 容，人们越来越重视数据结构。从70年
5、代中期到80年代， 各种版本的数据结构著作相继出现。数据结构发展趋势n面向各专门领域中特殊问题的数据结构得到研究 和发展，如多维图形数据结构等；n从抽象数据类型和面向对象的观点来讨论数据结 构已成为一种新的趋势，越来越被人们所重视。 课程目的n 能够分析研究计算机加工的对象的特性，获得 其逻辑结构，根据需求，选择合适存贮结构及其 相应的算法； n 学习一些常用的算法； n 复杂程序设计的训练过程，要求编写的程序结 构清楚和正确易读； n 初步掌握算法的时间分析和空间分析技术；基本概念和术语n数据(Data)：客观事物在计算机中的符号表示 ，是能被计算机识别和处理的符号总称。n数据元素(Data
6、 Element)：数据的基本单位， 用于完整地描述一个对象;n数据项(Data Object)：组成数据元素的有特定 意义的最小单位 。n数据对象(Data Structure)：相同特性数据元素 的集合，是数据的一个子集合;基本概念和术语n数据结构：相互之间存在一种或多种特定关 系的数据元素的集合。集合：线性结构：树形结构：图状结构：n形式定义：Data_Structure=D,S，D是数据 元素的有限集，S是D上关系的有限集基本概念和术语n存贮结构（物理结构）：数据结构在计算机中的表 示（映象）。顺序存贮结构：借助元素在存贮器中的相对位置表 示数据元素之间的关系。非顺序（链式）存贮结构：
7、借助指示元素存贮地址 的指针（Pointer）表示数据元素之间的逻辑关系。n结点（Node）:数据元素n数据域（Data Field)：数据项基本概念和术语an-1a0a1a20x1000a0a2a3a10x10000x20000x3000基本概念和术语n抽象数据类型（Abstract Data Type）ADT: 一个数学模型以及定义在该模型上的一组操作 。 ADT 抽象数据类型名 数据对象：数据对象定义 数据关系：数据关系定义 基本操作：基本操作定义 ADT 抽象数据类型名ADT Format ADT_Name DataDescribe the structure of the dataO
8、perationsConstructorOperation1Operation2 抽象数据类型（ADT）ADT由一组数据结构和在该数据上的一组操 作所组成。一般数据类型由具体语言系统内部定义， ADT是由编程者定义。在定义ADT时，数据结构部分只要求定义逻 辑结构，操作部分只要求定义操作说明。ADT较一般的数据类型抽象层次更高，更能 为其它用户提供良好的使用接口。ADT在C+中的描述ADT在C+中通过类类型来描述。ADT的数据部分定义为类私有(private)或保 护(protected)的数据成员。ADT的操作部分定义为类的公共（public） 成员函数，并且只给出操作说明（即函数声明） 。
9、操作的具体实现是在一个单独文件中给出， 类的声明存放在一个专门的头文件中，使两者分 离开，体现面向对象的程序设计（OOP）思想算法和算法分析 n算法：是对特定问题求解步骤的一种描述 算法是指令的有限序列，其中每一条指令表示一 个或多个操作。 算法具有以下五个特性： （1）有穷性 一个算法必须总是在执行有穷步 之后结束，且每一步都在有穷时间内完成。 （2）确定性 算法中每一条指令必须有确切的含 义。不存在二义性。且算法只有一个入口和一个 出口。 （3）可行性 一个算法是可行的。即算法描述的 操作都是可以通过已经实现的基本运算执行有限 次来实现的。算法和算法分析4）输入 一个算法有零个或多个输入
10、，这些输入取自于某个特定的对象集 合。 5）输出 一个算法有一个或多个输出 ，这些输出是同输入有着某些特定关 系的量。算法和算法分析n算法设计的要求：正确性：Correctness可读性: Readability健壮性: Robustness效率与低存贮量要求算法的表示n自然语言表示法n流程图表示法nNS流程图表示法n伪代码表示法n计算机语言表示法算法示例我们采用伪代码来表示算法.例1:在一个有序序列中查找最大元素算法procedure max(a1, a2, , an: integers) max := a1 for i := 2 to n if max am then i := m + 1
11、 else j := m end if x = ai then location := i else location := 0 location is the subscript of the term that equals x, or is zero if x is not found算法示例显然,当线性表中数据有序时,折半查找的效率要比线性 查找的效率高。如何来分析算法的效率?算法效率n程序跑的更快：u事后统计：利用计算机的时钟；u事前分析估算：用高级语言编写的程序运行的时间 主要取决于如下因素：F算法；F问题规模；F使用语言：级别越高，效率越低；F编译程序；F机器；算法效率n特定算法
12、“运行工作量”的大小只依赖于问题的规 模（通常用整数n表示），或者说是问题规模的函 数。n算法主要由程序的控制结构（顺序，分支，循环 ）和原操作（必须的操作）构成，算法的时间主 要取决于两者。n算法度量：选取一种对于研究问题来说是基本操 作的原操作，以该基本操作重复执行的次数作为 算法的时间度量。 （其中程序的主要执行时间在：循环上。）算法时间函数级别（Order of an algorithm）设 f 和 g 是两个定义在正整数内的函数qf(n) = O(g(n): f(n) 的级别 最多是 g(n) qif there exists a positive constant C1 such
13、that |f(n)| C2|g(n)| for all but finitely many n qThis is known as the big omega notationqf(n) = (g(n): f(n)的级别 是 g(n) if f(n)= O(g(n) and f(n) = (g(n).qThis is known as the big theta notation运行时间计算n假设某一算法在问题规模为n时的运行时间如下 :t(n) = 5n3 + 3n + 7 该算法运行时间的级别是多少?n通常情况我们只关心算法运行时间的上限： O(g(n)。运行时间计算n我们很快能发现t(
14、n) = 5n3 + 3n + 7的级别是O(n3)。为什么?运行时间计算nt(n)= 5n3 + 3n + 7 5n310503750001005000307500000010005000003007500000000010,00050000000300075000000000000示例Lets know consider the previous example to determine the constants C1 and C2Recall: f(n) = O(g(n): f(n) is of order at most g(n) qif there exists a positiv
15、e constant C1 such that |f(n)| C2|g(n)| for all but finitely many n 示例qO(n): Since t(n) = 5n3 + 3n + 7 5n3 + 3n3 + 7n3 = 15 n3for n 1, we can make C1 = 15 to obtain5n3 + 3n + 7 = O(n3)q(n): Since t(n) = 5n3 + 3n + 7 5n3 = 5n3for n 1, we can make C2 = 5 to obtain5n3 + 3n + 7 = (n3)q(n): Since 5n3 + 3
16、n + 7 = O(n3) and 5n3 + 3n + 7 = (n3) we conclude that 5n3 + 3n + 7 = (n3)函数增长率p定理：若A(n)=a m n m +a m-1 n m-1 +a1n+a0是一个m次多项式，则：A(n)=O(n m) =(n m)= (n m) 证明（略）。增长函数n“Popular” functions g(n) arenn log n, 1, 2n, n2, n!, n, n3, log nnListed from slowest to fastest growth:n 1n log nn nn n log nn n2n n3n 2nn n!常见函数增长率常见函数增长率常见函数增长率常见函数增长率常见函数增长率算法效率的度量一般情况下，
