数据结构与算法
2021-12-17 09:31:40 26 举报AI智能生成
数据结构基础
作者其他创作
大纲/内容
树
查找
图
排序
线性表(List)
线性表(List)的定义
零个或多个数据元素的有限序列
线性表的存储结构
顺序存储
链式存储
单链表
双链表
循环链表
广义表(Lists)
栈与队列
栈(Stack)
栈的定义
栈是限定仅在表尾进行插入和删除操作的线性表
栈的存储结构
顺序存储
数组实现
栈顶top指针从0开始(看个人习惯)
两栈共享空间
前提：相同数据类型的栈
操作
栈满：top1+1=top2
入栈：需要插入元素和栈号参数(指定入哪个栈)
出栈
代码
应用
通常当两个栈的空间需求有相反关系时(一个栈增长时另一个栈在缩短的情况)，
就像买卖股票一样，你买入时，一定有一个你不知道的人在做卖出操作，有人赚钱就一定有人赔钱
就像买卖股票一样，你买入时，一定有一个你不知道的人在做卖出操作，有人赚钱就一定有人赔钱
链式存储
链栈
栈顶放在单链表头部，无需头结点
top指针就是头指针
top指针就是头指针
操作
栈的应用
浏览器的后退键、编辑软件的撤销键(undo)
单调栈
应用场景：找到每一个数左边(右)离它最近且比它小(大)的数
原理：剔除一些永远用不到的元素(逆序关系)，剩下单调的元素
代码
递归
斐波那契数列
四则运算表达式求值
队列(Queue)
队列的定义
队列是只允许在一段进行插入操作，而在另一端进行删除操作的线性表
队列的存储结构
顺序存储
普通队列
数组实现
算法上一般队列装的是索引值，而不是元素值
而且写算法时我们只考虑移动指针，不用考虑元素出队后真正的删除
这样出队入队时间复杂度都是O(1)
而且写算法时我们只考虑移动指针，不用考虑元素出队后真正的删除
这样出队入队时间复杂度都是O(1)
普通队列，习惯tail从-1开始，head从0开始，head==tail时，队列内有一个元素
在上面两点的基础下
当前队列的长度就为tail-head+1
如果head，tail都从0开始，队长为tail-head
当前队列的长度就为tail-head+1
如果head，tail都从0开始，队长为tail-head
这里队列存放的是元素值，如果队头出队后，队列中所有元素都得向前移动，时间复杂度为O(n)
循环队列
如果普通队列队头出队后不将后续元素往前移动，那么会出现"假溢出"现象
如果还想要O(1)的时间复杂度，又不想出现这种情况，那么就需要循环队列来实现
如果还想要O(1)的时间复杂度，又不想出现这种情况，那么就需要循环队列来实现
定义：头尾相接的顺序存储结构称为循环队列
循环队列出现head==tail的情况会有两种
1、队列为空
2、队列满
1、队列为空
2、队列满
如何处理：
方法一：设置一个标志变量flag，当head==tail，且flag==0，队列为空
当head==tail，且flag==1，队列满
方法二(重点)：修改队列满条件，保留一个元素的空间
方法一：设置一个标志变量flag，当head==tail，且flag==0，队列为空
当head==tail，且flag==1，队列满
方法二(重点)：修改队列满条件，保留一个元素的空间
操作
初始化
注意：head指针指向队头，tail指针指向队尾元素的下一位
指针指的是索引值
指针指的是索引值
入队
出队
队长
通用的计算队列长度公式
(tail-head+QueueSize)%QuqueSize
(tail-head+QueueSize)%QuqueSize
队满
条件：(tail+1)%QueueSize==head
因为head可能比tail小，可能比tail大，可能是相差一个位置为满，但也可能相差整整一圈
如上图(4+1)%5==0,(1+1)%5==2
因为head可能比tail小，可能比tail大，可能是相差一个位置为满，但也可能相差整整一圈
如上图(4+1)%5==0,(1+1)%5==2
链式存储
链队列：其实就是线性表的单链表，只不过只能尾进头出
带头结点
带头结点
操作
队空
入队
出队
队长
链队列和循环队列比较
队列的应用
单调队列
应用场景：窗口滑动
原理和单调栈一致
都是去除一些永远用不到的元素
使得整个队列(栈)为单调递增(递减)
都是去除一些永远用不到的元素
使得整个队列(栈)为单调递增(递减)
思想
代码
思考的问题
为什么队列储存元素的索引而不是数值本身
为什么四行代码的顺序不能颠倒
为什么队列存储了窗口内从最小值到队尾元素的一个升序子序列
为什么维持窗口长度的那行代码使用了if，而不是whlie
使用STL库
串(string)
串的定义
串是由零个或多个字符组成的有限序列，又叫字符串
本质上是一种线性表扩展，只不过针对内容做出了限制
串的存储结构
顺序存储
数组实现
链式存储
链串：
与线性表类似，不过一个结点对应一个字符，会存在很大的空间浪费
一般一个结点存放多个字符(即块链结构)，若一个结点未被占满时，可以用"#"或其他非串值字符补全
与线性表类似，不过一个结点对应一个字符，会存在很大的空间浪费
一般一个结点存放多个字符(即块链结构)，若一个结点未被占满时，可以用"#"或其他非串值字符补全
链式存储结构----块链结构
操作
与线性表相比，线性表更关注的是单个元素的操作，比如查找、插入、删除一个元素
但串中更多的是查找子串位置、得到指定位置子串、替换子串等操作
但串中更多的是查找子串位置、得到指定位置子串、替换子串等操作
串的比较
采用按位比较ASCII码
给定两个串：s=,t= 当满足以下条件之一时，s < t
1、n < m,且 = (i =1,2,,n)
例：s=“hap”，t=“happy”
2、存在某个k≤min(m,n), 使得 = (i =1,2,,k-1), <
例：s=“happen”，t=“happy”
1、n < m,且 = (i =1,2,,n)
例：s=“hap”，t=“happy”
2、存在某个k≤min(m,n), 使得 = (i =1,2,,k-1), <
例：s=“happen”，t=“happy”
模式匹配
朴素的模式匹配算法(BF)
KMP模式匹配算法
数组(Array)
数组
数组特点
结构固定：
定义后维数和维界不再改变
因此对数组的操作通常不做插入和删除，只做读取和修改
定义后维数和维界不再改变
因此对数组的操作通常不做插入和删除，只做读取和修改
一维数组
定义
一维数组：线性表中的数据元素为非结构的简单元素
逻辑结构
线性结构。定长的线性表
多维数组
二维数组
一维数组中的数据元素又是一维数组结构
逻辑结构
严格上来说多维数组不是线性结构，
也可以说线性表结构是数组结构的一个特例(一维)
而数组结构又是线性表结构的扩展(扩展到二维三维等)
也可以说线性表结构是数组结构的一个特例(一维)
而数组结构又是线性表结构的扩展(扩展到二维三维等)
顺序存储结构
以行序为主序
以列序为主序
存储位置推算式
LOC = LOC + (n*(i - 0) + （j - 0）)*c
LOC = LOC + (n*(i - 0) + （j - 0）)*c
三维数组按页/行/列存放
由于计算机存储数据元素内存单元地址是一维的，所以多维数组需要将多维结构映射到一维结构
特殊矩阵的压缩存储
对称矩阵
定义
在n × n的矩阵a中，满足 = （1 ≤ i ，j ≤ n）
存储方法
以行序为主序将元素存放在一个一维数组中SA[n*(n+1)/2]中
n*n个存储单元 --> n*(n+1)/2个存储单元
访问
的一维索引k值：i×(i - 1)/2+(j-1)
如果需要访问上三角的元素，因为 = ，把i=j ，j=i带入上式，即
k = j×(j - 1)/2+(i-1)
k = j×(j - 1)/2+(i-1)
三角矩阵
定义
主对角线以上(或者以下)的数据元素(不包括主对角线)均为常数c
存储方法
非常数三角存储与对称矩阵一样存储到一个一维数组中，重复元素c共享一个元素存储空间
SA[n*(n+1)/2+1]
SA[n*(n+1)/2+1]
n*n个存储单元 --> n*(n+1)/2+1个存储单元
访问
下三角矩阵
上三角矩阵
这里数组索引从0开始，常数c放在最后一位
对角矩阵
稀疏矩阵的压缩存储
稀疏矩阵定义
存储方式
三元组顺序表法
三元组：(行号，列号，非零元素值)
三元组表：将非零元素对应对的三元组所构成的集合，以行序为主序排列成一个线性表
代码
若要唯一标识一个稀疏矩阵，还需要在存储三元组表的同时存储该矩阵的行数、列数和非零元素个数
为了方便操作，这一组数据存在索引0的位置(也可以存在末位)
为了方便操作，这一组数据存在索引0的位置(也可以存在末位)
优缺点
三元组顺序表又称有序的双下标法。
优点：非零元在表中按行序存储，因此便于进
行依行顺序处理的矩阵运算。
行依行顺序处理的矩阵运算。
缺点：不能随机存取。 若按行号存取某一行中的非
零元，则需从头开始进行查找。对于矩阵的加法、乘法等操作，非零元素个数和位置都会发生变化，则在表中就要进行插入和删除操作，顺序存储十分不方便
零元，则需从头开始进行查找。对于矩阵的加法、乘法等操作，非零元素个数和位置都会发生变化，则在表中就要进行插入和删除操作，顺序存储十分不方便
十字链表法
在三元组的基础上增加了两个域
right：指向同一行中的下一个三元组结点
down：指向同一列中的下一个三元组结点
right：指向同一行中的下一个三元组结点
down：指向同一列中的下一个三元组结点
代码
优点
能够灵活地插入或删除因运算二产生新的非零元素，实现矩阵的各种运算
0 条评论
下一页
