我们前面讲了很多数据结构相关的知识，本节课程，我们主要讲解怎么不自己定义，而是使用我们所使用的编程语言中，已经定义好的数据结构。
之前我们在栈那一节已经讲过栈的内置数据结构的使用，我们本章就不再进行讲解，我们这节课仍然采用那种方式进行讲解。
知识点
迭代器讲解
线性表的使用
队列的使用
映射（map）的使用
迭代器（Iterator）
首先，明确一点迭代器是 C++ 的知识，并不适用于 Java 和 Python 这两种语言，但是下面讲容器就要用到这一点，所以我们必须要提前讲一下。
迭代器的知识点很复杂，了解即可，当然有余力可以深究，了解就能做题，实现方式看容器讲解。
对于数组我们可以采用指针进行访问，但是对于其他的存储空间连续的数据结构或者说是存储单元我们就需要找到另一种方式来替代指针的行为作用，从而达到对于非数组的数据结构的访问和遍历，于是我们定义了一种新的变量叫做迭代器。
定义：
迭代器是一种检查容器内元素并遍历元素的数据类型。
迭代器提供对一个容器中的对象的访问方法，并且定义了容器中对象的范围。
容器和 string 有迭代器类型同时拥有返回迭代器的成员。
如：容器有成员 .begin() 和 .end(),其中 .begin() 成员复制返回指向第一个元素的迭代器，即指向第一个元素的“地址”，而 .end() 成员返回指向容器尾元素的下一个位置的迭代器。
即 .begin() 指向的是第一个合法元素的位置，.end() 指向是容器后第一个不合法元素的地址。
相应的还有容器反向迭代器成员 .rbegin() .rend(), .rbegin() 返回容器的元素前最后一个不合法的地址，rend() 返回容器的最后一个合法地址。
每种容器类型都定义了自己的迭代器类型：
如 vector：vector< int>:: iterator iter;//定义一个名为iter的变量
copy
数据类型是由 vector< int> 定义的 iterator 类型。
简单说就是容器类定义了自己的 iterator 类型，用于访问容器内的元素。
每个容器定义了一种名为 iterator 的类型，这种类型支持迭代器的各种行为。
我么们先讲一下各种迭代器的类型，在讲容器所用的迭代器类型，就可以明白怎么 *** 作。
容器
写在前面，由于 Python 的语言的特点，所有的数据结构大部分都需要自己实现，但是其 List 功能较强，用起来比较简单，当然我们也会再说一遍怎么实现。
在 Java 中各种数据结构都是继承于 list，所以 Java 的 list 功能也很强，它的功能有很多，由于篇幅原因我们会挑比较重要的讲解，其他的还需要同学们多去使用。
Vector 容器（类）
线性表中有 Vector 和 list，两者作用比较相似。
Vector 的主要作用就是可变长度的数组，就把他当成数组使用即可。
至于为甚我们我选择讲 Vector 而不是 List，因为 Vector 可以当作数组使用，用起来非常简单，也非常方便。
我们先讲解一下 c++ 的 Vector 使用：
#include 具体 *** 作如下：
a.size() //返回实际长度（元素个数），O(1)复杂度
a.empty() //容器为空返回1，否则返回0，O(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 ( vector<int>::iterator it=a.begin() ; it!=a.end() ; it++ )
cout<<*iterator<<endl;
当成数组使用。
for( int i=0;i<a.size();i++) cout<<a[i]<<endl;
上面我们讲解了 C++ 的实现方式，下面我们了解一下 java 的。
//第一种构造方法创建一个默认的向量，默认大小为 10：
Vector()
//第二种构造方法创建指定大小的向量。
Vector(int size)
//第三种构造方法创建指定大小的向量，并且增量用 incr 指定。
增量表示向量每次增加的元素数目。
Vector(int size,int incr)
//第四种构造方法创建一个包含集合 c 元素的向量：
Vector(Collection c)
以下为 Java Vector 的 Api。
修饰符和类型 方法和说明
boolean add(E e)将指定的元素附加到此 Vector 的末尾。
void add(int index, E element)在此 Vector 的指定位置插入指定元素。
boolean addAll(Collection<? extends E> c)将指定集合中的所有元素追加到末尾 这个向量，按照它们由指定的返回的顺序 集合的迭代器。
boolean addAll(int index, Collection<? extends E> c)将指定 Collection 中的所有元素插入到此 指定位置的向量。
void addElement(E obj)将指定的组件添加到此向量的末尾， 将其大小增加一。
int capacity()返回此向量的当前容量。
void clear()从此 Vector 中删除所有元素。
Object clone()返回此向量的克隆。
boolean contains(Object o)退货 true 如果此向量包含指定的元素。
boolean containsAll(Collection<?> c)如果此 Vector 包含所有元素，则返回 true 指定的集合。
void copyInto(Object[] anArray)将此向量的分量复制到指定的数组中。
E elementAt(int index)返回指定索引处的组件。
Enumeration elements()返回此向量的组件的枚举。
void ensureCapacity(int minCapacity)如有必要，增加此向量的容量，以确保它至少可以容纳由指定的组件数量最小容量参数。
boolean equals(Object o)比较指定的 Object 与此 Vector 是否相等。
E firstElement()返回第一个组件（索引处的项目 0） 的这个向量。
E get(int index)返回此 Vector 中指定位置的元素。
int hashCode()返回此 Vector 的哈希码值。
int indexOf(Object o)返回指定元素第一次出现的索引 在此向量中，如果此向量不包含该元素，则为 -1。
int indexOf(Object o,int index)返回指定元素第一次出现的索引这个向量，从 index, 或返回 -1 如果 未找到该元素。
void insertElementAt(E obj, int index)将指定对象作为组件插入此向量中的 指定的 index.
boolean isEmpty()测试此向量是否没有组件。
Iterator iterator()以适当的顺序返回此列表中元素的迭代器
E lastElement()返回向量的最后一个组件。
int lastIndexOf(Object o)返回指定元素最后一次出现的索引在此向量中，如果此向量不包含该元素，则为 -1。
int lastIndexOf(Object o, int index)返回指定元素最后一次出现的索引这个向量，从 index, 或返回 -1 如果 未找到该元素。
ListIterator listIterator()返回此列表中元素的列表迭代器（在适当的顺序）。
ListIterator listIterator(int index)返回此列表中元素的列表迭代器（在适当的序列），从列表中的指定位置开始。
E remove(int index)移除此 Vector 中指定位置的元素。
boolean remove(Object o)移除此 Vector 中第一次出现的指定元素如果 Vector 不包含该元素，则它保持不变。
boolean removeAll(Collection<?> c)从此 Vector 中删除其包含在指定的集合。
void removeAllElements()从此向量中删除所有组件并将其大小设置为零。
boolean removeElement(Object obj)删除参数的第一个（最低索引）出现从这个向量。
void removeElementAt(int index)删除指定索引处的组件。
protected void removeRange(int fromIndex, int toIndex)从此列表中删除索引介于两者之间的所有元素 fromIndex，包括在内，和 toIndex， 独家的。
boolean retainAll(Collection<?> c)仅保留此 Vector 中包含在指定的集合。
E set(int index, E element)将此 Vector 中指定位置的元素替换为指定的元素。
void setElementAt(E obj,int index)将组件设置在指定的位置 index 这个的向量是指定的对象。
void setSize(int newSize)设置此向量的大小。
int size()返回此向量中的组件数。
List subList(int fromIndex,int toIndex)返回此列表中 fromIndex 之间的部分的视图
Object[] toArray()返回一个包含此 Vector 中所有元素的数组以正确的顺序。
T[] toArray(T[] a)返回一个包含此 Vector 中所有元素的数组正确的顺序; 返回数组的运行时类型指定数组。
String toString()返回此 Vector 的字符串表示形式，包含 每个元素的字符串表示。
void trimToSize()将此向量的容量修剪为向量的电流 尺寸。
遍历 Vector
Enumeration vEnum = v.elements();
while (vEnum.hasMoreElements())
System.out.print(vEnum.nextElement() + " ");
Python 中，我们直接使用 list 即可来实现。
题目解析
快递员需要对快递进行分拣，现在小李是一名快递员，他想要你帮他设计一个程序用于快递的分拣，按城市分开。
现在有以下输入：
单号 省份
请你将单号按照城市分开，并输出。
城市按照输入顺序排序
单号按照输入顺序排序
copy
样例如下：
输入
10
10124214 北京
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
copy
下面我们来分析一下解题思路。
首先我们要知道中国城市肯定在 1000 个以内，但是单号我们不确定，我们不可能每个数组开 10000 个，那样内存不够，所以这时候我们就用到了我们的 vector，他的容量是动态申请的，在比赛中我们可以理解为无限制。
第一步：我们创建一个 vector 用于保存地址
vector city;
copy
第二步：我们创建一个 vector 组用于存放单号
vector dig[1000];
copy
第三步：我们定义一个映射函数，因为你的城市可能会再次出现，你需要知道之前有没有。
第四步：我们开始读入 *** 作并按照顺序进行存放
完整代码
C++ 解题代码：
```cpp
#include<iostream>
#include<vector>
using namespace std;
vector<string> city;
vector<string> dig[1000];
int Myfind(string s)
{
for(int i=0;i<city.size();i++)
{
if(city[i]==s) return i;
}
return -1;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
string d,c;
cin>>d>>c;
int flag=Myfind(c);
if(flag==-1){
city.push_back(c);
dig[city.size()-1].push_back(d);
}
else dig[flag].push_back(d);
}
for(int i=0;i<city.size();i++)
{
cout<<city[i]<<" "<<dig[i].size()<<endl;
for(int j=0;j<dig[i].size();j++)
cout<<dig[i][j]<<endl;
}
}
```cpp
Java 解题代码
Python 实现方式
队列 Queue
队列的讲解在之前的课程中已经讲过了，忘记的快回去复习。
我们直接开始看 *** 作吧。
C++ 中的队列
定义方式：在 C++ 里所有容器的定义方式基本一致。
queue<string> myqueue;
queue<int> myqueue_int;
成员函数:
front()：返回 queue 中第一个元素的引用。
back()：返回 queue 中最后一个元素的引用。
push(const T& obj)：在 queue 的尾部添加一个元素的副本。
pop()：删除 queue 中的第一个元素。
size()：返回 queue 中元素的个数。
empty()：如果 queue 中没有元素的话，返回 true。
Java 中的队列
Python 中的队列
题目回顾
CLZ 的银行。
第一行 M 次 *** 作（M<1000）
第二行 到 第M+1行 输入 *** 作
格式： IN name V
OUT V
IN name2 N
OUT 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
copy
具体的题目讲解，我们之前就已经讲解过了，这里我们主要是来看一下预置代码的方便性。
完整代码
C++实现：
#include copy
Java 实现
Python 实现
Map 映射
在之前我们学习散列表的时候我们就接触过了映射，这里我们要讲的是一种类似的数据结构。
map 是一个关联容器，它提供一对一的 hash。
第一个可以称为关键字(key)，每个关键字只能在 map 中出现一次
第二个可能称为该关键字的值(value)
map 以模板（泛型）方式实现，可以存储任意类型的数据，包括使用者自定义的数据类型。
Map 主要用于资料一对一映射（one-to-one）的情況，map 在 C++ 的內部的实现自建一颗红黑树，这颗树具有对数据自动排序的功能。
在 map 内部所有的数据都是有序的。
比如，像是管理班级内的学生，Key 值为学号，Value 放其他信息的结构体或者类。
C++ 中的 map
定义方式：
map<char, int> mymap1;
map<string, int> mymap2;
一般用法：
看容量。
int map.size();//查询map中有多少对元素
bool empty();// 查询map是否为空
copy
插入。
map.insert(make_pair(key,value));
//或者
map.insert(pair<char, int>(key, value))
//或者
map[key]=value
取值。
map<int, string> map;
//如果map中没有关键字2233，使用[]取值会导致插入
//因此，下面语句不会报错，但会使得输出结果结果为空
cout<<map[2233]<<endl;
//但是使用使用at会进行关键字检查，因此下面语句会报错
map.at(2016) = "Bob";
copy
遍历 *** 作
map<string, 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)：//返回迭代器，判断是否存在。
copy
Java 中的 map
Python 字典
题目演练
《弗里石的的语言》
小发明家弗里想创造一种新的语言，众所周知，发明一门语言是非常困难的，首先你就要克服一个困难就是，有大量的单词需要处理，现在弗里求助你帮他写一款程序，判断是否出现重复的两个单词。
有重复就输出重复单词，重复就输出 NO，多个重复输出最先出现的哪一个。
输入：
第 1 行，输入N，代表共计创造了多少个单词
第 2 行至第 N+1 行，输入 N 个单词
格式：
fjsdfgdfsg
fdfsgsdfg
bcvxbxfyres
copy
现在有以下样例输入：
样例 1
输入：
6
1fagas
dsafa32j
lkiuopybncv
hfgdjytr
cncxfg
sdhrest
输出：
NO
copy
样例 2
输入：
5
sdfggfds
fgsdhsdf
dsfhsdhr
sdfhdfh
sdfggfds
输出：
sdfggfds
copy
这个题的思路在前面我们已经讲过了，这里我们换一种方式解题。
使用映射和字典解题，是的原来的代码减少了超过一半，但是思路还是一样，可以说是非常的巧妙且省力。
C++ 解法
#include 欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）