数 据 结 构 计 算 机 学 院 肖明军 Email: xiaomj@ustc.edu.cn http://staff.ustc.edu.cn/~xiaomj.

Presentation on theme: "数 据 结 构 计 算 机 学 院 肖明军 Email: xiaomj@ustc.edu.cn http://staff.ustc.edu.cn/~xiaomj."— Presentation transcript:

1 数 据 结 构 计 算 机 学 院 肖明军

2 课程简介 先修课程及条件 程序设计的经验、C、离散数学、概率分析 教材：数据结构，黄刘生，经济科学出版社
考核：考试+作业+上机 参考书 C++ 数据结构，William Ford 清华影印版 数据结构和程序设计， Robert,Kruse.2nd版

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

4

5 § Ch.1 绪论 重要性 计算机：硬件+软件 算法+数据结构=程序设计（N.Wirth,84年图灵奖得主） 两个问题：信息的表示和处理
信息的表示和组织又直接关系到处理信息的程序的效率。随着应用问题的不断复杂，导致信息量剧增与信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，必须分析待处理问题中的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。

6 § Ch.1 绪论 编写解决实际问题的程序的一般过程： 问题所涉及的数据量大小及数据之间的关系;
如何用数据形式描述问题?—即由问题抽象出一个适当的数学模型; 问题所涉及的数据量大小及数据之间的关系; 如何在计算机中存储数据及体现数据之间的关系? 处理问题时需要对数据作何种运算? 所编写的程序的性能是否良好? 上面所列举的问题基本上由数据结构这门课程来回答。

7 例1：电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1, b1)，(a2, b2)，…(an, bn)，其中ai, bi(i=1，2…n) 分别表示某人的名字和电话号码。 本问题是一种典型的表格问题。如表所示，数据与数据成简单的一对一的线性关系。 姓名 电话号码 陈海 李四锋 。。。 要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。 线性表结构 7

8 例2：磁盘目录文件系统 本问题是一种典型的树型结构问题，如图所示，数据与数据成一对多的关系，是一种典型的非线性关系结构—树形结构。
磁盘根目录下有很多子目录及文件，每个子目录里又可以包含多个子目录及文件，但每个子目录只有一个父目录，依此类推： 本问题是一种典型的树型结构问题，如图所示，数据与数据成一对多的关系，是一种典型的非线性关系结构—树形结构。 树形结构

9 例3：交通网络图 从一个地方到另外一个地方可以有多条路径。本问题是一种典型的网状结构问题，数据与数据成多对多的关系，是一种非线性关系结构。
佛山 惠州 广州 中山 东莞 深圳 珠海 网状结构 其他例子： 图书馆的书目检索系统自动化问题 教师资料档案管理系统 多叉路口交通灯的管理问题 9

10 客观事物的符号表示，能由计算机程序识别、存储和加工处理的符号集合
§1.1 基本概念和术语 数据：信息载体 客观事物的符号表示，能由计算机程序识别、存储和加工处理的符号集合 所有能够数字化的信息均可认为是数据 数据元素：数据的基本单位，在程序中通常作为一个整体来进行考虑和处理 同义词：元素、结点、顶点、记录、对象、元组等 数据项：具有独立含义的最小标识单位，客观事物某一方面特性的数据描述 同义词：字段、域、属性等

11 §1.1 基本概念和术语 数据结构：相互之间存在一种或多种特定关系的数据元素的集合，即数据的组织形式 数据的逻辑结构：数据元素之间的逻辑关系
数据的存储结构：数据元素及其关系在计算机存储器内的表示 数据的运算：对数据施加的操作

12 §1.1 基本概念和术语 行：结点(对象、记录、元组等)； 数据结构举例 系别 姓名 职称 SCI EI 经费 1 张明 教授 5 20
王华 6 3 15 … 23 李立 60 行：结点(对象、记录、元组等)； 列：数据项(属性、域、字段等) 逻辑结构：开始结点？终端结点？内部结点？ 结点之间的逻辑关系：有且仅有1个开始结点和1个终端结点，表中任1结点最多只有1个直接前驱和1个直接后继-----线性关系 存储结构：用数组实现，还是用指针实现？ 运算：创建、插入、删除、查找等

