[ACM实验一]C++STL泛型编程（1）
杰拉斯 | 时间：2012-03-30, Fri | 6,923 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;
}
如需转载请注明出处：杰拉斯的博客
当前暂无评论 »