3.1、数据结构-线性表

数据结构

数据结构该章节非常重要，上午每年都会考10-12分选择题+下午一个大题

什么叫数据结构？我们首先来理解一下什么叫程序，程序就是数据结构+算法。由数据结构和算法就可以来组成我们的各种程序，比如说你的手机的点外卖程序，打车程序，这些程序底层就是由这两部分来组成的。
那数据结构又包含了两层的意义，一层叫数据，一层叫结构。
所谓的数据就是通过数据库那一章来专门来进行讲解，通过SQL语句来操作各种数据库，以及现在的大数据，数据存储，数据挖掘，数据分析。
结构是什么意思？是指我们的数据在内存或CPU中，在我们的程序使用过程中，它是以什么样的结构而存在的，这就我们所谓的数据结构。所以我们本章节的特点是在结构这两个字，而不是在数据两个字上。
那么结构呢，它又分成了很多种。比如说线性结构（线性结构有线性表，有站和队列，还有串）、数组、矩阵结构和广义表、树结构、图结构。这就是说我们的重点，都是数据存储的一个一个的结构。
我们的数据放在这个结构里面，我们怎么来对这些数据进行查找以及我们怎么来对这些数据来进行一个升序或者降序的一个排列，这就是我们所谓的一个算法。

线性结构

线性表

线性结构：每个元素最多只有一个出度和一个入度，表现为一条线状。线性表按存储方式分为顺序表和链表。
看下图：顺序表里2和3是线性结构中的两个元素，那么每一个元素是不是只有前面一个元素指向它，那么这个前面一个元素指向它的我们把给称之为入度。然后它再指向下一个元素代表出度。所以我们的首元素是只有出度没有入度，我们的尾元素只有入度没有出度。

顺序表的每一个元素与另一个元素之间紧紧贴在一起。注意：贴在一起不仅仅是我们看上去贴在一起，实际在内存中的存储也是紧密的挨在一起的
链表结构有三种方式：单链表、循环链表、双向链表

• 单链表
  每个元素都有两个部分组成，其中一个区域存放数据，另外一个区域存放下一个元素的地址。
  它只能从首元素->尾元素走下去。
• 双向链表
  由三个部分组成，一部分存放上一个元素的地址，一个存放数据，还有一个存放下一个元素的地址。
  可以从首元素->尾元素走，也可以从尾元素->首元素走。
  它是可以双向进行的，查询效率比单链表快上一倍。
  首节点的上一个元素地址为NULL，尾结点的下一个元素地址是NULL
• 循环链表：首节点的上一个节点指向尾结点，尾结点的下一个节点指向首节点。形成一个闭环，这个闭环就叫循环链表

顺序列表由于元素与元素之间是相邻的，我们可以直接从首元素来查到每个元素的位置。但是链表这里存储一个原来，那里存储一个元素，然后通过地址的形式进行一个强关联，这样会浪费一些空间用来存储地址，所以它的利用率没有顺序列表高。

存储结构：

• 顺序存储：用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的元素物理上也相邻。
  • 每一个元素与元素之间是直接相邻的并且紧紧的相邻进行一个存储的
  • 我们的头元素是没有入度，尾元素没有出度
• 链式存储：存储各数据元素的结点的地址并不要求是连续的，数据元素逻辑上相邻，物理上分开。

顺序存储和链式存储区别

在空间方面，因为链表还需要存储指针，因此有空间浪费存在。

在时间方面，由顺序表和链表的存储方式可知，当需要对元素进行破坏性操作（插入、删除）时，链表效率更高，因为其只需要修改指针指向即可，而顺序表因为地址是连续的，当删除或插入一个元素后，后面的其他节点位置都需要变动。

而当需要对元素进行不改变结构操作时（读取、查找），顺序表效率更高，因为其物理地址是连续的，如同数组一般，只需按索引号就可快速定位，而链表需要从头节点开始，一个个的查找下去。

单链表的插入和删除

