数据结构-严蔚敏.ppt

《数据结构-严蔚敏.ppt》由会员分享，可在线阅读，更多相关《数据结构-严蔚敏.ppt（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、上课前需要说明的几个问题： 1.任课教师：焦贤沛 联系电话：83816656 2. 交流信箱： 3.关于数据结构课程： 教材、重要性、时间安排（64+32）、 考试,第一章 绪 论,1.1 数据结构讨论的范畴,1.2 基本概念,1.3 算法和算法的量度,1.1 数据结构讨论的范畴,Niklaus Wirth： Algorithm + Data Structures = Programs,程序设计: 算法: 数据结构:,为计算机处理问题编制 一组指令集,处理问题的策略,问题的数学模型,结构静力分析计算,例如: 数值计算的程序设计问题, 线性代数方程组, 环流模式方程 (球面坐标系),全球天气预报

2、,【例1-1】图书目录表 由于表中每条记录（表示每一本书）的登录号各不相同，所以可用登录号来唯一地标识每条记录（一本图书）。在计算机的数据管理中，能唯一地标识一条记录的数据项被称为关键字。因为每本图书的登录排列位置有先后次序，所以在表中会按登录号形成一种次序关系，即整个二维表就是图书数据的一个线性序列。这种关系被称为线性结构。,非数值计算的程序设计问题,返回,返回,描述磁盘目录和文件结构时，假设每个磁盘包括一个根目录（root）和若干个一级子目录，每个一级子目录中又包含若干个二级子目录. 这种关系很像自然界中的树，所以称为目录树。如左图所示。,【例1-2】磁盘目录结构和文件管理系统,在这种结构

3、中，目录和目录以及目录和文件之间呈现出一对多的非线性关系。即根root有多个下属（也称为后代），每一后代又有属于自己的后代；而任一个子目录或文件都只有一个唯一的上级（也称为双亲）。称这种数学模型为树型数据结构。,【例1-3】教学计划编排问题,假如一个教学计划中包含许多课程。在课程之间，有些必须按规定的先后次序排课，如：学C6课程必须先学C3课，学C3课程必须先学C1课。这些课程之间存在先修和后续的关系。 在这种结构中，表示课程的数据之间呈现多对多的非线性关系，称这类数学模型为图形结构。,图结构还有：多岔路口交通灯的控制和管理、煤气管道的铺设造价等。,数据结构是一门讨论“描述现实世界实体的数学模

4、型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。,概括地说：,1.2 基本概念,一、数据与数据结构,二、数据类型,三、抽象数据类型,一、数据与数据结构,所有能被输入到计算机中，且能被计算机处理的符号的集合。,数据:,是计算机操作的对象的总称。,是计算机处理的信息的某种特定的符号表示形式。,是数据（集合）中的一个“个体”,数据元素:,是数据结构中讨论的基本单位,数据项：,是数据结构中讨论的最小单位,数据元素可以是数据项的集合,例如：,描述一个学生的数据元素可以是,称之为组合项,数据结构：,带结构的数据元素的集合,假设用三个 4 位的十进制数表示一个含 12 位数的十进制数。,321

5、4,6587,9345 a1(3214),a2(6587),a3(9345),则在数据元素 a1、a2 和 a3 之间存在着“次序”关系 a1,a2、a2,a3,3214，6587，9345 a1 a2 a3,6587，3214，9345 a2 a1 a3,例如:,又例，在2行3列的二维数组a1, a2, a3, a4, a5, a6 中六个元素之间 存在两个关系:,行的次序关系: 列的次序关系:,row = ,col = ,a1 a3 a5 a2 a4 a6,a1 a2 a3 a4 a5 a6,再例，在一维数组 a1, a2, a3, a4, a5, a6 的数据元素之间存在如下的次序关系:

