我需要用(元素，频率)对的双链表做一个包

Question

就像标题中一样，我需要使用带有(element，frequency(对的双链表来制作一个包。通过分析我做的其他项目，到目前为止我做了这个：

//bag.h
#pragma once
#include <utility>
using namespace std;
//DO NOT INCLUDE BAGITERATOR
//DO NOT CHANGE THIS PART
#define NULL_TELEM -111111;
typedef int TElem;
class BagIterator; 
class Bag {
private:
struct node
{
pair<TElem, int> info;
node* prev;
node* next;
};
node* head;
node* tail;
friend class BagIterator;
public:
//constructor
Bag();
//adds an element to the bag
void add(TElem e);
//removes one occurence of an element from a bag
//returns true if an element was removed, false otherwise (if e was not part of the bag)
bool remove(TElem e);
//checks if an element appearch is the bag
bool search(TElem e) const;
//returns the number of occurrences for an element in the bag
int nrOccurrences(TElem e) const;
//returns the number of elements from the bag
int size() const;
//returns an iterator for this bag
BagIterator iterator() const;
//checks if the bag is empty
bool isEmpty() const;
//destructor
~Bag();

和

//bag.cpp
#include "Bag.h"
#include "BagIterator.h"
#include <exception>
#include <iostream>
using namespace std;
Bag::Bag() {
//TODO - Implementation
this->head = nullptr;
this->tail = nullptr;
}
void Bag::add(TElem elem) {
//node* n;
//n = new node;
//n->pair.first = elem;
//dont know how to do it/continue it.
}

所以基本上我不知道如何实现add((函数。我想如果我有add((作为模型，我可以制作其他函数，比如remove((和search((，但由于我还需要计算频率，试错并没有让我取得任何进展。

Answer 1

试试这个。

void add(TElem elem) {
node* n = nullptr;
n = new node;
n->info.first = elem;
if (this->tail == nullptr) { //if we don't have an end
if (this->head == nullptr) { //if we dont have a start
this->head = n; //set the start to n
}
this->tail = n; //set the end to n
}
else {
this->tail->next = n; //our bag's end's next node equals n;
n->prev = this->tail; //n's previous equals our current tail
this->tail = this->tail->next; //our tail equals n
}
}

它为包的末端添加了一个元素。我还做了一个删除功能：

bool remove(TElem e) {
if (this->head == nullptr||this->tail==nullptr) return false; //if we have no elements
node* traverser = this->head; //our starting point is our bag's starting point
while (true) {
if (traverser->info.first == e) { //if we found our element
node* last = traverser->prev; //the element before ours
node* succ = traverser->next; //the element after ours
last->next = succ; //put the element before our's 's next element to the element after our's
succ->prev = last; //set the element after our's 's previous element to the element before our's
delete traverser; //delete our element
return true; 
}
else
if (traverser->next == nullptr) return false; //If we reached the end
else traverser = traverser->next; //move forward
}
}

此外，我建议您将此构造函数添加到node类中：

node() : prev(nullptr), next(nullptr) {} 

只是为了不出现错误。

此外，如果您感兴趣，也许这个迭代器模型对您有用：https://docs.google.com/document/d/1OOqm3ZnUc0ah-etI6ZbCuo41S0f_czoYcSOLwaNIQzM/edit?usp=sharing.