Модераторы: Poseidon, Rodman
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [C++]сортировка односвязного списка 
:(
    Опции темы
implementation
Дата 4.12.2011, 15:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

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



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


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



Большое спасибо,наперед )
PM MAIL   Вверх
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
PM MAIL WWW   Вверх
recored
Дата 4.6.2013, 21:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

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



t_gran, Если есть возможность, залейте этот код на Си (можно лишь касаемое метода выбора).
PM MAIL   Вверх
Google
  Дата 20.2.2019, 23:36 (ссылка)  





  Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman

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


 




[ Время генерации скрипта: 0.0624 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.