[C++知识库]线性表洛谷例题

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

这个比较简单 数组输入即可

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

这个题目数据比较大 不能用二维数组进行存储，需要借助map

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+6;
typedef long long ll;
map<int,map<int,int> >mp;
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++) {
		int x;
		cin>>x;
		if(x==1){
			int a,b,c;
			cin>>a>>b>>c;
			mp[a][b]=c;
		}else{
			int a,b;
			cin>>a>>b;
			cout<<mp[a][b]<<endl;
		}
	}
    return 0;
}

P1449 后缀表达式

我也不知道这是啥子线性了 这明显是栈啊 杰哥

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+6;
typedef long long ll;
map<int,map<int,int> >mp;
int main()
{
	stack<int>s;
	string ss;
	cin>>ss;
	int n=ss.size();
	for(int i=0;i<n;i++){
		if(ss[i]=='.')
		{
			stack<int>q;
			int j=i-1;
			while(j>=0&&ss[j]>='0'&&ss[j]<='9')
			{	
				q.push(ss[j]-'0');
				j--;
			}
			
			int sum=0;
			while(q.size()){
				sum=sum*10+q.top();
				q.pop();
			}
			//cout<<sum<<endl;
			s.push(sum);
		}
		else if(ss[i]=='@') break;
		else {
			if(ss[i]=='+'){
				int y=s.top();
				s.pop();
				int x=s.top();
				s.pop();
				
				s.push(x+y);
			}else if(ss[i]=='-'){
				int y=s.top();
				s.pop();
				int x=s.top();
				s.pop();
				
				s.push(x-y);
				
			}else if(ss[i]=='*'){
				int y=s.top();
				s.pop();
				int x=s.top();
				s.pop();
				
				s.push(x*y);
				
			}else if(ss[i]=='/'){
				int y=s.top();
				s.pop();
				int x=s.top();
				s.pop();
				
				s.push(x/y);
				
			}
		}
	//	cout<<1<<endl;
	}
	
	cout<<s.top();
    return 0;

P1996 约瑟夫问题

既然说是线性表了 那我就用链表写写吧

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+6;
typedef long long ll;
int n,m;

struct node{
	int date;
	node *next,*head;
};
node *head,*now;
int cnt=0,ans=0;
map<int,int>mp;
void init(){
	head=(node *)malloc(sizeof(node));
	head->date=1;
	head->next=head;
	head->head=head;
	now=(node *)malloc(sizeof(node));
	now=head;
}
void add(int key){
	node *p=(node *)malloc(sizeof(node));
	
	p->date=key;
	
	node *q=head->next;
	while(q->next!=head) q=q->next;
	
	if(key==n){
		head->head=p;
		q->next=p;
		p->next=head;
		p->head=q;
		return;
	}
	q->next=p;
	p->head=q;
	p->next=head;
}
void pt(){
	node *x=head;
	int k=0;
	while(k<n){
		k++;
		//cout<<x->date<<" ";
		x=x->next;
	}
	//cout<<endl;
}
void work(){
	cnt=0;
	//cout<<1<<endl;
	while(cnt<m){
		if(!mp[now->date])
		cnt++;
		if(cnt==m) break;
		now=now->next;
	//	cout<<1<<endl;
	}
	
	cout<<now->date<<" ";
	mp[now->date]=1;
	now->head->next=now->next;
	now->next->head=now->head;
	now=now->next;
}
int main()
{
	
	cin>>n>>m;
	init();
	for(int i=2;i<=n;i++) {
		add(i);
		//	cout<<i<<endl;
	}
//	pt();
	while(ans<n){
		ans++;//cout<<1<<endl;
		work();
		
	}
    return 0;
}

洛谷维护 先贴着

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+6;
typedef long long ll;
int n,m;
int kp=0;
struct node{
	int date;
	node *next,*head;
};
node *head,*now;
int cnt=0,ans=0;
map<int,int>mp;
void init(){
	head=(node *)malloc(sizeof(node));
	head->date=1;
	head->next=head;
	head->head=head;
	now=(node *)malloc(sizeof(node));
	now=head;
}
void add(int x,int y,int z){
	node *p=(node *)malloc(sizeof(node));
	
	p->date=z;
	
	node *q=now;
	while(q->date!=x) q=q->next;
	
	if(y==0){
		
		q->head->next=p; //cout<<q->head->date<<endl;
		p->head=q->head;
		p->next=q;
		q->head=p;
		if(q==now){
			now=p;
			
			now->next=p->next;
			now->head=p->head;
	//		cout<<1<<endl;
		}
		
	}else{
		p->head=q;
		
		p->next=q->next;
		
		q->next->head=p;
		q->next=p;
	//	cout<<q->next->date<<endl;
	}
	
}
void pt(int n){
	int ans=0;
	node *x=now;
	int k=0;
	while(ans<n){
		printf("%d ",x->date);
		x=x->next;
		ans++;
	}
	//cout<<endl;
}
void work(int key){
	
	node *p=head;
	int flag=0;
	while(p->next!=head){
		if(p->date==key)
		{
			flag=1;
			break; 
		}
		
		p=p->next;
	}
	
	if(flag){
		p->next->head=p->head;
		p->head->next=p->next;
		kp++;
	}
}
int main()
{
	init();
	scanf("%d",&n);
	
	for(int i=2;i<=n;i++) {
		int x,y;
		scanf("%d %d",&x,&y);
		add(x,y,i);//pt(i);
	//	cout<<endl; 
	}
//	pt(n);
	scanf("%d",&m);
	while(ans<m){
		ans++;//cout<<1<<endl;
		int x;
		scanf("%d",&m);
		work(x);
		
	}
	pt(n-kp);
    return 0;
}