绪论 1
§数据结构的发展 1
§数据结构的定义 1
§数据结构的重要性 2
第一章 表 4
§1．1表的概述 4
§1．2线性表 5
1．2．1线性表的顺序存贮 5
1．2．2线性表的单链接存贮 9
1．2．3线性表顺序存贮与链接存贮比较 11
1．2．4单链接表举例 12
1．2．5循环单链接表 13
1．2．6线性表的双链接存贮 15
1．2．7双链表的应用举例 17
§1．3栈 23
1．3．1栈的顺序存贮 23
1．3．2多个栈的链接存贮 33
1．3．3栈的应用 34
1．4．1顺序队列 46
§1．4队列 46
1．4．2链接队列 47
1．4．3队列的应用 49
§1．5压缩存贮、索引存贮和散列存贮 52
1．5．1压缩存贮 52
1．5．2索引存贮 53
1．5．3散列存贮 55
§1．6数组 73
1．6．1矩形数组 73
1．6．2矩形数组的压缩存贮 78
1．6．3 m维数组 91
§1．7串 96
1．7．1串的若干操作 96
1．1．2串的样品匹配问题 97
第二章 排序 102
§2．1插入排序 103
2．1．1线性插入排序 103
2．1．2链接线性插入排序 104
2．1．3折半插入排序 106
2．2．1线性选择排序 107
§2．2选择排序 107
2．2．2计数选择排序 108
2．2．3二次选择排序 110
§2．3交换排序 113
2．3．1标准排序 113
2．3．2振动排序（Shaker-Sort） 115
2．3．3 Shell排序及延迟交换的Shell排序 116
2．3．4快速排序 118
2．3．5更快速排序 122
2．3．6二分排序 123
2．3．7 Batcher并行排序（Batcher s parallel mathod） 125
§2．4合并排序 127
2．4．1二路合并 127
2．4．2 K路合并 129
2．4．3 二路线性合并排序 130
2．4．4二路自然合并排序 131
§2．5堆阵排序及改进后的堆阵排序 133
§2．6口袋排序 140
§2．7杂凑排序 143
§2．8几种主要排序方法的比较 145
2．9．1文件的基本概念 146
§2．9外排序 146
2．9．2文件处理的基本语句 147
2．9．3单缓冲区的排序 148
2．9．4两路合并排序 151
2．9．5多路合并排序 155
第三章 检索 159
§3．1检索给定的关键字 159
3．1．1顺序检索 159
3．1．2折半检索 160
3．1．3菲波那契检索（Fibonaccian searching） 162
3．1．4简单跳步检索 163
3．1．5两级固定跳步检索 165
§3．2检索第i个大的关键字 166
§3．3几种主要检索方法比较 171
第四章 树 173
§4．1一般树 173
4．1．1树的定义 173
4．1．2树的基本术语 173
4．1．3树的几种表示方法 175
4．1．4树的存贮形式 175
4．1．5树的一些操作 179
4．1．6树结构的应用 180
§4．2二叉树 181
4．2．1二叉树的定义与一般树转换为二叉树 181
4．2．2二叉树的周游 183
4．2．3二叉树的构造、检索和删除 187
4．2．4构造穿线二叉树 197
4．2．5穿线二叉树的删除 200
4．2．6二叉树的顺序存贮 207
4．3．2平衡排序树的构造——Adelson插入算法 211
4．3．1平衡树的定义 211
§4．3平衡树 211
4．3．3平衡排序树的删除 219
4．3．4平衡树的数学特征——“菲波那契树” 224
§4．4平衡穿线树 237
4．4．1平衡穿线树的插入 237
4．4．2平衡穿线树的删除S算法 239
§4．5最优检索树 242
4．5．1通路长度 242
4．5．2最优检索树 244
4．5．3最优叶子检索树——Huffmann树 245
§4．6最优排序检索树和最优叶子排序树 247
§4．7最左树 252
§4．8判定树 256
§4．9解答树 257
4．9．1背包问题（贪心问题） 258
4．9．2皇后问题 271
4．9．3马步问题 276
4．9．4树和Backus系统 278
§4．10键树 290
4．11．1多路检索树 294
§4．11 B树 294
4．11．2 B树的定义 295
4．11．3 B树的构造 295
4．11．4 B树的检索 296
4．11．5 B树的插入 298
4．11．6 B树的删除 301
§4．12 B+树 303
4．12．1 B+树的定义 305
4．12．2 B+树的检索 305
4．12．3 B+树的插入 307
4．12．4 B+树的删除 308
§4．13 B*树 313
4．13．1 B*树的定义 313
4．13．2 B*树的检索和插入 313
4．13．3 B*树的删除 318
§4．14前缀B树 323
4．14．1前缀B树的构造 324
4．14．4前缀B树的删除 326
4．14．3前缀B树的插入 326
4．14．2前缀B树的检索 326
§4．15二分B树 330
4．15．1二分B树的定义和构造 330
4．15．2二分B树的检索 331
4．15．3二分B树的插入 333
4．15．4二分B树的删除 334
4．15．5改进的二分B树 339
§4．16采用B树结构应注意的问题 340
§5．1图和叶表 342
5．1．1图的定义和基本术语 342
第五章 氧杂的数据结构 342
5．1．2图的表示和存贮形式 343
5．1．3图的周游和连通分量 346
5．1．4图的生成树和最小价值生成树 350
5．1．5无向图及其应用 353
5．1．6有向图及其应用 359
5．1．7有序图和叶表 378
5．1．8叶表转换成二叉图 378
5．1．9打印叶表叶子的值 385
§5．2多重链接结构和组合查询 386
5．2．2检索m重属性文件的方法 387
5．2．1 m重属性文件 387
附录一 BM算法 396
附录二 Rabin-Krap算法 398
附录三 习题 401
第一章 403
第二章 403
第三章 405
第四章 405
第五章 408
参考文献 410