数据结构-第1次课第一章基本概念(更改的)

1、第一章 绪论,计算机是一门研究利用计算机进行信息表示和处理的科学。涉及： 信息的表示 信息的处理 而信息的表示又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。 数据结构-独立的学科始于1968年，但在此之前有关内容已散见 于编译原理和操作系统的教材之中。 -1968年，美国的图灵奖”获得者克努特（D.E.Knuth）开创课程体系。,为什么要学习数据结构？,1、电子计算机的主要用途： 计算机是

2、一门研究利用计算机进行信息表示和处理的科学。涉及：信息的表示和信息的处理。 早期： 主要用于数值计算。 后来： 处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。 提高程序的效率、编写出一个“好”的程序。必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。,第一章 绪论,用计算机解决问题的过程,建立模型,构造求解算法,选择存储结构,编写程序,测试,描述问题的共性,描述问题的求解方法,将问题涉及的数据存储到计算机中,分析问题的过程,数据结构的作用,进行更为复杂的算法设计,选择合理的存储结构,提高编程技术,数据结构课程的形成和发展,形成阶段

3、60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。 1968年，美唐纳德克努特(Donald Ervin Knuth)教授开创了数据结构的最初体系，计算机程序设计技巧第一卷基本算法 ，“数据结构”被列入美国一些大学计算机科学系的教学计划。 发展阶段： 数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。 70年代后期，80年代初，我国高校陆续开设该课程。,介于数学、计算机硬件和计算机软件三者之间的一门核心课程。,数据结构课程所处的地位：,学习提要,掌握本课程所涉及到的基本名词、术语和概念，特别是数据的逻辑结构和存储结构之间的关系及性质。

4、了解抽象数据类型的定义、表示和实现方法。 理解算法设计的五个要素和基本要求；掌握算法效率的度量方法，着重学习算法的时间复杂度分析。,教学重点,数据、数据元素、数据项； 逻辑结构和存储结构在概念上的联系与区别； 数据结构及其三个组成部分； 抽象数据类型和数据抽象； 评价算法优劣的标准及方法。,1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法的衡量 1.4.1 算法 1.4.2 算法设计的要求 1.4.3 算法效率的度量 1.4.4 算法的存储空间的需求,1.1 什么是数据结构 众所周知，计算机的程序是对信息进行处理。在大多数情况下，这些信息并不

5、是没有组织的，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。,(数据结构在软件开发中的地位),系统分析,系统设计,系统实现,系统维护,系统设计,1.1 什么是数据结构,Niklaus Wirth Algorithm + Data Structures = Programs,程序: 算法: 数据结构:,为计算机处理问题编制的 一组指令集,处理问题的策略,问题的数学模型(信息表示),一元二次方程求解,例如: 数值计算的程序设计问题, 代数方程组, 环流模式方程 (球面坐标系),全球天气预报,例一：电话号码查询系统,算法：? 模型：?,设有一个电话号码薄，它记录了N个人的名字和其相应

6、的电话号码，假定按如下形式安排： (a1，b1) (a2，b2)(an，bn) 其中(ai，bi)(i=1，2n) 分别表示某人的名字和对应的电话号码。要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的信息。,线性表(N个人的信息),非数值计算的程序设计问题,例二：人机对弈问题,算法：? 模型：?,树(棋盘和棋子),例三：铺设城市的煤气管道,算法：? 模型：?,如何规划使得总投资花费最少？,图(城市铺设点和铺设成本),概括地说，,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系

7、和操作等的学科。,1.2 基本概念和术语,一、数据与数据结构,二、数据类型,三、抽象数据类型,一、数据与数据结构,所有能被输入到计算机中，且能被计算机处理的符号(数值、字符等)的集合。,数据:,是计算机操作的对象的总称。,是计算机处理的信息的某种特定的符号表示形式。,是数据（集合）中的一个“个体”,在计算机中通常作为一个整体进行考虑和处理。是数据结构中讨论的基本单位。,数据元素:,如:整数5,字符N等。 -是不可分割的“原子”,其中每个款项称为一个“数据项”,它是数据结构中讨论的最小单位,数据元素也可以由若干款项构成。,例如：,描述一个学生的数据元素,称之为组合项,数据结构：,带结构的数据元素