13 §1.1 基本概念和术语 逻辑结构 存储结构 线性结构：任一结点最多只有1个直接前驱和1个直接后继
非线性结构：一结点可有多个直接前驱和多个直接后继 集合结构：元素间无关系，只有元素是否属于集合的关系 存储结构 (1)顺序存储方法 逻辑上相邻的结点存储在物理位置上相邻的存储单元里 结点间的逻辑关系由存储单元的邻接关系来体现 借助于数组描述 应用于线性的数据结构，非线性的数据结构的线性化

14 §1.1 基本概念和术语 存储结构 (2)链接存储方法 该方法不要求逻辑上相邻的结点在物理位置上亦相邻 借助于指针来表示结点间的逻辑关系
(3)索引存储方法 在存储结点信息的同时，建立附加的索引表。 表中每项称为索引项 (关键字，地址) 稠密索引：每个结点对应1个索引项 稀疏索引：一组结点对应1个索引项 (4)散列存储方法 根据结点的Key直接计算出该结点的存储地址。

15 §1.1 基本概念和术语 数据结构的主要运算 ⑴ 建立(Create)一个数据结构； ⑵ 消除(Destroy)一个数据结构；
⑶ 从一个数据结构中删除(Delete)一个数据元素； ⑷ 把一个数据元素插入(Insert)到一个数据结构中； ⑸ 对一个数据结构进行访问(Access)； ⑹ 对一个数据结构(中的数据元素)进行修改(Modify)； ⑺ 对一个数据结构进行排序(Sort)； ⑻ 对一个数据结构进行查找(Search)。

16 §1.1 基本概念和术语 数据结构3方面之联系 同一逻辑结构的不同存储结构，则用不同名称称谓 例如， 线性表顺序表，链表，散列表
运算不同，称谓也不同 线性表栈、队列 顺序栈、顺序队列 数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。 在C语言中，用一维数组表示顺序存储结构；用结构体类型表示链式存储结构。

17 逻辑结构 物理结构 线性表 顺序存储结构 树 链式存储结构 图 复合存储结构 逻辑结构与所采用的存储结构 数据逻辑结构层次关系图
数据的逻辑结构 非线性结构 集合 图状结构 有向图 无向图 树形结构 一般树 二叉树 线性结构 一般线性表 线性表推广 广义表 数组 串 受限线性表 栈和队列 数据逻辑结构层次关系图 逻辑结构与所采用的存储结构 线性表 树 图 顺序存储结构 链式存储结构 复合存储结构 逻辑结构 物理结构

18 数据类型：是一个值的集合以及定义在这些值上的一组操作的总称，可看作是高级语言提供的数据结构
§1.1 基本概念和术语 数据类型：是一个值的集合以及定义在这些值上的一组操作的总称，可看作是高级语言提供的数据结构 原子类型：值不可分，一般是基本的预定义类型 int，char等，定义了“+”，“-”等 结构类型：可供用户定义的新类型，构造类型、导出类型、派生类型等 由基本类型组织而成，如数组、struct等

19 抽象的数据组织和与之相关的操作，可看作是数据的逻辑结构及其在逻辑结构上定义的抽象操作
§1.1 基本概念和术语 抽象数据类型（Abstract Data Type） 抽象的数据组织和与之相关的操作，可看作是数据的逻辑结构及其在逻辑结构上定义的抽象操作 特点 ①封装与隐藏：将数据和操作封装在一起，内部结构和实现细节对外屏蔽，实现信息隐藏 ②抽象：用户只能通过ADT里定义的接口和说明来访问和操作数据。他反映了程序设计的两层抽象： 概念层（抽象）---ADT、类说明 实现层---类实现，相当于普通类型 应用层----如main(){…}，通过操作对象解决实际问题

