数据结构与算法
2020-04-01 10:06:30 0 举报AI智能生成
数据结构整体总结
作者其他创作
大纲/内容
数据结构
实现
顺序存储
数组
特点
时间
查找O(1)
增减O(n）
空间
固定
链式存储
链表
单向链表
双向链表
循环链表
静态链表
特点
时间
查找O(n)
增减O(1）
空间
灵活
线性表
栈
应用
递归
逆波兰法
顺序栈
共享空间
链式栈
队列
顺序循环队列
链式队列
串
比较
ASCII码
操作
查找子串
得到子串
替换子串
KMP模式匹配算法
树
度
叶节点（0）
内部节点（1-n)
层次
存储结构
双亲表示法
孩子表示法
双亲孩子表示法
孩子兄弟表示法
二叉树
二叉树
特点
度<=2
左/右子树独立
五种基本形态
特殊二叉树
斜树
满二叉树
叶子在最下层
非叶子节点的度都为2
同深度树比较，满二叉树节点最多，叶子最多
完全二叉树
满二叉树倒序删减
性质
第i层上至多有2^(i-1)个节点（i>=1)
深度为k至多有2^k-1个节点
对任何一棵二叉树T，如果其终端节点数为n0,度为2的节点数为n2，则n0=n2+1
存储结构
顺序存储
一般只用于完全二叉树
二叉链表
data+lchild+rchild
遍历
前序遍历
根节点-左子树-右子树
根节点在前
中序遍历
根节点分割
搭配前/后可确定唯一二叉树
后序遍历
从左到右-先叶子后节点-最后根节点
根节点在后
递归
访问
前中后遍历
遍历左子树
遍历右子树
层序遍历
从上至下、从左至右
建立
即为遍历，将访问改为生成节点
线索二叉树
线索化
标志域
树、森林与二叉树的转换
树转换
左子树为子，右子树为兄弟
森林转换
所有的树为兄弟
逆转换
赫夫曼树
树的路径长度
带权路径长度WPL最小的二叉树称作赫夫曼树
赫夫曼编码
图
算法
0 条评论
下一页
