专栏文章

数据结构基础11月23日

wwangzilong913
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mir0zb1f
此快照首次捕获于
2025/12/04 13:58
3 个月前
此快照最后确认于
2025/12/04 13:58
3 个月前
查看原文
又是被迫写总结的一天啊！！

1.栈 stack

栈的定义

栈是一种 后进先出 的线性数据结构，我们可以用数组与一个变量（栈顶元素）和STL中的 stack进行实现。

栈的用途

1.表达式计算

依靠栈后进先出的特点，我们可以用其来做算数表达式的计算

中缀表达式转后缀表达式

  1. 建立一个用于存运算符的栈，逐一扫描该中缀表达式中的元素。
    （1）如果遇到一个数，输出该数。
    （2）如果遇到左括号，将其入栈。
    （3）如果遇到右括号，不断取出栈顶并输出，直到栈顶为左括号，然后把左括号出栈。
    （4）如果遇到运算符，只要栈顶元素的优先级不低于新符号，就不断取出栈顶并输出， 最后把新符号进栈。
  2. 依次取出并输出栈中的所有剩余符号，最终输出的序列就是一个与原中缀表达式等价的后缀表达式。

后缀表达式求值

  1. 建立一个用于存数的栈，逐一扫描该后缀表达式中的元素。 （1）如果遇到一个数，将其入栈。
    （2）如果遇到运算符，就取出栈顶的两个数进行计算，把结果入栈。
  2. 扫描完成后，栈中只剩下一个数，即最终结果。

2.括号匹配

利用栈后进先出的特性，将最近的左括号与右括号 "消掉"。
最后再判断栈是否为空。

3.单调栈

有一种特殊的栈，单调栈。即维护栈内元素递增或递减，及时排除不可能的选项，保持策略集合的高度有效性和秩序性。 对于某些有特殊性质的题，用单调栈可以极大的优化时间复杂度。

栈的典型例题

1. 表达式计算4

一道栈的综合题，可以分为三步来做：
  1. 去多余括号
  2. 转为后缀表达式
  3. 计算后缀表达式
还有三个易错点：
  1. 首尾加括号防越界
  2. 多位数的存储
  3. 负号的解决方式
Ac code
CPP
#include <bits/stdc++.h>
using namespace std;
stack <int> stk0;
stack <char> stk1;
stack <int> stk2;
map <char,int> m;
string s1;
char c1[1000005];
int j,k;
int main(){
	m['+'] = m['-'] = 1;
	m['*'] = m['/'] = 2;
	m['^'] = 3;
	cin>>s1;
	s1 = '(' + s1 + ')';
	for(int i = 0;i <= s1.size();i++){
		if(s1[i] == '('){
			stk0.push(i);
		}
		else if(s1[i] == '('){
			if(s1.empty()){
				s1.erase(i,1);
				i--;
			}
			else{
				stk0.pop();
			}
		}
	}
	for(int i = 0;i <= s1.size();i++){
		if(s1[i] == '(' && s1[i+1] == '-'){
			s1.insert(i+1,"0");
		}
	}
	for(int i = 0;i < s1.size();i++){
		char c = s1[i];
		if(c <= '9' && c >= '0'){
			j++;
			c1[j] = c;	
			if(s1[i+1] <= '9' && s1[i+1] >= '0'){
				j++;
				c1[j] = '.';
			}
		}
		else if(c == '('){
			stk1.push(c);
		}
		else if(c == ')'){
			while(!stk1.empty() && stk1.top() != '('){
				j++;
				c1[j] = stk1.top();
				stk1.pop();
			}
			stk1.pop();
		} 
		else{
			while(!stk1.empty() && m[stk1.top()] >= m[c] && stk1.top() != '('){
				j++;
				c1[j] = stk1.top();
				stk1.pop();
			}
			stk1.push(c);
		}
	}
	while(!stk1.empty()){
		j++;
		c1[j] = stk1.top();
		stk1.pop();
	}
//	for(int i = 1;i <= j;i++){
//		cout<<c1[i];
//	}
//	cout<<endl;
	for(int i = 1;i <= j;i++){
		if(c1[i] <= '9' && c1[i] >= '0'){
			k = k*10 + (c1[i]-'0');
			if(c1[i+1] != '.'){
				stk2.push(k);
				k = 0;
			}
		}
		else if(c1[i] == '+'){
			int a,b;
			a = stk2.top();
			stk2.pop();
			b = stk2.top();
			stk2.pop();
			stk2.push(b+a);
		}
		else if(c1[i] == '-'){
			int a,b;
			a = stk2.top();
			stk2.pop();
			b = stk2.top();
			stk2.pop();
			stk2.push(b-a);
		}
		else if(c1[i] == '*'){
			int a,b;
			a = stk2.top();
			stk2.pop();
			b = stk2.top();
			stk2.pop();
			stk2.push(b*a);
		}
		else if(c1[i] == '/'){
			int a,b;
			a = stk2.top();
			stk2.pop();
			b = stk2.top();
			stk2.pop();
			stk2.push(b/a);
		}
		else if(c1[i] == '^'){
			int a,b;
			a = stk2.top();
			stk2.pop();
			b = stk2.top();
			stk2.pop();
			stk2.push(pow(b,a));
		}
	}
	cout<<stk2.top();
	return 0;
}

