数据结构(C语言版)第1章

数据结构(C语言版)计算机教学PPT,教材作者：Ellis Horowitz Sartaj Sahni Susan Anderson-Freed,机械工业出版社风格不同于清华大学严蔚敏教材,作者论证严密,算法独特,注重引导创新思维!

数据结构( 语言版) 数据结构(C语言版)2011-2012学年第 2011-2012学年第1学期 学年第1 Ellis Horowitz Sartaj Sahni Susan Anderson-Freed

机械工业出版社

授课班级： 授课班级：计算机科学技术

2012-2-19

数据结构(C语言版)计算机教学PPT,教材作者：Ellis Horowitz Sartaj Sahni Susan Anderson-Freed,机械工业出版社风格不同于清华大学严蔚敏教材,作者论证严密,算法独特,注重引导创新思维!

本书目录第 1章 ： 第 2章 ： 第 3章 ： 第 4章 ： 第 5章 ： 基本概念 数组结构 栈和队列 线性表 树 第 6章 ： 图 第7章： 排序 第8章： 散列 第9章： 堆结构 10章 第10章：查找结构

2012-2-19

数据结构(C语言版)计算机教学PPT,教材作者：Ellis Horowitz Sartaj Sahni Susan Anderson-Freed,机械工业出版社风格不同于清华大学严蔚敏教材,作者论证严密,算法独特,注重引导创新思维!

第1章 基本概念本章主题： 本章主题：数据结构的基本概念和术语 教学重点：熟悉数据结构常用术语，掌握基本概念，了解算法 教学重点：熟悉数据结构常用术语，掌握基本概念，了解算法 时间复杂度和空间复杂度的分析与评价 教学难点： 教学难点：算法性能分析 主要内容： 主要内容： 1.1 系统生命周期 1.2 1.3 1.4 1.42012-2-19

算法描述 数据抽象 算法性能分析与评价3

数据结构(C语言版)计算机教学PPT,教材作者：Ellis Horowitz Sartaj Sahni Susan Anderson-Freed,机械工业出版社风格不同于清华大学严蔚敏教材,作者论证严密,算法独特,注重引导创新思维!

教学引入： 教学引入：数据结构概念补充数据结构是一门研究非数值计算 数据结构是一门研究非数值计算的程序设计问题中计算机的操作 非数值计算的程序设计问题中计算机的操作 对象以及它们之间的关系和操作的学科.主要有三个方面的内容： 对象以及它们之间的关系和操作的学科.主要有三个方面的内容： 数据的逻辑结构、数据的存储结构和对数据的算法。 数据的逻辑结构、数据的存储结构和对数据的算法。 逻辑结构：数据间的逻辑关系，有集合、线性表、树、图等四种 逻辑关系， 集合、线性表、 逻辑结构：数据间的逻辑关系 结构。 结构。 物理结构：数据在计算机内部的存储安排，是数据结构在计算机 存储安排， 物理结构：数据在计算机内部的存储安排 中的实现方法。主要有顺序、链接、散列、索引等四种基本存储结构， 中的实现方法。主要有顺序 链接、散列、索引等四种基本存储结构， 顺序、 等四种基本存储结构 并可以根据需要组合成其它更复杂的结构。 并可以根据需要组合成其它更复杂的结构。 算法：数据进行处理的方法。 算法：数据进行处理的方法。2012-2-19 4

数据结构(C语言版)计算机教学PPT,教材作者：Ellis Horowitz Sartaj Sahni Susan Anderson-Freed,机械工业出版社风格不同于清华大学严蔚敏教材,作者论证严密,算法独特,注重引导创新思维!

返回

数据结构示例:在表中会按登录号形成一种次序关系， 数据结构示例:在表中会按登录号形成一种次序关系，即整个二维表就是图书数据的一个线性序列。这种关系被称为线性结构 就是图书数据的一个线性序列。这种关系被称为线性结构。 线性结构。

表 1-1 图书目录表登录号 1 2 3 4 5 6 7 …2012-2-19

书号

书名

作者

出版社

定价 22 17.3 29 25

