【DAY07 软考中级备考笔记】数据结构：线性结构，数组矩阵和广义表

数据结构：线性结构，数组矩阵和广义表 3月2日 – 天气：晴

1. 线性表的定义和存储方式

> 这一部分只需要掌握下面的两点即可： > > * 采用顺序存储和链式存储的特点 > * 单链表的插入和删除操作

2. 栈和队列

> 这里需要注意的是循环队列中的判断队列为空和为满的条件 > > * 其中需要注意的是当队列为满的时候，实际上仍然存在一个存储位置为空

针对栈的两道例题：

第二道题涉及到了如何利用栈对算数表达式进行求解，这里需要注意一下求解的过程

3. 串

这一部分的重点主要是了解串中的一些概念的定义，可以根据不同的串判断其所属的类型。当然还有字符串匹配算法KMP，主要需要知道如何求next数组。

4. 数组

这一部分主要是了解数组的不同存储形式，如何计算制定元素在数组中的存储位置。

5. 矩阵

这一部分的主要内容就是介绍如何利用一维数组存储一些比较特殊的二维矩阵。里面涉及到的公式比较多，不需要死记硬背。解题的时候只需要带入特殊值，利用排除法求解即可。

6. 广义表

这里需要注意两点：

• 广义表和线性表的区别主要是：线性表中的元素都是不可以再分的单元素，而广义表中的元素既可以是单元素，也可以是一个线性表
• 广义表的重数：左括号或者右括号的数量