VPF::[C++]сортировка односвязного списка

implementation

Дата 4.12.2011, 15:09 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 4.12.2011

Репутация: нет
Всего: нет

Добрый день форумчанам!
Есть задача но не знаю как написать ее так как не знаю динамического программирования )
Будьте любезны ,помогите )

Построить класс для работы с односвязна списком. Элементы списка - целые числа. сформировать
список, упорядочить элементы списка по возрастанию, используя сортировку: a) методом
выбора, б) методом пузырька, в) методом вставки.

Большое спасибо,наперед )

t_gran

Дата 5.12.2011, 08:03 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 621
Регистрация: 13.11.2007
Где: г.Усть-Илимск

Репутация: 33
Всего: 37

Цитата

Есть задача но не знаю как написать ее так как не знаю динамического программирования )

Милый друг, динамическое программирование это далеко не то, что вы под этими словами подразумеваете.

Код


#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;
}

Результат выполнения

Бинарник с исходником ниже

P.S.: В комментариях увидите, что сортировку вставками для односвязного списка можно сделать только с помощью костылей. Я не стал извращаться, дабы не быть обсмеянным коллегами.

Это сообщение отредактировал(а) t_gran - 5.12.2011, 08:04

Присоединённый файл ( Кол-во скачиваний: 16 )

archive.7z 140,75 Kb

--------------------

Я знаю, что ничего не знаю© Сократ
user posted image

recored

Дата 4.6.2013, 21:55 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 4.6.2013

Репутация: нет
Всего: нет

t_gran, Если есть возможность, залейте этот код на Си (можно лишь касаемое метода выбора).

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »