codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <iostream> #include <cstdlib> #include <ctime> class TList { protected: struct TNode { int value; TNode* next; }; TNode* list; public: TList(): list(NULL) { ; } ~TList() { Clear(); } void Push(int theValue) { TNode* node = new TNode; node->value = theValue; node->next = list; list = node; }; bool IsEmpty() const { return (list == NULL); } int Top() const { return list->value; } int Pop() { int value = list->value; TNode* node = list; list = list->next; delete node; return value; } void Clear() { while (!IsEmpty()) { Pop(); } } friend std::ostream& operator << (std::ostream& theOS, const TList& theList) { TList::TNode* node = theList.list; while (node) { theOS << node->value << " "; node = node->next; } return theOS; } // В связи с отсутствием реализации итератора (дабы не разрывать вам мозг) // пришлось стать другом для класса TOperation. Можно конечно операции // прикрутить тут же, но это будет форменным безобразием, и я на такое не пойду friend class TOperation; }; class TOperation { protected: static void Swap(int& theA, int& theB) { int buff = theA; theA = theB; theB = buff; } public: static void AppendRandom(TList& list, unsigned count) { ::srand(::time(NULL)); while (count--) { list.Push(::rand() % 90 + 10); } } // Все сортировки выполняются путем перестановки значений // а не изменением указателей на узлы static void SortSelection(TList& list) { TList::TNode* head = list.list; while (head) { TList::TNode* marker = head; TList::TNode* cursor = head; while (cursor) { if (cursor->value < marker->value) { marker = cursor; } cursor = cursor->next; } Swap(head->value, marker->value); head = head->next; } } static void SortBubble(TList& list) { if (list.IsEmpty()) { return; } TList::TNode* head = list.list; TList::TNode* tail = list.list; while (tail->next) { tail = tail->next; } while (head != tail) { TList::TNode* cursor = head; TList::TNode* prev = head; while (cursor != tail) { if (cursor->value > cursor->next->value) { Swap(cursor->value, cursor->next->value); } prev = cursor; cursor = cursor->next; } tail = prev; } } static void SortInsert(TList& list) { // Данный вид сортировки абсурден для односвязного списка, // т.к. данная сортировка предпологает прямые и обратные проходы. // Если бы у нас был двусвязный список, то проблем бы небыло // http://ru.wikipedia.org/wiki/Сортировка_вставками } }; int main() { TList list; // Тест сортировки выброром std::cout << "Insert Sort Test" << std::endl; TOperation::AppendRandom(list, 20); std::cout << "list: " << list << std::endl; TOperation::SortSelection(list); std::cout << "sort: " << list << std::endl; std::cout << std::endl; list.Clear(); // Тест сортировки пузырьком std::cout << "Bubble Sort Test" << std::endl; TOperation::AppendRandom(list, 20); std::cout << "list: " << list << std::endl; TOperation::SortBubble(list); std::cout << "sort: " << list << std::endl; return 0; }
Private
[
?
]
Run code
Submit