数据结构-第一章-绪论课件

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