Microsoft PowerPoint - DS_Ch1.ppt [兼容模式]

Size: px

Start display at page:

Download "Microsoft PowerPoint - DS_Ch1.ppt [兼容模式]"

项穰戎
5 years ago
Views:

014/4/7 数据结构计算机学院肖明军 Email: xiaomj@ustc.edu.

c/~xiaomj 1 课程简介先修课程及条件程序设计的经验 C 离散数学概率分析教材 : 数据结构, 黄刘生, 经济科学出版社数据结构 (C 语言版 ), 严蔚敏,

1 绪论重要性人类社会已步入信息社会计算机不再仅仅局限于科学计算, 已深入到社会生活的各个领域给我一根杠杆, 我就能撬动地球给我一个接口, 我就能驱动地球 4

Wirth,84 年图灵奖得主 ) 两个问题 : 信息的表示和处理信息的表示和组织又直接关系到处理信息的程序的效率随着应用问题的不断复杂,

1 014/4/7 数据结构计算机学院肖明军课程简介先修课程及条件程序设计的经验 C 离散数学概率分析教材 : 数据结构, 黄刘生, 经济科学出版社数据结构 (C 语言版 ), 严蔚敏, 清华大学出版社考核 : 考试作业上机参考书 C 数据结构,William Ford 清华影印版数据结构和程序设计, Robert,Kruse.d 版 Ch.1 绪论重要性人类社会已步入信息社会计算机不再仅仅局限于科学计算, 已深入到社会生活的各个领域给我一根杠杆, 我就能撬动地球给我一个接口, 我就能驱动地球 4 Ch.1 绪论重要性计算机 : 硬件软件算法数据结构程序设计 (N.Wirth,84 年图灵奖得主 ) 两个问题 : 信息的表示和处理信息的表示和组织又直接关系到处理信息的程序的效率随着应用问题的不断复杂, 导致信息量剧增与信息范围的拓宽, 使许多系统程序和应用程序的规模很大, 结构又相当复杂因此, 必须分析待处理问题中的对象的特征及各对象之间存在的关系, 这就是数据结构这门课所要研究的问题 5 Ch.1 绪论编写解决实际问题的程序的一般过程 : 如何用数据形式描述问题? 即由问题抽象出一个适当的数学模型 ; 问题所涉及的数据量大小及数据之间的关系 ; 如何在计算机中存储数据及体现数据之间的关系? 处理问题时需要对数据作何种运算? 所编写的程序的性能是否良好? 上面所列举的问题基本上由数据结构这门课程来回答 6 1

014/4/7 例 1: 电话号码查询系统设有一个电话号码薄, 它记录了 N 个人的名字和其相应的电话号码, 假定按如下形式安排 :(a 1, b 1 ), (a, b ), (a, b ), 其中 a i, b i (i1, ) 分别表示某人的名字和电话号码本问题是一种典型的表格问题如表所示, 数据与数据成简单的一对一的线性关系姓名电话号码陈海 16145588 李四锋

数据与数据成多对多的关系, 是一种非线性关系结构佛山中山珠海广州网状结构东莞深圳惠州 9 数据 : 信息载体客观事物的符号表示, 能由计算机程序识别存储和加工处理的符号集合所有能够数字化的信息均可认为是数据数据元素 : 数据的基本单位, 在程序中通常作为一个整体来进行考虑和处理同义词 : 元素结点顶点记录对象元组等数据项 : 具有独立含义的最小标识单位,

