| Цитата |
Есть задача но не знаю как написать ее так как не знаю динамического программирования )
|
Милый друг, динамическое программирование это далеко не то, что вы под этими словами подразумеваете.
| Код |
#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;
}
|
http://codepad.org/IV7Fvuxc
Бинарник с исходником ниже
P.S.: В комментариях увидите, что сортировку вставками для односвязного списка можно сделать только с помощью костылей. Я не стал извращаться, дабы не быть обсмеянным коллегами. |