8、的集合,有一个特性相同的数据元素的集合，如果在数据元素之间存在一种或多种特定的关系，则称为一个数据结构。,指的是数据元素之间存在的关系,例如，当用三个 4 位的十进制数表示一个含 12 位数的十进制数时，,3214,6587,9345 a1(3214),a2(6587),a3(9345),则在数据元素 a1、a2 和 a3 之间存在着“次序”关系 a1, a2、a2, a3,3214，6587，9345,6587，3214，9345,例如:,a1 a2 a3,a2 a1 a3,又例，在 2 行 3 列的二维数组中六个元素 a1, a2, a3, a4, a5, a6 之间存在两个关系:,行的次

9、序关系:,row = ,col = ,列的次序关系:,若在 6 个数据元素a1, a2, a3, a4, a5, a6 之间存在如下的次序关系:,| i=1, 2, 3, 4, 5,数据结构是相互之间存在着某种逻辑关系的数据元素的集合。,可见，不同的“关系”构成不同的“结构”,则构成一维数组的定义。,从关系或结构分，数据结构可归结为以下四类:,线性结构:,树形结构,图状结构,集合结构,结构中的数据元素之间存在一对一的关系。,结构中的数据元素之间存在一对多的关系。,结构中的数据元素之间存在多对多的关系。,结构中的数据元素除了同属于一种类型外，别无其它关系。,数据结构包括“逻辑结构” 和“物理结构

