Линейные списки. Стек. Дек. Очередь
Категория реферата: Рефераты по информатике, программированию
Теги реферата: реферати, сочинение 5 класс
Добавил(а) на сайт: Губанов.
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата
В некоторых случаях возникает необходимость в качестве значения указателя принять «пустую» ссылку, которая не связывает с указателем никакого объекта. Такое значение в Паскале задается служебным словом nil и принадлежит любому ссылочному типу. Результаты выполнения оператора p:=nil можно изобразить следующим образом:
Процедура new(i) выполняет две функции:
1) резервирует место в памяти для размещения динамического объекта соответствующего типа с именем i;
2) указателю i присваивает адрес динамического объекта i.
Однако, узнать адрес динамической переменной с помощью процедуры writeln (i) нельзя.
Динамические объекты размещаются по типу стека в специальной области памяти — так называемой «куче» свободной от программ и статических переменных. Символ ^ после имени указателя означает, что речь идет не о значении ссылочной переменной, а о значении того динамического объекта, на который указывает эта ссылочная переменная.
Имя ссылочной переменной с последующим символом ^ называют «переменной с указателем». Именно она синтаксически выполняет роль динамической переменной и может быть использована в любых конструкциях языка, где допустимо использование переменных того типа, что и тип динамической переменной.
Если в процессе выполнения программы некоторый динамический объект р^, созданный в результате выполнения оператора new(p), становится ненужным, то его можно уничтожить (очистить выделенное ему место в памяти) с помощью стандартной процедуры dispose(p). В результате выполнения оператора вида dispose(p) динамический объект, на который указывает ссылочная переменная р, прекращает свое существование, занимаемое им место в памяти становится свободным, а значение указателя р становится неопределенным (но не равным nil).
Если до вызова процедуры dispose(p) имел пустое значение nil, то это приведет к «зависанию» программы.
Если же до вызова этой процедуры указатель р не был определен, то это может привести к выходу из строя операционной системы.
Значение одного указателя можно присвоить другому указателю того же типа. Можно также указатели одинакового типа сравнивать друг с другом, используя отношения «=» или «о».
Стандартные процедуры new и dispose позволяют динамически порождать программные объекты и уничтожать их, что дает возможность использовать память машины более эффективно.
Связанные списки данных. Несмотря на богатый набор типов данных в
Паскале, он не исчерпывает всего практически необходимого для разработки
многих классов программ. В частности, из разнообразных связанных структур
данных в языке стандартизированы массивы и файлы, а кроме них могут
потребоваться и схожие с ними, но иные структуры. Для них характерны, в
частности, следующие признаки: а) неопределенное заранее число элементов; б) необходимость хранения в оперативной памяти.
Средство для реализации таких структур дает аппарат динамических переменных. Простейшей из обсуждаемых структур является однонаправленный список. Он строится подобно очереди на прием к врачу: пациенты сидят на любых свободных местах, но каждый из них знает, за кем он в очереди (т.е. данные размещаются на свободных местах в памяти, но каждый элемент содержит ссылку на предыдущий или следующий элемент). Поскольку количество пациентов заранее не очевидно, структура является динамической.
Другая подобная структура - стек. Его моделью может служить трубка с
запаянным концом, в которую вкатывают шарики. При этом реализуется принцип
«последним вошел - первым вышел». Возможное количество элементов в стеке не
фиксировано.
Остановимся на примере стека и покажем его программную реализацию.
Технически при этом следует решить ряд задач, из которых наиболее
специфическими являются а) связывание последующих компонентов стека; б) смещение ссылок при каждом движении по стеку.
Из-за необходимости хранить не только значение каждого элемента, но и соответствующую ссылку на последующий элемент, каждый из элементов будем хранить в виде двухполевой записи, в которой первое поле - значение элемента, а второе - ссылка на следующий элемент. Схематически эту структуру можно описать следующим образом
(элементу, который пришел первым, ссылаться не на что, о чем свидетельствует «пустая ссылка» nil).
Ниже приведены примеры создания и уничтожения списков, добавление и удаление элементов из списка на Delphi. Рассмотрены только для однонаправленного и двунаправленного списков для остальных даны примеры в демонстрационной программе.
Type
List = ^Spisok; - Однонаправленный
Spisok = record
Info: Integer; - Информационное поле
Next: List; - Ссылка на следующий элемент end;
ListTwo = ^SpisokTwo; - Двунаправленный
Рекомендуем скачать другие рефераты по теме: гигиена реферат, курсовик.
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата