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