数据结构课件第1章-新.ppt

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

1、1,引 言 数据结构的概念及其研究的问题，是本章中重要的概念，它们贯穿整本书。除了数据结构研究的三个方面，我们对每种数据结构都会给出应用的实例。要学会描述数据结构和算法，分析算法的时、空复杂度。,第1章 基础知识,数据结构,DATA STRUCTURE,2,内容提要1给出数据结构的概念2介绍数据抽象和抽象数据类型3说明数据结构和算法描述的方法4介绍算法和算法分析的基本方法,3,1.1 算法和数据结构,瑞士的Wirth博士图灵奖获得者提出：程序算法+数据结构,4,1.1 算法和数据结构,课堂提要第1章 基础知识1.1 算法和数据结构1.2 什么是数据结构1.3 数据抽象和抽象 数据类型 1.4

2、描述数据结构和 算法1.5 算法分析的基本 方法,数据结构和算法是计算机学科的基础之一，更是软件技术的基础。算法设计通常建立在所处理的数据之上的，精心选择的数据结构可以带来更高效率的算法。,程序算法+数据结构,5,精心设计的数据结构真的可以带来更高效率的算法吗？,6,图一,7,，,图二,8,数据在计算机中的表示和存储不能是无组织的，是有规律，有结构的。,9,1.数据：计算机加工处理的对象 2.数据元素：是组成数据的基本单位，在计算机程序中通常作为一个整体来处理。数据元素由若干数据项组成。3.数据项是不可再分割的。,1.2 什么是数据结构,1.2.1 基本概念,10,表1.1 学生情况表,数据项

3、,11,数据结构的由来 数据结构主要是为研究和解决如何使用计算机组织和处理这些非数值问题而产生的理论、技术和方法。它已成为计算机学科研究的基本课题之一。,12,什么是数据结构定义1-数据元素之间的相互关系称为结构，带有结构的数据元素的集合称为数据结构。定义2-按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示 方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。,13,数据结构包括三个方面 逻辑结构：数据元素间的逻辑关系；存储结构：数据在计算机内的表示形式；运算：在数据上执行的操作。,14,数据结构举例,表1.1 学生情况表,逻辑结构，存

4、储结构，运算,15,1.2.2 数据的逻辑结构,数据结构的逻辑结构可以用一个二元组表示。即 DS=（D，R）其中，D是数据元素的有限集合，R是D中数据元素序偶的集合。,例如DS=D,R,D=a,b,c,d,R=,其中，序偶表示a和b之间的关系，我们称为a是b的直接前驱，b是a的直接后继。小圆圈代表数据元素，两个不同元素的序偶称为边。,16,4种基本的逻辑结构,对数据元素间逻辑关系的描述称为数据的逻辑结构。根据数据结构中数据元素之间关系的不同特征，可以划分为以下四种基本逻辑结构：,17,线性结构：数据元素之间存在一对一的关系。一个前驱，一个后继。树形结构：数据元素之间存在一对多的关系。图结构：数

5、据元素之间存在多对多的关系。每个结点的前驱和后继的数目都不同。,集合结构：结构中的数据元素之间除了“同属于一个集合”的关系外，没有其它关系。,四种逻辑结构也可以分成两类：线性结构和非线性结构。,18,几种存储结构 顺序结构 链接结构 索引结构 散列结构,地址信息称为链。表示空链。,1.2.3 数据的存储表示,存储结构:数据结构的实现形式，是数据结构在计算机内的表示，即数据元素及其关系在计算机存储器中的存储方式。,其中，顺序和链接是两种最基本的存储表示方法。,19,顺序存储 顺序（或称连续）表示方法需要一块连续的存储空间，并把逻辑上相关的数据元素一次存储在该连续的存储区中。,例如，由4个元素组成

6、的线性数据结构（a0,a1,a2,a3），存储在某个连续的存储区内，设存储区的起始地址是102，假定每个元素占2个存储单元。,Loc(ak)=102+2 k,20,链式存储,例如，线性结构（a0,a1,a2,a3）的链接存储表示。,结点存储块分成两部分，元素本身和该元素后继元素所在结点的存储地址。,Data Link,链接存储表示下，为在机内存储一个元素，除了需要存放该元素本身的信息外，还需要存放于该元素相关的其它元素的地址信息。这两部分信息组成一个数据元素的结点。,21,小结,22,1.2.4 数据结构的运算,数据结构最常见的运算 创建运算:创建一个数据结构；清除运算:删除数据结构中的全部元

