背包是一种不支持从中删除元素的集合数据类型。它的目的就是帮助用例收集元素并迭代遍历所有收集到的元素(用例也可以检查背包是否为空或者获取背包中元素的数量)。迭代的顺序不确定且与用例无关。要理解背包的概念,可以想象一个非常喜欢收集弹子球的人。他讲所有的弹子球都放在一个背包里,一次一个,并且会不时在所有弹子球中寻找某一颗拥有某种特点的弹子球。使用Bag的API,用例可以将元素添加进背包并根据需要随时使用for语句访问所有元素。用例也可以使用栈或是队列,但使用Bag可以说明元素的处理顺序不重要。
下面看实现代码:
template class Bag
{
public:
Bag(){}//和Stack的push()方法完全相同
void add(T item)
{
Node *oldFirst = first;
first = new Node();
first->item = item;
first->next = oldFirst;
}private:
struct Node
{
T item;
Node *next = nullptr;
};
Node *first = nullptr;
public:
//定义迭代器
class Iterator
{
friend class Bag;
//声明为友元
public:
Iterator() {}//重载相关的运算符
bool operator ==(const Iterator &iter) const
{
return current == iter.current;
}bool operator !=(const Iterator &iter) const
{
return current != iter.current;
}T& operator *() const
{
return current->item;
}Iterator operator ++(int) const
{
Iterator temp = *this;
current = current->next;
return temp;
}Iterator& operator ++()
{
current = current->next;
return *this;
}bool atEnd() const
{
return current == nullptr;
}protected:
Iterator(Node *p):current(p){}//上面声明了友元,所以才能调用这个构造函数Node *current = nullptr;
};
//定义相关的迭代器用法
Iterator begin()
{
return Iterator(first);
}Iterator end()
{
return Iterator(nullptr);
}};
该背包的实现同样是通过链表来实现,只需要将之前写的Stack实现中的push改名为add,并把pop去掉即可实现。并添加迭代器的实现,用来遍历其中的数据。迭代器的实现直接看代码即可。
下面是运用的代码:
int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);
Bag bag = Bag();
for(int i = 0;
i < 10;
++i)
{
bag.add(i);
}Bag::Iterator iter;
for(iter = bag.begin();
iter != bag.end();
++iter)
{
cout << *iter << endl;
}return a.exec();
}
运行结果为:

文章图片
小结:
通过实现实现了栈、队列、背包,我们拥有两种表示对象集合的方式,即数组和链表。c++内置了数组,链表也很容易通过结构体进行构造。这两者非常基础,常常被称为顺序存储和链式存储。
数据结构 | 优点 | 缺点 |
数组 | 通过索引可以直接访问任意元素 | 在初始化时就需要知道元素的数量 |
链表 | 使用的空间大小和元素的数量成正比 | 需要通过引用或者指针访问任意元素 |
推荐阅读
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- 数据结构和算法|LeetCode 的正确使用方式
- 先序遍历 中序遍历 后序遍历 层序遍历
- 数据结构|C++技巧(用class类实现链表)
- 数据结构|贪吃蛇代码--c语言版 visual c++6.0打开
- 算法|算法-二分查找
- 数据结构学习指导|数据结构初阶(线性表)
- leetcode题解|leetcode#106. 从中序与后序遍历序列构造二叉树
- java|ObjectOrientedProgramming - 面向对象的编程(多态、抽象类、接口)- Java - 细节狂魔