数据结构与算法
2020-03-13 18:11:51 1 举报AI智能生成
数据结构
作者其他创作
大纲/内容
数据结构绪论
定义
是相互之间存在一种或多种特定关系的数据元素的集合
基本概念与术语
组成
数据
描述客观事物的符号
数据元素
组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理，也被称为记录中
数据项
一个元素可以有若干个数据项组成，数据项是不可分割的最小单位
数据对象
性质相同的数据元素的集合，是数据的子集
数据结构
相互之间存在一种或多种特定关系的数据元素的集合
层级结构
数据
数据对象
数据元素1
数据项1
数据项2
数据元素2
数据项3
数据项4
逻辑结构与物理结构
逻辑结构
集合结构
集合中的数据元素除了同属一个集合外，它们之间没有其他关系
各个数据元素之间是平等的
线性结构
数据元素之间是一一对应的
树形结构
数据元素之间存在一种一对多的层次关系
图形结构
数据元素是多对多的关系
物理结构
顺序存储结构
把数据元素放在地址连续的存储单元里面
数据间的逻辑关系和物理关系一致
链式存储结构
把数据元素放在任意的存储单元里面
这组存储单元可以是连续的，也可以是不连续的
抽象数据类型
数据类型
一组性质相同的值的集合，以及定义在此集合上的一些操作的总称
抽象数据类型
指一个数学模型以及定义在该模型上的的一组操作
抽象数据类型体现了程序设计中问题的分解、抽象和信息掩藏的特性
算法
定义
解决特定问题求解步骤的描述
在计算机中表现为指令的有限序列
并且每条指令执行表示一个或多个操作
数据结构与算法的关系
数据结构用于解决数据存储问题
算法用于处理和分析数据
数据结构和算法存在“互利共赢、1+1>2”
数据结构用于解决数据存储问题
算法的特性
输入输出
算法具有零个或多个输出
有穷性
算法在执行有限步骤后，会自动结束而不会出现无限循环，且每一个步骤都在可接受的时间内完成
确定性
算法的每一步都具有确定的含义，不回出现二义性
可行性
算法的每一步都是可行的
算法设计的要求
正确性
没有语法错误
合法输入合法输出
非法输入、规定输出
刁难输入、满足要求输出
可读性
算法设计的另一个目的就是为了便于阅读、理解和交流
健壮性
非法输入能做相关处理，而不是产生异常或莫名结果
高效与低存储
算法的执行时间尽可能短
算法执行的存储空间使用尽可能低
算法效率的度量
事后统计法
设计好测试程序和数据，运行不同的算法比较时间，确定算法的效率
缺点
要先编写好算法，如果最终发现算法很糟糕，浪费时间
受计算机的硬件和软件的影响较大
设计测试数据困难(不同算法对不同规模的效率可能不一样)
事前分析估计法
在编写算法之前，根据统计方法对算法进行效率估算
影响程序执行的时间的因素
算法采用的方法、策略
编译产生的代码质量
输入数据的规模
及其执行指令的速度
评估效率的关键
基本操作的数量必须表示成输入规模的函数
函数的渐进增长
在输入规模n没有限制的情况下，只要超过一个树枝N，这个函数就总是大雨另一个函数，就称函数是渐进增长的
最高次数项的指数越大，随着n的增长，函数的结果也会增长的特别快
判断一个算法的效率时，函数中的常数项和其他的次要项通常可以忽略，至于要关注最高项即可
算法的时间复杂度
定义
全称：算法的渐进时间复杂度，建成时间复杂度
表示：T(n)=O(f(n))
推导大O阶方法
推导方法
用常数1取代运行时间中的所有加法常数
在修改后的运行次数函数中，只保留最高阶
如果最高阶项存在且不为1，去除与这个项相乘的常数
要确定算法的阶次，通常要确定某个特定语句或语句集的运行次数
常见时间复杂度(从小到大)
常数阶
常数不管是多少都记作O(1)
对数阶
O(logn)
线性阶
O(n)
nlogn阶
O(nlogn)
平方阶
O(n^2)
立方阶
O(n^3)
指数阶
O(2^n)
阶乘阶
O(n!)
..
O(n^n)
最坏情况与平均情况
最坏情况
最坏情况运行时间是一种保证
运行时间将不会再坏
除非特别指定，此处提到的运行时间都是最坏情况的运行时间
平均运行时间
计算所有情况的平均值
平均运行时间是所有情况中最有意义的，因为它是期望的运行时间
算法空间复杂度
运行算法所需要的存储空间
记作：S(n)=O(f(n)),n为问题规模，f(n)为所占存储空间关于n的函数
树
定义
树(tree)是n(n>=0)个结点的有限集，n=0时称为空树
任意一刻非空树中
有且仅有一个特定的称为根(Root)的结点
当n>1时，其余结点可分为m(m>0)个互不相交的有限集
其中灭哥哥子集合本身又是一棵树，并且称为根的子树(SubTree)
基本概念
度(Degree)
结点拥有的子树数量称为结点的度
度为0的结点称为叶结点(leaf),或终端结点
度不为0的结点称为非终端结点或分支结点
除了根结点之外，分支结点也称为内部结点
树的度是指树内各个结点的最大值
结点间关系
结点的子树的根称为该结点的孩子结点(Child)
相应的该结点称为孩子结点的双亲结点(Parent)
同一个双亲的孩子结点间互称兄弟结点(Sibling)
结点的祖先是从根到该结点所经分支上的所有结点
树的高度、深度(Depth)
树的层次
结点的层次(Level)从根开始定义
根为第一层
根的孩子为第二层，以此类推，双亲在同一层的结点互为堂兄弟(注意区分兄弟结点)
树中结点的最大层次称为树的深度或高度
有序树
树中的个结点的子树从左到右依次有序，不能互换的，则称为有序树，否则为无序树
森林
森林(Forest)是m(m>=0)棵互不相交的树的集合
树的存储结构
双亲表示法
双亲表示法
实现方法
假设使用一组连续空间存储树的结点
在每个结点由两部分组成
指针域parent
存储该结点的双亲在数组中的下边 或 在链表中的指针
数据域data
存储结点数据
根结点没有双亲，约定将指针域设为-1
扩展
为了实现不同的需求可以对应的变化结构
关注孩子结点
增加一个长子域，即结点最左边的孩子的域
关注兄弟结点之间的关系
在长子域的前提下，增加一个右兄弟域来体现兄弟关系
更复杂的需求
对应设计
原则
存储结构的设计是一个非常灵活的过程
一个存储结构的设计是否合理取决于几个因素
基于该结构的运算时间复杂度、空间复杂度
基于该结构的运算的运算是否方便
孩子表示法
实现方法
每个结点有多个指针域
每个指针域指向一棵子树的根结点
我们把这种表示方法叫做多重链表表示法
方案一
指针域的个数等于树的度
优点
树中个结点的度相差很小时，开辟的空间被充分使用的
缺点
树中各结点的度相差很大时，浪费空间，其他的指针域都是空的
方案二
每个结点指针域的个数等于该结点的度
实现
专门取一个位置来存储结点的指针域个数
其余的类似方案一
优点
充分利用了空间
缺点
增加了维护结点度的值，在运算上会带来时间上的损耗
方案三
改进方案二的缺点
把每个结点的孩子结点排列起来，以单链表存储，有n个结点则有n个孩子链表
如果是叶子结点则此单链表为空
n个头指针组成一个线性表，采用顺序存储结构，存放进一个以为数组中
实现
孩子链表的孩子结点
child
next
child
数据域，存储某个结点在表头数组中的下标
next
指针域，用来存储指向某结点的下一孩子结点的指针
表头结点
data
数据域，存储结点的数据信息
firstchild
有指针域，存储该结点的孩子链表的头指针
优点
可以查询某个结点的某个孩子，同时找到该孩子结点的兄弟结点
容易遍历整棵树，只需要遍历头节点数据即可
缺点
难以找到结点的双亲
双亲孩子表示法
实现
表头结点
data
数据域，存储结点的数据信息
parent
存储双亲结点的下标
firstchild
有指针域，存储该结点的孩子链表的头指针
孩子链表的孩子结点
child
数据域，存储某个结点在表头数组中的下标
next
指针域，用来存储指向某结点的下一孩子结点的指针
改进了双亲、孩子表示法存在的缺点
孩子兄弟表示法
场景
从树结点的兄弟角度观察
对于任意一棵树，存在下面的规律
它的结点的第一个孩子如果存在就是唯一的
该结点的右兄弟如果存在也是唯一的
实现
data
数据域
firstchild
指针域，存储该结点第一个孩子结点的存储地址
rightsib
指针域，存储该结点的有兄弟结点的存储地址
缺点
找双亲困难，但是可以参考之前的方法，加多一个指向双亲的指针域即可，但是这种思路主要还是为二叉树做准备
二叉树的定义
定义
二叉树是n(n>=0)个结点的有限集合
该集合或者为空集(称为空二叉树)，或者有一个根结点和两棵互不相交的，分别称为根结点的左子树和右子树的二叉树构成
二叉树的特点
每个结点最多只有两个子树，注意是最多两个，也可以没有
左子树和右子树的是有顺序的，不能颠倒
即时某个结点只有一个子树，也要区分是左还是右子树
二叉树的五种基本形态
空二叉树
只有一个根结点
根结点只有左子树
根结点只有右子树
根结点既有左子树又有右子树
特殊二叉树
斜树
左斜树
所有结点都只有左子树
右斜树
所有结点都只有右子树
满二叉树
所有的分支结点都存在左子树和右子树
所有叶子结点都在同一层上
简单粗暴的判断方法：高度为h，由2^h-1个节点构成的二叉树称为满二叉树。
完全二叉树
完全二叉树是由满二叉树而引出来的
深度为h的二叉树，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数(即1~h-1层为一个满二叉树)
第 h 层所有的结点都连续集中在最左边，这就是完全二叉树
二叉树的性质
在二叉树的第 i 层至多有 2^(i －1)个结点。(i>=1)
深度为 k 的二叉树至多有 2^k - 1个结点(k >=1)。
任何一棵二叉树T, 如果其叶结点数为n0, 度为2的结点数为 n2,则n0＝n2＋1。
具有 n (n>=0) 个结点的完全二叉树的深度为[log2 n]＋1
如将一棵有n个结点的完全二叉树自顶向下，同层自左向右连续为结点编号0,1, …, n-1
若i = 0, 则 i 无双亲, 若i > 0, 则 i 的双亲为i/2
如果2i>n，则结点i无左孩子，切结点i为叶子结点，否则其左孩子结点为2i
如果2i+1>n，则结点i无右孩子；否则右孩子结点为2i+1
二叉树的存储结构
顺序存储结构
实现
用一维数组存储二叉树中的结点，切结点存储的位置能体现结点之间的逻辑关系
简单来说就是：将一颗二叉树补成一棵完全二叉树来存储，否则无法确定结点之间的关系
缺点
对于非完全二叉树或满二叉树而言，会浪费空间
二叉链表
实现
二叉树每个结点最多有两个孩子
设计一个数据域data 和两个指针域分别为lchild 和 rchild
三叉链表
实现
在二叉链表的基础上增加一个指向双亲的指针
遍历二叉树
定义
从根结点出发，按照某种次序依次访问二叉树中所有节点
每个结点访问一次且仅被访问一次
遍历方法
深度遍历
前序遍历
过程
根结点 ---> 左子树 ---> 右子树
中序遍历
过程
左子树---> 根结点 ---> 右子树
后续遍历
过程
左子树 ---> 右子树 ---> 根结点
实现
递归
非递归
广度遍历
层次遍历
只需按层次遍历即可
过程
实现
推导遍历结果
前序+中序
后续加中序
二叉树的建立
为了让每个节点确认是否有左右孩子，针对普通的二叉树进行扩展
将二叉树中的每个节点的空指针引出一个虚节点，赋值为特定值，比如‘#’
通过上述方式处理后的二叉树为原二叉树的扩展二叉树
线索二叉树
原理
对于某些二叉树而言，并不是所有的指针域都被充分的利用，存在许多空指针域的存在
对于有n个节点的二叉链表，有2n个指针域，一共有n-1个分支数，也就是存在2n-(n-1)=n+1个空指针域
对于我们的遍历算法，在遍历结束后我们能轻易知道节点前驱后继节点，但是在未遍历，我们只知道左右节点，不一定能知道前驱或后继节点
我们可以利用这些空指针域，指向某种遍历方式下执行前驱或后继节点
定义
我们吧指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，对应的二叉树称为线索二叉树
线索化
对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化
结构设计
此处存在一个问题：就是某一节点的指针域是指向它的孩子节点呢还是线索呢？
对此需要为区分它们增加一个区分标志：ltag和rtag（只存放0，1）
为0时候，存放孩子节点，为1时存放前驱或后继
实现
线索二叉树的实现
线索化的过程就是在遍历的过程中修改指针的过程（具体实现后续补上）
树、森林与二叉树的转换
树转换二叉树
步骤
加线：所有的兄弟节点之间加一条连线
去线：对于每个节点只保留它与第一个孩子节点的连线，去掉与其他孩子的连线
调整：以树的根节点为轴心，将树顺时针旋转一定角度，其中第一个孩子为二叉树的左孩子，兄弟节点转换过来为右孩子
森林转二叉树
步骤
将每一棵树转成二叉树
第一棵二叉树不动，一次把后一棵二叉树的根节点作为前一刻二叉树根节点的右孩子节点
二叉树转树
步骤
加线：若节点的左孩子存在，将左孩子节点所有右孩子节点与该结点连接起来
去线：删除原二叉树中所有节点与其右孩子节点的连线
调整
森林转二叉树
步骤
前提：二叉树的根节点有右孩子
从根节点开始，若在右孩子，删除右孩子的连线
对分离的右孩子执行相同的操作
将分离出来的二叉树转换成树即可
树与森林的遍历
树的遍历
先根遍历
先访问树的根节点，然后依次遍历跟的每棵子树
后根遍历
先一次遍历每棵子树，在遍历根节点
森林的遍历
前序遍历
先根方式遍历森林中的第一棵树
再依次如上方法遍历剩余的森林
后续遍历
后根方式遍历森林中的第一棵树
再依次如上方法遍历剩余的森林
赫夫曼树与赫夫曼编码
赫夫曼树
定义与原理
路径长度
从树中一个节点到另一个节点之间的分支构成两个节点之间的路径，路径上的分支树木就叫做路径长度
树的路径长度
树的路径长度就是从树根到每一个即诶单的路径长度只之和
带权路径长度
考虑到权值，那么节点的带权路径长度为该节点到树根之间的路径长度与该结点权值的乘积
树的带权路径
树的带权路径长度为所有叶子节点的带权路径长度之和（WPL）
哈夫曼树
带权路径WPL最小的二叉树称为赫夫曼树，也叫做最优二叉树
生成哈赫夫曼
将所有节点按权值从小到大排序
去最小的两个节点作为新节点的孩子节点，权值小的为左节点，新节点N的权值为孩子节点权值之和
将新的节点N替换它的连个子节点，在按照之前的方法用N参与排序，重复上面的过程，直到所有节点处理完毕
赫夫曼编码
以每个字符出现的次数或平率为带权节点构建一棵赫夫曼树
将赫夫曼树做分支的权值置0，右分支权值置1
从根节点到叶子节点所经过的路径分支组成的0、1序列称为该结点的编码，即赫夫曼编码
图
定义
图的定义
一般表示为G(V,E)，其中G表示图，V是图G的顶点集合，E是图G的边集合
图(Graph)由顶点的有穷非空集合和顶点之间的边的集合组成
图的相关定义
无向边
若顶点vi和vj之间的边没有方向，则称这条边为无向边，用无序偶对(vi,vj)表示
有向边
若顶点vi和vj之间的边有方向，则称这条边为有向边或弧(Arc)，用有序偶对<vi,vj>表示
其中vi称为弧尾(Tail)，vj称为弧头(head)
若一个图的任意两个顶点之间都是有向边，则称该图为有向图(Directed graphs)
简单图
不存在顶点到其自身的边
同一条边不重复出现
完全无向图
在无向图中，任意两个顶点之间都存在边
n个顶点完全无向图有n*(n-1)/2条边
完全有向图
在有向图中，任意两个顶点之间都存在方向相反的两条弧
n个顶点完全有向图有n*(n-1)条边
稀疏、稠密图
很少边或很少弧的图称为稀疏图，反之为稠密图
这个概念比较模糊，是一个主观概念
网
有些图的边或者弧带有数字，这些数字叫做全(Weight)
带权的图通常称为网
子图
假设有两个图G1(V,{E}),G2(V1,{E1}),如果V1是V的子集，且E1是E的子集 ，则称G1为G的子图
顶点和边的关系
线性表
定义
零个或多个数据元素的有限序列
线性表元素的个数n(n>0)定义为线性表的长度，当n=0时，称为空表
在复杂的线性表中，一个数据元素可以有若干个数据项组成
物理结构
顺序存储结构
定义
用一段地址连续的存储单元依次存储线性表的数据元素
存储方式
需要的属性
存储空间的起始位置
线性表的最大存储容量：数组的长度maxSize
线性表当前长度：length
插入与删除
插入
插入位置 i 不合理，抛出异常
线性表的长度大于数组的长度，抛出异常或动态扩容
将从第 i 个位置到最后的元素往后移动一个位置
将要插入的数据元素插入第 i 个位置
线性表长度加1
删除
删除位置 i 不合理，抛出异常
去除删除元素
将从第 i +1 位置到最后的元素往前移动一个位置
线性表长度减1
时间复杂度
读取数据
无论在哪个位置都是O(1)
插入或删除
最好
O(1)
平均
O(n)
优缺点
优点
无须为元素表之间的逻辑关系额外增加存储空间
可以快速的取出表中任意位置的元素
缺点
插入、删除需要移动大量的元素
线性表的长度变化较大的时候，难以确定存储空间的容量
造成存储空间的碎片
链式存储结构
单链表
定义
为了表示数据元素 i 与 i+1 之间的逻辑关系，对数据元素 i 来说，除了存储本身数据外，还要存储其直接后继的信息
存储数据元素信息的部分称为数据域
存储直接后继位置信息的部分称为指针域，指针域中存储的信息称作指针或链
数据域和指针域组成的数据叫做节点
由n个节点连接成一个链表称为线性表的链式存储结构
每个节点只包含一个指针域的称为单链表
头节点与头指针
头指针
链表中的第一个节点的存储位置
若链表有头节点，则指向头节点的指针
头指针具有标识作用，常用头指针冠以链表的名字
无论链表是否为空，头指针均不为空，头指针是链表的必要元素
头节点
单链表的第一个节点前附设一个节点称为头节点
头节点是为了操作的统一和方便而设立的，放在第一个元素的节点之前
有了头节点，在第一个元素之前插入和删除第一个节点的操作就统一了
头节点不是链表的必要元素
单链表的读取
从头开始遍历，直到找到为止
插入与删除
插入
场景
单链表第i个数据插入结点 data=e
步骤
声明一个结点p指向链表的第一个结点，初始化j(计数器)从1开始
当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，此时j也相应的+1
未找到 i
若到了链表末尾p为空，说明第i个元素不存在（此时j<i,指定i大于链表的长度）
插入失败
找到 i
查找成功，在系统中生成一个空节点s
将数据元素e赋值给s , s->data=e
按顺序执行：s->next=p->next;p->next=s
插入成功
删除
场景
删除单链表第i个结点
步骤
声明一个结点p指向链表的第一个结点，初始化j(计数器)从1开始
当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，此时j也相应的+1
未找到 i
若到了链表末尾p为空，说明第i个元素不存在（此时j<i,指定i大于链表的长度）
删除失败或不需要删除
找到 i
查找成功
将要删除分结点q的后继结点接到此时p->next
执行语句：p->next=q->next
可选
将q->data赋值给e,作为返回值
释放q结点（跟语言有关）
整表创建
头插法
声明一个结点p
初始化一个空链表L
L的头节点指针指向NULL，即创建一个带头结点的单链表
循环操作
生成一个新的结点赋值给p
将p的后继节点指向第一个数据结点；p->next=L->next
将头节点的后继指向p；L->next=p
尾插法
声明一个结点p,因为尾插法，p为最后一个元素，所以：p->next=NULL
初始化一个空链表L
L的头节点指针指向NULL，即创建一个带头结点的单链表
循环操作
遍历链表L,知道某个结点p有p->next=NULL
将结点q插入结点p的后面；p->next=q
整表删除
声明两个结点q、p
将第一个结点赋值给p
循环操作
将p的下一个结点赋值给q；q->p.next
释放p
将q的值赋值给p，p=q
释放头节点
静态链表
定义
是一个数组：数组的每个元素由两个数据域组成；分别是data、cur
data:数据域，存放数据元素，通常是我们需要处理的数据元素
cur:相当于单链表中的next指针，此处存储的是后继元素在数组中的下表
插入
删除
优缺点
优点
插入和删除操作不需要改动游标，不需要移动元素
解决了顺序存储结构中的插入和删除操作需要移动大量元素的缺点
缺点
依旧存在连续存储分配表长难以确定的问题
失去了顺序存储结构随机存取的特性
循环链表
定义
将单链表中的终端节点的指针域由NULL改为头节点，使得整个单链表形成一个环
这种头尾相接的单链表称为但循环链表，简称循环链表
解决了如何从任意一个结点出发访问到链表的全部节点的问题
几个常见操作
O(1)访问最后一个结点
合并两个循环链表
双向循环列表
定义
在单链表的每个结点中，在设置一个指向其前驱结点的指针
此时一个结点有两个指针域（一个指向后一结点，一个指向前一结点），还有一个数据域三部分
常用操作
插入
需要更新两个指针变量
删除
需要更新两个指针变量
单链表与顺序存储结构的对比
单链表与顺序存储结构的对比
存储分配方式
顺序存储结构
采用一段连续的存储单元依次存储线性表的数据元素
单链表
采用一组任意的存储单元存储线性表的数据元素
时间性能
查找
顺序存储结构
O(1)
单链表
O(n)
插入、删除
顺序存储结构
平均需要移动一般的元素；O(n)
单链表
在算出某元素的指针位置后，插入和删除都是O(1)
空间性能
顺序存储结构
需要与分配存储空间，大了浪费，小了溢出
单链表
不需要预先分配内存，数据元素数量也没有限制，只要内存吃得下
需要额外的空间存储指针数据
使用场景
顺序存储结构
频繁查找，较少插入和删除
实现知道数据元素的个数的场景
单链表
频繁插入和删除，较少查找
数据元素的个数变化较大或无法确定的场景
栈与队列
定义
栈
限定仅在表尾进行插入和删除操作的线性表
队列
限定至于许一端进行插入操作，在另一端进行删除操作的吸纳性表
栈
说明
允许插入和删除的一点称为栈顶(top)
另一端称为栈底(bottom)
不包含任何数据元素的栈称为空栈
栈又被称为后进先出(Last In First Out)的线性表,简称LIFO结构
操作
插入
叫做进栈、入栈、压栈
push
删除
叫做出栈、弹栈
pop
栈的顺序存储结构
实现
栈是线性表的特例，栈的顺序存储就是线性表顺序存储的简化，简称顺序栈，用数组实现
下标为0的一端作为栈底
定义一个top变量只是栈顶元素在数组中的位置
进栈操作
场景：元素e 入栈s，s由数组data；栈顶top组成
步骤
s->top==(maxsize-1) ？
是
栈满，进栈失败
否
s->top=top++
s->data[s->top]=e
出栈栈作
栈s由数组data；栈顶top组成，弹出栈顶元素
步骤
s->top==-1？
是
栈空，弹出失败
否
e=s-data[s->top]
s->top--
两栈共享空间
场景
栈只允许进栈和出战、不存在插入和删除的时候移动数据的问题
但是，实现必须确定数组存储空间的大小，空间不够了，需要手动扩容
对于两个相同类型的栈，可以通过共享空间的方式，利用其事先开辟的存储空间进行操作
适用于两个栈的空间需求有相反的关系时候，一个增长、一个减少的情况
实现
数组有两个端，0 和 数组长最大下标maxIndex
有两个栈s1,s2,其中s1的栈底为0，s2的栈底为maxIndex
入栈、出栈
入栈时，往中间延伸，
出栈时向，各自栈底移动
极端条件
栈满情况
(s1->top++)=s2->top
(s2->top--)=s1->top
特殊情况
s2->top=maxIndex+1 且s1->top=maxIndex
此时s2栈空，s1栈满
s1->top=-1 且 s2->top = 0
此时s1 栈空，s2栈满
栈的链式存储结构及实现
定义
栈的链式存储结构，简称链栈
实现
将栈顶放在链表的头部
一般来说，因为有了栈顶在头部，所以单链表的头结点在链表中就不需要
一般来说，链栈是不会出现栈满的情况
对于空栈而言，top=null
进栈操作
场景
新节点s，其中data 为e ，top 为栈顶指针
步骤
s->next=top
top=s
出栈操作
场景
弹出栈顶元素p,返回其值e
步骤
e=top.data
top=top.next
栈的应用
递归
定义
一个直接调用自己或通过一系列的调用语句间接地调用自己的函数叫做递归函数
每个递归定义必须至少有一个条件满足的时候，递归停止，即不再引用自身而是返回退出
递归与迭代
递归
使用的是选择结构
递归是程序结构更清晰、间接、更易读
会建立函数的副本，耗费大量的时间和内存
迭代
使用的是循环结构
一般逻辑较递归复杂，可读性稍差
不需要反复的调用函数和占用额外的内存
斐波那契数列的实现
1，1，2，3，5，8，11...
前两项之和构成了后一项
栈在递归中的使用
递归的过程退回的顺序是它前进顺序的逆序
在退回的过程中，需要执行某些操作，包括恢复之前过程中存储起来的某些数据
这种先存储数据，然后又以逆序的方式恢复这些数据，恰好符合栈的特点
四则运算表达式求值
后缀表达法
定义
一种不需要括号的后缀表达法，称为逆波兰
案例
9+(3-1)*3+10/2 ==> 9 3 1 - 3 * + 10 2 / +
中缀转后缀
从左到右遍历中缀表达式的每个数字和符号
遇到数字就输出，成为中缀表达式的一部分
遇到符号，判断其与栈顶符号的优先级
若为右括号或优先级高于栈顶符号，则栈顶符号依次出栈并输出（如果是右括号，则匹配到做括号为止，此时要注意后续的优先级）
并将当前符号入栈，直到输出最后的后缀表达式为止
计算规则
遇到数字进栈
遇到符号，将栈顶的两个数字出栈进行计算
将计算的结果入栈
一直到最后得出结果
队列
定义
只允许在一端仅从插入操作，在另一端进行删除操作的线性表
先进先出(FIFO)
允许插入的一端叫做队尾
允许删除的一端叫做队头
队列的顺序存储结构
实现
假设一个队列有n个元素，需要建立一个大于n的数组
下标为0的一端为队头
入队操作
在队尾插入一个元素，不需要移动元素，时间复杂度O(1)
出队操作
下标为0的元素出队，其他元素往前移动一个位置，时间复杂度O(n)
存在问题
常规的顺序存储结构在出队的时候，需要移动所有的元素，这是一个非常耗资源的操作
解决方案
如果不限元素必须存储在数组的前n个单元，那么出队的效率会大大增加
为了避免只有一个元素的时候，队头队尾重合处理麻烦
引入两个指针 front：指向队头、rear：指向队尾的下一个位置
当front=rear时，说明队列为空
此时还有一个问题
使用过程中，队头、队尾都是向后移动
数组前面的为止由于出队而空出
数组后面的位置由于入队而被占用，此时可能出现队尾到了数组最后的位置，而数组前面的位置没有使用的情况，这种现象叫做假溢出
循环队列
定义
解决假溢出的方法就是后面满了，就再从头开始，也就是头尾相连接的循环
我们把头尾相连的顺序存储结构称为循环队列
判断队满方法
设置一个flag
当front=rear 且flag=0，队空
当front=rear 且flag=1，队满
预留一个空位
判断条件
当front=rear，队空
保留一个元素空间，队满时，数组中还有一个空闲单元，假设最大尺寸QueueSize
(rear+1)%QueueSize == front 队满
(rear+1)%QueueSize != front 队未满
计算队长公式
(rear - front + QueueSize) % QueueSize
队列的链式存储结构
说明
队列的链式存储结构就是线性表的单链表
只不过他是只能尾进头出
简称链队列
实现
队头指针指向队列的头节点
队尾指针指向终端结点
入队操作
场景
结点e插入队列Q，此时的终端结点为an
步骤
遍历到队列Q的终端结点，an
an->next=e
rear=e
分支主题
队列是否为空
是
返回空信息
否
front->next->next=null?
是
rear=front
否
p=front->next
front=p->next
返回p
循环队列与链队列
时间
循环队列
O(1)
链队列
O(1)
空间
循环队列
需要实现申请空间，使用期间不释放
链队列
每次使用需要申请空间和释放空间，会额外消耗资源
空间上更灵活，但是耗资源
建议
可以确定队最大长度？
是
循环队列
否
链队列
串
定义
由零个或多个字符组成的有限序列，也叫做字符串
串中字符数目n为串的长度
零个字符的串称为空串
串的的比较
逐个字符一次对比，直到分出大小
字符串大于它的字串
串的存储结构
顺序存储结构
实现
一般用定长的数组存储
在0的位置保存字符串的长度或在末尾固定某个字符('\0')标识字符串结束
缺点
对于字符长常用的操作如：连接、操作、替换都可能超出数组的最大长度
链式存储结构
实现
一个结点可以存储一个或多个字符，未满的位置可用‘#’占位
缺点
需要根据实际情况合理选择一个结点存储字符的数量
整体上不如顺序存储灵活
模式匹配
字符串中定位子串的操作称作串的模式匹配
朴素的模式匹配算法
对主串的每一个字符作为子串的开头，与要匹配的字符串进行匹配
对主串左大循环，每个字符开头做长度为T的小循环
直到匹配成功或者全部遍历完为止
KMP模式匹配算法
说明
有一种可以大大规避重复遍历情况的模式匹配算法叫做KMP模式匹配算法
实现原理
如果T串中的首个字符与T中后面的字符均不相等
案例
如有主串S="abcdefgab",字串T="abcdex"
因为T中首字母"a"与后面的字符均不相等，所以当匹配到第六位即S[e]!=T[x]的时候，第二轮的时候不需要从S[b]开始匹配
我们只需要从第六位S[f]开始匹配T[a]
直到匹配成功或遍历到末尾
如果T串中的首个字符与T中后面的字符存在相等的情况
案例
如有主串S="abcabcabc",字串T="abcabx"
第一次匹配到第六个位置S[6]!=T[6]
因为T[1]=T[4];T[2]=T[5]，所以S[1]=S[4];S[2]=S[5]
因为下一轮匹配的时候可以直接从S[6]开始匹配T[3]
直到匹配成功或遍历到末尾
next 数组值的推导
0 条评论
下一页