7、素；插入运算:在数据结构的指定位置上插入一个新元素；删除运算:将数据结构中的某个元素删除；,23,静态数据结构和动态数据结构 如果一个数据结构一旦创建，其结构不发生改变，则称为静态数据结构，否则成为动态数据结构。,24,小结 数据结构是一门研究程序设计问题中计算机的操作对象（数据）以及它们之间的关系和运算的学科。,25,1.3 数据抽象和抽象数据类型,抽象，封装和信息隐蔽是控制软件开发复杂度，提高软件可靠性的重要手段,本书采用抽象数据类型的观点讨论数据结构。,课堂提要第1章 基础知识1.1 算法和数据结构1.2 什么是数据结构1.3 数据抽象和抽象 数据类型 1.4 描述数据结构和 算法1.5

8、 算法分析的基本 方法,26,1.C 语言的数据类型(1)基本类型：字符、整型(2)构造类型：数组、结构和联合(3)指针类型：指针,例如，int a;变量a 的取值范围是：-3276832767对变量a执行的操作有：算术运算+、-、*、/、%关系运算、=、=、!=,2.数据类型 一个数据类型定义了一个值的集合以及作用于该值集的操作的集合。即一组值和一组操作。,1.3.3 数据类型和抽象数据类型,27,抽象数据类型（Abstract Data Type,ADT）是一个数据类型，其主要特征是该类型的对象及其操作的规范,与该类型对象的表示和操作的实现分离，实行封装和信息隐蔽，即使用和实现分离。,使用

9、和实现分离：使用者通过规范使用该类型的数据，而不必考虑其实现细节；改变实现将不影响使用。,例如，C+中的整型int就是抽象数据类型。它的实现是隐蔽的，使用者只能通过整型上定义的一组运算对整型变量 执行操作。,3.抽象数据类型,28,规范指明“做什么”，实现解决“怎样做”。规范是实现的准则和依据,29,一个数据结构包含两个层次：(1)数据结构的规范（抽象层）：逻辑结构和运算的定义组成了数据结构的规范(2)数据结构的实现（实现层）：存储结构和运算算法实现构成了数据结构的实现,1.3.4 数据结构和抽象数据类型,一种数据结构被视为一个抽象数据类型。,30,1.4 描述数据结构和算法,31,本书是怎样

10、描述每种数据结构？,1.4 描述数据结构和算法,首先描述数据结构的规范（逻辑结构和运算的定义）然后介绍数据结构的实现（存储结构和运算的具体程序实现），,32,（1）用格式化的自然语言来描述数据结构的规范。（2）用一个C+的抽象模板类描述数据结构的规范。,1.4.1 数据结构的规范,1.4 描述数据结构和算法,对数据结构的规范的描述：,33,数据结构描述举例-堆栈,1.4.1 数据结构的规范,34,ADT 1.1 栈抽象数据类型ADT Stack Data:(描述逻辑结构)0个或多个元素的线性序列（a0，a1，an-1)，遵循LIFO原则。Operations:(描述运算的定义)Create()

