как реализовать перегрузку оператора "=" для односвязного списка в c ++?

136
19 июня 2022, 16:50

Предыстория: мне нужно реализовать алгоритм быстрой сортировки для односвязного списка.

В алгоритме quickSort () на 24 и 25 строках кода есть оператор «=», который я не смог реализовать. Пожалуйста, помогите мне, дайте несколько примеров или идей)

Я пытался найти решение в Интернете, но были решения только для присваивания двух «list-ов» типа: sl1 = sl2. Но, как вы видете, в моем случае нам нужно присваивать «value» узла, например: arr [2] = arr [3];

#include <iostream>
using namespace std;
template <typename T>
T quickSort(T arr, int left, int right) {
    int i, j, temp, pivot;
    if(left>=right)
        return arr;
    i=left;
    j=right;
    pivot = (i+j)/2;
    while(i<j) {
        while (i<pivot && arr[i] <= arr[pivot])
            i++;
        while (j>pivot && arr[j] >= arr[pivot])
            j--;
        if(i<j) {
            temp = arr[i];
            arr[i] = arr[j];     //// // "=" operator
            arr[j] = temp;       //// // how can I implement overloading of this "=" operator???
            if(i==pivot)
                pivot=j;
            else if(j==pivot)
                pivot = i;
        }
    }
    quickSort(arr, left, pivot);
    quickSort(arr, pivot+1, right);
}
template <typename T>
class SingleList {
    class Node {
    public:
        T value;
        Node *next;
        Node(T value = T(), Node *next = nullptr) {
            this->value = value;
            this->next = next;
        }
    };
    int size;
    Node *head;
public:
    SingleList() {
        size = 0;
        head = nullptr;
    }
    int length() {
        return size;
    }
    T operator[] (int index) {
        T res = T();
        int c = 0;
        Node *cur = head;
        while (cur != nullptr) {
            if (c == index) {
                res = cur->value;
                break;
            }
            cur = cur->next;
            c++;
        }
        return res;
    }
    void pushFront(T elem) {
        if (head == nullptr)
            head = new Node(elem);
        else {
            Node *temp = new Node(elem, head);
            head = temp;
        }
        size++;
    }
    void popFront() {
        if (size <= 0)
            throw out_of_range("");
        else {
            Node *temp = head->next;
            delete head;
            head = temp;
            size--;
        }
    }
    void clearAll() {
        while (size != 0)
            popFront();
    }
    void pushBack(T elem) {
        if (head == nullptr)
            head = new Node(elem);
        else {
            Node *cur = head;
            while (cur->next != nullptr)
                cur = cur->next;
            Node *temp = new Node(elem);
            cur->next = temp;
        }
        size++;
    }
    void popBack() {
        if (size <= 0)
            throw out_of_range("");
        else {
            Node *cur = head;
            while (cur->next != nullptr)
                cur = cur->next;
            delete cur;
            size--;
        }
    }
    void add(T elem, int index) {
        if (index > size)
            throw out_of_range("");
        else if (index == 0) {
            Node *temp = new Node(elem, head);
            head = temp;
            size++;
        }
        else {
            Node *cur = head;
            int c = 0;
            while (cur != nullptr) {
                if (c == index - 1) {
                    Node *cur2 = cur->next;
                    Node *temp = new Node(elem, cur2);
                    cur->next = temp;
                    break;
                }
                cur = cur->next;
                c++;
            }
            size++;
        }
    }
    void set(T elem, int index) {
        if (index >= size)
            throw out_of_range("");
        else {
            int c = 0;
            Node *cur = head;
            while (cur != nullptr) {
                if (c == index) {
                    cur->value = elem;
                    break;
                }
                cur = cur->next;
                c++;
            }
        }
    }
    void remove(int index) {
        if (index >= size)
            throw out_of_range("");
        else if (index == size - 1) {
            int c = 0;
            Node *cur = head;
            while (cur != nullptr) {
                if (c == index - 1) {
                    Node *cur2 = cur->next;
                    delete cur2;
                    cur->next = nullptr;
                    break;
                }
                cur = cur->next;
                c++;
            }
            size--;
        }
        else if (index == 0) {
            Node *headNext = head->next;
            delete head;
            head = headNext;
            size--;
        }
        else {
            Node *cur = head;
            int c = 0;
            while (cur != nullptr) {
                if (c == index - 1) {
                    Node *cur2 = cur->next;
                    Node *cur3 = cur2->next;
                    cur->next = cur3;
                    delete cur2;
                    break;
                }
                cur = cur->next;
                c++;
            }
            size--;
        }
    }
    friend ostream& operator <<(ostream& out, SingleList<T>& l) {
        for(int i=0; i<l.length(); i++)
            out<<l[i]<<" ";
        return out;
    }
    friend istream& operator>>(istream& in, SingleList<T>& l) {
        cout << "\tEnter the size of list: ";
        int n;
        T val;
        cin >> n;
        cout << "\tEnter the elements of list: ";
        for (int i = 0; i < n; i++) {
            cin >> val;
            l.pushBack(val);
        }
        return in;
    }
    friend bool operator==(SingleList<T>& lSL, SingleList<T>& rSL) {
        if (lSL.size != rSL.size)
            return false;
        else {
            for (int i = 0; i < lSL.size; i++) {
                if (lSL[i] != rSL[i])
                    return false;
            }
            return true;
        }
    }
    friend bool operator!=(SingleList<T>& lSL, SingleList<T>& rSL) {
        if (lSL.size != rSL.size)
            return true;
        else {
            for (int i = 0; i < lSL.size; i++) {
                if (lSL[i] != rSL[i])
                    return true;
            }
            return false;
        }
    }
    ~SingleList() {
        clearAll();
    }
};
int main() {
    //TEST
    SingleList<int> sl;
    cin>>sl;
    int n = sl.length();
    SingleList<int> sortedSLL = quickSort(sl, 0, n - 1);
    cout<<"Sorted SLL: "<<sl;
    return 0;
}
Answer 1

Да примерно так же, как у вас - только возвращать должен ссылку.

 T& operator[] (int index) {
    Node *cur = head;
    int с == 0;
    while (cur != nullptr) {
        if (!index) {
            return cur->value;
        } else index--;
        cur = cur->next;
    }
    throw ::std::range_error("Out of range")
}

Только сама идея такой сортировки и такого оператора несколько необычна...

READ ALSO
Как извлечь usb устройство с помощью WinApi?

Как извлечь usb устройство с помощью WinApi?

Как используя средства WinApi безопасно извлечь телефон или компьютерную мышь из usb порта? Уже пробовал использовать CM_Request_Eject(), удалось извлечь...

146
Как четные столбцы матрицы инициализировать в обратном порядке?

Как четные столбцы матрицы инициализировать в обратном порядке?

Не уверен, что правильно понял ваши пожелания, но все же:

148