ISBN 7-302-02368-9 / TP. 1185 数据结构 ISBN 7-302-00860-4 / TP. 312 C 程序设计 ISBN 7-5053-9279-4 / TP. 311 数据结构 ISBN 7-5053-8168-7 / TP. 4757 计算机系统原理 ISBN 7-5609-2351-8

/ TP. 316 操作系统原理 ISBN 7-304-01404-0 / TP. 68

严蔚敏 清华大学 谭浩强 清华大学 徐孝凯 电子工业 张基温 电子工业

庞丽萍 华中科技大学 22.8 23.3 20 …

数据库基础与应用 王 利 中央电大

ISBN 7-5084-1648-1 / TP. 706 网页制作实例教程 齐建玲 中国水利水电 …

…

…

…

返回5

数据结构(C语言版)计算机教学PPT,教材作者：Ellis Horowitz Sartaj Sahni Susan Anderson-Freed,机械工业出版社风格不同于清华大学严蔚敏教材,作者论证严密,算法独特,注重引导创新思维!

【例1-2】磁盘目录结构和文件管理系统root bin math ds sw lib user zhao jiang shao li etc描述磁盘目录和文件结构时， 描述磁盘目录和文件结构时， 假设每个磁盘包括一个根目录 root)和若干个一级子目录， (root)和若干个一级子目录，每 个一级子目录中又包含若干个二级 子目录… 子目录…. 这种关系很像自然界中的树， 这种关系很像自然界中的树， 所以称为目录树。如左图所示。 所以称为目录树。如左图所示。

queue stack tree graph

在这种结构中，目录和目录以及目录和文件之间呈现出一对多的非 在这种结构中， 线性关系。即根root有多个下属(也称为后代),每一后代又有属于自己 有多个下属( ),每一后代又有属于自己 线性关系。即根root有多个下属 也称为后代), 的后代；而任一个子目录或文件都只有一个唯一的上级(也称为双亲)。 的后代；而任一个子目录或文件都只有一个唯一的上级(也称为双亲)。 称这种数学模型为树型数据结构 树型数据结构。 称这种数学模型为树型数据结构。2012-2-19 6

数据结构(C语言版)计算机教学PPT,教材作者：Ellis Horowitz Sartaj Sahni Susan Anderson-Freed,机械工业出版社风格不同于清华大学严蔚敏教材,作者论证严密,算法独特,注重引导创新思维!

【例1-3】教学计划编排问题课 编 程 号 C1 C2 C3 C4 C5 C6 C7 C8 C9 课 名称 程 计 算机 论 导 数 据结 构 汇 编语 言 C 程序 计 设 计 算机 形 图 学 接 口技 术 数 据库 理 原 编 译原 理 操 作系 统 先 课 修 程 无 C1, C4 C1 C1 C2, C3, C4 C3 C2, C9 C4 C2 C8 C7 C1 C1 C2 C4 C9 C3 C6 C5

一个教学计划中包含许多课程。在课程之间， 一个教学计划中包含许多课程。在课程之间，有些必须按规定的 先后次序排课， C6课程必须先学C3课 课程必须先学C3 C3课程必须先学C1课 课程必须先学C1 先后次序排课，如：学C6课程必须先学C3课，学C3课程必须先学C1课。 这些课程之间存在先修和后续的关系。在这种结构中， 这些课程之间存在先修和后续的关系。在这种结构中，表示课程的数据 之间呈现多对多的非线性关系，称这类数学模型为图形结构 多对多的非线性关系 图形结构。 之间呈现多对多的非线性关系，称这类数学模型为图形结构。

2012-2-19

数据结构(C语言版)计算机教学PPT,教材作者：Ellis Horowitz Sartaj Sahni Susan Anderson-Freed,机械工业出版社风格不同于清华大学严蔚敏教材,作者论证严密,算法独特,注重引导创新思维!

四类数据基本结构的示意图： 四类数据基本结构的示意图：

(a)集合结构 a)集合结构

(b)线性结构 b)线性结构

(c)树型结构 c)树型结构

(d)图形结构 d)图形结构

由以上例子可见，描述这类非数值计算问题的数学模型 由以上例子可见， 和方法不再是数学方

程，而是诸如线性表、 和方法不再是数学方程，而是诸如线性表、树 …… 此处隐藏：3726字，全部文档内容请下载后查看。喜欢就下载吧 ……