c++ - 努力使用链表实现 Set

Question

我的任务是用链表实现一个集合。我很快就创建了链表，然后开始构建集合。我在设置操作(并集/交集/差集)上遇到了一些困难，但是在实现之后我尝试制作一个驱动程序方法，现在我遇到了包含/添加的段错误。结果我无法正确检查我的操作。我不明白为什么会出现此错误。我忽略了一些东西...任何帮助将不胜感激。

链表.h

class ListNode
{

private:
    ListNode* prev;
    ListNode* next;
    int data;

public:
    ListNode() { prev = next = NULL;
    data=0;}
    ListNode(int d, ListNode* p, ListNode* n) { data = d; prev = p; next = n; }

    friend class List;
};

class List
{
private:
    ListNode* head;
    ListNode* tail;

public:
    List() { head = tail = NULL; }
    ~List();

    bool isEmpty() { return head == NULL; }
    bool contains(int value);

    void addToHead(int value);
    void addToTail(int value);

    int removeHead();
    int removeTail();

    int removeAt(int index);
    bool remove(int value);

    int at(int index);
    int valueOf(const ListNode* elem);
    const ListNode* getNext(const ListNode* node);
    const ListNode* getPrevious(const ListNode* node);
    const ListNode* getHead() { return head; }
    const ListNode* getTail() { return tail; }

    void print();
};

List::~List()
{
    while (!isEmpty())
        removeTail();
}

bool List::contains(int value)
{
    ListNode *tmp = head;  // <**This is where error occurs**
    while (tmp != NULL && tmp->data != value)
        tmp = tmp->next;

    return tmp != NULL;
}

void List::addToHead(int value)
{
    if (isEmpty())
    {
        head = tail = new ListNode(value, NULL, NULL);
    }
    else
    {
        head = new ListNode(value, NULL, head);
        head->next->prev = head;
    }
}

void List::addToTail(int value)
{
    if (isEmpty())
    {
        head = tail = new ListNode(value, NULL, NULL);
    }
    else
    {
        tail = new ListNode(value, tail, NULL);
        tail->prev->next = tail;
    }
}

int List::removeHead()
{
    int value = head->data;
    if (head == tail)
    {
        delete tail;
        head = tail = NULL;
    }
    else
    {
        head = head->next;
        delete head->prev;
        head->prev = NULL;
    }

    return value;
}

int List::removeTail()
{
    int value = head->data;
    if (head == tail)
    {
        delete tail;
        head = tail = NULL;
    }
    else
    {
        tail = tail->prev;
        delete tail->next;
        tail->next = NULL;
    }

    return value;
}



int List::removeAt(int index)
{

//    Remove the node at index. Return the int value contained at
//    the now removed node. Exit program if an invalid 
    ListNode *temp = head;
    int i=0;
    if (index == 0) {
        removeHead();
    }
    while (temp != NULL && i < index-1) {
        temp = temp->next;
        i++;
    }
    if (temp == NULL || temp -> next == NULL ) {
        exit(1);
    }
    else{
        ListNode* temp2 = temp->next;
        temp->next = temp->next->next;
        temp2->next = NULL;
        delete temp2; }
}

bool List::remove(int value)
{

//    Remove the provided value if it is contained in the list. Return true if the
//        value was found and remove, return false if no changes were made to the list
    ListNode *prev = head;
    ListNode* temp = head->next;

    if (prev->data==value){
       removeHead();
    }
else {
        while (temp != NULL && temp->data != value) {
            prev = temp;
            temp = temp->next;
        }

        if (temp == NULL) {
            cout << "No change" << endl;
            return false;
        } else {
            prev->next = temp->next; // unlink the node you remove
            delete temp; // delete the node
        }
    }
}

int List::at(int index)
{
//    Returns the int value contained at the node at the provided index. Exit program if
//        an invalid index is provided
    ListNode *temp = head;
    for(int i=1; i < index; i++) {
        if (temp -> next == NULL){
            exit(1);
        }
        temp = temp->next;
    }

    return valueOf(temp);
}


int List::valueOf(const ListNode* elem)
{

    return elem->data;
}

const ListNode* List::getNext(const ListNode* node)
{

    return node->next;
}

const ListNode* List::getPrevious(const ListNode* node)
{

    return node->prev;
}

void List::print() {

    ListNode *tmp = head;
    if (tmp != NULL) {
        do {
            if (tmp != NULL) {
                cout << tmp->data << " -> ";
                tmp = tmp->next;
            }
        } while (tmp != NULL);
    }
    cout << endl;
}
#endif //UNTITLED4_LIST_H

设置

