#Комп’ютерний практикум № 10
#СПИСКИ
Мета роботи - вивчити особливості організації черг та стеків.
##Теоретичні відомості
Найбільш важливим аспектом використання динамічних змінних є обробка спискових структур даних.
Список – це лінійно впорядкована сукупність однотипних елементів, послідовно зв'язаних між собою покажчиками, які входять до складу цих елементів.
Список, кожен елемент якого містить покажчик лише на наступний елемент називається однозв’язним. Кожен елемент такого списку складається з інфор-маційної частини і покажчика на наступний елемент списку. Останній елемент списку містить у адресному полі порожній покажчик (NULL), що інтерпретується як кінець списку. Початок однозв’язного списку зберігається у спеціальному покажчику, який називають вершиною списку.
Оголошення елемента такого списку у С/С++ виглядає наступним чином:
struct тип_структури
{тип_поля інформаційне_поле_1;
…
тип_поля інформаційне _поле_n;
тип_ структури адресне_поле;
}; Наприклад,
struct TNode
{ int Data; // інформаційне поле
TNode * Next; // адресне поле
};Над зв’язними лінійними списками можуть виконуватися такі дії:
- створення списку (вставка першого елемента);
- пошук елемента в списку;
- додавання нового елемента у список (на початок, в середину і в кінець списку);
- видалення елемента із списку (з початку, із середини, з кінця списку).
Для роботи із списком потрібні, як мінімум, покажчик на початок списку (head) та допоміжний покажчик (curr). Наприклад, вставка елемента всередину списка,
TList *curr = new TList; // створення нового елемента списка
cin >> curr->Data; // заповнення його інформаційного поля
curr->Next = prev->Next; // новостворений елемент позиціонується на наступний
prev->Next = curr; // попередній елемент позиціонується на новостворений Різновидами спискових структур є також стеки та черги.
Стек – це однозв'язний список, елементи якого обробляються за принципом LIFO («останнім прийшов - першим пішов»). Останній елемент у стеці є його вершиною. Всі операції в стеці можна проводити тільки з вершиною стеку.
Операції із стеками:
- створення стеку (внесення першого елемента);
- перевірка стеку на наявність елементів;
- додавання елемента в стек;
- видалення елемента із стеку.
Для роботи із стеком потрібно мати покажчик на вершину стеку (head) та допоміжний покажчик (curr). Наприклад, вставка елемента у стек,
TStack *curr = new TStack;
cin>> curr->Data;
curr-> Next = head; // наступним стає елемент, який був у вершині стека
head = curr; //як вершина стека встановлюється новостворений елемент Черга – це однозв'язний список, у якому елементи обробляються за принци-пом FIFO («першим прийшов - першим пішов»). У черги, окрім вершини (її першого елемента), є хвіст (її останній елемент). Операції із чергою:
- створення черги (внесення першого елемента);
- перевірка черги на наявність елементів;
- додавання елемента в чергу;
- видалення елемента із черги.
Елементи додаються лише в кінець черги, зчитуються та видаляються - лише з початку (вершини) черги. Представлення черги аналогічне стеку, відмінність лише у тому, що черга за-дається двома вказівниками: перший містить адресу початку черги (head), другий – адресу її кінця (last). Наприклад, видалення елемента із черги,
TQueue *curr = head; // запам'ятовування покажчика на голову черги
head = head ->next; //встановлення як голови елемента, який був
//наступним після неї
delete curr; //видалення елемента, який був головою черги Обробка однозв’язного списку не завжди зручна, оскільки відсутня можливість просування в протилежну сторону. Таку можливість надає двозв'язний список, кожен елемент якого містить два покажчики: на наступний (next) і по-передній (prev) елементи списку.
Для зручності обробки такого списку додають ще один особливий елемент - покажчик кінця списку (last). Тому двозв'язний список можна обробляти як зліва направо, так і справа наліво. Наприклад, видалення елемента двозв'язного списку,
curr->рrev->next = curr->next; // поле next елемента, що передує видаляємому,
// починає вказувати на наступний елемент
curr->next->prev = curr->prev; // поле prev наступного елемента починає
// вказувати елемент, що передує видаляємому
delete curr; //видалення поточного елементаРізновидом розглянутих видів лінійних списків є кільцевий список, який може бути організований на основі як однозв’язного, так і двозв'язного списків. При цьому в однозв’язному списку покажчик останнього елементу повинен вказувати на перший елемент; у двозв'язному списку в першому і останньому елементах відповідні покажчики перевизначаються на останній і перший елементи списку.
- Заданий текст, що має декілька рядків. Використовуючи стек, елементами якого є літери, надрукувати текст, в якому літери кожного рядка містяться у зворотному порядку.
- Побудувати список, елементами якого є дійсні числа. Знайти їх середнє арифметичне і розмістити отримане значення останнім елементом списку. Надрукувати початковий і змінений списки.
- Заданий рядок слів, які відокремлюються одне від одного пробілами. Побудувати список, елементами якого є відповідні слова. Вилучити із списку всі слова, що починаються та закінчуються на задану користувачем літеру. Надрукувати початковий і змінений списки.
- Задане натуральне число n та послідовність дійсних чисел х1, ..., хn. Використовуючи двозв'язний список, елементами якого є задані дійсні числа, визначити (x1 -xn )+ (x2 -xn-1) + ... + (xn -x1).
- Заданий текст, що містить декілька рядків слів, розділених пробілами. Використовуючи стек, елементами якого є слова, надрукувати текст, в якому слова кожного рядка містяться у зворотному порядку.
- Заданий рядок слів, які відокремлюються одне від одного комами. Побудувати список, елементами якого є відповідні слова. Вилучити із списку всі слова заданої користувачем довжини. Надрукувати початковий і змінений списки.
- Побудувати список, елементами якого є цілі числа. Знайти суму останнього і передостаннього його елементів і замістити відповідним значенням ці елементи списку. Надрукувати початковий і змінений списки.
- Заданий текст, що має декілька рядків. Використовуючи чергу або стек, елементами яких є літери, надрукувати тексти, що знаходяться між кожною парою дужок заданого користувачем виду.
- Заданий рядок слів, які відокремлюються одне від одного будь-якою кількістю пробілів. Побудувати список відповідних слів. Поміняти місцями найдовше та найкоротше слово цього списку. Надрукувати початковий і змінений списки.
-
Одне з можливих представлень тексту — це розділити його на рядки і створити список рядків, додавши ознаку кінця тексту. Використовуючи дане представлення тексту, визначити, чи входить задана літера у текст, і, якщо входить, то вивести «координати» першого входження цієї літери у текст (номер рядка і номер позиції в цьому рядку). -
Заданий рядок слів, які відокремлюються одне від одного символами “;”. Побудувати список слів, що містяться у цьому рядку. Вилучити із списку всі однакові слова. Надрукувати початковий і змінений списки. -
Побудувати список символів. Визначити найбільше значення списку і помістити його на початок списку. Надрукувати початковий і змінений списки. -
Задане натуральне число n та послідовність дійсних чисел х1, ..., хn. Використовуючи двозв'язний список, елементами якого є задані дійсні числа, ви-значити x1\*xn + x2\*xn-1 + ... + xn*x1. -
Заданий список символів. Перенести в кінець цього списку його перший елемент. Надрукувати початковий та змінений списки. -
Задана послідовність натуральних чисел. Використовуючи стек, надру-кувати у зворотному порядку усі числа, які містяться між найбільшим та найменшим числами послідовності. -
Текстовий файл містить вираз, записаний у звичайній (інфіксній) формі. Використавши стек, перекласти заданий вираз в постфіксну форму i записати в новий текстовий файл. Інфіксна форма виразу: а-b, a*b; постфіксна форма: ab-, ab+. -
Задана послідовність цілих чисел. Використовуючи стек, надрукувати у зворотному порядку усі її числа, що не кратні 5. -
Створити кільцевий список, елементами якого є числа. Послідовно вилучати кожне третє число. Підрахувати кількість вилучень. Вивести початковий список та вилучені елементи у порядку їх вилучення. -
Задана послідовність дійсних чисел, що містить від'ємні елементи. Побудувати список, елементами якого є відповідні числа. Вилучити всі від'ємні елементи цього списку. Надрукувати початковий та новий списки. -
Задана послідовність цілих чисел, що містить від'ємні елементи. Використовуючи стек, елементами якого є цілі числа, надрукувати у зворотному порядку всі додатні елементи послідовності. -
Задане натуральне число n та послідовність дійсних чисел х1, ..., хn. Ви-користовуючи двозв'язний список, елементами якого є задані дійсні числа, побудувати список, що містить елементи x1\*xn, x2\*xn, ..., xn-1*xn. -
Створити список цілих чисел. Вилучити із списку усі парні числа, підрахувавши їх кількість. Надрукувати початковий, змінений список та визначену величину. -
Задана послідовність цілих чисел. Використовуючи чергу, елементами якої є цілі числа, вивести на друк спочатку парні елементи послідовності, а потім – непарні. -
Побудувати кільцевий список, елементами якого є цілі числа. Послідовно вилучати кожне його парне число, заносячи його до стеку. Вивести початковий список та вміст стеку. -
Створити двозв'язний список, елементами якого є слова тексту. Вивести слова, які стоять на парних місцях при проході по списку в одному напрямку, та слова, які стоять на непарних позиціях при проході по списку в зворотньому напрямку. -
Задана послідовність цілих чисел. Побудувати список, у якому числа впорядковані у порядку зростання. Надрукувати послідовність і впорядкований список. -
Заданий текст, що містить декілька рядків слів, розділених пробілами. Використовуючи чергу, елементами якої є слова, та стек, елементами якого є літери, надрукувати текст, в якому літери слів кожного рядка містяться у зворотному порядку. -
Одне з можливих представлень тексту — це розділити його на рядки і створити список рядків, додавши ознаку кінця тексту. Використовуючи дане представлення тексту, визначити номер рядка з максимальною кількістю входжень заданої літери. -
Задане натуральне число n та послідовність дійсних чисел х1, ..., хn. Використовуючи двозв'язний список, елементами якого є задані дійсні числа, побудувати список, що містить елементи x1-xn, x2-xn, ..., xn-1-xn. -
Заданий список, елементами якого символи. Вставити в кінець списку новий елемент, що введений з клавіатури, та вилучити із списку перший його елемент. Надрукувати початковий та змінений списки.
- Чим відрізняються статичні і динамічні величини?
- Яка пам'ять називається динамічно розподіляється?
- Як виділити пам'ять під динамічну змінну?
- Як звільнити пам'ять від динамічної змінної?
- Які ситуації призводять до виникнення в динамічно розподіляємій пам'яті "сміття"?
- Що розуміють під зв'язаним списком?
- Як класифікують зв'язані списки?
- Які основні дії над списками?