数据结构 - 线性表、栈、队列、串

男娘i 2022-05-10 02:08 326阅读 0赞

![70][]

作者：谭东

最近把之前学过的数据结构和算法部分都重新研究看完了，整理分享一下。

**前言感想：之前遇到有人说不要说重复的东西，网上都有了，书里都有这些概念了。我听到之后很诧异，很感叹这个人或者这些人可能没有真正的去学习或者学懂数据结构吧？数据结构是什么？用来干嘛的？逻辑原理意图是什么？其实很多东西不是一进来就要直接学习多么高难度高深的算法什么的，没有基础知识的支撑、没有真正的学懂其思维逻辑，你又能拓展提升多高呢？又如何去改进算法呢？当别人问你，确定有限自动机和不确定有限自动机是什么、文法分析和词法分析怎么个流程和原理、用到哪里的、最优二叉树会画吗、路径最短会求吗、有向图会画吗、KMP算法是啥呢、通过KMP算法你第一反应是什么？能想到这个算法可以再优化改进它的时间和空间存储的效率吗... ...**

**有的人又说了，你说的这些看看教材就行，书上网上、百度百科都能搜到。那哪些东西网络没有的呢？书上有：官方的话你看懂了吗、真正学会了吗？网上有：网上的你看懂了吗？同样的东西，能够讲透的好文章值得保存。不是复制与粘贴，不加思索。**

**       数据结构！=算法，这应该是两门课。数据结构是算法的基础，顾名思义，就是把一堆数据，按照需求进行一定结构化的存储或排列，方便使用、处理。可以从时间长短和空间存储占用两个方面来优化和评价这个数据结构的好坏。设计好了这个结构，我们可以根据这个逻辑进行算法的编写。**

我相信，通过这些数据结构基础的认真学习，你可以弄懂这是什么、怎么用、用到哪、怎么改进。基础很重要，真正的理解也很重要。标题列的这些点是大的点、里面有其他的东西的扩展。例如DFA？NFA？

**这里主要给大家讲解线性表及其两种存储结构、线性表两种存储结构的插入和删除运算、栈及其两种存储结构、队列及其两种存储结构、串及其存储结构等。**

**数据结构是程序设计的重要基础。学习数据结构要达到的目标就是学会从问题出发，分析和研究计算机加工的数据的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作方法，为提高利用计算机解决问题的效率服务。**

数据结构是指数据元素的集合及元素间的相互关系和构造方法。元素之间的相互关系是数据的逻辑结构，数据元素及元素之间关系的存储称为存储结构（或物理结构）。数据结构按照逻辑关系的不同分为线性结构和非线性结构两大类，其中，非线性结构又可分为树结构和图结构。

算法与数据结构密切相关，数据结构是算法设计的基础，设计合理的数据结构可使算法简单而高效。

好了，介绍说完了，我们言归正传。先介绍**线性表。**

说到线性表，它主要是具有线性结构的一种。具有单一前驱和后继的数据关系，也就是“一个接一个排列，有唯一的前驱元素和后继元素”。

线性表示最简单、最基本也是最常用的一种线性结构。**常采用顺序存储和链式存储，主要的基本操作是插入、删除和查找等。**

1、先看线性表定义：

一个线性表是n(n≥0)个元素的有限序列，记作（a1，a2，... ...，an）。（符号下标）。

主要特点是：

存在唯一的表头和表尾；

除表头外，表中每一个元素均只有唯一的直接前驱。如下图中a2元素的直接前驱就是a1；

除表尾外，表中每一个元素均只有唯一的直接后继。如下图中a2元素的直接后继就是a3。

![70 1][]

2、再来看下线性表的存储结构：分为**顺序存储和链式存储**。

先看**顺序存储结构：**

顺序存储结构是用一组地址连续的存储单元一次存储线性表中的数据元素，从而使得逻辑关系相邻的两个元素在物理位置上也相邻。优点：可随机存取表中的元素；缺点：插入和删除操作需要移动大量的元素。

举个例子：

如一个班组织去看电影，每个人都是按照电影院的座位顺序坐的。这样的存储结构就是顺序存储，这样的座位方式，我们就可以随机任意知道某个座位上是哪个同学；但是如果插入或者删除一个座位的话，依然要保持相邻按照顺序做的，如删除的话，那么就要把后面的座位的同学都要往前移动。如果插入一个的话，那么后续的座位就要一个一个往后移动。所以这就是顺序存储的优缺点。

**在使用的时候，可以根据实际需求评估使用顺序存储结构。（读取和更新快，插入和删除慢）**

**![70 2][]**

