数据结构与算法
2022-06-20 16:12:51 41 举报AI智能生成
数据结构与算法知识复习思维导图
作者其他创作
大纲/内容
复杂度分析
空间复杂度
时间复杂度
最好
最坏
平均
均摊
线性表
线性结构：数据元素之间是一对一的关系。
线性结构：数据元素之间是一对一的关系。
栈
顺序栈
链式栈
数组
数组（Array）是一种线性表数据结构。
它用一组连续的内存空间，来存储一组
具有相同类型的数据。
它用一组连续的内存空间，来存储一组
具有相同类型的数据。
插入：
若有一元素想往int[n]的第k个位置插入数据，需要在k-n的位置往后移。
最好情况时间复杂度 O(1)
最坏情况复杂度为O(n)
平均负责度为O(n)
1） 插入：从最好O(1) 最坏O(n) 平均O(n)
2） 插入：数组若无序，插入新的元素时，
可以将第K个位置元素移动到数组末尾，把
心的元素，插入到第k个位置，此处复杂度为O(1)。
3） 删除：从最好O(1) 最坏O(n) 平均O(n)
4） 多次删除集中在一起，提高删除效率
连续的内存空间和相同类型的数据(随机访问的前提)。
优点：两限制使得具有随机访问的特性缺点：删除，插入数据效率低。
对内存空间要求高，需要一块连续的内存空间
链表
单链表
每个节点只包含一个指针，即后继指针。
单链表有两个特殊的节点，即首节点和尾节点。
为什么特殊？用首节点地址表示整条链表，尾节点
的后继指针指向空地址null。
为什么特殊？用首节点地址表示整条链表，尾节点
的后继指针指向空地址null。
性能特点：插入和删除节点的时间复杂度为O（1），
查找的时间复杂度为O(n)。
查找的时间复杂度为O(n)。
双向链表
节点除了存储数据外，还有两个指针分别指向前一个节点地址
（前驱指针prev）和下一个节点地址（后继指针next）。
（前驱指针prev）和下一个节点地址（后继指针next）。
首节点的前驱指针prev和尾节点的后继指针均指向空地址。
性能特点：
和单链表相比，存储相同的数据，需要消耗更多的存储空间。
循环链表
除了尾节点的后继指针指向首节点的地址外均与单链表一致。
适用于存储有循环特点的数据，比如约瑟夫问题。
队列
队列是一种受限的线性表数据结构,只支持两个操作:入队enqueue(),放一个数据到队列尾部;
出队dequeue0),从队列头部取一个元素。
出队dequeue0),从队列头部取一个元素。
队列跟栈一样,也是一种抽象的数据结构。
具有先进先出的特性,支持在队尾插入元素,在队头删除元素。
队列可以用数组来实现,也可以用链表来实现。
用数组实现的队列叫作顺序队列,用链表实现的队列叫作链式队列。
常见概念
数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。
数据元素：是组成数据的，有一定意义的基本单位，在计算机中通常作为整体处理，也被称为记录。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构的逻辑结构：数据对象中数据元素之间的相互关系，分为线性结构、树形结构、图形结构以及集合结构。
数据结构的物理结构：数据的逻辑结构在计算机中的存储形式，分为顺序存储和链式存储（不连续存储）。
算法：解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
算法五个基本特性：输入、输出、有穷性、确定性和可行性。
树形结构
数据元素之间存在一对多的层次关系
度：结点拥有的子树数
树的度：树内各结点的度的最大值
叶结点/终端结点：度为0的结点
树的深度/高度：树中结点的最大层次
图
图(Graph)是由顶点和连接顶点的边构成的离散结构。
图(Graph)是由顶点和连接顶点的边构成的离散结构。
无向图
有向图
图的存储
邻接矩阵
图的邻接矩阵的存储方式是用两个数组来实现的，一个一维数组存储顶点信息，
一个二维数组存储线（无向图）或弧（有向图）的信息。
一个二维数组存储线（无向图）或弧（有向图）的信息。
邻接表
邻接表存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。
0 条评论
下一页
