目    录

第1章  绪论 1

1.1  知识点1：数据结构的基本概念 1

1.1.1  要点归纳 1

1.1.2  例题解析 3

1.2  知识点2：算法和算法分析 7

1.2.1  要点归纳 7

1.2.2  例题解析 9

第2章  线性表 16

2.1  知识点1：线性表的基本概念 16

2.1.1  要点归纳 16

2.1.2  例题解析 18

2.2  知识点2：顺序表的算法 22

2.2.1  要点归纳 22

2.2.2  例题解析 24

2.3  知识点3：单链表的算法 31

2.3.1  要点归纳 31

2.3.2  例题解析 35

2.4  知识点4：双链表的算法 51

2.4.1  要点归纳 51

2.4.2  例题解析 55

2.5  知识点5：循环链表的算法 58

2.5.1  要点归纳 58

2.5.2  例题解析 61

第3章  栈和递归 67

3.1  知识点1：栈的基本概念 67

3.1.1  要点归纳 67

3.1.2  例题解析 68

3.2  知识点2：顺序栈的算法 72

3.2.1  要点归纳 72

3.2.2  例题解析 80

3.3  知识点3：链栈的算法 86

3.3.1  要点归纳 86

3.3.2  例题解析 87

3.4  知识点4：递归 90

3.4.1  要点归纳 90

3.4.2  例题解析 99

第4章  队列 111

4.1  知识点1：队列的基本概念 111

4.1.1  要点归纳 111

4.1.2  例题解析 112

4.2  知识点2：顺序队的算法 114

4.2.1  要点归纳 114

4.2.2  例题解析 117

4.3  知识点3：链队的算法 124

4.3.1  要点归纳 124

4.3.2  例题解析 126

第5章  串 134

5.1  知识点1：串的基本概念 134

5.1.1  要点归纳 134

5.1.2  例题解析 135

5.2  知识点2：顺序串的算法 137

5.2.1  要点归纳 137

5.2.2  例题解析 139

5.3  知识点3：链串的算法 143

5.3.1  要点归纳 143

5.3.2  例题解析 146

5.4  知识点4：模式匹配的算法 149

5.4.1  要点归纳 149

5.4.2  例题解析 155

第6章  数组和稀疏矩阵 163

6.1  知识点1：数组 163

6.1.1  要点归纳 163

6.1.2  例题解析 165

6.2  知识点2：稀疏矩阵 171

6.2.1  要点归纳 171

6.2.2  例题解析 174

第7章  树和二叉树 178

7.1  知识点1：树的基本概念 178

7.1.1  要点归纳 178

7.1.2  例题解析 182

7.2  知识点2：二叉树的基本概念 185

7.2.1  要点归纳 185

7.2.2  例题解析 189

7.3  知识点3：二叉树的算法 197

7.3.1  要点归纳 197

7.3.2  例题解析 207

7.4  知识点4：线索二叉树 232

7.4.1  要点归纳 232

7.4.2  例题解析 236

7.5  知识点5：哈夫曼树 239

7.5.1  要点归纳 239

7.5.2  例题解析 241

第8章  广义表 245

8.1  知识点1：广义表的基本概念 245

8.1.1  要点归纳 245

8.1.2  例题解析 246

8.2  知识点2：广义表的第一种存储结构 248

8.2.1  要点归纳 248

8.2.2  例题解析 254

8.3  知识点3：广义表的第二种存储结构 261

8.3.1  要点归纳 261

8.3.2  例题解析 266

第9章  图 272

9.1  知识点1：图的基本概念 272

9.1.1  要点归纳 272

9.1.2  例题解析 276

9.2  知识点2：图的遍历算法 285

9.2.1  要点归纳 285

9.2.2  例题解析 287

9.3  知识点3：最小生成树 300

9.3.1  要点归纳 300

9.3.2  例题解析 304

9.4  知识点4：最短路径 311

9.4.1  要点归纳 311

9.4.2  例题解析 316

9.5  知识点5：AOV网和拓扑排序 322

9.5.1  要点归纳 322

9.5.2  例题解析 323

9.6  知识点6：AOE网与关键路径 329

9.6.1  要点归纳 329

9.6.2  例题解析 331

第10章  查找 336

10.1  知识点1：线性表的查找 336

10.1.1  要点归纳 336

10.1.2  例题解析 340

10.2  知识点2：树表的查找 346

10.2.1  要点归纳 346

10.2.2  例题解析 355

10.3  知识点3：哈希表的查找 373

10.3.1  要点归纳 373

10.3.2  例题解析 376

第11章  内排序 393

11.1  知识点1：插入排序算法 393

11.1.1  要点归纳 393

11.1.2  例题解析 395

11.2  知识点2：选择排序算法 399

11.2.1  要点归纳 399

11.2.2  例题解析 402

11.3  知识点3：交换排序算法 409

11.3.1  要点归纳 409

11.3.2  例题解析 411

11.4  知识点4：归并排序算法 419

11.4.1  要点归纳 419

11.4.2  例题解析 421

11.5  知识点5：基数排序算法 423

11.5.1  要点归纳 423

11.5.2  例题解析 424

第12章  外排序和文件 429

12.1  知识点1：外排序 429

12.1.1  要点归纳 429

12.1.2  例题解析 431

12.2  知识点2：文件 435

12.2.1  要点归纳 435

12.2.2  例题解析 438

附录A  一份重点大学本科“数据结构”课程考试试题 444

附录B  一份重点大学本科“数据结构”课程考试试题 451

附录C  一份重点大学考研“数据结构”考试试题 458

附录D  一份重点大学考研“数据结构”考试试题 463

P10    2. 填空题       解：   解：   解：   解：   解：   答：   答：

P140

先判断参数i、j是否正确，若不正确，则返回一个空串；否则，新建一个串str，将s.ch[0]～s.ch[i?2]复制到str中，再将t.ch[0]～t.ch[t.len?1]复制到str中，最后将s.ch[i+j?1]～s.ch[s.len?1]复制到str中。返回这个新串。算法如下：

P156

表5.3  计算next数组

j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

t a b c a a b b c a b c a a b d a b

next[j] ?1 0 0 0 1 1 2 0 0 1 2 3 4 5 6 0 1

P157

表5.6  计算next数组

j 0 1 2 3 4 5 6 7 8

模式t a b c a b c a a a

next[j] ?1 0 0 0 1 2 3 4 1