资源描述
数据结构,主讲：计算机学院 张艳 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年5月。,3,主要内容和学习要点,1.1 什么是数据结构 1.2 数据结构的基本概念和术语 熟悉各名词、术语如数据、数据元素、数据项、数据对象、数据结构的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。 1.3 抽象数据类型的表示和实现 了解抽象数据类型的定义、表示和实现方法。 1.4 算法和算法分析 理解算法四个要素的确切含义。掌握计算语句频度和估算算法时间复杂度的方法。,4,计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题： 信息的表示 信息的处理 而信息的表示和处理又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。,引言,5,Q1 ： 什么是数据结构？ Q2 ：学习数据结构有什么用？ Q3 ：数据结构涵盖的主要内容？,讨论：,1.1 什么是数据结构,6,针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。 是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。,数据结构的地位,7,是相互之间存在一种或多种特定关系的数据元素的集合，表示为：,（数值或非数值）,Data_Structure=（D, R）,或是指同一数据元素类型中各元素之间存在的关系。,元素有限集,关系有限集,Q1:什么是数据结构,8,著名计算机科学家、Pascal语言发明者N.沃思教授提出： 程序 = 算法 + 数据结构 也就是说，计算机按照程序所描述的算法对某种结构的数据进行加工处理。 数据结构定义: 是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。 非数值计算的程序设计问题：信息自动检索、计算机游戏、多岔路口交通灯的管理。,什么是数据结构,按书名,按作者名,按分类号,索引表,例1 书目自动检索系统,书目文件,例2 人机对奕问题,例3 多叉路口交通灯管理问题,12,数据（data)：所有能输入到计算机中去的描述客观事物的符号 是计算机处理的信息的某种特定的符号表示形式。它包括数值 型数据和非数值型数据（如字符、图象、声音）。 数据元素（data element）：数据的基本单位，也称结点（node） 或记录（record）。 数据项(data item):有独立含义的数据最小单位，也称域(field)。 数据对象(data object)：性质相同的数据元素的集合，是数据的 一个子集。,1.2 数据结构的基本概念和术语,三者之间的关系：数据 对象 数据元素 数据项,例：班级通讯录 个人记录 姓名、年龄,13,数据对象(data object)：性质相同的数据元素的集合，是数据的 一个子集。 如大写字母字符数据对象是集合 C=A,B,C,，Z ； 整数数据对象是集合 N = 0, 1, 2, 数据结构（data structure)：数据元素和数据元素关系的集合。,Data_Structure=（D, R）,14,答：计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。 这是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。,程序设计实质好算法好结构,同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。,Q2：学习数据结构有什么用？,15,数据的逻辑结构,数据的存储结构,数据的运算：检索、排序、插入、删除、修改等,线性结构,非线性结构,顺序结构,链式结构,线性表,栈,队,树形结构,图形结构,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),解： 上述表达式可用图形表示为：,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,1345,h,链式存储 结构,h,22,答：在数据的逻辑结构上定义的操作算法。 它在数据的存储结构上实现。,最常用的数据运算有 5 种：,插入、删除、修改、查找、排序,解释3：什么是数据的运算？,23,Q1： 数据类型与抽象数据类型的区别？ Q2: 抽象数据类型如何定义？ Q3: 抽象数据类型如何表示和实现？,讨论：,抽象数据类型和伪码是学习数据结构的工具,1.3 抽象数据类型,24,数据类型（data type）： 一个值的集合和定义在这个集合上的一组操作的总称。如C语言中的整型（短整型2个字节表示范围-3276832767、长整型4个字节）、浮点型（4个字节，带小数点）、字符型（1个字节，用单引号表示，如a）、双精度型（8个字节） 抽象数据类型(ADT: Abstract Data Type)： 由用户定义，用以表示应用问题的数据模型。 由基本的数据类型组成, 并包括一组相关的服务（或称操作）。 区别：ADT与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐藏。,Q1： 数据类型与抽象数据类型的区别？,25,Q2 抽象数据类型如何定义？,抽象数据类型可以用以下的三元组来表示： ADT = （D，S，P） 数据对象 D上的关系集 D上的操作集,ADT抽象数据类型名 数据对象： 数据关系： 基本操作 ： ADT抽象数据类型名,ADT常用定义格式,26,抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。,注1 ：它有些类似C语言中的结构（struct)类型，但增加了相关的服务（或操作） 。 注2 ：教材中用类C语言（介于伪码和C语言之间）作为描述工具。,但上机时要用具体语言实现，如C或C+等,Q3 抽象数据类型如何表示和实现？,27,ADT Complex 数据对象:De1,e2e1,e2RealSet 数据关系:R | e1是实数部分,e2 是虚数部分 基本操作： InitComplex( in;i+) / y=y+1; / for (j=0;j=2*n;j+) / x+; / 基本操作 ,语句的频度指的是该语句执行的次数.一个算法中所有 语句的频度之和构成了该算法的运行时间.,解答: 语句1的频度是n+1;语句2的频度是n;语句3的频度是 n(2n+2)=2n2+2n;语句4的频度是n(2n+1)=2n2+n 所以该程序段的时间复杂度 T(n)=(n+1)+n+(2n2+2n)+(2n2+n)=4n2+5n+1=O(n2),实际上,可以用算法中基本操作重复执行的频度作为度量. 被视为基本操作的一般是最深层循环内的语句,算法的时间复杂度的计算,34,例2：矩阵相乘 for(i=1;i=n;i+) for(j=1;j=n;j+) cij=0; for(k=1;k=n;k+) cij=cij+aik*bkj; ,T(n)=O(n3),例3： 设n为正整数, 分析下列程序段中内层循环语句的程序步数。,for(i=1;i=n;i+) for(j=1;j=i;j+) for(k=1;k=j;k+) x+=y;,T(n)=O(n3),36,算法的存储量包括: 1输入数据所占空间; 2程序本身所占空间； 3辅助变量所占空间。 若输入数据所占空间只取决与问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间。 若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，记作：S(n) = O(g(n)表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。,算法的空间复杂度,37,注意：算法的所有性能之间都存在着或多或少的相互影响，因此，当设计一个算法，特别是大型算法时，要综合考虑算法的各项性能、算法的使用频率、算法处理的数据量的大小、算法描述语言的特性及算法运行的机器系统环境等各方面因素，才能设计出比较好的算法。,38,作业,习题集 1.1、1.2、1.3、1.8、1.9、1.10,
展开阅读全文