数据结构新1学习.pptx

1内容提要内容提要1 1 1 1给出数据结构的概念给出数据结构的概念2 2 2 2介绍数据抽象和抽象数据类型介绍数据抽象和抽象数据类型3 3 3 3说明数据结构和算法描述的方法说明数据结构和算法描述的方法4 4 4 4介绍算法和算法分析的基本方法介绍算法和算法分析的基本方法第1页/共51页21.1 1.1 算法和数据结构算法和数据结构瑞士的WirthWirth博士图灵奖获得者提出：程序算法+数据结构第2页/共51页31.1 1.1 算法和数据结构算法和数据结构课堂提要课堂提要课堂提要课堂提要第第第第1 1 1 1章章章章 基础知识基础知识基础知识基础知识1.1 1.1 1.1 1.1 算法和数据结构算法和数据结构算法和数据结构算法和数据结构1.2 1.2 1.2 1.2 什么是数据结构什么是数据结构什么是数据结构什么是数据结构1.3 1.3 1.3 1.3 数据抽象和抽象数据抽象和抽象数据抽象和抽象数据抽象和抽象 数据类型数据类型数据类型数据类型 1.4 1.4 1.4 1.4 描述数据结构和描述数据结构和描述数据结构和描述数据结构和 算法算法算法算法1.5 1.5 1.5 1.5 算法分析的基本算法分析的基本算法分析的基本算法分析的基本 方法方法方法方法 数据结构和算法是计算机学科的基础之一，更是软件技术的基础。算法设计通常建立在所处理的数据之上的，精心选择的数据结构可以带来更高效率的算法。程序算法+数据结构第3页/共51页4精心设计的数据结构真的可以带来更高效率的算法吗？第4页/共51页5 图一第5页/共51页6，图二第6页/共51页7 数据在计算机中的表示和存储不能是无组织的，是有规律，有结构的。第7页/共51页81.1.1.1.数据数据：计算机加工处理的对象 2.2.数据元素数据元素：是组成数据的基本单位，在计算机程序中通常作为一个整体来处理。数据元素由若干数据项组成。3.3.数据项数据项是不可再分割的。1.2 1.2 什么是数据结构什么是数据结构 1.2.1 1.2.1 基本概念基本概念第8页/共51页9表1.1 学生情况表学号学号姓名姓名性别性别其他信息其他信息B02040101王小红王小红女女B02040102林悦林悦女女B02040103陈菁陈菁女女B02040104张可可张可可男男数据项第9页/共51页10数据结构的由来数据结构的由来 数数据据结结构构主主要要是是为为研研究究和和解解决决如如何何使使用用计计算算机机组组织织和和处处理理这这些些非非数数值值问问题题而而产产生生的的理理论论、技技术术和和方方法法。它它已已成成为为计计算算机机学学科科研研究究的的基基本课题之一。本课题之一。第10页/共51页11什么是数据结构什么是数据结构定义1-数据元素之间的相互关系称为结构，带有结构的数据元素的集合称为数据结构。定义2-按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示 方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。第11页/共51页12 数据结构包括三个方面数据结构包括三个方面 逻辑结构：数据元素间的逻辑关系；逻辑结构：数据元素间的逻辑关系；存储结构：数据在计算机内的表示形式；存储结构：数据在计算机内的表示形式；运算：在数据上执行的操作运算：在数据上执行的操作。第12页/共51页13数据结构举例 表1.1 学生情况表学号学号姓名姓名性别性别其他信息其他信息B02040101王小红王小红女女B02040102林悦林悦女女B02040103陈菁陈菁女女B02040104张可可张可可男男逻辑结构，存储结构，运算第13页/共51页141.2.2 1.2.2 数据的逻辑结构数据的逻辑结构 数据结构的逻辑结构可以用一个二元组表示。即 DS=（D，R）其中，D是数据元素的有限集合，R是D中数据元素序偶的集合。例如DS=D,R,D=a,b,c,d,R=,DS=D,R,D=a,b,c,d,R=,其中，序偶表示a a和b b之间的关系，我们称为a a是b b的直接前驱，b b是a a的直接后继。小圆圈代表数据元素，两个不同元素的序偶称为边。abcd第14页/共51页154 4种基本的逻辑结构 (a)(a)集合结构(b)(b)线性结构(c)(c)树形结构(d)(d)图结构图1-2 1-2 四种基本的结构关系对数据元素间逻辑关系的描述称为数据的逻辑结构。根据数据结构中数据元素之间关系的不同特征，可以划分为以下四种基本逻辑结构：第15页/共51页16 线性结构：线性结构：线性结构：线性结构：数据元素之间存在数据元素之间存在一对一的关系。一对一的关系。一个前驱，一个前驱，一个后继。一个后继。树形结构：树形结构：树形结构：树形结构：数据元素之间存在数据元素之间存在一对多的关系。一对多的关系。图结构：图结构：图结构：图结构：数据元素之间存在多数据元素之间存在多对多的关系。每个结点的前对多的关系。每个结点的前驱和后继的数目都不同。驱和后继的数目都不同。集合结构：集合结构：结构中的数据元素之间除了“同属于一个集合”的关系外，没有其它关系。四种逻辑结构也可以分成两类：线性结构和非线性结构。(a)(a)集合结构(b)(b)线性结构(c)(c)树形结构(d)(d)图结构图1-2 1-2 四种基本的结构关系第16页/共51页17 几种存储结构几种存储结构 顺序结构顺序结构 链接结构链接结构 索引结构索引结构 散列结构散列结构 地址信息称为链。地址信息称为链。表示空链。表示空链。1.2.3 1.2.3 数据的存储表示数据的存储表示存储结构存储结构:数据结构的实现形式，是数据结构在计数据结构的实现形式，是数据结构在计算机内的表示，即算机内的表示，即数据元素及其关系数据元素及其关系在计算机存在计算机存储器中的存储方式。储器中的存储方式。其中，顺序和链接是两种最基本的存储表示方法。其中，顺序和链接是两种最基本的存储表示方法。第17页/共51页18 顺序存储顺序存储 顺序（或称连续）表示方法需要一块连续的存储空间，并把逻辑上相关的数据元素一次存储在该连续的存储区中。例如，由4个元素组成的线性数据结构（a0,a1,a2,a3），存储在某个连续的存储区内，设存储区的起始地址是102，假定每个元素占2个存储单元。Loc(ak)=102+2 k第18页/共51页19 链式存储链式存储 例如，线性结构（a0,a1,a2,a3）的链接存储表示。结点存储块分成两部分，元素本身和该元素后继元素所在结点的存储地址。Data LinkData Link链接存储表示下，为在机内存储一个元素，除了需要存放该元素本身的信息外，还需要存放于该元素相关的其它元素的地址信息。这两部分信息组成一个数据元素的结点。第19页/共51页20逻辑结构逻辑结构存储结构存储结构概念概念数据元素之间逻数据元素之间逻辑关系的描述辑关系的描述数据及其关系数据及其关系在计在计算机内的组织方式算机内的组织方式面向面向面向应用问题面向应用问题面向计算机面向计算机关系关系存储结构是逻辑结构在计算机内的映像存储结构是逻辑结构在计算机内的映像 小结小结第20页/共51页211.2.4 1.2.4 1.2.4 1.2.4 数据结构的运算数据结构的运算数据结构最常见的运算 创建运算:创建一个数据结构；清除运算:删除数据结构中的全部元素；插入运算:在数据结构的指定位置上插入一个新元素；删除运算:将数据结构中的某个元素删除；第21页/共51页22 静态数据结构静态数据结构和和动态数据结构动态数据结构 如果一个数据结构一旦创建，其结构不发生如果一个数据结构一旦创建，其结构不发生改变，则称为改变，则称为静态数据结构静态数据结构，否则成为，否则成为动动态数据结构态数据结构。第22页/共51页23 小结小结 数据结构是一门研究程序设计问题中计算机的操作对象（数据）以及它们之间的关系和运算的学科。第23页/共51页241.3 1.3 数据抽象和抽象数据类型数据抽象和抽象数据类型 抽象，封装和信息隐蔽是控制软件开发复杂度，提高软件可靠性的重要手段 本书采用抽象数据类型的观点讨论数据结构。课堂提要课堂提要课堂提要课堂提要第第第第1 1 1 1章章章章 基础知识基础知识基础知识基础知识1.1 1.1 1.1 1.1 算法和数据结构算法和数据结构算法和数据结构算法和数据结构1.2 1.2 1.2 1.2 什么是数据结构什么是数据结构什么是数据结构什么是数据结构1.3 1.3 1.3 1.3 数据抽象和抽象数据抽象和抽象数据抽象和抽象数据抽象和抽象 数据类型数据类型数据类型数据类型 1.4 1.4 1.4 1.4 描述数据结构和描述数据结构和描述数据结构和描述数据结构和 算法算法算法算法1.5 1.5 1.5 1.5 算法分析的基本算法分析的基本算法分析的基本算法分析的基本 方法方法方法方法第24页/共51页25 1.C 1.C 语言的数据类型(1)(1)(1)(1)基本类型：基本类型：基本类型：基本类型：字符、整型字符、整型 (2)(2)(2)(2)构造类型：构造类型：构造类型：构造类型：数组、结构和联合数组、结构和联合(3)(3)(3)(3)指针类型：指针类型：指针类型：指针类型：指针指针指针指针例如，例如，int a;int a;变量变量a a 的取值范围是：的取值范围是：-32768-32768 3276732767对变量对变量a a执行的操作有：执行的操作有：算术运算算术运算 +、-、*、/、%关系运算关系运算 、=、=、!=!=2.2.数据类型 一个数据类型定义了一个值的集合以及作用于该值集的操作的集合。即一组值和一组操作。1.3.3 1.3.3 数据类型和抽象数据类型数据类型和抽象数据类型 第25页/共51页26抽象数据类型（A Abstract bstract Data Data Type,Type,ADTADT）是一个数据类型，其主要特征是该类型的对象及其操作的规范,与该类型对象的表示和操作的实现分离，实行封装和信息隐蔽，即使用和实现分离。使用和实现分离：使用者通过规范使用该类型的数据，而不必考虑其实现细节；改变实现将不影响使用。例如，C+C+中的整型intint就是抽象数据类型。它的实现是隐蔽的，使用者只能通过整型上定义的一组运算对整型变量 执行操作。3.3.抽象数据类型第26页/共51页27规范指明“做什么”，实现解决“怎样做”。规范是实现的准则和依据第27页/共51页28一个数据结构包含两个层次：(1)(1)数据结构的规范（抽象层）：逻辑结构和运算的定义组成了数据结构的规范(2)(2)数据结构的实现（实现层）：存储结构和运算算法实现构成了数据结构的实现1.3.4 1.3.4 数据结构和抽象数据类型数据结构和抽象数据类型 一种数据结构被视为一个抽象数据类型。第28页/共51页291.4 描述数据结构和算法描述数据结构和算法第29页/共51页30本书是怎样描述每种数据结构？本书是怎样描述每种数据结构？1.4 1.4 描述数据结构和算法描述数据结构和算法 首先描述数据结构的首先描述数据结构的规范规范（逻辑结构和运逻辑结构和运算的定义）算的定义）然后介绍数据结构的然后介绍数据结构的实现实现（存储结构和运存储结构和运算的具体程序实现算的具体程序实现），），第30页/共51页31 （1 1）用格式化的自然语言来描述数据结构的规范。（2 2）用一个C+C+的抽象模板类描述数据结构的规范。1.4.1 1.4.1 数据结构的规范数据结构的规范1.4 1.4 描述数据结构和算法描述数据结构和算法对数据结构的规范的描述：第31页/共51页32数据结构描述举例-堆栈1.4.1 1.4.1 数据结构的规范数据结构的规范第32页/共51页33ADT 1.1 ADT 1.1 栈抽象数据类型ADT StackADT Stack Data:Data:(描述逻辑结构)0 0个或多个元素的线性序列（a a0 0，a a1 1，a an-1n-1)，遵循LIFOLIFO原则。Operations:Operations:(描述运算的定义)Create()Create()：创建一个空栈。Destroy():Destroy():撤消一个栈。Push(x)Push(x)：元素x x插入栈顶。Pop()Pop()：删除栈顶元素。Top(x)Top(x)：在x x中返回栈顶元素。（1 1）用ADTADT描述数据结构堆栈的例子对堆栈的规范的描述：第33页/共51页34程序 1.1 1.1 栈的C+C+模板抽象类templatetemplateclass Stackclass Stack public:public:virtual void Push(T x)=0;virtual void Push(T x)=0;virtual void Pop()=0;virtual void Pop()=0;virtual T Top(T&x)const=0;virtual T Top(T&x)const=0;除了构造函数，其余成员函数都是纯虚函数。顺序栈类SeqStackSeqStack是类StackStack在顺序存储表示下的一种实现，它是从抽象类StackStack派生出来的，它可以实例化。（2）用C+模板抽象类描述数据结构第34页/共51页35templatetemplatebool SeqStack:Push(T&x)bool SeqStack:Push(T&x)if(IsFull()if(IsFull()coutOverflowendl;coutOverflowendl;return false;return false;s+top=x;s+top=x;return true;return true;1.4.1.4.实现数据结构实现数据结构堆栈的实现：第35页/共51页361.5 1.5 算法分析的基本方法算法分析的基本方法内容提要内容提要 算法及其性能分析 算法的空间复杂度 算法的时间复杂度 渐近时间复杂度课堂提要课堂提要课堂提要课堂提要第第第第1 1 1 1章章章章 基础知识基础知识基础知识基础知识1.1 1.1 1.1 1.1 算法和数据结构算法和数据结构算法和数据结构算法和数据结构1.2 1.2 1.2 1.2 什么是数据结构什么是数据结构什么是数据结构什么是数据结构1.3 1.3 1.3 1.3 数据抽象和抽象数据抽象和抽象数据抽象和抽象数据抽象和抽象 数据类型数据类型数据类型数据类型 1.4 1.4 1.4 1.4 描述数据结构和描述数据结构和描述数据结构和描述数据结构和 算法算法算法算法1.5 1.5 1.5 1.5 算法分析的基本算法分析的基本算法分析的基本算法分析的基本 方法方法方法方法第36页/共51页371.1.什么是算法 一个算法(algorithm)(algorithm)是对特定问题的求解步骤的一种描述，它是指令的有限序列；此外，算法具有下列五个特征：(1)(1)输入 算法有零个或多个输入。(2)(2)输出 算法至少产生一个输出 (3)(3)确定性 算法的每一条指令都有确切的定义，没有二义性。(4)(4)能行性 算法的每一条指令都足够基本，它们可以通过已经实现的基本运算执行有限次来实现。(5)(5)有穷性 算法必须总能在执行有限步之后终止。1.5.1 1.5.1 算法及其性能分析算法及其性能分析 第37页/共51页382.2.算法描述方法 算法可以自然语言、流程图或程序设计语言描述。当一个算法用程序设计语言描述时，便成为程序。本书中，主要使用C+C+语言描述。3.3.算法的性能标准 (1)(1)正确性：算法的执行结果应当满足预先规定的功能和性能 要求。(2)(2)简明性：一个算法应当思路清晰、层次分明、易读易懂。(3)(3)健壮性：当输入不合法数据时，应能做适当处理，不至于 引起严重后果。(4)(4)效 率：有效使用存储空间和有高的时间效率。(5)(5)最优性：解决同一个问题可能有多种算法，应进行比较，选择最佳算法。第38页/共51页391.5.2 1.5.2 算法的时间复杂度算法的时间复杂度 程序步 一个程序步是指在语法上或语义上有意义的程序段，该程序段的执行时间与问题实例的特征无关。算法的时间复杂度 是程序运行从开始到结束所需的时间。第39页/共51页40程序1.3 1.3 求一个数组元素的累加之和float sum(float list,const int n)float sum(float list,const int n)float tempsum=0.0;float tempsum=0.0;for(int i=0;in;i+)for(int i=0;in;i+)tempsum+=listi;tempsum+=listi;return tempsum;return tempsum;程序步数为2n+32n+3。第40页/共51页411.5.3 1.5.3 渐近时间复杂度渐近时间复杂度 大O O记号 如果存在两个正常数c c和n n0 0，使得对所有的n n，n n n n0 0 ，有f(n)f(n)c g(n)c g(n)则有 f(n)=O(g(n)f(n)=O(g(n)。渐近时间复杂度 使用大O O记号表示的算法的时间复杂性，称为算法的渐近时间复杂度,简称时间复杂度。第41页/共51页42渐近时间复杂度 使用大O O记号表示的算法的时间复杂性，称为算法的渐近时间复杂度,简称时间复杂度。大O O记号用以表达一个算法运行时间的上界，可用程序步在数量级上估计算法的执行时间。例如，设 T(n)=3.6nT(n)=3.6n3 3+2.5n+2.5n2 2+2.8+2.8 8.9n8.9n3 3则根据大O O记号的定义容易证明 T(n)=O(nT(n)=O(n3 3)第42页/共51页43例如，程序1.21.2为求一个数组元素的累加之和的算法。float sum(float list,const int n)float sum(float list,const int n)float tempsum=0.0;/1 float tempsum=0.0;/1 for(int i=0;in;i+)/n+1 for(int i=0;in;i+)/n+1 tempsum+=listi;tempsum+=listi;/n /n return tempsum;/1 return tempsum;/1（1 1）总的程序步数为2n+3 2n+3，则渐近时间复杂性为O(n)O(n)。第43页/共51页44float sum(float list,const int n)float sum(float list,const int n)float tempsum=0.0;/1 float tempsum=0.0;/1 for(int i=0;in;i+)/n+1 for(int i=0;in;i+)/n+1 tempsum+=listi;tempsum+=listi;/n /n return tempsum;/1 return tempsum;/1（2 2）语句tempsum+=listitempsum+=listi可认为是关键操作，它的执行次数为n n次，则渐近时间复杂性为O(n)O(n)。很多情况下，可以通过考察一个算法中的关键操作（关键操作被认为是一个执行次数最多的程序步）的执行次数来计算算法的渐近时间复杂性。第44页/共51页45常见的渐近时间复杂性从小到大排列有：O(1)O(log2 n)O(n)O(nlog2 n)O(n2)O(n3)例如：若某算法程序的总程序步为4,则其渐近时间复杂性为多少？O(4)是错误写法。应为O(1)第45页/共51页46void Mult(int ann,bnn,cnn,int n)void Mult(int ann,bnn,cnn,int n)/n/n n n矩阵a a与b b 相乘得到c c。for(int i=0;in;i+)/n+1for(int i=0;in;i+)/n+1 for(int j=0;jn;j+)/n(n+1)for(int j=0;jn;j+)/n(n+1)cij=0;/n cij=0;/n2 2 for(int k=0;kn;k+)/n for(int k=0;kn;k+)/n2 2（n+1)n+1)cij+=aik*bkj;cij+=aik*bkj;/n /n3 3 程序步为：2n2n3 3+3n+3n2 2+2n+1+2n+1 渐近时间复杂度为：T(n)=O(nT(n)=O(n3 3)再看一例：第46页/共51页471.5.4 1.5.4 最好、最坏和平均情况时间复杂度最好、最坏和平均情况时间复杂度 对于某些算法，即使问题实例的规模相同，如果输入的数据不同，算法所需的时间开销也会不同。比如在有n n个元素的一维数组上查找一个给定元素。第47页/共51页48算法的空间复杂度 是程序运行从开始到结束所需的存储量。1.5.5 1.5.5 算法的空间复杂度算法的空间复杂度 第48页/共51页49程序运行所需的存储空间包括两部分：（1 1）固定部分 这部分空间与所处理数据的大小和个数无关，或者称与问题的实例的特征无关。主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。（2 2）可变部分 这部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关。例如，分别为100100个元素的两个数组相加，与分别为1010个元素的两个数组相加，所需的存储空间显然是不同的。第49页/共51页50本章小结需要重点掌握的知识点数据结构的概念（包括三个方面）渐近时间复杂度第50页/共51页51感谢您的观看！第51页/共51页