Предыстория: мне нужно реализовать алгоритм быстрой сортировки для односвязного списка.
В алгоритме 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;
}
Да примерно так же, как у вас - только возвращать должен ссылку.
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")
}
Только сама идея такой сортировки и такого оператора несколько необычна...
Айфон мало держит заряд, разбираемся с проблемой вместе с AppLab
Как используя средства WinApi безопасно извлечь телефон или компьютерную мышь из usb порта? Уже пробовал использовать CM_Request_Eject(), удалось извлечь...
Не уверен, что правильно понял ваши пожелания, но все же: