7. Лінійні списки як структури даних

Перелік алгоритмів, що розглядаються

  • визначення позиції елемента в списку;
  • видалення елемента зі списку;
  • вставка елемента у список.

Короткі теоретичні відомості

Питання для повторення

  1. Особливості роботи з покажчиками.

Постановка задачі

Списком (лінійним списком) є послідовність елементів певного типу. Найчастіше абстрактний тип даних список використовує такі оператори:

  1. Створення порожнього списку.
  2. Визначення позиції заданого елемента у списку.
  3. Видалення елемента із заданої позиції;
  4. Вставка заданого елемента у певну позицію.

При реалізації списків можливість переповнення структури не розглядається.

Опис алгоритмів

Опис структури даних
  • набір комірок, кожна з яких містить елемент списку (дані) і покажчик на наступну комірку списку (наступний);
  • комірка (заголовок), яка містить покажчик на перший елемент списку.
Позиція елемента розуміється як покажчик на комірку, яка містить покажчик на відповідний елемент, зокрема, позиція 1 - це покажчик в комірці заголовка.

1. Створення порожнього списку

Псевдокод
відвести пам'ять для елемента
покажчик елемента = NULL

2. Визначення позиції елемента

Ідея
Проглядати список, поки не зустрінеться не буде досягнуто кінець списку (покажчик NULL) або не зустрінеться шуканий елемент.
Псевдокод
tmp=заголовок
поки (tmp != NULL)
{
якщо (tmp.дані = = параметр)
то повернути tmp
}
повернути tmp

3. Видалення зі списку елемента, що слідує за елементом, на який вказує покажчик p

Ідея
Переспрямувати p.наступний на елемент, наступний за p.наступний
Псевдокод
p.наступний=p.наступний.наступний

4. Вставка елемента в позицію p

Ідея
Переспрямувати p.наступний на новий елемент, а покажчик нового елемента на
Псевдокод
  виділити пам’ять для елементу tmp
  tmp.дані=параметр
  tmp.наступний=p.наступний
  p.наступний=tmp

Завдання для виконання

Постановка задачі

Скласти програму, що забезпечує виконання операцій з лінійним списком. Програма повинна забезпечувати
  • реалізацію основних процедур роботи зі списком;
  • виконання вказаних викладачем дій зі списком.

Технічні умови

  • елементи списка є цілими числами.

Хід роботи

  1. Скласти програму List.cpp, де реалізувати основні функції роботи зі списком.
  2. Виконати в покроковому режимі вказані викладачем дії зі списком, записавши у звіт зміни, що відбуваються у списку.

Запитання для самоконтролю

  1. Які основні оператори використовує абстрактний тип даних список?
  2. Поясніть особливості реалізації списка за допомогою масива.
  3. Поясніть особливості реалізації списка за допомогою покажчиків.
  4. Порівняйте різні реалізації списку.
  5. Поясніть виконання основних операторів списку при його реалізації за допомогою покажчиків.