• (a)在单链表中插入节点：在a和b中间插入一个c
  1）先创建c
  2）将c的下一个元素地址指向b
  3）把a下一个元素地址指向b的断开改为指向c
• (b) 在单链表中删除节点：删除b
  断开b的下一个元素地址c，断开a的下一个元素地址b并指向c

在上图中p所指向的节点后插入s所指向的节点，操作为：

s->next=p->next,
p->next=s;

同理，在单链表中删除p所指向节点的后继节点q时，操作为：

free(p);
p->next=p->next->next;

练习题

〖2014年〗对于线庄表，相对于顺序存储，采用链表存储的缺点是（）。
A.数据元素之间的关系需要占用存储空间，导致存储密度不高
B.表中结点必须占用地址连续的存储单元，存储密度不高
C.插入新元素时需要遍历整个链表，运算的时间效率不高
D.删除元素时需要遍历整个链表，运算的时间效率不高

答案：A

栈和队列

队列、栈也是线性结构，结构如下图，队列是先进先出，分队头和队尾；栈是先进后出，只有栈顶能进出。

队列：FIFO（先进先出），比如：水管，先进去的水滴先出来
栈：FILO（先进后出），比如：枪的弹夹，先放进去的子弹最后才能出来

循环队列中，头指针指向第一个元素，尾指针指向最后一个元素的下一个位置，因此，当队列空时，head=tail,当队列满时，head=tail,这样就无法区分了。
因此，一般将队列少存一个元素，这样，队列满时的条件就变为tail+1=head，而考虑是循环队列，必须要除以最大元素数来取余数，即(tail+1)%size=head,如上图右边所示两个公式。循环队列的长度公式为(Q.tail-Q.head)%size。

优先队列：元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。使用堆来存储因为其不是按照元素讲队列的顺序来决定的。

练习题

【2014年】某双端队列如下图所示,要求元素进出队列必须在同一端口,即从A端进入的元素必须从A端出、从B端进入的元素必须从B端出,则对于4个元素的序列e1、e2、e3、e4,若要求前2个元素(e1、e2)从A端口按次序全部进入队列,后两个元素(e3、e4)从B端口按次序全部进入队列,则可能得到的出队序列是()

A. e1、e2、e3、e4
B. e2、e3、e4、e1
C. e3、e4、e1、e2
D. e4、e3、e2、e1

答案：D
只要找到e2>e1,e4>e3的

【2021年】设有栈S和队列Q初始状态为空,数据元素序列a,b,c,d,e,f依次通过栈S,且多个元素从S出栈后立即进入队列Q,若出队的序列是b,d,f,e,c,a,则S中的元素最多时,栈底到栈顶的元素依次为()。
A、a,b,c
B、a,c,d
C、a,c,e,f
D、a,d,f,e

答案C

串（了解）

字符串是一种特殊的线性表,其数据元素都为字符。

• 空串:长度为0的字符串,没有任何字符。
• 空格串:由一个或多个空格组成的串,空格是空白字符,占一个字符长度。
• 子串:串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串,空串是任意串的子串。
  例如：abcdef为主串，abf是子串

学过编程的应该见过indexOf函数：python,javascript等都有，是用来查找子串位置的。以下就是查找的相关算法（很复杂，花大量时间学习不划算，了解即可）

• 串的模式匹配算法:子串的定位操作,用于查找子串在主串中第一次出现的位置的算法。
• 基本的模式匹配算法:也称为布鲁特一福斯算法,其基本思想是从主串的第1个字符起与模式串的第1个字符比较,若相等,则继续逐个字符进行后续的比较;否则从主串中的第2个字符起与模式串的第1个字符重新比较,直至模式串中每个字符依次和主串中的一个连续的字符序列相等时为止,此时称为匹配成功,否则称为匹配失败。
• KMP算法:对基本模式匹配算法的改进,其改进之处在于:每当匹配过程中出现相比较的字符不相
  等时,不需要回溯主串的字符位置指针,而是利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的距离,再继续进行比较。