c++ - 我需要使用带有（元素，频率）对的双向链表制作一个包

Question

就像在标题中一样，我需要使用带有（元素，频率）对的双向链表来制作一个包。通过分析我做的其他项目，到目前为止我做了这个：

//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()，但由于我还需要计算频率，所以反复试验并没有让我得到任何结果。

标签： c++

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 。