算法与数据结构

出版时间：2009  出版社：电子工业出版社  作者：漆涛  页数：308  
Tag标签：无  

内容概要

　　《算法与数据结构（C++版）》是普通高等教育“十一五”国家级规划教材，系统介绍各种数据结构、常用算法及算法分析技术。数据结构的内容包括线性结构、树形结构、哈希结构、索引结构；算法方面的内容包括选择算法、查找算法、排序算法。《算法与数据结构（C++版）》还较为详细地分析了各种算法的时间复杂度和空间复杂度，介绍了分摊复杂度分析技术。作为各种数据结构和算法的应用，《算法与数据结构（C++版）》给出了图的标准界面及其实现。利用这个标准界面，实现了图论中的一些经典算法。　　《算法与数据结构（C++版）》以算法为主线组织内容，仿照C++标准模板库的界面给出了许多算法和数据结构的实现。《算法与数据结构（C++版）》可作为高校计算机相关专业“数据结构”课程的教材，也可作为计算机工作者的参考书。

书籍目录

第1章 绪论1.1 利用计算机解决问题的几个步骤1.2 基本概念和术语1.3 算法及其复杂度分析1.4 算法的描述语言第2章 算法分析技术2.1 无穷大的阶2.2 若干序列和函数的渐进性质2.2.1 调和级数2.2.2 Fibonacci序列2.2.3 log2函数2.2.4 基本定理2.2.5 Catalan数2.2.6 一个特别序列2.3 算法的时间复杂度2.4 算法的空间复杂度2.5 冒泡排序算法复杂度分析2.6 分摊复杂度分析2.6.1 累计法2.6.2 势函数法2.6.3 捐款记账法习题第3章 线性表3.1 顺序线性表：向量3.1.1 Vector类模板的成员变量3.1.2 向量的迭代子3.1.3 获取向量的成员3.1.4 向量元素的删除3.1.5 向量的存储管理3.1.6 添加函数3.1.7 完整的Vector类3.2 单链表3.2.1 单链表迭代子类3.2.2 添加和删除操作3.3 其他形式的单链表3.4 双链表3.5 静态链表3.6 动态内存管理3.7 矩阵3.8 对称矩阵3.9 稀疏矩阵习题第4章 栈与队列4.1 栈的定义与实现4.2 栈与函数调用4.2.1 函数调用框架4.2.2 汉诺塔问题4.2.3 间接递归调用4.3 广义栈4.4 回溯法4.4.1 八皇后问题4.4.2 八皇后问题回溯法的改进4.5 队列4.5.1 用链表实现队列4.5.2 用循环数组实现队列4.6 双端队列4.7 基数排序习题第5章 字符串与模式匹配算法5.1 字符集与字符5.2 字符串5.3 简单模式匹配算法5.4 KMP算法5.4.1 KMP算法的改进5.4.2 KMP类5.5 有限状态自动机模式匹配算法5.5.1 有限状态自动机5.5.2 模式匹配有限状态自动机5.6 Boyer-Moore模式匹配算法5.7 BM-KMP模式匹配算法习题第6章 树与二叉树6.1 树与森林6.2 二叉树6.3 二又树的二叉链表表示……第7章 选择第8章 查找第9章 排序第10章 图第11章 STL简介第12章 C++语言概要第13章 伪随机数产生与高精度计时器参考文献索引

章节摘录

第1章 绪论算法与数据结构不仅是计算机科学与技术学科一门重要的基础课程，也是许多后继课程（如操作系统、数据库和编译原理等）的先修课程。它不仅是计算机专业学生的必修课程，也是许多非计算机专业学生了解和学习计算机的选修课。在高等院校中，不仅计算机专业，许多其他非计算机专业也开设这门课程。事实上，“算法与数据结构”已经成为学生了解和学习计算机的重要基础课。算法与数据结构是伴随着计算机应用的普及与深入而产生的一门课程。早期的电子计算机是为数值计算而发明和设计的。应用在诸如弹道计算、天气预报等领域。现在计算机的应用已经渗透到社会的各个领域，如信息处理、图像识别、人工智能和电子交易等。这些领域大部分都是非数值计算领域，例如图像，其本质是人的感觉器官对客观事物的反映。现在的计算机不仅可以表示图像，而且可以存储、传输甚至识别图像。算法与数据结构是研究现实世界中非数值计算问题的程序设计、信息的计算机表示、计算机操作对象以及它们之间的关系的学科。现实世界是缤纷复杂的，而计算机所能表示的只有0与1，其存储器也是线性的，中央处理器本质上也只能做有限位的加法运算。算法与数据结构就像是横架在现实世界和计算机世界之间的一座桥梁，是利用计算机解决实际问题不可缺少的工具。离散数学也是以非数值问题为研究对象。与之相比，算法与数据结构更注重于算法的实现，而离散数学偏重于算法的理论。1.1 利用计算机解决问题的几个步骤利用计算机解决问题可归纳为以下几个步骤：①分析实际的具体问题，从中抽象出一个适当的数学模型；②设计一个求解此数学模型的算法；③编制计算机程序实现此算法，最终得到解答。