10、”两个方面(层次):,逻辑结构 是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系来表示;(形式定义）,物理结构 是逻辑结构在计算机中的表示和实现，故又称“存储结构” 。,数据结构的形式定义描述为:,数据结构是一个二元组 （逻辑结构）,Data_Structures = (D, S),其中:D 是数据元素的有限集， S 是 D上关系的有限集。,数据的存储结构, 逻辑结构在存储器中的映象,“数据元素”的映象 ？,“关系”的映象 ？,数据元素的映象方法：,用二进制位(bit)的位串表示数据元素,(321)10 = (501)8 = (101000001)2,A

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

12、整数为： int long_int3;,二、数据类型,在用高级程序语言编写的程序中，必 须对程序中出现的每个变量、常量或表 达式，明确说明它们所属的数据类型。,数据在真正用程序进行操作时，还必须对其进行类型分类。所以从抽 象数据类型的观点来讨论数据结构，已称为一种新的趋势，越来越被 人们所重视。 每个类型隐含或明显规定了在程序执行期间其变量或表达式允许取值 的范围以及允许进行操作。,整型数据类型：值的集合N2,1,0,1,2 一组操作：、x、/、%等 数据类型：基本类型和构造类型 基本类型：整型、浮点型、字符型 构造类型：数组、结构、联合、指针、枚举型、自定义,数据对象：某种数据类型元素的集合

13、。 例3、整数的数据对象是-3，-2，-1，0，1，2，3， 英文字符类型的数据对象是A，B，C，D，E，F，,数据类型 是一个值的集合和定义在此集合上的一组操作的总称。,1.3 抽象数据类型的表示与实现 每个类型隐含或明显规定了在程序 执行期间其变量或表达式允许取值的范 围以及允许进行操作。,例如：整型 值的范围是：-32768 32767 操作是：+，-，*，/，%,数据类型的抽象性：各种高级程序设计语言中都拥有“整数”类型，尽管它们在不同处理器上实现的方法不同，但对程序员而言是“相同的”，因为它们的数学特性相同。,从“数学抽象”的角度看，可称它为一个“抽象数据类型” 。,三、抽象数据类型

14、 (Abstract Data Type 简称ADT),是指一个数学模型（数据结构）以及定义在此数学模型上的一组操作,抽象数据类型是数据类型的扩展和抽象： 数据结构（数据对象D及其关系S） 定义在数据结构上的基本操作和算法（P）,ADT（抽象数据类型的两个重要特征）,数据抽象：用ADT描述程序处理的实体时，强调的是其本质的特征，其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。 数据封装：将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。如复数定义,例如，定义抽象数据类型“复数”,数据对象： De1,e2e1,e2RealSet 数据关系： R1 | e1是复

15、数的实数部分, | e2 是复数的虚数部分 ,ADT Complex ,基本操作：,AssignComplex( i=n;+i) for(j=1;j=n;+j) cij=0; for(k=1;k=n;+k) cij+=aik*bkj; ,一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作 T(n)=O(f(n) 它表示随问题规模n的增大，算法执行时间的增长率和 f(n)的增长率相同，称作算法的渐近时间复杂度，简称时 间复杂度。,由于是一个三重循环，每个循环从1到n，则总次数为: nnn=n3，时间复杂度为T(n)=O(n3),为了便于比较同一问题的不同算

16、法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该操作重复执行的次数作为算法的时间量度。,语句重复执行的次数也称为语句的频度： 例 +x;s=0; 将x自增看成是基本操作，则语句频度为，即时间复杂度为(1) 如果将s=0也看成是基本操作，则语句频度为1，其时间复杂度仍为(1)，即常量阶。 例 for(i=1;i=n;+i) +x;s+=x; 语句频度为：n其时间复杂度为：O(n) 即时间复杂度为线性阶。,显然，呗称作问题的基本操作的原操作应是其重复执行次数和算法的执行时间成正比的原操作， 多数情况下它是最深层循环内的语句中的原操作，它的执行次数和包含它

17、的语句的频度相同。 语句的频度指的是该语句重复执行的次数。,i=0: 赋值次,i=1: 赋值 2 次,i=2: 赋值3次,i=n-1:赋值n次,.,1+2+3+n=(1+n)n/2=n2/2+n/2,例 for(i=1;i=n;+i) for(j=1;j=n;+j) +x;s+=x; 语句频度为：n2 其时间复杂度为：O(n2) 即时间复杂度为平方阶。 例 for(i=0;i=n-1;+i) for(j=0;j=i;+j) aij=0; 其时间复杂度为：O(n2) 即时间复杂度为平方阶。 取语句频度增长最快的项。,一个算法时间为O(1)的算法，它的基本运算执行的 次数是固定的。因此，总的时间由

18、一个常数（即 零次多项式）来限界。而一个时间为O(n2)的算法 则由一个二次多项式来限界。,以下几种计算算法时间的多项式是最常用的。其关系为： 指数时间的关系为： O(2n)O(n!)O(nn) 当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。,最坏时间复杂性 平均时间复杂性,有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而 不同。例如： void bubble-sort(int a，int n) for(i=n-1;i0 ;i-) for(j=0;jaj+1) aj aj+1; 最好情况：0次 最坏情况：每次都换， (n2),由小到大排列,i=n-1: j从0到n-2 交换n-1次,.,(n-1)+(n-2)+(n-3)+1=(n-1)n/2=n2/2-n/2,i=n-2: j从0到n-3 交换n-2次,i=n-3: j从0到n-4 交换n-3次,i=1: j从0到0 交换1次,平均时间复杂性假设每种情况出现的概率相等，但很多情况下难以确定。,注意：时间与空间往往是对矛盾，要综合考虑。,1.4.4算法的存储空间需求 空间复杂度:算法所需存储空间的度量，记作: S(n)=O(f(n) 其中n为问题的规模(或大小),1输入数据所占空间,2程序本身所占空间；,3辅助变量所占空间。,本章学习要点,熟悉各名词、术语的含义，掌握基本概念； 理解算