数据结构的基本知识(数据结构基础知识大全)

导语：「第11节」数据结构的基础知识

我们从前面学习算法的过程中已经知道，程序是由算法和数据结构2部分组成的。可见，数据结构在程序中的重要性。所以，承接前面我们学到的算法知识，本节我给大家讲一讲数据结构方面的基础知识，这样大家能够对程序有更深的理解和领悟。

（一）什么是数据结构？

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合以及集合中数据元素之间的关系组成。它是计算机存储、组织数据的方式。精心选择的数据结构可以带来更高的运行或者存储效率。

数据结构分成逻辑结构、存储结构（物理结构）以及数据的运算。

其中，逻辑结构用来反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后关系，而与他们在计算机中的存储位置无关。

其中，数据的存储结构又称为物理结构。它是数据结构的实现形式，是数据的逻辑结构在计算机存储空间的存放形式。存储结构又分为顺序存储结构和链式存储结构2种。

顺序存储结构是把数据元素存放在地址连续的存储单元里，元素间的逻辑关系由存储单元的邻接关系来体现，比如，数组就是一种典型的顺序存储结构。链式存储结构不要求逻辑上相邻的元素在物理位置上也相邻，它可以把数据存放在内存的任意存储单元里。

（二）数据结构与算法存在什么样的关系？

前面我们提到，一个程序是由数据结构和算法2部分组成的。那么，数据结构和算法也是密不可分、缺一不可的。研究数据结构和算法之间的关系对于我们学习编程是大有裨益的！

1、算法的设计取决于数据的逻辑结构，而算法的实现依赖于采用的存储结构，其围绕数据结构操作。2、数据结构是底层，算法则处于高层，数据结构负责为算法提供服务。3、算法的目的也要为数据结构服务，比如，数据结构通常伴随有查找算法、递推算法、排序算法等等。4、数据结构往往与高效的检索算法、索引技术有关，其优劣性是在实现数据运算的算法中体现的。

网上有人用一张图将数据结构和算法间的关系展现了出来，如下所示：

（三）几种常见的数据结构解析

常见的重要数据结构有栈、树、堆、队列等等，下面我来一一分析。

1、栈

栈，是限定访问、插入、删除其中元素只能在栈尾（栈顶）进行的一种特殊线性表。线性表属于最简单的一种数据结构，是由n个相同数据类型的元素组成的有限序列，所以，在这里不多讲述。

对应于数据存储结构的2种形式，栈也有顺序栈和链栈2种。

顺序栈，又称栈的顺序存储结构，它是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，设定指针top指示栈顶元素的当前所处位置。链栈，又称栈的链式存储结构，链表的第1个元素是栈顶元素，链表的末尾是栈底结点，链表的头指针是栈顶指针，栈顶指针为空称为空栈。

2、队列

队列和栈类似，也是一种特殊的线性表。它规定只允许在一端插入，却在另一端删除。允许删除的那一端称为队首，允许插入运算的另一端称为队尾。通常称队列的元素的插入为进队，队尾的元素的删除为出队。

同样的，可以用顺序存储线性结构来表示队列，也可以用链式存储结构表示队列。

特别地，队列中还有中特殊的形式，称为优先级队列。优先级队列，每次出队（即删除元素）的都是最高优先级的元素，而并不一定是队首的元素。

3、树

树是由一个或多个节点组成的有限集T，它满足以下2个条件：有一个特定的节点称为根节点；其余的节点分成m个互不相交的有限集T1、T2、T3、…、Tm，其中每个集叉都是一棵树，称T1、T2、T3、…、Tm为根节点的子树。

一个节点的子树数目称为该节点的度。树中各节点的度的最大值称作树的度。树中节点的最大层次则是树的深度。

树的遍历：按照某种特定次序不遗漏、不重复地访问树中每一个节点元素的过程。按照访问次序分类，主要有前序遍历、后序遍历以及层序遍历3种。

其中，前序遍历，是先访问当前节点，再访问当前节点的左子树，最后访问当前节点的右子树，依次类推。其中，后序遍历，是先访问当前节点的左子树，再访问当前节点的右子树，最后访问当前节点，依次类推。其中，层序遍历，是先访问根节点，再从左向右访问根节点的子节点，然后从左向右访问根节点的孙子节点，依次类推。

4、二叉树

二叉树可以称为是一种特殊的树，但它与普通的树有着很大的区别是：①二叉树的节点子树要区分指出左子树和右子树，而树没有这样的规定。②二叉树的节点最大度是2，而树则可以大于2。

二叉树也有以下几种特殊种类：

①满二叉树：二叉树上每一层节点数目达到最大值。②二叉查找树：即二叉排序树，左子树的值都小于根节点的值，而右子树的值都大于根节点的值，同时左、右子树都是查找树。③平衡二叉树：属于二叉查找树中的分支，要求任何一个节点的左右子树的高度差都不大于1。④完全二叉树：除了最外层，其余层上的节点数目都达到最大值，而第n层上的节点集中存放在左子树中。

二叉树的遍历方法同树。

5、堆

堆属于一种特殊的线性表，它是一颗完全二叉树，其每个节点元素值都大于或等于左右子节点的元素值。

堆与二叉树的明显区别是：堆是线性的，而二叉树是非线性数据结构！

堆的典型应用案例就是堆排序，这是一种排序算法。堆排序首先要根据待排序记录的关键字建立初始堆，方法是：将待排序的关键字按层序遍历方式分放到一棵完全二叉树的各个节点中，所有i>[n/2]的节点Ki都没有子节点，以这样的Ki为根的子树已经是堆，因此初始堆可从完全二叉树的第（i=[n/2]）个节点开始，通过调整，逐步使以K[n/2]、K[n/2]-1、…、K2、K1为根的子树满足堆的定义。

好了，本节到此结束！

本文内容由小里整理编辑！