2. Largest Rectangle in a Histogram

单调栈的板子题，首先建立一个栈，用来保存若干个矩形，这些矩形的高度是单调递增的。我们从左往右依次扫描每个矩形。
如果当前矩形比栈顶矩形高，直接进栈。
否则不断取出栈顶，直至栈为空或栈顶矩形的高度比当前矩形小。在出栈过程中，我们累计被弹出的矩形的宽度之和，并且每弹出一个矩形，就用它的高度乘上累计的宽度去增加更新答案。
Ac code
CPP
#include <bits/stdc++.h>
using namespace std;
long long n,h[400000],l[400005],r[400005],ans;
stack <long long> st;
int main(){
	while(cin>>n){
		if(n == 0){
			break;
		}
		while(1){
			if(st.empty())
				break;
			st.pop();
		}
    	memset(l,0,sizeof(l));
	    memset(r,0,sizeof(r));
    	memset(h,0,sizeof(h));
		for(int i = 1;i <= n;i++)
			cin>>h[i];
		l[1] = 1;
		r[n] = 1;
		for(int i = 1;i <= n;i++){
			if(st.empty()){
				st.push(i);
				continue;
			}
			while(1){
				if(st.empty())
					break;
				if(h[st.top()] < h[i])
					break;
				st.pop();
			}
			if(!st.empty())
				l[i] = i - st.top();
			else
				l[i] = i;
			st.push(i);
		}
		while(1){
			if(st.empty())
				break;
			st.pop();
		}
		for(int i = n;i >= 1;i--){
			if(st.empty()){
				st.push(i);
				continue;
			}
			while(1){
				if(st.empty()){
					break;
				}
				if(h[st.top()] < h[i]){
					break;
				}
				st.pop();
			}
			if(!st.empty()){
				r[i] = st.top() - i;
			}
			else{
				r[i] = n - i + 1;
			}
			st.push(i);
		}
    	ans = 0;
		for(int i = 1;i <= n;i++)
			ans = max(ans,(l[i]+r[i]-1)*h[i]);
		cout<<ans<<endl;
	}
	return 0;
}

2.队列

队列的定义

队列是一种先进先出的线性数据结构。
一般来说，元素从右端进入队列，从左端离开队列，于是我们称队列的左端为队头，右端为队尾。
可以用数组和两个变量（分别指向队头与队尾）与STL中的 queue实现队列。

队列的用途

1. 队列的变体

（1）优先队列 priority_queue

优先队列是给每个元素附带一个评估值，出队时取出估值最大的一个，等价于一个二叉堆。

（2）双端队列 deque

队列的两端都能插入或取出元素。

2.广度优先搜索 BFS

没什么好讲的。给个题单

3.单调队列

与单调栈类似，维护队内元素的单调性，及时排除不可能的情况。
单调队列也是优化动态规划的重要手段。

队列的典型例题

1. 蚯蚓

Ac code
CPP
#include<bits/stdc++.h>
#define p u/v 
using namespace std;
long long n,m,q,u,v,t,a[100005];
queue <long long> q1,q2,q3;
long long get(){
	long long qa,qb,qc,maxx;
	qa = qb = qc = -2e9;
	if(!q1.empty()) qa = q1.front();
	if(!q2.empty()) qb = q2.front();
	if(!q3.empty()) qc = q3.front();
	maxx = max(qa,max(qb,qc));
	if(!q1.empty() && maxx == q1.front()) q1.pop();
	else if(!q2.empty() && maxx == q2.front()) q2.pop();
	else if(!q3.empty() && maxx == q3.front()) q3.pop();
	return maxx; 
}
inline int read(){
	char c;
	int d=0,e=1;
	c=getchar();
	while(!isdigit(c)){
		if(c == '-') e = -1;
		c = getchar();
	}
	while(isdigit(c)){
		d = (d<<1)+(d<<3)+(c^48);
		c = getchar();
	}
	return d*e;
}
void print(long long int d){
	if(d < 0){
		putchar('-');
		d = -d;
	}
	if(d < 10) putchar(d+48);
	else{
		print(d/10);
		putchar(d%10+48);
	}
}
int main(){
	n = read();
	m = read();
	q = read();
	u = read();
	v = read();
	t = read();
	for(int i = 1;i <= n;i++)
		a[i] = read();
	sort(a+1,a+1+n);
	for(int i = n;i >= 1;i--)
		q1.push(a[i]);
	for(int i = 1;i <= m;i++){
		long long maxx = get()+(i-1)*q;
		if(i % t == 0){
			print(maxx);
			putchar(' ');
		}
		q2.push(maxx * p - q * i);
		q3.push(maxx - maxx * p - q * i);
	}
	putchar('\n');
	for(int i = 1;i <= n+m;i++){
		long long maxx = get()+m*q;
		if(i % t == 0){
			print(maxx);
			putchar(' ');
		}
	}
	return 0;
}

