数据结构教程

内容简介

目录

文摘

数据结构教程(第二版)

内容提要：

图书目录：

数据结构教程

编者:黄育潜 滕少华

出版社：华中科技大学出版社

页码：224 页

出版日期：1996年

ISBN：7560912850

条形码：9787560912851

版本：1版

装帧：平装

开本：16

内容简介

《数据结构教程》用精练、流畅的语言详述了数据结构的基本概念、基本思想、基本原理及实际背景。共分十章，内容包括：绪论，线性表，栈和队列，特殊链表和特殊线性表，内、外排序，树，图，检索，文件。

书中以大量的例子来突出这样一个思想：数据结构是算法设计和描述的基础与工具，并采取了“对象描述、关键一步和总体控制”的算法讲解模式等多项化解难点的创新作法，在教学中深受学生欢迎。另外，《数据结构教程》采用实用的PASCAL语言作为数据结构和算法的描述工具，这将便于读者自学，也有利于帮助读者在今后的实践中应用所学的知识。

目录

第一章 绪论

1．1 数据结构和算法

1．2 数据的逻辑结构和存储结构

1．3 算法和算法分析

第二章 线性表

2．1 线性表及其基本运算

2．1．1 线性表

2．1．2 线性表的基本运算

2．2 线性表的顺序存储实现

2．2．1 向量——线性表的顺序存储表示

2．2．2 插入、删除与查找算法

2．3 应用——多项式相加（顺序存储实现）

2．3．1 多项式的压缩表示及其顺序存储

2．3．2 多项式相加

2．4 线性表的链式存储实现

2．4．1 单链表——线性表的链式存储表示

2．4．2 单链表的插入、删除与查找

2．4．3 关于单链表实现的注记

2．5 应用——多项式相加（链式存储实现）

2．5．1 多项式的链式存储表示

2．5．2 多项式的相加

第三章 栈和队列

3．1 栈

3．1．1 栈的概念

3．1．2 栈的基本运算

3．2 栈的顺序存储实现

3．2．1 顺序栈——栈的顺序存储表示

3．2．2 基本运算的实现

3．3 栈的应用——算术表达式的求值

3．3．1 表达式求值与运算符的优先数

3．3．2 表达式的中缀表示与后缀表示

3．3．3 表达式求值的算法实现

3．4 栈的链式存储实现及其应用

3．4．1 链接栈——栈的链式存储表示

3．4．2 基本运算的实现

3．4．3 链接栈的应用——可用空间栈

3．5 队列

3．5．1 队列的概念

3．5．2 队列的基本运算

3．6 队列的实现

3．6．1 顺序队列——队列的顺序存储实现

3．6．2 循环（顺序）队列——队列的另一种顺序存储实现

3．6．3 链接队列——队列的链式存储实现

3．7 队列的应用——医院门诊部病人管理系统

3．7．1 病人管理系统及所需数据结构

3．7．2 病人管理系统的实现

第四章 特殊链表和特殊线性表

4．1 带头结点的链表

4．1．1 LWH——带头结点的链表（List With Header node）

4．1．2 LWH的基本运算

4．1．3 头结点的其它应用和设计

4．2 环形链表

4．2．1 CL——环形链表（Circular linked List）

4．2．2 CL的基本运算

4．2．3 CL的应用

4．3 双链表

4．3．1 DL——双链表（Double—Iinked List）

4．3．2 DL的基本运算

4．3．3 DL的应用——简单行编辑器的设计与实现

4．4 字符串

4．4．1 串的基本概念

4．4．2 串的基本运算

4．4．3 串的存储实现

4．5 特殊矩阵

4．5．1 对称矩阵

4．5．2 三角矩阵

4．5．3 稀疏矩阵

第五章 内排序

5．1 引言

5．2 插入排序

5．2．1 直接插入排序

5．2．2 折半插入排序

5．2．3 Shell排序

5．3 选择排序

5．3．1 直接选择排序

