数据结构知识点总结

基础概念

数据
信息的载体，描述客观事物属性的数、字符、及所有能输入计算机并被计算机识别和处理的符号集合

数据元素
数据的基本单位，一个数据元素由若干个数据项组成

数据对象
具有相同性质的数据元素的集合

数据类型
一组性质相同的值的集合及定义在此集合上的一些操作的总称，分为原子型、结构型、抽象数据类型

数据结构
数据元素都不是孤立存在，它们之间存在某种关系，这种数据元素相互间的关系称为数据结构

数据结构3要素
数据的逻辑结构、数据的存储结构、数据运算

算法
对特定问题求解步骤的描述，特性：有穷性、确定性、可行性、输入、输出
好的算法应达到目标
正确性、可读性、健壮性、效率与第存储量需求

算法的度量
时间复杂度、空间复杂度

线性表

定义
具有相同数据类型的n个元素的有限序列
线性表特点
1.表中元素个数有限
2.表中元素具有逻辑上的顺序性
3.表中元素都是数据元素
4.表中元素数据类型相同
5.表中元素具有抽象性

1）顺序表

线性表顺序存储
顺序表操作
1.插入
最好O(1)，最坏O(n),平均O(n)
2.删除
最好O(1)，最坏O(n),平均O(n-1)
3.查找
最好O(1)，最坏O(n),平均O(n+1)

2）单链表

线性表的链式存储
单链表操作
1.插入
O(1)
2.删除
O(n)
3.查找
O(n)

3）双链表

在单链表的元素上增加一个指向前一个节点的指针

4）循环链表

链表最后一个元素的后继指针指向第一个元素

5）静态链表

借助数组来描述线性表的链式存储结构，插入、删除操作只需要修改指针，不需要移动元素

栈和队列

栈定义
只允许在一段进行插入或删除操作的线性表

栈顶
允许进行插入和删除的那一端

栈底
不允许插入和删除的另一端

空栈
不含仍和元素的空表

队列
一种受限制的线性表，只允许在一端进行插入，而在另一端进行删除

队头
允许删除的一端

队尾
允许插入的一端

空队列
不含任何圆度的空表

树和图

树定义
n个节点的有限集合

度
一个节点的子节点个数称为该节点的度；树中节点的最大度数称为数的度

高度
数中节点的最大层数

二叉树遍历
先序遍历、中序遍历、后序遍历、层次遍历

线索二叉树
在n个节点中，有n+1个空指针，存放遍历的后继节点，使得二叉树遍历效率更高

树的存储结构
双亲表示法、孩子表示法、孩子兄弟表示法

二叉树应用
二叉排序树、平衡二叉树、哈夫曼树、哈夫曼编码

图定义
由点、边组成的集合

图的存储
邻接矩阵法、邻接表法、十字链表、邻接多重表

图的遍历
广度优先、深度优先

图的应用
最小生成树、最短路径、拓扑排序

动态查找
包含插入、删除操作的查找

查找方式
顺序查找、折半查找、分块查找

B树的阶
B树中所有节点的孩子节点数的最大值

m阶B数满足以下特征
1.树中每个节点至多由m颗子树
2.每个节点至多含有m-1个关键字
3.除根节点外，至少有math.ceil(hm/2)颗子树
4.所有叶子节点在同一层次上

串
零个或多个字符组成的有限序列
串的存储
定长顺序存储、堆分配存储、块链存储