Class Node. Node*pbeg,*pend;//Вказівки на початок та кінець списку
{
...
};
Node*pbeg,*pend;//Вказівки на початок та кінець списку
public:
List() {pbeg = 0;pend=0;} //Конструктор
~List(); // Деструктор
void add(int d); // Додавання вузла у кінець списку
Node * find(int i); // Пошук вузла по ключу
bool remove (int key); // Видалення вузла
// Вставка вузла d після вузла с ключем key
Node* insert(int key, int d);
void print();// Друк списку у прямому напрямі
void print_back();// Друк списку в оберненому напрямі
};
Розглянемо реалізацію методів класу. Метод add виділяє пам'ять під новий об'єкт типу Node і приєднує його до списку, оновлюючи вказівки на його початок та кінець:
void List<Data>::add(Data d)
{
Node* pv = new Node(d);//Виділення пам’яті під новий вузол
if(pbeg == 0)pbeg = pend = pv; // Перший вузол списку
else
{
// Зв’язування нового вузла з попереднім
pv->prev = pend;
pend->next = pv;
pend = pv;// Оновлення вказівки на кінець списку
}
}
Метод find() виконує пошук вузла із заданим ключем і повертає вказівку на нього у разі успішного пошуку і 0 у разі відсутності такого вузла в списку:
Node* List::find(int d)
{
Node *pv = pbeg;
while(pv)
{
if(pv->d == d)break;
pv = pv->next;
}
return pv;
}
Метод insert() вставляє в список вузол після вузла з ключем key і повертає вказівку на вставлений вузол. Якщо такого вузла в списку немає, вставка не виконується і повертається значення 0:
Node * List::insert(int key, int d)
{
if(Node *pkey = find(key))
{ // Пошук вузла з ключем key
//Виділення пам’яті під новий вузол та його ініціалізація:
Node *pv = new Node(d);
// Встановлення зв’язку нового вузла з наступним:
pv->next = pkey->next;
// Встановлення зв’язку нового вузла з попереднім:
pv->prev = ркеу;
// Встановлення зв’язку попереднього вузла з новим:
pkey->next = pv;
// Встановлення зв’язку наступного вузла з новим:
if (ркеу != pend) (pv->next)->prev = pv;
// Оновлення вказівки на кінець списку,
// якщо вузол вставляється в кінець:
else pend = pv;
return pv;
}
return 0;
}
Метод remove видаляє вузол із заданим ключем із списку і повертає значення true у разі успішного видалення і false, якщо вузол з таким ключем в списку не знайдений:
bool List::remove(int key)
{
if(Node *pkey = find(key))
{
if (pkey == pbeg)
{ // Видалення з початку списку
pbeg = pbeg->next;
pbeg->prev = 0;
}
else if (pkey == pend)
{ // Видалення з кінця списку
pend = pend->prev;
pend->next = 0;
}
else
{ // Видалення з середини списку
(pkey->prev)->next = pkey->next;
(pkey->next)->prev = pkey->prev;
}
delete pkey;
return true;
}
return false;
}
Методи друку списку в прямому і зворотному напрямі поелементно переглядають список, переходячи по відповідних посиланнях:
void List ::print()
{
Node* pv = pbeg;
cout << char(10) << " list ";
while(pv)
{
cout << pv->d << " ";
pv = pv->next;
}
cout << char(10);
}
void List::print_back()
{
Node* pv = pend;
cout << char(10) << " list back ";
while(pv)
{
cout << pv->d << " ";
pv = pv->prev;
}
cout << char(10);
}
Деструктор списку звільняє пам'ять з-під всіх його елементів:
List::~List()
{
if(pbeg!=0)
{
Node* pv = pbeg;
while(pv)
{
pv = pv->next;
delete pbeg;
pbeg = pv;
}
}
}
Приклад програми, яка використовує клас List:
Дата добавления: 2014-12-26; просмотров: 689;