数据结构 东北大学软件学院数据结构课程建设小组.  通过本课程的学习掌握常用数据结构的逻辑结构特 征、存储结构及相关算法及实现的原理。  学会从问题入手，分析研究计算机加工的数据结构 的特性，以便为应用所涉及的数据设计适当的逻辑 结构、存储结构及其相应的操作算法，并初步掌握 时间和空间分析技术。

Presentation on theme: "数据结构 东北大学软件学院数据结构课程建设小组.  通过本课程的学习掌握常用数据结构的逻辑结构特 征、存储结构及相关算法及实现的原理。  学会从问题入手，分析研究计算机加工的数据结构 的特性，以便为应用所涉及的数据设计适当的逻辑 结构、存储结构及其相应的操作算法，并初步掌握 时间和空间分析技术。"— Presentation transcript:

1 数据结构 东北大学软件学院数据结构课程建设小组

2  通过本课程的学习掌握常用数据结构的逻辑结构特 征、存储结构及相关算法及实现的原理。  学会从问题入手，分析研究计算机加工的数据结构 的特性，以便为应用所涉及的数据设计适当的逻辑 结构、存储结构及其相应的操作算法，并初步掌握 时间和空间分析技术。  学会用 C++ 语言、使用 STL 进行编程，合理解决问 题。  学会书写符合软件工程规范的文件，编写的程序代 码应结构清晰、正确易读，能上机调试并排除错误。 本课程学习的目的

3  要求掌握表、栈、队列、串、数组、树、图等常用 的一些数据结构的逻辑形式、存储形式以及实现各 种操作的算法。  熟练使用 STL 编写大型程序，能根据用户的要求及 系统提供的数据，设计或选择合适的数据结构并能 编写正确的算法解决实际问题。  了解渐进时间复杂度分析方法，掌握常用算法设计 技术。  参与在软件设计各个阶段的工作，学会设计较复杂 的类来实现特殊的应用；学会调试及锁定性能瓶颈； 学会编写简练、有效和可扩充性好的代码。 本课程学习要求

4  教材  殷人昆，陶永雷等编著：《数据结构》（用面向对象方法与 C++ 描述），清华大学出版社， 2005.11 教材及参考书 (1)

5  推荐参考书  Mark Allen Weiss, 《 Data Structures and Problem Solving Using C++ 》, 影印版，清华大 学出版社。  Herbert Schildt, C++: The Complete Reference, Fourth Edition, 周志荣等译，电子工业出版社出 版  Herbert Schildt, C++: The Complete Reference, Fourth Edition, 周志荣等译 ，电子工业出版社出 版 教材及参考书 (2)

6  习题参考书  殷人昆，徐孝凯编著：《数据结构习题解析》（用面 向对象方法与 C++ 描述） 清华大学出版社， 2005.7 教材及参考书 (3)

7  学时分配：授课 56 学时 上机实验 8 学时 课外实验 32 学时  课程成绩： 平时成绩 ＋ 期末考试成绩 平时成绩 40 ％ 书面作业、上机实验 期末考试 60 ％ 闭卷笔试 学时分配及考核方式

8 学时安排 教学内容讲课上机时间小计 第 1 章 绪论 4 4 第 2 章 数组 44 第 3 章 链表 4 4 第 4 章 栈和队列 44 4 第 5 章 递归 42 第 6 章 树与森林 10 第 7 章 集合与搜索 6 6 第 8 章 图 8412 第 9 章 排序 86 第 10 章 索引结构与散列 4 4 总 计 56864

9 数据结构与算法基础 第一部分：数据结构的概念

10 为什么要学习数据结构 为什么要学习数据结构 什么是数据与数据结构 逻辑结构、存储结构及数据的操作 内容

11  步骤 （ 1 ）获取问题的需求 （ 2 ）分析问题，从问题抽象出模型 （ 3 ）设计阶段，给出解决方案。 （ 4 ）估算解决问题的开销，判断其可行性 （ 5 ）实现和运行维护 计算机解决问题的方法

12 通过对 问题的抽象 数据的抽取 算法的设计 。 分析问题和解决问题，就是应用数据结构 和算法来设计和实现高效程序。 问题求解的过程

13 描述问题领域中实际对象的数据及数据间的相互关系 按照数据及其关系的特点将数据存储到计算机中的存 储器中 编写算法模拟对象领域中的求解过程 数据结构和算法互为存在 问题求解的实质 程序 原始数据 结果数据

14 通讯录中联系人查找 问题求解的案例

15 在百度地图搜索引擎上查找餐馆； 问题求解的案例

16 在百度地图搜索引擎上查找餐馆； 问题求解的案例

17 软件工程专业要开设的课程中具有先后关系， 为所有课程安排合适的开设顺序； 问题求解的案例 C 1 高等数学 C 1 高等数学 C 2 程序设计基础 C 2 程序设计基础 C 3 离散数学 C 1, C 2 C 3 离散数学 C 1, C 2 C 4 数据结构 C 3, C 2 C 4 数据结构 C 3, C 2 C 5 高级语言程序设计 C 2 C 5 高级语言程序设计 C 2 C 6 编译方法 C 5, C 4 C 6 编译方法 C 5, C 4 C 7 操作系统 C 4, C 9 C 7 操作系统 C 4, C 9 C 8 普通物理 C 1 C 8 普通物理 C 1 C 9 计算机原理 C 8 C 9 计算机原理 C 8

