正版新书]数据结构邵斌9787302493327

章概论1
1.1什么是数据结构1
1.1.1数据和数据元素1
1.1.2数据对象与数据类型2
1.1.3数据结构2
1.2为什么要学习数据结构5
1.2.1学习数据结构的重要5
1.2.2数据结构的应用举例5
1.3算法和算法分析7
1.3.1什么是算法7
1.3.2算法的描述和设计7
1.3.3算法分析8
本章小结10
习题10
第2章线表12
2.1线表的基本概念12
2.1.1线表的定义12
2.1.2线表的基本操作13
2.2线表的顺序存储13
2.2.1顺序表13
2.2.2顺序表的基本操作14
2..顺序存储方式举例17
.线表的链式存储20
..1单链表的基本概念20
..2单链表的基本操作22
..链式存储举例25
..4循环链表28
..5双向链表30
..双向循环链表33..静态链表34
2.4线表顺序存储与链式存储的比较35
2.5线表的应用36
2.5.1约瑟夫问题36
2.5.2多项式加法38
2.5.3电文加密40
本章小结42
习题43
第3章栈和队列45
3.1栈45
3.1.1栈的定义与基本操作45
3.1.2顺序栈的存储结构和操作的实现47
3.1.3链栈的存储结构和操作的实现50
3.2栈的应用52
3.2.1数制转换52
3.2.2括号匹配问题54
3..子程序的调用55
3.2.4利用一个顺序栈逆置一个带头节点的单链表56
3.2.5后缀表达式59
3.3队列61
3.3.1队列的定义与基本操作61
3.3.2链队列的存储结构和操作的实现62
3.3.3顺序队列的存储结构和操作的实现64
3.4队列的应用68
3.4.1打印杨辉三角形68
3.4.2迷宫问题： 寻找一条从迷宫入口到出口的短路径71
3.5递归74
3.5.1递归的定义与实现74
3.5.2递归消除77
本章小结81
习题81
第4章串85
4.1串的定义和基本操作85
4.1.1串的定义85
4.1.2串的基本操作87
4.2串的表示和实现88
4.2.1串的定长顺序存储88
4.2.2串的堆存储结构91
4..串的块链存储结构93
4.3串的模式匹配算法97
4.3.1基本的模式匹配算法97
4.3.2模式匹配的改进算法——KMP算法100
本章小结102
习题102
第5章多维数组和广义表104
5.1多维数组104
5.1.1多维数组的定义104
5.1.2数组的存储结构105
5.2矩阵的压缩存储 106
5.2.1特殊矩阵106
5.2.2稀疏矩阵108
5.3广义表 114
本章小结116
习题117
第6章树和二叉树118
6.1树的概念与基本操作118
6.1.1树的定义118
6.1.2树的一些基本概念119
6.1.3树的基本操作120
6.2二叉树120
6.2.1二叉树的定义和基本操作120
6.2.2二叉树的质121
6..二叉树的存储结构1
6.3二叉树的遍历与线索化124
6.3.1二叉树的遍历124
6.3.2线索二叉树127
6.3.3基于遍历的应用与线索二叉树的应用129
6.3.4标识符树134
6.4树和森林134
6.4.1树的存储结构134
6.4.2树、森林和二叉树之间的转换137
6.4.3树和森林的遍历140
6.5哈夫曼树及其应用142
6.5.1与哈夫曼树相关的基本概念142
6.5.2哈夫曼树的应用144
6.5.3哈夫曼编码算法的实现146
*6.6树的147
本章小结150
习题151
第7章图154
7.1图的基本概念154
7.1.1图的定义154
7.1.2图的相关术语155
7.2图的存储结构157
7.2.1邻接矩阵表示法157
7.2.2邻接表表示法159
7.3图的遍历163
7.3.1深度优先搜索法163
7.3.2广度优先搜索法165
7.3.3非连通图的遍历167
7.4生成树与生成树167
7.4.1生成树的概念167
7.4.2构造生成树的普里姆(Prim)算法168
7.4.3构造生成树的克鲁斯卡尔(Kruskal)算法171
7.5短路径173
7.5.1从某个源点到其余各顶点的短路径174
7.5.2每一对顶点之间的短路径178
7.6拓扑排序181
7.7关键路径184
本章小结190
习题190
第8章查找195
8.1查找的基本概念195
8.1.1查找表和查找195
8.1.2查找表的数据结构表示196
8.1.3平均查找长度ASL196
8.2线表的查找196
8.2.1顺序查找 196
8.2.2二分查找198
8..分块查找201
8.3树表的查找203
8.3.1二叉排序树203
*8.3.2平衡二叉树208
*8.3.3B-树212
8.4散列表的查找221
8.4.1散列表的概念221
8.4.2散列函数的构造方法222
8.4.3处理的方法 2
8.4.4散列表上的运算 227
本章小结0
习题0
第9章排序2
9.1排序的基本概念2
9.1.1关键字与排序2
9.1.2排序的稳定
9.1.3排序方法的分类
9.1.4排序算法能评
9.1.5不同存储方式的排序过程
9.2插入排序4
9.2.1直接插入排序4
9.2.2希尔排序
9.3交换排序
9.3.1冒泡排序
9.3.2快速排序(霍尔排序)240
9.4选择排序244
9.4.1直接选择排序244
9.4.2堆排序245
9.5归并排序250
9.6基数排序253
9.6.1桶排序253
9.6.2多关键字的排序253
9.6.3链式基数排序254
9.7内部排序算法比较257
9.8外部排序简介259
本章小结259
习题260
参考文献263

