Динамическая реализация линейных списков

Динамическая реализация линейного списка, также как стека и очереди, основана на динамическом выделении и освобождении памяти для элементов списка. Логическая последовательность элементов списка создается ссылочными переменными с адресами последующих элементов (последний элемент имеет пустую ссылку nil).

Опять же для удобства реализации будем считать, что список ВСЕГДА содержит хотя бы один элемент-заголовок с адресом первого реального элемента списка. Это позволяет унифицировать процедуры добавления и удаления крайних элементов и устранить некоторые проверки. Адрес элемента-заголовка задается переменной-указателем pHead. Эта переменная устанавливается при первоначальном создании списка и в дальнейшем НЕ изменяется. Для реализации основных действий используются вспомогательные ссылочные переменные.

Необходимые объявления:

type pDinItem = ^ TDinItem; {ссылочный тип для адресации элементов списка}

TDinItem = record

{базовый тип, определяющий структуру элемента списка}

inf : ;

next : pDinItem; {адрес следующего элемента}

end;

var pHead : pDinItem;

Создание пустого списка включает:

  • выделение памяти под заголовок: new(pHead);
  • установку пустой ссылочной части заголовка: pHead^.next := nil;

Проход по списку от первого элемента к последнему практически не отличается от прохода по очереди.

Поиск заданного элемента включает:

  • установку вспомогательного указателя в адрес первого элемента списка
  • организацию цикла прохода по списку с завершением либо по совпадению информационной части элемента с заданным значением, либо по достижению конца списка
  • после завершения цикла проверить значение вспомогательного указателя и сделать вывод об успешности поиска

pCurrent := pHead^.next;

while (pCurrent nil) and (pCurrent^.inf ‘заданное значение’)

do pCurrent := pCurrent^.next;

if pCurrent = nil then ‘Элемента нет’ else ‘элемент найден’;

Удаление заданного элемента включает:

  • поиск удаляемого элемента с определением адреса элемента-предшественника (для этого вводится еще одна вспомогательная ссылочная переменная pPrev, инициированная адресом заголовка и изменяющая свое значение внутри цикла)
  • если удаляемый элемент найден, то изменяется ссылочная часть его предшественника:

pPrev^.next := pCurrent^.next

  • удаляемый элемент обрабатывается необходимым образом, т.е. либо освобождается занимаемая им память, либо он включается во вспомогательный список

Добавление нового элемента ПОСЛЕ заданного включает:

  • поиск заданного элемента с помощью вспомогательного указателя pCurrent
  • выделение памяти для нового элемента с помощью еще одного указателя pTemp
  • формирование полей нового элемента, в частности – настройка ссылочной части

pTemp^.next := pCurrent^.next;

  • изменение ссылочной части текущего элемента на адрес нового элемента

pCurrent^.next := pTemp;

Добавление нового элемента ПЕРЕД заданным включает:

  • поиск заданного элемента с одновременным определением элемента-предшественника (используются указатели pCurrent и pPrev)
  • выделение памяти для нового элемента с помощью еще одного указателя pTemp
  • формирование полей нового элемента, в частности – настройка ссылочной части: pTemp^.next := pCurrent;
  • изменение ссылочной части элемента-предшественника на адрес нового элемента: pPrev^.next := pTemp;

Если при использовании списка часто приходится добавлять или удалять элементы в конце списка, то для уменьшения расходов на просмотр всего списка можно ввести второй основной указатель — на последний элемент списка. Это потребует изменения процедур удаления и добавления для отслеживания этого указателя.

Довольно часто используется упорядоченная разновидность линейного списка, в котором элементы выстраиваются в соответствии с заданным порядком, например – целые числа по возрастанию, текстовые строки по алфавиту. Для таких списков изменяется процедура добавления – новый элемент должен вставляться в соответствующее место для сохранения порядка элементов. Например, если порядок элементов определяется целыми числами по возрастанию, то при поиске подходящего места надо найти первый элемент, больший заданного и выполнить вставку ПЕРЕД этим элементом.

Практические задания

Задание 1.Реализовать программу для простейшего моделирования линейного списка с помощью массива. Должны быть реализованы все основные действия:

  • проход по списку с выводом на экран информационных частей элементов
  • поиск элемента с заданной информационной частью
  • добавление нового элемента после заданного и перед заданным со сдвигом (при необходимости) хвостовой части вправо для освобождения ячейки массива
  • удаление заданного элемента со сдвигом (при необходимости) хвостовой части влево для заполнения образовавшейся пустой ячейки.

Выполнение всех операций предусматривает необходимые проверки (наличие в списке хотя бы одного элемента, наличие свободных ячеек, наличие искомого элемента). Все основные операции оформляются как подпрограммы с параметрами. Главная программа создает пустой список, устанавливая счетчик числа элементов в списке в ноль, и организует диалог для реализации всех операций.

