数据结构算法解析 殷人昆 编 大中专 文轩网

第1章数据结构绪论1
1.1简单的编程问题1
1.2简单的算法设计4
1.2.1枚举法编程4
1.2.2递推法编程8
1.2.3递归法编程11
1.2.4迭代法编程13
1.2.5动态规划法编程16
1.3简单的算法分析17
1.3.1语句的执行频度17
1.3.2时间复杂度度量18
1.3.3有关算法分析的选择题20
第2章线性表26
2.1线性表的概念26
2.1.1线性表的定义26
2.1.2线性表的应用26
2.2顺序表28
2.2.1顺序表的结构28
2.2.2顺序表的基本作28
2.2.3顺序表的相关算法31
2.3链表42
2.3.1单链表的结构42
2.3.2单链表的基本运算42
2.3.3单链表的相关算法50
2.4循环单链表80
2.4.1循环单链表的定义80
2.4.2循环单链表的基本运算81
2.4.3循环单链表的相关算法86
2.5双向链表90
2.5.1双向链表的定义与结构90
2.5.2双向链表的基本运算90
2.5.3双向链表的相关算法93
2.5.4异或双向链表99
2.6静态链表105
2.6.1静态链表的结构定义105
2.6.2静态链表的基本运算105
2.7线性表的应用实例109
2.7.1约瑟夫问题求解109
2.7.2用位向量表示集合111
2.7.3用有序链表表示集合115
2.7.4多项式的链表存储表示124
2.7.5大整数运算136
第3章栈和队列146
3.1栈146
3.1.1栈的概念146
3.1.2顺序栈148
3.1.3链式栈160
3.2队列165
3.2.1队列的定义及基本运算165
3.2.2顺序队列166
3.2.3链式队列177
3.2.4双端队列182
3.2.5优先队列188
3.3栈和队列的应用191
3.3.1栈在数制转换和括号配对中的应用191
3.3.2栈在表达式计算中的应用193
3.3.3栈和队列的其他应用199
3.3.4优先队列的应用209
3.4栈与递归214
3.4.1递归的概念214
3.4.2分治法与递归215
3.4.3减治法与递归217
3.4.4回溯法与递归227
3.4.5贪心法234
3.4.6动态规划法235
第4章多维数组、字符串与广义表240
4.1多维数组240
4.1.1一维数组240
4.1.2二维数组263
4.2特殊矩阵与稀疏矩阵277
4.2.1特殊矩阵与稀疏矩阵的概念277
4.2.2特殊矩阵相关的算法281
4.2.3稀疏矩阵相关的算法287
4.3字符串301
4.3.1字符串的概念301
4.3.2顺序串相关的算法304
4.3.3堆分配串相关的算法308
4.3.4块链存储字符串相关的算法323
4.3.5模式匹配算法327
4.4广义表333
4.4.1广义表的概念333
4.4.2头尾表示广义表相关的算法335
4.4.3层次表示广义表相关的算法342
第5章树与二树348
5.1树的基本概念348
5.1.1树的概念348
5.1.2树的双亲存储表示349
5.1.3树的子女链表存储表示353
5.1.4树的子女-兄弟链表存储表示361
5.1.5树的标准链表表示367
5.1.6树的广义表存储表示367
5.2二树及其存储表示370
5.2.1二树的概念370
5.2.2二树的顺序存储结构372
5.2.3二树的链式存储结构376
5.3二树的遍历384
5.3.1二树遍历的基本运算384
5.3.2创建二树的算法388
5.3.3二树遍历的非递归算法403
5.3.4二树遍历相关的算法417
5.3.5表达式树445
5.4线索二树453
5.4.1线索二树的结构定义453
5.4.2中序线索二树454
5.4.3先序和后序线索二树461
5.5树与森林的遍历467
5.5.1树与森林遍历的概要467
5.5.2基于树的双亲表示的遍历算法468
5.5.3基于子女链表表示的树的遍历算法472
5.5.4基于子女-兄弟链表表示的树的遍历算法476
5.6Huffman树486
5.6.1Huffman树及其结构定义486
5.6.2Huffman树相关的算法487
5.6.3Huffman编码相关的算法489
5.6.4很好判定树相关的算法493
5.7堆495
5.7.1堆的结构定义495
5.7.2小根堆的基本运算495
5.7.3小根堆相关的算法498
5.8并查集504
5.8.1并查集的结构定义504
5.8.2并查集主要作的实现505
第6章图509
6.1图的基本概念509
6.1.1图的基本定义与特征509
6.1.2图算法实例510
6.2图的存储表示511
6.2.1图的邻接矩阵表示511
6.2.2图的邻接表表示522
6.2.3无向图的邻接多重表表示534
6.2.4有向图的十字链表表示538
6.2.5关联矩阵541
6.3图的遍历544
6.3.1深度优先搜索544
6.3.2广度优先搜索549
6.3.3图顶点间的路径550
6.3.4图的连通性与生成树565
6.3.5双连通图的关节点578
6.4最小生成树579
6.4.1最小生成树的概念与定义579
6.4.2最小生成树相关的算法580
6.5最短路径592
6.5.1最短路径的概念592
6.5.2单源短路径相关的算法593
6.5.3所有顶点间短路径相关的算法605
6.6拓扑排序和关键路径613
6.6.1AOV网与拓扑排序613
6.6.2AOE网与关键路径618
6.7图的其他应用623
6.7.1算术表达式的计算623
6.7.2二部图627
6.7.3渡河问题629
6.7.4色问题633
第7章查找635
7.1查找的概念与简单查找方法635
7.1.1查找的概念635
7.1.2顺序查找635
7.1.3折半查找640
7.1.4斐波那契查找与插值查找644
7.1.5静态树表查找646
7.1.6跳表651
7.2二查找树655
7.2.1二查找树的概念655
7.2.2二查找树基本运算的实现655
7.2.3二查找树相关的算法659
7.2.4中序线索二查找树677
7.3AVL树680
7.3.1AVL树的概念680
7.3.2AVL树相关算法680
7.4B树与B+树690
7.4.1分块查找与索引表690
7.4.2B树696
7.4.3B+树703
7.5其他查找树711
7.5.1红黑树711
7.5.2伸展树722
7.5.3双链树727
7.5.4Trie树732
7.6散列法737
7.6.1散列法的概念737
7.6.2散列法的应用739
7.6.3用开地址法解决冲突743
7.6.4用链地址法解决冲突749
第8章排序753
8.1排序的概念与算法753
8.1.1排序的概念753
8.1.2计数排序算法753
8.2插入排序755
8.2.1直接插入排序755
8.2.2折半插入排序758
8.2.3希尔排序760
8.3交换排序761
8.3.1逆序与交换761
8.3.2起泡排序763
8.3.3快速排序769
8.4选择排序783
8.4.1简单选择排序783
8.4.2堆排序789
8.4.3锦标赛排序793
8.5归并排序797
8.5.1两路归并797
8.5.2递归二路归并排序805
8.5.3迭代的二路归并排序807
8.6桶排序813
8.6.1多排序码的概念813
8.6.2MSD桶排序813
8.6.3LSD桶排序817
8.7链表排序819
8.7.1链表排序方法819
8.7.2双向链表排序826
8.7.3静态链表排序827
8.8其他排序算法834
8.8.1选择算法834
8.8.2地址排序837
8.9外排序841
8.9.1输入输出缓冲区841
8.9.2多路平衡归并843
8.9.3初始归并段的生成845
8.9.4磁带归并排序853
8.9.5很好归并树855
参考文献859