【DAY05 软考中级备考笔记】线性表，栈和队列，串数组矩阵和广义表

线性表，栈和队列，串数组矩阵和广义表 2月28日 – 天气：阴转晴

时隔好几天没有学习了，今天补上。明天发工资，开心😄

1. 线性表

1.1 线性表的结构

首先线性表的结构分为物理结构和逻辑结构

• 物理结构按照实现不同可以分为
  • 顺序表
  • 链表：单链表，循环列表和双向链表
• 逻辑结构：在存储中，除了第一个元素和最后一个元素，每一个元素只有一个直接前驱和直接后继。对于第一个元素来说，只有一个直接后继。对于最后一个元素来说，只有一个直接前驱。

这里可以理解为链表和数组的区别。

1.2 线性表的定义

1.3 线性表的插入和删除操作

• 首先对于顺序存储来说，基本上插入和删除操作都是需要移动元素的。除非在最后一个元素之后插入元素，或者删除最后一个元素。因此更适合读取操作频繁的数据。
• 对于链表而言，插入和删除操作不需要进行元素的移动。因此更适合写入比较频繁的数据

下面对于三种不同的链表的插入删除的操作进行详解

• 单链表的插入

p->next=q->next; 
q->next=p;

• 单链表的删除

p=pre->next;
pre->next=p->next;

或者

pre->next = pre->next->next;

• 双链表的插入

node->next = p->next;
node->pre = p;
p->next->pre = node;
p->next = node;

• 双链表的删除

p->next = deleteNode->next;
deletNode->next->pre = = p;

2. 栈和队列

2.1 栈

栈是一种特殊的线性表，只允许在一端进行插入和删除

使用栈来进行括号匹配的方法：https://zhuanlan.zhihu.com/p/134675879

2.2 队列

也是一种特殊的线性表，只允许在一端进行插入，在另一端进行删除

其中比较复杂的队列是循环队列

这里重点是记住循环队列队满和队空的条件。

例题的解题方法为带入排除法

3. 串

串是由有限个字符构成的有限序列，是取值范围受限的线性表。如串S="a1a2a3a4"，其中S为串名，a1a2a3a4为串值。

除此之外，还有一些其他的概念也需要掌握：

• 空串：长度为零的串，不包含任何字符
• 空哥串：包含一个或多个空格组成的串
• 子串：由串中任意长度的连续字符构成的序列成为子串。含有子串的字符串成为主串。子串在主串中的位置指的是子串首次出现主串时，该子串第一个字符在主串中的位置。

空串时任意串的子串

• 串相等：两个串长度相等且对应位置上的字符也相等。
• 串比较：两个串比较比较多是对应位置上ASCII码值的大小。如果比较到最后，一个串已经结束，则按照串长度长度为大。

比较著名的KPM算法就是字符串模式匹配算法

4. 数组

数组已经很熟悉了，就不再赘述。这里需要注意的概念是数组存储是的两种模式：

• 行优先：一行一行的存储，先存储完第一行，再存储第二行
• 列优先：一列一列的存储，先存储完第一列，然后再存储第二列

上述存储方式是针对二维数组

例题答案：
$$a+(2\ast 5+3)\ast 2$$

5. 稀疏矩阵

稀疏矩阵中大部分只有上三角或者下三角的位置中存储元素，其余位置均为0，因为为了优化存储空间，可以使用一维数组进行存储。

对于稀疏矩阵中元素在一维数组中的对应关系的公式没有必要记，考试的时候直接带入计算即可。

解题思路：首先拿A(0,0)来试一试，A(0,0)应该存储在M[0]中，因此把i=0,j=0，带入到下面中，可以得到的是A，C正确

然后拿A(1,1)来试一试，A(1,1)应该存储在M[3]中,因此把i=1,j=1，带入到下面中，可以得到的是A正确

6. 广义表

广义表是线性表的一个推广，广义表中最重要的两个概念是

• 广义表的长度：最外层包含的元素个数
• 广义表的深度：括号嵌套的深度

• 广义表规定，空表{}的长度为0
• 若广义表中只有一个原子，则深度为0。其实，每次递归返回的值都是当前所在的子表的深度，原子默认深度为 0，空表默认深度为 1。
• 广义表中，第一个元素成为表头，其余元素均是表尾。

相关链接

• https://blog.csdn.net/Aaron_Kings/article/details/102999255
• https://blog.csdn.net/qq_37717494/article/details/105074513