[ create a new paste ] login | about

Link: http://codepad.org/IV7Fvuxc    [ raw code | output | fork ]

t_gran - C++, pasted on Dec 5:
#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;
}


Output:
1
2
3
4
5
6
7
Insert Sort Test
list: 11 89 77 66 25 24 38 76 71 64 82 49 86 22 97 55 57 18 15 25 
sort: 11 15 18 22 24 25 25 38 49 55 57 64 66 71 76 77 82 86 89 97 

Bubble Sort Test
list: 11 89 77 66 25 24 38 76 71 64 82 49 86 22 97 55 57 18 15 25 
sort: 11 15 18 22 24 25 25 38 49 55 57 64 66 71 76 77 82 86 89 97 


Create a new paste based on this one


Comments: