数据结构

出版时间：2001-07  出版社：中国水利水电出版社  作者：李根强 编  页数：243  

前言

　　数据结构是计算机专业及相关专业的一门重要专业基础课，也是一门必修的核心课程。在计算机科学的各领域中，都要使用到各种不同的数据结构，如编译系统中要使用栈、散列表、语法树等；操作系统中要使用队列、存储管理表、目录树等；数据库系统中要使用线性表、链表、索引树等；人工智能中要使用广义表、检索树、有向图等；同样在面向对象的程序设计、计算机图形学、软件工程、多媒体技术、计算机辅助设计等领域，都会用到各种不同的数据结构。因此，学好数据结构，对从事计算机技术及相关领域的工作人员来说，是非常重要的，它可以使你掌握各种常用的数据结构及算法实现，以及每一种算法的时间复杂度分析和空间复杂度分析，知道在哪种情况下，使用哪种数据结构最方便，为以后开发大型程序而使用各种不同的数据结构打下基础。　　数据结构的主要任务是讨论现实世界中的各种数据（数字、字符、字符串、声音、图形、图像等）的逻辑结构、在计算机中的各种存储结构（存储表示）以及对各种非数值运算的算法实现和分析各种算法的好坏及其在哪些地方比较适用。通过数据结构课程的学习，使学生具备用所学的数据结构来解决实际问题及评价算法优劣的能力，为以后学习后续专业课程及走上工作岗位从事计算机大型软件开发铺路。　　本书内容共分9章，第1章介绍了数据结构与算法等一些基本术语，并对算法描述及算法分析作了简单说明，介绍了衡量算法优劣的主要因素：时间复杂度和空间复杂度的求法；第2章到第4章，介绍了线性结构的逻辑特征，一些常用算法的实现及基本应用；第5章到第7章，介绍了非线性结构的逻辑特征，存储表示及一些常用算法实现及基本应用；第8章到第9章，介绍了在计算机中使用非常广泛的两种运算：查找和排序，对一些常用的查找、排序方法进行了详细说明，并给出了实现的算法及时间复杂度和空间复杂度分析。各章内容相对独立，可便于不同院校不同专业按需要组织教学。全书侧重于数据结构的应用，力求讲授内容与具体的计算机应用实例相结合，以便于学生加深对各章内容的理解和掌握。　　本书的最大特点是采用面向对象的程序设计语言（C++语言）作为算法的描述语言，所有算法都已经上机调试通过。但是，由于篇幅所限，大部分算法都是以单独的函数形式给出，若读者要运行这些算法，还必须给出一些变量的说明及主函数来调用所给的函数。因此，本书中的算法描述比原来数据结构教材中用类PASCAL语言或类C语言描述算法更直观，学生更容易理解和接受。作者在十几年的数据结构课程教学中，对数据结构中的各种算法进行了认真的研究和分析，在这方面积累了丰富的经验，因此，本书中所选的例题和习题都具有一定的针对性，都是针对特定的数据结构来进行描述的，方便学生理解和接受，并能为复杂的数据结构算法描述架桥铺路。

内容概要

　　《数据结构（C++描述）》从软件开发的实际需要出发，按照面向对象的程序设计思想，详细地介绍了线性表，栈和队列，串，多维数组和广义表，树，图等特殊的数据结构及在计算机中的表示及算法的实现，每个算法都用C++语言进行描述，并全部上机通过。最后两章，介绍了计算机中常用的两种运算：查找和排序，详细介绍了不同的查找、排序运算及各种方法的效率分析。　　《数据结构（C++描述）》中所有算法都在VC++ 6.0环境下运行通过。为了方便教学，《数据结构（C++描述）》免费为授课教师提供用PowerPoint制作的电子教案，教师在使用时可以根据需要进行必要的修改。　　《数据结构（C++描述）》既可以作为高职高专教材，也可以作为从事计算机软件开发人员和自学人员的参考书。

书籍目录

