《公共基础-数据结构与算法概念》由会员分享，可在线阅读，更多相关《公共基础-数据结构与算法概念（33页珍藏版）》请在金锄头文库上搜索。
1、数据结构东北大学软件学院数据结构课程建设小组 要求掌握表、栈、队列、串、数组、树、图等常用要求掌握表、栈、队列、串、数组、树、图等常用 的一些数据结构的逻辑形式、存储形式以及实现各的一些数据结构的逻辑形式、存储形式以及实现各 种操作的算法。种操作的算法。 熟练使用熟练使用STLSTL编写大型程序，能根据用户的要求及系编写大型程序，能根据用户的要求及系 统提供的数据，设计或选择合适的数据结构并能编统提供的数据，设计或选择合适的数据结构并能编 写正确的算法解决实际问题。写正确的算法解决实际问题。 了解渐进时间复杂了解渐进时间复杂度分析方法，掌握常用算法设计度分析方法，掌握常用算法设计 技术。技术。
2、 参与在软件设计各个阶段的工作，学会设计较复杂参与在软件设计各个阶段的工作，学会设计较复杂 的类来实现特殊的应用；学会调试及锁定性能瓶颈的类来实现特殊的应用；学会调试及锁定性能瓶颈 ；学会编写简练、有效和可扩充性好的代码。；学会编写简练、有效和可扩充性好的代码。本课程学习要求 通过本课程的学习掌握常用数据结构的逻辑结构特通过本课程的学习掌握常用数据结构的逻辑结构特 征、存储结构及相关算法及实现的原理。征、存储结构及相关算法及实现的原理。 学会从问题入手，分析研究计算机加工的数据结构学会从问题入手，分析研究计算机加工的数据结构 的特性，以便为应用所涉及的数据设计适当的逻辑的特性，以便为应用所涉及
3、的数据设计适当的逻辑 结构、存储结构及其相应的操作算法，并初步掌握结构、存储结构及其相应的操作算法，并初步掌握 时间和空间分析技术。时间和空间分析技术。 学会用学会用C+C+语言、使用语言、使用STLSTL进行编程，合理解决问题进行编程，合理解决问题 。 学会书写符合软件工程规范的文件，编写的程序学会书写符合软件工程规范的文件，编写的程序 代码应结构清晰、正确易读，能上机调试并排除错代码应结构清晰、正确易读，能上机调试并排除错 误。误。 本课程学习的目的步骤（1）获取问题的需求 （2）分析问题，从问题抽象出模型 （3）设计阶段，给出解决方案。 （4）估算解决问题的开销，判断其可行性 （5）实现
4、和运行维护计算机解决问题的方法通过对 l问题的抽象 l数据的抽取 l算法的设计分析问题和解决问题，就是应用数据结构 和算法来设计和实现高效程序。问题求解的过程l 描述问题领域中实际对象的数据及数据间的相互关系 l 按照数据及其关系的特点将数据存储到计算机中的存 储器中 l 编写算法模拟对象领域中的求解过程数据结构和算法互为存在问题求解的实质程序原始数据结果数据通讯录中联系人查找问题求解的案例在百度地图搜索引擎上查找餐馆；问题求解的案例在百度地图搜索引擎上查找餐馆；问题求解的案例l 软件工程专业要开设的课程中具有先后关系， 为所有课程安排合适的开设顺序；问题求解的案例C C1 1高等数学高等数学
5、C C2 2程序设计基础程序设计基础C C3 3离散数学离散数学 C C1 1, C, C2 2 C C4 4数据结构数据结构 C C3 3, C, C2 2C C5 5高级语言程序设计高级语言程序设计C C2 2C C6 6编译方法编译方法 C C5 5, C, C4 4C C7 7操作系统操作系统 C C4 4, C, C9 9C C8 8普通物理普通物理 C C1 1C C9 9计算机原理计算机原理 C C8 8数据结构的研究问题：非数值型数据之间的结构关系，及如何表示，如何存储，如何处理。数据结构： 讨论描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现。 为什么要学习数据结
6、构 研究和解决非数值数据的组织和处理研究和解决非数值数据的组织和处理 非数值计算问题的数学模型，不再是数学方程 例子：线性表、树、图、集合 算法算法+ +数据结构数据结构= =程序程序 算法和数据结构之间的关系 软件系统的架构应当建立在数据之上 数据结构的作用范畴数据结构的作用范畴 抽象数据对象的数学模型、明确操作 存储结构上映射数据、实现操作数据结构数据的逻辑结构 图、树、二叉树、线性表数据的存储结构 顺序方法 链式方法 索引方法 散列方法数据的运算 增加、修改、删除 排序、检索n为什么要学习数据结构n n什么是数据与数据结构什么是数据与数据结构n逻辑结构、存储结构及数据的操作内容 数据：数
7、据：数据是信息的载体，是描述客观事物的数数据是信息的载体，是描述客观事物的数 、字符、以及所有能输入到计算机中，被计算机、字符、以及所有能输入到计算机中，被计算机 程序识别和处理的符号的集合。程序识别和处理的符号的集合。 数值性数据数值性数据 非数值性数据非数值性数据 数据对象：数据对象：数据的子集。具有相同性质的数据成数据的子集。具有相同性质的数据成 员（数据元素）的集合。员（数据元素）的集合。 整数数据对象整数数据对象 N N = 0, = 0, 1, 1, 2, 2, 学生数据对象学生数据对象数据的概念数据元素数据元素：数据中的一个数据中的一个“ “个体个体” ”，也称，也称 “ “数据
8、记录数据记录” ” 。是数据结。是数据结构中讨论的基本单位构中讨论的基本单位 。 数据项数据项: : 相当于记录的相当于记录的“ “域域” ”, , 是数据的不可分割的最小单位。是是数据的不可分割的最小单位。是数据结构中讨论的最小单位数据结构中讨论的最小单位 。( (原子项、组合项原子项、组合项) )数据元素数据项数据的概念数据结构 数据结构：数据结构：一类按照一定的逻辑关系组织起来一类按照一定的逻辑关系组织起来 的数据的表示、相关操作的实现的数据的表示、相关操作的实现u逻辑结构：数据元素之间的逻辑关系u存储结构：数据结构在计算机存储器中的表示方法， 也称为存储表示；u运算：结构的行为特征，作
9、用于数据结构上的运算常见的基本数据结构：线性表、字符串、栈、常见的基本数据结构：线性表、字符串、栈、 队列、树和二叉树、图、字典队列、树和二叉树、图、字典数据的逻辑结构定义定义: : 由某一数据对象及该对象中所有数据成员之间的关系组成由某一数据对象及该对象中所有数据成员之间的关系组成 。记为：。记为：Data_StructureData_Structure = D, R = D, R其中：其中：D D是某一数据对象是某一数据对象R R是该对象中所有数据成员之间的关系的有限集合。是该对象中所有数据成员之间的关系的有限集合。“ “学生学生” ”表格表格在这类文档管理的数学模型中, 计算机处理的对象
10、之间通常 存在着一种最简单的线性关系,这类数学模型称为线性模型UNIXUNIX文件系统的系统结构图文件系统的系统结构图/ (root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp课程开设关系图图型结构 数据的逻辑结构 数据的逻辑结构的讨论，一般把重点放在关系关系集 R上； 根据R的性质刻画数据结构的特点，按照数据元 素之间的关系划分可以分成： 一对一：线性结构（linear structure） 一对多：树形结构(tree structure) 多对多：图型或网状结构(graph structure) 数据的存储结构 (物理结
11、构)：数据的各元素及其之间的关系在计算机中的存储表示。是逻辑结构的物理存储方式、存储映像 存储结构类型：顺序结构链式结构索引结构散列结构数据的存储结构顺序结构 用一块连续的存储区域存储数据 按照地址相邻的关系存储数据，借助于存储单元的自然顺序 来表示数据元素之间的关系 访问具有便利性 称之为紧凑存储结构数据的存储结构12345678链式结构 利用指针，在数据元素的存储中附加一个指针字段； 借助于指针指示的关系来表示数据元素的关系 链式存储为经常增删结点的复杂数据结构提供了解决方法 顺序查找 数据的存储结构索引结构 顺序存储的一种推广，使用整数编码来访问数据结点位置 构造一个将整数域Z映射到存储
12、地址域D的函数，把数据元素的整数索引值映射到结点的存储地址，一般用附加的存储空 间构成一个索引表数据的存储结构3337677979673733散列方法 利用散列函数的机制进行存储位置的计算 要适当地选取函数，解决地址冲突的问题数据的存储结构数据运算：定义于逻辑结构、实现于存储结构对数据的检索、插入、删除、更新、排序等操作数据的运算 它研究了计算机需要处理的数据对象和对象 之间的关系。 它刻画了应用中涉及到的数据的逻辑组织。 它描述了数据在计算机中如何存储、传送、 转换。小结小结 为什么要学习数据结构为什么要学习数据结构? ?n从传统的观点来看l数据的逻辑结构u 线性结构u 非线性结构主要讨论哪几种数据结构主要讨论哪几种数据结构？ABCDEFABDEGCABCDE线性结构非线性结构l数据的物理结构u 顺序结构u 链表结构u 散列结构u 索引结构l在数据结构上的操作u 查找u 排序u 插入u 删除u 修改