11、：创建一个空栈。Destroy():撤消一个栈。Push(x)：元素x插入栈顶。Pop()：删除栈顶元素。Top(x)：在x中返回栈顶元素。,（1）用ADT描述数据结构堆栈的例子,对堆栈的规范的描述：,35,程序 1.1 栈的C+模板抽象类templateclass Stack public:virtual void Push(T x)=0;virtual void Pop()=0;virtual T Top(T 除了构造函数，其余成员函数都是纯虚函数。顺序栈类SeqStack是类Stack在顺序存储表示下的一种实现，它是从抽象类Stack派生出来的，它可以实例化。,（2）用C+模板抽象类描述

12、数据结构,36,templatebool SeqStack:Push(T,1.4.实现数据结构,堆栈的实现：,37,1.5 算法分析的基本方法,内容提要 算法及其性能分析 算法的空间复杂度 算法的时间复杂度 渐近时间复杂度,课堂提要第1章 基础知识1.1 算法和数据结构1.2 什么是数据结构1.3 数据抽象和抽象 数据类型 1.4 描述数据结构和 算法1.5 算法分析的基本 方法,38,1.什么是算法 一个算法(algorithm)是对特定问题的求解步骤的一种描述，它是指令的有限序列；此外，算法具有下列五个特征：(1)输入 算法有零个或多个输入。(2)输出 算法至少产生一个输出(3)确定性 算

13、法的每一条指令都有确切的定义，没有二义性。(4)能行性 算法的每一条指令都足够基本，它们可以通过已经实现的基本运算执行有限次来实现。(5)有穷性 算法必须总能在执行有限步之后终止。,1.5.1 算法及其性能分析,39,2.算法描述方法 算法可以自然语言、流程图或程序设计语言描述。当一个算法用程序设计语言描述时，便成为程序。本书中，主要使用C+语言描述。,3.算法的性能标准 正确性：算法的执行结果应当满足预先规定的功能和性能 要求。(2)简明性：一个算法应当思路清晰、层次分明、易读易懂。(3)健壮性：当输入不合法数据时，应能做适当处理，不至于 引起严重后果。(4)效 率：有效使用存储空间和有高的

14、时间效率。(5)最优性：解决同一个问题可能有多种算法，应进行比较，选择最佳算法。,40,1.5.2 算法的时间复杂度,程序步 一个程序步是指在语法上或语义上有意义的程序段，该程序段的执行时间与问题实例的特征无关。,算法的时间复杂度 是程序运行从开始到结束所需的时间。,41,程序1.3 求一个数组元素的累加之和float sum(float list,const int n)float tempsum=0.0;for(int i=0;in;i+)tempsum+=listi;return tempsum;,程序步数为2n+3。,42,1.5.3 渐近时间复杂度,大O记号 如果存在两个正常数c和n

15、0，使得对所有的n，nn0，有f(n)c g(n)则有 f(n)=O(g(n)。,渐近时间复杂度 使用大O记号表示的算法的时间复杂性，称为算法的渐近时间复杂度,简称时间复杂度。,43,渐近时间复杂度 使用大O记号表示的算法的时间复杂性，称为算法的渐近时间复杂度,简称时间复杂度。,大O记号用以表达一个算法运行时间的上界，可用程序步在数量级上估计算法的执行时间。,例如，设 T(n)=3.6n3+2.5n2+2.88.9n3则根据大O记号的定义容易证明 T(n)=O(n3),44,例如，程序1.2为求一个数组元素的累加之和的算法。,float sum(float list,const int n)f

16、loat tempsum=0.0;/1 for(int i=0;in;i+)/n+1 tempsum+=listi;/n return tempsum;/1（1）总的程序步数为2n+3，则渐近时间复杂性为O(n)。,45,float sum(float list,const int n)float tempsum=0.0;/1 for(int i=0;in;i+)/n+1 tempsum+=listi;/n return tempsum;/1（2）语句tempsum+=listi可认为是关键操作，它的执行次数为n次，则渐近时间复杂性为O(n)。,很多情况下，可以通过考察一个算法中的关键操作（关

17、键操作被认为是一个执行次数最多的程序步）的执行次数来计算算法的渐近时间复杂性。,46,常见的渐近时间复杂性从小到大排列有：O(1)O(log2 n)O(n)O(nlog2 n)O(n2)O(n3)例如：若某算法程序的总程序步为4,则其渐近时间复杂性为多少？O(4)是错误写法。应为O(1),47,void Mult(int ann,bnn,cnn,int n)/nn矩阵a与b 相乘得到c。for(int i=0;in;i+)/n+1 for(int j=0;jn;j+)/n(n+1)cij=0;/n2 for(int k=0;kn;k+)/n2（n+1)cij+=aik*bkj;/n3 程序步为

18、：2n3+3n2+2n+1 渐近时间复杂度为：T(n)=O(n3),再看一例：,48,1.5.4 最好、最坏和平均情况时间复杂度,对于某些算法，即使问题实例的规模相同，如果输入的数据不同，算法所需的时间开销也会不同。比如在有n个元素的一维数组上查找一个给定元素。,49,算法的空间复杂度 是程序运行从开始到结束所需的存储量。,1.5.5 算法的空间复杂度,50,程序运行所需的存储空间包括两部分：（1）固定部分 这部分空间与所处理数据的大小和个数无关，或者称与问题的实例的特征无关。主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。（2）可变部分 这部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关。例如，分别为100个元素的两个数组相加，与分别为10个元素的两个数组相加，所需的存储空间显然是不同的。,51,本章小结,需要重点掌握的知识点数据结构的概念（包括三个方面）渐近时间复杂度,