工具函数模板
Last Update:
内置模板
我们前面讲了很多数据结构相关的知识,本节课程,我们主要讲解怎么不自己定义,而是使用我们所使用的编程语言中,已经定义好的数据结构。
之前我们在栈那一节已经讲过栈的内置数据结构的使用,我们本章就不再进行讲解,我们这节课仍然采用那种方式进行讲解。
知识点
- 迭代器讲解
- 线性表的使用
- 队列的使用
- 集合(set)的使用
- 映射(map)的使用
迭代器(Iterator)
首先,明确一点迭代器是 C++
的知识,并不适用于 Java
和 Python
这两种语言,但是下面讲容器就要用到这一点,所以我们必须要提前讲一下。迭代器的知识点很复杂,了解即可,当然有余力可以深究,了解就能做题,实现方式看容器讲解。
对于数组我们可以采用指针进行访问,但是对于其他的存储空间连续的数据结构或者说是存储单元我们就需要找到另一种方式来替代指针的行为作用,从而达到对于非数组的数据结构的访问和遍历,于是我们定义了一种新的变量叫做迭代器。
定义:
迭代器是一种检查容器内元素并遍历元素的数据类型。
迭代器提供对一个容器中的对象的访问方法,并且定义了容器中对象的范围。
迭代器和指针的区别:
容器和string
有迭代器类型同时拥有返回迭代器的成员。
如:容器有成员 .begin()
和 .end()
,其中 .begin()
成员复制返回指向第一个元素的迭代器,即指向第一个元素的“地址”,而 .end()
成员返回指向容器尾元素的下一个位置的迭代器。
即 .begin()
指向的是第一个合法元素的位置,.end()
指向是容器后第一个不合法元素的地址。
相应的还有容器反向迭代器成员 .rbegin()
.rend()
,.rbegin()
返回容器的元素前最后一个不合法的地址,rend()
返回容器的最后一个合法地址。
容器迭代器的使用
每种容器类型都定义了自己的迭代器类型:
1 |
|
数据类型是由 vector<int>
定义的 iterator
类型。简单说就是容器类定义了自己的 iterator
类型,用于访问容器内的元素。每个容器定义了一种名为 iterator
的类型,这种类型支持迭代器的各种行为。
我么们先讲一下各种迭代器的类型,在讲容器所用的迭代器类型,就可以明白怎么操作。
容器
写在前面,由于 Python
的语言的特点,所有的数据结构大部分都需要自己实现,但是其 List
功能较强,用起来比较简单,当然我们也会再说一遍怎么实现。
在 Java
中各种数据结构都是继承于 list
,所以 Java
的 list
功能也很强,它的功能有很多,由于篇幅原因我们会挑比较重要的讲解,其他的还需要同学们多去使用。
Vector 容器(类)
线性表中有 Vector
和 list
,两者作用比较相似。
Vector
的主要作用就是可变长度的数组,就把他当成数组使用即可。
至于为什么我们选择讲 Vector
而不是 List
,因为 Vector
可以当作数组使用,用起来非常简单,也非常方便。
我们先讲解一下 C++ 的 Vector
使用:
1 |
|
具体操作如下:
1 |
|
遍历的方式有两种:
- 迭代器使用与指针类似,可如下遍历整个容器。
1 |
|
- 当成数组使用。
1 |
|
Java 中我们一般使用 List,相信大家已经非常熟悉了,我们这里给大家补充一下 Vector 的用法,与 List 的使用方式非常的类似。
1 |
|
以下为 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$[] 返回一个包含此 Vector 中所有元素的数组正确的顺序; 返回数组的运行时类型指定数组。 |
String | toString()返回此 Vector 的字符串表示形式,包含 每个元素的字符串表示。 |
void | trimToSize()将此向量的容量修剪为向量的电流 尺寸。 |
遍历 Vector
1 |
|
Python 中,我们直接使用 list 即可来实现。
题目解析
快递员需要对快递进行分拣,现在小李是一名快递员,他想要你帮他设计一个程序用于快递的分拣,按城市分开。
现在有以下输入:
1 |
|
样例如下:
1 |
|
下面我们来分析一下解题思路。
首先我们要知道中国城市肯定在 $1000$ 个以内,但是单号我们不确定,我们不可能每个数组开 $10000$ 个,那样内存不够,所以这时候我们就用到了我们的 $vector$,他的容量是动态申请的,在比赛中我们可以理解为无限制。
- 第一步:我们创建一个 $vector$ 用于保存地址
1 |
|
- 第二步:我们创建一个 $vector$ 组用于存放单号
1 |
|
第三步:我们定义一个映射函数,因为你的城市可能会再次出现,你需要知道之前有没有。
第四步:我们开始读入操作并按照顺序进行存放
完整代码
C++ 解题代码:
1 |
|
Java 解题代码
1 |
|
Python 实现方式:
1 |
|
队列 Queue
队列的讲解在之前的课程中已经讲过了,忘记的快回去复习。
我们直接开始看操作吧。
C++ 中的队列
定义方式:在 C++ 里所有容器的定义方式基本一致。
1 |
|
成员函数:
front()
:返回queue
中第一个元素的引用。back()
:返回queue
中最后一个元素的引用。push(const T& obj)
:在queue
的尾部添加一个元素的副本。pop()
:删除queue
中的第一个元素。size()
:返回queue
中元素的个数。empty()
:如果queue
中没有元素的话,返回 true。
Java 中的队列:
定义方式:
1 |
|
部分成员函数(包括继承的):
add()
: 增加一个元索,如果队列已满,则抛出一个异常remove()
:移除并返回队列头部的元素,如果队列为空,则抛出一个异常element()
:返回队列头部的元素,如果队列为空,则抛出一个异常offer()
:添加一个元素并返回true
,如果队列已满,则返回false
poll()
: 移除并返问队列头部的元素,如果队列为空,则返回null
peek()
: 返回队列头部的元素,如果队列为空,则返回null
put()
: 添加一个元素, 如果队列满,则阻塞take()
: 移除并返回队列头部的元素,如果队列为空,则阻塞size()
: 返回队列长度。
Python 中的队列
定义方式:
1 |
|
成员函数:
Queue.qsize()
返回队列的大致大小。Queue.empty()
如果队列为空,返回True
否则返回False
Queue.full()
如果队列是满的返回True
,否则返回False
Queue.put(item, block=True, timeout=None)
- 常用时忽略默认参数,即使用
Queue.put(item)
。 - 将
item
放入队列,如果可选参数block
是true
并且timeout
是None
(默认),则在必要时阻塞至有空闲插槽可用。 - 如果
timeout
是个正数,将最多阻塞timeout
秒,如果在这段时间没有可用的空闲插槽,将引发Full
异常。 - 反之 (
block
是false
),如果空闲插槽立即可用,则把item
放入队列,否则引发Full
异常 ( 在这种情况下,timeout
将被忽略)。
- 常用时忽略默认参数,即使用
Queue.get(block=True, timeout=None)
- 常用时忽略默认参数,即使用
Queue.get()
。 - 从队列中移除并返回一个项目。如果可选参数
block
是true
并且timeout
是None
(默认值),则在必要时阻塞至项目可得到。 - 如果
timeout
是个正数,将最多阻塞timeout
秒,如果在这段时间内项目不能得到,将引发Empty
异常。反之 (block
是false
),如果一个项目立即可得到,则返回一个项目,否则引发Empty
异常 (这种情况下,timeout
将被忽略)。
- 常用时忽略默认参数,即使用
题目回顾
CLZ 的银行。
1 |
|
具体的题目讲解,我们之前就已经讲解过了,这里我们主要是来看一下预置代码的方便性。
完整代码
C++实现:
1 |
|
Java 实现
1 |
|
Python 实现
1 |
|
Map 映射
在之前我们学习散列表的时候我们就接触过了映射,这里我们要讲的是一种类似的数据结构。
map
是一个关联容器,它提供一对一的 hash
。
- 第一个可以称为关键字(
key
),每个关键字只能在map
中出现一次 - 第二个可能称为该关键字的值(
value
)
map
以模板(泛型)方式实现,可以存储任意类型的数据,包括使用者自定义的数据类型。Map
主要用于资料一对一映射(one-to-one
)的情況,map
在 C++
的內部的实现自建一颗红黑树,这颗树具有对数据自动排序的功能。在 map
内部所有的数据都是有序的。
比如,像是管理班级内的学生,Key
值为学号,Value
放其他信息的结构体或者类。
C++ 中的 map
定义方式:
1 |
|
一般用法:
- 看容量。
1 |
|
- 插入。
1 |
|
- 取值。
1 |
|
- 遍历操作
1 |
|
- 查找操作
1 |
|
Java 中的 map
定义方法:
1 |
|
这里我们讲的是排序的 map
还有不排序的 map
,java
里面叫 hashmap
,C++
里叫 unordered_map
,除了不排序,用法和功能都一样。
二者相差无几,大家如果不需要排序可以直接使用。
成员方法
方法名 | 方法描述 |
---|---|
void clear( ) | 从此映射中移除所有映射关系(可选操作)。 |
boolean containsKey(Object k) | 如果此映射包含指定键的映射关系,则返回 true。 |
boolean containsValue(Object v) | 如果此映射将一个或多个键映射到指定值,则返回 true。 |
boolean equals(Object obj) | 比较指定的对象与此映射是否相等。 |
Object get(Object k) | 返回指定键所映射的值;如果此映射不包含该键的映射关系,则返回 null。 |
int hashCode( ) | 返回此映射的哈希码值。 |
boolean isEmpty( ) | 如果此映射未包含键-值映射关系,则返回 true。 |
Set keySet( ) | 返回此映射中包含的键的 Set 视图。 |
Object put(Object k, Object v) | 将指定的值与此映射中的指定键关联 |
Object remove(Object k) | 如果存在一个键的映射关系,则将其从此映射中移除(可选操作)。 |
int size( ) | 返回此映射中的键-值映射关系数。 |
Collection values( ) | 返回此映射中包含的值的 Collection 视图。 |
Python 字典
在 Python
中我们不叫映射,也不叫 map
,我们称作字典。用法跟 Java
和 c++
都是有一定区别的。
- 字典的创建。
1 |
|
- 字典的添加。
1 |
|
- 字典的修改。
1 |
|
- 字典的删除。
1 |
|
- 字典的访问。
1 |
|
题目演练
《弗里石的的语言》
小发明家弗里想创造一种新的语言,众所周知,发明一门语言是非常困难的,首先你就要克服一个困难就是,有大量的单词需要处理,现在弗里求助你帮他写一款程序,判断是否出现重复的两个单词。
有重复就输出重复单词,重复就输出
NO
,多个重复输出最先出现的哪一个。
输入:
第 $1$ 行,输入 $N$,代表共计创造了多少个单词 第 $2$ 行至第 $N+1$ 行,输入 $N$ 个单词
格式:
1 |
|
现在有以下样例输入:
样例 1
1 |
|
样例 2
1 |
|
这个题的思路在前面我们已经讲过了,这里我们换一种方式解题。
使用映射和字典解题,是的原来的代码减少了超过一半,但是思路还是一样,可以说是非常的巧妙且省力。
C++ 解法
1 |
|
Java 解法
1 |
|
Python 解法
1 |
|