数据结构第一章.ppt

1、数据结构,2020年8月14日星期五,学时数：48学时（16学时实验） 教 材：数据结构C语言版严蔚敏、吴伟民 -清华大学出版社（配题集）,参考书： 1 殷人昆等，数据结构（用面向对象方法与C+描述），清华 大学出版社 2数据结构C语言篇习题与解析，李春葆，清华大学出版社 3 丁宝康等，数据结构自学考试指导，清华大学出版社,课程介绍,学习要求,1、上课认真听讲，适当做好笔记，按时交作业。 2、复习和预习。 3、课后需要多读课本和参考书，上网查看相关内容，在理解基本内容的基础上，多看、多做习题。 4、上机实践。, 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示和实现

2、1.4 算法和算法分析,第1章 绪论,数据结构与程序的关系 思考:下表是10次C语言课程的测验成绩，请设计一个小程序计算这10次测验的总分和平均分。,1.1 什么是数据结构,方法一: void main() int t1,t2,t3,t4,t5,t6,t7,t8,t9,t10; int sum; int average; t1=; t2=; t3=; t4=; t5=; t6=; . sum=t1+.t10; average=sum/10; ,方法二: void main() int t10=80,.; int sum; int average; int i; sum=0; for (i=0;

3、i10;i+) sum+=ti; average=sum/10; ,哪种方法好? 为什么?,如何选择最佳的数据结构来解决程序问题是为什么需要学习数据结构的重要原因。 数据结构主要研究数据的逻辑结构,在计算机中的存储结构以及对数据进行各种非数值运算的方法和算法。,数据结构示例A 线性表,1.1 什么是数据结构,数据结构示例B树,1.1 什么是数据结构,1.许卓群，张乃孝，杨冬青，唐世渭，数据结构，国防科技大学计算机研究所，1985年 “按某种逻辑关系组织起来的一批数据，按一定的存储表示方式把它存储在计算机的存储器中，并在这些数据上定义了一个运算的集合，就叫做一个数据结构。” 特点：从三个方面来看

4、数据结构。,2.李春葆，数据结构（C语言篇）习题与解析，清华大学出版社，2000年 “数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构又可以分为下述三个组成部分，它们分别是数据的逻辑结构、数据的存储结构和数据的运算。” 特点：明确强调“关系”，且细分“关系”。,1.1 什么是数据结构,3.黄国瑜，叶乃菁，数据结构，清华大学出版社，2001年 “在程序语言中，“数据类型”是指程序语言中变量所能表示并存储的数据种类，“数据实体”则是指在一种数据类型中的所有可能元素的集合。而“数据结构”，大致上说来，就是数据实体中元素之间的关系，包括数据的表示法和运算。” 特点：指出“关系”为表示法和

5、运算。,4.陈慧南，数据结构C语言描述，西安电子科技大学出版社，2003年 “从数学概念上讲，一个数据结构是由数据元素依据某种逻辑联系组织起来的。 研究数据结构是为了解决应用问题，所以讨论数据结构必须同时讨论在数据结构上执行的相关运算及其算法才有意义。” 特点：从逻辑联系入手，兼顾其它方面。,1.1 什么是数据结构,数据结构要解决的问题,1 数值问题 例 已知：游泳池的长len和宽wide，求面积area 建模型： 问题涉及的对象： 游泳池的长len 宽wide，面积area； 对象之间的关系： area=lenwide,设计求解问题的方法 编程 main ( ) int len, wide