6、,| i=1, 2, 3, 4, 5,或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。,可见，不同的“关系”构成不同的“结构”,数据的逻辑结构可归结为以下四类:,线性结构,树形结构,图状结构,集合结构,数据结构的形式定义为:,数据结构是一个二元组,Data_Structures = (D, S),其中:D 是数据元素的有限集， S 是 D上关系的有限集。,数据的存储结构, 逻辑结构在存储器中的映象,“数据元素”的映象 ？,“关系”的映象 ？,数据元素的映象方法：,用二进制位(bit)的位串表示数据元素,(321)10 = (501)8 = (101000001)2,A = (10

7、1)8 = (001000001)2,关系的映象方法：,（表示x, y的方法）,顺序映象,以相对的存储位置表示后继关系,例如:令 y 的存储位置和 x 的存储位置之间差一个常量 C,而 C 是一个隐含值，整个存储结构中只含数据元素本身的信息,x y,链式映象,以附加信息(指针)表示后继关系,需要用一个和 x 在一起的附加信息指示 y 的存储位置,y x,在不同的编程环境中，,存储结构可有不同的描述方法。,当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。,例如:,以三个带有次序关系的整数表示一个长整数时，可利用 C 语言中提供的整数数组类型。,typedef int

8、Long_int 3；,定义长整数为:,二、数据类型,在用高级程序语言编写的程序中， 必须对程序中出现的每个变量、 常量或表达式，明确说明它们所 属的数据类型。,例如，C 语言中提供的基本数据类型有:,整型 int,浮点型 float,字符型 char,逻辑型 bool （ C+语言）,双精度型 double,实型（ C+语言）,数据类型 是一个 值的集合 和定义在此集合上的 一组操作 的总称。,不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。,三、抽象数据类型 (Abstract Data Type 简称ADT),是指一个数学模型以及定义在此数学模型上的一组操作。,例如，抽象数据

9、类型复数的定义：,数据对象： De1,e2e1,e2RealSet 数据关系： R1 | e1是复数的实数部分 | e2 是复数的虚数部分 ,ADT Complex ,基本操作：,AssignComplex( / 选择第 i 个最小元素 for ( k = i+1; k n; +k ) if (ak aj ) j = k;,for ( i = 0; i n-1; +i ) if ( j != i ) aj ai ,例 三 起 泡 排 序,void bubble_sort(int -i) / bubble_sort,基本操作: 赋值操作,时间复杂度: O(n2), change = FALSE;

10、 / change 为元素进行交换标志 for (j=0; j aj+1) aj aj+1; change = TRUE ; / 一趟起泡,四、算法的存储空间需求,算法的空间复杂度定义为:,表示随着问题规模 n 的增大， 算法运行所需存储量的增长率 与 g(n) 的增长率相同。,S(n) = O(g(n),算法的存储量包括:,1输入数据所占空间,2程序本身所占空间,3辅助变量所占空间,若输入数据所占空间只取决于问题 本身，和算法无关，则只需要分析除 输入和程序之外的辅助变量所占额外 空间。,若所需额外空间相对于输入数据量 来说是常数，则称此算法为原地工作。,若所需存储量依赖于特定的输入， 则通

11、常按最坏情况考虑。,关于C与VC使用的一些注意问题,1、主函数前一般需用无类型返回，即： void main() 2、即使只用到了printf()函数或scanf()函数，也需要包含相应的头文件，即： #include 当然，你也可以使用C+的输入输出方式。,C+中的参数传递,1、值参的传递 2、通过指针方式进行参数传递 3、通过引用参数进行参数传递 具体方式详见例题。,教材中的类C在转换成程序时需注意的方面：,1、关于ElemType，是一个数据类型，但并不是C中所固有的数据类型，在实际运行时需对它重新加以定义，以适应具体问题的需要。 2、教材中的算法都忽略了局部变量的定义，实际运行时应该予以补充。 3、凡是函数中调用的库函数，都要先包含相应的头文件，若调用了用户自定义函数，则需对其进行定义。即不能调用尚不存在的函数。,关于3个常用的函数：,头文件#include 1、malloc(字节数) ，返回值为指针 2、free(指针变量） 3、realloc(指针变量，字节数） ，返回值为指针，可复制参数中指针变量原有内存中的数据。 请见例题中关于这三个函数的使用方式说明,1. 熟悉各名词、术语的含义，掌握基本概念。,2. 理解算法五个要素的确切含义。,本章学习要点,3. 掌握计算语句频度和估算算法时间复杂度的方法。,