Я не могу понять, как получить мой односвязный список в мой метод сортировки. Я должен перегрузить индекс, чтобы иметь доступ к различным частям моего списка. Проблема, с которой я сталкиваюсь, заключается в том, чтобы выяснить, как изменить этот список с помощью функции сортировки.
template <typename E>
class SNode {
private:
E elem;
SNode<E>* next;
friend class SLinkedList<E>;
template <typename E>
friend ostream& operator <<(ostream& out, SLinkedList<E>& v);
};
template <typename E>
class SLinkedList {
public:
SLinkedList();
~SLinkedList();
bool empty() const;
const E& front() const;
void addFront(const E& e);
void removeFront();
int getSize();
SNode<E>* getHead();
void sort();
void printDetails() const;
//overload
E& operator[] (const int index);
const E& operator[] (const int index) const;
private:
SNode<E>* head;
int size;
};
template <typename E>
E& SLinkedList<E>::operator [](const int index) {
SNode<E>* temp = head;
for (int i = 0; i < index; i++) {
temp = temp->next;
}
E out = temp->elem;
return out;
}
template <typename E>
const E& SLinkedList<E>::operator [](const int index) const {
SNode<E>* temp = head;
for (int i = 0; i < index; i++) {
temp = temp->next;
}
E out = temp->elem;
return out;
}
template <typename E>
void SLinkedList<E>::sort() {
for (int i = 1; i < getSize(); ++i) {
E curr = (*this)[i];
int j = i - 1;
while (j >= 0 && (*this)[j] > curr); {
E temp = (*this)[i];
this->elem = (*this)[j];
this[j] = temp;
j = j - 1;
}
(*this)[j + 1] = curr;
}
}
void main() {
SLinkedList<float> lst;
int lstElems = 10;
srand(time(NULL));
for (int i = 0; i < lstElems; i++) {
lst.addFront(randGen());
}
cout << "Unsorted list: " << lst << endl;
lst.printDetails();
cout << "TEST SINGLE LIST ELEMENT: " << lst[1] << endl;
lst.sort();
cout << "Sorted list: " << lst << endl;
system("pause");
}
[]
- это O (i), где i будет доступной позицией; это ограничивает производительность любого метода сортировки как минимум O (n ^ 2), а может быть и хуже. Оператор[]
работает для массивов, потому что доступ к ним равен O(1), а со списком — нет. Вы должны разработать свой метод сортировки, не думая о позициях. Подсказка: подумайте о сортировке вставками для квадратичного алгоритма или о стратегии «разделяй/властвуй» для получения O (n log n) -быстрой сортировки или сортировки слиянием-. Любопытно, что алгоритмы «разделяй/властвуй» проще для сортировки списков, чем для массивов. Удачи - person lrleon   schedule 19.10.2015