本书严格按照计算机考研大纲的内容和次序来组织。每一章都包括相关知识点的介绍和总结，以及大量的习题解答。习题中包含2009—2014年的所有考研习题，并给出了深入浅出的解答。除了考研题目之外，本书还选用了大量的习题，包含的题型有概念题、选择题和程式设计题。这些习题可以很好地帮助读者理解数据结构的基本知识以及灵活套用数据结构。

本书可作为参加计算机及相关专业硕士研究生考前複习的参考教材，也可以作为各高等院校计算机专业或其他相关专业“数据结构”课程的教材。

数据结构是计算机专业最基础、最重要的课程之一，也是全国硕士研究生入学考试计算机专业的必考科目。

第1章绪论/1

1.1算法与数据结构/1

1.1.1数据的逻辑结构/1

1.1.2数据结构的运算/2

1.2存储实现/3

1.3算法分析/4

1.3.1时间複杂度/4

1.3.2空间複杂度/7

习题与解答/7第2章线性表/11

2.1线性表的定义和基本操作/11

2.1.1线性表的定义/11

2.1.2线性表的基本操作/11

2.2线性表的实现/12

2.2.1线性表的顺序实现/12

2.2.2线性表的连结实现/15

2.3线性表的套用/22

2.3.1大整数的处理/22

2.3.2多项式的处理/25

习题与解答/27第3章栈、伫列和数组/38

3.1栈/38

3.1.1栈的基本概念/38

3.1.2栈的顺序实现/39

3.1.3栈的连结实现/40

3.1.4栈的套用/41

3.2伫列/53

3.2.1伫列的概念/53

3.2.2伫列的顺序实现/54

3.2.3伫列的连结实现/553.2.4伫列的套用/57

3.2.5火车车厢重排/61

3.3特殊矩阵的存储/64

3.3.1对称矩阵/64

3.3.2三角矩阵/65

3.3.3稀疏矩阵/65

习题与解答/66第4章树与二叉树/86

4.1树的基本概念/86

4.2二叉树/87

4.2.1二叉树的定义及主要特徵/87

4.2.2二叉树的顺序实现/88

4.2.3二叉树的连结实现/89

4.2.4二叉树的遍历/91

4.2.5线索二叉树的概念和构造/98

4.3树和森林/100

4.3.1树的存储/100

4.3.2森林和二叉树的转换/102

4.3.3树和森林的遍历/103

4.4树和二叉树的套用/103

4.4.1二叉排序树/103

4.4.2平衡二叉树/106

4.4.3哈夫曼树和哈夫曼编码/112

4.4.4树与等价类的处理/115

习题与解答/117第5章图/146

5.1图的概念/146

5.2图的存储/148

5.2.1邻接矩阵法/148

5.2.2邻接表法/149

5.2.3邻接多重表/150

5.2.4十字鍊表/151

5.3图的遍历/152

5.3.1深度优先遍历/152

5.3.2广度优先遍历/154

5.4图的基本套用/157

5.4.1最小生成树/157

5.4.2最短路径/162

5.4.3拓扑排序/168

5.4.4关键路径/170

习题与解答/173第6章查找/196

6.1查找的基本概念/196

6.2静态查找表/196

6.2.1顺序查找/197

6.2.2折半查找/197

6.2.3分块查找/198

6.3B树和B+树/199

6.3.1B树/199

6.3.2B+树/202

6.4散列表/203

6.4.1散列函式/204

6.4.2碰撞的解决/204

6.4.3字元串的存储与匹配/211

6.5查找算法的分析与套用/214

习题与解答/215第7章排序/226

7.1基本概念/226

7.2插入排序/226

7.2.1直接插入排序/226

7.2.2折半插入排序/227

7.3冒泡排序/227

7.4简单选择排序/228

7.5希尔排序/228

7.6快速排序/229

7.7堆排序/231

7.8二路归併排序/235

7.9基数排序/236

7.10外排序/238

7.11各种内排序算法的比较/240

习题与解答/241参考文献/264

第1章走进Qt/1

1.1Qt简介/1

1.1.1认识Qt/1

1.1.2Qt开发环境的主要构成介绍/2

1.1.3使用Qt开发C++应用程式的优势/4

1.2Qt的下载、安装与配置/4

1.2.1Windows平台下Qt的C++语言开发环境安装与配置/4

1.2.2Linux平台下Qt的C++语言开发环境安装与配置/7

1.3Qt Creator集成开发环境/12

1.3.1Qt Creator集成开发环境/12

1.3.2Qt Creator常用选单功能介绍/13

1.3.3使用Qt创建项目/14

1.3.4Qt开发环境的使用方法/18

1.3.5Qt项目档案的建立、添加和删除/18

1.3.6编辑项目的源程式档案和界面档案/19

1.3.7项目编译模式及其配置/20

1.3.8编译并连结生成项目档案/20

1.3.9纠正编译或连线出现的错误/20

1.3.10Qt工具列的使用/21

1.4Qt Creator在线上帮助系统及其使用/21

1.4.1Qt中如何寻求帮助/21

1.4.2帮助档案的打开及使用原始码

编辑器/22

1.4.3缩小查找範围/23

1.5使用Qt Creator开发C++语言程式/24

1.5.1Windows平台下使用Qt开发C++语言程式/24

1.5.2Linux平台下使用Qt开发C++语言程式/29

1.6习题/36第2章C++程式设计基础/37

2.1C++语言简介/37

2.1.1认识C++/37

2.1.2C++的标準化/37

2.2C++源程式的结构/38

2.2.1C++源程式举例/38

2.2.2C++源程式的结构/40

2.2.3C++语言的基本语法成分/41

2.3基本数据与表达式/42

2.3.1数据类型/42

2.3.2常量和变数/44

2.3.3运算符与表达式/46

2.4C++中的输入输出/47

2.5程式的控制结构/50

2.5.1顺序结构/50

2.5.2选择结构/50

2.5.3循环结构/55

2.5.4跳转语句/58

2.6函式/59

2.6.1函式/59

2.6.2函式的其他特性/62

2.7数组与字元串/65

2.7.1数组/65

2.7.2字元串与string类/67

2.8指针与引用/70

2.8.1指针/70

2.8.2引用/71

2.9const修饰符/76

2.10动态记忆体分配/79

2.11习题/82

2.11.1选择题/82

2.11.2填空题/83

2.11.3编程题/84第3章类与对象/85

3.1面向对象程式设计概述/85

3.1.1面向对象的基本概念/85

3.1.2面向对象的基本特徵/88

3.1.3面向对象的语言简介/89

3.2类与对象的定义/90

3.2.1类的定义/90

3.2.2对象的定义与使用/97

3.2.3类的作用域/101

3.2.4类的封装性和信息隐藏——公有接口与私有实现的分离/102

3.3构造函式与析构函式/104

3.3.1构造函式/104

3.3.2複製构造函式/113

3.3.3析构函式/118

3.4对象的深複製/120

3.5静态成员/122

3.5.1静态数据成员/122

3.5.2静态成员函式/124

3.6常类型/127

3.6.1常对象/127

3.6.2类的常数据成员/128

3.6.3类的常成员函式/129

3.7友元/131

3.7.1友元函式/131

3.7.2友元类/136

3.7.3友元套用举例/138

3.8对象数组与类的组合/140

3.8.1对象数组/140

3.8.2类的组合/144

3.9程式举例/147

3.10习题/149

3.10.1选择题/149

3.10.2问答及编程题/152第4章继承与派生/154

4.1单继承/155

4.1.1继承的定义/155

4.1.2访问控制/157

4.1.3重名的成员变数和成员函式/160

4.1.4在派生类中访问静态成员/162

4.1.5基类的初始化/163

4.2多继承/168

4.2.1派生类的构造与访问/168

4.2.2虚继承/169

4.3习题/170第5章虚函式与多态/171

5.1类指针的关係/172

5.2静态联编和动态联编/174

5.3虚函式/175

5.4纯虚函式和抽象类/178

5.5习题/181第6章运算符重载/182

6.1运算符重载概述/183

6.1.1运算符重载的实质/183

6.1.2用友元函式和成员函式重载运算符的异同/186

6.1.3++和--运算符的重载/188

6.2习题/191第7章模板和异常处理/192

7.1模板的概念/192

7.2函式模板/192

7.2.1函式模板的声明/192

7.2.2函式模板的实例化/193

7.2.3函式模板套用举例/195

7.3类模板/197

7.3.1类模板的定义/197

7.3.2类模板的实例化/198

7.3.3类模板的套用举例/199

7.4标準模板库/202

7.4.1容器/203

7.4.2算法/206

7.4.3叠代器/209

7.5异常处理/210

7.5.1异常处理概述/210

7.5.2异常处理的实现/211

7.5.3标準库中的异常类型/216

7.6习题/218

7.6.1选择题/218

7.6.2编程题/218第8章输入输出流与命名空间/220

8.1I/O流的概念/220

8.2标準I/O流/221

8.2.1标準I/O流概述/221

8.2.2标準输出/222

8.2.3标準输入/224

8.2.4重载插入/提取函式/225

8.3格式控制/228

8.3.1用ios成员函式格式化/228

8.3.2用操纵运算元格式化/231

8.4档案处理/232

8.4.1档案和流/232

8.4.2档案的打开和关闭/233

8.4.3文本档案/234

8.4.4二进制档案/235

8.5命名空间/238

8.6习题/241第9章图形界面程式设计基础/242

9.1图形界面程式设计基础知识/242

9.1.1C++中的对象/242

9.1.2Qt C++中的窗体/243

9.1.3Qt C++中的部件和部件类/243

9.1.4Qt C++中的属性(Properties)视窗/244

9.2Qt的信号和槽/244

9.3Qt的元对象系统/246

9.4Qt命令行法开发图形界面程式/246

9.5Qt中如何实现用户操作的回响/249

9.6Qt中如何实现视窗部件的布局/250

9.7习题/252第10章对话框编程/254

10.1代码编程创建对话框/254

10.2对话框的可视化设计/263

10.3可扩展的对话框/271

10.4对话框的动态实现/279

10.5Qt内置的视窗部件和对话框类/280

10.6习题/285第11章使用Qt开发文本编辑器/286

11.1Qt Creator的下载和安装/286

11.2Qt Creator开发简单的文本编辑器/287

11.2.1创建项目TextEditor/287

11.2.2TextEditor的主视窗、选单和

图示/289

11.2.3TextEditor档案新建、保存和另外储存为的功能实现/300

11.2.4TextEditor档案的打开、关闭和退出系统的功能实现/308

11.2.5TextEditor文本複製、剪下、贴上以及撤销的功能实现/309

11.2.6TextEditor文本查找功能的

实现/310

11.2.7TextEditor查找和定位函式的

方法/311

11.2.8TextEditor中实现状态栏/316

11.3习题/318附录AC++关键字/319附录BC++运算符/320

参考文献/321