【数据结构与算法】临时抱佛脚

2018-03-10

字数统计: 1.3k字 | 阅读时长≈ 5分

咳咳，蓝桥杯在四月份就要开始了，而我还什么都没有学，先从数据结构开始抱佛脚吧。到时候即使没有名次（90%以上几率），至少还能安慰自己：“不管怎么说，至少努力了（一个月）······”

参考书为《算法竞赛入门经典》刘老师的书。

vector、set、map容器的基本用法

vector

vector是一个不定长数组，在元素不确定或时常变化的情况下适合使用。

定义：

1	vector<type> name

功能：

尾部插入元素：

1	name.push_back( element );

在i+1个元素前面插入元素：

1	name.insert(name.begin() + i, a);

删除地i+1个元素：

1	name.erase(name.begin + i);

大小：

1	name.size();

头：

1	name.begin();

尾：

1	name.end();

判断是否为空：

1	name.empty();

(如果为空，则返回1，否则返回0)

查找元素a：

1	find(name.begin(),name.end(),element);

(注意，如果找到，返回的是element的位置指针，++如果没有找到，返回的是name.end()++ );

set

set是一个集合，set内元素不能重复，需要注意的是，在set中，元素是按照升序自然排列好的，可以运用这一性质来解题。

定义：

1	set<type> name；

功能：

插入元素：

1	name.insert( element );

删除元素：

1	name.erase( element );

大小：

1	name.size();

头：

1	name.begin();

尾：

1	name.end();

判断是否为空：

1	name.empty();

(如果为空，则返回1，否则返回0)

查找元素a：

第一种方法：

1	find(name.begin(),name.end(),element);

(注意，如果找到，返回的是element的位置指针，如果没有找到，返回的是name.end() );

第二种方法：

1	name.find(element);

(同样的，如果找到，返回的是element的位置指针，如果没有找到，返回的是 name.end() );

第三种方法：

1	name.count(element)

；count函数的功能是数set中有几个element，但因为元素不能重复，所以实际上返回值只能为1或者0，因此我们可以这么想：如果有element，返回的是1，否则就是0。

map

map是一个Key-Value对应的容器，是从Key到Value的映射，Key和Value都不能重复。

定义：

1	map<type1, type2> name

功能：

插入元素：

1	name[element1] = element2;

当我们写如下语句时

1	word_count[ string("Anna") ] = 1;

将发生以下事情

a. 一个未命名的临时string对象被构造并传递给与map类相关联的下标操作符，这个对象用“Anna”初始化；

b. 在word_count中查找“Anna”项，没有找到；

c. 一个新的键/值对被插入到word_count中。当然，键是一个string对象，持有“Anna”。但是，值不是1，而是0；

d. 插入完成，接着值被赋为1；

删除元素：

查找元素a：

第一种方法：

1	Count(keyValue)：

count()返回map中keyValue出现的次数。（当然，对于 map而言，返回值只能是 0或1。）如果返回值非0，我们就可以安全地使用下标操作符。

例如：

1
2
3

int count = 0;
if ( word_count.count( "wrinkles" ))
count = word_count[ "wrinkles" ];

第二种方法：

1	Find(keyValue)：

如果实例存在，则find()返回指向该实例的iterator。如果不存在，则返回等于end()的iterator。

例如：

int count = 0;
map<string,int>::iterator it = word_count.find( "wrinkles" );
if ( it != word_count.end() )
count = (*it).second;

指向map中元素的iterator指向一个pair对象，其中first拥有键，second拥有值。

迭代器的使用及疑问

1
2
3

for(set<string>::iterator it = cup.begin();it != cup.end();it++){
        cout<<*it<<endl;
    }

这是使用迭代器输出容器中每一个元素的代码。

问题在于，为什么是

1	it != cup.end()

而不是

1	it<=cup.end()

因为在C++中，container.end()函数返回的值，指向的是container 最后一个节点的后一个节点。

为什么要这么设置？

在知乎中，有人解释这样做有以下好处：

解释一：

假设以起止指针的方式实现数组，止指针指向最后一个元素的下一个，则以下几条至始至终都正确：

数组的终点指针减去起点指针之差，再除以单个元素的长度，等于数组元素的个数；
空数组的起点指针等于终点指针；
数组的空间占用等于终点指针减去起点指针；
…
如果换成终点指针指向最后一个元素，还有多少条件能始终保持不变？
数组的终点指针减去起点指针之差，在除以单个元素的长度，再加1等于数组元素的个数。如果终点指针为NULL，则长度为0； // 变了
空素组的终点指针指向NULL;
数组的空间占用等于终点指针减去起点指针，再加上一个元素的长度，如果终点指针为NULL，则空间占用为0；// 变了

解释二：

因为STL中的begin和end定义的是一个半开放区间“[begin, end)”，end是最后一个元素的后一个位置。这样做有两个好处：

1，判断是否到尾部简单只要!=end就行了，<运算在STL中是要避免的，因为计算量可能会比较大。

2，判断空区间很简单begin()==end()
要取最后一个元素的话用last()方法。

来源：
https://www.zhihu.com/question/20638791/answer/15712282
https://www.zhihu.com/question/20638791/answer/15710634

本文作者： Yuang
本文链接： http://www.yuuuuang.com/2018/03/10/数据结构与算法的临时抱佛脚/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！