数据结构基本概念.ppt

数据结构的基本概念,廖丹 宽带光纤传输与通信系统技术教育部重点实验室 Key Laboratory of Broadband Optical Fiber Transmission and Communication Networks,制作：段景山 廖丹 主讲：廖丹,Outline,数据结构定义 数据的逻辑结构 数据的存储结构 算法,Outline,数据结构定义 数据的逻辑结构 数据的存储结构 算法,什么是数据结构,Niklaus Wirth :算法十数据结构=程序(Algorithms Data Structures Programs，Prentice-Hall，1976) 什么是程序？ 什么是算法？ 什么是数据结构？,数据结构,数据结构的概念 数据及数据元素的概念 数据是客观事物在计算机内的抽象描述 数据指一些事实，或一些数，或一些符号集合 组成数据的“事实”、“数值”或“符号”称为数据元素 数据元素可由若干个数据项组成,数据及数据元素,例1、学生花名册,数据元素,数据,学生名字的集合,每个学生的名字,例2、学生成绩表,数据,数据元素,数据项,学生成绩的集合,每个学生的成绩,名字,成绩,数据结构的概念,数据结构的概念 数据结构讨论计算机系统中数据的组织形式及其相互关系 是相互之间存在一种和多种特定关系的数据元素的集合,例：大楼中的电梯,电梯在楼层中只能逐层移动,例：公司的组织关系,楼层间的关系是线性的,员工间形成树型关系,涉及,元素的集合,元素间的关系,在关系里的操作,电梯的运动,人员的管理,例：用数据结构描述整数I*,1、组成整数数据的全部元素的集合I I 0，1，2，3,2、I中元素的关系集合RE,3、I*的运算集合P，比如算术四则运算,4、P中诸运算的运算规则RU， 如乘、除法优先于加、减法等,I* I，RE，P，RU,数据结构的概念,RE -10,01,12,数据结构的概念,例：用数据结构的思想分析以下实物： 一个十字路口的红绿灯管制 包含两部电梯的管理系统 一条公交路线 成都市公交系统,元素 关系 运算,数据结构的概念,元素集合,元素间的关系,运算,计 算 机 系 统,元素在计算机系统里的表示 字符？字串？整数？ 元素间的逻辑关系逻辑结构 元素在计算机系统中的存储方式，物理空间关系存储结构 操作指令的集合 算法,数据的逻辑结构与数据的存储结构,例：班级里的同学,可能有各种各样的逻辑关系。比如班长、班委、群众等。形成相应的逻辑结构。,上课时，大家的座次形成存储结构,座次（存储结构）可能与逻辑关系有关，也可能无关。,数据结构的概念,此外，数据的运算也是数据结构不可分割的一个方面,Outline,数据结构定义 数据的逻辑结构 数据的存储结构 算法,数据的逻辑结构 数据元素之间关系的描述 描述法 二元组 关系：一般抽象为前驱与后继关系， 即表明结构中，一个元素的前一个元素是谁，它的后一个元素又是谁,B （ K， R ）,K：元素集合,R：元素间关系的集合,数据的逻辑结构,图示法 图形要素： 结点和有向线段 结点：表示一个数据元素，一般以方形框代表 不管多么复杂的结点，都看作是一个结点 有向线段：表示元素之间的关系。 箭尾指向的结点是前驱。 箭头指向的结点是后继,K i,K h,K j,Ki的前驱,Ki的后继,数据的逻辑结构,研究为什么一个结点是 另一个结点的前驱或后继,数据的逻辑结构,线性结构 线性表 队列 堆栈 非线性结构 树 图 集合结构,Outline,数据结构定义 数据的逻辑结构 数据的存储结构 算法,数据的存储结构（物理结构） 是数据元素在计算机系统存储器中的存放方式 也可以说，是数据逻辑结构在存储器中的存放方式,数据的存储结构,存储器的特点：由地址连续的单元构成,K1,K2,K3,K4,数据的存储结构,逻辑结构,K1,K2,K3,K4,K5,K6,数据的存储结构,逻辑结构,数据的存储结构,思考：为什么数据逻辑结构与物理结构没有完全统一？,存储器的特点：由地址连续的单元构成。线性关系,单元间的线性关系有时不能直接反映复杂的逻辑关系,几种物理存储方式 顺序存储方法 连续顺序地存放数据元素 若数据的逻辑结构也是顺序（线性）的，则逻辑结构和物理结构完全统一了 连续存放的数据元素可以在内存中容易找到,数据的存储结构,链接存储方法 元素在内存中不一定连续存放 在元素中附加指针项，通过指针可以找到关系元素,元素指针,结点,元素,指针,数据的存储结构,K1,K2,K3,K4,K5,K6,数据的存储结构,逻辑结构,索引存储方法 为放在内存中的元素建立索引表 元素可以离散存放 通过查索引表找到需要的元素,数据的存储结构,散列存储方法 结点中设一关键值，利用关键值和相应算式算出结点位置（地址）,例：以用户姓名为关键值,DJS,算式：字母的序号相加,041019 33,ZXM,262413 63,数据的存储结构,所以，DJS放在33号地址单元 ZXM放在63号地址单元,小结：数据的逻辑结构与物理结构 1、物理结构是元素在内存中的存储方式，与元素间固有的逻辑关系是相对独立的两个问题 物理结构着眼于结点在内存中的定位 2、简单的逻辑结构可能和物理结构一致 例：线性逻辑关系与顺序存储方法 3、利用物理结构在内存中找到一个结点，而为什么要找这个结点却由元素间的逻辑关系决定 任何一个算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构 4、逻辑结构与存储结构是一个问题的两个方面,数据的逻辑结构和存储结构,Outline,数据结构定义 数据的逻辑结构 数据的存储结构 算法,算法 算法的概念及特点 算法是为解决某一特定类型问题规定的运算规则的有穷集合 有穷性：非无限执行，必须在有限步骤内结束 确定性：非二义，下一步必须是明确的 有效性：每一步是可执行的 输入：外部输入零个或多个 输出：至少一个,特 点,算法,算法与程序 相似：都是解决问题的方法和步骤，是指令的集合 区别： 描述方法 联系：程序用某种程序设计语言来实现算法,程序使用程序设计语言,算法可以使用框图及其他语言,算法,要求描述一个算法时必须满足： 对输入和输出的描述 描述语句准确、无二义 保证算法的有穷性和有效性,算法,在数据结构中常见的问题 创建、插入、删除、更新、检索、排序 注意：每个问题都有一种和多种算法 找到效率最高的，消耗存储空间最小的 以最容易理解的方式设计 设计的算法不容易出错或出错情况较少,算法,数据结构研究什么,数据之间的逻辑关系，建模 数据的存储，如何在计算机中储存 如何高效的处理数据，算法的设计,一些补充内容,在其它一些参考文献中使用的一些常见概念，作一些简单的描述，方便阅读相关资料： ADT 时间复杂度 空间复杂度,ADT,抽象数据类型（Abstract Data Types简称ADT） ADT是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。 抽象数据类型可以看作是描述问题的模型，它独立于具体实现。它的优点是将数据和操作封装在一起，使得用户程序只能通过在ADT里定义的某些操作来访问其中的数据，从而实现了信息隐藏。 举例：食堂的队列如果抽象出来，对外部来说，服务的师傅只需要知道服务队头，而队列内部怎么排的并不需要关心。,时间复杂度,按照不同算法，编写程序，实际运行比较时间效率； 需要实际的代码实现，且受到软件实现等因素影响，所以一般采用事先分析估算的算法； 只考虑问题的规模（一般用用自然数n表示，例如需要处理的数据个数），认为一个特定的算法的时间复杂度，只采取于问题的规模，或者说它是问题的规模的函数； 为了方便比较，通常的做法是，从算法选取一种对于所研究的问题（或算法模型）来说是基本运算的操作（例如比较），以其重复执行的次数作为评价算法时间 时间复杂度一般用O(f(n)来表示 渐进符号（O）的定义：当且仅当存在一个正的常数 C，使得对所有的 n n0 ，有 f(n) Cg(n)则 f(n) = O(g(n),空间复杂度,空间复杂度指算法所需要的额外空间的数理，不包括提供数据是所占用的空间；就是占用内存空间大小的渐进复杂度 程序所需内存空间的大小为关于数据规模的一个函数，如果函数为多项式，那么空间复杂度就是忽略了这个多项式的低次项和常系数的单项式。 如数据规模是n，所需空间是2*n3+5*n2+logn+3个字节，那么空间复杂度是O(n3)。,