《数据结构耿国华高教版 第1章课件》由会员分享，可在线阅读，更多相关《数据结构耿国华高教版 第1章课件（81页珍藏版）》请在金锄头文库上搜索。
1、2020/8/29,1,西北师范大学经济管理学院 -信息管理系,本演示文稿可能包含观众讨论和即席反应。使用 PowerPoint 可以跟踪演示时的即席反应， 在幻灯片放映中，右键单击鼠标 请选择“会议记录” 选择“即席反应”选项卡 必要时输入即席反应 单击“确定”撤消此框 此动作将自动在演示文稿末尾创建一张即席反应幻灯片，包括您的观点。,数据结构课件,用C语言描述,2020/8/29,2,第1章 绪 论,1.7 关于学习数据结构,1.1 数据结构的基本概念(定义),1.2 数据结构的内容（研究范围）,1.3 算法设计,1.4 算法描述工具,1.5 对算法作性能评价,1.6 数据结构与C语言表示
2、,2020/8/29,3,1.1 数据结构的基本概念（定义）,数据结构的相关名词： 数据（Data） 数据元素（Data Element） 数据对象（Data Object） 数据结构（Data Structure） 数据类型(Data Type) 数据抽象与抽象数据类型,2020/8/29,4,数据（Data）,定义： 数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。 数据包含整型、实型、布尔型、图象、字符、声音等一切可以输入到计算机中的符号集合。,例如对C源程序,2020/8/29,5,数据元素（Data Element）,定义： 数据元素是组成数据的基本单位 ，是数
3、据集合的个体，在计算机中通常作为一个整体进行考虑和处理。例如：,2020/8/29,6,数据对象（Data Object）,定义： 数据对象是性质相同的数据元素的集合，是数据的一个子集。,整数集合：N=0，1，2， 无限集 字符集合：C=A，B，Z 有限集,例如：,2020/8/29,7,数据结构（Data Structure）,定义： 数据结构是指相互之间存在一种或多种特定关系的数据元素集合，是带有结构的数据元素的集合，它指的是数据元素之间的相互关系，即数据的组织形式。 例如表结构：,2020/8/29,8,数据结构（Data Structure）,树型结构,图结构,2020/8/29,9,
4、数据类型(Data Type),定义： 数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。,如在高级语言中，整型类型的取值范围为： -32768+32767，运算符集合为加、减、乘、除、取模，即+、-、*、/、%。,2020/8/29,10,数据类型(Data Type),高级语言中的数据类型分为两大类：,1.原子类型，其值不可分解。如C语言中的标准类型（整型、实型、字符型、）。,2.结构类型，其值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是非结构的，也可以是结构的。,指针类型属于哪种类型？,2020/8/29,11,数据抽象与抽象数据类型,数据的抽象
5、 抽象数据类型(Abstract Data Type) 抽象数据类型实现 ADT的表示与实现 面向对象的概念 结构化的开发方法与面向对象开发方法不同点,2020/8/29,12,1.2 数据结构的内容,逻辑结构 存储结构 运算集合,2020/8/29,13,逻辑结构,定义： 数据的逻辑结构是指数据元素之间逻辑关系描述。,形式化描述： Data_Structure=（D,R）其中D是数据元素的有限集，R是D上关系的有限集。,四类基本的结构 集合结构、线性结构、树型结构、图状结构。,2020/8/29,14,集合结构,定义： 结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。,例如：
6、,2020/8/29,15,线性结构,定义： 结构中的数据元素之间存在着一对一的线性关系。,例如：,2020/8/29,16,树型结构,定义： 结构中的数据元素之间存在着一对多的层次关系。,例如：,2020/8/29,17,图状结构或网状结构,定义： 结构中的数据元素之间存在着多对多的任意关系。,例如：,2020/8/29,18,综上所述，数据的逻辑结构可概括为：,逻辑结构,2020/8/29,19,存储结构,定义： 存储结构（又称物理结构）是逻辑结构在计算机中存储映象，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。,形式化描述： D要存入机器中，建立一从D的数据元素到存储空间
7、M单元映象S ，DM，即对于每一个d， dD,都有唯一的zM使S（D）=Z, 同时这个映象必须明显或隐含地体现关系R。,2020/8/29,20,逻辑结构与存储结构的关系为：,存储结构是逻辑关系的映象与元素本身映象，是数据结构的实现；逻辑结构是数据结构的抽象。,数据元素之间关系在计算机中的表示方法： 顺序映象 （顺序存储结构） 非顺序映象（非顺序存储结构）,存储结构,2020/8/29,21,运算集合,例如工资表：,2020/8/29,22,数据结构的内容,综上所述，数据结构的内容可归纳为三个部分， 逻辑结构、存储结构和运算集合： 按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计
8、算机存贮器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。,2020/8/29,23,1.3 算法,算法（Algorithm）定义 算法的特性 算法设计的要求,2020/8/29,24,算法（Algorithm）定义,定义： Algorithm is a finite set of rules which gives a sequence of operation for solving a specific type of problem. 算法是规则的有限集合，是为解决特定问题而规定的一系列操作。,2020/8/29,25,算法的特性,1. 有限性：有限步骤之内正常结束，不能形成无
9、穷循环,2. 确定性：算法中的每一个步骤必须有确定含义，无二 义性得以实现。,3. 输 入： 有多个或0个输入,4. 输 出： 至少有一个或多个输出。,5. 可行性：原则上能精确进行，操作可通过已实现基本 运算执行有限次而完成。,2020/8/29,26,算法设计的要求,算法的正确性,算法特征：,可读性,健壮性,高效率和低存储量,例如要求n个数的最大值问题 给出算法如下： max:=0; for（i=1 ；imax) max=x; ,2020/8/29,27,1.4 算法描述的工具,概述： 算法+数据结构=程序 算法、语言、程序的关系 设计实现算法过程步骤 类描述算法的语言选择,2020/8/
10、29,28,算法、语言、程序的关系,1. 算法：描述了数据对象的元素之间的关系（包括数据逻辑关系、存贮关系描述）。,2. 描述算法的工具：算法可用自然语言、框图或高级程序设计语言进行描述。,3.程序是算法在计算机中的实现。,2020/8/29,29,设计实现算法过程步骤,1. 找出与求解有关的数据元素之间的关系,2. 确定在某一数据对象上所施加运算,3. 考虑数据元素的存储表示,4. 选择描述算法的语言,5.设计实现求解的算法，并用程序语言加以描述。,2020/8/29,30,类描述算法的语言选择,类语言：,类语言是接近于高级语言而又不是严格的高级语言，具有高级语言的一般语句设施，撇掉语言中的
11、细节，以便把注意力主要集中在算法处理步骤本身的描述上。,2020/8/29,31,3.赋值语句,对C语言作以下描述：,（1）简单赋值,1）变量名=表达式 2） 变量+， 3） 变量- -，,（2）串联赋值,变量1=变量2=变量3=变量k=表达式,2020/8/29,32,对C语言作以下描述：,（4）条件赋值,变量名=条件表达式？表达式1:表达式2,（3）成组赋值,(, ,) 数组名1下标1下标2=数组名2下标1下标2,2020/8/29,33,4.条件选择语句,对C语言作以下描述：,if () 语句;,if () 语句1; else 语句2;,2020/8/29,34,情况语句,switch
12、(） case 判断值1: 语句组 1； break; case 判断值2: 语句组 2； break; ,case 判断值n: 语句组n; break; default: 语句组； break; ,对C语言作以下描述：,2020/8/29,35,对C语言作以下描述：,5.循环语句,for 语句,for (；） 循环体语句；,2020/8/29,36,while 语句,while (） 循环体语句； ,对C语言作以下描述：,do while 语句,do 循环体语句 while (）,2020/8/29,37,1.5 对算法作性能评价,评价算法的标准： 评价一个算法主要看这个算法所占用机器资源的
13、多少，而这些资源中时间代价与空间代价是两个主要的方面，通常是以算法执行所需的机器时间和所占用的存储空间来判断一个算法的优劣。 性能评价 有关数量关系计算,2020/8/29,38,性能评价,定义： 对问题规模与该算法在运行时所占的空间S与所耗费的时间T给出一个数量关系的评价。,问题规模N对不同的问题其含义不同： 对矩阵是阶数； 对多项式运算是多项式项数； 对图是顶点个数； 对集合运算是集合中元素个数。,2020/8/29,39,有关数量关系计算,数量关系评价体现在时间算法在机器中所耗费时间。 数量关系评价体现在空间算法在机器中所占存储量。 关于算法执行时间 语句频度 算法的时间复杂度 数据结构
14、中常用的时间复杂度频率计数 最坏时间复杂度 算法的空间复杂度,2020/8/29,40,关于算法执行时间,定义： 一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。,分析： 不是针对实际执行时间的精确地算出算法执行具体时间，而是针对算法中语句的执行次数做出估计，从中得到算法执行时间的信息。,2020/8/29,41,语句频度,定义： 语句频度是指该语句在一个算法中重复执行的次数。,例如： 两个矩阵相乘,算法语句 对应的语句频度 1for（i=0；i n;i+） n 2for （j=0；jn;j+） n2 3 cij=0; n
15、2 4 for (k=0;k n; k+) n3 cij=cij+aik*bkj; n3 总执行次数：Tn=2n3+2n2 +n,2020/8/29,42,算法的时间复杂度,算法的时间复杂度，即是算法的时间量度记做： T(n)=O(f(n),例如给出X=X+1,（1）x=x+1 ；时间复杂度为O(1)，称为常量阶；,（2）for (i=1; i= n; i+) x=x+1; 时间复杂度为O(n)，称为线性阶；,（3）for (i=1; i= n; i+) for (j=1;j= n; j+) x=x+1; 时间复杂度为O(n2), 称为平方阶。,2020/8/29,43,常用的时间复杂度频率计
16、数,数据结构中常用的时间复杂度频率计数有7个:,O(1) 常数型 O(n)线性型 O(n2)平方型 O(n3)立方型 O(2n)指数型 O(log2n)对数型 O(nlog2n)二维型,按时间复杂度由小到大排列的频率表：,2020/8/29,44,常用的时间复杂度频率计数,常用的时间复杂度频率表：,2020/8/29,45,最坏时间复杂度,定义： 讨论算法在最坏情况下的时间复杂度，即分析最坏情况下以估计出算法执行时间的上界。,例如冒泡排序算法,2020/8/29,46,void bubble(int a, int length) 将a中整数数组重新排序，达到递增有序 int i=0, j, temp
