第1章绪论ppt课件.PPT

《第1章绪论ppt课件.PPT》由会员分享，可在线阅读，更多相关《第1章绪论ppt课件.PPT（80页珍藏版）》请在三一文库上搜索。

1、第1章 绪 论,教学目标 学习与数据结构有关的基本概念和基本方法。 重点、难点 数据结构（逻辑结构、存储结构），抽象 数据类（定义、实现），算法（定义、设计要求、描述工具、复杂度分析）。 教学方法 提出问题、分析问题、解决问题,第1章 绪 论,1.7 关于学习数据结构,1.1 数据结构的基本概念(定义),1.2 数据结构的内容（研究范围）,1.3 算法设计,1.4 算法描述工具,1.5 对算法作性能评价,1.6 数据结构与C语言表示,返回,1.1 数据结构的基本概念（定义）,数据结构的相关名词： 数据（Data） 数据元素（Data Element） 数据对象（Data Object） 数据结

2、构（Data Structure） 数据类型(Data Type) 数据抽象与抽象数据类型,数据（Data）,定义： 数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。 数据包含整型、实型、布尔型、图象、字符、声音等一切可以输入到计算机中的符号集合。,例如对C源程序,数据元素（Data Element）,定义： 数据元素是组成数据的基本单位 ，是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。例如：,数据对象（Data Object）,定义： 数据对象是性质相同的数据元素的集合，是数据的一个子集。,整数集合：N=0，1，2， 无限集 字符集合：C=A，B，Z 有限

3、集,例如：,数据结构（Data Structure）,定义： 数据结构是指相互之间存在一种或多种特定关系的数据元素集合，是带有结构的数据元素的集合，它指的是数据元素之间的相互关系，即数据的组织形式。 例如表结构：,数据结构（Data Structure）,树型结构,图结构,数据类型(Data Type),定义： 数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。,如在高级语言中，整型类型的取值范围为： -32768+32767，运算符集合为加、减、乘、除、取模，即+、-、*、/、%。,数据类型(Data Type),高级语言中的数据类型分为两大类：,1.原子类型，其值不可分

4、解。如C语言中的标准类型（整型、实型、字符型、）。,2.结构类型，其值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是非结构的，也可以是结构的。,指针类型属于哪种类型？,数据抽象与抽象数据类型,数据的抽象 抽象数据类型(Abstract Data Type) 抽象数据类型实现 ADT的表示与实现 面向对象的概念 结构化的开发方法与面向对象开发方法不同点,1.2 数据结构的内容,逻辑结构 存储结构 运算集合,逻辑结构,定义： 数据的逻辑结构是指数据元素之间逻辑关系描述。,形式化描述： Data_Structure=（D,R）其中D是数据元素的有限集，R是D上关系的有限集。,四类

5、基本的结构 集合结构、线性结构、树型结构、图状结构。,集合结构,定义： 结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。,例如：,线性结构,定义： 结构中的数据元素之间存在着一对一的线性关系。,例如：,树型结构,定义： 结构中的数据元素之间存在着一对多的层次关系。,例如：,图状结构或网状结构,定义： 结构中的数据元素之间存在着多对多的任意关系。,例如：,综上所述，数据的逻辑结构可概括为：,逻辑结构,存储结构,定义： 存储结构（又称物理结构）是逻辑结构在计算机中存储映象，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。,形式化描述： D要存入机器中，建立一从D的数据

6、元素到存储空间M单元映象S ，DM，即对于每一个d， dD,都有唯一的zM使S（D）=Z, 同时这个映象必须明显或隐含地体现关系R。,逻辑结构与存储结构的关系为：,存储结构是逻辑关系的映象与元素本身映象，是数据结构的实现；逻辑结构是数据结构的抽象。,数据元素之间关系在计算机中的表示方法： 顺序映象 （顺序存储结构） 非顺序映象（非顺序存储结构）,存储结构,运算集合,例如工资表：,数据结构的内容,综上所述，数据结构的内容可归纳为三个部分， 逻辑结构、存储结构和运算集合： 按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机存贮器中，并在这些数据上定义了一个运算的集合，就叫做数据结构

7、。,1.3 算法,算法（Algorithm）定义 算法的特性 算法设计的要求,算法（Algorithm）定义,定义： Algorithm is a finite set of rules which gives a sequence of operation for solving a specific type of problem. 算法是规则的有限集合，是为解决特定问题而规定的一系列操作。,算法的特性,1. 有限性：有限步骤之内正常结束，不能形成无穷循环,2. 确定性：算法中的每一个步骤必须有确定含义，无二 义性得以实现。,3. 输 入： 有多个或0个输入,4. 输 出： 至少有一个或多

8、个输出。,5. 可行性：原则上能精确进行，操作可通过已实现基本 运算执行有限次而完成。,算法设计的要求,算法的正确性,算法特征：,可读性,健壮性,高效率和低存储量,例如要求n个数的最大值问题 给出算法如下： max:=0; for（i=1 ；imax) max=x; ,1.4 算法描述的工具,概述： 算法+数据结构=程序 算法、语言、程序的关系 设计实现算法过程步骤 类描述算法的语言选择,算法、语言、程序的关系,1. 算法：描述了数据对象的元素之间的关系（包括数据逻辑关系、存贮关系描述）。,2. 描述算法的工具：算法可用自然语言、框图或高级程序设计语言进行描述。,3.程序是算法在计算机中的实现

9、。,设计实现算法过程步骤,1. 找出与求解有关的数据元素之间的关系,2. 确定在某一数据对象上所施加运算,3. 考虑数据元素的存储表示,4. 选择描述算法的语言,5.设计实现求解的算法，并用程序语言加以描述。,类描述算法的语言选择,类语言：,类语言是接近于高级语言而又不是严格的高级语言，具有高级语言的一般语句设施，撇掉语言中的细节，以便把注意力主要集中在算法处理步骤本身的描述上。,3.赋值语句,对C语言作以下描述：,（1）简单赋值,1）变量名=表达式 2） 变量+， 3） 变量- -，,（2）串联赋值,变量1=变量2=变量3=变量k=表达式,对C语言作以下描述：,（4）条件赋值,变量名=条件表

