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; просмотров: 683;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.009 сек.