18 数据结构的研究问题： 非数值型数据之间的结构关系， 及如何表示，如何存储，如何处理。 数据结构： 讨论描述现实世界实体的数学模型 及其上的操作在计算机中的表示和实现。

19 为什么要学习数据结构 研究和解决非数值数据的组织和处理 研究和解决非数值数据的组织和处理 非数值计算问题的数学模型，不再是数学方程 例子：线性表、树、图、集合 算法 + 数据结构 = 程序 算法 + 数据结构 = 程序 算法和数据结构之间的关系 软件系统的架构应当建立在数据之上 数据结构的作用范畴 数据结构的作用范畴 抽象数据对象的数学模型、明确操作 存储结构上映射数据、实现操作

20 数据结构 数据的逻辑结构 图、树、二叉树、线性表 数据的存储结构 顺序方法 链式方法 索引方法 散列方法 数据的运算 增加、修改、删除 排序、检索

21 为什么要学习数据结构 什么是数据与数据结构 什么是数据与数据结构 逻辑结构、存储结构及数据的操作 内容

22  数据：数据是信息的载体，是描述客观事物的数、 字符、以及所有能输入到计算机中，被计算机程 序识别和处理的符号的集合。  数值性数据  非数值性数据  数据对象：数据的子集。具有相同性质的数据成 员（数据元素）的集合。  整数数据对象 N = { 0,  1,  2, … }  学生数据对象 数据的概念

23 数据元素：数据中的一个 “ 个体 ” ，也称 “ 数据记录 ” 。是数据结构 中讨论的基本单位 。 数据项 : 相当于记录的 “ 域 ”, 是数据的不可分割的最小单位。是数 据结构中讨论的最小单位 。 ( 原子项、组合项 ) ( 原子项、组合项 ) 数据元素 数据项 数据的概念

24 数据结构 数据结构：一类按照一定的逻辑关系组织起来 的数据的表示、相关操作的实现 数据结构：一类按照一定的逻辑关系组织起来 的数据的表示、相关操作的实现   逻辑结构：数据元素之间的逻辑关系   存储结构：数据结构在计算机存储器中的表示方法， 也称为存储表示；   运算：结构的行为特征，作用于数据结构上的运算 常见的基本数据结构：线性表、字符串、栈、 队列、树和二叉树、图、字典

25 数据的逻辑结构 定义 : 由某一数据对象及该对象中所有数据成员之间的关系组成。 记为： 由某一数据对象及该对象中所有数据成员之间的关系组成。 记为： Data_Structure = {D, R} Data_Structure = {D, R}其中： D 是某一数据对象 D 是某一数据对象 R 是该对象中所有数据成员之间的关系的有限集合。 R 是该对象中所有数据成员之间的关系的有限集合。

26 “ 学生 ” 表格 在这类文档管理的数学模型中, 计算机处理的对象之间通常 存在着一种最简单的线性关系, 这类数学模型称为线性模型

27 UNIX 文件系统的系统结构图 / (root) bin lib user etc math ds swyintaoxie Stack.cppQueue.cpp Tree.cpp

28 课程开设关系图 —— 图型结构

29 为什么要学习数据结构 什么是数据与数据结构 逻辑结构、存储结构及数据的操作 逻辑结构、存储结构及数据的操作 内容

30 数据的逻辑结构  关系  数据的逻辑结构的讨论，一般把重点放在关系集 R 上；   根据 R 的性质刻画数据结构的特点，按照数据元 素之间的关系划分可以分成： 一对一：线性结构（ linear structure ） 一对多：树形结构 (tree structure) 多对多：图型或网状结构 (graph structure)

31  数据的存储结构 ( 物理结构 ) ： 数据的各元素及其之间的关系在计算机中的存储表示。 是逻辑结构的物理存储方式、存储映像  存储结构类型： 顺序结构 链式结构 索引结构 散列结构 数据的存储结构

32   顺序结构 用一块连续的存储区域存储数据 按照地址相邻的关系存储数据，借助于存储单元的自然顺序 来表示数据元素之间的关系 访问具有便利性 称之为紧凑存储结构 数据的存储结构 12345678

33   链式结构 利用指针，在数据元素的存储中附加一个指针字段； 借助于指针指示的关系来表示数据元素的关系 链式存储为经常增删结点的复杂数据结构提供了解决方法 顺序查找 数据的存储结构

34   索引结构   顺序存储的一种推广，使用整数编码来访问数据结点位置   构造一个将整数域 Z 映射到存储地址域 D 的函数，把数据元素 的整数索引值映射到结点的存储地址，一般用附加的存储空 间构成一个索引表 数据的存储结构 33376779 673733

35   散列方法 利用散列函数的机制进行存储位置的计算 要适当地选取函数，解决地址冲突的问题 数据的存储结构

36  数据运算： 定义于逻辑结构、实现于存储结构 对数据的检索、插入、删除、更新、排序等操 作 数据的运算

37  它研究了计算机需要处理的数据对象和对象 之间的关系。  它刻画了应用中涉及到的数据的逻辑组织。  它描述了数据在计算机中如何存储、传送、 转换。 小结 为什么要学习数据结构 ?

38 从传统的观点来看 数据的逻辑结构  线性结构  非线性结构 主要讨论哪几种数据结构 ？

39 ABCDEF A B DEG C A B C D E 线性结构 非线性结构

40 数据的物理结构  顺序结构  链表结构  散列结构  索引结构

41 在数据结构上的操作  查找  排序  插入  删除  修改