#include <iostream>
#include "list.h"

using namespace std;

class Set
{
private:
    List* list;
    int set_size;
public:
    Set();
    ~Set();

    bool contains(int value);
    bool add(int value);
    bool remove(int value);
    void clear();

    Set* set_union(Set&);
    Set* intersection(Set&);
    Set* difference(Set&);

    void print();
    int size() { return set_size; }
};

    Set::Set() {
        list = NULL;
        set_size = 0;
    }

    Set::~Set() {
        delete list;
        set_size = 0;
    }

    bool Set::contains(int value) {
        // Returns a boolean value representing if the provided int value is contained
        //in the list
        if(list->contains(value)){
            return false;
        }
        else{
            list->addToHead(value);
            set_size++;
            return true;
        }
    }

    bool Set::add(int value) {
    //    Returns a boolean value representing if the provided int value was successfully
    //    added to the list do not allow duplicate


        if (!contains(value))
        { list->addToTail(value);}

        else {return false;}

    }

    bool Set::remove(int value) {

      return  list->remove(value);
    }

    void Set::clear() {
    //This function should assign 0 to set_size, and delete list.
        set_size = 0;
        delete list;
    }

    Set *Set::set_union(Set &s) {
        //Creates and returns a Set pointer that contains the set union of the
        //invoking Set object and a second Set object passed into the function
        Set *temp = new Set();

        for(int t= 1;t<s.set_size; t++)
           temp->add(s.list->at(t));

        return  temp;

    }

    Set *Set::intersection(Set &s) {
    //    Creates and returns a Set pointer that contains the set intersection of the
    //    invoking Set object and a second Set object passed into the function.
        Set *temp = new Set();
        for ( int i = 0; i < set_size; i++) {
            if (s.contains(list->at(i))) {
                temp->add(list->at(i));
            }
        }
        return temp;
    }

    Set *Set::difference(Set &s) {
    //    Creates and returns a Set pointer that contains the set difference between
    //    the invoking Set object and a second Set object passed into the function. The
    //    invoking Set object should be considered the set that is being subtracted from (
    //    Invoking Set – Parameter Set)

        Set *temp = new Set();
        for ( int i = 0; i < set_size; i++) {
            if (s.contains(list->at(i))) {
                temp->add(list->at(i));
            }
        }
        for( int i = 0; i < set_size; i++){
            if (temp->contains(list->at(i))) {
                s.remove(list->at(i));
            }
        }
        return temp;
    }

    void Set::print() {
    //    TO DO --- Already have print in list

    }

    int main() {
        int choice, item, size1, size2;
        cout << "Please Enter the starting Value of Set#1:";
        cin >> size1;
        Set set1;
        cout << "\nPlease Enter the starting Value of Set#2:";
        cin >> size2;
        Set set2;

        cout << "\n Enter " << size2 << " numbers in Set1:";
        for (int i = 1; i < size1; i++) {
            cin >> item;
            set1.add(item);
        }

        cout << "\n Enter " << size2 << " numbers in Set2:";
        for (int i = 1; i < size1; i++) {
            cin >> item;
            set2.add(item);
        }

        while (choice !=7) {
            cout << "1.Insert Element into the Set" << endl;
            cout << "2.Delete Element of the Set" << endl;
            cout << "3.Size of the Set" << endl;
            cout << "4.Union of Set" << endl;
            cout << "5.intersections of set" << endl;
            cout << "6.difference of set" << endl;
            cout << "7.Exit" << endl;
            cout << "Enter your Choice: ";
            cin >> choice;
            switch (choice) {
                case 1:
                    cout << "Enter value to be inserted: ";
                    cin >> item;
                    // st.insert(item);
                    break;
                case 2:
                    cout << "Enter the element to be deleted: ";
                    cin >> item;
                    //st.erase(item);
                    break;
                case 3:
                    cout << "Size of the Set1: ";
                    cout << set1.size() << endl;
                    cout << "\nSize of the Set2: ";
                    cout << set2.size() << endl;

                    break;
                case 4:

                    break;
                case 5:

                    break;
                case 6:
                    exit(1);
                default:
                    cout << "Wrong Choice" << endl;
            }
        }
        return 0;
    }

Answer 1

您的 Set 对象包含一个指向 List(链表)的指针，该指针在 Set 构造函数中被分配给 NULL，但没有此 List 的内存已分配。这就是为什么每次您尝试对该 List 进行操作时，您的应用程序都会出现段错误的原因。

您要么需要:

• 检查这个列表是否需要在堆上分配(让 Set 持有一个 List 而不是 List*)<
• 为 Set 对象中的 List(With new)正确分配内存。