小梁数据结构
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 条评论
下一页
