国二计算机考试线性表、栈、队列、串知识点思维导图
简单介绍国二计算机考试线性表、栈、队列、串知识点内容
树图思维导图提供 国二计算机考试线性表、栈、队列、串知识点思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 国二计算机考试线性表、栈、队列、串知识点思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：3ea41bff48a3f7037152162c766417ad
思维导图大纲
线性表、栈、队列、串思维导图模板大纲
递归算法时间复杂度
T(n)=aT(n/b)+f(n)
比较n^(log b a)和f(n)的阶数
若不相等，取大的
若相等，*log2n
T（n）=T(n-1)+T(n-2)
时间复杂度为2^n
线性表
顺序表
注意分配的是地址连续的存储单元
数组中元素下标从0开始，线性表元素位序从1开始
插入操作，范围为[1,n+1]，在i处插入就是把i和后面的元素都向后移动
链表
小tip：经常考察单循环链表表尾元素删除较为困难，哪怕有尾指针，为了删除后尾指针还能指向链表尾，很困难
分类
双链表
循环链表
循环单链表
循环双链表
静态链表
使用数组存储，预先分配连续空间，数组指针域指向像一个元素数组下标
单链表
建立单链表
头插法
尾插法
栈
分类
链栈
一般没有头结点，top直接指向栈顶元素
只有表头没有表尾指针的单向循环链表非常不适合作为链栈
共享栈
top1-top0=1,栈满
使用共享栈的好处是节省存储空间，降低发生上溢的可能
顺序栈
初始时S.top=-1;栈空：S.top=-1;栈满S.top=maxsize-1
乱七八糟
n个元素进栈，出栈的元素排列为Cn,2n/n+1
删除栈底元素不是栈的基本操作
PUSH：进栈；POP：出栈
栈的应用
括号匹配、递归调用
表达式求值
队列
分类
链队
头指针指向队头结点，尾指针指向队尾结点
双端队列
输入受限的双端队列
一端可以插入删除，另一端只能删除
默认：全部输入之后再输出（真题有限制，垃圾王道没说限制）
输出受限的双端队列
一端可以插入删除，另一端只能插入
循环队列
记住一点，rear只加不减，front只减不加，rear跑在front前面
队列的应用
树的层次遍历
图的广度优先遍历
矩阵
对称、三角、三对角
行优先、列优先
稀疏矩阵
使用三元组：（行，列，值）
压缩存储的数组下标一定从0开始
串
概念
S='abc123'
子串、串长
模式匹配
KMP算法
next数组
从-1，0开始，表示正确的关系
从0，1开始（整体+1）方便移位比较
考研时数组下标从0开始
乱七八糟
特点：模式匹配时指示主串的指针不会变小
简单算法O（mn）；KMP算法O（m+n）
前缀、后缀不能包含整个字符串
nxet数组值是前一个字母的最长相等前后缀的值
比较失败，下次还从当前位置进行比较（2019）
相关思维导图模板
树图思维导图提供 抓住重点 在线思维导图免费制作，点击“编辑”按钮，可对 抓住重点 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：4c49e4799ddf94a339c56e46eb96a826
树图思维导图提供 数智技术在工程设备管理中的应用 在线思维导图免费制作，点击“编辑”按钮，可对 数智技术在工程设备管理中的应用 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：f9a2de84ad9a9ceebc96385d71be9ebe
沪公网安备 31011502019485号
上海工商