数据结构与算法
2022-06-20 16:12:51 40 举报AI智能生成
数据结构与算法知识复习思维导图
作者其他创作
大纲/内容
空间复杂度
最好
最坏
平均
均摊
时间复杂度
复杂度分析
线性表线性结构：数据元素之间是一对一的关系。
顺序栈
链式栈
栈
限定仅在表尾进行插入和删除操作的线性表，允许插入和删除的一端为栈顶，另一端是栈底。
性质：后进先出
「栈」是一种后进先出的线性表。
插入：若有一元素想往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） 多次删除集中在一起，提高删除效率
数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
连续的内存空间和相同类型的数据(随机访问的前提)。
优点：两限制使得具有随机访问的特性缺点：删除，插入数据效率低。
对内存空间要求高，需要一块连续的内存空间
数组
每个节点只包含一个指针，即后继指针。
单链表有两个特殊的节点，即首节点和尾节点。为什么特殊？用首节点地址表示整条链表，尾节点的后继指针指向空地址null。
性能特点：插入和删除节点的时间复杂度为O（1），查找的时间复杂度为O(n)。
单链表
节点除了存储数据外，还有两个指针分别指向前一个节点地址（前驱指针prev）和下一个节点地址（后继指针next）。
首节点的前驱指针prev和尾节点的后继指针均指向空地址。
性能特点：和单链表相比，存储相同的数据，需要消耗更多的存储空间。
双向链表
除了尾节点的后继指针指向首节点的地址外均与单链表一致。
适用于存储有循环特点的数据，比如约瑟夫问题。
循环链表
链表
链表中的每一个内存块被称为节点Node。节点除了存储数据外，还需记录链上下一个节点的地址，即后继指针next。
插入、删除数据效率高O(1)级别（只需更改指针指向即可），随机访问效率低O(n)级别（需要从链头至链尾进行遍历）。
和数组相比，内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。
链表的内存结构是不连续的内存空间，是将一组零散的内存块串联起来，从而进行数据存储的数据结构。
队列
数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。
数据元素：是组成数据的，有一定意义的基本单位，在计算机中通常作为整体处理，也被称为记录。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构的逻辑结构：数据对象中数据元素之间的相互关系，分为线性结构、树形结构、图形结构以及集合结构。
数据结构的物理结构：数据的逻辑结构在计算机中的存储形式，分为顺序存储和链式存储（不连续存储）。
算法：解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
算法五个基本特性：输入、输出、有穷性、确定性和可行性。
常见概念
数据元素之间存在一对多的层次关系
度：结点拥有的子树数
树的度：树内各结点的度的最大值
叶结点/终端结点：度为0的结点
树的深度/高度：树中结点的最大层次
树形结构
是N（N>=0）个结点的有限集合，该集合或为空集（空二叉树），或者由一个根结点和两颗互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
二叉树
所有分支结点都存在左子树和右子树，并且所有非叶子节点都在同一层上
满二叉树
对一棵具有n个结点的二叉树按层序编号，如果编号i（1<= i <= n）的结点与同样深度的满二叉树中的编号i 的结点在二叉树的位置完全相同，则这棵二叉树称为完全二叉树
完全二叉树
树
每个结点最多只有两颗子树
左右子树是有顺序的
即使某结点只有一颗子树，也要区分是右子树还是左子树
二叉树的特点
无向图
有向图
图的邻接矩阵的存储方式是用两个数组来实现的，一个一维数组存储顶点信息，一个二维数组存储线（无向图）或弧（有向图）的信息。
邻接矩阵
邻接表存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。
邻接表
图的存储
图图(Graph)是由顶点和连接顶点的边构成的离散结构。
邻接(adjacency)：邻接是两个顶点之间的一种关系。
关联(incidence)：关联是边和顶点之间的关系。
两个重要关系：
数据结构与算法
0 条评论
回复 删除
下一页
