计算机软件及应用数据结构绪论PPT课件

1、11.2 基本概念数据：指所有能被输入到计算机中，且能被计算机处理的。是计算机操作的。数据元素:是数据结构中讨论的单位。在计算机程序中作为一个“”进行考虑。一. 数据和数据结构第1页/共47页2数据项：是数据结构中讨论的的单位。数据对象:是的数据元素的集合，如:一个班级的成绩表可以看作一个数据对象。它是数据的一个子集。数据结构：若在特性相同的数据元素集合中的数据元素之间存在一种或多种特定的关系，则称该数据元素的集合为“数据结构“。数据结构是带“结构”的数据元素的集合。 第2页/共47页3数据结构是一个二元组 Data_Structures = (D, S)其中: D 是数据元素的有限集， S

2、是 D上关系的有限集。第3页/共47页4二. 数据类型在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。 【例】C/C+语言中提供的基本数据类型有:整 型 int浮 点 型 float字符型 char逻辑型 bool （ C+语言）双精度型 double1.2 基本概念第4页/共47页5第5页/共47页6三. 抽象数据类型 (Abstract Data Type , ADT)抽象数据类型：是指一个数学模型以及定义在此数学模型上的一组操作。即：ADT的定义由一个值域和定义在该值域上的一组操作组成。ADT的定义仅取决于数据模型的逻辑特征。ADT和数

3、据类型实质上是一个概念。与其在计算机内部的表示和实现无关。“抽象”的意义在于数据类型的数学抽象特性。不论内部结构如何变化，都不会影响外部使用。第6页/共47页7例：线性表这样的抽象数据类型。 数学模型数学模型：数据元素的集合；：数据元素的集合； 该集合内的元素的该集合内的元素的关系关系：除第一个和最后一个外，每个元素有唯一的前趋和唯：除第一个和最后一个外，每个元素有唯一的前趋和唯一的后继；一的后继； 操作操作：插入一个元素、删除一个元素等。：插入一个元素、删除一个元素等。 第7页/共47页8抽象数据类型不仅仅局限于固有数据类型，也包括用户自定义的数据类型。ADT 按照其值的不同特性，分为4种类

4、型：原 子 类 型：其值不可分解的类型；如：int固定聚合类型：其值由确定数目的成分按某种结构组成；如：复数；可变聚合类型：其值由不固定数目的成分按某种结构组成；如：学生基本情况，有序整数序列；多形数据类型：其值的成分不确定的数据类型；（元素之间的关系相同，基本操作也相同 ）第8页/共47页92. 数据封装：将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。1. 数据抽象：用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。第9页/共47页10抽象数据

5、类型可用三元组表示:ADT =（D，S，P）其中：D 是数据对象； S 是 D 上的关系集； P 是对 D 的基本操作集。 第10页/共47页11数据结构是一个二元组 Data_Structures = (D, S)其中: D 是数据元素的有限集， S 是 D上关系的有限集。第11页/共47页12ADT 抽象数据类型名 数据对象：数据对象的定义-D 数据关系：数据关系的定义-S 基本操作：基本操作的定义-P ADT抽象数据类型名基本操作的定义格式为:基本操作名（参数表） 初始条件：初始条件描述 操作结果：操作结果描述 其中，数据对象和数据关系的定义用伪码描述第12页/共47页131.参数表：赋

6、值参数: 只为操作提供输入值。引用参数: 以&打头，除可提供输入值外，还将返回操作结果。2. 初始条件: 描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若初始条件为空，则省略之。3. 操作结果: 说明了操作正常完成之后，数据结构的变化状况和应返回的结果。第13页/共47页14【例】抽象数据类型 复数 的定义：数据对象：De1, e2e1,e2RealSet 数据关系：R1 | e1是复数的实数部分， | e2 是复数的虚数部分 ADT Complex 第14页/共47页15基本操作：AssignComplex( &Z, v1, v2 )

7、操作结果：构造复数 Z,其实部和虚部分别被赋以参数 v1 和 v2 的值。DestroyComplex( &Z)操作结果：复数Z被销毁。 GetReal( Z, &realPart )初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。第15页/共47页16GetImag( Z, &ImagPart )初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。Add( z1,z2, &sum )初始条件：z1, z2是复数。操作结果：用sum返回两个复数z1, z2 的和值。 ADT Complex假设:z1和z2是上述定义的复数则

8、 Add(z1, z2, z3) 操作的结果即为用户需要的结果z3 = z2 + z1第16页/共47页17抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。【例】利用C+语言实现的复数类型如下描述：第17页/共47页18typedef struct float realpart； float imagpart； complex；/ -存储结构的定义/ -基本操作的函数原型说明void Assign( complex &Z, float realval, float imagval )；/ 构造复数 Z,其实部和虚部分别被赋以参数/ realval 和 imag

9、val 的值第18页/共47页19float GetReal( cpmplex Z )； / 返回复数 Z 的实部值float Getimag( cpmplex Z )； / 返回复数 Z 的虚部值void add( complex z1, complex z2, complex &sum )； / 以 sum 返回两个复数 z1, z2 的和第19页/共47页20/ -基本操作的实现void add( complex z1, complex z2, complex &sum ) / 以 sum 返回两个复数 z1, z2 的和 sum.realpart = z1.realpa

