[ACM实验一]C++STL泛型编程(1)

蓝飞 蓝飞 | 时间:2012-03-30, Fri | 5,072 views
编程算法 

实验项目:C++STL泛型编程(1)
实验目的:掌握C++STL vector向量容器、stack堆容器和queue队列容器的应用。
实验要求:使用VC++6.0实现实验要求。
实验内容:

1.利用vector向量容器,实现1—n个数围成一圈,隔3输出,输出最后的顺序号。
2.利用stack堆栈容器,实现输入一个算术表达式中包含圆括弧、方括弧和花括弧三种类型的括弧,输出是否正确配对。例如:
输入:{4\[6*(8+9)]}+6}
输出:不匹配
3.利用queue队列容器实现杨辉三角,根据输入的n,输出对应的杨辉三角(猛击进入相应OJ题目)。
4.附加题:
一矩形阵列由0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩阵整列的细胞个数,如:
输入:输入m,n,然后在输入m×n的矩阵:
4 10
0 2 3 4 5 0 0 0 6 7
1 0 3 4 5 6 0 5 0 0
2 0 4 5 6 0 0 6 7 1
0 0 0 0 0 0 0 0 8 9
输出:细胞个数为4
提示:用队列实现

1.利用vector向量容器,实现1—n个数围成一圈,隔3输出,输出最后的顺序号。

#include<iostream>
#include<vector>
using namespace std;
int main(){
	vector<int> vec;
	int n, i;
	cin >> n;
	for(i = 1; i <= n; ++i){
		vec.push_back(i);
	}
	i = 0;		//从第一个元素开始输出
	while(!vec.empty()){
		i = i % vec.size();	//取模,防止下标超出数组范围,并形成循环
		cout << vec.at(i) << ends;	//输出容器中第i个元素
		vec.erase(vec.begin() + i);	//该元素已输出,应删除
		i += 2;	//隔3输出,应加3,但由于删除了一个元素,因此应再减1,即应加2
	}
	return 0;
}

2.利用stack堆栈容器,实现输入一个算术表达式中包含圆括弧、方括弧和花括弧三种类型的括弧,输出是否正确配对。
例如:
输入:{4\[6*(8+9)]}+6}
输出:不匹配

#include<iostream>
#include<stack>
#include<string>
using namespace std;
int main(){
	char c;
	string op_left = "([{";
	string op_right = ")]}";
	stack<char> s;
	while((c = getchar()) != '\n'){
		if(op_left.find(c) < op_left.length()){
			s.push(c);	//若找到左括号,则入栈
		}else if(op_right.find(c) < op_right.length()){
			if(s.size() == 0 || op_right.find(c) != op_left.find(s.top())){
				cout << "不匹配" << endl;
				break;		//若找到右括号,却没有相应左括号匹配,退出循环
			}else{
				s.pop();	//否则相应左括号出栈
			}
		}
	}
	if(s.size() > 0){		//若还有左括号未被匹配,则说明不匹配
		cout << "不匹配" << endl;
	}
	return 0;
}

3.利用queue队列容器实现杨辉三角,根据输入的n,输出对应的杨辉三角猛击进入相应OJ题目):

杨辉三角的特性,每个数字等于上面的两个数字相加,即这两个数字之前的数字已经没有存在的必要而出队,而接下来的数字就等于队头与再次出队后的队头之和,该题思路比较清晰,稍微有点耐心就能看懂。

#include<iostream>
#include<iomanip>
#include<queue>
using namespace std;
int main(){
	int n;
	while(cin >> n){
		queue<int> q;
		for(int i = 0; i <= n - 1; ++i){
			for(int j = 0; j < n - i - 1; ++j){
				cout << "   ";
			}
			if(i > 0){
				q.push(1);
				cout << setw(3) << 1 << "   ";	//输出每行行首的1
			}
			if(i > 1){
				q.pop();	//删除上一行行末的1
				for(int j = 1; j < i; ++j){
					int num = q.front();
					q.pop();
					num += q.front();	//当前数等于队列中第1、2个元素之和,即要保证队头为当前数左上方的数字
					q.push(num);
					cout << setw(3) << num << "   ";
				}
			}
			q.push(1);
			cout << setw(3) << 1 << endl;	//输出每行行末的1
		}
		cout << endl;
	}
	return 0;
}

附加题:
一矩形阵列由0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩阵整列的细胞个数。

输入:输入m,n,然后在输入m×n的矩阵:
4 10
0 2 3 4 5 0 0 0 6 7
1 0 3 4 5 6 0 5 0 0
2 0 4 5 6 0 0 6 7 1
0 0 0 0 0 0 0 0 8 9
输出:细胞个数为4
提示:用队列实现

该题与[ACM_ZJUT_2012]勘探油田思路基本一致,不作详细解释。

#include<iostream>
#include<queue>
using namespace std;
struct Pos{
	int x;
	int y;
	Pos(int _x, int _y):x(_x),y(_y){};
};
int offset[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int main(){
	int m, n, i, j, num = 0;
	cin >> m >> n;
	int **a = new int*[m];
	for(i = 0; i < m; ++i){
		a[i] = new int[n];
		for(j = 0; j < n; ++j){
			cin >> a[i][j];
		}
	}
	queue<Pos> q;
	for(i = 0; i < m; ++i){
		for(j = 0; j < n; ++j){
			if(a[i][j] > 0){
				q.push(Pos(i, j));
				while(!q.empty()){
					Pos p = q.front();
					a[p.x][p.y] = 0;
					q.pop();
					for(int k = 0; k < 4; ++k){
						int x = p.x + offset[k][0];
						int y = p.y + offset[k][1];
						if(x >= 0 && x < m && y >= 0 && y < n && a[x][y] > 0){
							q.push(Pos(x, y));
						}
					}
				}
				++num;
			}
		}
	}
	cout << num << endl;
	return 0;
}
如需转载请注明出处:蓝飞技术部落格

当前暂无评论 »