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

Задание 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. Усложненные списковые структуры