2 014/4/7 例 1: 电话号码查询系统设有一个电话号码薄, 它记录了 N 个人的名字和其相应的电话号码, 假定按如下形式安排 :(a 1, b 1 ), (a, b ), (a, b ), 其中 a i, b i (i1, ) 分别表示某人的名字和电话号码本问题是一种典型的表格问题如表所示, 数据与数据成简单的一对一的线性关系姓名电话号码陈海李四锋例 : 磁盘目录文件系统磁盘根目录下有很多子目录及文件, 每个子目录里又可以包含多个子目录及文件, 但每个子目录只有一个父目录, 依此类推 : 本问题是一种典型的树型结构问题, 如图所示, 数据与数据成一对多的关系, 是一种典型的非线性关系结构树形结构线性表结构 7 树形结构 8 例 : 交通网络图从一个地方到另外一个地方可以有多条路径本问题是一种典型的网状结构问题, 数据与数据成多对多的关系, 是一种非线性关系结构佛山中山珠海广州网状结构东莞深圳惠州 9 数据 : 信息载体客观事物的符号表示, 能由计算机程序识别存储和加工处理的符号集合所有能够数字化的信息均可认为是数据数据元素 : 数据的基本单位, 在程序中通常作为一个整体来进行考虑和处理同义词 : 元素结点顶点记录对象元组等数据项 : 具有独立含义的最小标识单位, 客观事物某一方面特性的数据描述 10 同义词 : 字段域属性等数据结构 : 相互之间存在一种或多种特定关系的数据元素的集合, 即数据的组织形式数据的逻辑结构 : 数据元素之间的逻辑关系数据的存储结构 : 数据元素及其关系在计算机存储器内的表示数据的运算 : 对数据施加的操作 11 数据结构举例系别姓名职称 SCI EI 经费 1 张明教授王华教授 6 15 李立教授行 : 结点 ( 对象记录元组等 ); 列 : 数据项 ( 属性域字段等 ) 逻辑结构 : 开始结点? 终端结点? 内部结点? 结点之间的逻辑关系 : 有且仅有 1 个开始结点和 1 个终端结点, 表中任 1 结点最多只有 1 个直接前驱和 1 个直接后继线性关系存储结构 : 用数组实现, 还是用指针实现? 1 运算 : 创建插入删除查找等

3 014/4/7 逻辑结构线性结构 : 任一结点最多只有 1 个直接前驱和 1 个直接后继非线性结构 : 一结点可有多个直接前驱和多个直接后继集合结构 : 元素间无关系, 只有元素是否属于集合的关系存储结构 (1) 顺序存储方法逻辑上相邻的结点存储在物理位置上相邻的存储单元里结点间的逻辑关系由存储单元的邻接关系来体现借助于数组描述应用于线性的数据结构, 非线性的数据结构的线性化 1 存储结构 () 链接存储方法该方法不要求逻辑上相邻的结点在物理位置上亦相邻借助于指针来表示结点间的逻辑关系 () 索引存储方法在存储结点信息的同时, 建立附加的索引表表中每项称为索引项 ( 关键字, 地址 ) 稠密索引 : 每个结点对应 1 个索引项稀疏索引 : 一组结点对应 1 个索引项 (4) 散列存储方法根据结点的 Key 直接计算出该结点的存储地址 14 数据结构的主要运算 ⑴ 建立 (Create) 一个数据结构 ; ⑵ 消除 (Destroy) 一个数据结构 ; ⑶ 从一个数据结构中删除 (Delete) 一个数据元素 ; ⑷ 把一个数据元素插入 (Isert) 到一个数据结构中 ; ⑸ 对一个数据结构进行访问 (Access); ⑹ 对一个数据结构 ( 中的数据元素 ) 进行修改 (Modify); ⑺ 对一个数据结构进行排序 (Sort); ⑻ 对一个数据结构进行查找 (Search) 15 数据结构方面之联系同一逻辑结构的不同存储结构, 则用不同名称称谓例如, 线性表顺序表, 链表, 散列表运算不同, 称谓也不同线性表栈队列顺序栈顺序队列数据的逻辑结构和物理结构是密不可分的两个方面, 一个算法的设计取决于所选定的逻辑结构, 而算法的实现依赖于所采用的存储结构在 C 语言中, 用一维数组表示顺序存储结构 ; 用结 16 构体类型表示链式存储结构逻辑结构物理结构线性表顺序存储结构树链式存储结构图复合存储结构逻辑结构与所采用的存储结构数据的逻辑结构线性结构非线性结构受限线性表线性表推广集合树形结构图状结构数据类型 : 是一个值的集合以及定义在这些值上的一组操作的总称, 可看作是高级语言提供的数据结构原子类型 : 值不可分, 一般是基本的预定义类型 it,char 等, 定义了, - 等结构类型 : 可供用户定义的新类型, 构造类型导出类型派生类型等由基本类型组织而成, 如数组 struct 等一般线性表栈和队列串数组广义表一般树二叉树有向图无向图数据逻辑结构层次关系图 17 18