章概论数据结构章概论本章要点什么是数据结构为什么要学习数据结构数据对象和数据类型算法和算法分析本章学习目标了解数据结构的基本概念，理解常用术语。
掌握数据元素间的4类结构关系。
掌握算法的定义及特，掌握算法设计的要求。
掌握分析算法的时间复杂度和空间复杂度的方法。
1.1什么是数据结构计算机科学是一门研究信息表示和处理的科学。信息的表示和组织直接关系到处理信息程序的效率。由于许多系统程序和应用程序的规模很大，结构又相当复杂，因此需要对程序设计方法进行系统的研究，这不仅涉及研究程序的结构和算法，同时也涉及程序加工对象(数据)的结构，因为数据的结构直接影响算法的选择和效率。
1.1.1数据和数据元素数据(Data)是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储和加工处理。可以说，数据是计算机程序加工的“原料”。例如，一个求解代数方程的程序所处理的对象是整数、实数或复数，一个编译程序或文本编辑程序所处理的对象是字符串。随着计算机科学和技术的发展，计算机应用领域的扩大，数据的含义也随之越来越广。目前，图像、声音、视频等都可以通过编码而由计算机处理，因此它们也属于数据的范畴。
数据元素(DataElement)是数据中具有独立意义的个体，是数据的基本单位，通常在计算机程序中作为一个整体进行考虑和处理。例如，表中的学生信息、通讯录中的个人或组织的通信信息等，数据元素也称为元素、节点或记录。有时，一个数据元素可以由若干个数据项(也称字段、域)组成，数据项是数据不可分割的单位。[1][1]1.1.2数据对象与数据类型在数据结构中往往涉及数据类型与数据对象的概念。
数据对象(DataObject)是质同的数据元素的集合，它是数据的一个子集。例如，整数数据对象是集合N=0，±1，±，±，…；大写字母字符数据对象是集合C='A'，'B'，…，'Z'。需要注意的是，计算机中的整数数据对象集合N1应该是上述集合N的一个子集，N1=0，±1，±2，…，±maxint，其中maxint是依赖于所使用的计算机和语言的整数。
数据类型(DataType)是计算机程序中的数据对象以及定义在这个数据对象集合上的一组操作的总称。例如，C语言中的整数类型是区间\\[-maxint，+maxint\\]上的整数，在这个集合上可以进行加、减、乘、整除、求余等操作。
数据类型可以分为原子数据类型和结构数据类型，原子数据类型是由计算机语言所提供的，如C语言中的整型、实型、字符型；结构数据类型是利用计算机语言提供的一种描述数据元素之间逻辑关系的机制，由用户自己定义而成，如C语言中的数组类型、结构体类型等。
1.1.3数据结构数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。比如需要描述数据对象元素，并使这些运算能合法地用于数据对象的各元素上。
数据结构(DataStructure)是指数据对象以及该数据对象集合中的数据元素之间的相互关系(即数据元素的组织形式)。数据结构的研究范围主要包括研究数据的逻辑结构和物理结构(数据结构在计算机中的表示)，而且对每种结构定义相适应的运算，并使用某种高级程序设计语言给出各种运算的算法，分析算法的效率，同时还研究各种数据结构在计算机科学和软件工程中的某些应用，讨论数据分类、检索等方面的技术。