数据结构与程序实现PDF电子书下载

第1章 数据结构与算法的概念 1

1．1数据结构的概念 1

1．1．1数据、数据元素与数据类型 1

1．1．2数据结构的概念 3

1．1．3抽象数据类型 5

1．2算法的概念和描述 7

1．2．1算法的概念 7

1．2．2算法的描述 10

1．3算法的时间复杂度和空间复杂度 10

1．3．1算法的评价 10

1．3．2算法的时间复杂度 11

1．3．3算法的空间复杂度 14

习题1． 15

第2章 线性表 19

2．1线性表的概念和运算 19

2．1．1线性表的概念 19

2．1．2线性表的运算 20

2．2顺序表 23

2．2．1顺序表的概念 23

2．2．2顺序表中基本运算的实现 23

2．3链表 41

2．3．1链表的基本结构 42

2．3．2线性链表的操作 4

2．3．3循环链表 52

2．3．4双向链表 55

2．3．5线性表存储方法的比较 57

2．4广义表 58

2．4．1广义表的概念和基本运算 58

2．4．2广义表的存储表示与算法实现 59

2．4．3广义表的应用 78

2．5典型试题分析 78

习题2 95

第3章 栈和队列 97

3．1栈 97

3．1．1栈的概念 97

3．1．2 顺序栈 99

3．1．3链接栈 118

3．1．4栈的应用举例 121

3．2队列 130

3．2．1队列的概念 130

3．2．2顺序队列 131

3．2．3链接队列 143

3．2．4循环队列 145

3．2．5队列的应用举例 156

3．3典型试题分析 160

习题3 184

第4章 数组、矩阵和串 188

4．1数组的存储结构 188

4．1．1一维数组的存储结构 188

4．1．2二维数组的存储结构 193

4．1．3 n维数组的存储结构 201

4．2矩阵的压缩存储 210

4．2．1特殊矩阵的压缩存储 210

4．2．2稀疏矩阵的压缩存储 211

4．3串 225

4．3．1串的基本概念 226

4．3．2串的基本操作 226

4．3．3串的存储结构 228

4．3．4模式匹配 231

4．4典型试题分析 234

习题4 260

第5章 树 264

5．1树 264

5．1．1树的定义及表示 264

5．1．2树的常用术语 265

5．1．3树的基本运算 267

5．1．4树的存储结构 267

5．1．5树的遍历 271

5．2二叉树 274

5．2．1二叉树的定义 274

5．2．2二叉树的几种基本形态 274

5．2．3二叉树的基本性质 274

5．2．4二叉树的存储结构 276

5．2．5二叉树的生成算法与遍历 278

5．2．6二叉树的基本运算与实现 292

5．2．7二叉树的算法举例 299

5．3树、森林与二叉树的转换 306

5．4线索二叉树 313

5．4．1线索二叉树的概念 313

5．4．2以中序线索链表为存储结构的中序遍历 315

5．4．3以中序线索链表为存储结构的逆中序遍历 316

5．4．4线索链表的生成 317

5．4．5线索二叉树的操作实现 322

5．5二叉树的应用 329

5．5．1二叉排序树 329

5．5．2哈夫曼树 336

5．6典型试题分析 342

习题5 361

第6章 图 369

6．1图的基本概念 369

6．1．1图的定义 369

6．1．2图的常用术语 370

6．1．3图的基本操作 372

6．2图的存储结构 373

6．2．1邻接矩阵 373

6．2．2邻接表与逆邻接表 383

6．2．3邻接多重表 395

6．3图的遍历 396

6．3．1深度优先遍历 396

6．3．2广度优先遍历 400

6．3．3图的遍历的简单应用 408

6．4无向连通图的最小生成树 418

6．4．1最小生成树的概念 418

6．4．2 Prim算法 419

6．4．3 Kruskal算法 424

6．5图的最短路径 428

6．5．1单源最短路径 428

6．5．2所有顶点对之间的最短路径 433

6．6有向无环图及其应用 440

6．6．1有向无环图的概念 440

6．6．2 AOV网与拓扑排序 440

6．6．3 AOE网与关键路径 446

6．7典型试题分析 455

习题6 495

参考文献 502