简单介绍线性表、栈、队列、串的内容
树图思维导图提供 计算机考试知识线性表、栈、队列、串思维导图 在线思维导图免费制作,点击“编辑”按钮,可对 计算机考试知识线性表、栈、队列、串思维导图 进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:d37a0ed5d5f8749a1c3da9264865c550
线性表、栈、队列、串思维导图模板大纲
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)
树图思维导图提供 BI大数据课程 在线思维导图免费制作,点击“编辑”按钮,可对 BI大数据课程 进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:507bb5b47558c8c0e5c1493d505c4a10
树图思维导图提供 计算机辅助电子线路设计 在线思维导图免费制作,点击“编辑”按钮,可对 计算机辅助电子线路设计 进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:6ca7534122e478b7cd1b28b3c72601e8