Поняття про список.

Розглянемо структуру даних - однонаправлений (однозв'язаний) список. Список - це скінче­ний набір даних одного типу, між якими налагоджено зв'язок. Елемент однонаправленого списку складається з двох частин: самого даного (часто складеного) та вказівника на наступний елемент списку. Для опису списку використовують тип даних структура і вказівник, а саме:

struct <назва типу списку?

{

<тип поля 1> <назва поля 1>;

<тип поля п> <назва поля п>;

<тип вказівника> *<назва типу списку>;

};

<назва типу списку> *<назва вказівника 1>

*<назва вказівника п>;

Приклад. Створимо структуру про річку (rika), яка міс­тить поля: назва, довжина річки у кілометрах та площа ба­сейну у квадратних кілометрах, і поставимо їй у відповідність елементи списку:

struct rika // Створюємо тип rika

(

char nazva[12];

int dov;

long int pi;

rika *dali; // Створюємо поле вказівник на тип rika

}; rika 'element, 'pershij, *poperednij, *novyj;

Тут element - вказівник (тип структура rika) на поточний еле­мент списку, element -> dov - динамічна змінна цілого типу (int),

яка містить значення довжини річки, a element -> dali - вказівник на наступний елемент списку. Звідси випливає, що element-> dali -> dov - це довжина наступної річки, a element -> dali -> dali -вказівник на ще наступну річку і т.д.

Приклад.Створити список, який містить ін­формацію про річки. Вивести цей список на екран. Додати на початок списку новий запис. Вивести список зі змінами.

Щоб увести дані про всі річки, можна використати тип даних - масив структур. Вважатимемо, що кількість річок, про які необхідно ввести інформацію, невідома, тому звичай­ний масив використати не можна. Навіть якщо кількість да­них відома, то працювати з таким масивом не раціонально. Адже щоб вставити в середину масиву новий елемент, потріб­но зміщувати "хвіст масиву" праворуч. Щоб уникнути цього, застосовують список.

Програма Список рік розв'язує поставлену задачу і демонст­рує основні прийоми опрацювання списку. Елементи списку опрацьовують один за одним за допомогою команд циклу. Спочатку створюють список і вводять із клавіатури в нього дані. Щоб завершити введення даних, домовимося ввести нулі для значень назви, довжини та площі басейну річки. Після завершення введення буде створено зайвий (останній) елемент списку (з нулями). Його слід пізніше ліквідувати, заздалегідь оголосивши ще один вказівник (на попередній елемент спис­ку) і прийнявши poperednij -> dali = NULL. Суттєва перевага спис­ків у тому, що вилучити зафіксований (тобто вибраний відпо­відно до деякої умови) елемент можна за допомогою одної ко­манди переадресації вигляду poperednij -> dali = zafix -> dali.

Виводимо список на екран. Створюємо новий елемент спис­ку і вводимо в його поля дані. Новий елемент зробимо першим у списку. Суттєва перевага списку над масивом і в цьому разі: щоб вставити новий елемент після зафіксованого, потрібно лише дві команди переадресації і жодної "брудної роботи з хвостом". Вказівник нового елемента переадресовуємо туди, куди вказував вказівник зафіксовано елемента, а вказівник зафіксованого елемента "втикаємо" в новий елемент:

novyj->dali = zafix->dali; zafix->dali = novyj;

// Список рік

#include <iostream.h>

#include <conio.h>

struct rika // Створюємо тип rika

{

char nazva[12];

int dov;

longintpl;

rika *dali; // Створюємо поле вказівник типу rika

};

rika *element, *pershij, *poperednij, *novyj;

void StvorytySpysok(void); // Функція створення списку

void VyvestyNaEkran(void); // Функція виведення списку на екран

void StvorytyNjvyjElement(void); // Функція створення нового елемента void main() {

cout<<"Створення списку\п"

cout << "Для закінчення введіть усі нулі\п";

StvorytySpysok();

VyvestyNaEkran();

StvorytyNjvyjElement();

// Додаємо до початку списку новий елемент

element = pershij;

novyj -> dali = element;

pershij = novyj;

cout « "Новий список \п";

VyvestyNaEkran();

}

//--------------------------------------------------------------------------------------

void StvorytySpysok(void)

{

element = new (rika);

pershij = element;

do

{

poperednij = element;

cout<<"Уведіть назву, довжину та площу річки\п"; сіп » element -> nazva;

сіn>>element -> dov;

сіn>>element-> pi;

element-> dali = new (rika); :

element = element-> dali; .

}

while (poperednij-> dov != 0 II poperednij-> pi != 0); poperednij-> dali = NULL;

}

//------------------------------------------------------------------------------------------

void VyvestyNaEkran(void)

{

cout<<"Створено такий список:\n";

element = pershij;

while (element != NULL)

{

сout<<element -> nazva<<"\t"<<

element -> dov<<"\t" <<element -> pi<<"\n";

element = element -> dali;

//----------------------------------------------------------------------------------------

void StvorytyNjvyjElement(vold)

{

novyj = new (rika);

cout<<"Уведіть назву, довжину та площу нової річки\п";

сіn>>novyj -> nazva >>novyj -> dov>>novyj -> pi;

}

Cтек.

Стек - це структура даних, у якій еле­мент, записаний останнім, зчитують (він доступний для опра­цювання) першим. Принцип "останній прийшов - перший пі­шов" використовується в багатьох технічних пристроях і в побуті: ріжок від автомата; посадка пасажирів у вагон, який має лише одні двері тощо. Стек використовують у програму­ванні, зокрема, для реалізації рекурсії. Рекурсія виконується так: спочатку всі виклики нагромаджуються (аналогія така: пружина стискається), а потім виконуються вкладені функції (пружина розпрямляється).

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

Приклад. Ввести послідовність символів, де крапка (".") є ознакою закінчення введення. Вивести введе­ні символи на екран у зворотному порядку.

Розв'яжемо цю задачу із застосуванням стека (stack), який містить такі поля: символ (ch), вказівник на наступний еле­мент стека (dali).

#include <iostream.h> // Програма Стек

#include <conio.h>

struct stack // Оголошення типу stack

(

char ch;

stack *dali;

};

stack *st, 'element;

void StvorytyStek(stack *st);

void VyluchenniaZiSteku(stack *st);

void main()

{

st = NULL;

StvorytyStek(st);

VyluchenniaZiSteku(st);

}

//--------------------------------------------------------------------------------------------

void StvorytyStek(stack *st)

{

char a;

do // Bводимо дані у стек

{ // Зчитуємо символ, введений з клавіатури

а = getch();

element = new (stack); // Виділяємо місце для нового елемента

element -> dali = st; // Перенаправляємо вказівники

st = element;

element -> ch = a;

}

while (a != '.'); // Поки не введена крапка

//--------------------------------------------------------------------------------------------

void VyluchenniaZiSteku(stack *st)

{ // Вилучення елементів зі стека та

do // виведення їх на екран

{

st = element -> dali;

element = st;

cout<< st -> ch;

}

while (st-> dali != NULL);

}