数据结构课件(第一章).ppt

《数据结构课件(第一章).ppt》由会员分享，可在线阅读，更多相关《数据结构课件(第一章).ppt（58页珍藏版）》请在三一办公上搜索。

1、数据结构课程地位,数据结构与其它课程关系图：,参考书籍：,数据结构（C语言版）严蔚敏 吴伟民 清华大学出版社数据结构题集(C语言版)严蔚敏 清华大学出版社数据结构学习指导与典型题解朱战立 西安交通大学出版社数据结构与程序设计C语言描述(第2版)(Data Structure&Program Design in C)Robert L.Kruse 2001-9清华大学出版社数据结构及应用算法教程(配软盘)严蔚敏 陈文博 清华大学出版社数据结构（C语言篇）习题与解析（修订版）李春葆 清华大学出版社C/C+与数据结构 王立柱 编著 清华大学出版社,关于本书内容说明,本书基本结构 第一部分：数据结构的基

2、本概念（第1章）第二部分：基本的数据结构 包括：线性结构线性表、栈和队列、串、数组与广义表（第25章）非线性结构树、图（第6、7章）第三部分：基本技术 包括：查找技术与排序技术（第8、9、10章）,返回,西安工程大学 计算机科学学院,第一章 绪论,内容简介,1.1 什么是数据结构1.2 数据结构的内容1.3 算法1.4 算法描述的工具 1.5 对算法作性能评价1.6 关于学习数据结构,1.1 什么是数据结构（定义）,数据结构的相关名词：数据（Data）数据元素（Data Element）数据对象（Data Object）数据结构（Data Structure）数据类型(Data Type)数据

3、抽象与抽象数据类型,返回,数据（Data）,定义：数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。数据包含整型、实型、布尔型、图象、字符、声音等一切可以输入到计算机中的符号集合。例如对C源程序 源程序 目标程序 可执行程序（.c）（.obj）（.exe）,C编译程序,C链接程序,return,数据元素（Data Element）,定义：数据元素是组成数据的基本单位，是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。例如：,数据项,数据元素,return,数据对象（Data Object）,定义：数据对象是性质相同的数据元素的集合，是数据的一个子集。例如：整数集合

4、：N=0，1，2，无限集 字符集合：C=A，B，Z 有限集,return,数据结构（Data Structure）,定义：数据结构是指相互之间存在一种或多种特定关系的数据元素集合，是带有结构的数据元素的集合，它指的是数据元素之间的相互关系，即数据的组织形式。例如表结构：,数据结构（Data Structure）,树形结构,return,数据类型(Data Type),定义：数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。如在高级语言中，整型类型的取值范围为：-32768+32767，运算符集合为加、减、乘、除、取模，即+、-、*、/、%。,数据类型(Data Type),

5、高级语言中的数据类型分为两大类：1.原子类型，其值不可分解。如C语言中的标准类型（整型、实型、字符型）及指针。2.结构类型，其值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是非结构的，也可以是结构的。,return,数据抽象与抽象数据类型,数据的抽象抽象数据类型(Abstract Data Type)ADT的表示与实现,数据的抽象,汇编语言中十进制表示的数据98.65、9.6E3等,它们是二进制数据的抽象;高级语言中，给出更高一级的数据抽象，如整型、实型、字符型等;还可以进一步定义更高级的数据抽象，如各种表、队、栈、树、图、窗口、管理器等复杂的抽象数据类型。,return,

6、抽象数据类型(Abstract Data Type),定义：抽象数据类型（简称ADT）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。一个抽象数据类型确定了一个模型，但将模型的实现细节隐藏起来；它定义了一组运算，但将运算的实现过程隐藏起来。,抽象数据类型(Abstract Data Type),线性表的抽象数据类型的描述：ADT Linear_list数据元素 所有ai属于同一数据对象，i=1，2，n,n=0；逻辑结构 所有数据元素ai（i=1，2，n-1）存在次序关系，a1无前趋，an无后继；操作 设L为Linear_listInitial(L)初始化空线性表；Length(

7、L)求线性表的表长；Get(L,i)取线性表的第i个元素；Insert(L,i,b)在线性表的第i个位置插入元素b；Delete(L,i)删除线性表的第i个元素；,return,ADT的表示与实现,ADT的定义：ADT 数据对象:结构关系:基本操作:ADT 基本操作的定义格式为：(参数表)操作前提:操作结果:,ADT的表示与实现,关于参数传递 参数表中的参数有值参和变参两种。用标准C语言表示和实现ADT描述时，主要有两个方面：(1)通过结构体将int、float等固有类型组合到一起,构成一个结构类型,再用typedef为该类型或该类型指针重新起一个名字。(2)用C语言函数实现各操作。基本操作包