20 §1.1 基本概念和术语 ADT ADT_Name{ 抽象数据类型（Abstract Data Type）
Operations： Constructor：//构造函数，创建对象实例 Operation1：//用C++或C函数原型描述 input： Preconditions：//初始条件，执行本操作前系统 //需满足的状态 process：//对数据执行的操作 output：//对返回数据的说明 Postconditions：//执行本操作后系统的状态 Operation2： }

21 §1.1 基本概念和术语 例：抽象数据类型复数的定义 ADT Complex { } ADT Complex
数据对象：D＝{e1,e2｜e1,e2∈RealSet } 数据关系：R1＝{<e1,e2> | e1是复数的实数部分,e2 是复数的虚数部分} 基本操作： InitComplex( &Z, v1, v2 ) 操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。 DestroyComplex( &Z) 操作结果：复数Z被销毁。 GetReal( Z, &realPart) 初始条件：复数已存在。 操作结果：用realPart返回复数Z的实部值。 GetImag( Z, &ImagPart) 操作结果：用ImagPart返回复数Z的虚部值。 Add( z1,z2, &sum ) 初始条件：z1, z2是复数。 操作结果：用sum返回两个复数z1、z2的和值。 } ADT Complex

22 §1.1 基本概念和术语 抽象数据类型的表示与实现 通过程序设计语言中的类型来实现 C C++，Java 抽象数据类型 数据对象 结构体
数据对象 结构体 基本操作 函数 C++，Java 抽象数据类型 类class 数据对象 数据成员 基本操作 成员函数(方法)

