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