数据结构与算法

计算机二级数据结构与算法思维导图分享！下图清晰地梳理了算法、数据结构的基本概念、线性表及其顺序存储结构、栈和队列、线性链表等内容的脉络！希望对小伙伴们有帮助哦！

数据结构与算法

算法

算法的基本概念

概念：算法是指一系列解决问题的清晰指令

4个基本特征：可行性、确定性、有穷性、拥有足够的情报

两种基本要素

对数据对象的运算和操作

算数运算

逻辑运算

关系运算

数据传输

算法的控制结构（各操作之间的执行顺序）

描述算法的工具

同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行，效率均不同

传统流程图

N-S结构化流程图

算法描述语言

设计的基本方法：列举法、归纳法、递推法、减半递推技术、回溯法

算法的复杂度

算法的时间复杂度：执行算法所需要的计算工作量

问题的规模

待处理的数据的状态

算法的空间复杂度：执行算法所需的内存空间

算法程序所占的空间

输入的初始数据所占的存储空间

算法执行各过程中所需的额外空间

算法执行过程中的工作单元

某种数据结构所需要的附加存储

数据结构的基本概念

数据结构是自相互有关联的数据元素的集合，即数据组织形式。

逻辑结构

反应数据元素之间的逻辑关系

存储结构

数据的逻辑结构在计算机存储空间中的存放形式

顺序存储

索引存储

散列存储

链式存储

对各种数据结构进行的运算

数据

数据元素

数据对象

数据的逻辑结构

数据元素的集合D

集合上的关系B=(D,R)

按各元素前后件关系的复杂度

非线性结构

空的数据结构是线性还是非线性视具体情况而定

线性表及其顺序存储结构

线性表的基本概念

线性表（线性结构）最简单常用的一种数据结构

线性表的顺序存储结构

元素所占的存储空间必须连续

元素在存储空间的位置是按逻辑顺序存放的

线性表的插入运算

最坏情况，插入在第一个，其他均需要移动

线性表的删除运算

栈和队列

栈及其基本运算

基本概念

栈是一种特殊的线性表，插入和删除运算都在线性表的一段进行，先进后出，后进先出

常考

栈顶：允许插入和删除的一段

栈底：栈的另一端

空栈：栈中没有元素的栈

特点

栈顶元素是最先被插入和最后被删除的元素

栈有记忆作用

在顺序存储结构下，栈的插入和删除运算不需要移动表中其他数据元素

栈顶指针top动态反应了栈中元素的变化情况

顺序存储和运算

入栈运算

在栈顶位置插入一个新元素：栈顶指针+1，新元素插入到栈顶指针指向的位置，当栈顶指针指向最后即已满，上溢错误

退栈运算

读栈顶运算

队列及其基本运算

基本概念

队尾：允许插入的一端

线性结构

有且只有一个根节点，且每个节点最多只有一个直接前驱和一个直接后驱的非空数据结构（前件和后件）

排头：允许删除的一端

循环队列及其运算

入队运算

在循环队列的队尾加入一个新元素

上溢：队列非空s=1，队尾指针等于队头指针，队列已满，不能入队运算

退队运算

从队头位置退出一个元素并赋给指定的变量

下溢：队列为空s=0,不能进行退队运算

线性链表

单链表/线性链表

只有一个指针来存放下一个元素

链式存储方式

数据域

存放数据元素值

指针域

存放指针（指针用于指向迁建或后件）

树和二叉树

树可以有无数个结点，但二叉树最多有两个

树的基本概念

树是简单的非线性结构

根：有且仅有一个没有前驱的节点

父节点：每个节点只有一个前件，无前件的节点只有一个

子节点：每个节点可以有多个后件，无后件的节点称为叶子节点

树的度：所有节点最大的度

树的深度：树的最大层次

二叉树的定义及其基本性质

二叉树的定义

非线性结构，有限的节点集合

完全二叉树

满二叉树

（ ）

可为空，空的二叉树无节点，非空二叉树有且只有一个根节点

每个节点最多可以有两棵子树，左子树和右子树

二叉树的基本性质

在二叉树的遍历中无论是前序遍历，中序遍历还是后序遍历，二叉树的叶子节点优先

在二叉树的第k层上至多有2k-1个节点

深度为m的二叉树至多有2m-1个节点

对任何一棵二叉树，度为0的节点（叶子节点）总是比度为2的节点多一个

具有n个节点的完全二叉树的深度至少为[log2n]（整数部分）+1

满二叉树与完全二叉树

满二叉树

除最后一层外，每一层的所有节点都有两个子结点

每一层的节点数都达到最大值，第k层有2k-1个结点

深度为m的二叉树有2m-1个结点

完全二叉树

除最后一层外，每一层的节点数均达到最大值

在最后一层上只缺少右边的若干结点

叶子结点只可能在层次最大的两层上出现，对于任何一个结点，其右分支的子孙结点的最大层次为p，则其左分支下的子孙结点的最大层次为p或p+1

二叉树的遍历

原则：先左后右

分类

前序遍历

根节点→左子树→右子树

中序遍历

左子树→根节点→右子树

后序遍历

左子树→右子树→根节点

查找技术

顺序查找

只能用顺序查找的两种情况

线性表为无序表

链式存储的有序表

二分法查找

只适用于顺序存储的，按非递减排列的有序表

查找方法

最坏情况查找log2n次

排序技术

交换类排序法

冒泡排序法

最坏情况比较次数为n（n-1）/2次

平均执行时间o（n2）

快速排序法

o（nlog2n）

任取待排序序列中的某个元素作为基准

分为左右两个子序列

左子序列的排序码均≤基准元素的排序码

右子序列的排序码锯≥基准元素的排序码

然后排序，直到整个序列有序