小梁数据结构
2025-12-21 20:46:37 0 举报
AI智能生成
期末速成
作者其他创作
大纲/内容
数据结构
基本术语
数据(所有元素集合)
数据元素:数据结构基本单位(记录)
数据项:数据元素具体信息(元素)
数据对象:相同属性的数据元素集合(具有条件的元素集合)
数据>数据对象>数据元素>数据项
组织方式
逻辑结构(唯一性)
线性结构(1:1)
线性表
栈、队列
串、数组
非线性结构(1:∞ | ∞:∞)
树形结构
图形结构
物理结构(存储结构)
顺序存储(连续)
链式存储(不一定连续)
数据本身信息
一个或多个指向其他元素的指针
算法
基本特征
输入(可以没有输入)
输出(一定要有输出)
确定性
有穷性
可行性
评价
正确性
可读性
健壮性
高效性
时间代价
时间复杂度
常数:O(1)
对数:O(log2(n))
线性:O(n)
平方:O(n²)
语句频度:代码执行的次数
单层循环(n)
嵌套循环(n*m)
空间代价
空间复杂度
组成部分
输入数据所占空间(输入的数据)
辅助存储空间:固定不变(临时变量、局部变量、常量)
临时空间:动态增加(数组、链表节点、栈帧)
类型
常数O(1):所需空间不会随输入规划变化
线性O(n):所需空间与输入数据量成正比
线性表(1:1)
特点
有序性
唯一性
动态性
常见操作
插入
删除
访问
搜索
排序
表示和实现
顺序表(逻辑相邻,物理相邻)
优点
时间(随机存取表中任一元素)
空间(存储密度大)
缺点
时间(插入、删除某一元素需要移动大量元素)
空间(浪费存储空间,是静态存储方式,元素个数不能自由扩充)
链表(逻辑相邻,物理不一定相邻):数据+指针
分类
单链表(一个指针)
双链表(两个指针)
循环链表(首尾相连)
存储结构
头指针(第一个结点的指针)
首元节点(第一个元素的结点)
头结点(首元结点前的一个结点,存首元结点的位置信息)
栈和队列
栈(先进后出,后进先出)
顺序栈:只能在栈顶删除和插入
常规操作
初始化(S.top = S.base)
栈是否为空(S.top == S.base)
长度(S.top - S.base)
清空栈(S.top = S.base)
进栈
出栈
链栈
队列(先进先出)
顺序存储
循环队列:队满(rear+1)%M个元素 == front
链式存储
串、数组、广义表
串
常见名词
主串
字串
字符位置
字串位置
串相等
空格串
匹配
bf算法
KMP算法
数组
存储方式
行列存储
矩阵
对称矩阵:地址(i(i-1)/2+j)
广义表
广义表(LS:表名,ai:子表、元素(原子),n:长度):广义表是可能含有 0 个或多个子表的表
去表头(先找第一个子表,没有就找第一个原子),去表尾(去掉表头剩下的)
特点
次序性
有长度
有深度(括号的重数)
可递归(自己可作为自己的子表)
可共享
树、二叉树
树(1:∞)
二叉树
性质
第i层上至多有2^(i-1)个结点,至少有1个
深度为k的二叉树至少有(2^k)-1个结点,至少有k个
叶子数n0=n1+1
具有n个节点的完全二叉树的深度必为[log2(n)]+1
完全二叉树从上至下,从左到右编号,若编号为i,则左孩子必为2i,右孩子必为2i+1,双亲必为i/2
区分
满二叉树:每一层都充满结点(特殊情况)
完全二叉树(最后一层叶子不满)
遍历
先序,中序,后序
哈夫曼编码
编码过程(遇0向左,遇1向右)
WPL、权值、带权路径 WPL=权值*带权路径
哈夫曼树(权值大的结点靠近根)
0 条评论
下一页