公共基础-数据结构与算法概念

东北大学软件学院SoftwareCollegeNortheasternUniversity版权所有 数据结构 东北大学软件学院数据结构课程建设小组 要求掌握表 栈 队列 串 数组 树 图等常用的一些数据结构的逻辑形式 存储形式以及实现各种操作的算法 熟练使用STL编写大型程序 能根据用户的要求及系统提供的数据 设计或选择合适的数据结构并能编写正确的算法解决实际问题 了解渐进时间复杂度分析方法 掌握常用算法设计技术 参与在软件设计各个阶段的工作 学会设计较复杂的类来实现特殊的应用 学会调试及锁定性能瓶颈 学会编写简练 有效和可扩充性好的代码 本课程学习要求 通过本课程的学习掌握常用数据结构的逻辑结构特征 存储结构及相关算法及实现的原理 学会从问题入手 分析研究计算机加工的数据结构的特性 以便为应用所涉及的数据设计适当的逻辑结构 存储结构及其相应的操作算法 并初步掌握时间和空间分析技术 学会用C 语言 使用STL进行编程 合理解决问题 学会书写符合软件工程规范的文件 编写的程序代码应结构清晰 正确易读 能上机调试并排除错误 本课程学习的目的 步骤 1 获取问题的需求 2 分析问题 从问题抽象出模型 3 设计阶段 给出解决方案 4 估算解决问题的开销 判断其可行性 5 实现和运行维护 计算机解决问题的方法 通过对问题的抽象数据的抽取算法的设计分析问题和解决问题 就是应用数据结构和算法来设计和实现高效程序 问题求解的过程 描述问题领域中实际对象的数据及数据间的相互关系按照数据及其关系的特点将数据存储到计算机中的存储器中编写算法模拟对象领域中的求解过程数据结构和算法互为存在 问题求解的实质 通讯录中联系人查找 问题求解的案例 在百度地图搜索引擎上查找餐馆 问题求解的案例 在百度地图搜索引擎上查找餐馆 问题求解的案例 软件工程专业要开设的课程中具有先后关系 为所有课程安排合适的开设顺序 问题求解的案例 C1高等数学C2程序设计基础C3离散数学C1 C2C4数据结构C3 C2C5高级语言程序设计C2C6编译方法C5 C4C7操作系统C4 C9C8普通物理C1C9计算机原理C8 数据结构的研究问题 非数值型数据之间的结构关系 及如何表示 如何存储 如何处理 数据结构 讨论描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现 为什么要学习数据结构 研究和解决非数值数据的组织和处理非数值计算问题的数学模型 不再是数学方程例子 线性表 树 图 集合算法 数据结构 程序算法和数据结构之间的关系软件系统的架构应当建立在数据之上数据结构的作用范畴抽象数据对象的数学模型 明确操作存储结构上映射数据 实现操作 数据结构 数据的逻辑结构图 树 二叉树 线性表数据的存储结构顺序方法链式方法索引方法散列方法数据的运算增加 修改 删除排序 检索 为什么要学习数据结构什么是数据与数据结构逻辑结构 存储结构及数据的操作 内容 数据 数据是信息的载体 是描述客观事物的数 字符 以及所有能输入到计算机中 被计算机程序识别和处理的符号的集合 数值性数据非数值性数据数据对象 数据的子集 具有相同性质的数据成员 数据元素 的集合 整数数据对象N 0 1 2 学生数据对象 数据的概念 数据元素 数据中的一个 个体 也称 数据记录 是数据结构中讨论的基本单位 数据项 相当于记录的 域 是数据的不可分割的最小单位 是数据结构中讨论的最小单位 原子项 组合项 数据元素 数据项 数据的概念 数据结构 数据结构 一类按照一定的逻辑关系组织起来的数据的表示 相关操作的实现逻辑结构 数据元素之间的逻辑关系存储结构 数据结构在计算机存储器中的表示方法 也称为存储表示 运算 结构的行为特征 作用于数据结构上的运算常见的基本数据结构 线性表 字符串 栈 队列 树和二叉树 图 字典 数据的逻辑结构 定义 由某一数据对象及该对象中所有数据成员之间的关系组成 记为 Data Structure D R 其中 D是某一数据对象R是该对象中所有数据成员之间的关系的有限集合 学生 表格 在这类文档管理的数学模型中 计算机处理的对象之间通常存在着一种最简单的线性关系 这类数学模型称为线性模型 UNIX文件系统的系统结构图 root bin lib user etc math ds sw yin tao xie Stack cpp Queue cpp Tree cpp 课程开设关系图 图型结构 数据的逻辑结构 数据的逻辑结构的讨论 一般把重点放在关系集R上 根据R的性质刻画数据结构的特点 按照数据元素之间的关系划分可以分成 一对一 线性结构 linearstructure 一对多 树形结构 treestructure 多对多 图型或网状结构 graphstructure 数据的存储结构 物理结构 数据的各元素及其之间的关系在计算机中的存储表示 是逻辑结构的物理存储方式 存储映像 存储结构类型 顺序结构链式结构索引结构散列结构 数据的存储结构 顺序结构用一块连续的存储区域存储数据按照地址相邻的关系存储数据 借助于存储单元的自然顺序来表示数据元素之间的关系访问具有便利性称之为紧凑存储结构 数据的存储结构 链式结构利用指针 在数据元素的存储中附加一个指针字段 借助于指针指示的关系来表示数据元素的关系链式存储为经常增删结点的复杂数据结构提供了解决方法顺序查找 数据的存储结构 索引结构顺序存储的一种推广 使用整数编码来访问数据结点位置构造一个将整数域Z映射到存储地址域D的函数 把数据元素的整数索引值映射到结点的存储地址 一般用附加的存储空间构成一个索引表 数据的存储结构 散列方法利用散列函数的机制进行存储位置的计算要适当地选取函数 解决地址冲突的问题 数据的存储结构 数据运算 定义于逻辑结构 实现于存储结构对数据的检索 插入 删除 更新 排序等操作 数据的运算 它研究了计算机需要处理的数据对象和对象之间的关系 它刻画了应用中涉及到的数据的逻辑组织 它描述了数据在计算机中如何存储 传送 转换 小结为什么要学