算法与数据结构
2019-07-30 23:36:15 0 举报AI智能生成
算法与数据结构思维导图
作者其他创作
大纲/内容
算法
迭代
使用一个迭代的方法计算结果
不需要反复调用函数，浪费内存
不简洁
递归
需要不断调用函数，建立函数副本，消耗内存
代码简洁易懂
父主题
排序算法
排序类型
稳定
冒泡排序，插入排序，归并排序，计数排序，桶排序，基数排序
不稳定
选择排序，希尔排序，堆排序，快速排序
内排
冒泡排序，选择排序，插入排序，希尔排序，堆排序，快速排序
外排
归并排序，计数排序，桶排序，基数排序
算法
冒泡排序
两两相邻数据比较，如果前面比后面大就进行交换，直到数列有序
实现
for(i=0;i<arr.lenth;i++)
{
for(j=0;j<arr.lenth-i-1;j++)
{
if(arr[j]>arr[j+1])
{
swap(arr[j],arr[j+1]);
}
}
}
{
for(j=0;j<arr.lenth-i-1;j++)
{
if(arr[j]>arr[j+1])
{
swap(arr[j],arr[j+1]);
}
}
}
时间复杂度
最好：数组有序，比较n-1次，时间复杂度是O(n)
最坏：数组逆序，第一次比价n-1次....总次数=n-1+n-2+...+1=(n-1)n/2,时间复杂度是O(n^2)
平均复杂度：(O(n)+O(n^2))/2=O(n^2)
空间复杂度
因为这个排序是在原数组上进行的操作，所以空间复杂度：O(1)
稳定性
相邻连个元素进行比较，所以不存在跳跃比较，移动的情况，所以是稳定比较
排序类型
由于每次排序都需要用到整个数组，所以需要将数组全部加载到内存中，所以是内排序
选择排序
每次选出最大的数据，将他放到最后，直到所有的数据有序
实现
for(i=0;i<arr.lenth-1;i++)
{
max=a[0];
for(j=i+1;j<arr.lenth;j++)
{
if(arr[j]>a[i])
{
swap(a[i],a[j]);
}
}
}
{
max=a[0];
for(j=i+1;j<arr.lenth;j++)
{
if(arr[j]>a[i])
{
swap(a[i],a[j]);
}
}
}
时间复杂度
插入排序
希尔排序
堆排序
快速排序
归并排序
计数排序
桶排序
基数排序
查找算法
1.分治算法
2.动态规划
3.贪心算法
4.回溯
5.分支界限
数据结构
数据结构简介
逻辑结构
1.线性表
（1）顺序线性表
数组
访问快，时间复杂度O(1)
删除、插入速度慢，时间复杂度O(n)
连续单元存储，存储空间不好确定，不好扩展
造成存储空间碎片
适合频繁查找数据
（2）链式线性表
单链表
访问慢，时间复杂度未O(n)
删除插入快，时间复杂度O(1)
存储在任意存储单元，每个节点包括数据元素和指向下一个节点的指针
适合不知道线性表需要多大的空间
静态链表
使用顺序结构实现链式链表
双向链表
每个节点除了包含数据元素还包括一个指向上一个节点的指针和指向下一个节点的指针
2.栈与队列
栈
后进先出(LIFO)
顺序存储
单栈
共享栈
两个栈共享存储空间，栈1的栈顶在下标0处，栈2的栈顶在下表n-1处
链式存储
标记栈顶，判断栈是否为空
栈可以实现回退操作，递归和四则运
递归
递归在执行的时候，需要不断的调用自身，直到可以返回确定的值，这个两个操作正好对应着栈的压栈和出栈的操作。
四则运算
电脑使用后缀法进行四则运算，后缀表达式就是使用栈进行存储；人通常使用的是中缀式
中缀式—>后缀式的构造
数字直接输出，对符号进行压栈，当前符号优先级高于栈顶符号，输出；否则压栈。
遇到右括号进行压栈，进行上面一步操作，遇到左括号先出栈直到右括号，这里不进行压栈；
后缀式计算
对输出的后缀式遍历，对数字进行压栈；
遇到运算符，将栈顶的两个数字弹出计算结构压入栈中
系统管理的对象就是放进一个全局栈里面的，等不需要的时候，一个一个出栈，释放所占的内存
队列
先进先出(FIFO)
线性存储
顺序队列
使用数组模拟队列
数组插入删除比较繁琐
循环顺序队列
将队列的头和尾可以在数组中任意变化
插入删除不需要频繁移动数据
顺序队列的存储空间是提前申请的，可能会溢出
链式存储
链式队列
弥补顺序栈的不足，不需要提前申请空间，只是需要频繁引入申请和释放
只允许在一端进行插入操作，而在另一端进行删除操作的线性表
郭先申请的应该先被满足
3.串
是由零个或多个字符组成的有限序列，又叫字符串
链式存储
可变字符串
顺序存储
不可变字符串
字符串匹配模式
朴素匹配模式
循环遍历文本串，匹配串不改变
暴力匹配算法
文本串从i开始和模式串从j开始，如果字符匹配就i++,j++;
如果字符不匹配，i=i-j+1,j=0
事件复杂度：O(n*m)
KMP模式
教程
https://www.jianshu.com/p/68e9a227cb45
kmp算法
先计算模式字符串的最大前后缀公共元素和next数组
最大前缀和最大后缀
使用两个变量i=0,j=1，并操作模式串S;
- 如果S[i]!=S[j],j++；
i==0,next[j]=i;
i!=0,next[j]=next[i];
2.如果S[i]!=S[j],将i的存在next[j]中，并i++,j++；
重复步骤1、2，直到j到达文本串的末尾;
next数组
将next[0]=-1;
文本字串T,模式字串S；
用模式字符串去匹配文本字符串
i=0,j=0，操作模式字符串S和文本字符串T,以及next数组；
1.T[i]==S[j]时，i++,j++；
2.T[i]!=S[j]时，j=next[j];
重复步骤1、2，直到匹配成功或者文本串到达末尾
时间复杂度：O(n+m)
4.树
特征
n（n>=0）个结点的有限集
节点间的关系
孩子（child）
双亲（parent）
兄弟（sibling）
祖先
子孙
节点
节点拥有的子树称为节点的度(degree)
度为0的节点被称为叶子节点（leaf），不为0的节点称为分支节点
除根节点外，分支节点也称为内部节点
树的度是内节点的度的最大值
其他
节点层次（level）
节点中最大的层次称为节点的深度（depth）或高度
如果左右子树是有序的称为有序子树，否则称为无序子树
森林，多个不相交树集合
存储结构
双亲表示法
在每个结点中，拥有指向双亲结点的指针（可以扩展子结点或者兄弟结点）
孩子表示法
每个结点有多个指针域，其中每个指针指向一棵子树的根结点，叫多重链表表示法；把每个结点排列起来，以单链表做存储结构，叫孩子表示法。
孩子兄弟表示法
一个结点设置两个指针，分别指向该结点的第一个子结点和该结点的右兄弟。
二叉树
特点
每个节点最多拥有两棵子树：左子树和右子树
左右子树有序
只有一个子树也要分左右
基本形态
空子树
没有节点
只有一个根节点
节点只有左子树
节点只有右子树
节点有左右两个子树
特殊二叉树
斜树
所有节点只有左子树成为左斜树，反之右斜树
满二叉树
所有分支节点都有左右子树，并且叶子节点在同一层
完全二叉树
对于一个树高为h的二叉树，如果其第0层至第h-1层的节点都满
如果最下面一层节点不满，则所有的节点在左边的连续排列，空位都在右边
层次遍历如果遇到空节点，队列中还有子树不是完全二叉树
二叉树性质
性质一：在二叉树的第i层最多有2^(i-1)的结点（i>=1）
最多结点的二叉树是满二叉树，除了叶结点，所有结点的度都为2，所以，第i层最多有2^(i-1)个结点
性质2：深度为k的二叉树至多有2^k-1个结点（k>=1）
由性质1可以求出每层的结点数，则k（k>=1）层二叉树总共节点数为：n = 2^0 + 2^1 + ... 2^(k-1)=1*(1-2^k)/(1-2) = 2^k - 1
性质3：对任何一颗二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1
二叉树的总结点数为：n = n0 + n1 + n2（n0为叶结点，n1为度为1的结点数，n2为度为2的结点数）；
那么结点数为n的二叉树有多少条连接线呢？很明显每个结点，除了根结点都有指向连接线，所以，结点数为n的二叉树的总连接线为n-1；
从一个结点的度来算，度为1的结点会有1条连接线，连接子结点；
度为2的结点会有2连接线，连接子结点；
根结点没有双亲结点，所以没有连向根结点的连接线，那么有：n-1 = 1*n0 + 2*n2；
和第一条方程式联合可得：n0=n2+1。
性质4：具有n个结点的完全二叉树的深度为⎣log2(n)⎦ + 1（⎣x⎦表示不大于x的最大整数，取下界）
设置有n个结点的完全二叉树的深度为k，则：
2^(k-1)-1< n <= 2^k-1
2^(k-1)-1< n <= 2^k-1
因为k是整数，所以：
2^(k-1)<= n < 2^k
2^(k-1)<= n < 2^k
取对数得：
k-1<=log2(n)<k，即：k<=log2(n)+1并且k>log2(n)
所以：k=|log2(n)| + 1
k-1<=log2(n)<k，即：k<=log2(n)+1并且k>log2(n)
所以：k=|log2(n)| + 1
性质5：如果对一颗有n个结点的完全二叉树（其深度为|log2(n)| + 1）的结点按层编号（从第1层到第|log2(n) + 1|层，每层从左到右），对任一结点i（1<= i <= n）有
如果i=1，则结点i是二叉树的根结点，无双亲；如果i>1，则其双亲是结点|i/2|（取下界）。
如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i
如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1
存储结构
顺序结构
由于二叉树每个结点最多只有2个子树，并且左右子树是有顺序的，所以，可以使用数组直接存储
没有节点的位置存为空，直到最后一个节点
链式结构
每个节点除数据元素外，包含一个指向左子树的指针和指向右子树的指针
遍历
二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问有且仅有一次
前序
若二叉树为空，则返回；否则，先遍历根结点，然后遍历左子树，再遍历右子树。
中序
如果二叉树为空，则返回；否则，从根结点开始，先遍历左子树，然后是根结点，左后是右子树。
后序
如果二叉树为空，则返回；否则，先遍历左子树，然后遍历右子树
层序
如果二叉树为空，则返回；否则，从树的第一层，根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序逐个结点访问。
线索二叉树
加上向前驱和后续的指针称线索二叉树
https://blog.csdn.net/u014492609/article/details/40477795#
如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后续，
那么采取线索二叉链表的存储结构就是非常不错的选择
那么采取线索二叉链表的存储结构就是非常不错的选择
前驱
后驱
树、森林、二叉树的转换（兄弟孩子法）
树转二叉树
森林转二叉树
二叉树转为树
二叉树转为森林
赫夫曼树
图
物理结构
顺序存储
数组
链接存储
链表
0 条评论
下一页
