02_数据结构基本概念.ppt

数据结构的基本概念;Outline;Outline;什么是数据结构;数据结构;数据及数据元素;数据结构的概念;例：用数据结构描述整数I*;数据结构的概念;数据结构的概念;数据的逻辑结构与数据的存储结构;Outline;数据的逻辑结构 数据元素之间关系的描述 描述法 二元组 关系：一般抽象为前驱与后继关系， 即表明结构中，一个元素的前一个元素是谁，它的后一个元素又是谁 ;图示法 图形要素： 结点和有向线段 结点：表示一个数据元素，一般以方形框代表 不管多么复杂的结点，都看作是一个结点 有向线段：表示元素之间的关系。 箭尾指向的结点是前驱。 箭头指向的结点是后继;数据的逻辑结构;Outline;数据的存储结构（物理结构） 是数据元素在计算机系统存储器中的存放方式 也可以说，是数据逻辑结构在存储器中的存放方式;K1;K1;数据的存储结构;几种物理存储方式 顺序存储方法 连续顺序地存放数据元素 若数据的逻辑结构也是顺序（线性）的，则逻辑结构和物理结构完全统一了 连续存放的数据元素可以在内存中容易找到 ;链接存储方法 元素在内存中不一定连续存放 在元素中附加指针项，通过指针可以找到关系元素;K1;索引存储方法 为放在内存中的元素建立索引表 元素可以离散存放 通过查索引表找到需要的元素;散列存储方法 结点中设一关键值，利用关键值和相应算式算出结点位置（地址） ;小结：数据的逻辑结构与物理结构 1、物理结构是元素在内存中的存储方式，与元素间固有的逻辑关系是相对独立的两个问题 物理结构着眼于结点在内存中的定位 2、简单的逻辑结构可能和物理结构一致 例：线性逻辑关系与顺序存储方法 3、利用物理结构在内存中找到一个结点，而为什么要找这个结点却由元素间的逻辑关系决定 任何一个算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构 4、逻辑结构与存储结构是一个问题的两个方面;Outline;算法 算法的概念及特点 算法是为解决某一特定类型问题规定的运算规则的有穷集合 有穷性：非无限执行，必须在有限步骤内结束 确定性：非二义，下一步必须是明确的 有效性：??一步是可执行的 输入：外部输入零个或多个 输出：至少一个 ;算法与程序 相似：都是解决问题的方法和步骤，是指令的集合 区别： 描述方法 联系：程序用某种程序设计语言来实现算法;要求描述一个算法时必须满足： 对输入和输出的描述 描述语句准确、无二义 保证算法的有穷性和有效性;在数据结构中常见的问题 创建、插入、删除、更新、检索、排序…… 注意：每个问题都有一种和多种算法 找到效率最高的，消耗存储空间最小的 以最容易理解的方式设计 设计的算法不容易出错或出错情况较少 ;数据结构研究什么;一些补充内容;ADT;时间复杂度;空间复杂度