《数据结构讨论的范畴.ppt》由会员分享，可在线阅读，更多相关《数据结构讨论的范畴.ppt（68页珍藏版）》请在三一办公上搜索。
1、第一章绪 论,1.1 数据结构讨论的范畴,1.2 与数据结构相关的概念,1.3 算法和算法的量度,软件开发的过程:,系统分析,系统实现,系统维护,系统设计,系统设计,确定系统所要达到的目标,确定实现方案并生成系统,实地安装调试,系统修整完善,Niklaus Wirth Algorithm+Data Structures=Programs,程序设计:算法:数据结构:,为计算机处理问题编制 一组指令集,处理问题的策略,问题的数学模型,例如:,鸡兔同笼问题,二元一次代数方程组,结构静力分析问题,全球天气预报,高次线性代数方程组,球面坐标系下的环流模式方程,非数值计算的程序设计问题,例一 求一组(n个
2、)整数中的最大值,例二 交叉路口的交通管制问题,例三 煤气管道的铺设问题,例四 数据库中表格管理问题,概括地说，,数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。,一、基本概念和术语,二、数据结构,三、数据类型和抽象数据类型,所有能被输入到计算机中，且能被计算机处理的符号(数字、字符等)的集合。,数据,是计算机操作的对象的总称。,是计算机处理的信息的某种特定的符号表示形式。,是数据（集合）中的一个“个体”,在计算机中通常作为一个整体进行考虑和处理。是数据结构中讨论的基本单位。,数据元素,例如，整数“5”,字符“N”等。-是不可分割的“原
3、子”,它是数据结构中讨论的最小单位。,又如,描述一个学生的数据元素由多个款项构成，其中每个款项称为一个“数据项”。,称之为组合项,原子项,关键字,能识别一个或几个数据元素的数据项。若能起唯一识别作用，则被称为“主”关键字，否则称为“次”关键字。,数据对象,具有相同特性的数据元素的集合。如:整数、实数等。,数据结构,带结构的数据元素的集合,有一个特性相同的数据元素的集合，如果在数据元素之间存在一种或多种特定的关系，则称为一个数据结构。,指的是数据元素之间存在的关系,例如，可用三个 4 位的十进制数表示一个含 12 位数的“长整数”。,3214,6587,9345 a1(3214),a2(6587
4、),a3(9345),对长整数进行运算的程序中的操作对象是一个含三个数据元素a1,a2,a3的集合，且三者之间存在下列“次序”关系:a1,a2、a2,a3。,又如，在 2 行 3 列的二维数组中六个元素 a1,a2,a3,a4,a5,a6之间存在着两个关系:,“行”的次序关系:,row=,col=,“列”的次序关系:,在含 6 个数据元素a1,a2,a3,a4,a5,a6 的集合上存在如下的次序关系:,|i=1,2,3,4,5,“数据结构”是相互之间存在着某种逻辑关系的数据元素的集合。,可见，不同的“关系”构成不同的“结构”,则构成“一维数组”。,可用如下的数据结构描述“班集体”:,班主任，班
5、长1，班长2，舍长1，舍长p,学生1，学生2，学生n,，,，,数据结构的形式定义描述为:,数据结构是一个二元组,Data_Structures=(D,S),其中:D 是数据元素的有限集，S 是 D上关系的有限集。,从关系或结构分，数据结构可归结为以下四类:,线性结构,树形结构,图状结构,集合结构,数据结构包括“逻辑结构”和“物理结构”两个方面(层次):,逻辑结构 是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系来表示;,物理结构 是逻辑结构在计算机中的表示和实现，故又称“存储结构”。,存储结构是逻辑结构在存储器中的映象,“数据元素”的映象？,“关系”的映象
6、？,用二进制位(bit)的位串表示数据元素,(321)10=(501)8=(101000001)2,A=(101)8=(001000001)2,“关系”的两种映象方法：,（表示x,y的方法）,顺序映象,以 x 和 y 之间相对的存储位置表示后继关系,例如:令 y 的存储位置和 x 的存储位置之间相差一个预设常量 C，而 C 是一个隐含值，,存储结构中只包含数据元素本身的信息,链式映象,以附加信息(指针)表示后继关系,需要用一个和 x 绑定在一起的附加信息(指针)指示 y 的存储位置,以“由数据元素 x 的存储映象和附加的指针合成的结点”表示数据元素。,存储结构的描述方法随编程环境的不同而不同，
7、,当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。,typedef int Long_int 3,例如，当以“顺序映象”表示长整数时，可定义为:,定义“日期”为:typedef struct int y;/年号 Year int m;/月号 Month int d;/日号 Day DateType;/日期类型,定义“学生”为:typedef struct char id8;/学号 char name16;/姓名 char sex;/性别M/F:男/女 DateType bdate;/出生日期 Student;/学生类型,何谓“数据类型”？,在用高级程序语言编写的程序
8、中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。,例如，C+语言中的基本数据类型有:,逻辑型 bool、字符型 char、整型 int 和 实型(浮点型 float和双精度型 double),数据类型是一个“值”的集合和定义在此集合上的“一组操作”的总称。,对程序员而言，各种语言中的整数类型都是一样的，因为它们的数学特性相同。,从这个意义上可称“整数”是一个抽象数据类型。,抽象数据类型和数据类型的实质相同，范畴更广，不局限于语言中的数据类型。,抽象数据类型(Abstract Data Type 简称ADT)是指一个数学模型以及定义在该模型上的一组操作。,通常称语言中已
9、经实现的数据类型为固有数据类型。,抽象数据类型有两个重要特征:,“数据抽象”和“数据封装”,数据抽象,数据封装,用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。,将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节,抽象数据类型的描述方法,ADT=（D，S，P）,其中:D 是数据对象，S 是 D 上的关系集，P 是对 D 的基本操作集。,数据对象是特性相同的数据元素的集合，是数据的一个子集。,例如,抽象数据类型“复数”的定义:,R1|e1是复数的实数部分,|e2 是复数的虚数部分,ADT Complex,数据对
10、象：,De1,e2e1,e2RealSet,数据关系：,基本操作：,AssignComplex(&Z,v1,v2)操作结果：构造复数 Z,其实部和虚部 分别被赋以参数 v1 和 v2 的值。,DestroyComplex(&Z)操作结果：复数 Z 被销毁。,GetReal(Z,&realPart)初始条件：复数 Z 已存在。操作结果：用 realPart 返回复数 Z 的实部值。,GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart 返回复数 Z 的虚部值。,Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum 返回两个复数 z1,
11、z2 的和值。,ADT Complex,#include#include complex.hvoid main(),complex z1,z2,z3,z4,z;float RealPart,ImagPart;InitComplex(z1,8.0,6.0);InitComplex(z2,4.0,3.0);Add(z1,z2,z3);Multiply(z1,z2,z4);if(Division(z4,z3,z)GetReal(z,RealPart);GetImag(z,ImagPart);/if,ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义
12、ADT 抽象数据类型名,其中基本操作的定义格式为:,基本操作名（参数表）初始条件：初始条件描述 操作结果：操作结果描述,赋值参数 只为操作提供输入值；引用参数 以&打头，除可提供输入值外，还将返回操作结果。,初始条件 描述操作执行之前的数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。,操作结果 说明在操作正常完成之后，数据结构的变化状况和应返回的结果。,初始条件可以为空，并可省略。,抽象数据类型的表示和实现,抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。,例如，对之前定义的复数类型,typedef struct float realpart；f
13、loat imagpart；complex；,/-存储结构的定义,/-基本操作的函数原型说明,void Assign(complex&Z,float realval,float imagval)；/构造复数 Z,其实部和虚部分别被赋以参数/realval 和 imagval 的值,float GetReal(cpmplex Z)；/返回复数 Z 的实部值,float Getimag(cpmplex Z)；/返回复数 Z 的虚部值,void add(complex z1,complex z2,complex&sum)；/以 sum 返回两个复数 z1,z2 的和,/-基本操作的实现,void a
14、dd(complex z1,complex z2,complex,一、算法的定义,二、算法设计的原则,三、算法效率的衡量方法和准则,四、算法的存储空间需求,是为了解决某类问题而规定的一个有限长的操作序列。,3可行性,一个算法必须满足以下五个重要特性：,算法,1有穷性,2确定性,5有输出,4有输入,有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束。算法中的每个步骤都能在有限时间内完成。,确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。,可行性 算法中的所有操作都必须足够基本，都可以
15、通过已经实现的基本操作运算有限次实现之。,有输入 作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。,有输出 它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。,设计算法时，通常应考虑达到以下目标：,1正确性,2.可读性,3健壮性,4高效率与低存储量需求,正确性,首先，算法应当满足以特定的“规格说明”方式给出的需求。,其次，对算法是否“正确”的理解可以有以下四个层次：,a不含语法错误；,b对于某几组输入数据能够得出满足要求的结果；,c程序对于精心选择的、典型
16、、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；,通常以第 c 层意义的正确性作为衡量一个算法是否合格的标准。,d程序对于一切合法的输入数据都能得出满足要求的结果；,可读性,算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试；,健壮性,当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。,高效率与低存储量需求,存储量指的是算法执行过程中所需的最大存储空间。,两者都
17、与问题的规模有关。,效率指的是算法执行时间；,通常有两种衡量算法效率的方法:,事后统计法,事前分析估算法,缺点：1.必须执行程序 2.其它因素掩盖算法本质,优点：可以预先比较各种算法，以便 均衡利弊从中选优。,和算法执行时间相关的因素：,1算法选用的策略,2问题的规模,3编写程序的语言,4编译程序产生的机器代码的质量,5计算机执行指令的速度,算法选用的策略,问题的规模,一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量 n 表示），或者说，它是问题规模的函数。,假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n)的增长率相同，则可记作：,T(n)=O(f(n),称
18、 T(n)为算法的(渐近)时间复杂度,如何估算 算法的时间复杂度？,算法=控制结构+原操作（固有数据类型的操作）,算法的执行时间=(原操作(i)的执行次数原操作(i)的执行时间),算法的执行时间 与 原操作执行次数之和 成正比,从算法中选取一种对于所研究的问题来说是 基本操作 的原操作，以该基本操作 在算法中重复执行的次数 作为算法运行时间的衡量准则。,“基本操作”指的是，该操作重复执行次数和算法的运行时间成正比。,例一两个矩阵相乘,void mult(int a,int b,int/for/mult,基本操作:乘法操作,时间复杂度:O(n3),for,for,for,*,void selec
19、t_sort(int&a,int n)/将 a 中整数序列重新排列成自小至大有序的整数序列。/select_sort,for(i=0;i n-1;+i),例二选择排序,基本操作:比较(数据元素)操作,时间复杂度:O(n2),j=i;/选择第 i 个最小元素for(k=i+1;k n;+k)if(ak aj)j=k;,if(j!=i)aj ai;,例三起泡排序,void bubble_sort(int-i)/bubble_sort,基本操作:赋值操作,时间复杂度:O(n2),change=FALSE;/change 为元素进行交换标志 for(j=0;j aj+1)aj aj+1;change=
20、TRUE;/一趟起泡,for,for,算法的空间复杂度定义为:,表示随着问题规模 n 的增大，算法运行所需存储量的增长率与 g(n)的增长率相同。,S(n)=O(g(n),算法的存储量包括:,1输入数据所占空间,2程序本身所占空间；,3辅助变量所占空间。,若输入数据所占空间只取决与问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。,若所需额外空间相对于输入数据量来说是个常量，则称此算法为原地工作。,若所需存储量依赖于特定的输入，则通常按最坏情况考虑。,1.熟悉各名词、术语的含义，掌握基本概念。,2.理解算法五个要素的确切含义。,本章学习要点,3.掌握计算语句频度和估算算法时间复杂度的方法。,提几点要求:,1.课前预习，了解本堂课内容;,2.课后复习，在理解教学内容的基础上 做练习题;,3.独立完成作业;,4.勤答疑，多问“为什么”。,(n-1)+(n-2)+1=n(n-1)/2=n2/2+n/2,312597,13,23,5,79,12357,519732,15,9,79,39,15,29,7,37,27,15,35,25,13,23,12,9,7,5,3,2,
