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

出版时间：2012-11  出版社：乔海燕、蒋爱军、高集荣、 刘晓铭 清华大学出版社 (2012-12出版)  作者：乔海燕，蒋爱军，高集荣 等 著  页数：217  

内容概要

　　《高等院校计算机实验与实践系列示范教材：数据结构与算法实验实践教程》共9章，内容包括程序测试与运行时间度量、线性表和串的实现及其应用、栈与队列的实现和应用、递归、二叉树的实现和应用、查找的实现与应用、排序的实现与应用、图算法及其应用和标准模板库STL简介。每章针对常用的数据结构和算法设计了例题和习题，部分习题在书后附有参考答案。

书籍目录

第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章二叉树的实现和应用 5.1二叉树的表示 5.1.1二叉链表 5.1.2二叉链表的构造 5.1.3编程练习：二叉树的二叉链表表示 5.1.4编程练习：二叉树的输出 5.1.5二叉树的顺序结构 5.2二叉树的遍历 5.2.1二叉树的深度优先遍历 5.2.2编程练习：二叉树的遍历和构造 5.2.3编程练习：二叉树的构造 5.2.4二叉树的广度优先遍历 5.2.5编程练习：树的层次遍历 5.3 Huffman编码的实现及其应用 5.3.1 Huffman编码及其无损压缩 5.3.2实现基于Huffman编码的压缩和解压缩 小结 第6章查找的实现与应用 6.1顺序查找 6.1.1简单查找 6.1.2编程练习：顺序查找的应用和实现 6.1.3条件查找 6.1.4函数对象 6.1.5编程练习：条件查找的应用 6.2二分查找的应用 6.2.1返回存在性的二分查找 6.2.2编程练习：二分查找的应用和实现 6.2.3返回位置的二分查找 6.2.4编程练习：查找中间数 6.3二叉查找树 6.3.1二叉查找树的插入 6.3.2编程练习：二叉查找树的插入 6.3.3二叉查找树的查找 6.3.4编程练习：二叉查找树的查找 6.3.5二叉查找树的删除 6.3.6编程练习：二叉查找树的删除 …… 第7章排序的实现与应用 第8章图算法及其应用 第9章标准模板库STL简介 参考文献 索引

章节摘录

版权页：   插图：   模板机制的使用，使得可以实现容器与数据类型的无关性（同样的容器可以管理不同数据类型的元素，用类模板实现），以及算法与数据类型的无关性（同样的算法可以操作不同类型的数据，用函数模板实现）。但是，仅有模板机制，却无法实现算法与容器的无关性。也就是说，无法用同样的算法来操纵不同种类的容器。为了解决这一问题，C++标准库设计中使用了迭代器这一概念，通用算法使用迭代器在容器上进行操作。 所谓迭代器，就是一种抽象的指针，是面向对象的广义指针，用来指向容器（或流）中的对象，使得可以按顺序访问容器（即数据结构）中的对象，而不必暴露容器的内部结构，从而实现算法与容器的无关性。借助于迭代器，同一算法可以对不同种类容器中的数据进行操作。C++标准库中的迭代器以类模板的方式定义，使得可以在不同的数据结构上体现统一的行为方式。也就是说，可以使用迭代器以基本相同的方式遍历容器中的元素，而无须关注底层的数据结构到底是顺序存储的vector还是链式存储的Iist。 9.2.1 C++标准库迭代器简介 C++标准库中迭代器的实现机制非常复杂，下面仅从使用的角度对迭代器进行介绍。“迭代器”一词一般有两种含义：一是指“迭代器类型”；二是指“迭代器类型的对象”，就像有时将一个“指针类型的变量”也叫做一个“指针”一样。 迭代器类型有许多具体的不同类别，就像指针类型有基类型不同的许多指针类型一样（如指向int型对象的指针与指向string型对象的指针就属于基类型不同的指针类型）。标准库中定义的迭代器类型有5种类别，不同类别的迭代器类型提供不同的操作，实现不同的功能，具体如表9—7所示。 注9.1 表9—7中所列的每个迭代器类别称为一个概念（concept），如果一种迭代器支持一个概念所要求的运算，也称该迭代器是相应概念的模型。例如，vector关联的迭代器是输入迭代器的模型，是双向迭代器的模型，也是随机迭代器的模型。 标准库中的每种容器都以嵌入类的形式定义了自己的迭代器类型，这些迭代器类型对基类型为容器元素类型的指针进行封装，并重载相应运算符。

编辑推荐

《高等院校计算机实验与实践系列示范教材:数据结构与算法实验实践教程》是独立于其他数据结构和算法教材的辅导书，可作为高等院校数据结构与算法实验课的教材和参考书，也适用于计算机编程爱好者。

用户评论 (总计1条)

•   值得拥有，再也不用担心挂科了！！