10、rt + z2.realpart; sum.imagpart = z1.imagpart + z2.imagpart; 其它省略 第20页/共47页211.3 算法和算法的衡量一. 算法算法:算法是对特定问题求解步骤的一种描述, 是指令的有限序列，其中每一条指令表示一个或多个操作。一个算法必须满足以下五个重要特性：1有穷性 2确定性 3可行性4有输入 5有输出第21页/共47页221有穷性: 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，且每一步骤都能在有限时间内完成。2确定性: 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且

11、在任何条件下，算法都只有一条执行路径。3可行性: 算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。第22页/共47页234有输入：零个或多个的输入。作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。5有输出：一个或多个的输出。它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。第23页/共47页24有穷性？不是一个算法！ 第24页/共47页25二. 算法设计的原则设计算法时，通常应考虑达到以下目标：1正确性2. 可读性3健壮性4高效率与低存储量

12、需求第25页/共47页261正确性算法应当满足以特定的“规格说明”方式给出的需求。对算法是否“正确”的理解可以有以下四个层次：a程序中不含语法错误；b程序对于几组输入数据能够得出满足要求的结果； c程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果； d程序对于一切合法的输入数据都能得出满足要求的结果；通常以第 c 层意义的正确性作为衡量标准。第26页/共47页272. 可读性算法主要是为了人的阅读与交流，其次才是为计算机执行，因此算法应该易于人的理解；另一方面，难读的程序易于隐藏较多错误而难以调试。3健壮性当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，

13、而不是产生莫名奇妙的输出结果处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便进行处理第27页/共47页284高效率与低存储量需求通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。第28页/共47页29 算法与程序的区别算法与程序的区别 算法算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有个问题可以有多个多个算法。算法。 程序程序是用某种程序设计语言对是用某种程序设计语言对算法的具体实现。算法的具体实现。 主要区别：有穷性、正确性

14、和描述方法 程序可以是程序可以是无穷无穷的，例如的，例如OS，算法是，算法是有穷有穷的；的； 程序可以是程序可以是错误错误的，而算法必须是的，而算法必须是正确正确的；的； 程序是用程序是用程序设计语言描述程序设计语言描述的，在机器上可以执行，算法还可以用的，在机器上可以执行，算法还可以用自然语自然语言、框图、高级程序语言言、框图、高级程序语言等方式描述。等方式描述。第29页/共47页30三. 算法效率的衡量方法和准则 事后统计缺点：1必须执行程序 2其它因素掩盖算法本质第30页/共47页31和算法执行时间相关的因素： 算法选用的策略 问题的规模 编写程序的语言 编译程序产生的机器代码的质量 计

15、算机执行指令的速度事前分析第31页/共47页32第32页/共47页第33页/共47页第34页/共47页35算法 = 控制结构 + 原操作（固有数据类型的操作）算法的执行时间 = （原操作(i)的执行次数原操作(i)的执行时间）算法的执行时间 与 原操作执行次数之和 成正比 通常，从算法中选取一种对于所研究的问题来说是 基本操作 的原操作，以该基本操作 在算法中重复执行的次数 作为算法运行时间的衡量准则。第35页/共47页36例:求下列程序段各语句的频度频度。 (1)for(i=1; i=n;i+) n+1(1)for(i=1; i=n;i+) n+1 x+; n x+; n(2) for(j=

16、1;j=n;j+) n+1 for(k=1;k=n;k+) n*(n+1) x+; n*n 第36页/共47页37(1)i=1; k=0;while (i=n-1) k+=10*i; i+;语句频度T(n)i=1; k=0;do k+=10*i; i+; while (i=n-1)(2)语句频度T(n)=n-1=n-1第37页/共47页38(3)k=0;for(i=1;i=n;i+) for(j=i;j=n;j+) k+;i=1时；j循环n次i=2时；j循环n-1次i=n时；j循环1次语句频度T(n) =n+(n-1)+1=(n-1+1)*(n+1)/2第38页/共47页39【例】两个NN矩阵

17、相乘void mult(int a, int b, int& c ) / 以二维数组存储矩阵元素，c 为 a 和 b 的乘积 for (i=1; i=n; +i) / n+1 for (j=1; j=n; +j) /n*(n+1) ci,j = 0; /n*n for (k=1; k1 & change; - -i) /n-1次change = FALSE; / change 为元素进行交换标志 for (j=0; j aj+1) aj aj+1; change = TRUE ; / (n-2)*i / 一趟起泡 / bubble_sort基本操作:比较操作时间复杂度: O(n

18、2)第40页/共47页411i0j11n2)n(Ti1n2)1.111(i1n2)101i (i1n2ii2)/2-(n*1)n(2/)12)1n(*2)1n(1)n(.32)n(O2第41页/共47页42void select_sort(int& a, int n) / 将 a 中重新排列成自小至大有序的整数序列。 for ( i = 0; i n-1; +i ) j = i; / 选择第 i 个最小元素for ( k = i+1; k n; +k ) if (ak aj ) j = k; if ( j != i ) aj ai / select_sort【例】选择排序基本操作: 比较(数据元素)操作时间复杂度: O(n2)除