8、括插入、删除、更新、查找、排序等。,return,1.2 数据结构的内容,逻辑结构 存储结构 运算集合,返回,逻辑结构,定义：数据的逻辑结构是指数据元素之间逻辑关系描述。形式化描述：Data_Structure=（D,R）其中D是数据元素的有限集，R是D上关系的有限集。四类基本的结构 集合结构、线性结构、树型结构、图状结构。,集合结构,定义：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。集合,线性结构,定义：结构中的数据元素之间存在着一对一的线性关系。线性表,树型结构,定义：结构中的数据元素之间存在着一对多的层次关系。,树,图状结构或网状结构,定义：结构中的数据元素之间存在着

9、多对多的任意关系。,图,逻辑结构,综上所述，数据的逻辑结构可概括为：,return,逻辑结构,非线性结构树、图,线性结构线性表、栈、队字符串、数组、广义表,存储结构,定义：存储结构（又称物理结构）是逻辑结构在计算机中存储映象，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。形式化描述：D要存入机器中，建立一从D的数据元素到存储空间M单元映象S，DM，即对于每一个d，dD,都有唯一的zM使S（D）=Z,同时这个映象必须明显或隐含地体现关系R。,存储结构,逻辑结构与存储结构的关系为：存储结构是逻辑关系的映象与元素本身映象，是数据结构的实现；逻辑结构是数据结构的抽象。数据元素之间关系在

10、计算机中的表示方法：顺序映象（顺序存储结构）非顺序映象（非顺序存储结构）,return,运算集合,例如工资表：,数据结构的内容,数据结构的内容可归纳为三个部分：逻辑结构、存储结构和运算集合。按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机存贮器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。,return,1.3 算法,算法（Algorithm）定义 算法的特性 算法设计的要求,返回,算法（Algorithm）定义,定义：Algorithm is a finite set of rules which gives a sequence of operation for

11、 solving a specific type of problem.算法是规则的有限集合，是为解决特定问题而规定的一系列操作。,return,算法的特性,1.有限性：有限步骤之内正常结束，不能形成无穷循环2.确定性：算法中的每一个步骤必须有确定含义，无二义性得以实现。3.输入：有多个或0个输入 4.输出：至少有一个或多个输出。5.可行性：原则上能精确进行，操作可通过已实现基本运算执行有限次而完成。,return,算法设计的要求,算法特征：算法的正确性 可读性 健壮性 高效率和低存储量,求n个数的最大值，算法如下：max=0;for（i=1;imax)max=x;,return,1.4 算法

12、描述的工具,概述：算法+数据结构=程序 算法、语言、程序的关系 设计实现算法过程步骤类描述算法的语言选择,返回,算法、语言、程序的关系,1.算法：描述了数据对象的元素之间的关系（包括数据逻辑关系、存贮关系描述）。2.描述算法的工具：算法可用自然语言、框图或高级程序设计语言进行描述。3.程序是算法在计算机中的实现。,return,设计实现算法过程步骤,1.找出与求解有关的数据元素之间的关系2.确定在某一数据对象上所施加运算3.考虑数据元素的存储表示4.选择描述算法的语言5.设计实现求解的算法，并用程序语言加以描述。,return,类描述算法的语言选择,类语言：类语言是接近于高级语言而又不是严格的

13、高级语言，具有高级语言的一般语句设施，撇掉语言中的细节，以便把注意力主要集中在算法处理步骤本身的描述上。,对C语言作以下描述：,1.预定义常量和类型#define TRUE 1#define FALSE 0#define MAXSIZE 100#define OK 1#define ERROR 0,对C语言作以下描述：,2.函数的表示形式：数据类型 函数名（形式参数及说明）内部数据说明；执行语句组；/*函数名*/,对C语言作以下描述：,3.赋值语句对C语言作以下描述：（1）简单赋值 1）变量名=表达式 2）变量+，3）变量-，（2）串联赋值变量1=变量2=变量3=变量k=表达式,对C语言作以下

14、描述：,（3）条件赋值变量名=条件表达式？表达式1:表达式2 4.条件选择语句 if()语句;if()语句1;else 语句2;,对C语言作以下描述：,情况语句switch(）case 判断值1:语句组 1；break;case 判断值2:语句组 2；break;case 判断值n:语句组n;break;default:语句组；break;,对C语言作以下描述：,5.循环语句for 语句for(；）循环体语句；,对C语言作以下描述：,while 语句 while(）循环体语句；do while 语句 do 循环体语句 while(）,对C语言作以下描述：,6.输入、输出函数7.其它一些语句8.

15、注释语句9.一些基本的函数,return,1.5 对算法作性能评价,评价算法的标准：评价一个算法主要看这个算法所占用机器资源的多少，而这些资源中时间代价与空间代价是两个主要的方面，通常是以算法执行所需的机器时间和所占用的存储空间来判断一个算法的优劣。性能评价 有关数量关系计算,返回,性能评价,定义：对问题规模与该算法在运行时所占的空间S与所耗费的时间T给出一个数量关系的评价。问题规模N对不同的问题其含义不同：对矩阵是阶数；对多项式运算是多项式项数；对图是顶点个数；对集合运算是集合中元素个数。,return,有关数量关系计算,数量关系评价体现在时间算法在机器中所耗费时间。数量关系评价体现在空间算

16、法在机器中所占存储量。关于算法执行时间语句频度 算法的时间复杂度数据结构中常用的时间复杂度频率计数 最坏时间复杂度 算法的空间复杂度,return,关于算法执行时间,定义：一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。分析：不是针对实际执行时间的精确地算出算法执行具体时间，而是针对算法中语句的执行次数做出估计，从中得到算法执行时间的信息。,return,语句频度,定义：语句频度是指该语句在一个算法中重复执行的次数。例如：两个矩阵相乘算法语句 对应的语句频度 1for（i=0；i n;i+）n 2 for（j=0；jn;j

17、+）n2 3 cij=0;n2 4 for(k=0;k n;k+)n3 cij=cij+aik*bkj;n3 总执行次数：T(n)=2n3+2n2+n,return,算法的时间复杂度,算法的时间复杂度，即是算法的时间量度记做：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)，称为线性阶；,return,常用的时间复杂度频率计数,常用的时间复杂度频率计数 数据结构中常用的时间复杂度频率计数有7个:O(1)常数型 O(n)线性型 O(n2)平方型 O(n3)立方型 O(2n)指数型 O(

18、log2n)对数型 O(nlog2n)二维型按时间复杂度由小到大排列的频率表：P17,return,最坏时间复杂度,定义：讨论算法在最坏情况下的时间复杂度，即分析最坏情况下以估计出算法执行时间的上界。例如冒泡排序算法,最坏时间复杂度,void bubble(int a,int length)int i=0,j,temp;int change;do change=false;for(j=1;jaj+1)temp=aj;aj=aj+1;aj+1=temp;change=true;i=i+1;while(ilength|change=true),return,算法的空间复杂度,定义：用空间复杂度作为算法所需存储空间的量度，记做：S(n)=O(f(n)。,return,1.6 关于学习数据结构,数据结构课程地位 数据结构课程学习特点 关于本书内容编写说明,返回,数据结构课程学习特点,教学目标：学会分析数据对象的特征，掌握数据组织方法和计算机的表示方法，以便为应用所涉及数据选择适当的逻辑结构、存储结构及相应算法，初步掌握算法时间空间分析的技巧，培养良好的程序设计技能。学习方法：学习数据结构，必须经过大量的实践，在实践中体会构造性思维方法，掌握数据组织与程序设计的技术。,