23 ADT复数的C描述 typedef struct { }Complex;
double realpart; double imagpart; }Complex; boolean assign(Complex *pSrc, Complex *pDes){ if (pSrc ==NULL || pDes==NULL ) return ERROR; pDes->realpart = pSrc->realpart; pDes->imagpart = pSrc->imagpart; return TRUE; } Complex *add(Complex *pZ1, Complex *pZ2){ Complex *pSum = (Complex *)malloc(sizeof(Complex)); if ( pSum==NULL )return NULL; pSum->realpart = pZ1->realpart + pZ2->realpart; pSum->imagpart = pZ1->imagpart + pZ2->imagpart; return pSum;

24 ADT复数的C++描述 class Complex{ // 类的声明 protected: double realpart;
double magpart; public: Complex( ); Complex(double realVal，double imagVal); Complex(Complex& z){ assign(z) ;} ~Complex( ); void assign(Complex& z); double getReal(void) const { return realpart;} double getImag(void) const { return imagpart;} friend Complex add(Complex& z1, Complex& z2); }；

25 // 类的实现部分 Complex::Complex(double realVal, double imagVal){ realpart = realVal; imagpart= imagVal; } void Complex::assign(Complex& z){ realpart = z.realpart; imagpart= z.imagpart; Complex add(Complex& z1, Complex& z2){ Complex sum(z1); sum.realpart += z2.realpart； sum.imagpart += z2.imagpart； return sum;

26 输入、输出、有穷性（有穷步骤，每步时间有限） 确定性（算法只有唯一执行路径）、可行性（所有 操作可通过已经实现的基本运算有限次实现之）
§1.2 算法描述 分析 算法 重要性：数据的运算是通过算法描述的 定义：非形式地说，算法是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或多个值作为输出。因此，一个算法就是一系列将输入转换为输出的计算步骤。 5要素 输入、输出、有穷性（有穷步骤，每步时间有限） 确定性（算法只有唯一执行路径）、可行性（所有 操作可通过已经实现的基本运算有限次实现之） 算法与程序的联系与区别 算法和程序都是指令的有限序列 ，但是：程序是算法，而算法不一定是 程序。 算法和程序的区别主要在于： (1) 在语言描述上，程序必须是用规定的程序设计语言来写，而算法很随意； (2) 在执行时间上，算法所描述的步骤一定是有限的，而程序可以无限地执行下去。 所以： 程序 = 数据结构 + 算法 说通俗一些 就是将，算法是解决一个问题的思路，程序，则是解决这些问题所具体好写的代码。 算法没有语言界限。他只是一个思路。为实现相同的一个算法，用不同语言编写的程序会不一样。 算法是写程序的思想,程序是算法的体现!

27 §1.2 算法描述 分析 输入实例 一个问题的输入实例是由满足问题陈述中的限制、并能计算出该问题解的所有输入构成的。 算法描述 自然语言、数学语言、伪语言、程序语言等均可 本课程以C为主，但不拘泥于细节 算法评价 正确性、可读性、健壮性、 时空性能

28 §1.2 算法描述 分析 缺陷 算法分析 算法效率的度量 事后统计：利用计算机内部的计时功能 必须先运行依据算法编制的程序
§1.2 算法描述 分析 算法分析 算法效率的度量 事后统计：利用计算机内部的计时功能 缺陷 必须先运行依据算法编制的程序 时间统计量依赖于计算机的软硬件环境 double start, stop; time (&start); main process(n, …); time (&stop); double runTime = stop -start; printf ("%d%d\n" , n, runTime );

29 §1.2 算法描述 分析 事前分析估算(时间) 求出该算法的一个时间界限函数 一些影响因素: 算法的策略 问题的规模 书写程序的语言
§1.2 算法描述 分析 事前分析估算(时间) 求出该算法的一个时间界限函数 一些影响因素: 算法的策略 问题的规模 书写程序的语言 编译器产生的机器代码的质量 机器执行指令的速度

30 §1.2 算法描述与分析 算法分析 算法的时间是每语句执行时间的总和 每语句的执行时间=该语句执行次数（频度） X该语句执行1次的时间 假定：每语句执行1次的时间为1个时间单位 则：算法的执行时间=∑各语句频度 问题的规模（Size）n 输入量的大小，如… 时间复杂度：算法的运行时间，是问题规模的函数

31 §1.2 算法描述与分析 时间复杂度 例1：矩阵乘法 for ( i=0; i＜n; i++) //n+1 for ( j=0; j＜n; j++) { //n(n+1) C[i] [j]=0; //n2 for ( k=0;k＜n; k++) //n2(n+1) C[i][j]=C[i][j]+A[i][k]*B[k][j]; //n3 } 详细分析： T(n)=2n3+3n2+2n+1 简单分析：频度最大的语句 T(n)= =n3

32 从宏观上评价时间性能，只关心当n趋向无穷大时，T(n)的数量级(阶)
§1.2 算法描述与分析 渐近时间复杂度（简称时间复杂度） 从宏观上评价时间性能，只关心当n趋向无穷大时，T(n)的数量级(阶) 即：T(n) 和n3同阶，数量极相同 记作：T(n)=O(n3)

33 §1.2 算法描述与分析 大O的数学定义 若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在两个正的常数c和n0， 使得当n≥n0时都满足0≤T(n)≤c·f(n)。 例２ {++x; s=0 ;} 将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1) 。 如果将s=0也看成是基本操作，则语句频度为２，其时间复杂度仍为Ｏ(1)，即常量阶。

34 §1.2 算法描述与分析 例３ for(i=1; i<=n; ++i) { ++x; s+=x ; }
§1.2 算法描述与分析 例３ for(i=1; i<=n; ++i) { ++x; s+=x ; } 语句频度为：2n，其时间复杂度为：O(n) ，即为线性阶。 例４ for(i=1; i<=n; ++i) 　　　　for(j=1; j<=n; ++j) 语句频度为：2n2 ，其时间复杂度为：O(n2) ，即为平方阶。