第1章 结论
1.1 什么是数据结构
1.1.1 数据结构示例
1.1.2 基本术语
1.1.3 数据结构
1.2 算法的描述
1.2.1 基本概念
1.2.2 算法描述
1.3 算法分析
1.3.1 时间复杂度
1.3.2 空间复杂度
1.4 小结
1.5 习题
第2章 线性表
2.1 线性表的定义及其运算
2.1.1 线性表的定义
2.1.2 线性表的运算
2.1.3 线性表的抽象数据类型描述
2.2 线性表的顺序存储结构
2.2.1 顺序表结构
2.2.2 顺序表运算
*2.2.3 顺序表存储空间的动态分配
2.3 线性表的链式存储结构
2.3.1 单链表结构
2.3.2 单链表运算
2.3.3 循环链表结构
2.3.4 双向链表结构
2.4 顺序表与链表比较
2.5 算法应用举例
2.6 小结
2.7 习题
第3章 栈和队列
3.1 栈
3.1.1 栈的定义
3.1.2 栈的运算
3.1.3 栈的抽象数据类型描述
3.1.4 顺序栈
3.1.5 链栈
3.1.6 栈的应用
3.2 队列
3.2.1 队列的定义
3.2.2 队列的基本运算
3.2.3 队列的抽象数据类型描述
3.2.4 循环队列
3.2.5 链队列
3.2.6 队列的应用
3.3 小结
3.4 习题
第4章 串
4.1 串的定义及运算
4.1.1 基本概念
4.1.2 串的运算
4.1.3 串的抽象数据类型描述
4.2 串的存储结构
4.2.1 顺序存储
4.2.2 链式存储
4.2.3 索引存储
4.3 串的运算的实现
4.3.1 串插入
4.3.2 串删除
4.3.3 子串定位
4.4 串操作应用举例
*4.4.1 文本编辑
*4.4.2 建立词索引表
4.5 小结
4.6 习题
第5章 多维数组和广义表
5.1 多维数组
5.1.1 多维数组的概念
5.1.2 多维数组在计算机内的存放
5.2 多维数组的存储结构
5.2.1 行优先顺序
5.2.2 列优先顺序
5.3 特殊矩阵及其压缩存储
5.3.1 特殊矩阵
5.3.2 压缩存储
5.4 稀疏矩阵
5.4.1 稀疏矩阵的存储
5.4.2 稀疏矩阵的运算
5.5 广义表
5.5.1 基本概念
5.5.2 存储结构
5.5.3 基本运算
5.6 小结
5.7 习题
第6章 树
6.1 树的基本概念
6.1.1 树的定义
6.1.2 基本术语
6.1.3 树的表示
6.1.4 树的性质
6.2 二叉树
6.2.1 二又树的定义
6.2.2 二叉树的性质
6.2.3 二叉树的存储结构
6.2.4 二叉树的抽象数据类型
6.3 遍历二叉树
6.3.1 前根场历
6.3.2 中根遍历
6.3.3 后根遍历
6.3.4 遍历算法应用举例
6.4 线索二叉树
6.4.1 线索的概念
6.4.2 线索的描述
6.4.3 线索的算法实现
6.4.4 线索二叉树上的运算
6.5 树和森林
6.5.1 树的存储结构
6.5.2 树、森林和二叉树的转换
6.5.3 树和森林的遍历
6.6 哈夫曼树
6.6.1 基本术语
6.6.2 哈夫曼树构造
6.6.3 哈夫曼树的应用
6.7 小结
6.8 习题
第7章 图
7.1 图的基本概念
7.1.1 图的定义
7.1.2 图的基本术语
7.2 图的存储结构
7.2.1 邻接矩阵
7.2.2 邻接表
7.2.3 邻接多重表
7.3 图的遍历
7.3.1 深度优先搜索遍历
7.3.2 广度优先搜索遍历
7.4 生成树和最小生成树
7.4.1 基本概念
7.4.2 普里姆（prim）算法
7.4.3 克鲁斯卡尔（kruskal）算法
7.5 最短路径
7.5.1 单源点最短路径
7.5.2 所有顶点对之间的最短路径
7.6 拓扑排序
7.6.1 实现规则
7.6.2 算法描述
7.7 小结
7.8 习题
第8章 查找
8.1 查找的基本概念
8.2 线性表的查找
8.2.1 顺序查找
8.2.2 二分查找
*8.2.3 索引查找
*8.2.4 分块查找
8.3 树表查找
8.3.1 二叉排序树查找
*8.3.2 平衡二叉树查找
8.4 散列查找
8.4.1 基本概念
8.4.2 散列函数的构造
8.4.3 解决冲突的方法
8.4.4 散列查找算法实现
8.4.5 散列查找的性能分析
8.5 小结
8.6 习题
第9章 排序
9.1 基本概念
9.1.1 排序介绍
9.1.2 基本概念
9.2 插入排序
9.2.1 直接插入排序
9.2.2 二分插入排序
9.2.3 希尔排序
9.3 交换排序
9.3.1 冒泡排序
9.3.2 快速排序
9.4 选择排序
9.4.1 直接选择排序
*9.4.2 树形选择排序
9.4.3 堆排序
9.5 归并排序
9.5.1 二路归并排序
*9.5.2 多路归并排序
9.6 分配排序
*9.6.1 多关键字排序
*9.6.2 链式基数排序
9.7 各种内排序方法的比较和选择
9.7.1 各种内排序方法的比较
9.7.2 各种内排序方法的选择
9.8 小结
9.9 习题

