商业网站建设设计公司,网站的特征包括,公司建设网站申请,网站链接是什么迭代器讲解线性表的使用队列的使用集合#xff08;set#xff09;的使用映射#xff08;map#xff09;的使用
迭代器#xff08;Iterator#xff09;
迭代器是 C 的知识#xff0c;但是下面讲容器就要用到这一点#xff0c;所以我们必须要提前讲一下。迭代器的知识点…迭代器讲解线性表的使用队列的使用集合set的使用映射map的使用
迭代器Iterator
迭代器是 C 的知识但是下面讲容器就要用到这一点所以我们必须要提前讲一下。迭代器的知识点很复杂了解即可当然有余力可以深究了解就能做题实现方式看容器讲解。 对于数组我们可以采用指针进行访问但是对于其他的存储空间连续的数据结构或者说是存储单元我们就需要找到另一种方式来替代指针的行为作用从而达到对于非数组的数据结构的访问和遍历于是我们定义了一种新的变量叫做迭代器。 定义 迭代器是一种检查容器内元素并遍历元素的数据类型。 迭代器提供对一个容器中的对象的访问方法并且定义了容器中对象的范围。 迭代器和指针的区别 容器和string有迭代器类型同时拥有返回迭代器的成员。 如容器有成员 .begin() 和 .end()其中 .begin() 成员复制返回指向第一个元素的迭代器即指向第一个元素的“地址”而 .end() 成员返回指向容器尾元素的下一个位置的迭代器。 [1,2,3] 即 .begin() 指向的是第一个合法元素的位置也就是1.end() 指向是容器后第一个不合法元素的地址也就是3后面的一个位置。 相应的还有容器反向迭代器成员 .rbegin() .rend().rbegin() 返回容器的元素前最后一个不合法的地址也就是1前面的位置rend() 返回容器的最后一个合法地址也就是3所在的位置。
容器迭代器的使用
每种容器类型都定义了自己的迭代器类型
如 vectorvectorint::iterator iter;//定义一个名为iter的变量
数据类型是由 vectorint 定义的 iterator 类型。简单说就是容器类定义了自己的 iterator 类型用于访问容器内的元素。每个容器定义了一种名为 iterator 的类型这种类型支持迭代器的各种行为。
Vector 容器类
线性表中有 Vector 和 list两者作用比较相似。 vector是随机访问的可以当作数组去使用list不行list随机访问的时间是 O ( n ) O(n) O(n)的而vector是 O ( 1 ) O(1) O(1)的所以会选择vector而不是list Vector 的主要作用就是可变长度的数组就把他当成数组使用即可非常简单也非常方便。 C 的 Vector 使用
#include vector //头文件
vectorint a; //定义了一个int类型的vector容器a
vectorint b[100]; //定义了一个int类型的vector容器b组
//定义100个容器每个容器是无限可放的
//vector里可以放入自定义类型
struct rec
{···
};
vectorrec c; //定义了一个rec类型的vector容器c
vectorint::iterator it; //vector的迭代器与指针类似具体操作如下
a.size() //返回实际长度元素个数O(1)复杂度
a.empty() //容器为空返回1否则返回0O(1)复杂度
a.clear() //把vector清空
a.begin() //返回指向第一个元素的迭代器*a.begin()与a[0]作用相同
a.end() //越界访问指向vector尾部指向第n个元素再往后的边界
a.front() //返回第一个元素的值等价于*a.begin和a[0]
a.back() //返回最后一个元素的值等价于*--a.end()和a[size()-1]
a.push_back(x) //把元素x插入vector尾部
a.pop_back() //删除vector中最后一个元素遍历的方式有两种
迭代器使用与指针类似可如下遍历整个容器。 for ( vectorint::iterator ita.begin() ; it!a.end() ; it )cout*iteratorendl;for ( auto ita.begin() ; it!a.end() ; it )cout*iteratorendl;当成数组使用。
for( int i0;ia.size();i) couta[i]endl;快递分拣
快递员需要对快递进行分拣现在小李是一名快递员他想要你帮他设计一个程序用于快递的分拣按城市分开。 现在有以下输入
单号 省份
请你将单号按照城市分开并输出。
城市按照输入顺序排序
单号按照输入顺序排序样例如下
输入1010124214 北京
12421565 上海
sdafasdg213 天津
fasdfga124 北京
145252 上海
235wtdfsg 济南
3242356fgdfsg 成都
23423 武汉
23423565f 沈阳
1245dfwfs 成都输出北京 2
10124214
fasdfga124
上海 2
12421565
145252
天津 1
sdafasdg213
济南 1
235wtdfsg
成都 2
3242356fgdfsg
1245dfwfs
武汉 1
23423
沈阳 1
23423565f解题思路
首先我们要知道中国城市肯定在 1000 个以内但是单号我们不确定我们不可能每个数组开 10000 个那样内存不够所以就用到了vector他的容量是动态申请的在比赛中我们可以理解为无限制。
第一步我们创建一个 vector 用于保存地址
vectorstring city;第二步我们创建一个 vector 组用于存放单号
vectorstring dig[1000];第三步我们定义一个映射函数因为你的城市可能会再次出现你需要知道之前有没有。第四步我们开始读入操作并按照顺序进行存放
完整代码
#includeiostream
#includevector
using namespace std;vectorstring city; //放城市
vectorstring dig[1000]; //放属于这个city单号int Myfind(string s) //找到它是第几个city的数字
{for(int i0;icity.size();i){if(city[i]s) return i;}return -1;
}
int main()
{int n;cinn;for(int i0;in;i){string d,c;cindc; //输入城市单号int flagMyfind(c);if(flag-1){ //如果没找到返回-1city.push_back(c); //城市换一个新的dig[city.size()-1].push_back(d); //size是从1开始的对应的dig是从0开始的所以size()-1把单号换新的}else dig[flag].push_back(d); //找到的话把它放到所属城市的容器里面}for(int i0;icity.size();i){coutcity[i] dig[i].size()endl; //输出city和属于city的容器的大小for(int j0;jdig[i].size();j)coutdig[i][j]endl; //输出容器的内容}
}队列 Queue
从左侧进从右侧出 定义方式在 C 里所有容器的定义方式基本一致。
queuestring myqueue;
queueint myqueue_int;成员函数:
front()返回 queue 中第一个元素的引用。back()返回 queue 中最后一个元素的引用。push(const T obj)在 queue 的尾部添加一个元素的副本。pop()删除 queue 中的第一个元素。size()返回 queue 中元素的个数。empty()如果 queue 中没有元素的话返回 true。
CLZ 的银行。
第一行 M 次操作M1000 第二行 到 第M1行 输入操作
格式 IN name VOUT VIN name2 NOUT N即 第一个字符串为操作 是IN进入排队和OUT 出队 IN 排队 跟着两个字符串为姓名和权限V或N OUT 为出队即完成操作V和N代表那个窗口完成了操作
输出M次操作后V队列和N队列中姓名先输出V队列后输出N队列。
样例
输入
5
IN xiaoming N
IN Adel V
IN laozhao N
OUT N
IN CLZ V输出
Adel
CLZ
laozhao代码
#include iostream
#include queue
using namespace std;queuestring V; //一个vip队列
queuestring N; //一个普通队列int main()
{int M;cinM; //输入M次操作while(M--){string op,name,type;cinop; //先输入opif(opIN) //是进队{cinnametype; //输入名字和属于哪个队if(typeV) //属于v队进v队V.push(name);else //属于n队进n队N.push(name);}else //不是入队就是出队{cintype; //输入哪个队if(typeV) //属于v队v出队V.pop();elseN.pop(); //属于n队n出队}}//输出队列while(V.size()) //当队列中有元素时{coutV.front()endl; //输出队首V.pop(); //把它出队}while(N.size()){coutN.front()endl;N.pop();}
}Map 映射
map 是一个关联容器它提供一对一的 hash。
第一个可以称为关键字(key)每个关键字只能在 map 中出现一次 函数中的x变量 第二个可能称为该关键字的值(value) 根据x一定能找到y map 以模板泛型方式实现可以存储任意类型的数据包括使用者自定义的数据类型。 Map 主要用于资料一对一映射的情況map 在 C 的內部的实现自建一颗红黑树这颗树具有对数据自动排序的功能。在 map 内部所有的数据都是有序的。 比如像是管理班级内的学生Key 值为学号Value 放其他信息的结构体或者类。 定义方式
mapchar, int mymap1;
mapstring, int mymap2;一般用法
看容量。
int map.size();//查询map中有多少对元素
bool empty();// 查询map是否为空插入。 map.insert(make_pair(key,value));//或者map.insert(pairchar, int(key, value))//或者map[key]value取值。
mapint, string map;//如果map中没有关键字2233使用[]取值会导致插入
//因此下面语句不会报错但会使得输出结果结果为空
coutmap[2233]endl;//但是使用使用at会进行关键字检查因此下面语句会报错
map.at(2016) Bob;遍历操作
mapstring, string::iterator it;
for (it mapSet.begin(); it ! mapSet.end(); it)
{cout key it-first endl;cout value it-second endl;
}查找操作
m.count(key)//由于map不包含重复的key因此m.count(key)取值为0或者1表示是否包含。
m.find(key)//返回迭代器判断是否存在。弗里石的的语言 小发明家弗里想创造一种新的语言众所周知发明一门语言是非常困难的首先你就要克服一个困难就是有大量的单词需要处理现在弗里求助你帮他写一款程序判断是否出现重复的两个单词。 有重复就输出重复单词没有重复就输出 NO 多个重复输出最先出现的哪一个。 输入 第 1行输入 N代表共计创造了多少个单词 第 2 行至第 N1 行输入 N 个单词
格式
fjsdfgdfsg
fdfsgsdfg
bcvxbxfyres现在有以下样例输入 样例 1
输入6
1fagas
dsafa32j
lkiuopybncv
hfgdjytr
cncxfg
sdhrest输出NO样例 2
输入5
sdfggfds
fgsdhsdf
dsfhsdhr
sdfhdfh
sdfggfds输出sdfggfds题目解析
使用映射解题
代码 #include iostream#include mapusing namespace std;mapstring,bool mp;
int main ()
{int n;string ansNO; //先定一个答案NOcinn;for(int i0;in;i){string word;cinword; //输入单词if(mp.count(word)){ //计算出现的次数如果有这个单词answord; //输出break;}else mp[word]1; }coutansendl; //都处理完了输出NO就可以了}Set 使用
在C中set是一个基于红黑树实现的关联容器它可以自动将元素排序并保持唯一性。 默认情况下set使用元素类型的运算符来比较和排序其元素。 要一个自定义的排序准则可以在声明set时指定一个比较函数或函数对象。
测试
#include bits/stdc.h
using namespace std;// 1.set 的定义 set数据类型 变量名setint intSet;
setstring stringSet;int main()
{string s1测试1;string s2测试2;string s3测试3;//2. 插入操作stringSet.insert(s3);stringSet.insert(s1);//5. 返回集合元素数量printf(前2次插入操作完成后的元素数量为%d\n,stringSet.size());stringSet.insert(s2);printf(前3次插入操作完成后的元素数量为%d\n,stringSet.size());//6.遍历整个集合借助迭代器实现//定义方式 容器类型 type ::iterator namesetstring ::iterator setStringIterator;for(setStringIteratorstringSet.begin();setStringIterator!stringSet.end();setStringIterator)cout*setStringIterator ;puts();//3. 删除操作stringSet.erase(s3);printf(删除操作完成后的元素数量为%d\n,stringSet.size());for(setStringIteratorstringSet.begin();setStringIterator!stringSet.end();setStringIterator)cout*setStringIterator ;puts();//4. 判断是否由此元素if(stringSet.count(s2)!0) cout存在元素s2endl;
}运行结果
前两次插入操作完成后的元素数量为2
前两次插入操作完成后的元素数量为3
测试1 测试2 测试3
删除操作完成后的元素数量为2
测试1 测试2
存在元素测试2Process finished with exit code 0自定义排序准则
要使用自定义排序准则你可以定义一个比较函数或者更常见的是定义一个比较类比较函数对象然后将其作为第二个模板参数传递给set。
使用比较类函数对象
定义一个比较类通常更灵活因为它可以持有状态虽然在大多数排序场景中不需要。
#include iostream
#include set// 比较类
struct Compare {bool operator()(const int a, const int b) const {return a b; // 降序排序}
};int main() {std::setint, Compare s;s.insert(3);s.insert(1);s.insert(4);s.insert(2);for (int x : s) {std::cout x ;}return 0;
}在这个例子中set使用提供的比较准则来排序其元素。在第二个例子中我们定义了一个比较类并将其作为set的模板参数。