35 §1.2 算法描述与分析 定理：若A(n)=am n m +am-1 n m-1 +…+a1n+a0是一个m次多项式，则A(n)=O(n m) 例５ for(i=2;i<=n;++i) for(j=2;j<=i-1;++j) {++x; a[i,j]=x; } 语句频度为：1+2+3+…+n-2=(1+n-2) ×(n-2)/2 =(n-1)(n-2)/2 =n2-3n+2 ∴时间复杂度为O(n2)，即此算法的时间复杂度为平方阶。 一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。

36 §1.2 算法描述与分析 以下六种计算算法时间的多项式是最常用的。其关系为：
§1.2 算法描述与分析 以下六种计算算法时间的多项式是最常用的。其关系为： O(1)<O(㏒n)<O(n)<O(n㏒n)<O(n2)<O(n3) 指数时间的关系为： O(2n)<O(n!)<O(nn) 当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。 有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。

37 例1：素数的判断算法。 Void prime( int n) /* n是一个正整数 */ { int i=2 ;
while ( (n% i)!=0 && i*1.0< sqrt(n) ) i++ ; if (i*1.0>sqrt(n) ) printf(“&d 是一个素数\n” , n) ; else printf(“&d 不是一个素数\n” , n) ; } 嵌套的最深层语句是i++；其频度由条件( (n% i)!=0 && i*1.0< sqrt(n) ) 决定，显然i*1.0< sqrt(n) ，时间复杂度O(n1/2)。

38 例2：冒泡排序法。 Void bubble_sort(int a[]，int n)
{ for (i=n-1, change=TURE; i>1 && change; --i) change=false; for (j=0; j<i; ++j) if (a[j]>a[j+1]) { a[j] ←→a[j+1] ; change=TURE ; } } 最好情况：0次 最坏情况：1+2+3+⋯+n-1=n(n-1)/2 平均时间复杂度为： O(n2)

39 §1.2 算法描述与分析 空间复杂度(Space complexity) ：是指算法编写成程序后，在计算机中运行时所需存储空间大小的度量。记作： S(n)=O(f(n)) 其中： n为问题的规模(或大小) 该存储空间一般包括三个方面： 指令常数变量所占用的存储空间; 输入数据所占用的存储空间; 辅助(存储)空间。 一般地，算法的空间复杂度指的是辅助空间。 一维数组a[n]： 空间复杂度 O(n) 二维数组a[n][m]： 空间复杂度 O(n*m)

40 作 业 1 数据的逻辑结构？数据的物理结构？逻辑结构与物理结构的区别和联系是什么？ 2 分析以下程序段的时间复杂度，请说明分析的理由或原因。
作 业 1 数据的逻辑结构？数据的物理结构？逻辑结构与物理结构的区别和联系是什么？ 2 分析以下程序段的时间复杂度，请说明分析的理由或原因。 ⑴ Sum1( int n ) { int p=1, sum=0, m ; for (m=1; m<=n; m++) { p*=m ; sum+=p ; } return (sum) ; }

41 ⑵ ⑶ 递归函数 Sum2( int n ) { int sum=0, m, t ; for (m=1; m<=n; m++)
{ p=1 ; for (t=1; t<=m; t++) p*=t ; sum+=p ; } return (sum) ; ⑶ 递归函数 fact( int n ) { if (n<=1) return(1) ; else return( n*fact(n-1)) ; }

42 3. 按增长率由小至大的顺序排列下列各函数： 4. 有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将降低次项用大“O”记号表示。例如，设T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n)，T2(n) = 2.0nlgn-2n=2.0nlgn+O(n)，这两个式子表示，当n足够大时T1(n)优于T2(n)，因为前者的常数因子小于后者。请用此方法表示下列函数，并指出当n足够大时，哪一个较优，哪一个较劣？ ⑴ T1(n)=5n2-3n+60lgn ⑵ T2(n)=3n2+1000n+3lgn ⑶ T3(n)=8n2+3lgn ⑷ T4(n)=1.5n2+6000nlgn