【数据结构】c++实现背包数据结构

背包是一种不支持从中删除元素的集合数据类型。它的目的就是帮助用例收集元素并迭代遍历所有收集到的元素（用例也可以检查背包是否为空或者获取背包中元素的数量）。迭代的顺序不确定且与用例无关。要理解背包的概念，可以想象一个非常喜欢收集弹子球的人。他讲所有的弹子球都放在一个背包里，一次一个，并且会不时在所有弹子球中寻找某一颗拥有某种特点的弹子球。使用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++内置了数组，链表也很容易通过结构体进行构造。这两者非常基础，常常被称为顺序存储和链式存储。

数据结构	优点	缺点
数组	通过索引可以直接访问任意元素	在初始化时就需要知道元素的数量
链表	使用的空间大小和元素的数量成正比	需要通过引用或者指针访问任意元素