数据结构

章节摘录

　　第1章 数据结构概述　　对于一个有志于从事IT专业技术的人士来说，数据结构（Data Structure）是一门与计算机软件和硬件都密切相关的学科，其中包含了算法（Algorithm）、数据存储结构、排序、搜索、哈希函数与程序设计等概念。　　1.1　数据结构简介　　数据结构可以看成是在数据处理过程中用于分析、组织数据的方法和操作逻辑，它主要关注数据间的特性与相互关系。　　在现代社会中，计算机与信息紧密相关，由于计算机具有处理速度快与存储容量大的两大特点（如图1.1所示），因此在数据处理的过程中具有举足轻重的作用。　　数据结构是用计算机进行数据处理的一套完整逻辑。程序设计者必须选择一种数据结构来进行数据的增加、修改、删除、保存等操作，如果在选择数据结构时作了错误的决定，程序的执行速度可能变得非常低，如果选错了数据类型，后果更是不堪设想。　　因此当用计算机解决问题时，必须以计算机所能接受的模式来认识问题，并设计适当的算法去处理数据，这是数据结构讨论的重点。简单地说，数据结构就是对数据与算法结构的研究。　　1.1.1　数据与信息　　谈到数据结构，首先必须了解什么是数据（Data）与信息（Information）。从字义上来看，数据是指未经加工过的文字（Word）、数字（Number）、符号（Symbol）或图形（Graph）等，它表达的是没有什么利用价值的基本元素或对象，例如姓名、课程表、通信录等都可泛泛地称为“数据”（Data）。　　当数据经过处理（Process），例如以特定的方式进行系统地整理、归纳甚至统计分析后就成为信息（Information）。而这样处理的过程就称为“数据处理”（Data Processing）。　　从严谨的角度来形容“数据处理”就是用人力或机器设备对数据进行系统的整理，如记录、排序、合并、整合、计算、统计等，以使原始的数据符合需求而成为有用的信息。数据处理过程如图1.2所示。　　有的读者可能会有疑问：“数据和信息的角色是否绝对一成不变呢？”这也不一定，同一份文件可能在某种状况下为数据，而在另一种状况下则为信息。例如美伊战争的某战役死伤人数报告，对你我这样的平民百姓而言，可能只是一份“数据”，不过对于英美联军的指挥官而言可就是弥足珍贵的“信息”。　　1.1.2　算法　　数据结构与算法是程序设计的核心。程序能否快速而有效地完成预定的任务取决于数据结构，而程序是否能清楚而正确地把问题解决则取决于算法，所以可以这么认为：“数据结构+算法=可执行的程序”，如图1.3所示。　　在韦氏辞典中算法被定义为：“在有限步骤内解决数学问题的程序。”如果用在计算机领域中，也可以把算法定义成：“为了解决某一个工作或问题所需要有限数目的机械性或重复性指令与计算步骤”。　　在日常生活中有许多工作都可以利用算法来描述，例如员工的工作报告、宠物的饲养过程、学生的功课表等。　　当了解了算法的定义后，需要说明计算机算法所必须符合的5个特性，如图1.4所示。以上5个特性的说明如表1.1所示。　　接下来要考虑的是如何描述一个算法。其实算法描述的主要目的是让人们了解算法的流程与步骤，只要能清楚地表现算法的5项特性即可。常用的算法描述如下。　　1.一般文字　　一般文字采用中文、英文、数字等进行描述。文字叙述法的特色在于使用文字或语言叙述来说明演算步骤。图1.5就是一名学生小华早上上学并买早餐的简单文字算法。

书籍目录

