数据结构与算法注重理论与实践相结合，不仅是计算机学科的核心基础课程，也是程序设计的重要理论基础。本书系统地讲述了数据结构与算法的基本理论和实际应用，《数据结构与算法/计算机系列教材》分为两个部分，共9章，第一部分主要讨论数据结构的基础知识和表示方式，包括线性结构（线性表、栈、队列、串、数组及广义表）、树形结构、图形结构等的定义、表示和实现；第二部分讨论排序和查找两类常用算法的原理、方法及其实现技巧。 全书强调实用，注重理论指导下的实际可操作性，注重实际问题的解决。书中所有关于基本数据结构的定义和算法描述均采用标准的C语言格式给出，所有算法代码均在TC 2.0、Visual C++ 6.0、Codeblocks等开发环境中调试通过并运行正确，读者可根据各自的要求和习惯等选择使用对应的工具。 本书可作为高等学校计算机类各专业数据结构课程的教材或参考书，特别适合应用技术型本科层次的学生使用；也可供从事计算机应用相关工作的人员参考。

　　随着计算机科学技术的不断发展和应用领域的不断扩大，在许多非数值处理的应用问题中，计算机所面对的数据结构十分复杂、数据量巨大且形式多样化，如何根据各类实际问题归纳、抽象出对象的数据特征及对象间的相互联系，从而选择合适的数据组织方法和存储方法，设计高效的求解算法，成为计算机学科需要解决的最迫切的任务。
数据结构与算法是一门实践性很强同时又十分抽象的计算机学科基础课程，本书基于CDIO的理念进行编写。CDIO是源于国外的工程教育模式，体现了欧美理工类学科教育改革的全新理念。通过构思(Conceive)、设计(Design)、实现(Implement)和运行(Operate)4个环节，引导学生积极参与“做中学”和“基于项目的教育和学习”的整个过程，达到学习效果的提高和升华，真正实现课程教学的目的。本书将这种教学理念引入到编写中，每种数据结构均以流行的抽象数据类型格式（ADT）对其进行定义，使用C语言函数的形式描述其对应的存储结构及基本操作算法，以典型算法设计来实现其基本应用，以应用实例分析深化对基本概念的理解和培养分析问题与解决问题的能力。
本书强调实用性，注重理论指导下的可操作性，注重提高分析问题、解决问题的能力。各章均配有小结，目的在于引导读者复习该章内容；各章课外习题和实验课题由配套教材《数据结构与算法习题解析和实验指导》提供，以期通过典型习题与实践指导使读者更全面、更透彻地掌握数据结构与算法这门课程。
本书第1章介绍数据结构的概念，第2～第5章介绍各种线性结构的知识，第6章介绍树形结构，第7章介绍图形结构，第8章介绍查找算法，第9章介绍排序算法。
参加编写的有邹永林（第1、第4、第7和第9章）、周蓓（第2、第6和第8章）、唐晓阳（第3和第5章），周思林、朱奭、沈健、洪蕾等参与讨论和算法的设计与调试；邹永林负责全书的统稿。
由于作者水平有限，书中难免存在不足之处，恳请广大读者批评指正。
编者
2015年5月

第1章绪论/1
1.1引言/1
1.1.1几个实例/1
1.1.2数据结构的产生和发展/3
1.2数据结构/4
1.2.1基本概念和术语/4
1.2.2数据结构定义/5
1.2.3数据类型和抽象数据类型/7
1.3算法定义、描述和分析/10
1.3.1算法定义/10
1.3.2算法设计技术/11
1.3.3算法描述/12
1.3.4算法分析/13
1.4小结/18
习题1/18第2章基本线性结构——线性表/20
2.1概述/20
2.1.1线性表的概念/20
2.1.2线性表的类型定义/22
2.2顺序表/23
2.2.1线性表的顺序表示/23
2.2.2顺序表的实现/23
2.3链表/28
2.3.1线性表的链式表示/28
2.3.2线性链表的实现/28
2.3.3循环链表的实现/33
2.3.4双向链表的实现/34
2.3.5静态链表的实现/35
2.4算法设计举例/362.5小结/39
习题2/40第3章限定性线性结构——栈和队列/41
3.1栈/41
3.1.1栈的类型定义/41
3.1.2顺序栈的表示和实现/42
3.1.3链栈的表示和实现/45
3.2队列/47
3.2.1队列的类型定义/47
3.2.2顺序队列的表示和实现/48
3.2.3链队的表示和实现/51
3.3算法设计举例/53
3.4小结/59
习题3/59第4章特殊线性结构——串/61
4.1概述/61
4.1.1串的概念/61
4.1.2串的逻辑定义/62
4.2串的表示和实现/63
4.2.1串的顺序存储表示/63
4.2.2串的链式存储表示/66
4.3模式匹配/67
4.3.1概念/67
4.3.2模式匹配的基本算法（BF算法）/67
4.3.3KMP算法/69
4.3.4Horspool算法和BoyerMoore算法/72
4.4算法设计举例/77
4.5小结/78
习题4/79第5章扩展线性结构——数组和广义表/80
5.1数组/80
5.1.1数组的定义/80
5.1.2数组的存储表示/81
5.2矩阵的压缩存储/83
5.2.1特殊矩阵/84
5.2.2稀疏矩阵/85
5.3广义表/89
5.3.1广义表的定义/89
5.3.2广义表的存储结构/91
5.4算法设计举例/94
5.5小结/96
习题5/96第6章树形结构——树和二叉树/98
6.1树的定义和术语/98
6.1.1树的定义/98
6.1.2树的基本术语/99
6.1.3树的表示/100
6.1.4树的遍历/101
6.2二叉树/101
6.2.1二叉树的定义/101
6.2.2二叉树的性质/102
6.2.3二叉树的存储结构/104
6.2.4遍历二叉树/106
6.2.5线索二叉树/109
6.2.6二叉树算法设计举例 /113
6.3树和森林/115
6.3.1树的存储结构/116
6.3.2树、森林与二叉树的转换/118
6.3.3森林的遍历/120
6.4哈夫曼树及其应用/121
6.4.1哈夫曼树/121
6.4.2哈夫曼编码/122
6.4.3哈夫曼编码的实现/123
6.5小结/126
习题6/126第7章图形结构——图/128
7.1图的基本概念/128
7.1.1图的定义/128
7.1.2基本术语/130
7.2图的表示和实现/132
7.2.1邻接矩阵/132
7.2.2邻接表/134
7.2.3十字链表/137
7.2.4邻接多重表/138
7.3图的遍历/139
7.3.1深度优先搜索/139
7.3.2广度优先搜索/142
7.4图的典型应用算法设计/144
7.4.1生成树和最小生成树/145
7.4.2拓扑排序/150
7.4.3关键路径/153
7.4.4最短路径/161
7.5小结/165
习题7/165第8章常用算法I——查找/167
8.1基本概念/167
8.1.1查找的定义/167
8.1.2基本术语/168
8.2线性表的查找/169
8.2.1顺序查找/169
8.2.2二分查找/170
8.2.3分块查找/173
8.3树表查找/174
8.3.1二叉排序树/174
8.3.2平衡二叉树/181
8.3.3B树/189
8.4散列查找/197
8.4.1散列表/197
8.4.2散列函数的构造方法/199
8.4.3处理冲突的方法/201
8.4.4散列表的查找及分析 /204
8.5自组织线性表/207
8.6小结/209
习题8/210第9章常用算法II——排序/211
9.1概述/211
9.2内部排序/212
9.2.1直接插入排序和希尔排序/212
9.2.2冒泡排序和快速排序/215
9.2.3简单选择排序和堆排序/220
9.2.4归并排序/223
9.2.5基数排序/225
9.2.6其他内部排序方法/229
9.2.7内部排序效益评估/231
9.3外部排序/231
9.3.1外部排序方法/232
9.3.2自然归并/233
9.3.3多路平衡归并/234
9.3.4置换选择排序/235
9.3.5最佳归并树/236
9.4小结/237
习题9/237

