数据结构与算法实验实践教程

第1章 程序测试与运行时间度量

1.1 程序的规格说明与测试

1.1.1 程序的规格说明

1.1.2 编程练习：排序函数的规格说明

1.1.3 程序测试

1.1.4 编程练习：排序的测试

1.1.5 随机数的生成

1.1.6 自动化测试

1.1.7 编程练习：排序的自动测试

1.2 程序的运行时间度量

1.2.1 取得CPU时间

1.2.2 统计排序函数的运行时间

1.2.3 编程练习：排序的运行时间度量

1.2.4 理解算法的时间复杂度

1.2.5 编程练习：最大连续子序列和算法运算时间的比较

小结

第2章 线性表和串的实现及其应用

2.1 标准库数据结构vector和list的使用

2.1.1 标准库数据结构vector

2.1.2 线性表vector的应用

2.1.3 编程练习：vector的应用

2.1.4 标准库数据结构list

2.1.5 线性表的应用

2.1.6 编程练习：线性表的应用

2.1.7 编程练习：多项式的表示和运算

2.1.8 编程练习：集合运算

2.2 抽象数据类型线性表的实现及其测试

2.2.1 线性表抽象数据类型定义

2.2.2 编程练习：使用数组表示线性表

2.2.3 使用单链表表示线性表

2.2.4 编程练习：熟悉单链表

2.2.5 编程练习：线性表的单链表实现

2.3 串的应用

2.3.1 数据结构串string

2.3.2 编程练习：索引表的生成

2.3.3 编程练习：一个行编辑器的实现

小结

第3章 栈与队列的实现和应用

3.1 标准库栈的使用

3.1.1 STL模板类stack

3.1.2 编程练习：熟悉栈的操作和栈的应用

3.2 栈的实现

3.2.1 栈的定义

3.2.2 编程练习：栈的实现

3.3 队列的应用

3.3.1 STL模板队列queue

3.3.2 队列应用例子

3.4 队列的实现

3.4.1 队列的定义

3.4.2 编程练习：队列的实现

3.5 栈和队列的应用

3.5.1 车厢调度问题

3.5.2 编程练习：车厢调度问题

3.5.3 编程练习：服务队列模拟问题

小结

第4章 递归

4.1 递归算法

4.1.1 递归函数的例子

4.1.2 一摞烙饼的排序

4.1.3 编程练习：递归

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 编程练习：回溯

……

第5章 二叉树的实现和应用

第6章 查找的实现与应用

第7章 排序的实现与应用

第8章 图算法及其应用

第9章 标准模板库STL简介

附录A 问题和软装置列表

附录B 实验报告参考格式

附录C 部分参考程序

参考文献

索引

《数据结构与算法实验实践教程》是为“数据结构与算法”实验课程设计的教材。全书共9 章，内容包括程序测试与运行时间度量、线性表和串的实现及其应用、栈与队列的实现和应用、递归、二叉树的实现和应用、查找的实现与应用、排序的实现与应用、图算法及其应用和标准模板库STL 简介。每章针对常用的数据结构和算法设计了例题和习题，其中大部分习题可以通过网上在线测评系统http://soj.me提交。部分习题在书后附有参考答案。本书是独立于其他数据结构和算法教材的辅导书，可作为高等院校数据结构与算法实验课的教材和参考书，也适用于计算机编程爱好者。

《高等院校计算机实验与实践系列示范教材：数据结构与算法实验实践教程》特色：站在工程、开发和研究三个角度，进行实践性教学环节的设计。
从社会对计算机专业人才能力需求的角度，系统地规划计算机实验和实践的方式和内容。
开发实训验证型、开发研究型等不同层次的教学内容，以满足大专、本科以及某些研究生层次的教学需求。以系统性、开放性、经典性和适用性等全新的面貌呈现在中国的计算机教学领域。
精心挖掘和遴选作者，把他们多年积累的教学经验编写成教材。