数据结构 (2010 年度畅销榜NO.11126 )

本书系统介绍了最常用的数据结构，包括线性表、栈、队列、数组、矩阵的压缩存储、树与二叉树、图以及查找和排序的算法等。阐述各种数据结构的逻辑关系，分析讨论各种数据结构在计算机内的存储表示，以及在这些数据结构下的算法实现，并对各种算法的时间和空间性能作简要分析。
本书既注重原理又注重实践，对基本的算法均给出相应的C语言程序的描述，并加以较详细的注释。全书配有大量的图表，每章后都附有习题，内容丰富，概念讲解清楚，逻辑性强。在本书的最后给出实验内容的附录。
本书可作为高等院校计算机相关专业的教材，亦适合于计算机爱好者自学，还可供广大从事计算机应用和开发的技术人员参考。

第1章数据结构概论
1.1数据结构的概念
1.1.1什么是数据结构
1.1.2基本概念和术语
1.1.3数据结构课程的内容和任务
1.2数据类型、抽象数据类型和参数传递
1.2.1数据类型
1.2.2抽象数据类型
1.2.3参数传递
1.3算法和算法分析
1.3.1算法特性
1.3.2算法描述
1.3.3算法性能分析与度量
1.4习题
第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.3.3循环链表
2.3.4双向链表
2.3.5单链表应用举例
2.4顺序表和链表的比较
2.5习题
第3章栈
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.3.4编译错误处理
3.3.5迷宫问题
3.4习题
第4章队列
4.1队列的定义及基本运算
4.1.1队列的定义
4.1.2队列的基本运算
4.2队列的存储结构及运算实现
4.2.1顺序队列
4.2.2队列的链式存储结构
4.3队列应用举例
4.4习题
第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.5串的模式匹配
5.5.1简单的模式匹配算法
5.5.2改进后的模式匹配算法
5.6串操作应用举例
5.7习题
第6章数组、特殊矩阵和广义表
6.1数组的逻辑结构及存储结构
6.1.1数组的定义及逻辑结构
6.1.2数组的内存映像
6.2矩阵的压缩存储
6.2.1对称矩阵的压缩存储
6.2.2三角矩阵
6.2.3带状矩阵
6.3稀疏矩阵
6.3.1稀疏矩阵的转置
6.3.2稀疏矩阵的乘积
6.4广义表
6.4.1广义表的概念和特性
6.4.2广义表的存储结构
6.4.3广义表的基本运算和实现
6.5习题
第7章树和二叉树
7.1树的定义及表示
7.1.1树的定义及相关术语
7.1.2树的表示
7.2叉树
7.2.1二叉树的定义
7.2.2二叉树的性质
7.2.3叉树的存储结构
7.2.4二叉树的基本操作及运算实现
7.3二叉树的遍历
7.3.1二叉树的遍历方法及递归实现
7.3.2由遍历序列恢复二叉树
7.4线索二叉树
7.4.1线索二叉树的定义及结构
7.4.2线索二叉树的基本运算
7.5树和森林
7.5.1树的存储结构
7.5.2叉树与树和森林的相互转换
7.5.3树和森林的遍历
7.5.4树的应用
7.6哈夫曼树及应用
7.6.1最优二叉树(哈夫曼树)
7.6.2哈夫曼编码
7.7习题
第8章图
8.1图的基本概念和基本术语
8.1.1图的基本定义
8.1.2图的基本与术语
8.1.3图的基本操作
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构造最小生成树的Prim算法.
8.4.5构造最小生成树的Kmskal算法
8.5最短路径
8.5.1从一个源点到其他各顶点的最短路径
8.5.2每一对顶点之间的最短路径
8.6有向无环图及其应用
8.6.1有向无环图的定义
8.6.2AOV网与拓扑排序
8.6.3AOE网与关键路径
8.7习题
第9章查找
9.1基本概念
9.2静态查找表
9.2.1顺序表的查找
9.2.2有序表的查找
9.2.3索引顺序表的查找
9.3动态查找表
9.3.1二叉排序树
9.3.2平衡二叉树
9.3.3B-树和B+树
9.4哈希表查找(杂凑法)
9.4.1什么是哈希表
9.4.2哈希函数的构造方法
9.4.3处理冲突的方法
9.4.4哈希表的查找及其分析
9.5习题
第10章排序
10.1概述
10.2插入排序
10.2.1直接插入排序
10.2.2折半插入排序
10.2.3希尔排序(又称缩小增量排序)
10.3交换排序
10.3.1冒泡排序
10.3.2快速排序
10.4选择排序
10.4.1简单选择排序
10.4.2树形选择排序
10.4.3堆排序
10.5归并排序
10.6基数排序
10.6.1多关键字的排序
10.6.2链式基数排序
10.7外部排序
10.8习题
附录实验内容

随着社会经济的高速发展，我国的高等教育已进入从精英教育走向大众化教育的发展阶段。高职高专教育近年来虽然得到了飞速的发展，但还仍处于探索阶段，教材改革已成为教育改革的重要方面。 “数据结构”是计算机程序设计的重要理论基础，是计算机及相关专业的一门专业基础课，计算机的系统软件和应用软件都要用到各种不同的数据结构，因此学好“数据结构”对于学习计算机专业的其他课程，如操作系统、数据库管理系统、软件工程等都是十分有益的。本书在编写过程中充分考虑到高职高专学生的特点，本着注重基础、易于实践、通俗易懂的原则，旨在为高校教改教学提供实践教材。该书的编写符合现代教育技术和教学规律，以培养实际开发和应用能力为主要教学目的，同时也可供从事计算机应用等工作的技术人员参考。 C语言以其灵活的编程方式，强大的指针处理功能，现已成为描述数据结构的最佳语言之一。考虑到计算机专业的学生都先学过C语言，本书完全用C语言描述，读者可根据具体情况轻松地升级到C++或Visual C++。考虑到本书面向的读者主要是专科生， “数据结构”又是较难学习的一门课程，所以在编写教材时，总结了笔者多年来在教学上的实践和体会，并参考了国内外较新的有关文献编写而成，所涉及到的数据结构都有较完整的数据类型定义，算法结构完整，可上机调试实现。 全书包含10章内容和1个附录：第1章介绍数据结构的主要内容、基本概念、算法的评价标准和评价方法。第2章至第6章介绍几种常用的线性结构，包括线性表、栈、队列、串以及数组、特殊矩阵和广义表。第7章介绍具有广泛应用价值的树形结构——树和二叉树及其重要应用。第8章介绍复杂的数据结构——图及其应用。第9章和第10章分别介绍数据处理中广泛应用的查找和排序技术。每一种数据结构都有较完整的数据类型定义，并详细地讨论各种数据结构在计算机内的存储表示及算法的实现，并对C语言描述的算法作相应的注释和简要的分析。本书最后的附录给出一些较典型的实验，使读者通过实验来加深对数据结构这门课程的理解和掌握。 本书可作为高等院校计算机相关专业的教材，亦适合于计算机爱好者自学，还可供广大从事计算机应用和开发的技术人员参考。 本书的第1、2、3、7章和附录部分由王钢编写，第4、5、6章由杨德芳编写，第8、9、10章由李国编写，最后由王钢和徐红统改定稿。 本书在编写过程中，参考了大量的文献资料和国内外较新的优秀教材，并得到许多老师和专家的大力支持，在此表示诚挚的谢意。 由于时间仓促及作者的水平有限，书中缺点和错误在所难免，恳请广大读者批评指正。