Міністерство освіти і науки України
Національний технічний університет України "КПІ"
Кафедра медичної кібернетики та телемедицини
Лабораторна робота №2
Тема: Динамічні структури даних
Варіант №16 (задача 17.16).
Виконав:
студент ІМ-81
Плахтій Артур Миколайович
Перевірив:
старший викладач
Зінченко Ніна Павлівна
Київ 2009
Содержание
1. Теоретическая часть
Некоторые линейные списки
Построение сложных структур в динамической памяти
Бинарные деревья
2. Условия задачи
Текст программы
Екран результату
Контрольні розрахунки
Висновок
Список літературних джерел
1. Теоретическая часть
Некоторые линейные списки
Стек создается как линейный список. Пусть Top - указатель на начало стека. Стек удобно строить в обратном порядке. Следующий фрагмент программы демострирует основные операции работы со стеком:
Type ukaz=stak, stak=record inf: integer, next: ukaz, end, Var Top,Tek: ukaz; value: integer Procedure DobavS;
Begin new (Tek) readln (Tek. inf) Tek. next: =Top Top: =Teк End Procedure UdalS Begin Top: =Top. next if Top=0 then writeln (‘нехватка элементов’) End
Для организация очереди можно использовать аналогичный ссылочный тип, при этом необходимо иметь указатели на начальный nach и конечный kon элементы. Очередь удобно строить в прямом порядке (рис.1).
Рис.1. Пример построения очереди в прямом порядке
Циклически связанный список (циклический список) - такой список, в котором связь от последнего узла идет к первому элементу списка. На рис.2 изображен односвязный циклический список. В нем можно получить доступ к любому элементу списка, отправляясь от любой точки.
Рис.2. Пример циклического списка
Наиболее важные операции для односвязных циклических списков:
1. включить элемент слева
2. включить элемент справа
3. исключить узел слева
Если nach1 и nach2 указывают на два разных списка L1 и L2 (см. рис.3), то можно включить справа в список L1 весь список L2, для чего нужно выполнить присваивания, используя промежуточную переменную PP типа pointer:
Var PP: pointer {... } PP: =nach1. link nach1. link: =nach2. link nach2. link: = PP
Рис.3. Циклический список L1 + L2
Каждый элемент списка с двумя связями содержит два указателя: на соседние слева и справа элементы (см. рис.4). По такому списку удобно двигаться вперед и назад, так как он содержит два входа в список. Для создания двусвязного списка можно использовать следующий тип:
Type ptr=element element=record d: integer right,left: ptr end
Рис.4. Пример списка с двумя связями (двунаправленный список)
Важное преимущество двусвязного списка состоит в том, что для того чтобы удалить элемент tek, достаточно знать только адрес этого узла, так как адреса предыдущего и следующего элементов хранятся в tek. left и tek. right:
tek. left. right: =tek. right tek. right. left: =tek. left
Здесь вы можете проверить, как вы научились работать с двунаправленным списком.
Списки с полутора связями представляют собой чередование элементов с одной и двумя связями. Их преимущество: требуют меньше памяти, чем двусвязные, но ходить по списку можно вперед и назад.
Рис.5. Пример списка с полутора связями
Построение сложных структур в динамической памяти С помощью указателей можно создавать самые разнообразные структуры, в том числе более сложные, чем простые линейные списки. ............
