Xreferat.com » Рефераты по информатике и программированию » Основные понятия алгоритмического языка

Основные понятия алгоритмического языка

p3^:=p1^+Sqr(p2^);

writeln('p1^=',p1^:3,' p2^=',p2^:3,' p3^=',p3^:3);

p1:=p2;

writeln('p1^=',p1^:3,' p2^=',p2^:3)

end.


на экран дисплея будут выведены результаты:


p1^= 2 p2^= 4 p3^= 18

p1^= 4 p2^= 4


37. Д И Н А М И Ч Е С К И Е С Т Р У К Т У Р Ы

Д А Н Н Ы Х


Структурированные типы данных, такие, как массивы, множества, за-

писи, представляют собой статические структуры, так как их размеры

неизменны в течение всего времени выполнения программы.

Часто требуется, чтобы структуры данных меняли свои размеры в ходе

решения задачи. Такие структуры данных называются динамическими, к

ним относятся стеки, очереди, списки, деревья и другие. Описание ди-

намических структур с помощью массивов, записей и файлов приводит к

неэкономному использованию памяти ЭВМ и увеличивает время решения за-

дач.

Каждая компонента любой динамической структуры представляет собой

запись, содержащую по крайней мере два поля: одно поле типа указа-

тель, а второе - для размещения данных. В общем случае запись может

содержать не один, а несколько укзателей и несколько полей данных.

Поле данных может быть переменной, массивом, множеством или записью.

Для дальнейшего рассмотрения представим отдельную компоненту в ви-

де:

г=====¬

¦ D ¦

¦=====¦

¦ p ¦

L=====-

где поле p - указатель;

поле D - данные.

Описание этой компоненты дадим следующим образом:


type

Pointer = ^Comp;

Comp = record

D:T;

pNext:Pointer

end;


здесь T - тип данных.

Рассмотрим основные правила работы с динамическими структурами

данных типа стек, очередь и список, базируясь на приведенное описание

компоненты.


38. С Т Е К И


Стеком называется динамическая структура данных, добавление компо-

ненты в которую и исключение компоненты из которой производится из

одного конца, называемого вершиной стека. Стек работает по принципу


LIFO (Last-In, First-Out) -


поступивший последним, обслуживается первым.

Обычно над стеками выполняется три операции:

-начальное формирование стека (запись первой компоненты);

-добавление компоненты в стек;

-выборка компоненты (удаление).

Для формирования стека и работы с ним необходимо иметь две пере-

менные типа указатель, первая из которых определяет вершину стека, а

вторая - вспомогательная. Пусть описание этих переменных имеет вид:


var pTop, pAux: Pointer;


где pTop - указатель вершины стека;

pAux - вспомогательный указатель.

Начальное формирование стека выполняется следующими операторами:


г=====¬ г=====¬

New(pTop); ¦ *--¦---¬ ¦ ¦

L=====- ¦ ¦=====¦

pTop L-->¦ ¦

L=====-


г=====¬ г=====¬

pTop^.pNext:=NIL; ¦ *--¦---¬ ¦ ¦

L=====- ¦ ¦=====¦

pTop L-->¦ NIL ¦

L=====-


г=====¬ г=====¬

pTop^.D:=D1; ¦ *--¦---¬ ¦ D1 ¦

L=====- ¦ ¦=====¦

pTop L-->¦ NIL ¦

L=====-


Последний оператор или группа операторов записывает содержимое

поля данных первой компоненты.

Добавление компоненты в стек призводится с использованием вспо-

могательного указателя:


г=====¬ г=====¬ г=====¬

New(pAux); ¦ *--¦---¬ ¦ ¦ ----¦--* ¦

L=====- ¦ ¦=====¦ ¦ L=====-

pTop ¦ ¦ ¦<--- pAux

¦ L=====-

¦

¦ г=====¬

¦ ¦ D1 ¦

¦ ¦=====¦

L-->¦ NIL ¦

L=====-


г=====¬ г=====¬ г=====¬

pAux^.pNext:=pTop; ¦ *--¦---¬ ¦ ¦ ----¦--* ¦

L=====- ¦ ¦=====¦<--- L=====-

pTop ¦ ¦ *--¦-¬ pAux

¦ L=====- ¦

¦ ¦

¦ г=====¬ ¦

¦ ¦ D1 ¦ ¦

¦ ¦=====¦ ¦

L-->¦ NIL ¦<-

L=====-


г=====¬ г=====¬ г=====¬

pTop:=pAux; ¦ *--¦---¬ ¦ ¦ ----¦--* ¦

L=====- ¦ ¦=====¦<--- L=====-

pTop L-->¦ *--¦-¬ pAux

L=====- ¦

¦

г=====¬ ¦

¦ D1 ¦ ¦

¦=====¦ ¦

¦ NIL ¦<-

L=====-


г=====¬

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: