《数据结构课件(第一章)》由会员分享，可在线阅读，更多相关《数据结构课件(第一章)（58页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程地位数据结构与其它课程关系图：编译原理编译原理人工智能人工智能操作系统操作系统离散数学离散数学计算机基础知识计算机基础知识其它专业课其它专业课数据结构数据结构数据库数据库程序设计语言程序设计语言参考书籍：参考书籍：n数据结构（数据结构（C语言版）语言版） 严蔚敏严蔚敏 吴伟民吴伟民 清华大学出版社清华大学出版社n数据结构题集数据结构题集(C语言版语言版) 严蔚敏严蔚敏 清华大学出版社清华大学出版社n数据结构学习指导与典型题解朱战立数据结构学习指导与典型题解朱战立 西安交通大学出版西安交通大学出版社社n数据结构与程序设计数据结构与程序设计C语言描述语言描述 (第第2版版)(Data
2、Structure &Program Design in C)Robert L.Kruse 2001-9清华大学出版社清华大学出版社n数据结构及应用算法教程数据结构及应用算法教程(配软盘配软盘) 严蔚敏严蔚敏 陈文博陈文博 清华大清华大学出版社学出版社n数据结构（数据结构（C语言篇）语言篇）习题与解析（修订版）习题与解析（修订版） 李春葆李春葆 清华大学出版社清华大学出版社nC/C+与数据结构与数据结构 王立柱王立柱 编著编著 清华大学出版社清华大学出版社关于本书内容说明本书基本结构本书基本结构 第一部分：数据结构的基本概念（第1章）第二部分：基本的数据结构包括：线性结构线性表、栈和队列、串、
3、数组与广义表（第25章）非线性结构树、图（第6、7章）第三部分：基本技术包括：查找技术与排序技术（第8、9、10章） 返回西安工程大学西安工程大学 计算机科学学院计算机科学学院第一章 绪论内容简介内容简介 n1.1什么是数据结构n1.2数据结构的内容n1.3算法n1.4算法描述的工具 n1.5对算法作性能评价n1.6关于学习数据结构 1.1 什么是数据结构（定义）什么是数据结构（定义）数据结构的相关名词：数据结构的相关名词： n数据（数据（Data）n数据元素（数据元素（Data Element） n数据对象（数据对象（Data Object） n数据结构（数据结构（Data Structur
4、e） n数据类型数据类型(Data Type) n数据抽象与抽象数据类型数据抽象与抽象数据类型返回数据（数据（Data） n定义： 数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。 数据包含整型、实型、布尔型、图象、字符、声音等一切可以输入到计算机中的符号集合。例如对C源程序 源程序目标程序可执行程序（.c） （.obj） （.exe）C编译程序C链接程序return数据元素（数据元素（Data Element） n定义： 数据元素是组成数据的基本单位，是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。例如：学号学号姓名姓名性别性别籍贯籍贯 出生年出生年月月住址
5、住址101赵凌赵凌女女河北河北1983.11北京北京数据项数据元素return数据对象（数据对象（Data Object） n定义：定义： 数据对象是性质相同的数据元素的集数据对象是性质相同的数据元素的集合，是数据的一个子集。合，是数据的一个子集。例如：例如： 整数集合：整数集合：N=0，1，2， 无限无限集集 字符集合：字符集合：C=A，B，Z 有限有限集集return数据结构（数据结构（Data Structure） n定义：定义： 数据结构是指相互之间存在一种或多数据结构是指相互之间存在一种或多种特定关系的数据元素集合，种特定关系的数据元素集合，是带有结构的数据元素的集合，它指的是数据元
6、素之间的相互关系，即数据的组织形式。例如表结构：学号学号姓名姓名性别性别籍贯籍贯出生年出生年月月住址住址101赵凌赵凌女女河北河北1983.11北京北京数据结构（数据结构（Data Structure） 学校系处研究机构教研室实验室树形结构return数据类型数据类型(Data Type) n定义：定义： 数据类型是一组性质相同的值集合以数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。及定义在这个值集合上的一组操作的总称。 如在高级语言中，整型类型的取值范围为：-32768+32767，运算符集合为加、减、乘、除、取模，即+、-、*、/、%。数据类型数据类型(Data T
7、ype) n高级语言中的数据类型分为两大类：高级语言中的数据类型分为两大类：1.原子类型，原子类型，其值不可分解。如C语言中的标准类型（整型、实型、字符型）及指针。2.结构类型，结构类型，其值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是非结构的，也可以是结构的。return数据抽象与抽象数据类型数据抽象与抽象数据类型 n数据的抽象数据的抽象n抽象数据类型抽象数据类型(Abstract Data Type) nADT的表示与实现的表示与实现数据的抽象n汇编语言中十进制表示的数据汇编语言中十进制表示的数据98.65、9.6E3等等, 它们是二进制数据的抽象它们是二进制数据的抽
8、象; n高级语言中，给出更高一级的数据抽象，如高级语言中，给出更高一级的数据抽象，如整型、实型、字符型等整型、实型、字符型等;n还可以进一步定义更高级的数据抽象，如各还可以进一步定义更高级的数据抽象，如各种表、队、栈、树、图、窗口、管理器等复种表、队、栈、树、图、窗口、管理器等复杂的抽象数据类型。杂的抽象数据类型。return抽象数据类型(AbstractDataType)n定义：定义： 抽象数据类型抽象数据类型（简称ADT）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。一个抽象数据类型确定了一个模型，但将模型的实现细节隐藏起来；它定义了一组运算，但将运算的实现过程隐藏起来。
9、抽象数据类型抽象数据类型(Abstract Data Type) n线性表的抽象数据类型的描述：线性表的抽象数据类型的描述：ADT ADT Linear_listLinear_list数据元素数据元素 所有所有a ai i属于同一数据对象，属于同一数据对象， i=1i=1，2 2，n,nn,n=0=0；逻辑结构逻辑结构 所有数据元素所有数据元素a ai i（i=1i=1，2 2，n-1n-1）存在）存在次序关系次序关系 ，a a1 1无前趋，无前趋，a an n无后继；无后继；操作操作 设设L L为为Linear_listLinear_listInitial(LInitial(L) )初始化空
10、线性表；初始化空线性表；Length(LLength(L) )求线性表的表长；求线性表的表长；Get(L,iGet(L,i) )取线性表的第取线性表的第i i个元素；个元素；Insert(L,i,bInsert(L,i,b) )在线性表的第在线性表的第i i个位置插入元素个位置插入元素b b； Delete(L,iDelete(L,i) )删除线性表的第删除线性表的第i i个元素；个元素； returnADT的表示与实现nADT的定义：的定义： ADT 数据对象数据对象: 结构关系结构关系: 基本操作基本操作: ADT n基本操作基本操作的定义格式为：的定义格式为： (参数表参数表) 操作前提
11、操作前提: 操作结果操作结果:ADT的表示与实现的表示与实现 n关于参数传递关于参数传递 参数表中的参数有参数表中的参数有值参值参和和变参变参两种。两种。n用标准用标准C语言表示和实现语言表示和实现ADT描述时，主要描述时，主要有两个方面：有两个方面： ( ( 1 ) 1 ) 通过结构体将通过结构体将intint、floatfloat等固有类型组合到一起等固有类型组合到一起, ,构构成一个结构类型成一个结构类型, ,再用再用typedeftypedef为该类型或该类型指针重新为该类型或该类型指针重新起一个名字。起一个名字。 ( 2 )( 2 )用用C C语言函数实现各操作。基本操作包括插入、删
12、除、语言函数实现各操作。基本操作包括插入、删除、更新、查找、排序等更新、查找、排序等 。return1.2 数据结构的内容数据结构的内容 n逻辑结构逻辑结构 n存储结构存储结构 n运算集合运算集合 返回逻辑结构逻辑结构 n定义：定义： 数据的逻辑结构是指数据元素之间逻辑关系描述。数据的逻辑结构是指数据元素之间逻辑关系描述。n形式化描述：形式化描述： Data_Structure=（D,R）其中）其中D是数据元素是数据元素的有限集，的有限集，R是是D上关系的有限集。上关系的有限集。n四类基本的结构四类基本的结构 集合结构集合结构、线性结构线性结构、树型结构树型结构、图状结构图状结构。集合结构集合
13、结构 n定义： 结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。 集合集合线性结构线性结构 n定义：结构中的数据元素之间存在着一对一的线性关系。线性表树型结构树型结构 n定义：定义： 结构中的数据元素之间存在着一对多的层次关系。树树图状结构或网状结构图状结构或网状结构 n定义：结构中的数据元素之间存在着多对多的任意关系。图图逻辑结构逻辑结构 综上所述，数据的逻辑结构可概括为：return逻辑结构非线性结构树、图线性结构线性表、栈、队字符串、数组、广义表存储结构存储结构 n定义：定义： 存储结构（存储结构（又称物理结构）是逻辑结构在计算又称物理结构）是逻辑结构在计算机中存储映象，
14、机中存储映象，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。 n形式化描述：形式化描述： D要存入机器中，建立一从要存入机器中，建立一从D的数据元素到存的数据元素到存储空间储空间M单元映象单元映象S ，DM，即对于每一个，即对于每一个d， dD,都有唯一的都有唯一的zM使使S（D）=Z, 同时这个映同时这个映象必须明显或隐含地体现关系象必须明显或隐含地体现关系R。存储结构存储结构 逻辑结构与存储结构的关系为：存储结构是逻辑关系的映象与元素本身映象，是数据结构的实现；逻辑结构是数据结构的抽象。 数据元素之间关系在计算机中的表示方法：n顺序映象（顺序存储结构）n非顺序映象（非顺序存
15、储结构）return运算集合运算集合 例如工资表：例如工资表：编号编号姓名姓名性别性别基本基本工资工资工龄工龄工资工资应扣应扣工资工资实发实发工资工资数据结构的内容数据结构的内容 数据结构的内容可归纳为三个部分：数据结构的内容可归纳为三个部分： 逻辑结构、存储结构和运算集合。 按某种逻辑关系组织起来的一批数据，按按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机存贮器中，一定的映象方式把它存放在计算机存贮器中，并在这些数据上定义了一个运算的集合，就叫并在这些数据上定义了一个运算的集合，就叫做数据结构。做数据结构。 return1.3 算法算法 n算法（Algorithm）定义
16、n算法的特性n算法设计的要求 返回算法（Algorithm）定义n定义：定义： Algorithm is a finite set of rules which gives a sequence of operation for solving a specific type of problem. 算法是规则的有限集合，是为解决特定问题而规定的一系列操作。 return算法的特性1. 有限性有限性：有限步骤之内正常结束，不能形：有限步骤之内正常结束，不能形成无穷循环成无穷循环2. 确定性确定性：算法中的每一个步骤必须有确定：算法中的每一个步骤必须有确定含义，无二义性得以实现。含义，无二义性得
17、以实现。 3. 输入输入： 有多个或有多个或0个输入个输入 4. 输出输出： 至少有一个或多个输出。至少有一个或多个输出。5. 可行性可行性：原则上能精确进行，操作可通过：原则上能精确进行，操作可通过已实现基本运算执行有限次而完成。已实现基本运算执行有限次而完成。 return算法设计的要求算法特征：算法特征：n算法的正确性算法的正确性 n 可读性可读性 n 健壮性健壮性 n 高效率和低存储量高效率和低存储量求求n个数的最大值，算法如下：个数的最大值，算法如下： max=0; for（i=1 ;imax) max=x; return1.4算法描述的工具n概述：概述： 算法算法+数据结构数据结构
18、=程序程序 n算法、语言、程序的关系算法、语言、程序的关系 n设计实现算法过程步骤设计实现算法过程步骤n类描述算法的语言选择类描述算法的语言选择返回算法、语言、程序的关系1. 算法：描述了数据对象的元素之间的关系算法：描述了数据对象的元素之间的关系（包括数据逻辑关系、存贮关系描述）。（包括数据逻辑关系、存贮关系描述）。2. 描述算法的工具：算法可用自然语言、框描述算法的工具：算法可用自然语言、框图或高级程序设计语言进行描述。图或高级程序设计语言进行描述。3.程序是算法在计算机中的实现。程序是算法在计算机中的实现。return设计实现算法过程步骤1. 找出与求解有关的数据元素之间的关系找出与求解
19、有关的数据元素之间的关系2. 确定在某一数据对象上所施加运算确定在某一数据对象上所施加运算3. 考虑数据元素的存储表示考虑数据元素的存储表示4. 选择描述算法的语言选择描述算法的语言5.设计实现求解的算法，并用程序语言加以描设计实现求解的算法，并用程序语言加以描述。述。return类描述算法的语言选择类语言：类语言：类语言是接近于高级语言而又不是严格的高级语言，具有高级语言的一般语句设施，撇掉语言中的细节，以便把注意力主要集中在算法处理步骤本身的描述上。对对C语言作以下描述：语言作以下描述：1.预定义常量和类型预定义常量和类型 # define TRUE 1 # define FALSE 0
20、# define MAXSIZE 100 # define OK 1 # define ERROR 0 对对C语言作以下描述：语言作以下描述：2.函数的表示形式：数据类型函数名（形式参数及说明）内部数据说明；执行语句组；/*函数名*/对对C语言作以下描述：语言作以下描述： 3.赋值语句对C语言作以下描述：（1）简单赋值1）变量名=表达式2）变量+，3）变量-，（2）串联赋值变量1=变量2=变量3=变量k=表达式 对对C语言作以下描述：语言作以下描述： （3）条件赋值变量名=条件表达式？表达式1:表达式2 4.条件选择语句if()语句;if()语句1;else语句2; 对对C语言作以下描述：语言
21、作以下描述： 情况语句switch(）case判断值1:语句组1；break;case判断值2:语句组2；break;case判断值n:语句组n;break;default:语句组；break;对对C语言作以下描述：语言作以下描述： 5.循环语句nfor语句for(；）循环体语句；对对C语言作以下描述：语言作以下描述：nwhile语句while(）循环体语句；ndowhile语句do循环体语句while(）对对C语言作以下描述：语言作以下描述：6.输入、输出函数7.其它一些语句8.注释语句9.一些基本的函数return1.5对算法作性能评价n评价算法的标准：评价算法的标准： 评价一个算法主要看
22、这个算法所占用机评价一个算法主要看这个算法所占用机器资源的多少，而这些资源中时间代价与空器资源的多少，而这些资源中时间代价与空间代价是两个主要的方面，通常是以算法执间代价是两个主要的方面，通常是以算法执行所需的行所需的机器时间机器时间和所占用的和所占用的存储空间存储空间来判来判断一个算法的优劣。断一个算法的优劣。 n性能评价性能评价 n有关数量关系计算 返回性能评价性能评价n定义： 对问题规模与该算法在运行时所占的空间S与所耗费的时间T给出一个数量关系的评价。问题规模N对不同的问题其含义不同：对矩阵是阶数；对多项式运算是多项式项数；对图是顶点个数；对集合运算是集合中元素个数。return有关数
23、量关系计算数量关系评价体现在时间算法在机器中所耗费时间。数量关系评价体现在空间算法在机器中所占存储量。n关于算法执行时间n语句频度 n算法的时间复杂度n数据结构中常用的时间复杂度频率计数 n最坏时间复杂度 n算法的空间复杂度 return关于算法执行时间关于算法执行时间 n定义： 一个算法的执行时间大致上等于其所有一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间语句执行时间的总和，对于语句的执行时间是是指该条语句的执行次数和执行一次所需时指该条语句的执行次数和执行一次所需时间的乘积间的乘积。n分析：分析： 不是针对实际执行时间的精确地算出算不是针对实际执行时间的精确地算
24、出算法执行具体时间，而是针对算法中语句的执法执行具体时间，而是针对算法中语句的执行次数做出行次数做出估计估计，从中得到算法执行时间的，从中得到算法执行时间的信息。信息。return语句频度语句频度 n定义：定义： 语句频度是指该语句在一个算法中重复执行的次数。语句频度是指该语句在一个算法中重复执行的次数。例如：例如： 两个矩阵相乘两个矩阵相乘算法语句算法语句 对应的语句频对应的语句频度度 1for（i=0；i n;i+） n 2 for （j=0；jn;j+） n2 3 cij=0; n2 4 for (k=0;k n; k+) n3 cij=cij+aik*bkj; n3 总执行次数：总执行
25、次数：T(n)=2n3+2n2 +nreturn算法的时间复杂度算法的时间复杂度 n算法的时间复杂度，即是算法的时间量度记做：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常用的时间复杂度频率计数常用的时间复杂度频率计数 n常用的时间复杂度频率计数n数据结构中常用的时间复杂度频率计数有数据结构中常用的时间复杂度频率计数有7个个:nO(1)常数型O(n)线性型O(n2)平方型nO(n3)立方型O(2n)指数型O(log2n)对数型nO(nlog2n)二维型n
26、按时间复杂度由小到大排列的频率表：P17return最坏时间复杂度最坏时间复杂度 n定义：讨论算法在最坏情况下的时间复杂度，即分析最坏情况下以估计出算法执行时间的上界。例如冒泡排序算法最坏时间复杂度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算法的空间复杂度n定义：定义： 用空间复杂度作为算法所需存储空间的量度，记做：S(n)=O(f(n)。 return1.6关于学习数据结构n数据结构课程地位n数据结构课程学习特点n关于本书内容编写说明返回数据结构课程学习特点n教学目标：学会分析数据对象的特征，掌握数据组织方法和计算机的表示方法，以便为应用所涉及数据选择适当的逻辑结构、存储结构及相应算法，初步掌握算法时间空间分析的技巧，培养良好的程序设计技能。n学习方法：学习数据结构，必须经过大量的实践，在实践中体会构造性思维方法，掌握数据组织与程序设计的技术。
