出版说明

前言

第1章数据结构与算法

11引言

111为什么要学习数据结构

112数据结构课程的内容

12数据结构的概念

121基本概念和术语

122抽象数据类型

13数据结构的描述方法

131数据结构的C语言描述

132数据结构的C++语言描述

133数据结构的Java语言描述

14算法

141算法及其特征

142算法的描述

143算法的性能分析

15典型例题

16本章小结

161知识点小结

162扩展学习导读

练习题

实验题

题目1比较算法复杂性描述函数的

增长

题目2矩阵连乘算法的时间和空间

复杂度

第2章递归

21引言

211问题的提出

212什么是递归

22递归调用的实现原理

221递归算法的构成

222递归调用的内部过程

223递归的正确性证明

23递归转化为非递归

231递归转化为递推

232递归转化为回溯

233手工模拟递归

24典型例题

25本章小结

251知识点小结

252扩展学习导读

练习题

实验题

题目1全排列的递归实现

题目2八皇后问题

题目3比较递归与非递归算法的

时空效率

第3章线性结构

31引言

311问题的提出

312线性表的定义

313线性表的基本运算

32线性表的顺序存储与实现

321顺序表

322顺序表上基本运算的实现

323顺序表应用举例

33线性表的链式存储与实现

331单链表

332单链表上基本运算的实现

333循环链表

334双向链表

335链表应用举例

34顺序表和链表的比较

35堆栈

351堆栈的定义及基本运算

352堆栈的存储及运算实现

353堆栈的应用举例

36队列

361队列的定义及基本运算

362队列的存储及运算实现

363队列的应用举例

37其他线性结构及扩展

371字符串

372数组

373特殊矩阵

374稀疏矩阵

38典型例题

39本章小结

391知识点小结

392扩展学习导读

练习题

实验题

题目1Josephus环问题

题目2一元多项式运算

题目3模拟停车场管理

第4章树结构

41引言

411问题提出

412相关概念

42二叉树

421二叉树的基本运算

422二叉树的主要性质

423二叉树的存储

424二叉树基本运算的实现

43二叉树的遍历

431递归方法实现二叉树遍历

432非递归方法实现二叉树的

三种遍历

433按层次遍历二叉树

44二叉树遍历的应用

441构造二叉树的二叉链表存储

442在二叉树中查找值为x的

数据元素

443统计给定二叉树中叶子结点的

数目

444表达式运算

445由遍历序列恢复二叉树

45线索二叉树

451线索二叉树的定义及其结构

452线索二叉树的创建

453线索二叉树的遍历

46最优二叉树

461最优二叉树的概念

462最优二叉树的构造

463最优二叉树的应用——哈夫曼

编码

47树

471树的基本操作

472树的表示

473树的存储

474树和森林与二叉树之间的

转换

475树或森林的遍历

476树的应用

48典型例题

49本章小结

491知识点小结

492扩展学习导读

练习题

实验题

题目哈夫曼编码/译码器

第5章图结构

51引言

511问题的提出

512相关概念

513图的基本操作

52图的存储

521邻接矩阵

522邻接表

53图的遍历

531深度优先搜索

532广度优先搜索

533遍历图的简单应用

54生成树和最小生成树

541生成树和生成森林

542最小生成树

543构造最小生成树的Prim算法

544构造最小生成树的Kruskal

算法

55最短路径

551单源点最短路径——Dijkstra

算法

552每一对顶点之间的最短路径

56拓扑排序与关键路径

561有向无环图的概念

562AOV网与拓扑排序

563AOE网与关键路径

57典型例题

58本章小结

581知识点小结

582扩展学习导读

练习题

实验题

题目校园导游程序

第6章查找技术

61引言

611问题提出

612相关概念

62线性表查找

621顺序查找

622顺序存储的有序表查找

63树结构查找

631二叉排序树

632平衡二叉树

64散列表查找

641基本概念

642散列函数的构造方法

643处理冲突的方法

644散列表的性能分析

65查找方法的比较

66典型例题

67本章小结

671知识点小结

672扩展学习导读

练习题

实验题

题目1职工信息检索系统

题目2个人图书管理系统

第7章排序技术

71引言

711问题的提出

712相关概念

72插入排序

721直接插入排序

722折半插入排序

723希尔排序

73交换排序

731冒泡排序

732快速排序

74选择排序

741简单选择排序

742树结构选择排序

743堆排序

75归并排序

76基数排序

761多关键码排序

762链式基数排序

77排序方法比较

771性能比较

772不同排序方法的适用情况

78典型例题

79本章小结

791知识点小结

792扩展学习导读

练习题

实验题

题目各种内部排序的性能比较

第8章扩展应用举例

81求最大子段和

811问题描述

812问题分析与解决

82表达式树的构造

821问题描述

822问题分析与解决

83由等价关系求划分

831问题描述

832问题分析与解决

84本章小结

841知识点小结

842扩展学习导读

练习题

实验题

题目1模拟银行排队办理业务

题目20-1背包问题

附录

附录A实验要求

附录B模拟试卷

模拟试卷一（本科水平）

模拟试卷二（本科水平）

模拟试卷三（研究生入学考试水平）

模拟试卷四（研究生入学考试水平）

附录C2012年全国硕士研究生入学

统一考试计算机科学与技术

学科联考试卷（“数据结构”

部分）

参考文献