青岛理工大学数据结构课件第一章

《青岛理工大学数据结构课件第一章》由会员分享，可在线阅读，更多相关《青岛理工大学数据结构课件第一章（38页珍藏版）》请在金锄头文库上搜索。

1、数据结构,主讲：计算机学院 张艳 Email:zhangyan1228_ Telephone:15963299081 数据结构网上课堂：http:/221.0.174.198:58888/datastructure,2,教 材：严蔚敏等，数据结构（C语言版），清华大学出版社，2007（配题集） 参考书： 1 殷人昆等，数据结构（用面向对象方法与C+描述），清华大学出版社，1999年7月。 2 殷人昆等，数据结构习题解析，清华大学出版社，2002年4月。 3 李春保，数据结构习题与解析（C语言篇），清华大学出版社，2001年1月。 4 丁宝康等，数据结构自学考试指导，清华大学出版社， 2001年

2、5月。,3,主要内容和学习要点,1.1 什么是数据结构 1.2 数据结构的基本概念和术语 熟悉各名词、术语如数据、数据元素、数据项、数据对象、数据结构的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。 1.3 抽象数据类型的表示和实现 了解抽象数据类型的定义、表示和实现方法。 1.4 算法和算法分析 理解算法四个要素的确切含义。掌握计算语句频度和估算算法时间复杂度的方法。,4,计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题： 信息的表示 信息的处理 而信息的表示和处理又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系

3、统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。,引言,5,Q1 ： 什么是数据结构？ Q2 ：学习数据结构有什么用？ Q3 ：数据结构涵盖的主要内容？,讨论：,1.1 什么是数据结构,6,针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。 是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。,数据结构的地位,7,是相互之间存在一种或多种特定关系的数据元素的集合，表示为：,（数值或非数值）,Data_Structure=（D, R）,或是指同一数据

4、元素类型中各元素之间存在的关系。,元素有限集,关系有限集,Q1:什么是数据结构,8,著名计算机科学家、Pascal语言发明者N.沃思教授提出： 程序 = 算法 + 数据结构 也就是说，计算机按照程序所描述的算法对某种结构的数据进行加工处理。 数据结构定义: 是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。 非数值计算的程序设计问题：信息自动检索、计算机游戏、多岔路口交通灯的管理。,什么是数据结构,按书名,按作者名,按分类号,索引表,例1 书目自动检索系统,书目文件,例2 人机对奕问题,例3 多叉路口交通灯管理问题,12,数据（data)：所有能输入到计算

5、机中去的描述客观事物的符号 是计算机处理的信息的某种特定的符号表示形式。它包括数值 型数据和非数值型数据（如字符、图象、声音）。 数据元素（data element）：数据的基本单位，也称结点（node） 或记录（record）。 数据项(data item):有独立含义的数据最小单位，也称域(field)。 数据对象(data object)：性质相同的数据元素的集合，是数据的 一个子集。,1.2 数据结构的基本概念和术语,三者之间的关系：数据 对象 数据元素 数据项,例：班级通讯录 个人记录 姓名、年龄,13,数据对象(data object)：性质相同的数据元素的集合，是数据的 一个子集

6、。 如大写字母字符数据对象是集合 C=A,B,C,，Z ； 整数数据对象是集合 N = 0, 1, 2, 数据结构（data structure)：数据元素和数据元素关系的集合。,Data_Structure=（D, R）,14,答：计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。 这是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。,程序设计实质好算法好结构,同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。,Q2：学习数据结构有什么用？,15,数据的逻辑结构,数据的存储结构,数据的运算：检索、排序、插入、删

7、除、修改等,线性结构,非线性结构,顺序结构,链式结构,线性表,栈,队,树形结构,图形结构,Q3:数据结构研究的内容：,索引结构,散列结构,16,集合结构： 仅同属一个集合 线性结构: 一对一（1:1) 树 形结 构: 一对多（1:n) 图 形 结 构: 多对多 (m:n),非线性,线 性,逻辑结构可细分为4类：,指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。,解释1：什么叫数据的逻辑结构？,17,（1） S=(D, R) D= a, b, c, d, e, f R=(a,e), (b,c), (c,a), (e,f), (f,d),解： 上述表达式可用

8、图形表示为：,b c a e f d,此结构为线性的。,例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。,18,该结构是非线性的。,解：上述表达式可用图形表示为：,（2） S=(D, R) D=di | 1i5 R=(di , dj ), ij,d1 d5 d2 d4 d3,19,答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。,解释2：什么叫数据的物理结构？,数据的逻辑结构与存储结构密切相关 算法设计 逻辑结构 算法实现 存储结构,还有索引存储结构和散列存储结构,1536,元素2,1400,元素1,1346,元素3,元素4,13

