实验项目: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://www.clanfei.com/2012/03/298.html
欢迎访问交流,至于我为什么要多弄一个博客,因为我热爱前端,热爱网页,我更希望有一个更加自由、真正属于我自己的小站,或许并不是那么有名气,但至少能够让我为了它而加倍努力。。
=======================签 名 档=======================
分享到:
相关推荐
泛型编程入门级教程,书中包含了60多道浙江大学的ACM题目,并有详细的讲解,采用STL泛型编程思想,适合泛型编程入门,并提高自身代码能力,ACM能力。
C++ STL库函数总结(纯手打,主要偏向ACM竞赛方面使用)
C++ STL l速成 适合acmer快速上手stl
acm中常用的STL。vector、set、map、string、priority-queue、list、bitset等含详细代码以及注释。
ACM STL 模板 感兴趣的acmer值得下载吧.......................................................................................................................................................................
ACM 程序设计:STL编程及应用-1.pdf
《ACM程序设计》详细讲解了ACM国际大学生程序设计竞赛(ACM/ICPC)编程、调试方法,以及提高时间、空间性能的策略,并充分利用了c++泛型编程的高效率、规范化的特性,全部采用c++泛型编程。 第1章讲解了ACM程序设计...
ACM 程序设计:STL编程及应用-6.pdf
acm菜鸟看的stl初级模板
《ACM程序设计(第2版)》详细讲解了ACM国际大学生程序设计竞赛(ACM/ICPC)编程、调试方法,以及提高时间、空间性能的策略,并充分利用了C++泛型编程的高效率、规范化的特性,全部采用C++泛型编程。第1章讲解了ACM程序...
ACM_STL
第一篇 入门篇 1 第1章 新手入门 2 1 ACM国际大学生程序设计竞赛简介 2 2 ACM竞赛需要的知识 3 3 团队配合 5 4 练习、练习、再练习 5 5 对新手的一些建议 6 第2章 C++语言介绍 8 1 C++简介 8 2 变量 8 3 C++数据类型...
2、 C++面试宝典(林锐《高质量编程第三版》 )、 C++ primer、 Thinking in C++。 说明: 1、部分C++语言面试题中可能会参杂部分和C相关的知 识,为了保持题目的灵活性故保留,但选题最终还是 会以C++语言题目为主体...
ACM STL
C++STL培训,ACM培训一部分。
STL的好书,里面讲述了大量泛型编程的方法,对提高变成能里很有帮助
此文档涵盖了ACM 常用的STL。希望对于参加ACM的人有帮助。
ACM比赛STL 基本的函数大全
ACM实验新人指导,acm初学者的教程,几乎包括acm基础的所有东西
结合ACM真题对stl有进行了详细的解释