在分类袋中添加C ++ [英] Adding in a sorted bag C++

问题描述

我想在C ++中实现排序的bag（collection）数据结构（带有单链接列表），当我要测试add函数时遇到问题。这是测试：

I want to implement the sorted bag(collection) data structure(with a singly-linked list) in C++ and I have a problem when I want to test the add function. This is the test:

SortedBag sb(relation1);  (relation1 is e1<=e2) 
    sb.add(5);
    std::cout << sb.size()<<" ";
    sb.add(6);
    std::cout << sb.size() << " ";
    sb.add(0);
    std::cout << sb.size() << " ";
    sb.add(5);
    std::cout << sb.size() << " ";
    sb.add(10);
    std::cout << sb.size() << " ";
    sb.add(8);
    std::cout << sb.size() << " ";

它将打印1 2 3 3 4 5而不是1 2 3 4 5 6。

And it will print 1 2 3 3 4 5 instead of 1 2 3 4 5 6.

这是添加函数：

void SortedBag::add(TComp e) {
    Node* auxiliarElement = new Node;
    Node* CheckSLL = new Node;
    int flagStop = 1;

    if (this->head == nullptr)
    {
        auxiliarElement->value = e;
        auxiliarElement->freq = 1;
        auxiliarElement->next = nullptr;
        this->head = auxiliarElement;
    }
    else {
        CheckSLL = this->head;
        while (CheckSLL->next != nullptr && rel(CheckSLL->value, e)) 
        {
            if (CheckSLL->value == e) {
                CheckSLL->freq += 1;
                flagStop = 0;
                break;
            }
            CheckSLL = CheckSLL->next;
        }
        if (CheckSLL == this->head && flagStop)
        {
            auxiliarElement->value = e;
            auxiliarElement->freq = 1;
            auxiliarElement->next = this->head;
            this->head = auxiliarElement;
            flagStop = 0;
        }
        if (CheckSLL->value == e && flagStop)
        {
            CheckSLL->freq += 1;
            flagStop = 0;
        }
        if (flagStop) {
            auxiliarElement->value = e;
            auxiliarElement->freq = 1;
            auxiliarElement->next = nullptr;
            CheckSLL->next = auxiliarElement;
        }
    }
}

size（）函数有效很好，我也将其发布：

The size() functions works fine, I will post that too:

int SortedBag::size() const {
    int Size = 0;
    Node* goThrough = new Node;
    goThrough = this->head;
    while (goThrough != nullptr) {
        Size += goThrough->freq;
        goThrough = goThrough->next;
    }
    return Size;
}

我不知道为什么它不增加频率第二个5.有人可以帮我吗？ （struct节点具有值，freq和指向下一个节点的指针）

And I can't find out why it doesn't add the frequency from the second 5. Can somebody help me, please? (the struct Node has value,freq and a pointer to the next Node)

推荐答案

对于初学者来说，这些语句

For starters these statements

Node* CheckSLL = new Node;

和

Node* goThrough = new Node;

导致内存泄漏。

也此输出

And it will print 1 2 3 3 4 5.

与输入的数据序列不对应，因为函数 size 计算频率的总值

does not correspond to the sequence of entered data because the function size counts the total value of frequencies

Size += goThrough->freq;

因此在 6 元素中插入了列表，则输出应为

So as 6 elements were inserted in the list then the output should be

1 2 3 4 5 6

关系应指定为 e1< e2 不像 e1< = e2

函数 add 可以非常简单地定义。我假设该关系对应于运算符<。

The function add can be defined very simply. I assume that the relation corresponds to the operator <.

void SortedBag::add( TComp e ) 
{
    Node **current = &this->head;

    while ( *current != nullptr && rel( ( *current )->value, e ) )
    {
        current = &( *current )->next;
    }

    if ( *current == nullptr || rel( e, ( *current )->value ) )
    {
        Node *new_node = new Node;

        new_node->value = e;
        new_node->freq  = 1;
        new_node->next = *current;

        *current = new_node;
    }
    else
    {
        ++( *current )->freq;
    }
}

您应该确定函数 size 返回频率或列表中的节点数。

And you should decide whether the function size returns frequencies or the number of nodes in the list.

这里是一个演示程序。

#include <iostream>
#include <functional>

template <typename T, typename Comparison = std::less<T>>
class List
{
private:
    struct Node
    {
        T value;
        size_t freq;
        Node *next;
    } *head = nullptr;

    Comparison cmp;

public:
    explicit List() : cmp( Comparison() )
    {
    }

    explicit List( Comparison cmp ) : cmp( cmp )
    {
    }

    ~List()
    {
        while ( this->head != nullptr )
        {
            Node *current = this->head;
            this->head = this->head->next;
            delete current;
        }
    }

    List( const List & ) = delete;
    List & operator =( const List & ) = delete;

    void add( const T &value );

    friend std::ostream & operator <<( std::ostream &os, const List &list )
    {
        for ( Node *current = list.head; current != nullptr; current = current->next )
        {
            os << current->value << ':' << current->freq << " -> ";
        }

        return os << "null";
    }
};


template <typename T, typename Comparison>
void List<T, Comparison>::add( const T &value ) 
{
    Node **current = &this->head;

    while ( *current != nullptr && cmp( ( *current )->value, value ) )
    {
        current = &( *current )->next;
    }

    if ( *current == nullptr || cmp( value, ( *current )->value ) )
    {
        Node *new_node = new Node { value, 1, *current };

        *current = new_node;
    }
    else
    {
        ++( *current )->freq;
    }
}

int main() 
{
    List<int> list;

    list.add( 5 );
    list.add( 6 );
    list.add( 0 );
    list.add( 5 );
    list.add( 10 );
    list.add( 8 );

    std::cout << list << '\n';

    return 0;
}

程序输出为

0:1 -> 5:2 -> 6:1 -> 8:1 -> 10:1 -> null

这篇关于在分类袋中添加C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！