6、,area ;scanf (“%d %d%n”, ,2 非数值问题 例 已知班级学生情况，如下表1_1，要求分班按入学成绩排列顺序。 表1_1： 学号 姓名 性别 出生日期 籍贯 入学成绩 所在班级 082001 杨润生 男 82/06/01 广州 561 00计算机1 082031 石磊 男 83/12/21 汕头 512 00计算机1 082053 李梅 女 83/02/23 阳江 532 00计算机2 082064 马耀先 男 82/07/12 广州 509 00计算机2,计算机内的数值运算依靠方程式，而非数值运算则要依靠数据结构。,同样的数据对象，用不同的数据结构来表示，运算效率可能有

7、明显的差异。,程序设计实质 = 好算法 + 好结构,学习数据结构课程的用处,1.1 什么是数据结构,本书讨论的典型数据结构包括：线性表、堆栈、队列、数组、串、树、二叉树和图。,是介于数学、计算机硬件和计算机软件三者之间的一门核心课程,数学,硬件,软件,数据结构课程的地位,1.1 什么是数据结构,数据-是对客观事物的符号表示，在计算机科学中是指所有（Data） 能输入到计算机中并被计算机程序处理 的符号的总 称(整数、实数、字符串、图像、声音等)。,数据元素-是数据的基本单位，具有完整确定的实际意义， （Data Element） 在计算机程序中通常作为一个整体进行考虑和 处理(又称记录、结点等

8、)。,数据项- 一个数据元素可由若干个数据项组成， 是数据的 （Data Item） 不可分割的最小单位(又称字段等)。,三者之间的关系：数据数据元素数据项,例：学生档案个人记录姓名、性别、籍贯,1.2 基本概念和术语,数据对象（Data Object）-是性质相同的数据元素的集合， 是数据的一个子集。,数据结构（Data Structure）-是相互之间存在一种或多种 特定关系的数据元素的集合。,表示为： Data_Structure = ( D, S ),元素有限集,关系有限集,例1：用数据结构表示一周中的七天。,Data_Structure=(D,S),其中， D= S= ,Mon,Tu

9、e, Wen, Thu, Fri, Sat, Sun,1.2 基本概念和术语,（1）Data_Structure=(D,S)，其中， D= 01，02，03，04，05 S= ,（2） S=(D, R) D= a, b, c, d, e, f R= , , , , ,解: 上述表达式可用图形表示为：,a,e,b,c,f,d,例2：将下述表达式用图形的形式表示出来,集合结构,线性结构,1.2 基本概念和术语,（3） Data_Structure=(D,S),其中， D= 01，02，03，04，05 ，06，07 S=(01,02)，(01,03)，(01,04)，(02,05)，(02,06)

10、，(03,07) ,（4） S=(D,R) D=di | 1i5, 1j5 R=, ij,01,02,03,04,05,06,07,树形结构,图状结构,1.2 基本概念和术语,逻辑结构-数据元素之间的逻辑关系，即结构中定义的“关系”。,逻辑结构可细分为4类：,集合结构 线性结构 树形结构 图状结构,一对一关系,一对多关系,多对多关系,1.2 基本概念和术语,物理结构-也称存储结构，是数据的逻辑结构在计算机存 储器内的表示（映像）。,顺序映像 非顺序映像,特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。,特点是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。,例：复数 3.

11、0-2.3i 的存储形式,算法的设计取决于选定的数据（逻辑）结构 算法的实现依赖于采用的存储结构,-顺序存储结构,-链式存储结构,1.2 基本概念和术语,数据类型-是一个值的集合和定义在这个值集上的一组操作 的总称。,抽象数据类型由用户定义，用以表示应用问题的数据模型。它由基本的数据类型组成，并包含一组相关的操作。,抽象数据类型可用ADT=（D，S，P）三元组表示,ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名,ADT常用定义格式：,1.3 抽象数据类型的表示与实现,例：给出自然数（Natural Number）的抽

12、象数据类型定义。,IsZero(x) : Boolean if (x=0) 返回True else 返回False Add (x, y) : NaturalNumber if (x+y=MaxInt)返回 x+y else 返回MaxInt Subtract (x, y) : NaturalNumber if (x y) 返回 0 else 返回 x - y Equal (x, y) : Boolean if (x=y) 返回True else 返回 False,ADT NaturalNumber ,NaturalNumber,数据对象:,数据关系:,数据操作:,一个整数的有序子集合,它开始于

13、0, 结束于机器能表示的最大整数。,1.3 抽象数据类型的表示与实现,一、算法：,算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。,二、算法的5个特性： 有穷性、确定性、可行性、输入和输出,三、算法设计的要求： 正确性、可读性、健壮性、效率与低存储需求,时间复杂度,空间复杂度,1.4 算法和算法分析,时间复杂度：,一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中语句的执行次数称为语句频度或时间频度，记为T(n)。,算法中基本操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作 T（n）=O（

14、f（n） 随着问题规模的增大，算法执行时间的增长率和f（n）的增长率相同，称为算法的渐近时间复杂度，简称时间复杂度。,1.4 算法和算法分析,从算法中选取一种对于所研究的问题来说是 基本操作 的原操作，以该基本操作 在算法中重复执行的次数 作为算法运行时间的衡量准则。,算法的时间复杂度由嵌套最深层语句的频度决定,1.4 算法和算法分析,时间复杂度,一般没有必要精确地计算出算法的时间复杂度,只要大致计算出相应的数量级即可。,3n+2=O(n) 因为 3n+24n 当 n2时 6*2n+n2=O(2n) 因为6*2n+n2 7*2n 当 n4,例：,渐进符号（O）的定义：当且仅当存在一个正的常数

15、C，使得对所有的 n n0 ，有 f(n) Cg(n)，则： f(n) = O(g(n), +x;s=0;, for(i=1;i=n;+i) +x;s+=x;, for(j=1;j=n;+j) for(k=1;k=n;+k) +x;s+=x;,O （1）,O （n）,O （n2）,算法的时间复杂度由嵌套最深的语句的频度决定的, i=1; while(i=n) i=i*2;,O （log2n）,1.4 算法和算法分析,1.4 算法和算法分析,算法分析应用举例,算法中基本操作重复执行的次数是问题规模n的某个函数，其时间量度记作 T(n)=O(f(n)，称作算法的渐近时间复杂度(Asymptotic

16、 Time complexity)，简称时间复杂度。 一般地，常用最深层循环内的语句中的原操作的执行频度(重复执行的次数)来表示。 “O”的定义： 若f(n)是正整数n的一个函数，则 O(f(n)表示 M0 ，使得当n n0时，| f(n) | M | f(n0) | 。 表示时间复杂度的阶有： O(1) ：常量时间阶 O (n)：线性时间阶 O(n) ：对数时间阶 O(nn) ：线性对数时间阶,O (nk)： k2 ，k次方时间阶 例 两个n阶方阵的乘法 for(i=1，i=n; +i) for(j=1; j=n; +j) cij=0 ; for(k=1; k=n; +k) cij+=aik

17、*bkj ; 由于是一个三重循环，每个循环从1到n，则总次数为： nnn=n3时间复杂度为T(n)=O(n3) 例 +x; s=0 ; 将x自增看成是基本操作，则语句频度为，即时间复杂度为(1) 。,如果将s=0也看成是基本操作，则语句频度为，其时间复杂度仍为(1)，即常量阶。 例 for(i=1; i=n; +i) +x; s+=x ; 语句频度为：2n，其时间复杂度为：O(n) ，即为线性阶。 例 for(i=1; i=n; +i) for(j=1; j=n; +j) +x; s+=x ; 语句频度为：2n2 ，其时间复杂度为：O(n2) ，即为平方阶。,定理：若A(n)=a m n m

18、+a m-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; ai,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)的算法则由一个二次多项式来限界。,以下六种计算算法时间的多项式是最常用的。其关系为： O(1)O(n)O(n)O(nn)O(n2)O(n3) 指数时间的关系为： O(2n)O(n!)O(nn) 当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的