4 014/4/7 抽象数据类型 (Abstract Data Type) 抽象的数据组织和与之相关的操作, 可看作是数据的逻辑结构及其在逻辑结构上定义的抽象操作特点 1 封装与隐藏 : 将数据和操作封装在一起, 内部结构和实现细节对外屏蔽, 实现信息隐藏抽象 : 用户只能通过 ADT 里定义的接口和说明来访问和操作数据他反映了程序设计的两层抽象 : 概念层 ( 抽象 )---ADT 类说明实现层 --- 类实现, 相当于普通类型应用层 ---- 如 mai(){, 通过操作对象解决实际问题 19 抽象数据类型 (Abstract Data Type) ADT ADT_Name{ Data: 数据结构 ( 数据对象和数据关系 ) 说明 Operatios: Costructor:// 构造函数, 创建对象实例 Operatio1:// 用 C 或 C 函数原型描述 iput: Precoditios:// 初始条件, 执行本操作前系统 // 需满足的状态 process:// 对数据执行的操作 output:// 对返回数据的说明 Postcoditios:// 执行本操作后系统的状态 Operatio: 0 例 : 抽象数据类型复数的定义 ADT Complex { 数据对象 :D{e1,e e1,e RealSet 数据关系 :R1{<e1,e> e1 是复数的实数部分,e 是复数的虚数部分基本操作 : IitComplex( &Z, v1, v ) 操作结果 : 构造复数 Z, 其实部和虚部分别被赋以参数 v1 和 v 的值 DestroyComplex( &Z) 操作结果 : 复数 Z 被销毁 GetReal( Z, &realpart) 初始条件 : 复数已存在操作结果 : 用 realpart 返回复数 Z 的实部值 GetImag( Z, &ImagPart) 初始条件 : 复数已存在操作结果 : 用 ImagPart 返回复数 Z 的虚部值 Add( z1,z, &sum ) 初始条件 :z1, z 是复数操作结果 : 用 sum 返回两个复数 z1 z 的和值 ADT Complex 1 抽象数据类型的表示与实现通过程序设计语言中的类型来实现 C 抽象数据类型数据对象结构体基本操作函数 C,Java 抽象数据类型类 class 数据对象数据成员基本操作成员函数 ( 方法 ) ADT 复数的 C 描述 typedef struct { double realpart; double imagpart; Complex; boolea assig(complex *psrc, Complex *pdes){ if (psrc NULL pdesnull ) retur ERROR; pdes->realpart psrc->realpart; pdes->imagpart psrc->imagpart; retur TRUE; Complex *add(complex *pz1, Complex *pz){ Complex *psum (Complex *)malloc(sizeof(complex)); if ( psumnull )retur NULL; psum->realpart pz1->realpart pz->realpart; psum->imagpart pz1->imagpart pz->imagpart; retur psum; ADT 复数的 C 描述 class Complex{ // 类的声明 protected: double realpart; double magpart; public: Complex( ); Complex(double realval,double imagval); Complex(Complex& z){ assig(z) ; ~Complex( ); void assig(complex& z); double getreal(void) cost { retur realpart; double getimag(void) cost { retur imagpart; fried Complex add(complex& z1, Complex& z); ; 4 4

5 014/4/7 // 类的实现部分 Complex::Complex(double realval, double imagval){ realpart realval; imagpart imagval; void Complex::assig(Complex& z){ realpart z.realpart; imagpart z.imagpart; Complex add(complex& z1, Complex& z){ Complex sum(z1); sum.realpart z.realpart; sum.imagpart z.imagpart; retur sum; 5 1. 算法描述分析算法重要性 : 数据的运算是通过算法描述的定义 : 非形式地说, 算法是任意一个良定义的计算过程, 它以一个或多个值作为输入, 并产生一个或多个值作为输出因此, 一个算法就是一系列将输入转换为输出的计算步骤 5 要素输入输出有穷性 ( 有穷步骤, 每步时间有限 ) 确定性 ( 算法只有唯一执行路径 ) 可行性 ( 所有操作可通过已经实现的基本运算有限次实现之 ) 算法与程序的联系与区别 6 1. 算法描述分析输入实例一个问题的输入实例是由满足问题陈述中的限制并能计算出该问题解的所有输入构成的算法描述自然语言数学语言伪语言程序语言等均可本课程以 C 为主, 但不拘泥于细节算法评价正确性可读性健壮性时空性能 7 1. 算法描述分析算法分析算法效率的度量事后统计 : 利用计算机内部的计时功能缺陷必须先运行依据算法编制的程序时间统计量依赖于计算机的软硬件环境 double start, stop; time (&start); mai process(, ); time (&stop); double rutime stop -start; pritf ("%d%d\",, rutime ); 8 1. 算法描述分析事前分析估算 ( 时间 ) 求出该算法的一个时间界限函数一些影响因素 : 算法的策略问题的规模书写程序的语言编译器产生的机器代码的质量机器执行指令的速度 9 算法分析算法的时间是每语句执行时间的总和每语句的执行时间该语句执行次数 ( 频度 ) X 该语句执行 1 次的时间假定 : 每语句执行 1 次的时间为 1 个时间单位则 : 算法的执行时间各语句频度问题的规模 (Size) 输入量的大小, 如时间复杂度 : 算法的运行时间, 是问题规模的函数 0 5

6 014/4/7 时间复杂度例 1: 矩阵乘法 for ( i0; i<; i) //1 for ( j0; j<; j) { //(1) C[i] [j]0; // for ( k0;k<; k) // (1) C[i][j]C[i][j]A[i][k]*B[k][j]; // 详细分析 : T() 1 简单分析 : 频度最大的语句 T() 1 i 0 j 0 k 0 1 lim T ( ) / lim( 1) / 渐近时间复杂度 ( 简称时间复杂度 ) 从宏观上评价时间性能, 只关心当趋向无穷大时, T() 的数量级 ( 阶 ) lim lim T ( ) / ( 即 :T() 和同阶, 数量极相同记作 :T()O( ) 1 ) / 大 O 的数学定义若 T() 和 f() 是定义在正整数集合上的两个函数, 则 T()O(f()) 表示存在两个正的常数 c 和 0, 使得当 0 时都满足 0 T() c f() 例 for(i1; i<; i) { x; sx ; 语句频度为 :, 其时间复杂度为 :O(), 即为线性阶例 {x; s0 ; 将 x 自增看成是基本操作, 则语句频度为 1, 即时间复杂度为 O(1) 如果将 s0 也看成是基本操作, 则语句频度为, 其时间复杂度仍为 O(1), 即常量阶例 4 for(i1; i<; i) for(j1; j<; j) { x; sx ; 语句频度为 :, 其时间复杂度为 :O( ), 即为平方阶 4 定理 : 若 A()a m m a m-1 m-1 a 1 a 0 是一个 m 次多项式, 则 A()O( m ) 例 5 for(i;i<;i) for(j;j<i-1;j) {x; a[i,j]x; 语句频度为 :1 -(1-) (-)/ (-1)(-)/ - 时间复杂度为 O( ), 即此算法的时间复杂度为平方阶一个算法时间为 O(1) 的算法, 它的基本运算执行的次数是固定的因此, 总的时间由一个常数 ( 即零次多项式 ) 来限界而一个时间为 O( ) 的 5 算法则由一个二次多项式来限界以下六种计算算法时间的多项式是最常用的其关系为 : O(1)<O( log)<o()<o(log)<o( )<O( ) 指数时间的关系为 : O( )<O(!)<O( ) 当取得很大时, 指数时间算法和多项式时间算法在所需时间上非常悬殊因此, 只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法, 那就取得了一个伟大的成就有的情况下, 算法中基本操作重复执行的次数还随问题的输入数据集不同而不同 6 6

7 014/4/7 例 1: 素数的判断算法 Void prime( it ) /* 是一个正整数 */ { it i ; while ( (% i)!0 && i*1.0< sqrt() ) i ; if (i*1.0>sqrt() ) pritf( &d 是一个素数 \, ) ; else pritf( &d 不是一个素数 \, ) ; 嵌套的最深层语句是 i; 其频度由条件 ( (% i)!0 && i*1.0< sqrt() ) 决定, 显然 i*1.0< sqrt(), 时间复杂度 O( 1/ ) 7 例 : 冒泡排序法 Void bubble_sort(it a[],it ) { for (i-1, chageture; i>1 && chage; --i) chagefalse; for (j0; j<i; j) if (a[j]>a[j1]) { a[j] a[j1] ; chageture ; 最好情况 :0 次最坏情况 :1-1(-1)/ 平均时间复杂度为 : O( ) 8 空间复杂度 (Space complexity) : 是指算法编写成程序后, 在计算机中运行时所需存储空间大小的度量记作 : S()O(f()) 其中 : 为问题的规模 ( 或大小 ) 该存储空间一般包括三个方面 : 指令常数变量所占用的存储空间 ; 输入数据所占用的存储空间 ; 辅助 ( 存储 ) 空间一般地, 算法的空间复杂度指的是辅助空间一维数组 a[]: 空间复杂度 O() 二维数组 a[][m]: 空间复杂度 O(*m) 9 作业 1 数据的逻辑结构? 数据的物理结构? 逻辑结构与物理结构的区别和联系是什么? 分析以下程序段的时间复杂度, 请说明分析的理由或原因 ⑴ Sum1( it ) { it p1, sum0, m ; for (m1; m<; m) { p*m ; sump ; retur (sum) ; 40 ⑵ Sum( it ) { it sum0, m, t ; for (m1; m<; m) { p1 ; for (t1; t<m; t) p*t ; sump ; retur (sum) ; ⑶ 递归函数 fact( it ) { if (<1) retur(1) ; else retur( *fact(-1)) ; 41. 按增长率由小至大的顺序排列下列各函数 : 100, (/), (/),,,!, 4. 有时为了比较两个同数量级算法的优劣, 须突出主项的常数因子, 而将降低次项用大 O 记号表示例如, 设 T 1()1.9lg lgO(), T ().0lg-.0lgO(), 这两个式子表示, 当足够大时 T 1 () 优于 T (), 因为前者的常数因子小于后者请用此方法表示下列函数, 并指出当足够大时, 哪一个较优, 哪一个较劣? ⑴ T 1 ()5-60lg ⑵ T () 1000lg ⑶ T ()8 lg ⑷ T 4 () lg, lg, lg, / 4 7

Microsoft PowerPoint - DS_Ch1_EN [兼容模式]

Microsoft PowerPoint - DS_Ch1_EN [兼容模式] Data Structure Ch.1 Introduction Dr. He Emil Huang School of Computer Science and Technology Soochow University 与课本对应关系严蔚敏老师课本的第一章 Kruse 教材 P0 Chapter 7.6 Asymptotics 渐进 E-mail: huangh@suda.edu.cn http://home.ustc.edu.cn/~huang8/ds.html