机电系统软件设计方法-03数据结构.pdf

机电系统软件基础 机电系统软件基础 机机电电系系统统软软件件基基础础 机电系统软件基础 机电系统软件基础 机机电电系系统统软软件件基基础础 第三讲：数据结构与操作 内容大纲 • 什么是数据结构 • 基础数据结构 – 线性数据结构 – 非线性数据结构 • 常用操作 – 查找，插入和删除 • 作业与思考 1：什么是数据结构 • 数据结构是计算机存储、组织数据的方式 • 数据结构是指相互之间存在一种或多种特 定关系的数据元素的集合 • 通常情况下，精心选择的数据结构可以带 来更高的运行或者存储效率 • 数据结构往往同高效的检索算法和索引技 术有关。 1：什么是数据结构 • 为什么需要数据结构？ – 信息的表示 – 信息的处理 • 举例 – 图书检索 – 井字棋 – 交通管理问题 图书检索 井字棋博弈 交通管理问题 基本概念和术语 • 数据 – 客观事物的符号表示 • 数据元素 – 数据处理的基本单元 • 数据对象 – 相同性质的数据元素的集合 • 数据结构 – 特定关系数据元素的集合 – 集合 – 线性结构 – 树形结构 – 图或网状结构 基本概念和术语 • 逻辑结构 – 数据元素之间的逻辑关系 • 物理结构 – 又叫存储结构 – 顺序存储结构 – 链式存储结构 基本概念和术语 • 数据类型 • 抽象数据类型 • 算法 – 问题求解步骤的一种描述 • 算法分析 – 时间复杂度 T(N)=O(f(n)) – 空间复杂度 S(N)=O(f(n)) 2：线性数据结构 • 线性表 – N个数据元素的有限序列 – “ ” 唯一的一个 第一个元素 – “ ” 唯一的一个 最后一个元素 – 除第一个元素外，其他任何元素都只有一个前 驱 – 除最后一个元素外，其他任意元素都只有一个 后继 2：线性数据结构 • 线性表举例 2：线性数据结构 • 线性表的物理存储方 式 – 顺序存储 – 链式存储 比较两种存储方式的区别 • 线性存储 – 需要连续的内存空间 – 可以直接访问任意元素 – 添加删除元素时需要移动大量的数据 • 链式存储 – 对存储空间没特殊要求 – 会浪费一定的存储空间 – 查找元素需要遍历 – 添加、删除操作简便 2：线性数据结构 • 栈和队列 栈和队列 • 本质上是线性表 • 只是限制了数据进出的方向 – 先进先出：队列 – 先进后出：堆栈 • 数据存储方式与线性表相同 • 操作被限制了 – pop push 队列： 和 – pop push 堆栈： 和 更复杂的队列 • 双向队列 • 循环队列 3：非线