潍坊网站制作价格,wordpress固态链接,海东高端网站建设,盐都城乡建设部网站首页前言
本文基础知识部分来自于b站#xff1a;分享笔记的好人儿的思维导图与王道考研课程#xff0c;感谢大佬的开源精神#xff0c;习题来自老师划的重点以及考研真题。此前我尝试了完全使用Python或是结合大语言模型对考研真题进行数据清洗与可视化分析#xff0c;本人技术…前言
本文基础知识部分来自于b站分享笔记的好人儿的思维导图与王道考研课程感谢大佬的开源精神习题来自老师划的重点以及考研真题。此前我尝试了完全使用Python或是结合大语言模型对考研真题进行数据清洗与可视化分析本人技术有限最终数据清洗结果不够理想相关CSDN文章便没有发出。
考研真题待更新 欢迎订阅专栏408直通车 请注意本文中的部分内容来自网络搜集和个人实践如有任何错误请随时向我们提出批评和指正。本文仅供学习和交流使用不涉及任何商业目的。如果因本文内容引发版权或侵权问题请通过私信告知我们我们将立即予以删除。 文章目录 前言第三章 栈、队列和数组栈栈的概念栈的实现顺序栈S.top 0 共享栈链栈 队列队列的概念队列的实现队列的顺序存储结构rear指向队尾元素 队列的链式存储结构小结 双端队列挺喜欢考的考点栈和队列有相同逻辑结构线性结构合适与不合适做链队的链表关键看能不能获取到首尾指针带首尾的非循环或带尾的循环 栈和队列的应用栈的应用括号表达式求值中缀表达式转后缀表达式后缀表达式的计算中缀表达式转前缀表达式前缀表达式的计算中缀表达式的计算用栈实现其他小结 递归小结 队列的应用 数组和特殊矩阵本节的题目计算都可以不记公式直接代入推导数组特殊矩阵 补充代码栈数组模拟循环队列数组模拟单调栈单调队列 考研真题408 - 2023 第三章 栈、队列和数组
栈 栈的概念 限定仅在一端进行插入和删除操作的线性表又称后进先出LIFO的线性表 允许插入删除的那一端叫栈顶Top不允许插入和删除的一端叫栈底Bottom 特殊的线性表后进先出LIFO 注意n个不同元素进栈出栈元素不同排序个数为n个元素能构成多少种不同的二叉树 栈的实现
顺序栈 栈的顺序存储结构 顺序栈的基本结构 利用一组地址连续的存储单元存放自栈底到栈顶的数据元素同时设一个栈顶指针Top 基础结构 栈顶指针初始值S.top -1若有元素则指向栈顶元素S.data[S.top] 进栈栈不满时栈指针先1再送值到栈顶 出栈栈非空时先取栈顶元素值再将栈顶指针-1 栈空条件S.top -1 栈满条件S.top MaxSize-1 栈长S.top 1 顺序栈的基本操作 初始化、判栈空、进栈、出栈、读栈顶元素本质就是操作顺序表
S.top 0 共享栈
共享栈 概念 让两个顺序栈共享一个一维数组空间将两个栈的栈底分别设置在共享空间的两端两个栈顶向共享空间的中间延伸 原则 栈空判断top0 -1时0号栈为空top1 MaxSize时1号栈为空 栈满判断两个栈顶指针相邻即top1-top0 1时 其他操作和顺序栈类似
链栈 栈的链式存储结构 采用单链表实现并规定所有操作都是在单链表的表头进行 优点 便于多个栈共享存储空间和提高效率不存在栈满上溢的情况
队列
队列的概念 是一种操作受限的线性表只允许在表的一端进行插入队尾另一端进行删除队头 特殊的线性表先进先出FIFO 队头删除元素的一端 队尾插入元素的一端
队列的实现
队列的顺序存储结构
队列的顺序存储结构 分配一块连续的存储单元存放队列元素设两个指针 队头指针front指向队头元素 队尾指针rear指向队尾元素的下一个元素 基础结构 初始状态队空条件Q.front Q.rear 0 进队操作队不满时先送值到队尾元素再将队尾指针1 出队操作队不空时先取队头元素值再将队头指针1 假溢出在data数组依然存在空位置时却已经满足队列满的条件出栈的元素位置空闲 循环队列(解决假溢出问题) 概念 把存储队列元素的表逻辑上视为一个环 基本操作 初始时Q.front Q.rear 0 队头指针1Q.front (Q.front 1) % MaxSize 队尾指针1Q.rear (Q.rear 1) % MaxSize 队列长度(Q.rear MaxSize - Q.front) % MaxSize 队空Q.front Q.rear 队满判断 牺牲一个单元来区分队空和队满即队头指针在队尾指针的下一位置作为队满标志 队满条件(Q.rear 1) % MaxSize Q.front 类型中增设表示元素个数的数据成员int size 队空Q.size 0 队满Q.size MaxSize 类型中增设tag数据成员以区分是队满还是队空 tag 0时若因删除导致Q.front Q.rear则队空 tag 1时若因插入导致Q.front Q.rear则队满
rear指向队尾元素 牺牲一个存储单元
front在rear后两个位置队满front在rear后一个位置队满
队列的链式存储结构
队列的链式存储结构 队列的链式表示时一个同时带有队头指针和队尾指针的单链表 头指针指向队头结点队尾指针指向队尾结点当Q.front NULL且Q.rear NULL时队列为空 不存在队列满且溢出问题适合于数据元素变动较大的情况 小结 双端队列挺喜欢考的考点 概念 双端队列是指允许两端都可以进行入队和出队操作的队列其逻辑结构仍是线性表 分类 输出受限的双端队列允许在一端进行插入和删除但在另一端只允许插入的双端队列 输入受限的双端队列允许在一端进行插入和删除但在另一端只允许删除的双端队列
栈和队列有相同逻辑结构线性结构 合适与不合适做链队的链表关键看能不能获取到首尾指针带首尾的非循环或带尾的循环
单链表实现队列队头只能设置在链头关注删除操作需找到新队头
栈和队列的应用
栈的应用
括号 括号匹配 步骤 初始设置一个空栈顺序读入括号 若右括号则从栈中弹出一个符号判断是否匹配 若左括号则压入栈中 失败条件 不匹配、结束后栈仍有元素、遇右括号栈为空
表达式求值 中缀表达式转后缀表达式 从左到右遍历各元素 若遇到操作数直接加入后缀表达式 遇到界限符“(”直接入栈“)”则依次弹出栈内运算符并加入后缀表达式直到弹出“(”为止 遇到运算符依次弹出栈中优先级高于或等于当前运算符的所有运算符并加入后缀表达式若碰到“(”或栈空则停止之后再把运算符入栈 后缀表达式的计算
从左向右扫描元素若扫描到操作数则压入栈若扫描到运算符则弹出两个栈顶元素执行运算将结构压回栈中 中缀表达式转前缀表达式
同理但从右到左遍历“(”和“)”与中缀转后缀的功能相反最后结果依次翻转 前缀表达式的计算
从右向左扫描元素若扫描到操作数则压入栈若扫描到运算符则弹出两个栈顶元素执行运算将结构压回栈中 中缀表达式的计算用栈实现 初始化操作数栈和运算符栈 若扫描到操作数压入操作数栈若扫描到运算符或界限符按“中缀转后缀”的逻辑压入运算符栈可能弹出运算符若弹出则将栈顶的两个操作数运算压回操作数栈 其他
其他数制转换、八皇后问题、行编辑程序、函数调用、迷宫求解等
小结 递归 概念 若对象部分地包含自己或用自己给自己定义则称这个对象是递归的 若一个过程直接或间接的调用自己则这个过程是递归的 分治的思想必备条件 能将一个问题转变成一个新问题且两者的解法相同或类似不同的仅是对象且对象有变化规律 可以通过上述转化将问题化简 必须有一个明确的递归出口递归边界 形式 小结 队列的应用
脱机打印输出、解决多用户引起的资源竞争问题、广度优先遍历、网络电文传输按时间先后顺序依次进行等等 数组和特殊矩阵 本节的题目计算都可以不记公式直接代入推导
数组 概念 数组是由n个相同类型的数据元素构成的有限序列每个元素在n个线性关系中的序号称为元素下标下标取值范围称为数组的维界 与线性表的关系 数组是线性表的推广一维数组可视为一个线性表二维数组可以视为其元素也是定长线性表的线性表 数组的存储结构 数组的所有元素在内存中占用一段连续的存储空间 一维数组 存储结构关系式LOC(ai) LOC(a0) i × L 0 i nL是每个元素所占存储单元 多维数组 按行优先一行行存储 存储结构关系式LOC(ai,j) LOC(a0,0) [i × (h1 l) j] × L 二维数组h1 × h2 按列优先一列列存储 存储结构关系式LOC(ai,j) LOC(a0,0) [j × (h2 l) i] × L 二维数组h1 × h2
特殊矩阵 指具有许多相同矩阵元素或0元素并且这些相同矩阵元素或0元素的分布有一定规律 压缩矩阵 找出特殊矩阵中值相同的矩阵元素的分布规律把那些呈现分布规律的、多个值相同的元素只分配一个存储空间对0元素不分配空间 对称矩阵 概念 若对一个n阶方阵中的任意元素a(i, j) a(j, i)则称其为对称矩阵可放在一维数组B[n(n1)/2]中 存储位置计算公式 三角矩阵 概念 上/下三角区的所有元素均为同一常量其可压缩为存储完下/上三角区和主对角线上元素 存储常量一次 下/上三角矩阵元素下标对应关系 下三角矩阵 上三角矩阵 下/上三角矩阵在内存中的压缩存储形式 下三角矩阵 上三角矩阵 三对角矩阵 概念 又称带状矩阵除以对角线为中心的3条对角线区域外都为0 压缩存储将元素按行优先方式存放在一维数组B中且a(i, j)与B[n]对应关系为k 2i j - 3 稀疏矩阵 概念 矩阵中非0元素的个数t相对矩阵元素的个数s来说非常少即st 存储方式 三元组行标、列标、值 十字链表法 稀疏矩阵压缩存储后失去了随机存取的特性
补充代码
栈数组模拟
对数组简单操作略
循环队列数组模拟 循环队列注意点队满与队空条件需要有区别即需要一个额外的元素空间判断队空与队满
void push_q(int x){if((tail N 1) % N ! head){ //判断队满q[tail] x;tail (N tail 1) % N; //队尾插入一个数据注意指针移动需要%N对头类似head(Nhead1)%N;}
}
bool empty(){ //判断是否为空return head tail;
}
void pop_q(){ //对头删去一个元素if(!empty())head (N head 1) % N;
}
void query(){ //查询对头元素if(!empty())printf(%d\n,q[head]);
}单调栈 应用场景求某个数左边第一个小于他的数 思路在每次暴力从for循环的当前值向左遍历找第一个小于数的O(n2)情况下进行优化 在向左遍历过程中删去无用的数左边小于但值大于利用栈形成单调增大的序列所求数即为栈顶 for(int i0;in;i){scanf(%d,v);while(tops[top-1]v) top--; //去除比当前数大但在左边的数if(!top) printf(-1 );else printf(%d ,s[top-1]); //输出栈顶元素即第一个小于当前数的数s[top]v; //当前数压入栈中}单调队列 应用场景滑动窗口中最小值也可优化背包问题 思路同理通过删去无用的数进行优化 求滑动窗口中最小值队列头保留最小的数遍历数组若队尾数大于遍历的数则不断删去队尾同理无用的数使得队列单调增在遍历过程中不断更新队头使得不超过滑动窗口。 for(int i0;in;i){if(lri-q[l]len-1) l; //移动对头使不超过滑动窗口为了实现q数组存下标while(lrv[q[r-1]]v[i]) r--; //弹出队尾无用数因为会在队尾弹出不满足先进先出原则事实上也不能叫单调队列q[r]i; //每次都入队一个if(ilen-1) printf(%d ,v[q[l]]);
}考研真题
408 - 2023
考研真题待更新
