数据结构与算法

内容推荐

　　《数据结构与算法》共分13章。第1章：从c到c++，帮助读者系统复习c++，同时使本书也适用于只学过c语言的读者。第2章～第4章的内容包括：string类、向量类模板vector、链表类模板和适配器，主要为在自定义stl框架下描述数据结构奠定基础。第5章～第13章的内容包括：二叉树、堆、树、图、二叉搜索树、平衡二叉搜索树、b树、散列、排序和性能分析，主要是在定义stl框架下描述的数据结构。
　　《数据结构与算法》既可以作为高等院校计算机及相关专业本科生的数据结构教材，也可以作为计算机编程爱好者和工程技术人员的自学教材和参考书。

 

目录

出版者的话

编委会

丛书序言

前言

教学建议

第1章　从C到C++

  1.1　从数组到顺序表

    1.1.1　数组的局限性

    1.1.2　顺序表的声明

    1.1.3　顺序表的实现

    1.1.4　删除顺序表的重复数据

    1.1.5　数据抽象

  1.2　C语言的局限性

  1.3　C++基础知识

    1.3.1　变量和const常量

    1.3.2　输入/输出

    1.3.3　内联函数

    1.3.4　运算符重载

    1.3.5　函数重载

    1.3.6　引用型

    1.3.7　构造函数

    1.3.8　提取符和插入符重载

    1.3.9　默认参数

    1.3.10　new和delete运算符

  1.4　C++顺序表类

    1.4.1　从C顺序表到C++顺序表类

    1.4.2　顺序表类的实现

    1.4.3　复制构造函数

    1.4.4　复制赋值运算符重载

    1.4.5　下标运算符重载

    1.4.6　构造函数与初始化

    1.4.7　new和delete运算符与构造和析构

    1.4.8　类定义

  1.5　函数模板和类模板

    1.5.1　函数模板

    1.5.2　顺序表类模板

  1.6　继承和多态性

    1.6.1　构造函数的参数初始化表

    1.6.2　继承

    1.6.3　受保护成员

    1.6.4　多态性和虚函数

    1.6.5　虚析构函数

    1.6.6　纯虚函数和抽象类

  习题

第2章　String类

  2.1　String类的声明

  2.2　String类的实现

    2.2.1　构造和析构

    2.2.2　成员赋值运算符

    2.2.3　成员转换

    2.2.4　串连接

    2.2.5　关系运算

    2.2.6　求子串

    2.2.7　子串插入

    2.2.8　子串删除

    2.2.9　下标运算符

    2.2.10　字符查找

    2.2.11　输入/输出

  2.3　模式匹配

  2.4　深入讨论

    2.4.1　转换赋值运算符函数的替代

    2.4.2　成员函数“类串+C串”的替代

    2.4.3　explicit修饰符

  习题

第3章　向量类模板Vector

  3.1　Vector定义

  3.2　通用算法和迭代器

  3.3　Vector的插入和删除函数

  3.4　求素数

  3.5　函数对象

  3.6　深入讨论——函数模板实例化中的问题

  习题

第4章　链表类模板和适配器

  4.1　链表类模板list

  4.2　适配器

    4.2.1　链栈

    4.2.2　链队列

    4.2.3　优先级链队列

  习题

第5章　二叉树

  5.1　二叉树的基本概念

  5.2　二叉树的性质

  5.3　二叉树的存储结构

    5.3.1　二叉树顺序存储结构

    5.3.2　二叉树链式存储结构

  5.4　二叉树层次遍历

    5.4.1　层次遍历

    5.4.2　把二叉树的顺序存储转化为链式存储

    5.4.3　垂直输出二叉树

  5.5　二叉树前序遍历

    5.5.1　前序遍历递归算法

    5.5.2　前序遍历非递归算法

    5.5.3　快速排序

    5.5.4　集合的幂集

  5.6　二叉树中序遍历

    5.6.1　中序遍历递归算法

    5.6.2　中序遍历非递归算法

    5.6.3　汉诺塔递归算法

  5.7　二叉树后序遍历

    5.7.1　后序遍历递归算法

    5.7.2　后序遍历非递归算法

    5.7.3　求二叉树的深度以及二叉链表的复制和删除

    5.7.4　把二叉树的顺序存储转化为链式存储的递归算法

    5.7.5　由前序和中序序列建立二叉链表

  习题

第6章　堆

  6.1　小根堆Heap类

  6.2　堆排序

  6.3　哈夫曼树

    6.3.1　哈夫曼树的定义

    6.3.2　建立哈夫曼树

    6.3.3　哈夫曼编码

  习题

第7章　树

  7.1　树的基本概念和存储

  7.2　Tree类

  7.3　树的遍历

  7.4　八皇后

  习题

第8章　图

  8.1　图的基本概念

  8.2　Graph类

  8.3　图的遍历

    8.3.1　广度优先遍历

    8.3.2　深度优先遍历

  8.4　最小生成树

    8.4.1　普里姆算法

    8.4.2　克鲁斯卡尔算法

  8.5　最短路径

    8.5.1　求单源最短路径的迪克斯特拉算法

    8.5.2　所有顶点对之间的最短带权路径

    8.5.3　一顶点对之间的最短带权路径

  8.6　拓扑序列

  8.7　关键路径

  8.8　迷宫求解

  习题

第9章　二叉搜索树

  9.1　类型声明与实现

  9.2　中序迭代器

  9.3　频率统计

  9.4　中序线索二叉树

  习题

第10章　平衡二叉搜索树

  10.1　动态平衡方法

  10.2　平衡二叉搜索树类型

  习题

第11章　B树

  11.1　线性索引

  11.2　静态m路搜索树

  11.3　B_树

  11.4　B+树

  习题

第12章　散列

  12.1　散列表

  12.2　散列函数

    12.2.1　平方取中法

    12.2.2　除留余数法

    12.2.3　折叠法

    12.2.4　数字分析法

  12.3　分离链接法

  12.4　开放定址法

    12.4.1　线性探查法

    12.4.2　平方探查法

    12.4.3　双散列函数探查法

  习题

第13章　排序和性能分析

  13.1　性能分析

    13.1.1　时间复杂性分析

    13.1.2　空间复杂性分析

  13.2　插入排序

    13.2.1　直接插入排序

    13.2.2　折半插入排序

    13.2.3　希尔排序

  13.3　交换排序

    13.3.1　起泡排序

    13.3.2　快速排序

  13.4　选择排序

    13.4.1　直接选择排序

    13.4.2　堆排序

    13.4.3　锦标赛排序

  13.5　归并排序

    13.5.1　归并

    13.5.2　迭代归并排序

  13.6　基数排序

  13.7　外排序

    13.7.1　外排序的基本过程

    13.7.2　k路归并

  习题