数据结构
2020-04-14 18:43:22 0 举报AI智能生成
数据结构
作者其他创作
大纲/内容
如果学习c++，学习数据结构后，推荐学习标准模板库(STL)
排序算法
知识点：
复杂度
稳定性
具体实现
详细总结
插入排序
o(n^2)
稳定
选择排序
o(n^2)
不稳定
冒泡排序
o(n^2)
稳定
快速排序
o(nlog2^n)
不稳定
堆排序
o(nlog2^n)
不稳定
归并排序
o(nlog2^n)
稳定
计数排序
o(n+k)
稳定
基数排序
o(n*k)
稳定
算法实现
python
c++
常用数据结构
线性结构
顺序表
数组
链表
判断是否有环
环的大小
两个有序链表的合并，多个有序链表的合并
栈
队列
经常用来实现BFS
稀疏矩阵
三元组表示
非线性结构
二叉树
种类
满二叉树
高度位h的二叉树恰好有2^h - 1个结点
完全二叉树
一棵二叉树中，只有最下面两层结点的度可以小于2
最下一层的叶结点集中在靠左的若干位置上
扩充二叉树
除叶子结点外，其余结点都必须有两个孩子
二叉搜索树(BST)
定义
若左子树不空，则左子树上所有结点的关键字均小于根结点的关键字
若右子树不空，则右子树上所有结点的关键字均大于根结点的关键字
对二叉搜索树的搜索、插入和删除操作的平均时间为o(log2^n），或o(h)，h为树的高度
二叉平衡树(AVL)
定义
其根的左右子树高度之差的绝对值不超过1
其根的左右子树都是二叉平衡树
问题：leetcode题目，判断一棵树是否为AVL树
红黑树
是一个自平衡二叉搜索树
要求
结点是红色或者黑色
根结点是黑色
所有叶子结点是黑色
每个红色结点必须有两个黑色子结点
从任一结点到其每个叶子结点的所有简单路径都包含相同数目的黑色结点
C++STL中实现map和set等数据结构
样例
NIL是叶子结点
性质
二叉树的第i层最多2^(i-1)个结点
高度为h的二叉树上至多2^h-1个结点(即满二叉树)
包含n个元素的二叉树的高度至少为log2(n+1)向上取整
具有n个结点的完全二叉树的高度为log2(n+1)向上取整
结点i的左孩子为：2*i+1,右孩子为：2*i+2
结点i的父结点为(i-1)/2向下取整
存储方式
顺序存储
链表表示
遍历
前序遍历
父-左-右
中序遍历
左-父-右
后序遍历
左-右-父
宽度遍历
深度遍历
哈夫曼树
哈夫曼算法
构造具有最小加权路径长度的扩充二叉树的算法
用哈夫曼算法构造的扩充二叉树称为哈夫曼编码树
构造过程
将一组大小为n的权值，生成一个由n棵树组成的森林
从森林中选择两个根结点最小的树，分别作为新树根的左、右子树，新树根的权值是左右子树根结点的权值之和
从森林中删除这两棵树，另将新二叉树插入森林中
重复（2）（3），知道森林中只有一棵树
注意：一般叶子结点用方形结点表示，二非叶子结点用圆形结点表示
哈夫曼编码
并查集
多叉树
B-树
m阶B树
定义
根结点至少有两个子结点
每个非根结点所包含的关键字个数j满足：m/2(向上取整) <= j <= m-1
除根结点和叶子结点以外所有结点的度数正好是关键字总数加1
所有的叶子结点都位于同一层
表示方式
2-3树 或者 (2,3)树
表示内部结点只可能有2或3个子结点
m阶B树是一棵m叉搜索树
左边子树的结点的值小于父结点的值，右边相反
通过减少树高来降低二叉查找树的查找代价，主要是跟内存与磁盘交互有关
样例
4阶B树
性质
叶子结点总数 -1 = 元素总数N
B+树
通常用于数据库和操作系统的文件系统中
性质
所有关键字存在叶子结点，中间结点只存储索引
B+树中的叶子结点收尾相连
参考资料
链接
链接
字典树
散列表
冲突
散列函数
除留余数法
h(key) = key mod M
M是散列表的大小
平方取中法
折叠法
数字分析法
拉链法
开地址法
如果遇到某个位置为空，直接放入。如果不为空，就需要一种解决冲突的策略来确定如何探查下一个空位置。
根据探查序列的规则
线性探查法
h(key) mod M, (h(key)+1)mod M, ....., h_i = (h(key)+i) mod M
伪随机探查法
y0=h(key), y_i+1 = (y_i + p) mod M
y0为伪随机树发生器的初值，p为与M接近的素数
二次探查法
h0(key), h1(key), ...., h2i-1(key), h2i(key)
h0(key) = h(key)
h2i-1(key) = (h(key)+i^2) mod M
h2i(key) = (h(key)-i^2) mod M
双散列法
Hi = (h1(key) + i*h2(key)) mod M, i = 0,1,2,
跳表
提高访问链表的搜索速度
跳表结构
堆
定义
最小堆
一个大小为n的堆是一棵包含n个结点的完全二叉树，该树的每个结点关键字大于等于其双亲结点的关键字值
最大堆
每个结点的关键字小于等于其双亲结点的关键字值，堆顶元素最大
堆操作
子主题
堆排序
哈希表
搜索
顺序搜索
二分搜索
有序数组的二分搜索
二叉搜索树的查找
时间复杂度log(2^n)
字符串
KMP算法
实现
C++中string的各种操作
find
int n = s.find("is")
从开头开始查找
int n = s.find("is", 5);
从位置5开始查找
rfind
倒着查询，使用跟find一样
insert()
str.insert(str.begin()+2, 'a');
只能添加单个字符
str.insert(1, 4, 'a');
在1位置插入4个字符a
const char * cptr = "abc";
str.insert(1, cptr);
str.insert(1, cptr);
在1位置插入字符串abc
reverse()
逆序
reverse(str.begin(), str.end());
pop_back()
删除末尾的字符
push_back(char c);
添加字符到末尾
append()
在末尾添加字符串或字符
str.append("str");
const char * cptr = "C-string"; str.append(cptr);
const char carr[] = "Two and one"; str.append(carr, 4);
4表示只添加carr前面四个字符
compare()
const char * cptr = "abc";
string str2 = "233345";
int a = str.compare(cptr);
int b = str.compare(str2);
string str2 = "233345";
int a = str.compare(cptr);
int b = str.compare(str2);
如果在str中找到了对应字符串，则返回在str中的起始下标，否则返回-1
clear()
s.clera();
清空字符串
substr(int pos, int len)
string sub = s.substr(2,3);
第2个位置开始，长度为3
to_string()
可以将数值类型转换成string类型
string str = to_string(23.45);
删除字符串中的某个字符
string str = "12333453242";
str.erase(remove(str.begin(), str.end(), '2'), str.end());
str.erase(remove(str.begin(), str.end(), '2'), str.end());
删除str所有等于2的字符
注意remove无法删除字符串，需要配合erase使用
getline()
从I/O读取一行写入字符串
string name; getline(std::cin, name);
转char *
c_str()
char * c = s.c_str();
data()
char * c = s.data();
string的更多操作参考
图
图的存储方式
邻接矩阵
邻接表
图的遍历
深度优先遍历DFS
宽度优先遍历BFS
拓扑排序
AOV网络或顶点活动网络
步骤
从图中选择一个入度为0的顶点，并输出之
从图中删除该顶点及其所有出边
重复1和2，直到所有顶点已列出；或者直到剩下的图中再也没有入度为0的顶点为止，后者表示图中包含有向回路
关键路径
AOE网络
顶点代表时间，有向边代表活动
有向边的权值代表所需的时间
样例
关键路径
有些活动可以并行地执行，所以完成工程所需的最短时间，是从开始顶点到完成顶点的最长路径的长度，这条最长路径被称为关键路径
关键活动
对整个公管处的最短工期有影响的活动
求解方法
动态规划
最小代价生成树
一棵生成树的代价是各条边上的代价之和。一个网络的各生成树中，具有最小代价的生成树称为该网络的最小代价生成树
构造最小代价生成树的算法
普里姆算法
选一个代价最小的边，然后从其他一个结点出发一直找最小代价的边，递归下去
子主题
克鲁斯卡尔算法
一直选择代价最小的边，直到所有结点连通，需要保证不会出现回路
示例
单源最短路径
最短路径
迪杰斯特拉算法
弗洛伊德算法
所有顶点之间的最短路径
弗洛伊德算法
0 条评论
下一页
