Void main(). for (int i = 2; i<6; i++) add(&pend, i);

{

Node *pbeg = first(l);

Node *pend = pbeg;

for (int i = 2; i<6; i++) add(&pend, i);

while (pbeg)

cout << del(&pbeg) << " ";

}

// Початкове формування черги

Node* first(int d)

{

Node *pv = new Node;

pv->d = d;

pv->p = 0;

return pv;

}

// Додавання в кінець

void add(Node **pend, int d)

{

Node *pv = new Node;

pv->d = d;

pv->p = 0;

(*pend)->p = pv;

*pend = pv;

}

// Вибірка

int del(Node **pbeg)

{

int temp = (*pbeg)->d;

Node *pv = *pbeg;

*pbeg = (*pbeg)->p;

delete pv;

return temp;

}

Результат роботи програми:

12 3 4 5

8.4. Лінійний список

Найпростіший спосіб зв'язати безліч елементів – зробити так, щоб кожен елемент містив посилання на наступний. Такий список називається однонаправленим (однозв’язним). Якщо додати в кожен елемент друге посилання – на попередній елемент, вийде двонаправлений список (двозв’язний), якщо останній елемент зв'язати вказівкою з першим, вийде кільцевий список.

Кожен елемент списку містить ключ, що ідентифікує цей елемент. Ключ зазвичай буває або цілим числом, або рядком і є частиною поля даних. У якості ключа в процесі роботи із списком можуть виступати різні частини поля даних. Наприклад, якщо створюється лінійний список із записів, які містять прізвище, рік народження, стаж роботи та стать, будь-яка частина запису може виступати як ключ: при впорядковувань списку за алфавітом ключем буде прізвище, а при пошуку, наприклад, ветеранів праці ключем буде стаж. Ключі різних елементів списку можуть збігатися.

Над списками можна виконувати наступні операції:

– початкове формування списку (створення першого елементу);

– додавання елементу в кінець списку;

– читання елементу із заданим ключем;

– вставка елементу в задане місце списку (до або після елементу із заданим ключем);

– видалення елементу із заданим ключем;

– впорядковування списку по ключу.

Розглянемо двонаправлений лінійний список. Для формування списку і роботи з ним потрібно мати принаймні одну вказівку – на початок списку. Зручно завести ще одну вказівку – на кінець списку. Для простоти допустимо, що список складається з цілих чисел, тобто опис елементу списку виглядає таким чином:

struct Node

{

int d;

Node *next;

Node *prev;

};

Нижче приведена програма, яка формує список з 5 чисел, додає число в список, видаляє число із списку і виводить список на екран. Вказівка на початок списку позначена pbeg, на кінець списку – pend, допоміжні вказівки – pv та ркеу.

#include <iostream>

using namespace std;