导语：数据结构学习笔记（一）数据结构概论

1、数据结构是什么

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。记为：Data_Structure=（D，R）其中D是数据元素的集合，R是该集合中所有元素之间的关系的有限集合。

数据结构

　　一般认为，一个数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的算法才有意义。一个逻辑数据结构可以有多种存储结构，且各种存储结构会影响数据处理的效率。但数据结构底层存储方式其实只有两种：数组（顺序存储）和链表（链式存储）。

　　在各种类型的程序设计中，数据结构的选择是一个基本的考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重地依赖于是否选择了最优的数据结构。一般确定了数据结构后，算法就容易得到了。同样我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。这种思想导致了许多种软件设计方法和程序设计语言的出现，面向对象的程序设计语言就是其中之一。

2、数据结构的作用

　　首先，由于数据结构的重要性，许多高级程序设计语言，例如 java、C、Python等都可以但建议最好使用C语言运行编写代码。

（2）选择一两本数据结构的书，阅读第一遍时，建议从头到尾看，不要心急，开始可能进度慢一点，但如果你对前面的基础知识有足够了解，后面的学习会越来越容易随心应手，数据结构虽然抽象难懂，学习起来苦涩无味，但它逻辑性很强，一环扣一环，很有意思。

（3）阅读时，摘抄是很好的习惯，摘抄会减慢的你学习速度，除非你有超强的理解能力，一般来说，边阅读边摘抄的过程，也是大脑学习的过程，看了一遍，只是初步了解，但抄写一遍，更能好好消化阅读的内容。

（4）阅读完一个章节时，一定要把主要关键的内容列出来，然后根据关键内容，不用看书，也能把具体核心的相关算法写出来。阅读完一个章节后，一定要适当练习，通过习题集来检验自己是否真正理解书中的内容，最佳效果是把相关习题的算法，都认真运行一次，加强记忆，增强对数据结构的理解思维，特别是逻辑思维。

（5）数据结构与算法是紧密关联的，学习之后，尽量把相关知识应用到之后的编程与实际工作中去。其实我们所开发的任何项目中，都会运用到数据结构及算法，不管是底层的操作系统、数据库、单片机等，还是现在热门的人工智能，大数据分析与开发、边缘计算等，都离不开数据结构及算法的支持。

4、数据结构的种类

数据结构有很多种，如集合结构、线性结构，树状结构、图状结构等，一般来说，按照数据的逻辑结构对其进行简单的分类，包括线性结构和非线性结构（集合、树状和图状）两类。

数据结构的种类

(1)线性结构

简单地说，线性结构就是表中各个结点具有线性关系。如果从数据结构的语言来描述，线性结构应该包括如下几点：

1、线性结构是非空集。

2、线性结构有且仅有一个开始结点和一个终端结点。

3、线性结构所有结点都最多只有一个直接前驱结点和一个直接后继结点。

线性表就是典型的线性结构，还有队列，双队列，数组，串等都属于线性结构。

（2）非线性结构

简单地说，非线性结构就是表中各个结点之间具有多个对应关系。如果从数据结构的语言来描述，非线性结构应该包括如下几点：

1、非线性结构是非空集。

2、非线性结构的一个结点可能有多个直接前驱结点和多个直接后继结点。

在实际应用中，多维数组、广义表、树结构和图结构等数据结构都属于非线性结构。

五、数据结构的存储方式

数据结构在计算机内存中存储包括数据元素的存储和元素之间关系的表示。元素之间关系在计算机中有两种不同的表示方法，顺序表示和非顺序表示。因此得出两种不同的存储方式：顺序存储（数组）和链式存储（链表）。

（1）顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构关系。数据元素存放的地址是连续的。

一个数据元素插入之后，后面的元素都要向后移动

（2）链式存储结构：在每个数据元素中增加一个空间来存放另一个元素地址的指针，用该指针来表示 数据元素之间的逻辑结构关系。数据元素的存放地址是否连续不有要求。如下图，用一组地址任意的存储单元存放线性表中的数据元素：

线性表数据结构

所以散列表、栈、队列、堆、树、图都是上层建筑，而数组和链表才是「结构基础」。因为那些多样化的数据结构，其源头，都是在链表或者数组上的特殊操作而已。

比如说队列、栈这两种数据结构既可以使用链表也可以使用数组实现。用数组实现，就要处理扩容缩容的问题；用链表实现，没有这个问题，但需要更多的内存空间存储节点指针。

散列表就是通过散列函数把键映射到一个大数组里。而且对于解决散列冲突的方法，拉链法需要链表特性，操作简单，但需要额外的空间存储指针；线性探查法就需要数组特性，以便连续寻址，不需要指针的存储空间，但操作稍微复杂些。

树其实也是如此，用数组实现就是堆，因为堆是一个完全二叉树，用数组存储不需要节点指针，操作也比较简单；用链表实现就是很常见的那种树，因为不一定是完全二叉树，所以不适合用数组存储。为此，在这种链表树结构之上，又衍生出各种不同的设计，比如二叉搜索树、AVL 树、红黑树、区间树、B 树等等，以解决不同的问题。

图也是两种表示方法，邻接表就是链表，邻接矩阵就是二维数组。邻接矩阵判断连通性迅速，并可以进行矩阵运算解决一些问题，但是如果图比较稀疏的话，弱点很耗费空间。邻接表比较节省空间，但是很多操作的效率上肯定比不过邻接矩阵。

综上，数据结构种类很多，甚至你也可以发明自己的数据结构，但是底层存储无非数组或者链表，二者的优缺点如下：

数组由于是连续存储,可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。正因为连续存储，内存空间要求高，必须有足够的连续内存空间，而且内存空间必须一次性分配够，所以说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，容易浪费内存，时间复杂度 O(N)；而且你如果想在数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，操作效率低，时间复杂度 O(N)。

链表因为元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题，内存利用率高，不会浪费内存；如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度 O(1)。但是正因为存储空间不连续，你无法根据一个索引算出对应元素的地址，所以不能随机访问，必须从第一个开始遍历，查找效率低；而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间。

6、数据结构的基本操作

对于任何数据结构，其基本操作无非遍历 + 访问，再具体一点就是：增删查改。数据结构种类很多，但它们存在的目的都是在不同的应用场景，尽可能高效地增删查改。这就是它们的最基本工作。如何遍历 + 访问？从数据结构整体来看，各种数据结构的遍历 + 访问无非两种形式：线性的和非线性的。

线性形式是以for/while迭代为代表，非线性形式以递归为代表，具体的我们下一节继续学习。

【参考文献】数据结构(C语言版）、labuladong的算法小抄、大话数据结构

免责声明:本站部份内容由优秀作者和原创用户编辑投稿，本站仅提供存储服务，不拥有所有权,不承担法律责任。若涉嫌侵权/违法的，请反馈，一经查实立刻删除内容。本文内容由快快网络小迪创作整理编辑！