有一个公式，用来获取顺序存储结构的线性表的第i个元素ai的存储位置：

LOC(ai)=LOC(ai）+（i-1）\*L

其中，LOC(a1)是表中第一个元素的存储位置，L是表中每个元素的所占空间大小。

再看**链式存储：**

是指用结点来存储数据元素，结点的空间可以是连续的，也可以不连续。因此存储数据元素时必须存储元素之间的逻辑关系（也就是用指针）。结点空间只有在需要的时候才申请，无需事先分配。

**优点：插入和删除不需要移动元素，操作方便。**

**缺点：增加了存储空间开销，不能随机访问任一结点。**

最基本的结点结构：（数据域和指针域）

![70 3][]

举个例子：

![70 4][]

每个结点都有数据域和指针域，指针指向上一个元素或者下一个元素。这样的结构就是链式存储结构。优点就是插入和删除需要要移动元素，更改指针指向位置即可。不过增加了存储空间，因为既要存数据又要存指针。并且不可以随机访问数据，要从第一个查起，第一个访问指针指向下一个，这样遍历查询。

链式存储中，还有其他几种链表结构：

（1）双向链表：每个节点包含两个指针，指明直接前驱和直接后继元素，可以在两个方向上遍历链表。如图所示：

![70 5][]

（2）循环链表：表尾结点的指针指向表中的第一个结点，可以在任何位置上开始遍历整个链表。

![70 6][]

（3）静态链表：借助数组来描述线性表的链式存储结构。

在链式存储结构中，只需要一个指针（头指针）指向第一个结点，就可以顺序访问表中的任意一个元素。为了简化对链表状态的判定和处理，特别引入一个不存储数据元素的结点，称为头结点，将其作为链表的第一个结点并令头指针指向该节点。

那么之前的两个图就变成这样了。

![70 7][]

![70 8][]

3、线性表的插入和删除运算：

（1）基于顺序存储结构的运算

插入元素前要移动元素，以挪出空的存储单元，然后再插入元素；删除元素时同样需要移动元素，以填充被删除出来的存储单元。在等概率下平均移动元素的次数分别是：插入元素（n/2），删除元素（(n-1)/2）。

什么意思呢？举个例子：你去电影院，想座某个位置，是不是先要让这个座位和附近的人移动下，挪出这个位置后，你才可以入座呢？删除元素同理。

看下我画的这个图就理解了：

![70 9][]

![70 10][]

（2）基于链式存储结构的运算

在链式存储结构下进行插入和删除操作，其实质是对相关指针的修改。

先看下在单向链表中插入和删除的指针变化：

![70 11][]

![70 12][]

再看下双向链表插入和删除数据：

![70 13][]

![70 14][]

**4、接下来我们看下栈：**

栈是只能通过访问一端实现数据存储和检索的一种线性表，栈进行插入和删除操作的一端为栈顶，另一端为栈底。是先进先出（FILO）或后进先出（LIFO）的线性表。

栈的存储结构有顺序存储和链式存储。

顺序存储：一组连续第直存储单元一次存储自栈顶到栈底的数据元素，同时附设指针Top指示栈顶元素的位置，当一个元素入栈时，要判断是否栈满，如果栈满，则元素入栈会发生上溢现象。

链式存储：用链表作为存储结构，也称链栈。由于栈中元素只能在栈顶一段进行操作，因此不必设置头结点，链表的头指针就是栈顶指针。

**应用：表达式求值、括号匹配等，在计算机语言的实现以及将递归过程转变为非递归过程的处理中，栈有重要的作用。**

**5、接下来我们看下队列：**

队列是先进先出（FIFO）的线性表，它只允许在表的一端插入元素，另一端删除元素。允许插入元素的一端为队尾（Rear），允许删除元素的一端称为队头（Front）。

队列的存储结构有：顺序存储和链式存储。

顺序存储：是利用一组地址连续的存储单元存放队列中的元素。由于队列中元素的插入和删除限定在队列的两端进行，因此设置对头指针和队尾指针，分别指示当前队首元素和队尾元素。

链式存储：用链表表示的队列简称链队列。为便于操作，给链队列添加一个头结点，并令头指针指向头结点。队列为空判定条件：头指针和尾指针的值相同，且均指向头结点。

**应用：一般队列结构常用于处理需要排队的场合，如操作系统中处理打印任务的打印队列、离散事件的计算机模拟等。**

**6、接下来我们看下串：**

仅由字符构成的有限序列，是取值范围受限的线性表，一般记为S='a1a2...an'，其中S是串名，a1a2...an是串值。

（1）空串：长度为0的传，不包含任何字符；

（2）空格串：有一个或多个空格组成的串（有长度）；

（3）子串：由串中任意长度的连续字符构成的序列，含有子串的串成为主串，子串在主串中的位置指子串首次出现时，该子串的第一个字符在主串中的位置，空串是任意串的子串。

例如：主串：adbbcc；子串：cb；

（4）串相等：两个串长度相等且对应位置字符也相同；

（5）串比较：以字符ASCII码值作为比较依据，从两串第一个字符开始进行，字符ASCII码值大者所在的串为大，若其中一个串先结束，则串长较大者为大。

例如：cfdeg>cfd；cfdeg<cfed；

再来看串的存储结构：每个字符串最后要增加个串结束的标志\\0。

（1）串的顺序存储：是用一组地址连续的存储单元来存储串值的字符序列。由于串中的元素为字符，因此可通过程序语言提供的字符数组定义串的存储空间，也可以根据串长的需要动态申请字符串的空间。

（2）传的链式存储：当用链表存储串中的字符时，每个结点中可以存储一个字符，也可以存储多个字符，要考虑存储密度问题。在链式存储结构中，结点的大小的选择和顺序存储方法中数组空间大小的选择一样重要，它直接影响对串处理的效率。

举个例子：

![70 15][]

7、串的模式匹配：

子串的定位操作通常称为串的模式匹配，它是各种串处理系统中最重要的运算之一。子串也称为模式串。

（1）朴素的模式匹配算法：也称为布鲁特-福斯算法，基本思想是：从主串的第一个字符起与模式串的第一个字符比较，若相等，则继续逐个字符进行后续的比较，否则从主串的第二个字符起与模式串的第一个字符重新比较，直至模式串中的每个字符依次和主串中的一个连续的字符序列相等，则称匹配成功，否则称匹配失败。

（2）改进的模式匹配算法：改进的模式匹配算法又称为KMP算法，其改进之处在于：每当匹配过程中出现相比较的字符不相等时，不需要回溯主串的指针，而是利用已经得到的“部分匹配”的结果，将模式串向后“滑动”尽可能远的距离，再继续进行比较。

8、总结：

上自己手写的笔记。

![70 16][]

![70 17][]

课本资料：

![70 18][]

数据结构图：

![70 19][]

![70 20][]

之前大学学的是这本教材，推荐下。

![70 21][]

参考文献：

\[1\]严蔚敏，吴伟民.数据结构\[M\].北京：清华大学出版社，2011.

[70]: /images/20220510/da310327fca34b95b59e9577d625562e.png
[70 1]: /images/20220510/9cc12ba4b7844d23a1b485eaeaeb4bf6.png
[70 2]: /images/20220510/110d62194fbd4fafb5b2e9f0ab8f8dbb.png
[70 3]: /images/20220510/98fed43fdc734ea1abdb2a17e3102db4.png
[70 4]: /images/20220510/7ce42899a041474b807b82ed9a58b192.png
[70 5]: /images/20220510/682c192a37df4083ac95341b3b81e6a0.png
[70 6]: /images/20220510/61acef0f6c804defa8d972d98f7f5d02.png
[70 7]: /images/20220510/21f46ef3484a40b99df1ad022acfbe6d.png
[70 8]: /images/20220510/f7818acc50964642a401146783250b0c.png
[70 9]: /images/20220510/b5a84ecfca1b4d7bb6ffd4cf89f12644.png
[70 10]: /images/20220510/83980a004fe2489cb843323e49b9eb23.png
[70 11]: /images/20220510/9795e8fc08ae45f2acc316ec6e3fc2c2.png
[70 12]: /images/20220510/ab25b201e05b4e6fa30c067a8b4687fd.png
[70 13]: /images/20220510/401b14e15acc4cd1b89d5f4102fa7245.png
[70 14]: /images/20220510/d5dfe6cf6f944174bae80f314690371e.png
[70 15]: /images/20220510/2d614533d41d425abb0400ba33c39927.png
[70 16]: /images/20220510/de47c4a6a624407d99b72bb38e6bcfeb.png
[70 17]: /images/20220510/3548e28cd36f498cba054ad8e3ca528c.png
[70 18]: /images/20220510/dbfa826791024af4a0a619b0e08b0b12.png
[70 19]: /images/20220510/537710b13ae0479cadc2d0638d944f2f.png
[70 20]: /images/20220510/edb11abddfd84b3ca89f966ffe39c5db.png
[70 21]: /images/20220510/effe7df957314e1a9ed300fcc9b21de4.png