[ACM实验一]C++STL泛型编程（1）

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

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;
}

原文地址（本人博客）：http://lanfei.sinaapp.com/2012/03/298.html

欢迎访问交流。