数据结构和算法
2024-08-17 15:19:24 58 举报AI智能生成
为你推荐
查看更多
有助于数据结构和算法的学习，我还会实时的进行更新内容，感谢您的点赞和提意见。
作者其他创作
大纲/内容
集合结构：其中的数据元素除了属于同一个集合外，没有其他任何的关系。
线性结构：其中的数据元素都是一对一的关系（就好像一条线）。
树形结构：其中的数据元素存在一对多的层次关系。
图形结构：其中的数据元素存在多对多的关系。
逻辑结构：是指数据对象中数据元素之间的关系。
顺序存储结构：就是把数据元素存储在地址连续的存储单元中，其数据间的逻辑结构和物理结构是一致的。
链式存储结构：就是把数据元素存储再任何的存储单元中，存储单元可以是连续的也可以是不连续的，但是为了保持数据间的逻辑结构我们就通过指针的方式来保持关系。
物理结构：数据的逻辑结构在计算机中的存储形式。
逻辑结构和物理结构
输入：最少有0个或者多个输入。
输出：至少有一个输出。
有穷性：算法的步骤必须是有限的，不能出现无限的循环，并且每个步骤的执行时间也是再可接受的范围。
确定性:算法的每个步骤必须都有确定的意义既无歧义，在一定条件下只能有一条执行路径。
可行性：算法的每一步必须都是可行的，每一步都能通过有限的执行次数完成。
算法的五大基本特征
算法没有于法的错误。
算法对于一个合法的输入必须有一个满足要求的输出结果。
对于不合法的输入要提供满足规格的输入要求。
算法对于故意刁难的输入测试都有满足要求的输出结果。
正确性:算法至少具备输入、输出和加工处理的无歧义性，能够正确的反应问题的需求并正确得到答案。
可读性
健壮性：当输入数据不合理时，也能做出相应的处理，而不产生异常、崩溃等莫名其妙的结果。
时间效率高和存储量低
算法的设计要求
事后统计法（不推荐）
忽略常数的相加。
只保留最高项。
去掉与最高项相乘的常数。
推导大O的攻略
常见的时间复杂度
最坏情况：就是一个算法的最长时间。也就是算法最长时间的保证。
平均情况：就是期望的运行时间
公式：T（n）=O(f(n))
时间复杂度
空间和时间是可以转换的。
公式：S(n）=O(f(n));
空间复杂度
事先分析法
算法采用的方法和策略。
编译产生的代码质量。
问题的输入规模。
机器执行指令的速度。
影响算法效率因素
算法效率的度量方法
每次循环都会找出当前循环中最小的元素，然后和此次循环中的队首元素进行交换。
选择排序
每次循环都比较前后两个元素的大小，如果前者大于后者，则将两者进行交换。这样做会将每次循环中最大的元素替换到末尾，逐渐形成有序集合。将每次循环中的最大元素逐渐由队首转移到队尾的过程形似“冒泡”过程，故因此得名。
一个优化冒泡排序的方法就是如果在一次循环的过程中没有发生交换，则可以立即退出当前循环，因为此时已经排好序了。
冒泡排序
插入排序的精髓在于每次都会在先前排好序的子集合中插入下一个待排序的元素，每次都会判断待排序元素的上一个元素是否大于待排序元素，如果大于，则将元素右移，判断再上一个元素与待排序元素；否则该处就应该是该元素的插入位置。
插入排序
堆排序的过程是首先构建一个大顶堆，大顶堆首先是一棵完全二叉树，其次它保证堆中某个节点的值总是不大于其父节点的值。
因为大顶堆中的最大元素肯定是根节点，所以每次取出根节点即为当前大顶堆中的最大元素，取出后再重新构建大顶堆，再取出根节点，再重新构建…重复这个过程，直到数据都被取出，最后取出的结果即为排好序的结果。
堆排序
归并排序使用的是分治的思想，首先将数组不断拆分，直到最后拆分成两个元素的子数组，将这两个元素进行排序合并，再向上递归。不断重复这个拆分和合并的递归过程，最后得到的就是排好序的结果。
合并的过程是将两个指针指向两个子数组的首位元素，两个元素进行比较，较小的插入到一个temp数组中，同时将该数组的指针右移一位，继续比较该数组的第二个元素和另一个元素…重复这个过程。最后temp数组保存的便是这两个子数组排好序的结果。最后将temp数组复制回原数组的位置处即可。
归并排序
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序
快速排序
是插入排序的一种、冲破O(n2）的第一批算法之一。
它会优先比较距离较远的元素
区别
希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
希尔排序（缩小增量排序）
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。
计数排序
桶排序(Bucket sort)是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
工作原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序。
桶排序
基数排序也是非比较的排序算法
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
基数排序基于分别排序，分别收集，所以是稳定的。
基数排序（卡片排序）
基数排序：根据键值的每位数字来分配桶
计数排序：每个桶只存储单一键值
桶排序：每个桶存储一定范围的数值
这三种排序算法都利用了桶的概念
基数排序 vs 计数排序 vs 桶排序
排序算法（10种）
说明：顺序查找适合于存储结构为顺序存储或链接存储的线性表。
基本思想：顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。
顺序查找
说明：元素必须是有序的，如果是无序的则要先进行排序操作。
基本思想：也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。
注：折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。——《大话数据结构》
二分查找
基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。
注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。
插值查找
基本思想：也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。
斐波那契查找
基本思想：二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。
二叉查找树（BinarySearch Tree，也叫二叉搜索树，或称二叉排序树Binary Sort Tree）或者是一棵空树，或者是具有下列性质的二叉树： 1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 3）任意节点的左、右子树也分别为二叉查找树。
二叉查找树性质：对二叉查找树进行中序遍历，即可得到有序的数列。
二叉树查找算法
2-3查找树的性质： 1）如果中序遍历2-3查找树，就可以得到排好序的序列； 2）在一个完全平衡的2-3查找树中，根节点到每一个为空节点的距离都相同。（这也是平衡树中“平衡”一词的概念，根节点到叶节点的最长距离对应于查找算法的最坏情况，而平衡树中根节点到叶节点的距离都一样，最坏情况也具有对数复杂度。）
平衡查找树之2-3查找树（2-3 Tree）
基本思想：红黑树的思想就是对2-3查找树进行编码，尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型，红色链接，他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的，使用红色链接的两个2-nodes来表示一个3-nodes节点，并且向左倾斜，即一个2-node是另一个2-node的左子节点。这种做法的好处是查找的时候不用做任何修改，和普通的二叉查找树相同。
红黑树是一种具有红色和黑色链接的平衡查找树，同时满足：红色节点向左倾斜一个节点不可能有两个红色链接整个树完全黑色平衡，即从根节点到所以叶子结点的路径上，黑色链接的个数都相同。
红黑树的性质：整个树完全黑色平衡，即从根节点到所以叶子结点的路径上，黑色链接的个数都相同（2-3树的第2）性质，从根节点到叶子节点的距离都相等）。
平衡查找树之红黑树（Red-Black Tree）
树表查找
说明：分块查找又称索引顺序查找，它是顺序查找的一种改进方法。
算法思想：将n个数据元素\"按块有序\"划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须\"按块有序\"；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……
分块查找
我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素\"分类\"，然后将这个元素存储在相应\"类\"所对应的地方。但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了\"冲突\"，换句话说，就是把不同的元素分在了相同的\"类\"之中。后面我们将看到一种解决\"冲突\"的简便做法。 总的来说，\"直接定址\"与\"解决冲突\"是哈希表的两大特点。
哈希表
哈希函数的规则是：通过某种转换关系，使关键字适度的分散到指定大小的的顺序结构中，越分散，则以后查找的时间复杂度越小，空间复杂度越高。
哈希函数
算法思想：哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。
哈希查找
查找算法（7种）
就是要减少不必要的回溯
不必要的回溯是由模式串（就是去要匹配的字符串）决定的，不是由目标（被匹配的字符串）决定的。
KMP算法（看毛片算法）
最简单的反模式匹配算法
需要反复的回溯到前面进行再次匹配
BF(BoyFriend）算法
定义：查看字符长1中有没有和字符串2相同的字符串片段。
模式匹配算法
算法
概要
零个就代表时空表。
有序的说的是数据元素是由顺序的。
定义：有零个或者多个数据元素组成的有序序列。
前驱和后继：a的前驱是a-1，a的后继就是a+1；并且有且只有一个前驱和后继。
定义：是指一组性质相同的值的集合及定义在着个集合上的一些操作的总称。
定义：是指一个数据模型及定义在该模型上的一组操作，有一组特定的特性。
抽象数据类型
原子类型：就是不可再分割的一些数据类型。如：整形、浮点型、字符型等。
结构类型：由若干个类型组成的，是可以在分开的类型。
按照取值的不同可分为
数据类型
基本方法（函数）
定义：就是再物理地址中申请连续的存储单元，然后把这些相同的数据类型有序的放入到这些存储单元中。
特点：再存，读数据时不管在那个位置时间复杂度都为O(1)；再插入和删除时不管在什么位置时间复杂度都是O(n); 所以 比较适合数据元素稳定，不经常进行插入和删除操作，反而适合更多读取和存储操作的应用。
不需要为表之间元素之间的逻辑关系而增加存储容量；
可以快速存取表中任何位置的元素。
优点
插入和删除操作需要移动大量元素；
当线性表的长度变化大时，就难以确定存储空间的容量；
容易造成空间碎片
缺点
例子：数组。
顺序存储结构
定义：是用任意一组存储单元来存储线性表的数据元素，这一组存储单元可以存在于内存中任何空闲的位置。
特点：每个存储单元（节点）除了存储数据（数据域）还要存储其后继元素的位置信息（指针域，里面的信息被称为指针或者链）。
链式存储结构
顺序存储结构用一段连续的存储单元，一次存储线性表的元素。
单链表是链式存储结构，用任意一组存储单元存储线性表的元素。
存储分配方式
顺序存储是O(1)。
单链表是O(n)。
查找
顺序存储需要平均移动一半所以时间复杂度为O(n)。
插入和 删除
时间性
顺序存储结构需要预先分配空间大小，分小了溢出，分多了空间浪费。
单链表是链式的存储结构，可以不预先分配大小，灵活方便，只要有空间就行。
空间分配
顺序存储和单链表（链式结构）的优缺点
线性表的存储结构的定义
单链表
空链表
定义：就是每个节点只有一个指针域。
是链表指向第一个节点的指针，如果该链表有头节点，那么该指针就是指向头节点的指针。
头指针具有标识的作用，所以常以头指针冠以链表的名字（指针变量的名字）。
无论链表是否为空，头指针均不为空。
头指针时链表的必要元素。
头指针
头节点是为了操作的统一和方便而设立的，放在第一个节点之前，数据域一般无意义（可以存储链表的长度）。
有了头节点再第一个节点前插入或者删除第一个节点都会和其他的节点操作一致。
头节点不是必要的元素。
头节点
头指针和头节点
C语言代码节点定义示例
插入思路
删除思路
整表删除
特点：读取的时间复杂度为O(n);插入和删除的复杂度O(1);
优点：对于每次插入和删除操作越频繁越多的操作单链表的优势就会更加明显。
头插法：就是新插入的元素插在最前面。优点：插入简单。缺点：插入的顺序和逻辑顺序不同。
尾插法：就是新插入的元素插在最后面。
定义：单链表得最后一个节点指向头节点。
注意：判断空表是Head的Next是否为head。
单循环链表
定义：就是有两个指针指向前驱节点和后继节点。
插入
删除
双向循环链表
注意：循环链表不一定有头节点
循环链表
单链表只能向后指，而循环链表可以向前向后
动态链表
创建
注意
优点和缺点
静态链表
静态链表和动态链表是线性表链式存储结构的两种不同的表示方式。
静态链表是用类似于数组方法实现的，是顺序的存储结构，在物理地址上是连续的，而且需要预先分配地址空间大小。所以静态链表的初始长度一般是固定的，在做插入和删除操作时不需要移动元素，仅需修改指针。
动态链表是用内存申请函数（malloc/new）动态申请内存的，所以在链表的长度上没有限制。动态链表因为是动态申请内存的，所以每个节点的物理地址不连续，要通过指针来顺序访问。
动态链表和静态链表的区别
链表
线性表
定义：是在一端进行插入操作，在另一端进行删除操作的一个线性表。先进先出的线性表。
插入在尾部进行
出队在头部进行
队列的操作
在出队操作时，每个元素都要往前进行移动，时间复杂度高，不太实用。
当队头为0时
可能会造成越界（越过最大值）。
当队头是指针时
实际上不存在环形的存储结构，可以用顺序表模拟出来。
循环队列
销毁队列：因为队列一般是动态的存储在内存，所以一般不使用时要进行及时的清除所占用的内存。
链式存储结构（常用）
结构
队列
定义：是一种线性结构，先进后出，后进先出，他要求删除（出栈，弹栈）和插入（进栈、压栈）操作在栈尾完成。表头称为栈底，表尾称为栈顶。当栈中没有任何数据时被称为空栈。
都是在栈顶进行。
删除和插入
清空：就是将栈中的数据清空，就是将栈顶指向栈尾，不改变数据的物理结构。
销毁：就是将栈中数据占物理内存进行清空。
栈的操作
s.top-s.base(两个数据必须是同一个数据类型、指针不能加)
计算栈的当前容量
顺序存储结构（常用）
计数器中会有一个指针指向栈顶，一个int类型的Count变量记录栈的当前容量。
栈
定义：堆可以被看成是一棵树，如：堆排序。
堆
堆是在程序运行时，而不是在程序编译时，申请某个大小的内存空间。即动态分配内存，对其访问和对一般内存的访问没有区别。
栈就是一个桶，后放进去的先拿出来，它下面本来有的东西要等它出来之后才能出来。（后进先出）
堆、栈、队列之间的区别是？
栈和堆、队列
节点是一个包含数据元素和若干指向其子树的分支。节点所拥有的子树数成为节点的度（Degree）。
度为0的节点被称为叶节点（Leaf）或者终端节点。
度不为0的节点称为非终端节点或者分支节点。除了根节点外，分支节点也被称为内部节点。
树的度是树内个节点的度的最大值。
节点分类
结点的子树的根成为该结点孩子节点（Child）。相应的该结点也称为孩子节点的双亲（Parent）节点。
同一个双亲的结点成为兄弟（Sibling）节点。
结点的祖先是从根到该结点所经分支上的所有结点。相应的以某结点为根的子树中的所有结点都是该结点的子孙节点。
节点间关系
从根开始定义起为第一层，其孩子结点为第二层，孩子的孩子结点为第三层，以此类推。
结点的层次（Level）
双亲在同一层的结点被称为堂兄弟结点。
堂兄弟结点
树中结点的最大层次被称为树的深度
深度（Depth）或者高度
是m（m>=0）棵互不相交的树的集合。
森林（Forest）
其他概念
概念
在每个结点中除了数据外，附设一个指针指示器指向其双亲结点在数组中的位置
双亲表示法
把每个结点的孩子结点排列起来，以单链表作为存储结构，则n个结点就有n个单链表，叶结点的单链表为空表。然后n个头指针又组成一个线性表，采用顺序存储的结构，存放在一个一维数组中。
双亲孩子表示法：就是在孩子表示法的基础上加上双亲指针（不要单链表）。
孩子表示法
任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟结点。
孩子兄弟表示法
存储结构的设计是一个非常灵活的过程。一个存储结构设计的是否合理，取决于基于该存储结构的运算是否合适，是否方便，时间复杂度好不好等等。
多重链表表示法：就是在每个结点中除了数据域外，还要有很多的指针域，其中每一个指针域指向一棵子树的根节点。
树的存储结构
第一个数据元素：无前驱
最后一个数据元素：无后继
中间元素：一个前驱一个后继
线性结构
根结点：无双亲，唯一。
叶结点：无孩子，可以多个
中间节点：一个双亲多个孩子。
树结构
线性结构和树结构的不同
如果将树中结点的各个子树看成从左至右是有次序的，不能交换，则称为有序树，否则就是无序树。
有序树和无序树
是n（n>=0）个结点的有限集合，该集合或者为空集合（称为空二叉树），或者有一个根节点和两颗互不相交的、分别称为根节点的左子树和右子树的二叉树组成。
所有的结点都只有左子树的二叉树被称为左斜树；所有的结点都只有右子树的二叉树被称为右斜树，这两者统一被称为斜树。
斜树
在一棵二叉树中，如果所有的分支结点都存在左子树和右子树，并且所有的叶子都在同一层上，这样的二叉树就被称为满二叉树。
叶子结点只能出现在最后一层，出现在其他层就会不平衡。
非叶子结点的度必须是2。
在同样深度的二叉树中，满二叉树的结点和叶子节点都是最多的。
特点
满二叉树
对于一个具有n个节点的二叉树按层序编号，如果标号为i（1<=i<=n）的结点于同样深度的满二叉树中的编号为i的结点在二叉树中位置完全相同，则这颗二叉树称为完全二叉树。
叶子结点只能出现最下两层。
最下层的叶子结点只能出现在最左侧连续的位置。
倒数二层，若有叶子结点，一定出现在右部连续的位置。
如果结点度为1，则该结点只有左孩子，既不存在只有右子树的情况。
同样的结点数的二叉树，完全二叉树的深度最小。
示例
完全二叉树
特殊二叉树
每个结点最多有两棵子树，所以二叉树不存在度大于2的结点。
左子树和右子树是有顺序的，次序不能颠倒。
即使一个结点只有一棵树，也要区分是左子树还是右子树。
空二叉树
只有一个根节点
根节点只有左子树
根节点只有右子树
根节点既有右子树也有右子树
五种基本形态
在二叉树的第i层上至多有2^(i-1)-1个结点（i>=1）。
深度为k的二叉树至多有2^k-1结点（k>=1）
对任何一棵树二叉树T，如果其终端结点数为n0，度为2的结点数为n1，则n0=n1+1
具有n个结点的完全二叉树的深度为[log2N]+1([x]指的是不大于x的最大整数)
性质
顺序存储结构：一个完全二叉树，按照相应的下标对应其相同的位置，对于一般的二叉树就是相对于完全二叉树没有的结点就用^来表示
二叉链表：二叉树每个结点最多有两个子结点，所以给他设计一个数据域与两个指针域，这样的链表叫做二叉链表。
二叉树的存储结构
定义：是从根节点出发，按照某种次序依次访问二叉树中得所有结点，使得每个结点都被访问一次。
前序遍历：根左右
中序遍历：左根右
后序遍历：左右根
层序遍历：一层一层一次访问，每层是从左到右。
方法
遍历二叉树
当知道二叉树的中序遍历时，在知道前序遍历或者后序遍历中的一个就可以推导出二叉树的形状。
当不知道二叉树的中序遍历时无法推导出二叉树的形状。
二叉树推导
二叉树（Binary Tree）
指向前驱和后继的指针称为线索，加上线索的二叉链表。
定义
二叉树以某种次序遍历使其变为线索二叉树的过程称作线索化。
线索化的过程就是在遍历的过程中修改空指针。
线索化
如果所用的二叉树需要经常遍历或者查找节点时需要某种遍历序列中的前驱节点和后继节点，那么采用线索二叉链表的存储结构就是非常不错的选择。
适用的情况
线索二叉树
树的分类
树
数据结构
普通方法：就是先遍历得到长度n，然后再遍历n/2次得到中间节点。
高级方法：设置一个快指针和慢指针，快指针是慢指针得2倍，这样快指针到达末尾时慢指针刚好到中间。 快指针就是Next2次，慢指针就是Next1次。
快速找到未知长度单链表的中间节点？
面时题
约瑟夫问题
循环链的方式解决
魔法师发牌
拉丁方阵
解决方法：递归，就是先将前面的63个金片按照顺序排好在一个宝石针上然后再把第64个放在另一个宝石针上，再将那63个拍好的按照之前的办法再放到这个针上就行。
汉诺塔
八皇后问题
经典问题
数据结构和算法
0 条评论
回复 删除
下一页
