Wie man eine Liste aus einer verketteten Liste in C++ extrahiert

Question

Ich versuche, diese beiden Funktionen "extract" und "deleteList" zu implementieren und irgendwie komme ich nicht klar. Ich weiß, wie eine verkettete Liste funktioniert, aber ich bin neu in der Programmierung und kann einfach keinen Algorithmus finden. Könnte ich um ein paar Tipps bitten?

Ich möchte, dass die extract-Funktion eine Liste von Werten zurückgibt, die das Prädikat erfüllen, und diese aus der Originalliste entfernt (deshalb wird sie als Referenz übergeben).

Ich möchte, dass die delete-Funktion alle löscht, die denjenigen entsprechen, die aus dem Argument übergeben werden.

Mein Code sieht so aus:

#include 
#include 
using namespace std;

template 
struct Node
{
    T data;
    Node* next;
};
template 
void showList(const Node* head)
{
    while(head->next != NULL)
        {
            cout<data<<" ";
            head = head->next;
        }
    cout<
Node* arrayToList(const T tab[], size_t size)
{
    Node *prev;
    for(int i = size-1; i>=0 ; i--){
        Node *p = new Node;
        p->data = tab[i];
        p->next = prev;
        prev = p;
    }
    return prev;
}

template
Node* extract(Node*& head, bool (*predicate)(const T&))
{

}

template 
void deleteList(Node*& head)
{
    //delete passed in
}

bool isEven(const int& n)
{
    return n%2 == 0;
}
bool isLong(const string& s)
{
    return s.size() >=5;
}

Danke, Leute!

Answer 1

Zunächst hat Ihre showList() ein potentielles Problem beim Dereferenzieren eines Null-Zeigers. Es sollte also so aussehen:

template 
void showList(const Node* head)
{
    while(head != NULL)
    {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

Zweitens ist es praktischer, Hilfsfunktionen wie pushToList() und popFromList() zu haben:

template 
void pushToList(Node*& head, const T &element)
{
    Node *p = new Node;
    p->data = element;
    p->next = head;
    head = p;
}

template 
T popFromList(Node*& head)
{
    T value;

    if (head != NULL) {
        Node* tmp = head;
        value = head->data;
        head = head->next;
        delete tmp;
    }

    return value;
}

Sie können Ihr arrayToList() mit Hilfe von pushToList() umschreiben:

template 
Node* arrayToList(const T tab[], size_t size)
{
    Node* head = NULL;
    for(int i = size - 1; i >= 0; i--){
        pushToList(head, tab[i]);
    }
    return head;
}

Und implementieren Sie deleteList() mit Hilfe von popFromList():

template 
void deleteList(Node*& head)
{
    while (head != NULL) {
        popFromList(head);
    }
}

exctract() kann auch mit Hilfe von push und pop implementiert werden. Sie erstellen einfach zwei temporäre Listen und füllen sie entsprechend dem Prädikat:

template
Node* extract(Node*& head, bool (*predicate)(const T&))
{
    Node *extracted = NULL;
    Node *rest = NULL;

    while (head != NULL) {
        T value = popFromList(head);
        if (predicate(value)) {
            pushToList(extracted, value);
        } else {
            pushToList(rest, value);
        }
    }

    reverseList(extracted);
    reverseList(rest);

    head = rest;

    return extracted;
}

Ein Problem ist, dass die temporären Listen nach der Hauptarbeit umgekehrt werden. Daher benötigen wir die Funktion reverseList(), die ebenfalls mit push und pop implementiert werden kann:

template 
void reverseList(Node*& head)
{
    Node *result = NULL;
    while(head != NULL) {
        pushToList(result, popFromList(head));
    }
    head = result;
}

Es handelt sich nicht um eine sehr effektive Implementierung, aber ich denke, sie erledigt die Arbeit.

Ich habe den vollständigen Quellcode hier bereitgestellt.