《数据结构严蔚敏课件第章PPT课件》由会员分享，可在线阅读，更多相关《数据结构严蔚敏课件第章PPT课件（14页珍藏版）》请在金锄头文库上搜索。
1、数据结构严蔚敏课件第章PPT课件 数据结构(严蔚敏)课件第11章xx年9月5日星期三2页【课前思考】你过去是否听说过数据结构？你知道数据结构是一门讨论什么内容的学科吗？同学们见过算法+数据结构=程序设计这本书吧，它正好说明数据结构的实质是讨论程序设计的方法。 通过这门课的学习，同学们将掌握非数值计算程序设计中用的基本方法和技巧。 xx年9月5日星期三3页【学习目标】熟悉各名词、术语的含义，掌握基本概念。 理解算法五个要素的确切含义。 掌握计算语句频度和估算算法时间复杂度的方法。 【重点和难点】本章讨论的都是一些基本概念，因此没有难点，重点在于了解有关数据结构的各个名词和术语的含义，以及语句频度
2、和时间复杂度、空间复杂度的估算。 【知识点】数据、数据元素、数据结构、数据类型、抽象数据类型、算法及其设计原则、时间复杂度、空间复杂度。 xx年9月5日星期三4页【学习指南】1.熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。 分清哪些是逻辑结构的性质，哪些是存储结构的性质。 2.了解抽象数据类型的定义、表示和实现方法。 3.熟悉类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、输出的方式以及错误处理方式。 4.理解算法五个要素的确切含义和对算法正确性的理解。 5.掌握计算语句频度和估算算法时间复杂度的方法。 xx年9月5日星期三5页1.1数据结构讨论
3、的范畴1.2基本概念1.3算法和算法的量度xx年9月5日星期三6页1.1数据结构讨论的范畴Niklaus WirthAlgorithm+Data Structures=Programs程序设计:算法:数据结构:为计算机处理问题编制一组指令集处理问题的策略问题的数学模型xx年9月5日星期三7页结构静力分析计算例如:数值计算的程序设计问题线性代数方程组环流模式方程(球面坐标系)全球天气预报xx年9月5日星期三8页非数值计算的程序设计问题例一:求一组(n个)整数中的最大值算法:?模型？基本操作是“比较两个数的大小”取决于整数值的范围xx年9月5日星期三9页例二计算机对弈算法?模型?对弈的规则和策略棋
4、盘及棋盘的格局xx年9月5日星期三10页例三足协的数据库管理算法?模型?需要管理的项目？如何管理？用户界面？各种表格xx年9月5日星期三11页概括地说数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。 xx年9月5日星期三12页1.2基本概念 一、数据与数据结构 二、数据类型 三、抽象数据类型xx年9月5日星期三13页 一、数据与数据结构所有能被输入到计算机中，且能被计算机处理的符号的集合。 数据:是计算机操作的对象的总称。 是计算机处理的信息的某种特定的符号表示形式。 xx年9月5日星期三14页是数据（集合）中的一个“个体”数据元素:是
5、数据结构中讨论的基本单位数据对象是性质相同的数据元素的集合是数据的子集xx年9月5日星期三15页数据项是数据结构中讨论的最小单位数据元素可以是数据项的集合例如描述一个运动员的数据元素可以是年年月月日日姓名俱乐部名称出生日期参加日期职务业绩称之为组合项xx年9月5日星期三16页数据结构带结构的数据元素的集合假设用三个4位的十进制数表示一个含12位位数的十进制数。 3214,6587,9345a1 (3214),a2 (6587),a3 (9345)则在数据元素a 1、a2和a3之间存在着“次序”关系?a1,a2?、?a2,a3?3214，6587，9345a1a2a36587，3214，9345
6、a2a1a3例如:xx年9月5日星期三17页又例，在2行3列的二维数组a1,a2,a3,a4,a5,a6中六个元素之间存在两个关系:a1a2a3a4a5a6行的次序关系:列的次序关系:row=,col=,a1a3a5a2a4a6a1a2a3a4a5a6数据结构带结构的数据元素的集合xx年9月5日星期三18页再例，在一维数组a1,a2,a3,a4,a5,a6的数据元素之间存在如下的次序关系:|i=1,2,3,4,5或者说，数据结构是相互之间存在着某种关系的数据元素的集合。 数据结构带结构的数据元素的集合可见，不同的“关系”构成不同的“结构”xx年9月5日星期三19页数据结构包括以下几个方面?数据
7、元素之间的逻辑关系，即逻辑结构?数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构?施加在该数据上的操作，即数据的运算xx年9月5日星期三20页数据的逻辑结构可归结为以下四类:线性结构树形结构图状结构集合结构xx年9月5日星期三21页数据结构的形式定义为:数据结构是一个二元组Data_Structures=(D,S)其中:D是数据元素的有限集，S是D上关系的有限集。 xx年9月5日星期三22页数据的存储结构(物理结构)逻辑结构在存储器中的映象“数据元素”的映象？“关系”的映象？xx年9月5日星期三23页数据元素的映象方法用二进制位(bit)的位串表示数据元素 (321)10= (50
8、1)8= (101000001)2xx年9月5日星期三24页关系的映象方法（表示?x,y?的方法）顺序映象(顺序存储方法)以相对的存储位置表示后继关系例如:令y的存储位置和x的存储位置之间差一个常量C而C是一个隐含值，整个存储结构中只含数据元素本身的信息x yxx年9月5日星期三25页链式映象(链式存储方法)需要用一个和x在一起的附加信息指示y的存储位置y x不要求在逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系由附加的指针字段表示。 xx年9月5日星期三26页索引存储方法存储结点信息的同时，建立附加的索索引表。 索引表中的每一项称为索引项，索引项的一般形式是关键字与地址。 散列(或哈希
9、)存储方法根据结点的关键字通过散列函数直接计算出一个值，并将这个值作为该结点的存储地址。 xx年9月5日星期三27页在不同的编程环境中，存储结构可有不同的描述方法。 当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。 xx年9月5日星期三28页例如:以三个带有次序关系的整数表示一个长整数时，可利用C语言中提供的整数数组类型。 typedef intLong_int3定义长整数为:xx年9月5日星期三29页 二、数据类型在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。 xx年9月5日星期三30页例如，C语言中提供的基本
10、数据类型有:整型int浮点型float字符型char逻辑型bool（C+语言）双精度型double实型（C+语言）xx年9月5日星期三31页数据类型是一个值的集合和定义在此集合上的一组操作的总称。 不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。 xx年9月5日星期三32页 三、抽象数据类型(Abstract DataType简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。 xx年9月5日星期三33页例如，抽象数据类型复数的定义数据对象De1,e2e1,e2RealSet数据关系R1|e1是复数的实数部分|e2是复数的虚数部分ADT Complexxx年9月5日星期三
11、34页基本操作AssignComplex(&Z,v1,v2)操作结果构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。 DestroyComplex(&Z)操作结果复数Z被销毁。 GetReal(Z,&realPart)初始条件复数已存在。 操作结果用realPart返回复数Z的实部值。 xx年9月5日星期三35页GetImag(Z,&ImagPart)初始条件复数已存在。 操作结果用ImagPart返回复数Z的虚部值。 Add(z1,z2,&sum)初始条件z1,z2是复数。 操作结果用sum返回两个复数z1,z2的和值。 ADT Complexxx年9月5日星期三36页假设:z1和z2
12、是上述定义的复数则Add(z1,z2,z3)操作的结果z3=z1+z2即为用户企求的结果xx年9月5日星期三37页ADT有两个重要特征:数据抽象用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。 数据封装将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。 xx年9月5日星期三38页抽象数据类型的描述方法抽象数据类型可用（D，S，P）三元组表示。 其中D是数据对象；S是D上的关系集；P是对D的基本操作集。 xx年9月5日星期三39页ADT抽象数据类型名数据对象数据对象的定义数据关系数据关系的定义基本操作基本操作
13、的定义ADT抽象数据类型名其中基本操作的定义格式为:基本操作名（参数表）初始条件初始条件描述操作结果操作结果描述xx年9月5日星期三40页赋值参数只为操作提供输入值。 引用参数以&打头，除可提供输入值外，还将返回操作结果。 初始条件描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。 操作结果说明了操作正常完成之后，数据结构的变化状况和应返回的结果。 若初始条件为空，则省略之。 xx年9月5日星期三41页抽象数据类型的表示和实现抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。 例如，对以上定义的复数。 xx年9月5日星期三42页ty
14、pedef structfloat realpart；float imagpart；plex；/-存储结构的定义/-基本操作的函数原型说明void Assign(plex&Z,float realval,float imagval)；/构造复数Z,其实部和虚部分别被赋以参数/realval和imagval的值xx年9月5日星期三43页float GetReal(cpmplex Z)；/返回复数Z的实部值float Getimag(cpmplex Z)；/返回复数Z的虚部值void add(plex z1,plex z2,plex&sum)；/以sum返回两个复数z1,z2的和xx年9月5日星期
15、三44页/-基本操作的实现void add(plex z1,plex z2,plex&sum)/以sum返回两个复数z1,z2的和sum.realpart=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+z2.imagpart;其它省略xx年9月5日星期三45页1.4算法和算法分析 一、算法 二、算法设计的原则 三、算法效率的衡量方法和准则 四、算法的存储空间需求xx年9月5日星期三46页算法是为了解决某类问题而规定的一个有限长的操作序列。 一个算法必须满足以下五个重要特性11有穷性22确定性33可行性44有输入55有输出 一、算法xx年9月5日星期三47页11有穷性对于任意一组合法输入值，在执行有穷步
