| Код |
#include "stdafx.h"
#include <windows.h>
#include <iostream>
// Нумерация списка с единицы
// Класс, реализующий работу с двусвязным списком на базе любого типа
template <typename T>
class CSpisok
{
private:
struct SItem
{
SItem * next; // указатель на следующий элемент
T value; // значение
SItem * pred; // указатель на предыдущий элемент
};
SItem * First; // указатель на первый элемент списка
SItem * Last; // указатель на последний элемент списка
public:
CSpisok::~CSpisok()
{
SItem * p = First;
SItem * temp = p;
while(p != 0)
{
temp = p->next;
delete p;
p = temp;
}
}
CSpisok::CSpisok()
{
First = 0;
Last = 0;
}
T& CSpisok::GetItem(UINT32 num) // возвращает элемент с номером num
{
SItem * p = First;
UINT chislo = 1;
while (p != 0)
{
if (chislo == num)
{
return p->value;
}
p = p->next;
chislo++;
}
std::cout << "Error." << std::endl;
}
SItem& CSpisok::GetStruct(UINT32 num) // возвращает структуру с номером num
{
SItem * p = First;
UINT chislo = 1;
while (p != 0)
{
if (chislo == num)
{
return *p;
}
p = p->next;
chislo++;
}
std::cout << "Error." << std::endl;
}
UINT32 CSpisok::GetSize() // Возвращает размер списка
{
UINT32 chislo = 0;
SItem * p = First; // счетчик
while (p != 0)
{
p = p->next;
chislo++;
}
return chislo;
}
VOID CSpisok::OutputValues() // вывод значений
{
SItem * p = First; // счетчик
while (p != 0)
{
std::cout << p->value << " ";
p = p->next;
}
std::cout << std::endl;
}
VOID CSpisok::PushBack(T num)// добавление в конец
{
SItem * s = new SItem;
if (Last != 0)
{
Last->next = s;
}
s->value = num;
s->next = 0;
s->pred = Last;
Last = s;
if (First == 0)
First = s;
}
VOID CSpisok::PushFront(T num)// добавление в начало
{
SItem * s = new SItem;
if (First != 0)
{
First->pred = s;
}
s->value = num;
s->next = First;
s->pred = 0;
First = s;
if (Last == 0)
Last = s;
}
VOID CSpisok::DeleteFirst() // удалить первый
{
SItem * temp = First;
First = First->next;
First->pred = 0;
delete temp;
}
VOID CSpisok::DeleteLast() // удалить последний
{
Last->pred->next = 0;
delete Last;
}
VOID CSpisok::DeleteNumber(UINT32 num) // удаление элемента с
// номером в списке = num
{
SItem * p = &GetStruct(num);
if (p == First)
{
p->next->pred = 0;
First = First->next;
}
else if (p == Last)
{
p->pred->next = 0;
Last = Last->pred;
}
else
{
p->pred->next = p->next;
p->next->pred = p->pred;
Last = Last->pred;
}
}
VOID CSpisok::Paste(T value, UINT32 num) // вставка значения со
// значением = value после номера в списке = num
{
SItem * s = new SItem;
UINT32 chislo = 1;
SItem * p = First; // счетчик
while (p != 0)
{
if (chislo == num)
{
if (p == First)
{
}
else if (p == Last)
{
}
else
s->value = value;
s->pred = p;
s->next = p->next;
p->next->pred = s;
p->next = s;
break;
}
p = p->next;
chislo++;
}
}
VOID CSpisok::Change(UINT32 num1, UINT32 num2) // поменять местами элементы с номерами num1 и num2
{
if (num2 > num1)
{
T temp = num1;
num1 = num2;
num2 = temp;
}// num1 = max
SItem * n = &GetStruct(num1);
SItem * m = &GetStruct(num2);
if (m == n)
{
return; // ничего не делать, если переставляемые номера совпадают
}
T temp = m->value;
m->value = n->value;
n->value = temp;
}
VOID CSpisok::Sort(BOOL value) //сортировка пузырьком.TRUE - по возрастанию,
// FALSE- по убыванию
{
if (value == TRUE)
{
SItem * i = First; // счетчик
SItem * j = First; // счетчик
int a, b;
for (a = 1, i = First; i->next != 0; i = i->next, ++a)
{
for (b = 1, j = First; j->next != 0; j = j->next, ++b)
{
if (j->value > j->next->value)
{
Change(b, b + 1);
}
}
}
}
else
{
SItem * i = First; // счетчик
SItem * j = First; // счетчик
int a, b;
for (a = 1, i = First; i->next != 0; i = i->next, ++a)
{
for (b = 1, j = First; j->next != 0; j = j->next, ++b)
{
if (j->value < j->next->value)
{
Change(b, b + 1);
}
}
}
}
}
};
int main()
{
CSpisok<std::string> qwe;
qwe.PushBack("qwe");
qwe.PushBack("rty");
qwe.PushBack("asd");
qwe.PushBack("ghjz");
qwe.PushBack("vbn");
for(UINT32 i = 1; i <= qwe.GetSize(); ++i)
{
std::cout << qwe.GetItem(i) << " ";
}
std::cout << std::endl;
qwe.Sort(FALSE);
for(UINT32 i = 1; i <= qwe.GetSize(); ++i)
{
std::cout << qwe.GetItem(i) << " ";
}
return 0;
}
|
| Цитата |
создать класс слов "двусвязный список"
|
Как я понял нужно создать класс "двусвязный список", элементами которго нужно сделать слова.В реализации класса много функций в том числе сортировка(правда пузырьком  )
За счет шаблона достигается универсальность.
PS: Нашел небольшой косячок.
В функциях GetStruct и GetItem выдает warning-и типа не все проверено.В случае ошибки что возвращать, если мы не знаем изначально тип? |