Авторизация |
Динамические структуры данных
Ранее рассмотрены данные, имеющие статическую структуру, неизменную в процессе работы программы. Для таких данных распределение памяти производится перед началом работы программы, и сопоставление переменной выделенной ей зоны памяти сохраняется до конца выполнения программы. Однако в ряде случаев для решения задач более удобно применять динамические, гибкие структуры данных, размеры и организация которых изменяются по ходу работы программы.
К таким типам данных относится в первую очередь ссылочный тип, объектами которого являются ссылки на определенные адреса в памяти. Каждый такой адрес указывает на начало некоторой зоны в памяти, выделенной для объекта заданного типа. Ссылочный тип описывается следующим образом:
type тип 1 = |…
Например, список вещественных чисел можно определить так:
type ссыл = f комп; комп = record дан: real; след ! ссыл end;
Допустим, такой список еще только нужно построить. Тогда, определив ссылочный тип, нужно ввести две ссылочные переменные:
var s, t i ссыл; после чего начинать строить с конца списка, выделив зону памяти с помощью оператора new (s) и создав в этой зоне пустой список оператором s: == nil, а затем выделив зону new (0 и разместив в этой зоне последний элемент списка.
Переприсвоим ссылки: ссылке текущего элемента списка (в данном случае пэ) присваиваем нынешнее значение начальной ссылки (в данном случае…
В число этих операций, помимо последовательного перехода от элемента к элементу, входят включение нового элемента в список и исключение элемента из списка. Включение и исключение элементов могут производиться в любом месте спискаПереход от одного элемента, к другому производится с помощью несложной операции. Пусть имеется ссылочная переменная, указывающая на некоторый элемент списка целых чисел. Если этой переменной присвоить след;
то значением этой переменной уже будет ссылка на следующий элемент списка (или nil, если этот элемент последний). Таким образом можно просматривать любую часть списка.
Итак, операции включения и исключения сводятся к изменению значений ссылочной части задействованных элементов. Но для работы с началом…
Различие в процедурах включения и исключения в зависимости от местоположения элемента требует дополнительных проверок. Чтобы избежать этого и унифицировать процедуру, прибегают к использованию заглавного элемента, информационная часть которого или пуста, или содержит служебную информацию. Заглавный элемент — величина в списке постоянная, он не может быть исключен, и перед ним нельзя ставить никакой другой элемент.
Задания
1. Какие операции можно производить со списками?
2. Как происходит переход от одного элемента списка к другому?
3. Как включить в список новый элемент?
4. Каким образом исключается элемент из списка?
5. Как производится включение в список и исключение первого элемента?
6. В чем смысл…
|
|