洛谷题单--线性表

2023-11-23 17:15
文章标签 线性表 洛谷题

本文主要是介绍洛谷题单--线性表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

P3156 【深基15.例1】询问学号

链接 : 【深基15.例1】询问学号 - 洛谷

直接输入，然后输出a[i]即可;

代码 : 

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int main(){int  n, q ; cin >> n >> q;vector<int> a(n+1);for(int i=1;i<=n;i++) cin >> a[i];while(q--){int x ;cin >> x;cout << a[x] << endl;}	return 0;
}

P3613 【深基15.例2】寄包柜

链接 : 【深基15.例2】寄包柜 - 洛谷

这题直接套用stl中的map解决就行了 : 

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
int main(){int n , q ; cin >> n >> q;int op,i,j,k;map<int,map<int,int>> a; // 下标 while(q--){cin >> op;if(op == 1){cin >> i >> j >> k;a[i][j] = k;}else{cin >> i >> j;cout << a[i][j] << endl;}}return 0;
}

或者用数组模拟 : 

#include<cstdio>
#include<map>
using namespace std;
int n,q,p,k;
map<long long,int>b;
long long i,j;
int main()
{scanf("%d%d",&n,&q);while(q--){scanf("%d%d%d",&p,&i,&j);if(p==1){scanf("%d",&k);b[i*1000000+j]=k;}else printf("%d\n",b[i*1000000+j]);}return 0;
}

P1449 后缀表达式

栈的模板题，直接用stack来模拟栈，或者用数组来模拟stack也行；

// 后缀表达式;
// 可以用栈stack模拟
// 也可以用数组模拟 #include<cstring>
#include<iostream>
#include<stack>
#include<algorithm>
using namespace std;
stack<int> st;
char ch = '0';
int s = 0;
int x , y ;
int main(){while(ch != '@'){ch = getchar();if(ch=='+'){x = st.top() ; st.pop();y = st.top() ; st.pop();st.push(x+y) ; }else if(ch == '-'){x = st.top() ; st.pop();y = st.top() ; st.pop();st.push(y - x);}else if(ch == '*'){x = st.top() ; st.pop();y = st.top() ; st.pop();st.push(x * y);}else if(ch == '/'){x = st.top() ; st.pop();y = st.top() ; st.pop();st.push(y / x);}else if(ch == '.') {st.push(s);s = 0;}else{s = s* 10 + (int)(ch-'0');}}cout << st.top() << endl;return 0;
}

P1996 约瑟夫问题

直接暴力模拟就行