5．3．2 堆排序

5．4 交换排序

5．4．1 冒泡排序

5．4．2 快速排序

5．5 归并排序

5．6 分配排序

第六章 树

6．1 树的基本概念

6．2 树的存储结构

6．3 树的遍历

6．4 树的线性表示

6．5 二叉树

6．5．1 满二叉树和完全二叉树

6．5．2 树转换成相应二叉树

6．6 二叉树的遍历

6．7 二叉树的顺序存储

6．7．1 完全二叉树的顺序存储

6．7．2 按前序的存储形式

6．8 穿线二叉树

6．8．1 穿线二叉树的操作

6．8．2 穿线排序

第七章 图

7．1 图的概念

7．2 图的存储结构

7．2．1 邻接矩阵

7．2．2 邻接表

7．2．3 邻接多重表

7．3 图的遍历和图的连通分量

7．3．1 深度优先搜索法

7．3．2 广度优先搜索法

7．3．3 图的连通分量

7．4 生成树和最小生成树

7．5 最短路径

7．5．1 从一个源点到其它各顶点的最短路径

7．5．2 每一对顶点之间的最短路径

7．6 拓扑排序

第八章 检索

8．1 基本概念

8．2 线性表的检索

8．2．1 顺序检索法

8．2．2 二分检索法

8．2．3 分页块检索

8．3 二叉排序树

8．4 丰满树和平衡树

8．4．1 丰满树

8．4．2 平衡二叉排序树

8．5 最佳二叉排序树和Huffman树

8．5．1 扩充二叉树

8．5．2 最佳二叉排序树

8．5．3 Huffman树

8．6 散列表(Hash)检索

8．6．1 散列函数

8．6．2 处理冲突的方法

第九章 文件

9．1 文件的基本概念

9．2 外存储器简介

9．2．1 磁带

9．2．2 磁盘

9．2．3 分页块存储法

9．3 文件组织概述

9．3．1 文件的逻辑结构

9．3．2 文件的存储结构

9．3．3 文件上的操作

第十章 外排序

10．1 外排序概述

10．2 磁盘排序

10．2．1 多路合并

10．2．2 初始顺串的生成

10．3 磁带排序

10．3．1 平衡合并排序

10．3．2 多阶段合并排序

参考文献

……

文摘

3．7队列的应用——医院门诊部病人管理系统

前面曾说到，在日常工作和生活中，以排队方式来组织和管理对象，常能简单而有效地解决问题。计算机应用的实践也一再证明，以这种方式来组织和管理数据，也常能帮助我们找到简单且有效的解题算法。下面以医院门诊部的一个病人管理系统为例，说明队列这一数据结构的应用。

3．7．1病人管理系统及所需数据结构

为简化起见，假定医院门诊部病人管理工作大致如下进行：当一病人进入门诊室时，负责挂号的医务人员就根据观察和简短询问发给他一个从0（病危）到4（一般）变化的优先数，让他到相应优先数队列中去排队等待。当一医生空闲时，就根据优先数和等待时间，通知某候诊病人去就诊。其原则是，优先级高的（即，优先数小的）先考虑，同一优先级中，则先来的先考虑。

根据管理系统的一般组织模式，可以设想本系统将按以下步骤进行工作。

（1）系统初始化

（2）重复以下工作，直到接到退出命令

①显示系统功能菜单；

②用户打入所选择的功能号；

③执行功能号对应的程序。

（3）程序结束

就病人管理系统来说，功能菜单中至少应包括以下两功能：

①病人登记；

②确定下一就诊病人。

现在，首先来考虑该系统所需的数据结构，即组织数据的方式。容易看出，这样一个系统中的数据就是一个个病人的姓名、优先数和到达时间。倘若把病人以其到达门诊部的先后次序组织到一个队列中去，则具体的到达时间就不必要了。图3．8（a）给出了由7名病人按到达次序组成的队列。不过，这样的单队列对按就诊原则来确定下一就诊病人是很不方便的。此外，它还将导致破坏队列的操作原则（队首出队、队尾进队）。解决这一问题的一个简单方法是，将候诊病人组织成多个队列，即队列数组，使数组的第i个元素是优先数为i的队列，每一队列内部则按到达次序来组织，如，设队列数组取名为qus，则上述同一组数据，用队列数组来表示，形如图3．8（b）。这时，由于优先数已隐含在队列编号（数组下标）中，故队列中只须保留病人名就可以了。

数据结构教程(第二版)

作/译者：唐发根出版社：北京航空航天大学出版社

出版日期：2005年05月

ISBN：9787810775861 [十位:7810775863]

页数：372 重约：0.590KG

定价：￥36.00

内容提要：

《数据结构教程》(第二版)是1996年出版的第一版的修订版。修订版在保持第一版基本框架和特色的基础上,对其中的内容做了大量的增删和修改,书中所有算法采用C语言描述。

书中讨论了包括线性表、堆栈、队列、树和图在内的各种数据结构和数据文件的基本概念、逻辑结构与存储结构,以及在这些结构的基础上所实施的相关操作。全书仍分为11章。每一章在增加了大量例题解析的同时,还配有丰富的、各种类型的习题,并且提供了体现各章基本内容的上机实践题。

本书可以作为高等院校计算机专业本科学生的教材,也可以作为报考高等学校计算机专业硕士研究生入学考试的复习用书,同时还可以作为从事计算机系统软件和应用软件设计与开发人员的参考资料。

图书目录：

第1章 绪论

1.1 什么是数据结构

1.2 数据结构的发展简史及其在计算机科学中的地位

1.3 算法

1.3.1 算法及其性质

1.3.2 基本算法

1.3.3 算法的描述

1.4 算法分析

1.4.1 时间复杂度

1.4.2 空间复杂度

1.4.3 其他方面

习题

第2章 线性表

2.1 线性表的定义及其基本操作

2.1.1 线性表的定义

2.1.2 线性表的基本操作

2.2 线性表的顺序存储结构

2.2.1 顺序存储结构的构造

2.2.2 几种常见操作的实现

2.2.3 顺序存储结构小结

2.3 线性链表及其操作

2.3.1 线性链表的构造

2.3.2 线性链表的基本算法

2.4 循环链表及其操作

2.5 双向链表及其操作

2.5.1 双向链表的构造

2.5.2 双向链表的插入与删除算法

2.6 链表的应用举例

2.6.1 链式存储结构下的一元多项式相加

2.6.2 打印文本文件的最后n行

习题

第3章 数组

3.1 数组的概念

3.2 数组的存储结构

3.3 矩阵的压缩存储

3.3.1 对称矩阵的压缩存储

3.3.2 对角矩阵的压缩存储

3.4 稀疏矩阵的三元组表表示

3.4.1 稀疏矩阵的三元组表存储方法

3.4.2 稀疏矩阵的转置算法

3.4.3 稀疏矩阵的相加算法

3.4.4 稀疏矩阵的相乘算法

3.5 稀疏矩阵的链表表示

3.5.1 线性链表存储方法

3.5.2 带行指针向量的链表存储方法

3.5.3 十字链表存储方法

3.6 数组的应用举例

3.6.1 一元多项式的数组表示

3.6.2 n阶魔方

习题

第4章 堆栈和队列

4.1 堆栈的概念及其操作

4.1.1 堆栈的定义

4.1.2 堆栈的基本操作

4.2 堆栈的顺序存储结构

4.2.1 顺序堆栈的构造

4.2.2 顺序堆栈的基本算法

4.2.3 多个堆栈共享连续空间

4.3 堆栈的链式存储结构

……

第5章 广义表

第6章 串

第7章 树与二叉树

第8章 图

第9章 文件及查找

第10章 内排序

第11章 外排序

附录 上机实践题

习题答案

参考文献