第1章 数据结构概述1.1 数据结构简介1.1.1 数据与信息1.1.2 算法1.2 程序设计简介1.2.1 程序开发流程1.2.2 结构化程序设计1.2.3 面向对象程序设计1.2.4 数据类型1.3 面向对象的概念与C++语言1.3.1 C++语言1.3.2 类1.3.3 继承1.3.4 多态1.4 算法效率的分析1.4.1 大O1.4.2 大Q1.4.3 大θ重点整理本章习题第2章 数组和稀疏矩阵2.1 线性表2.1.1 线性表的定义2.1.2 线性表的应用2.2 数组简介2.2.1 一维数组2.2.2 二维数组2.2.3 三维数组2.2.4 n维数组2.3 矩阵简介与运算2.3.1 矩阵相加2.3.2 矩阵相乘2.3.3 转置矩阵2.3.4 稀疏矩阵2.3.5 上三角形矩阵2.3.6 下三角形矩阵2.3.7 带状矩阵2.4 数组与多项式2.4.1 多项式简介2.4.2 多项式的加法重点整理本章习题第3章 链表3.1 指针简介3.1.1 指针声明3.1.2 动态内存分配3.1.3 C++语言中的动态分配与释放3.2 单链表3.2.1 单链表的建立3.2.2 单链表的结点删除3.2.3 单链表的结点插入3.2.4 单链表的反转3.2.5 单链表的连接3.2.6 多项式的表示法3.3 循环链表3.3.1 循环链表的定义3.3.2 循环链表的结点插入3.3.3 循环链表的结点删除3.3.4 循环链表的连接3.3.5 循环链表与稀疏矩阵的表示法3.4 双向链表3.4.1 双向链表的定义3.4.2 双向链表的结点插入3.4.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 后序表示法求值4.4 中序表达式转换成前序和后序表达式4.4.1 二叉树法4.4.2 括号法4.4.3 堆栈法4.5 前序和后序表达式转换成中序表达式4.5.1 括号法4.5.2 堆栈法重点整理本章习题第5章 队列5.1 队列简介5.1.1 队列的基本操作5.1.2 队列的数组实现5.1.3 队列的链表实现5.2 队列的应用5.2.1 循环队列5.2.2 优先队列5.2.3 双向队列重点整理本章习题第6章 树6.1 树简介6.2 二叉树简介6.2.1 二叉树的定义6.2.2 特殊二叉树的介绍6.3 二叉树的存储方式6.3.1 二叉树的数组表示法6.3.2 二叉树的链表表示法6.4 二叉树的遍历6.4.1 中序遍历6.4.2 前序遍历6.4.3 后序遍历6.4.4 二叉树的遍历实例6.4.5 二元运算树6.5 二叉树的深入研究6.5.1 排序二叉树6.5.2 线索二叉树6.5.3 索引二叉树6.6 树的二叉树表示法6.6.1 树转换成二叉树6.6.2 二叉树转换成树6.6.3 森林转换成二叉树6.6.4 二叉树转换成森林6.6.5 树与森林的遍历6.6.6 确定惟一二叉树重点整理本章习题第7章 图7.1 图的简介7.1.1 图的起源7.1.2 图的名词术语7.2 图的表示法7.2.1 邻接矩阵法7.2.2 邻接表法7.2.3 多重邻接链表法7.2.4 标记法7.3 图的遍历7.3.1 深度优先法7.3.2 广度优先法7.4 生成树7.5 最小生成树7.5.1 Prim算法7.5.2 Kruskal算法7.6 图的最短路径7.6.1 单点对全部顶点的最短路径7.6.2 顶点之间的最短路径7.7 AOV网络与拓扑排序7.7.1 拓扑排序7.7.2 AOE网络重点整理本章习题第8章 排序8.1 排序简介8.1.1 排序的分类8.1.2 排序算法的分析8.2 内部排序法8.2.1 冒泡排序法8.2.2 选择排序法8.2.3 插入排序法8.2.4 希尔排序法8.2.5 合并排序法8.2.6 快速排序法8.2.7 堆排序法8.2.8 基数排序法8.3 外部排序法8.3.1 直接合并排序法8.3.2 K-路合并法8.3.3 多相合并法重点整理本章习题第9章 查找9.1 查找简介9.2 常见的查找方法9.2.1 顺序查找法9.2.2 二分查找法9.2.3 插值查找法9.2.4 斐波纳契查找法9.2.5 哈希查找法重点整理本章习题

编辑推荐

　　《数据结构（C++版）》将各种数据结构的重要理论、算法作最详实的诠释，大量的图解说明降低学习难度，完整的范例程序将理论加以实践。书中所有的算法均以C++程序语言描述，藉此加深学习理解，促进学用结合，提高软件开发能力。全书共9章，内容包括数据结构概述、数组和稀疏矩阵、链表、堆栈、队列、树、图、排序、查找。

作者简介

《数据结构(C++版)》通过架构清晰和易懂的表达方式将数据结构中各种算法作最详尽的诠释与举例，并利用完整的C++程序设计将各种理论加以实践。 

全书共9章，包括数据结构概述、数组和稀疏矩阵、链表、堆栈、队列、树、图、排序、查找。为了将算法讲解的清晰易懂，《数据结构(C++版)》不尽以伪代码来说明，而是利用C++语言来展现，同时，书中的重要理论均辅以范例程序，从而透彻理解原理的精髓。为了验收各章的学习成果，章后附加重点整理和习题，提供更多实战演练的机会。

图书封面

---

 数据结构下载

---