TreeMind树图在线AI思维导图
当前位置:树图思维导图模板资格考试计算机计算机理论知识线性表、栈、队列、串思维导图

计算机理论知识线性表、栈、队列、串思维导图

  收藏
  分享
免费下载
免费使用文件
U517027942 浏览量:12022-11-07 14:00:34
已被使用0次
查看详情计算机理论知识线性表、栈、队列、串思维导图

简单介绍线性表、栈、队列、串内容

树图思维导图提供 计算机理论知识线性表、栈、队列、串思维导图 在线思维导图免费制作,点击“编辑”按钮,可对 计算机理论知识线性表、栈、队列、串思维导图  进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:613504c8712613bc13f690ef57552a62

思维导图大纲

线性表、栈、队列、串思维导图模板大纲

递归算法时间复杂度

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)

相关思维导图模板

计算机理论知识传输系统思维导图思维导图

树图思维导图提供 计算机理论知识传输系统思维导图 在线思维导图免费制作,点击“编辑”按钮,可对 计算机理论知识传输系统思维导图  进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:4454067a46ed5333931759de55378bb4

计算机理论知识接口特性与设备思维导图思维导图

树图思维导图提供 计算机理论知识接口特性与设备思维导图 在线思维导图免费制作,点击“编辑”按钮,可对 计算机理论知识接口特性与设备思维导图  进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:dc9af4e01906e9fc20672ad772a50c1e