Проверить работу программы для небольшого массива (до 10 элементов).

Задание 2. Изменить предыдущую программу для создания упорядоченного списка. Для этого надо изменить логику работы подпрограммы добавления элемента. Подпрограмма должна находить соответствующее место для нового элемента, т.е. поиск должен останавливаться при обнаружении первого элемента, большего заданного. Предусмотреть обработку особых случаев:

  • если в списке нет ни одного элемента, вставка производится в первую ячейку массива
  • если все элементы меньше заданного, вставка производится в конец списка

Проверить работу программы для двух случаев: список целых чисел по возрастанию и список коротких текстовых строк по алфавиту.

Задание 3.Реализовать линейный список на базе массива с указателями-индексами. Список должен иметь заголовок (нулевая ячейка массива) с номером первого элемента списка. Набор операций — стандартный. Для отслеживания свободных ячеек использовать простейшую схему – отмечать свободные ячейки специальным значением индекса ( -1). Главная программа при создании пустого списка должна отметить все ячейки массива (кроме нулевой) как свободные.

Задание 4.Реализовать линейный динамический список со стандартным набором операций. Пустой список содержит только элемент-заголовок, который создается главной программой в начале работы и содержит значение nil в ссылочной части. У непустого списка в ссылочной части хранится адрес первого реального элемента. Адрес заголовка сохраняется в глобальной ссылочной переменной. Все действия оформляются как подпрограммы.

Подпрограмма для добавления элемента после заданного должна работать и для пустого списка – в этом случае новый (он же первый реальный!) элемент должен добавляться сразу после заголовка. Для этого проверить пустоту списка, после чего для пустого списка установить глобальный указатель текущего элемента в адрес заголовка, для непустого списка вызвать процедуру поиска. Само добавление выполняется обычным образом.

Задание 5.Изменить предыдущую программу так, чтобы удаляемый из основного списка элемент добавлялся во вспомогательный список с возможностью просмотра вспомогательного списка. Работа со вспомогательным списком может выполняться по стековому принципу.

В предыдущую программу надо внести следующие изменения:

  • добавить глобальную ссылочную переменную для хранения адреса вершины стека
  • в начале главной программы создать пустой вспомогательный список (стек)
  • в основное меню добавить возможность просмотра вспомогательного списка (стека)
  • изменить процедуру удаления элемента из основного списка, заменив операцию освобождения памяти операциями добавления удаленного элемента во вспомогательный список (стек)
  • добавить обычную процедуру вывода вспомогательного списка (стека)

Задание 6.Изменить предыдущую программу для поддержки упорядоченных списков (см. задание 2).

3.7. Контрольные вопросы по теме

1. В чем состоит отличие списковых структур от стека и очереди?

2. Что включает в себя стандартный набор операций со списком?

3. В чем состоит простейший способ реализации списка с помощью массива?

4. Как выполняется вставка элемента при простейшей реализации списка на базе массива?

5. Как выполняется удаление элемента при простейшей реализации списка на базе массива?

6. В чем состоят преимущества и недостатки простейшего способа реализации списков с помощью массивов?

7. За счет чего можно повысить эффективность простейшей реализации списка с помощью массива?

8. В чем смысл реализации статического списка с указателями-индексами?

9. Какую структуру имеют элементы массива при статической реализации списка?

10. Какие описания необходимы для статической реализации списка?

11. Как выполняется проход по статическому списку?

12. Как выполняется поиск элемента в статическом списке?

13. Какие особые ситуации возможны при статической реализации списка?

14. Что такое пустой статический список?

15. Как выполняется добавление элемента после заданного в статическом списке?

16. Как выполняется добавление элемента перед заданным в статическом списке?

17. Как выполняется удаление элемента в статическом списке?

18. Как в простейшем случае можно отслеживать свободные ячейки массива при реализации статического списка?

19. В чем недостатки простейшего способа отслеживания свободных ячеек при реализации статического списка?

20. Как используется вспомогательный список свободных ячеек при статической реализации списка?

21. Как инициализируется вспомогательный список свободных ячеек при создании пустого статического списка?

22. Что является основой реализации динамических списков?

23. Какую структуру имеют элементы динамического списка?

24. Какие описания необходимы для реализации динамического списка?

25. Какие переменные используются для реализации операций с динамическими списками?

26. Что включает в себя создание пустого динамического списка?

27. Как выполняется проход по динамическому списку?

28. Как выполняется поиск элемента в динамическом списке?

29. Как выполняется удаление элемента в динамическом списке?

30. Как выполняется добавление элемента после заданного в динамическом списке?

31. Как выполняется добавление элемента перед заданным в динамическом списке?

32. Какие особенности возникают при обработке упорядоченных списков?

Тема 4. Усложненные списковые структуры

Реализация односвязного списка c++ Часть 1 | Урок #133


Похожие статьи.

Понравилась статья? Поделиться с друзьями: