数据结构课程设计案例精编:用C/C++描述

第一部分 理论基础.

绪言——致成长中的程序员们

一、为什么要使用c++?

二、为什么要使用stl?

三、编程的一些规范

四、应当使用什么开发环境?

第1章 数据结构导论

1．1 数据结构与算法

1．1．1 数据结构

1．1．2 算法

1．2 数据结构的抽象形式——抽象数据类型

1．2．1 抽象数据类型

1．2．2 应用程序编程接口(api)

1．2．3 维护程序和文档

1．3 c++类和抽象数据类型

1．3．1 c++类

1．3．2 继承性

1．3．3 多态性

1．3．4 泛型设计和模板

1．4 运算与算法

.1．4．1 运算

1．4．2 算法

1．5 算法分析

1．5．1 时空性能

1．5．2 时间复杂度分析

1．5．3 空间复杂度分析

1．5．4 算法分析与代码优化调整

第2章 c++语言概述

2．1 c++语言的演化和标准化历程

2．2 c++支持的程序设计风格

2．2．1 基于过程的程序设计

2．2．2 基于对象的程序设计

2．2．3 面向对象的程序设计

2．2．4 泛型程序设计

2．3 模块化程序设计

2．3．1 函数

2．3．2 类和封装机制

2．4 类的构造、析构和赋值

2．4．1 构造函数和析构函数

2．4．2 类的赋值

2．5 类层次结构——继承和多态

2．5．1 访问控制：public、private和protected继承

2．5．2 虚函数与多态

2．6 异常处理

2．6．1 异常处理的应用情况

2．6．2 异常处理基础知识

2．6．3 其他错误处理技术

2．7 推荐的编程习．惯和风格

第3章 c++模板编程入门

3．1 类模板

3．1．1 如何定义类模板

3．1．2 如何实现类模板的成员函数

3．1．3 如何使用类模板

3．2 函数模板

3．2．1 如何定义函数模板

3．2．2 如何使用函数模板

3．3 模板实例化

3．4 模板的特化

3．4．1 类模板的特化

3．4．2 函数模板的特化

3．5 模板参数

3．6 静态成员和变量

3．7 模板和friend

3．8 函数对象(仿函数)

3．8．1 如何定义函数对象

3．8．2 函数对象的使用

3．8．3模板函数对象

3．8．4 标准库中的函数对象

第4章 泛型设计、stl库与数据结构

4．1 标准c++与stl

4．1．1 模板——现代c++风格的基础

4．1．2 stl的发展历程

4．1．3 stl与c++标准程序库

4．1．4 stl的实现版本

4．1．5 准标准程序库：boost库

4．1．6 泛型算法与stl的应用展示

4．2 泛型程序设计与多态

4．2．1 面向对象程序设计中的多态

4．2．2 泛型程序设计中的多态

4．2．3 gp与oop的对比

4．3 泛型程序设计与stl

4．3．1 stl库的设计：容器、算法与迭代器

4．3．2 accumulate函数示例

4．4 概念与模型

4．4．1 必要条件集合

4．4．2 示例：迭代器

4．5 关联类型与特性类

4．5．1 函数模板中需要的关联类型

4．5．2 类中的typedef嵌套

4．5．3 特性类的定义

4．5．4 部分特化

4．5．5 标签分派，

4．6 stl中的核心concept：迭代器剖析

4．6．1 迭代器概述

4．6．2 迭代器与索引的比较

4．6．3 stl的迭代器分类

4．6．4 stl中迭代器种类的选择

4．7 stl的其他组件

4．7．1 stl的数据结构：容器

4．7．2 stl算法

4．7．3 函数对象

4．7．4 适配器

4．7．5 分配器

第二部分 基础数据结构

第5章 线性表

5．1 线性表概述

5．1．1 线性表基础知识

5．1．2 线性表类adt

5．2 顺序存储结构——顺序表

5．2．1 顺序表的定义及特点

5．2．2 顺序表的遍历与查找

5．2．3 顺序表的其他操作

5．2．4 顺序表类adt以及类定义

5．3 链式存储结构——链表

5．3．1 单链表

5．3．2 双向链表

5．3．3 循环链表

5．3．4 链表类adt以及类定义

5．4 vector的基本操作及应用

5．4．1 vector迭代器

5．4．2 vector的基本操作

5．5 list的基本操作及应用

5．5．1 list迭代器

5．5．2 list的基本操作

5．6 slist的基本操作及应用

5．6．1 slist的迭代器

5．6．2 slist的基本操作

5．7 线性表的应用案例

5．7．1 稀疏多项式的加法和乘法

5．7．2 大整数加法..

第6章 栈与队列

6．1 双端队列

6．1．1 deque概况

6．1．2 操作与应用

6．2 堆栈基础

6．2．1 堆栈的定义

6．2．2 堆栈adt

6．3 栈的使用

6．3．1 进制转换

6．3．2 列车调度

6．4 表达式计算

6．4．1 中缀表达式转换为后缀表达式

6．4．2 后缀表达式的计算

6．4．3 测试

6．5 队列和优先队列

6．5．1 队列的定义

6．5．2 队列adt

6．5．3 队列的实现

6．5．4 优先队列

6．6 使用队列

6．6．1 时间驱动的模拟

6．6．2 基数排序法

6．7 栈与队列的综合实例

6．7．1 农夫过河问题

6．7．2 深度优先搜索算法

6．7．3 广度优先搜索算法

第7章 递归

7．1 递归基础

7．1．1 递归的概念

7．1．2 使用递归的情况

7．2 汉诺塔问题

7．2．1 问题的提出

7．2．2 问题的递归求解

7．2．3 hanoi类

7．3 迷宫问题

7．3．1 问题的提出

7．3．2 迷宫的回溯分析

7．3．3 maze类

7．4 八皇后问题

7．4．1 问题的描述

7．4．2 八皇后问题的回溯分析

7．4．3 queenchess类的设计

7．5 递归算法的评价

7．5．1 递归工作栈

7．5．2 递归算法的复杂度

7．5．3 递归与迭代的比较

第8章 树和二叉树

8．1 树和二叉树基础知识

8．1．1 序列容器与有序关联容器

8．1．2 广义树结构

8．1．3 二叉树的定义与性质

8．1．4 二叉树遍历算法

8．1．5 二叉树遍历算法的应用

8．2 二叉搜索树基础知识

8．2．1 二叉搜索树的定义

8．2．2 二叉搜索树的操作

8．2．3 二叉搜索树类adt

8．2．4 二叉搜索树的结构

8．2．5 二叉搜索树的实现要点

8．2．6 二叉搜索树的迭代器

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 音像商店事务管理系统

第9章 图

9．1 图的抽象

9．1．1 图的描述

9．1．2 图的数据结构

9．2 图的算法

9．2．1 图搜索算法

9．2．2 拓扑排序

9．2．3 连通分量算法

9．2．4 最短路径问题

9．2．5 最小生成树问题

9．3 boost图库介绍

9．3．1 stl中的泛型

9．3．2 bgl中的泛型

9．3．3 bgl中的图算法

9．3．4 bgl实现的数据结构

9．3．5 bgl的历史

9．4 图类的实现与应用

9．4．1 图的概念(concepts)

9．4．2 图类的实现

9．4．3 图类应用示例

9．5 图算法的实现和应用

9．5．1 访问器

9．5．2 图遍历算法的应用

9．5．3 拓扑排序的应用

9．5．4 最短路径算法的应用

9．5．5 最小生成树算法的应用

9．6 图的建模与可视化——graphviz软件与dot语言

9．6．1 核心绘图引擎

9．6．2 图文件描述语言——dot语言

9．6．3 graphviz应用示例

第三部分 综合应用

第10章 综合应用案例

10．1 数据压缩——霍夫曼编码解码器的实现

10．1．1 数据压缩理论简介

10．1．2 huffman树

10．1．3 需求分析

10．1．4 huffman压缩类的接口与应用

10．1．5 huffman压缩类的实现

10．1．6 huffman解压缩

10．2 算法时间复杂度测度——算法计时器的实现

10．2．1 精确测定算法时间的困难

10．2．2 应用统计方法解决困难

10．2．3 完成自动分析的timer类

10．2．4 应用timer类测试stl sort算法时间性能

10．3 理论计算机科学家族谱的文档／视图模式——stl组件的综合应用

10．3．1 系统设计：“模型—视图—控制器”模式

10．3．2 数据关系建模与数据结构选择

10．3．3 从源数据文档到视图

10．3．4 完整的族谱视图程序以及运行示例

10．4 词典检索系统——数据结构选择对系统性能影响的示例

10．4．1 解决方案1：应用全排列的方法查找变位词

10．4．2 解决方案2：应用pair向量改进时间效率

10．4．3 解决方案3：使用映射改进空间效率

附录a boost安装指南

附录b 随书所附光盘内容清单

附录c stl库容器类速查手册...