9、45,h,链式存储 结构,h,22,答：在数据的逻辑结构上定义的操作算法。 它在数据的存储结构上实现。,最常用的数据运算有 5 种：,插入、删除、修改、查找、排序,解释3：什么是数据的运算？,23,Q1： 数据类型与抽象数据类型的区别？ Q2: 抽象数据类型如何定义？ Q3: 抽象数据类型如何表示和实现？,讨论：,抽象数据类型和伪码是学习数据结构的工具,1.3 抽象数据类型,24,数据类型（data type）： 一个值的集合和定义在这个集合上的一组操作的总称。如C语言中的整型（短整型2个字节表示范围-3276832767、长整型4个字节）、浮点型（4个字节，带小数点）、字符型（1个字节，用单

10、引号表示，如a）、双精度型（8个字节） 抽象数据类型(ADT: Abstract Data Type)： 由用户定义，用以表示应用问题的数据模型。 由基本的数据类型组成, 并包括一组相关的服务（或称操作）。 区别：ADT与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐藏。,Q1： 数据类型与抽象数据类型的区别？,25,Q2 抽象数据类型如何定义？,抽象数据类型可以用以下的三元组来表示： ADT = （D，S，P） 数据对象 D上的关系集 D上的操作集,ADT抽象数据类型名 数据对象： 数据关系： 基本操作 ： ADT抽象数据类型名,ADT常用定义格式,26,抽象数据类型可

11、以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。,注1 ：它有些类似C语言中的结构（struct)类型，但增加了相关的服务（或操作） 。 注2 ：教材中用类C语言（介于伪码和C语言之间）作为描述工具。,但上机时要用具体语言实现，如C或C+等,Q3 抽象数据类型如何表示和实现？,27,ADT Complex 数据对象:De1,e2e1,e2RealSet 数据关系:R | e1是实数部分,e2 是虚数部分 基本操作： InitComplex( &Z, v1, v2 ) 操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。 DestroyComplex( &Z) 操作结果：

12、复数Z被销毁。 GetReal( Z, &realPart ) 初始条件：复数已存在。 操作结果：用realPart返回复数Z的实部值。 GetImag( Z, &ImagPart ) 初始条件：复数已存在。 操作结果：用ImagPart返回复数Z的虚部值。 ADT Complex,例：抽象数据类型复数的表示与实现,28,1.4 算法的描述和算法分析,Q1. 什么是算法？如何评判一个算法的好坏？ Q2. 时间复杂度和空间复杂度如何表示？ Q3. 计算举例,讨论：,29,算法（algorithm）：解决某一特定问题的具体步骤的描述，是指令的有限序列。 算法特性： （1） 输入：一个算法必须有0个

13、或多个输入。它们是算法开始运算前给予算法的量。这些输入取自于特定的对象的集合。它们可以使用输入语句由外部提供，也可以使用赋值语句在算法内给定。 （2） 输出：一个算法应有一个或多个输出，输出的量是算法计算的结果。 （3） 确定性：算法的每一步都应确切地、无歧义地定义。对于每一种情况，需要执行的动作都应严格地、清晰地规定。 （4） 有穷性：一个算法无论在什么情况下都应在执行有穷步后结束。 （5） 可行性：即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。,Q1. 什么是算法？如何评判一个算法的好坏？,30,（1） 正确性 在合理的数据输入下，能在有限时间内得到正确的结果 （2）

14、可读性 程序可读性好，易于人对算法的理解。 （3） 健壮性 当输入的数据非法时，算法应当恰当地作出反映或进行 相应处理，而不是产生莫 名奇妙的输出结果。并且， 处理出错的方法不应是中断程序的执行，而应是返回一 个表示错误或错误性质的值，以便在更高的抽象层次上 进行处理。 （4） 运行时间（时间复杂性）常用时间复杂度来衡量 指一个算法在计算机上运算所花费的时间。 （5）占用的存储空间（空间复杂性）常用空间复杂度来衡量 指一个算法在计算机存储器中所占用的存储空间。,算法设计的原则（性能标准）,31,时间复杂度：通常把算法中所包含的简单操作次数的多少叫做算法的时间复杂度。 算法的执行时间与简单操作执

15、行次数之和成正比。简单操作次数越少，运行时间也越少。 设解决一个问题的规模为n（比如排序问题中，n表示待排序元素的个数；在矩阵运算中，n表示矩阵的阶数；在图的遍历中，n表示图中的顶点数），简单操作被重复执行的次数是n的一个函数 f（n）。 假如，随着问题规模n的增长，算法执行时间的增长率和f(n）增长率相同，则可记作： T (n) = O(f(n) 其中T（n）叫算法的渐进时间复杂度，简称时间复杂度， O是Order（数量级）的首字母，意思是T（n）与f（n）只差一个常数倍。,Q2:时间复杂度如何表示,32,注1 O（）为渐近符号。 注2 空间复杂度S(n)按数量级递增顺序也与上表类同。,复杂度高,复杂度低,时间复杂度T(n)按数量级递增顺序为：,33,例1: 分析以下程序段的时间复杂度. for (i=0;in;i+) / y=y+1; / for (j=0;j=2*n;j+) / x+; / 基本操作 ,语句的频度指的是该语句执行的次数.一个算法中所有 语句的频度之和构成了该算法的运行时间.,解答: 语句1的频度是n+1;语句2