数据结构

树

查找

图

排序

零个或多个数据元素的有限序列

线性表(List)的定义

顺序存储

单链表

双链表

循环链表

链式存储

线性表的存储结构

广义表(Lists)

线性表(List)

栈是限定仅在表尾进行插入和删除操作的线性表

栈的定义

栈顶top指针从0开始(看个人习惯)

数组实现

前提：相同数据类型的栈

栈满：top1+1=top2

入栈：需要插入元素和栈号参数(指定入哪个栈)

出栈

代码

操作

通常当两个栈的空间需求有相反关系时(一个栈增长时另一个栈在缩短的情况)，就像买卖股票一样，你买入时，一定有一个你不知道的人在做卖出操作，有人赚钱就一定有人赔钱

应用

两栈共享空间

栈顶放在单链表头部，无需头结点top指针就是头指针

链栈

栈的存储结构

浏览器的后退键、编辑软件的撤销键(undo)

应用场景：找到每一个数左边(右)离它最近且比它小(大)的数

原理：剔除一些永远用不到的元素(逆序关系)，剩下单调的元素

AcWing 找到每一个数左边离它最近且比它小的数

单调栈

斐波那契数列

递归

四则运算表达式求值

栈的应用

栈(Stack)

队列是只允许在一段进行插入操作，而在另一端进行删除操作的线性表

队列的定义

算法上一般队列装的是索引值，而不是元素值而且写算法时我们只考虑移动指针，不用考虑元素出队后真正的删除这样出队入队时间复杂度都是O(1)

普通队列，习惯tail从-1开始，head从0开始，head==tail时，队列内有一个元素

在上面两点的基础下当前队列的长度就为tail-head+1如果head，tail都从0开始，队长为tail-head

这里队列存放的是元素值，如果队头出队后，队列中所有元素都得向前移动，时间复杂度为O(n)

AcWing 829. 模拟队列

普通队列

如果普通队列队头出队后不将后续元素往前移动，那么会出现\"假溢出\"现象如果还想要O(1)的时间复杂度，又不想出现这种情况，那么就需要循环队列来实现

定义：头尾相接的顺序存储结构称为循环队列

如何处理：    方法一：设置一个标志变量flag，当head==tail，且flag==0，队列为空              当head==tail，且flag==1，队列满    方法二(重点)：修改队列满条件，保留一个元素的空间

循环队列出现head==tail的情况会有两种1、队列为空2、队列满

注意：head指针指向队头，tail指针指向队尾元素的下一位指针指的是索引值

初始化

入队

出队

通用的计算队列长度公式    (tail-head+QueueSize)%QuqueSize

队长

条件：(tail+1)%QueueSize==head font color=\"#000000\" style=\"\

队满

循环队列

链队列：其实就是线性表的单链表，只不过只能尾进头出    带头结点

队空

链队列和循环队列比较

队列的存储结构

应用场景：窗口滑动

原理和单调栈一致都是去除一些永远用不到的元素使得整个队列(栈)为单调递增(递减)

思想

AcWing 154. 滑动窗口

为什么队列储存元素的索引而不是数值本身

为什么四行代码的顺序不能颠倒

为什么队列存储了窗口内从最小值到队尾元素的一个升序子序列

为什么维持窗口长度的那行代码使用了if，而不是whlie

思考的问题

使用STL库

单调队列

队列的应用

队列(Queue)

栈与队列

串是由零个或多个字符组成的有限序列，又叫字符串

本质上是一种线性表扩展，只不过针对内容做出了限制

串的定义

链串：与线性表类似，不过一个结点对应一个字符，会存在很大的空间浪费一般一个结点存放多个字符(即块链结构)，若一个结点未被占满时，可以用\"#\"或其他非串值字符补全

链式存储结构----块链结构

串的存储结构

与线性表相比，线性表更关注的是单个元素的操作，比如查找、插入、删除一个元素但串中更多的是查找子串位置、得到指定位置子串、替换子串等操作

采用按位比较ASCII码

给定两个串：s=span class=\"equation-text\" data-index=\"0\" data-equation=\"a_1a_2\\cdots a_n\" contenteditable=\"false\

串的比较

朴素的模式匹配算法(BF)

KMP模式匹配算法

模式匹配

串(string)

结构固定：定义后维数和维界不再改变因此对数组的操作通常不做插入和删除，只做读取和修改

数组特点

一维数组：线性表中的数据元素为非结构的简单元素

定义

线性结构。定长的线性表

逻辑结构

一维数组

一维数组中的数据元素又是一维数组结构



严格上来说多维数组不是线性结构，也可以说线性表结构是数组结构的一个特例(一维)而数组结构又是线性表结构的扩展(扩展到二维三维等)

以行序为主序

以列序为主序

存储位置推算式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)

访问

对称矩阵

主对角线以上(或者以下)的数据元素(不包括主对角线)均为常数c

非常数三角存储与对称矩阵一样存储到一个一维数组中，重复元素c共享一个元素存储空间SA[n*(n+1)/2+1]

n*n个存储单元 --> n*(n+1)/2+1个存储单元

下三角矩阵span class=\"equation-text\" contenteditable=\"false\" data-index=\"0\" data-equation=\"k=\\begin{cases}i×(i-1)/2+(j-1) --i≥j(非常数部分) \\\(n+1)/2------- i

上三角矩阵j(常数c)\\end{cases}\"

这里数组索引从0开始，常数c放在最后一位

三角矩阵

对角矩阵

特殊矩阵的压缩存储

稀疏矩阵定义

三元组：(行号，列号，非零元素值)

三元组表：将非零元素对应对的三元组所构成的集合，以行序为主序排列成一个线性表

若要唯一标识一个稀疏矩阵，还需要在存储三元组表的同时存储该矩阵的行数、列数和非零元素个数       为了方便操作，这一组数据存在索引0的位置(也可以存在末位)

三元组顺序表又称有序的双下标法。 

优点：非零元在表中按行序存储，因此便于进行依行顺序处理的矩阵运算。

缺点：不能随机存取。 若按行号存取某一行中的非零元，则需从头开始进行查找。对于矩阵的加法、乘法等操作，非零元素个数和位置都会发生变化，则在表中就要进行插入和删除操作，顺序存储十分不方便

优缺点

三元组顺序表法

在三元组的基础上增加了两个域right：指向同一行中的下一个三元组结点down：指向同一列中的下一个三元组结点

能够灵活地插入或删除因运算二产生新的非零元素，实现矩阵的各种运算

优点

十字链表法

存储方式

稀疏矩阵的压缩存储

数组(Array)

数据结构与算法