1、耿国华耿国华等编著等编著16/24/2020课前说明课前说明?上课时间上课时间单周：周一、周二的1、2节课双周：周一的1、2节课卷面(70%)+平时(30%)平时成绩：作业(20%)+点名(10%)?成绩评定成绩评定2关于本书内容编写说明数据结构的基本概念（第1章）线性表（第2章）基本三结部基本的数据结构分构3线性结构栈和队列（第3章）串（第4章）数组和广义表（第5章）非线性结构树（第6章）图（第7章）查找技术（第8章）排序技术（第9、10章）基本的数据处理技术第第1 1章章?1.11.1?1.21.2?1.31.3绪绪 论论什么是数据结构什么是数据结构(定义定义)数据结构的内容数据结构的内容
2、（研究范围）（研究范围）算法算法?1.41.4?1.51.5?1.61.6算法描述的工具算法描述的工具对算法作性能评价对算法作性能评价关于学习数据结构的学习关于学习数据结构的学习41.1 1.1 什么是数据结构（定义）什么是数据结构（定义）数据结构的相关名词：?数据（Data）?数据元素（Data Element）?数据对象（Data Object）?数据结构（Data Structure）?数据类型(Data Type)?数据抽象与抽象数据类型5数据（数据（DataData）?定义：数据是描述客观事物的数值、字符以及能输数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合入机
3、器且能被处理的各种符号集合。数据包含整型、实型、布尔型、图象、字符、声音等一切可以输入到计算机中的符号集合。例如对C源程序C编译程序源程序源程序（.c）目标程序目标程序（.obj）C链接程序可执行程序可执行程序（.exe）6数据元素（数据元素（Data ElementData Element）?定义定义：数据元素是组成数据的基本单位组成数据的基本单位，是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。例如：数据项数据项学 号姓 名性 别籍 贯101 赵虹玲女河北.出生年月1983.11.住 址北京.数数据据元元素素7数据对象（数据对象（Data Object）?定义定义：数据对象是性
4、质相同的数据元素的集合性质相同的数据元素的集合，是数据的一个子集。例如：整数集合：N=0，1，2，无限集字符集合：C=A，B，Z 有限集8数据数据可放入机器（与机器的关联性）?数据特点可被加工（能被处理）?数据结构数据元素组成数据的基本单位（与数据的关系是集合的个体）数据对象性质相同的数据元素的集合（与数据的关系是集合的子集）9数据结构（数据结构（Data Structure）?定义：数据结构是指相互之间存在一种或多种特数据结构是指相互之间存在一种或多种特定关系的数据元素集合定关系的数据元素集合，是带有结构的数据元素的集合，它指的是数据元素之间的相互关系，即数据的组织形式。例如表结构：学 号姓
5、 名性 别籍 贯101 赵虹玲女河北.出生年月1983.11.住 址北京.10数据结构（数据结构（Data Structure）树型结构学校图结构12 系处研究机构5教研室实验室3411数据类型数据类型(Data Type)(Data Type)?定义：数据类型是一组性质相同的值集合以及定数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称义在这个值集合上的一组操作的总称。如在高级语言中，整型类型的取值范围为：-32768+32767，运算符集合为加、减、乘、除、取模，即+、-、*、/、%。12数据类型数据类型(Data Type)(Data Type)?高级语言中的数据类型分
6、为两大类：1.原子类型原子类型，其值不可分解。如C语言中的标准类型（整型、实型、字符型、）。2.结构类型结构类型，其值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是非结构的，也可以是结构的。13指针类型属于哪种类型？指针类型属于哪种类型？数据抽象与抽象数据类型数据抽象与抽象数据类型?数据的抽象抽象数据类型(Abstract Data Type)抽象数据类型实现ADT的表示与实现面向对象的概念结构化的开发方法与面向对象开发方法不同点14数据的抽象数据的抽象?汇编语言中十进制表示的数据 98.65、9.6E3等,它们是二进制数据的抽象;?高级语言中，给出更高一级的数据抽象，如整
7、型、实型、字符型等，还可以进一步定义更高级的数据抽象，如各种表、队、栈、树、图、窗口、管理器等复杂的抽象数据类型。15抽象数据类型抽象数据类型(Abstract Data Type)(Abstract Data Type)?定义：抽象数据类型（简称抽象数据类型（简称ADTADT）是指基于一类逻辑关系的数）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作据类型以及定义在这个类型之上的一组操作。一个抽象数据类型确定了一个模型，但将模型的实现细节一个抽象数据类型确定了一个模型，但将模型的实现细节隐藏起来；它定义了一组运算，但将运算的实现过程隐藏隐藏起来；它定义了一组运算，但将运算的实现
8、过程隐藏起来。起来。用抽象数据类型的概念来指导问题的求解过程：用抽象数据类型的概念来指导问题的求解过程：数学模型数学模型非形式算法非形式算法抽象数据模型抽象数据模型伪语言程序伪语言程序数据结构数据结构可执行程序可执行程序16抽象数据类型抽象数据类型(Abstract Data Type)(Abstract Data Type)?线性表的抽象数据类型的描述：ADT Linear_list数据元素数据元素所有所有a ai i属于同一数据对象，属于同一数据对象，i=1i=1，2 2，n nnn0 0；逻辑结构逻辑结构所有数据元素所有数据元素a ai i（i=1i=1，2 2，n-1n-1）存在次序关
9、系）存在次序关系a，a ai i无前趋，无前趋，a an n无后继；无后继；操作操作设设L L为为Linear_listLinear_listInitial(L)Initial(L)初始化空线性表；初始化空线性表；Length(L)Length(L)求线性表的表长；求线性表的表长；Get(L,i)Get(L,i)取线性表的第取线性表的第i i个元素；个元素；Insert(L,i,b)Insert(L,i,b)在线性表的第在线性表的第i i个位置插入元素个位置插入元素b b；Delete(L,i)Delete(L,i)删除线性表的第删除线性表的第i i个元素；个元素；17抽象数据类型实现抽象数据
10、类型实现实现的三种方法：?传统的面向过程的程序设计传统的面向过程的程序设计?“包包”、“模型模型”的设计方法的设计方法?面向对象的程序设计面向对象的程序设计（Object Oriented Programming，简称OOP）18ADT的表示与实现的表示与实现?ADT的定义：ADT 数据对象:结构关系:基本操作:ADT 基本操作的定义格式为：(参数表)操作前提:操作结果:19ADT的表示与实现的表示与实现?关于参数传递：参数表中的参数有值参和变参两种。用标准C语言表示和实现ADT描述时，主要有两个方面：一、通过结构体将int、float等固有类型组合到一起,构成一个结构类型,再用typedef
11、为该类型或该类型指针重新起一个名字。二、用C语言函数实现各操作。20面向对象的概念面向对象的概念?面向对象的概念：面向对象=对象+类+继承+通信对象：指在应用问题中出现的各种实体、事件、规格说明等类：具有相同属性和服务的对象继承：是是面向对象方法的最有特色的方面。21。结构化与面向对象开发方法的不同点结构化与面向对象开发方法的不同点?结构化的开发方法：是面向过程的开发方法，首先着眼于系统要实现的功能。首先着眼于应用问题所涉及的对象，包括对象、对象属性和要求的操作，从而建立对象结构和为解决问题需要执行的时间序列。?面向对象的开发方法面向对象的开发方法：221.2 数据结构的内容数据结构的内容?逻
12、辑结构?存储结构?运算集合23逻辑结构逻辑结构?定义：数据的逻辑结构是指数据元素之间逻辑关系描述。?形式化描述：Data_Structure=（D,R）其中D是数据元素的有限集，R是D上关系的有限集。?四类基本的结构集合结构、线性结构、树型结构、图状结构。24集合结构集合结构?定义定义：结构中的数据元素之间除了同属于一个集结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。合的关系外，无任何其它关系。例如：集合集合25线性结构线性结构?定义：定义：结构中的数据元素之间存在着一对一的线结构中的数据元素之间存在着一对一的线性关系。性关系。例如：线性表线性表26树型结构树型结构?定义：结
13、构中的数据元素之间存在着一对多的层结构中的数据元素之间存在着一对多的层次关系。次关系。例如：树树27图状结构或网状结构图状结构或网状结构?定义：定义：结构中的数据元素之间存在着多对多的任结构中的数据元素之间存在着多对多的任意关系。意关系。图例如：28逻辑结构逻辑结构综上所述，数据的逻辑结构可概括为综上所述，数据的逻辑结构可概括为：线性结构线性结构线性表、栈、队、字符串线性表、栈、队、字符串数组、广义表数组、广义表逻辑结构逻辑结构非线性结构非线性结构树、图树、图29存储结构存储结构定义：存储结构（又称物理结构）是逻辑结构在计存储结构（又称物理结构）是逻辑结构在计算机中存储映象算机中存储映象，是逻
14、辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。?形式化描述：D要存入机器中，建立一从 D的数据元素到存储空间M单元映象S，DM，即对于每一个 d，dD,都有唯一的zM使S（D）=Z,同时这个映象必须明显或隐含地体现关系 R。?30存储结构存储结构逻辑结构与存储结构的逻辑结构与存储结构的 关系关系为：为：存储结构存储结构是逻辑关系的映象与元素本身映象，是数是逻辑关系的映象与元素本身映象，是数据结构的实现据结构的实现；逻辑结构逻辑结构是数据结构的抽象是数据结构的抽象。数据元素之间关系在计算机中的表示方法：数据元素之间关系在计算机中的表示方法：?顺序映象顺序映象（顺序存储结构）（顺序存储
15、结构）?非顺序映象非顺序映象（非顺序存储结构（非顺序存储结构）31运算集合运算集合例如工资表：编编号号姓姓名名性别性别女女男男男男基本工资基本工资345345676744544590903453450000工龄工资工龄工资145145454518518560601301300000应扣工资应扣工资303000004545000025250000实发工资实发工资451451121258658650504504500000100001100001张爱芬张爱芬100002100002李李 林林100003100003刘刘 晓峰晓峰100004100004100005100005赵赵孙孙俊俊涛涛女女男
16、男5605609090450450606022522590901901908080656500005050000072172180805915918080100121100121张兴强张兴强男男102510259898365365535310010000001291.511291.5132数据结构的内容数据结构的内容综上所述，数据结构的内容可归纳为三个部分，逻辑结构逻辑结构、存储结构存储结构和和运算集合运算集合：按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机存贮器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。331.3 算法算法?算法（算法（AlgorithmAl
17、gorithm）定义）定义?算法的特性算法的特性?算法设计的要求算法设计的要求34算法（算法（AlgorithmAlgorithm）定义）定义?定义：Algorithmisafinitesetofruleswhichgivesa sequenceofoperationforsolving a specific type of problem.算法是规则的有限集合，是为解决特定问算法是规则的有限集合，是为解决特定问题而规定的一系列操作。题而规定的一系列操作。35算法的特性算法的特性1.有限性：有限步骤之内正常结束，不能形成无穷循环2.确定性：算法中的每一个步骤必须有确定含义，无二义性得以实现。3
18、.输 入：有多个或0个输入4.输 出：至少有一个或多个输出。5.可行性：原则上能精确进行，操作可通过已实现基本运算执行有限次而完成。36算法设计的要求算法设计的要求算法特征：?例如要求n个数的最大值问题算法的正确性可读性健壮性高效率和低存储量给出算法如下：max:=0;for（i=1；imax)max=x;371.4 算法描述的工具算法描述的工具?概述：算法+数据结构=程序?算法、语言、程序的关系?设计实现算法过程步骤?类描述算法的语言选择38算法、语言、程序的关系算法、语言、程序的关系1.算法：描述了数据对象的元素之间的关系（包括数据逻辑关系、存贮关系描述）。2.描述算法的工具：算法可用自然
19、语言、框图或高级程序设计语言进行描述。3.程序是算法在计算机中的实现。39设计实现算法过程步骤设计实现算法过程步骤1.找出与求解有关的数据元素之间的关系2.确定在某一数据对象上所施加运算3.考虑数据元素的存储表示4.选择描述算法的语言5.设计实现求解的算法，并用程序语言加以描述。40类描述算法的语言选择类描述算法的语言选择?类语言：类语言是接近于高级语言而又不是严格的高级语言，类语言是接近于高级语言而又不是严格的高级语言，具有高级语言的一般语句设施，撇掉语言中的细节，具有高级语言的一般语句设施，撇掉语言中的细节，以便把注意力主要集中在算法处理步骤本身的描述以便把注意力主要集中在算法处理步骤本身
20、的描述上。上。41对C语言作以下描述：1.预定义常量和类型#define TRUE 1#define FALSE 0#define MAXSIZE 100#define OK 1#define ERROR 042对C语言作以下描述：2.函数的表示形式：数据类型 函数名（形式参数及说明）内部数据说明；int max(a,b)执行语句组；if(a=b)return/*函数名*/else return b;43a;对C语言作以下描述：3.赋值语句赋值语句（1）简单赋值简单赋值1）变量名）变量名=表达式表达式2）变量变量+，3）变量变量-，eg:a=b+1;eg:i+;eg:i-;（2）串联赋值串联赋
21、值变量变量1=变量变量2=变量变量3=变量变量k=表达式表达式eg:a=b=c=d=eg:a=b=c=d=k+1;44对C语言作以下描述：（3）成组赋值成组赋值(,变量变量k=(,)数组名数组名1 1 下标下标11下标下标2=2=数组名数组名2 2 下标下标11下标下标22eg:a12=b12（4）条件赋值条件赋值变量名变量名=条件表达式？表达式条件表达式？表达式1:表达式表达式2eg:a=1 b=2?0:1eg:a=1 b=2?0:145对C语言作以下描述：4.条件选择语句?if ()语句;if(ab)k+;?if ()语句1;if(ab)k+;else 语句2;else k-;46对C语言
22、作以下描述：?情况语句switch(）case 判断值1:语句组 1；case 判断值n:语句组n;break;break;case 判断值2:语句组 2；default:语句组；break;break;47对C语言作以下描述：?eg：switch(B)case 0:printf(“请输入0”）；case 1:printf(“请输入1”）；default printf(“错误”）；break;break;break;48对C语言作以下描述：5.循环语句循环语句?for 语句语句for(；）循环体语句；循环体语句；for（i=2；i=20;i+)k=i+1;49对C语言作以下描述：?while
23、语句语句while(）循环体语句；循环体语句；while(i=10)i-;dodoi-;?do while 语句语句do 循环体语句循环体语句while(）while(i=10)while(i=10)50对C语言作以下描述：6.输入、输出函数输入、输出函数scanf getchar、printf putchar7.其它一些语句其它一些语句 return、break、continue8.注释语句注释语句/*字符串字符串*/9.一些基本的函数一些基本的函数max，min，abs，eof511.5 对算法作性能评价对算法作性能评价?评价算法的标准：评价一个算法主要看这个算法所占用机器资源的多少，而这
24、些资源中 时间代价与空间代价是两个主要的方面，通常是以算法执行所需的机器时间和所占用的存储空间来判断一个算法的优劣。性能评价有关数量关系计算有关数量关系计算52性能评价?定义：定义：对问题规模与该算法在运行时所占的空间对问题规模与该算法在运行时所占的空间 S与所与所耗费的时间耗费的时间T给出一个数量关系的评价给出一个数量关系的评价。问题规模问题规模N对不同的问题其含义不同：对不同的问题其含义不同：对矩阵是阶数；对矩阵是阶数；对多项式运算是多项式项数；对多项式运算是多项式项数；对图是顶点个数；对图是顶点个数；对集合运算是集合中元素个数。对集合运算是集合中元素个数。53有关数量关系计算有关数量关系
25、计算数量关系评价体现在时间数量关系评价体现在时间算法在机器中所耗费时间。算法在机器中所耗费时间。数量关系评价体现在空间数量关系评价体现在空间算法在机器中所占存储量。算法在机器中所占存储量。?关于算法执行时间关于算法执行时间?语句频度语句频度?算法的时间复杂度算法的时间复杂度?数据结构中常用的时间复杂度频率计数数据结构中常用的时间复杂度频率计数?最坏时间复杂度最坏时间复杂度?算法的空间复杂度算法的空间复杂度54关于算法执行时间关于算法执行时间?定义定义：一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。?分析分析：不是针对实际
26、执行时间的精确地算出算法执行不是针对实际执行时间的精确地算出算法执行具体时间，而是针对算法中语句的执行次数做出估具体时间，而是针对算法中语句的执行次数做出估计，从中得到算法执行时间的信息。计，从中得到算法执行时间的信息。55语句频度语句频度?定义：定义：语句频度是指该语句在一个算法中重复执行的次数。语句频度是指该语句在一个算法中重复执行的次数。对应的语句频度对应的语句频度1 1forfor（i=0i=0；i n;i+i n;i+）n n2 2for for（j=0j=0；jn;j+jn;j+）n n2 23 cij=0;n3 cij=0;n2 24 for(k=0;k n;k+)n4 for(
27、k=0;k n;k+)n3 3cij=cij+aikcij=cij+aik*bkj;nbkj;n3 3 例如：例如：算法语句算法语句两个两个矩阵矩阵相乘相乘总执行次数：总执行次数：Tn=2n3+2n2+n56算法的时间复杂度算法的时间复杂度算法的时间复杂度，即是算法的时间量度记做：算法的时间复杂度，即是算法的时间量度记做：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+)fo
28、r(j=1;j=n;j+)x=x+1;时间复杂度为时间复杂度为O(n2),称为平方阶。称为平方阶。57常用的时间复杂度频率计数常用的时间复杂度频率计数?数据结构中常用的时间复杂度频率计数有 7个:O(1)常数型常数型O(n)线性型线性型O(n3)立方型立方型O(2n)指数型指数型O(nlog2n)二维型二维型O(n2)平方型平方型O(log2n)对数型对数型按时间复杂度由小到大排列的频率表：按时间复杂度由小到大排列的频率表：58常用的时间复杂度频率计数常用的时间复杂度频率计数?常用的时间复杂度频率表：常用的时间复杂度频率表：loglog2 2n n0 01 12 23 34 45 5n n1
29、12 24 48 816163232nlognlog2 2n n0 02 28 824246464160160n n2 21 14 41616646425625610241024n n3 31 18 86464512512509650963276832768一般讲：前一般讲：前3种可实现，种可实现，2 2后后3种虽理种虽理论上是可实论上是可实4 4现的，实际现的，实际上只有对上只有对N1616限制在很小限制在很小256256范围才有意范围才有意义，当义，当N较较6553665536大时，不可大时，不可21474836482147483648能实现。能实现。2 2n n59最坏时间复杂度最坏时间
30、复杂度?定义：定义：讨论算法在最坏情况下的时间复杂度，即分讨论算法在最坏情况下的时间复杂度，即分析最坏情况下以估计出算法执行时间的上界。析最坏情况下以估计出算法执行时间的上界。例如冒泡排序算法例如冒泡排序算法60最坏时间复杂度最坏时间复杂度void bubble(int a,int length)将将a中整数数组重新排序，达到中整数数组重新排序，达到temp=aj;递增有序递增有序 aj=aj+1;int i=0,j,temp;aj+1=temp;int change;change=true;dochange=false;i=i+1;for(j=1;jaj+1)while(ilength|ch
31、ange=true)61算法的空间复杂度算法的空间复杂度?定义：用空间复杂度作为算法所需存储空间的量度，用空间复杂度作为算法所需存储空间的量度，记做：记做：S(n)=O(f(n)。621.6 关于学习数据结构关于学习数据结构?数据结构课程地位数据结构课程地位?数据结构课程学习特点数据结构课程学习特点?关于本书内容编写说明关于本书内容编写说明63数据结构课程地位数据结构课程地位?数据结构与其它课程关系图：数据结构与其它课程关系图：操作系统操作系统数据库数据库编译原理编译原理人工智能人工智能非线性程序设计非线性程序设计数据结构专业基础课专业基础课离散数学离散数学语言程序设计语言程序设计计算机原理设
32、计计算机原理设计64数据结构课程学习特点数据结构课程学习特点?教学目标教学目标：学会分析数据对象的特征，掌握数据组织方法和学会分析数据对象的特征，掌握数据组织方法和计算机的表示方法，以便为应用所涉及数据选择适当计算机的表示方法，以便为应用所涉及数据选择适当的逻辑结构、存储结构及相应算法，初步掌握算法时的逻辑结构、存储结构及相应算法，初步掌握算法时间空间分析的技巧，培养良好的程序设计技能。间空间分析的技巧，培养良好的程序设计技能。?学习方法学习方法：学习数据结构，必须经过大量的实践，在实践中学习数据结构，必须经过大量的实践，在实践中体会构造性思维方法，掌握数据组织与程序设计的技体会构造性思维方法，掌握数据组织与程序设计的技术。术。65关于本书内容编写说明关于本书内容编写说明?本书基本结构第一部分：数据结构的基本概念（第第一部分：数据结构的基本概念（第1章）章）第二部分：基本的数据结构第二部分：基本的数据结构包括：线性结构包括：线性结构线性表、栈和队列、串、数组线性表、栈和队列、串、数组与广义表与广义表（第（第25章）章）非线性结构非线性结构树、图（第树、图（第6、7章）章）第三部分：基本技术第三部分：基本技术包括：查找技术与排序技术（第包括：查找技术与排序技术（第8、9、10章）章）66