10、达式？表达式1:表达式2,（3）成组赋值,(, ,) 数组名1下标1下标2=数组名2下标1下标2,4.条件选择语句,对C语言作以下描述：,if () 语句;,if () 语句1; else 语句2;,情况语句,switch (） case 判断值1: 语句组 1； break; case 判断值2: 语句组 2； break; ,case 判断值n: 语句组n; break; default: 语句组； break; ,对C语言作以下描述：,对C语言作以下描述：,5.循环语句,for 语句,for (；） 循环体语句；,while 语句,while (） 循环体语句； ,对C语言作以下描述：,

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

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

13、=0；jn;j+） n2 3 cij=0; n2 4 for (k=0;k n; k+) n3 cij=cij+aik*bkj; n3 总执行次数：Tn=2n3+2n2 +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)，称为线性阶；,（3）for (i=1; i= n; i+) for (j=1;j= n; j+) x=x+1; 时间复杂度为O(n2), 称为平方阶。,常用的时间复杂度频率计数,数

14、据结构中常用的时间复杂度频率计数有7个:,O(1) 常数型 O(n)线性型 O(n2)平方型 O(n3)立方型 O(2n)指数型 O(log2n)对数型 O(nlog2n)二维型,按时间复杂度由小到大排列的频率表：,常用的时间复杂度频率计数,常用的时间复杂度频率表：,最坏时间复杂度,定义： 讨论算法在最坏情况下的时间复杂度，即分析最坏情况下以估计出算法执行时间的上界。,例如冒泡排序算法,void bubble(int a, int length) 将a中整数数组重新排序，达到递增有序 int i=0, j, temp; int change ; do change=false ; for(j=

15、1;jaj+1), temp= aj; aj=aj+1; aj+1=temp; change=true; i=i+1 ; while(ilength | change=true ) ,最坏时间复杂度,算法的空间复杂度,定义：,用空间复杂度作为算法所需存储空间的量度， 记做： S(n)=O(f (n) 。,1.6 数据结构与C语言表示,1.6.1 数据结构与程序设计的关联性,问题描述：欲求1名学生10次C语言程序设计的测试成绩总分与平均分。其中10次测验的成绩分别为：80，85，77，56，68，83，90，92，80，98。,程序示例1-1：,main() int sum，verage； /*

16、总分，平均分*/ int t1,t2,t3,t4,t5,t6,t7,t8,t9,t10； /*10个变量存10次成绩*/ t1=80；t2=85；t3=77；t4=56； t5=68； /*分别赋值*/ t6=83；t7=90；t8=92；t9=80；t10=98; sum= t1+t2+t3+t4+t5+t6+t7+t8+t9+t10; /*计算总分*/ average=sum/10; /*计算平均分*/ printf(“总分=%dn”,sum); printf(“平均分=%dn”, average); ,根据测试次数与测试成绩的关系，采用数组结构存储测验成绩，提高了程序的适用范围。 mai

17、n() int sum，erage；int i; int t10 =80，85，77，56，68，83，90，92，80，98 /*分别赋值*/ sum=0; /*总分置初值*/ for (i=0; i10; i+) sum=sum+ti; average=sum/10; /*计算平均分*/ printf(“总分=%dn”,sum); printf(“平均分=%dn”, average); ,程序示例1-2：,1.6.2 结构化程序设计与函数的模块化,结构化程序设计 ：是为使程序具有合理的结构，以保证程序正确性而规定的一套程序设计的方法 。,程序设计的实质：算法+数据结构=程序 即“程序是在数

18、据的特定表示方式的基础上，对抽象算法的具体描述”。 程序结构=控制结构+数据结构, 结构化程序设计目的,通过设计结构良好的程序，以程序的静态良好结构保证程序动态执行的正确性，使程序易理解、易调试、易维护，以提高软件开发的效率，减少出错率。,结构化程序设计的构成单元,任何程序都可由顺序、选择、重复三种基本控制结构来组成。,结构化程序设计方法,其一：“自顶向下，逐步求精”的设计思想 ；其二：“独立功能，一个入口，一个出口“的模块化结构； 其三：“仅用三种基本控制结构”的设计原则,1.6.3 面向对象与抽象数据类型,1.面向对象的概念：,面向对象=对象+类+继承+通信,对象：指在应用问题中出现的各种

19、实体、事件、规格说明等 。,类：具有相同属性和服务的对象,继承：是面向对象方法的最有特色的方面。,面向对象程序设计的特点是封装性、继承性和多态性,与数据结构密切相关的是定义在数据结构上的一组操作。,基本操作主要有： 插入：在数据结构中的指定位置上增添新的数据元素 ； 删除：删去数据结构中某个指定数据元素 ； 更新：改变数据结构中某个元素的值，在概念上等价于删除和插入操作的组合 ； 查找：在数据结构中寻找满足某个特定要求的数据元素（的位置和值）； 排序：（在线性结构中）重新安排数据元素之间的逻辑顺序关系，使数据元素按值由小到大或由大到小的次序排列。,结构化与面向对象开发方法的不同点,结构化的开发

20、方法：是面向过程的开发方法，首先着眼于系统要实现的功能。,面向对象的开发方法： 首先着眼于应用问题所涉及的对象，包括对象、对象属性和要求的操作，从而建立对象结构和为解决问题需要执行的时间序列。,用抽象数据类型的概念来指导问题的求解过程：,2抽象数据类型与问题求解方法,定义： 抽象数据类型（简称ADT）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。,一个抽象数据类型确定了一个模型，但将模型的实现细节隐藏起来；它定义了一组运算，但将运算的实现过程隐藏起来。,数据的抽象,汇编语言中十进制表示的数据98.65、9.6E3等, 它们是二进制数据的抽象;,高级语言中，给出更高一级的数据抽

21、象，如整型、实型、字符型等， 还可以进一步定义更高级的数据抽象，如各种表、队、栈、树、图、窗口、管理器等复杂的抽象数据类型。,抽象数据类型,线性表的抽象数据类型的描述：,ADT Linear_list 数据元素 所有ai属于同一数据对象，i=1，2，n n0； 逻辑结构 所有数据元素ai（i=1，2，n-1）存在次序关系 ，ai无前趋，an无后继； 操作 设L为Linear_list Initial(L)初始化空线性表； Length(L)求线性表的表长； Get(L,i)取线性表的第i个元素； Insert(L,i,b)在线性表的第i个位置插入元素b； Delete(L,i)删除线性表的第i

22、个元素；,抽象数据类型实现,传统的面向过程的程序设计,实现的三种方法：,“包”、“模型”的设计方法,面向对象的程序设计（Object Oriented Programming，简称OOP）,ADT的表示与实现,ADT的定义：,ADT 数据对象: 结构关系: 基本操作: ADT ,基本操作的定义格式为：, (参数表) 操作前提: 操作结果:,关于参数传递：,参数表中的参数有值参和变参两种。,用标准C语言表示和实现ADT描述时，主要有两个方面：,二、用C语言函数实现各操作。,一、通过结构体将int、float等固有类型组合到一起,构成一个结构类型,再用typedef为该类型或该类型指针重新起一个名

23、字。,ADT的表示与实现,1.6.4 算法描述规范与设计风格,1. 算法表示格式与函数模块化,函数返回值类型 函数名（形式参数及说明） 内部数据说明； 执行语句组； /*函数名*/,算法表示格式,1.6.4 算法描述规范与设计风格,函数的模块化,1. 算法表示格式与函数模块化,包含文件语句 宏定义语句 自定义类型语句 所有子函数的原型说明 子函数1定义 . . . 子函数n定义 主函数定义,2. 算法描述要点,1.6.4 算法描述规范与设计风格,加上必要的注释,注释形式可以用/*字符串*/,避免函数返回值隐含说明,预定义常量和类型,# define TRUE 1 # define FALSE

24、0 # define MAXSIZE 100 # define OK 1 # define ERROR 0,避免可能出现的二义性表达,注意不同的退出语句区别,return 或return：用于函数结束。 break语句：可用在循环语句或switch语句中结束循环过程或跳出情况语句。 continue语句：可用在循环语句中结束本次循环过程，进入下一次循环过程。 exit语句：表示出现异常情况时，控制退出函数。,使用有意义的函数名与变量名,2. 算法描述要点,1.6.4 算法描述规范与设计风格,简化输入、输出表述,规范多分支转向,3. 与参数传递的相关技术,1.6.4 算法描述规范与设计风格,变量

25、的作用域,全局变量：程序中所有函数都可以访问的量,局部变量：只能在该函数中访问的量。,参数传递方式,参数传递是函数之间进行信息通讯的重要渠道。其参数传递的主要方式有传值和传地址两类。函数参数表中的参数有两种：第一种参数只为操作提供待处理数据,又称值参；第二种参数既能为操作提供待处理数据，又能返回操作结果，也称变量参数。,#include viod swap1(int a,int b) int c; c=a; a=b; b=c; printf(“swap1中的a= %d,b=%d”,a,b); viod swap2(int *a,int *b) int c; c=*a, *a=*b, *b=c;

26、 ,关于参数传递示例源程序：,void main() int x=100,y=800; swap1(x,y); /*调用函数swap1()*/ printf(“n调用swap1后x= %d,y=%d”,x,y); /*输出调用swap1后的数据*/ x=100;y=800; swap2( /*输出调用swap2后的数据*/ ,关于参数传递示例源程序：,4. 函数结果的带出方式,1.6.4 算法描述规范与设计风格,三种带出方式:全程量、函数返回值、传址参数,若函数结果需要带出多个值，该怎样实现?可以采用全局变量方式带出，通过地址传递带出（数组方式、结构体方式、指针方式）两类方式之一来实现。,通过

27、参数表的参数传递是一种参数显式传递方式，而通过全局变量是一种隐式参数传递，一个函数中对全局变量的改变会影响其它程序的调用，使用全局变量必须注意这个问题。,全局变量方式：,int MIN; /* 全局变量 */ int fun1(int a, int n) /*通过函数return返回最大值，通过全局变量MIN带回最小值*/ int i,max; max=MIN=a0; /给最大值最小值赋初值 for (i=0;imax) max=ai; if (aiMIN) MIN=ai; return(max); ,一个全局变量方式带出的例子,int *fun2(int a,int n) /*将最大、最小值

28、放到数组b中，通过return返回*/ static int b2; b0=b1=a0; /给最大值最小值赋初值 int i; for (i=1;ib0) b0=ai; if (aib1) b1=ai; return(b); ,数组方式带出的例子,Data *fun3(int a,int n) /*将最大、最小值放到结构体指针p中，通过return返回*/ Data *p; int i; p=(Data *)malloc(sizeof(Data *); /指针初始化 p-max=p-min=a0; /给最大值最小值赋初值 for(i=1;ip-max) p-max=ai; if (aimin)

29、 p-min=ai; return(p); ,结构体方式带出的例子,Data fun4(int a,int n) /*将最大、最小值放到结构体p中，通过结构体p带回返回值*/ Data p; int i; p.max=p.min=a0; /给最大值最小值赋初值 for(i=1;ip.max) p.max=ai; if (aip.min) p.min=ai; return(p); ,指针方式带出的例子,1.7 关于学习数据结构,数据结构课程地位 数据结构课程学习特点 关于本书内容编写说明,数据结构课程地位,数据结构与其它课程关系图：,数据结构,数据库,人工智能,专业基础课,操作系统,编译原理,非

30、线性程序设计,离散数学,语言程序设计,计算机原理设计,数据结构课程学习特点,教学目标： 学会分析数据对象的特征，掌握数据组织方法和计算机的表示方法，以便为应用所涉及数据选择适当的逻辑结构、存储结构及相应算法，初步掌握算法时间空间分析的技巧，培养良好的程序设计技能。 学习方法： 学习数据结构，必须经过大量的实践，在实践中体会构造性思维方法，掌握数据组织与程序设计的技术。,要点小结,1. 掌握数据结构的基本概念,数据结构包括数据的逻辑结构、存储结构和运算集合这三个部分,2. 注意逻辑结构与存储结构的区别,要点小结,逻辑结构定义了数据元素之间的逻辑关系。 存储结构是逻辑结构在计算机中实现。 一种逻辑结构可以采用不同存储方式存放在计算机中，但都必须反映出要求的逻辑关系。,要点小结,3面向对象概念：理解什么是数据类型、抽象数据类型、数据抽象和信息隐蔽规则。了解什么是面向对象。,抽象数据类型的封装性； Coad与Yourdon定义：面向对象=对象+类+继承+通信； 面向对象方法着眼点在于应用问题所涉及的对象。,4算法与算法分析：理解算法的定义、算法的特性、算法的时间代价、算法的空间代价。,要点小结,算法与程序的不同之处需要从算法的特性来解释； 算法的正确性是最重要的要求，理解正确性的层次； 算法的可读性是必须考虑的，算法描述的格式与方法； 算法的时间代价是指算法的渐进时间复杂性度量。,返回,