线性数据结构 (Week 3)

发布于 2022-11-14  1853 次阅读


只学了链表,和 map。(理直气壮)

T1 队列安排

要用手写一种很新的东西存数据。
每个同学自带左手和右手,于是用链表完成对队列的操作。

代码如下。

#include <iostream>
using namespace std;
const int N=1e6+5;
struct hand{
	int l,r;
};//同学的左手和右手。
hand stu[N]={0};
void add(int i,int j,int f){//把j同学插入。
	if(f==0){//j是插入的同学 j i x的情况。j在i左边。
		stu[j].r=i;
		stu[j].l=stu[i].l;
		stu[stu[i].l].r=j;
		stu[i].l=j;
	}
	else{// i j x的情况。j在i右边。
		stu[j].l=i;
		stu[j].r=stu[i].r;
		stu[stu[i].r].l=j;
		stu[i].r=j;
	}
}
void del(int x){//删除编号为x的同学。
	if(stu[x].l==0&&stu[x].r==0) return;//没有这个同学。
	else{
		stu[stu[x].l].r=stu[x].r;
		stu[stu[x].r].l=stu[x].l;
		stu[x].l=0,stu[x].r=0;//删掉。
	}
}
int main(){
	int n; cin>>n;//n个同学。
	//非常重要。
	stu[0].l=0,stu[0].r=0;//设第零个同学自己抱住自己。
	add(0,1,1);//先把第一个同学插入。
	int num,op;//指有num个同学,op是操作类型(0/1)
	for(int i=2;i<=n;i++){
		cin>>num>>op;
		add(num,i,op);//进行插入操作。 
	}
	//删除操作。
	int cnt; cin>>cnt;//进行cnt次删除操作。。
	for(int i=1;i<=cnt;i++){
		int ds; cin>>ds;
		del(ds);
	}
	for(int i=stu[0].r;i;i=stu[i].r){//遇到0同学的时候就停止了。
		cout<<i<<' ';
	}
	cout<<endl;//行末换行。
	return 0;
}

当然也可以用标记的方式决定输不输出这个同学,(要是换了一道题有要求的还是得乖乖写hh。


T2 括号匹配

在发现字符串长度不超过100后。

bully。
#include <bits/stdc++.h>
using namespace std;
bool vis[105]={false};
int main(){
	string a; cin>>a;
	for(int i=0;i<a.length();i++){
		if(a[i]==')'||a[i]==']'){//如果遇到了右括号。
			for(int l=i-1;l>=0;l--){//查找右括号左边的左括号。
				if((a[l]=='('||a[l]=='[')&&vis[l]==false){//找到最近的没被查找过的左括号。
					if((a[l]=='('&&a[i]==')')||(a[l]=='['&&a[i]==']')){
						vis[i]=true,vis[l]=true;
						break;//配对成功。
					}
					else break;//配对失败。
				}
			}
		}
	}
	for(int i=0;i<a.length();i++){
		if(vis[i]==true){
			cout<<a[i];
		}
		else{
			if(a[i]=='('||a[i]==')') cout<<"()";
			if(a[i]=='['||a[i]==']') cout<<"[]";
		}
	}
	return 0;
}

其实这道题是试图让我们用栈解吧。))


T3 后缀表达式

是一道好题 用栈存数据的好题。

#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main(){
	stack<int> num;//存数字。
	stack<char> op;//存运算符。
	char a;
	int x=0;
	while(cin>>a&&a!='@'){
		if(a=='.'){//遇到 . 时。
			num.push(x);//把数字存入栈中。
			x=0;//重新初始化x。
		}//遇到点吧数字压入栈中。
		if(a>='0'&&a<='9'){
			x*=10; x+=a-'0';
		}//读取数字
		//加减乘除————。(感觉写的好笨)
		if(a=='+'){
			int x1,x2;
			x1=num.top();
			num.pop();
			x2=num.top();
			num.pop();
			x1+=x2;
			num.push(x1);
		}
		else if(a=='-'){
			int x1,x2;
			x1=num.top();
			num.pop();
			x2=num.top();
			num.pop();
			x2-=x1;
			num.push(x2);
		}
		else if(a=='*'){
			int x1,x2;
			x1=num.top();
			num.pop();
			x2=num.top();
			num.pop();
			x2*=x1;
			num.push(x2);
		}
		else if(a=='/'){
			int x1,x2;
			x1=num.top();
			num.pop();
			x2=num.top();
			num.pop();
			x2/=x1;
			num.push(x2);
		}
	}
	cout<<num.top();//最后的一枚数字就是经过n次运算后的答案了。
	return 0;
}

T4 寄包柜

这题柜子里还有格子,如果用二维数组的话会M,如果搜索的话会T。传统的连续顺序表在这里用起来非常尴尬。

于是(看题解后)去学了强大的Map
Map存储的数据类型是pair,可以存很多pair
Pair<key,value>的键值对,是存储一个键键映射的一个值的数据类型,其中keyvalue可以是自带的任意一种数据类型,也可以是自定义的结构体,其中key的值会用const修饰,也就是说他是不可更变的值。

Map常用的函数有:

.insert()
用法:map变量名.insert({key,value});
.erase()
用法:map变量名.erase(key);
会删除mapkeypair

在经过一些map的小实验后,过此题简直如有神助。)

#include <iostream>
#include <map>//要包含头文件map!
using namespace std;
int main(){
	map<pair<int,int>,int> m;
	//定义一个map容器。
	//key为柜子和格子,value为物品。
	int n,q;//有n个柜子,q次操作。
	cin>>n>>q;
	for(int i=1;i<=q;i++){
		int op;
		cin>>op;
		//存入操作。
		if(op==1){
			int x1,x2,x3;
			cin>>x1>>x2>>x3;
			if(x3!=0)
			m.insert({{x1,x2},x3});
			else//坑点:物品为0时要拿出来。。
			m.erase({x1,x2});
		}
		//访问操作。
		else{
			int x1,x2;
			cin>>x1>>x2;
			cout<<m[{x1,x2}]<<endl;
			//访问的时候要 m[key]。
		}
	}
	return 0;
}

可以说是非常简单(bu);

但是关于map的认识也只停留在过 T4 的程度。

其他的函数,我还没用过(之后会学的!)

.find()
.begin() / .rbegin()
.end() / .rend()
.empty()
.clear()
.size()
.swap()
.count()
//不能声明count为变量名的元凶?)


总结:

总结是

链表Map啊很好用 但是对使用条件适用范围不是非常熟练。

②我是不是看太多题解了?)(反正学到了新东西诶嘿。)