2. 最大子序和

本题是求区间和的问题，我们一般变为前缀和相减来解决。
我们枚举左端点，在规定长度内，找最大的前缀和为右端点。因此，我们用一个队列存这个下标递增，前缀和的值也递增的序列。
每个ii都要进行三个步骤，维持长度、更新答案、去除不可能的元素。
Ac code
CPP
#include <bits/stdc++.h>
using namespace std;
int n,m,ans = INT_MIN,sum[300005],q[300005],front = 1,back = 1;
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i = 1;i <= n;i++){
		int x;
		cin>>x;
		sum[i] = sum[i-1] + x;
	}
	q[1] = 0;
	for(int i = 1;i <= n;i++){
		while(front <= back && i - q[front] > m)
			front++;
		ans = max(ans,sum[i] - sum[q[front]]);
		while(front <= back && sum[q[back]] >= sum[i])
			back--;
		back++;
		q[back] = i;
	}
	cout<<ans;
	return 0;
}

3.Hash表

Hash表的定义

Hash表又称散列表，一般由Hash函数与链表结构（拉链法）或一个大数组（开放选址法） 共同实现。
当需要对较多复杂信息进行统计时，可以用Hash函数把这些信息映射到一个容易维护的域值内。
因为域值变简单，范围变小，可能造成Hash冲突，所以需要上面提到的链表或大数组来解决。

Hash表的用途

1.统计出现次数或是否出现

因为经Hash函数处理的数变简单，范围变小，所以可以更好的完成这类的题目。

2.字符串 Hash

字符串 Hash可以把一个任意长度的字符串映射成一个非负整数，并且冲突的概率极小。具体方法如下：
取一固定值PP，把固定值PP进制数，并发配一个大于0的数值，代表每种字符。一般来说，我们分配的数值都远小于PP。 然后取一固定值MM,求出该PP进制数对MM的余数作为该字符串的Hash值。
（通常情况，PP取131或13331）

Hash表的典型例题

1. Snowflake Snow Snowflakes

把雪花的六个角按顺时针设为a1,a2,a3,a4,a5,a6a1,a2,a3,a4,a5,a6,将Hash函数定义为Hash(a1,a2,a3,a4,a5,a6)=(∑j6+∏j6)Hash(a1,a2,a3,a4,a5,a6)=(\sum_j^6 + \prod_j^6) modmod PP (j=1)
如果两片雪花Hash值不同，就说明一定不一样；如果一样，就暴力比较两片雪花是否相同。
CPP
#include <bits/stdc++.h>
using namespace std;
const int M = 99991,N = 1e6 + 5;
int n,snow[N][10];
int HEAD[M],NEXT[N],tot;
int Hush(int *a){
	int h=0,j=1;
	for(int i = 0;i < 6;i++){
		h = (h + a[i]) % M;
		j = (long long)j * a[i] % M;
	}
	return (h + j) % M;
}
bool check2(int *a,int *b){
	bool flag;
	for(int i = 0;i < 6;i++){
		for(int j = 0;j < 6;j++){
			flag = true;
			for(int k = 0;k < 6;k++){
				if(a[(i+k) % 6] != b[(j+k) % 6]){
					flag = false; 
				}
			}
			if(flag) return true;
			flag = true;
			for(int k = 0;k < 6;k++){
				if(a[(i-k+6) % 6] != b[(j+k) % 6]){
					flag = false; 
				}
			}
			if(flag) return true;
		}
	}
	return false;
}
bool check1(int *a){
	int now = Hush(a);
	for(int i = HEAD[now];i;i = NEXT[i]){
		if(check2(a,snow[i])) return true;
	}
	tot++;
	memcpy(snow[tot],a,6*sizeof(int));
	NEXT[tot] = HEAD[now];
	HEAD[now] = tot;
	return false; 
}
int main(){
	cin>>n;
	while(n--){
		int a[10];
		for(int i = 0;i < 6;i++){
			cin>>a[i];
		}
		if(check1(a)){
			cout<<"Twin snowflakes found.";
			return 0;
		}
	}
	cout<<"No two snowflakes are alike.";
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...