参考文献/238
第1章计算机基础知识/1
1.1计算机概述/1
1.1.1计算机发展简史/1
1.1.2计算机的分类/3
1.1.3微机发展简史/4
1.1.4计算机的特点/5
1.1.5计算机的发展趋势/6
1.1.6计算机的应用领域/7
1.2计算机信息技术基础/8
1.2.1信息和数据/8
1.2.2信息的特征/9
1.2.3计算机处理信息的过程/10
1.2.4信息高速公路/10
1.3数制转换/11
1.3.1数字化信息编码的概念/11
1.3.2进位计数制/11
1.3.3不同进制之间的转换/13
1.3.4二进制数在计算机内的表示/15
1.4计算机中的信息编码/18
1.4.1二|十进制BCD码/18
1.4.2西文字符编码/18
1.4.3汉字的编码表示/20
1.4.4汉字的输入/22
1.5计算机系统组成/22
1.5.1冯·诺依曼结构的计算机硬件系统/22
1.5.2软件系统/24
1.5.3计算机的工作过程/26
1.6微型计算机的硬件组成/26
1.6.1微机的硬件组成/26
1.6.2微机的主要性能和配置/33
1.7多媒体技术/34
1.7.1多媒体技术概念/34
1.7.2多媒体计算机的组成/35
1.7.3多媒体设备和接口/35
1.7.4多媒体技术的应用/37
1.7.5常见多媒体文件格式简介/38第2章Windows XP操作系统/41
2.1操作系统概述/41
2.1.1操作系统基础知识/41
2.1.2典型的操作系统/43
2.2中文Windows XP基础知识/45
2.2.1Windows XP概述/45
2.2.2Windows XP的基本概念、术语及其基本操作/48
2.3Windows XP磁盘文件管理/61
2.3.1Windows XP中文件及文件夹的浏览/61
2.3.2在Windows XP中文件及文件夹的管理/63
2.3.3Windows XP磁盘的管理/76
2.4Windows XP的设置/78
2.4.1控制面板的概念/78
2.4.2显示器的设置/78
2.4.3输入设备的设置/81
2.4.4“开始”菜单的设置/82
2.4.5设置输入法/83
2.4.6添加硬件/84
2.4.7添加/删除程序/85
2.4.8打印机的设置/88
2.4.9其他辅助设置 /91
2.5Windows XP附件的使用/93
2.5.1记事本的使用/93
2.5.2画图的使用/94
2.5.3Windows XP系统工具的使用/96
2.5.4计算器的使用/97
2.5.5Windows XP中的多媒体应用程序/98第3章Word 2003及应用/102
3.1启动Word 2003/102
3.1.1使用“开始”菜单启动Word/102
3.1.2使用桌面快捷方式启动Word/102
3.1.3打开已有的Word文档启动Word/102
3.2Word 2003窗口/103
3.2.1标题栏/104
3.2.2菜单栏/104
3.2.3工具栏/105
3.2.4标尺/107
3.2.5编辑区/108
3.2.6滚动条/108
3.2.7状态栏/108
3.2.8任务窗格/108
3.3创建新文档/109
3.3.1创建空白文档/110
3.3.2使用本机上的模板创建新文档/110
3.4文档内容的录入/111
3.4.1文档录入基础/112
3.4.2输入中英文文字和符号/112
3.4.3插入对象/113
3.5保存和关闭文档/115
3.5.1保存文档/115
3.5.2关闭文档/118
3.6打开文档/118
3.6.1打开一个文档/118
3.6.2同时打开多个文档/120
3.7视图方式和其他显示方式/121
3.7.1普通视图方式/121
3.7.2页面视图方式/122
3.7.3Web版式视图方式/122
3.7.4大纲视图方式/122
3.7.5阅读版式视图方式/123
3.7.6文档结构图/123
3.7.7全屏显示/124
3.7.8设置显示比例/124
3.7.9拆分窗口/125
3.7.10显示或隐藏非打印字符/126
3.8文档的编辑与排版/126
3.8.1文档的基本编辑/126
3.8.2字符格式设置/131
3.8.3段落格式设置/135
3.8.4美化文档及排版/138
3.8.5页面设置/147
3.8.6查找与替换/148
3.8.7拼写和语法检查/150
3.8.8打印预览及打印/152
3.8.9样式和模板/154
3.9表格应用/157
3.9.1创建表格/157
3.9.2数据输入与表格选择/161
3.9.3编辑表格/162
3.9.4设置表格格式/168
3.9.5表格计算与排序/172
3.10图形对象处理/174
3.10.1绘制的图形/174
3.10.2插入与编辑图片/185
3.10.3艺术字/191
3.10.4文本框与图文混排/194
3.10.5公式编辑器/197第4章Excel 2003及应用/201
4.1Excel 2003基础/201
4.1.1Excel 2003窗口/201
4.1.2工作簿的基本操作/205
4.1.3保护工作簿/208
4.2工作表的编辑/209
4.2.1数据输入/209
4.2.2工作表的编辑/215
4.2.3工作表的操作/221
4.3工作表中数值计算/223
4.3.1使用公式/223
4.3.2使用函数/228
4.4工作表的格式设置/232
4.4.1单元格格式设置/232
4.4.2页面设置及打印/242
4.5数据管理/246
4.5.1数据清单的概念/246
4.5.2数据排序/247
4.5.3数据筛选/249
4.5.4数据分类汇总/252
4.6数据图表化/254
4.6.1图表的基础知识/254
4.6.2创建与编辑图表/257
4.7Word与Excel的协同操作/263第5章PowerPoint 2003及应用/265
5.1PowerPoint 2003基础/265
5.1.1PowerPoint 2003的启动/265
5.1.2PowerPoint 2003的窗口/265
5.1.3视图方式/266
5.2创建演示文稿/267
5.2.1从空白演示文稿开始创建/268
5.2.2根据内容提示向导创建演示文稿/269
5.2.3根据设计模板创建演示文稿/270
5.2.4根据现有演示文稿创建演示文稿/272
5.3幻灯片的制作和编辑/273
5.3.1幻灯片的制作/273
5.3.2幻灯片的制作/273
5.4幻灯片的编辑和基本格式设置/281
5.4.1选择幻灯片/281
5.4.2文本的编辑和格式设置/282
5.4.3删除、隐藏和重排幻灯片/284
5.5幻灯片的修饰/286
5.5.1幻灯片版式/286
5.5.2背景/286
5.5.3应用设计模板/288
5.5.4应用配色方案/289
5.5.5应用母版/290
5.5.6页眉和页脚/291
5.6演示文稿放映与打包/292
5.6.1设置动画效果/292
5.6.2设置切换效果和切换时间/295
5.6.3录制旁白/296
5.6.4超链接/297
5.6.5设置放映方式/299
5.6.6 幻灯片放映方法/301
5.6.7演讲者放映方式下的放映控制/302
5.6.8演示文稿的打印/303
5.6.9演示文稿的打包/304第6章Access 2003及应用/306
6.1数据库系统简介/306
6.1.1数据库的概念/306
6.1.2数据库技术的产生和发展/307
6.1.3数据模型/308
6.1.4Access简介/311
6.2Access 2003的基本操作/312
6.2.1启动与退出Access 2003/312
6.2.2Access数据库对象/312
6.2.3数据库基本操作/314
6.3表及应用/318
6.3.1表简介/318
6.3.2表的建立/319
6.3.3数据的编辑/323
6.3.4建立表间关系/325
6.4查询及应用/327
6.4.1查询的概念/327
6.4.2查询的建立/328
6.4.3查询的基本操作/330
6.5窗体及应用/332
6.5.1窗体的概念/332
6.5.2窗体的建立/333
6.5.3利用窗体进行数据处理/337
6.6打印/339
6.6.1记录的打印/339
6.6.2窗体的打印/339
6.6.3报表的打印/340第7章计算机网络及Internet/343
7.1计算机网络基础知识/343
7.1.1计算机网络的发展/343
7.1.2计算机网络的分类/344
7.1.3计算机网络的功能/346
7.1.4计算机网络体系结构和网络协议的基本概念/346
7.1.5物理地址和逻辑地址/349
7.1.6计算机网络硬件/349
7.2Internet基础知识/351
7.2.1Internet的发展史及其特点/351
7.2.2Internet提供的服务/352
7.2.3Internet的组成/354
7.2.4IP地址和域名/354
7.2.5Internet在中国/357
7.3Internet常用接入方式/358
7.3.1通过电话拨号接入Internet/359
7.3.2通过局域网接入Internet/364
7.3.3通过ADSL接入Internet/365
7.3.4断开Internet连接/366
7.4诊断网络故障的简单命令/366
7.5WWW与IE浏览器/368
7.5.1WWW的基本概念/368
7.5.2IE的基本应用/370
7.5.3在Internet上搜索和下载信息/375
7.5.4IE的基本设置/378
7.6FTP与BBS/381
7.6.1FTP/381
7.6.2BBS/383
7.7电子邮件服务/385
7.7.1电子邮箱简介/385
7.7.2申请一个免费的电子邮箱/386
7.8使用Outlook Express收发电子邮件/387
7.8.1邮件账户/388
7.8.2创建并发送电子邮件/391
7.8.3接收和阅读电子邮件/395
7.8.4邮件管理和通讯簿/396第8章计算机病毒及网络信息安全/402
8.1计算机病毒/402
8.1.1病毒历史/402
8.1.2病毒的定义与特性/403
8.1.3病毒的结构及分类/404
8.1.4常见病毒介绍/405
8.1.5计算机病毒的传染与症状/407
8.1.6病毒的预防与清除/407
8.2网络信息安全/409
8.2.1网络信息安全概述/409
8.2.2网络黑客/410
8.2.3计算机犯罪/411
8.2.4信息安全技术/413第9章网页制作/416
9.1HTML 概述/416
9.1.1HTML和页面/416
9.1.2HTML文件/417
9.2FrontPage 2003及应用/418
9.2.1FrontPage的启动与退出/421
9.2.2FrontPage中的视图/421
9.2.3FrontPage的编辑方式/422
9.2.4网页制作/422
9.2.5网页布局/432
9.2.6创建表单页面/439
9.2.7网页的发布/440
第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