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