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;

 








Дата добавления: 2014-12-26; просмотров: 721;


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

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

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

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