C++数据结构原理与经典问题求解

第1章绪论

1.1数据与数据结构

1.1.1数据及其类型

1.1.2数据结构简介

1.2算法

1.2.1算法的概念

1.2.2算法的分析

1.2.3算法的设计

1.3C++语言简介

1.3.1C++的产生与发展

1.3.2C++与面向对象思想

1.3.3C++中的类和对象

1.4本章小结

第2章C++编程基础

2.1开始C++编程

2.1.1输入输出

2.1.2预处理

2.1.3名字空间

2.2深入的类编程

2.2.1访问控制

2.2.2初始化与清除

2.2.3动态创建对象

2.2.4友元函数

2.2.5拷贝构造函数

2.3丰富的C++特性

2.3.1常量

2.3.2函数重载

2.3.3运算符重载

2.3.4异常处理

2.4代码重用机制

2.4.1继承

2.4.2多态

2.4.3模板

2.5标准模板库

2.5.1STL简介

2.5.2STL构成

2.5.3STL的不同版本

2.6本章小结

第3章指针、数组与字符串

3.1指针

3.1.1指针的概念

3.1.2指针的语法

3.1.3函数与参数传递

3.2数组

3.2.1数组定义与初始化

3.2.2数组与指针

3.2.3数组的抽象数据类型

3.2.4大整数乘法问题

3.2.5荷兰国旗问题

3.3字符串

3.3.1C++中的字符串

3.3.2字符串抽象数据类型

3.3.3字符串的匹配算法

3.3.4字符串指数问题

3.4动态内存管理

3.4.1关键词new和delete

3.4.2避免内存错误

3.5本章小结

第4章链表

4.1单向链表

4.1.1单向链表的结构

4.1.2单向链表类的实现

4.1.3有序链表的合并

4.1.4多项式加法问题

4.2单向循环链表

4.2.1单向循环链表的结构

4.2.2单向循环链表类的实现

4.2.3约瑟夫问题

4.2.4魔术师发牌问题

4.2.5拉丁方阵问题

4.3双向循环链表

4.3.1双向循环链表的结构

4.3.2双向循环链表类的实现

4.3.3Vigenere加密问题

4.3.4选美比赛问题

4.4游标类的设计与实现

4.4.1游标类的结构

4.4.2游标类的实现

4.5STL与链表

4.5.1STL中链表类的接口

4.5.2遍历

4.5.3元素的插入与删除

4.6本章小结

第5章栈与队列

5.1栈

5.1.1栈的结构

5.1.2栈的实现

5.1.3括号匹配问题

5.1.4停车场模拟问题

5.2队列

5.2.1队列的结构

5.2.2队列的实现

5.2.3舞伴问题

5.2.4杨辉三角形问题

5.2.5游程编码问题

5.3优先级队列

5.3.1优先级队列的结构

5.3.2优先级队列的实现

5.4STL中的栈与队列

5.4.1STL中的stack

5.4.2STL中的queue

5.4.3STL中的priority_queue

5.5本章小结

第6章递归

6.1递归的概念

6.1.1递归的定义

6.1.2应用递归的原则

6.1.3递归和非递归的转化

6.2分治法

6.2.1分治法简述

6.2.2汉诺塔问题

6.2.3传染病问题

6.3回溯法

6.3.1回溯法简述

6.3.2迷宫问题

6.3.3八皇后问题

6.3.4骑士周游问题

6.4本章小结

第7章树

7.1树的概念

7.1.1树的定义

7.1.2树的术语

7.1.3树的抽象数据类型

7.2二叉树

7.2.1二叉树的定义

7.2.2二叉树的性质

7.2.3二叉树的实现

7.2.4二叉树的遍历

7.2.5二叉树的线索化

7.3树与森林

7.3.1树的存储表示

7.3.2树的实现

7.3.3树与森林的遍历

7.3.4森林与二叉树的转换

7.4霍夫曼树

7.4.1霍夫曼树的概念

7.4.2霍夫曼树的构造方法

7.4.3霍夫曼编码及其实现

7.5堆

7.5.1堆的概念

7.5.2堆的建立

7.5.3堆的操作

7.6基于STL实现树结构

7.6.1STL中的vector

7.6.2STL中的map

7.7医院建模问题

7.8本章小结

第8章图

8.1图的基本概念

8.1.1图的定义

8.1.2图的术语

8.1.3图的运算

8.1.4图的抽象数据类型

8.2图的存储与表示

8.2.1图的邻接矩阵表示

8.2.2图的邻接表表示

8.2.3两种表示法的比较

8.3图的遍历

8.3.1欧拉路径与欧拉回路

8.3.2哈密尔顿路径与哈密尔顿回路

8.3.3广度优先遍历

8.3.4深度优先遍历

8.4最短路径问题

8.4.1固定起点最短路问题

8.4.2非固定起点最短路问题

8.4.3最短路径的动态规划解法

8.4.4旅游交通路线问题

8.5最小生成树

8.5.1最小生成树的定义

8.5.2克鲁斯卡尔算法

8.5.3普里姆算法

8.6经典问题举例

8.6.1文字游戏问题

8.6.2道路修建问题

8.6.3回家路线问题

8.6.4水塘计算问题

8.6.5棍子还原问题

8.7本章小结

第9章树形搜索结构

9.1二叉搜索树

9.1.1二叉搜索树的概念

9.1.2二叉搜索树的操作

9.1.3二叉搜索树的实现

9.1.4二叉搜索树的分析

9.2AVL树

9.2.1AVL树的概念

9.2.2AVL树的旋转

9.2.3AVL树的实现

9.3红黑树

9.3.1红黑树的概念

9.3.2红黑树的操作

9.3.3红黑树的实现

9.4Trie树

9.4.1Trie树的概念

9.4.2Trie树的表示

9.4.3Trie树的实现

9.5本章小结

第10章集合与字典

10.1集合论基础

10.1.1集合的概念

10.1.2集合的运算

10.2集合的实现

10.2.1位向量集合

10.2.2链表集合

10.3字典

10.3.1字典的概念

10.3.2搜索运算

10.4散列

10.4.1散列的概念

10.4.2散列函数

10.4.3处理散列冲突

10.4.4散列的应用

10.5经典问题举例

10.5.1拼写检查问题

10.5.2无线网络问题

10.5.3第K个数问题

10.6STL中的set

10.7本章小结

第11章排序

11.1排序问题概述

11.1.1基本概念和定义

11.1.2排序算法的分类

11.1.3排序算法分析与选择

11.2插入排序

11.2.1直接插入排序

11.2.2二分法插入排序

11.2.3希尔排序

11.3选择排序

11.3.1直接选择排序

11.3.2堆排序

11.4交换排序

11.4.1冒泡法排序

11.4.2Shaker排序

11.4.3快速排序

11.5归并排序

11.6计数排序

11.7本章小结

参考文献

　　无独有偶，许多世界顶级的软件公司都喜欢在面试时问一些考查应试者思维能力的问题，为什么呢？道理很简单，单纯掌握一门编程语言并不足以编写出好的程序。重要的是，掌握思考问题的方法和解决问题的策略。而本书不仅是一本向程序员传授专业技术的书，更是一本教导人们如何思考问题的书。本书注重对数据结构相关理论的应用和实现，以典型数据结构、程序设计方法及问题求解方法为研究对象，将三者融会贯通的同时，巧妙地将丰富的C++面向对象语言程序设计实践融入其中。全书时刻不离对经典问题求解这一要旨，通过生动丰富的问题描述突出经典问题求解的趣味性和实效性，并且注意从日常生活中可能遇到的实际问题出发以引导读者思考。　　本书是一部关于计算机科学与工程领域基础性核心课程数据结构与算法的专著。全书以典型数据结构、程序设计方法及问题求解方法为研究对象，用C++面向对象程序设计语言作为描述语言，时刻突出对经典问题求解这一要旨，并将丰富的C++语言程序设计实践融入其中。　　全书采用“数据结构原理描述→面向对象实现→解决经典问题→STL介绍”的基本架构，既强调理论的完整性，又突出实例引导的驱动性，用经典问题和大量背景描述提高读者的阅读兴趣，从而使原本枯燥的理论变得妙趣横生。基于上述框架，本书简要回顾了基本C++程序设计方法后，又全面系统地介绍了链表、队列、栈、树、图等基本数据结构。此外，本书还提供了近百个算法、数十个经典问题和十余个综合问题的完整实现代码近万余行。　　本书内容实用，体例新颖，结构清晰，既可以作为大、中专院校在校师生相关课程的参考书，也可以作为信息学竞赛中数据结构方面的辅导用书。此外，本书也可供计算机科学与工程领域从业人员参考和查阅。