// 暴力模拟 
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
int main(){int n , m ; cin >> n >> m;int cnt = 0 , k = 0 , s = 0;vector<int> a(n+1,0);while(cnt != n){k++;if(k>n) k = 1;// 标号 if(a[k]==0){s++;//人数 if(s==m){cnt ++;s = 0;a[k] = 1;cout << k << " ";}	}}	return 0;
}

用队列来操作 : 

用cnt来统计当前报数的人数，如果cnt == m,那么输出队头，且队头出队；

否则将队头放入最后面，以此来实现模拟；

// 用队列模拟 : 
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int main(){int n , m ;  cin >> n >> m ;queue<int> q;for(int i=1;i<=n;i++) q.push(i);int cnt = 1 ; // 表示当前数的人数 while(!q.empty()){if(cnt == m){cout << q.front() << " ";q.pop();cnt = 1;}else{q.push(q.front());q.pop();cnt ++;}}cout << endl;
}

P1160 队列安排

这题是一道静态双链表的好题 : 用结构体数组去模拟双链表 ， 结构体中定义l,r分别表示t[i]的左节点 和 右节点 ， 用 tag 表示 是否被删除；

具体可以参考luogu第一篇题解，要注意的是，要设置t[0].l=0.t[0].r=0,然后add(1,0,1),这样就可以避免循环而出现死循环的问题；

代码 : 

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;struct Node{int l,r;int tag;//标记是否要用到 
}t[N]={0};void add(int i,int k,int p){if(p==1) { // i放到k右 t[i].r = t[k].r;t[i].l = k;t[k].r = i;t[t[i].r].l = i;} else { // i放到k左边 t[i].l = t[k].l;t[k].l = i;t[i].r = k;t[t[i].l].r = i;}
}int main(){int n ; cin >> n;t[0].l = 1 ; t[0].r = 0;add(1,0,1);for(int i=2;i<=n;i++){int k,p;cin >> k >> p;// k 表示 k 号同学 // p 表示左右add(i,k,p);	}int m ; cin >> m;int mx = m;while(m--){int x ; cin >> x;t[x].tag = 1; }for(int i=t[0].r;i;i=t[i].r){if(t[i].tag==0){cout << i << " ";}}return 0;
}

P1540 [NOIP2010 提高组] 机器翻译

链接 : [NOIP2010 提高组] 机器翻译 - 洛谷

这个题最先想到的就是用vector来模拟队列，代码如下 : 

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int main(){int  m, n ; cin >> m >> n;vector<int> a;int ans = 0;while(n--){int x ; cin >> x;if(find(a.begin(),a.end(),x) == a.end()){ // 找不到 a.push_back(x);ans ++;}if(a.size() > m)a.erase(a.begin());}cout << ans << endl;return 0;
}

那用队列(queue)怎么写呢?代码如下 :(这里有个小trick : 用一个tag数组记录x是否出现过) 


#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int tag[1010] = {0};
int main(){int  m, n ; cin >> m >> n;queue<int> a;int ans = 0;while(n--){int x ; cin >> x;if(!tag[x]){ // 找不到 a.push(x);ans ++;tag[x] = true;}if(a.size() > m){int y = a.front();if(x != y) tag[y] = 0;a.pop();}}cout << ans << endl;return 0;
}

P1739 表达式括号匹配

链接 : 表达式括号匹配 - 洛谷

这题应该是栈来模拟，但是用不到，只用设置一个cnt变量，遇到(减一，遇到)加一，如果cnt>0，直接返回false,为true当且仅当最后cnt==0,请看代码 : 

#include<bits/stdc++.h>
using namespace std;
int main(){string s ;cin >> s;int t = 0 ;for(char& c : s){if(c=='(') t--;else if(c==')') t++;if(t>0 ){cout << "NO" << endl;return 0;}}if(t==0) cout << "YES" << endl;else cout << "NO" << endl;
}

 P4387 【深基15.习9】验证栈序列

链接 : 【深基15.习9】验证栈序列 - 洛谷

用栈模拟

代码如下 : 

#include<iostream>
#include<stack>
using namespace std;
stack<int>q;//栈q 
int p,n;//p组数据，n为序列长度 
int main()
{cin>>p;while(p--){cin>>n;int a[n+1],b[n+1],sum=1;//入栈队列a，待检验队列b，计数器sum for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i]; for(int i=1;i<=n;i++){q.push(a[i]);//入栈 while((q.top())==b[sum]) {q.pop(),sum++;//sum++到b下一个元素 if(q.empty())break;//注意这里，第一次RE就因为当栈空时还用了出栈操作，所以要手动结束循环 }}if(q.empty()) cout<<"Yes"<<endl;//如果栈为空说明出栈序列b正确 else cout<<"No"<<endl;while(!q.empty())q.pop();//清空栈 }return 0; 
}

这篇关于洛谷题单--线性表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/419486。

相关文章

数据结构：线性表的顺序存储

数据结构：线性表的顺序存储

文章目录 🍊自我介绍🍊线性表的顺序存储介绍概述例子 🍊顺序表的存储类型设计设计思路类型设计 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入
阅读更多...
[数据结构]线性表之单链表的类模板实现

[数据结构]线性表之单链表的类模板实现

类的具体实现如下： /#include"LinearList.h"#include <iostream>#include <cstdlib>using namespace std;template<class T>struct LinkNode //链表节点类{T data;LinkNode<T>* link;LinkNode(LinkNode<T>* ptr=NULL):
阅读更多...
线性表中顺序表的合并

线性表中顺序表的合并

对两个顺序表进行合并，算法的复杂度为O(La.size+Lb.size)。 已知： 顺序线性表La和Lb的元素按值非递减排列 归并La和Lb得到的顺序线性表Lc，Lc的元素也按值非递减排列。 代码定义： void mergeList(SeqList *La,SeqList *Lb,SeqList *Lc){Lc->capacity = La->size + Lb->size;Lc->b
阅读更多...
C/C++线性表---顺序表算法全解析

C/C++线性表---顺序表算法全解析

课程笔记来源： MOOC网 郝斌数据结构 之前学过一遍数据结构，面试时候真的忘光了，之前去华环让写一个简单的链表删除算法也是没有写出来，想做CS，必须把数据结构学好了，还是再来一遍吧。 -------------------------------------------------------------------------------------------------------
阅读更多...
寒假集训第二天——线性表

寒假集训第二天——线性表

现在时间是北京时间1点23分，第二天集训。。。 昨天花了老长时间把线性表看了下，表示很有压力，不大会用。。。 先说下我学到的线性表的皮毛。。。 首先是链表的构建，构建有两种方式： 顺序链表（尾插法建单链表） #include<stdio.h>struct node{int date;struct node *next;};int main(){int i,n;node *he
阅读更多...
002线性逻辑结构——线性表

002线性逻辑结构——线性表

目录 1.数据之间的逻辑关系 2.存储结构的实现 2.1顺序存储结构实现线性表： 对该顺序表进行一系列的增删改查： ①增：         Ⅰ）顺序添加：         Ⅱ）插入添加： ②删：       ③改：       ④查：       输出 整体代码示例 1.数据之间的逻辑关系 线性表：具有相同数据类型的有限个（n）数据元素的序列
阅读更多...
【数据结构】—— 线性表

【数据结构】—— 线性表

目录 前言一、顺序表1.1 顺序表的定义及其特点1.2 顺序表的C语言实现1.2.1 定义顺序表1.2.2 初始化1.2.3 插入1.2.4 删除1.2.5 查找 二、链表2.1 链表的定义2.2 单向链表的实现2.2.1 定义单向链表2.2.2 创建链表2.2.3 插入元素2.2.4 删除元素2.2.5 查找 2.3 双向循环链表 前言   线性表是最基本、最简单、也是
阅读更多...
简述线性表、栈和队列的异同

简述线性表、栈和队列的异同

相同点 线性表、栈和队列都是线性结构（即数据元素之间存在一对一的线性关系），其中栈和队列又是特殊的线性表。 栈和队列是操作位置受限的线性表,即对插入和删除的位置加以限制。 ​​​​不同点 （操作位置的限制） 线性表允许在表中的任意合法位置进行插入和删除操作，没有位置限制。 栈仅允许在表的一端（栈顶）进行插入（入栈）和删除（出栈）操作，因而是后进先出表。 队列仅允许在表的一端（队
阅读更多...
线性表之单向链表

线性表之单向链表

1. 单向链表的结构         在上一个章节中为大家详细讲解了静态链表，它解决了插入和删除数据的时候大量移动元素的问题，但是解决不了合理分配和使用内存的问题。解决这个问题的最优方案就是使用动态链表，简称链表。         链表和数组都可以称之为线性表，数组是一种顺序存储结构的线性表，而链表是一种链式存储结构的线性表，链表中的节点和节点之间的内存是不连续的，它们之间的前后关系需要通过指
阅读更多...
利用线性表的顺序结构求集合的并、交、差、补（C语言实现）

利用线性表的顺序结构求集合的并、交、差、补（C语言实现）

昨天用数据结构中的线性表的顺序结构实现了关于集合的并、交、差、补的集合运算，做个记录，希望也能帮助到其他人。 一、算法分析 　　（1）用数组A，B，C，E表示集合。假定A={1,3，4，5，6，7，9，10}, 　　B={2，,3，4，7，8，10}, E={1,2，3，4，5，6，7，8，9，10}, 　　输入数组A，B，E（全集），输入数据时要求检查数据是否重复（集合中的数据要求不重
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2