章节摘录

　　在前面几章中，我们介绍了线性表、栈和队列、串等线性结构及多维数组、广义表、树和图等非线性结构，讨论了它们的逻辑结构、存储结构及运算，并且在运算中，曾经讨论过一些简单的查找运算。但由于查找运算的使用频率相当高，几乎在任何一个计算机系统中都会涉及到，所以当问题的规模相当大时，查找算法的效率就显得十分重要。因此，本章将着重讨论各种查找方法，并通过对它们的效率分析来比较各种查找方法的优劣。　　查找，也称为检索。在我们日常生活中，随处可见查找的实例。如查找某人的地址、电话号码；查某单位45岁以上职工等，都属于查找范畴。本书中，我们规定查找是按关键字进行的，所谓关键字（key）是数据元素（或记录）中某个数据项的值，用它可以标识（或识别）一个数据元素。例如，描述一个考生的信息，可以包含：考号、姓名、性别、年龄、家庭住址、电话号码、成绩等关键字。但有些关键字不能惟一标识一个数据元素，而有的关键字可以惟一标识一个数据元素。如刚才的考生信息中，姓名不能惟一标识一个数据元素（因有同名同姓的人），而考号可以惟一标识一个数据元素（每个考生考号是惟一的，不能相同）。我们将能惟一标识一个数据元素的关键字称为主关键字，而其他关键字称为辅助关键字或从关键字。

编辑推荐

　　本书从软件开发的实际需要出发，按照面向对象的程序设计思想，详细地介绍了线性表，栈和队列，串，多维数组和广义表，树，图等特殊的数据结构及在计算机中的表示及算法的实现，每个算法都用C++语言进行描述，并全部上机通过。最后两章，介绍了计算机中常用的两种运算：查找和排序，详细介绍了不同的查找、排序运算及各种方法的效率分析。　　本书中所有算法都在VC++ 6.0环境下运行通过。为了方便教学，本书免费为授课教师提供用PowerPoint制作的电子教案，教师在使用时可以根据需要进行必要的修改。　　本书既可以作为高职高专教材，也可以作为从事计算机软件开发人员和自学人员的参考书。

用户评论 (总计3条)

•   思想讲解比我们的课本还好，高职教材？总之很好，至于代码…………不敢恭维
•   课本还可以，可以很好的了解C++
•   这次买的书的质量不错。要是每次都这样就好了！