Реферат: Алгоритмические языки и программирование:. Алгоритмическое программирование реферат


Реферат: Алгоритмические языки и программирование

Московский авиационный институт

(технический университет)

------------------------

Кафедра вычислительной математики и программирования

К У Р С О В А Я Р А Б О Т А

по курсу

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

2 семестр

Студент: Xaлиулов.А.Р

Группа : 08-106

Руководитель: Никулин С.П.

Оценка:

Дата:

Москва 1995

1. 2ВВЕДЕНИЕ

Цель курсовой работы - проверить знания студента по

пройденному за второй семестр материалу. Студент должен владеть

основами работы в операционной системе UNIX, знать ее основные

команды и возможности, иметь представление об ЭВМ семейства VAX,

архитектуре и основных принципах работы.

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

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

матриц, организацию и работу с линейными списками.

Цель оформления отчетов по курсовой работе - привить студентам

навыки правильного оформления научно-технических отчетов,

программной и технической документации в соответствии со

стандартами.

2. Р Е Ф Е Р А Т

"Алгоритмы и структуры данных языка Pascal"

2.1 Введение

Любая программа, выполняемая на ЭВМ, обрабатывает данные с

целью получения требуемого результата. В современных языках

программирования (Pascal,C,Modula-2,Ada) имеются базовые типы

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

вых; они облегчают составление программ для решения сложных за-

дач,однако не избавляют программиста от проблем разработки ал-

горитмов и выбора подходящей структуры данных.

При разработке алгоритма выбирается некоторая удобная абс-

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

операций над этим абстрактным типом данных.

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

трактной структуры данных с помощью структуры данных языка

программирования (отображение на массив, на файлы).Если задача

позволяет,целесообразнее использовать более простые структуры

данных.К таким традиционным структурам данных, допускающих

простое и эффективное представление на ЭВМ, относятся массивы,

строки, записи, стеки, списки, деревья, таблицы, графы, файлы.

Очень часто язык содержит лишь некоторые из перечисленных

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

щихся.Так в Pascal граф можно представить с помощью массива или

списка, строку с помощью массива или списка.

Теперь последовательно рассмотрим вышеперечисленные структу-

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

языку Pascal.

2.2 _Массив

Переменная или константа, имеющая структуру массива, являет-

ся совокупностью элементов одного и того же типа. Каждая от-

дельная компонента массива может быть явно обозначена, доступ к

ней может осуществлятся по одному или нескольким индексам.Число

компонент массива определяется при его описании и во время ра-

боты программы не меняется. В Pascal массив является стандарт-

ным типом данных. Его объявление может иметь вид:

type massiv = array [1..10,1..10] of integer;

или packed array [1..10,1..10] of integer;

var M:massiv;

где М - массив размером 10*10 из целых чисел, а доступ к

компонентам осуществляется по индексам i и j. Возможность дина-

мического задания массива, как в Modula-2, в Pascal отсутству-

ет. Количество компонент массива, их тип должны задаваться явно

т.е. задаваться до начала работы программы. Массивы находят ши-

рокое применение при решении многих задач, в том числе и для

отображения более сложных структур данных.

2.3 _Последовательные файлы

Слово "файл" в языке Pascal употребляется для объектов сос-

тоящих из компонент одного и того же типа. В любой момент вре-

мени непосредственно доступна (для чтения и записи) только одна

компонента, другие становятся доступными по мере продвижения по

файлу. Таким образом, чтобы прочитать элемент файла необходимо

просмотреть все элементы стоящие до него. Такие файлы называют-

ся файлами последовательного доступа или последовательными фай-

лами. Длинна файла не фиксируется и может меняться в процессе

выполнения программы.

Файловый тип в Pascal - это единственный тип значений, пос-

редством которого данные, обрабатываемые программой, могут быть

получены извне, а результаты переданы во внешний мир.

В Pascal файловый тип задается следующим образом:

type T = TValue;{ тип компоненты файла }

< имя файлового типа > = file of T;

или packed file of T;

Как обычно, файловый тип может быть введен в употребление в

разделе типов, как было описано выше, либо непосредственно за-

дан при описании переменных, например:

var myfile: file of T;

Файлы, имена которых включаются в список заголовка програм-

мы, называются внешними файлами, они существуют вне программы.

Если же имена файлов не внесены в список заголовка программы,

то такие файлы существуют только во время выполнения программы

и называются внутренними. Внутренние файлы носят в основном

вспомогательный характер. Стандартный ввод осуществляется из

файла input, а вывод в файл output.

Для доступа к отдельным элементам файла в Pascal введены

специальные процедуры. Оператор процедуры rewrite(f) устанавли-

вает файл в режим записи, если раньше в этот файл были записаны

какие-то данные, то они теряются. Оператор процедуры write(f,x)

записывает в файл f очередную компоненту x, после чего окно

сдвигается на следующую позицию.

Если какой-то, компоненты которого уже записаны ранее, необ-

ходимо прочитать,то для этого в Pascal используются стандартные

процедуры reset и read. Оператор процедуры reset(f) переводит

файл f в режим чтения и устанавливает окно на первую пози-

цию файла. Оператор процедуры read(f,v) присваивает переменной

v значение текущей компоненты из файла f и передвигает окно на

следующую позицию. Процедура reset может применятся к одному и

тому же файлу несколько раз и при этом содержимое его не изме-

няется.

Если необходимо разделить копирование текущего элемента и

передвижение окна, используют стандартные процедуры с использо-

ванием буферной переменной. Она обозначается f_, где f - имя

файла. Тогда при чтении копируется значение елемента из окна

е:=f_ и окно сдвигается оператором процедуры get(f). При запи-

си сначала буферной переменной присваивается значение нового

элемента файла f_:=e и окно сдвигается оператором процедуры

put(f).

Работа с файлом может проходить либо в режиме записи, либо в

режиме чтения.Для определения конца файла в Pascal имеется

стандартная логическая функция eof (end of file).

Операция конкатенации двух файлов и отношение равенства над

файлами в Pascal не определены, но их достаточно просто реали-

зовать средствами языка.

2.4 _Списки

Использование только статических объектов при программирова-

нии может вызывать определенные трудности, так как не всегда

удается получить эффективную программу, а эффективность при ре-

шении многих задач является главным фактором. Иногда до работы

программы мы не знаем не только размера значения объекта, но и

даже того, будет ли он существовать или нет. Такого рода прог-

раммные объекты, которые возникают при выполнении программы или

размер которых изменяется во время выполнения программы, назы-

вают динамическими. Язык Pascal предусматривает возможность

составления эффективных программ с использованием динамических

объектов. При этом динамический объект не может иметь собствен-

ного имени, так как все идентификаторы должны быть описаны в

соответствующих разделах программы. Поэтому в Pascal принято не

именовать, а обозначать динамический объект и введен специаль-

ный ссылочный тип. Значением этого типа является ссылка на

программный объект, по которой осуществляется прямой доступ к

этому объекту. Динамический объект обозначается присоединением

символа _ к имени переменной-ссылки на этот объект:

type T = integer;{тип динамического объекта}

pointer = ^T;{имя ссылочного типа - pointer}

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

var p:pointer;

Значениями ссылочного типа являются значения адресов единиц

оперативной памяти конкретной машины. Значение NIL принадлежит

любому ссылочному типу. Оно указывает на отсутствие связи с

объектом. Сам динамический объект порождается с помощью стан-

дартной процедуры new, фактическим параметром которой является

ссылка на этот объект. Выполнение процедуры new(p) порождает

динамический объект типа Т, т.е. процедура new ищет в оператив-

ной памяти незадействованную до этого момента область памяти

подходящего размера и присваивает переменной-ссылке p значение

адреса начала этой области.

В языке Pascal также определена специальная процедура

dispose, уничтожающая динамический объект, т.е. высвобождающая

область памяти, зарезервированной под этот объект. Динамические

объекты размещающиеся на внешних носителях обычно имеют струк-

туру файла.

С помощью ссылочного типа можно создавать динамические

структуры самого разнообразного характера, например линейные

списки.

Структура данных,где каждый информационный элемент снабжает-

ся ссылкой на следующий за ним,называется связным списком. В

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

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

список как единый объект. Однонаправленный список из целых чи-

сел на Pascal можно организовать так:

type TValue = integer;

pointer = ^element;

element = record

info:TValue;

next:pointer;

end;

list = pointer;

где поле next - указатель на следующий элемент списка. Ука-

затель последнего элемента равен NIL. Однако при использовании

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

никнуть определенные трудности. По однонаправленному списку

можно двигаться только в одну сторону - от первого элемента к

последнему. Между тем нередко необходимо произвести обработку

элементов, предшествующих элементу с заданным свойством. Для

устранения этого неудобства в каждый элемент добавляется еще

одно поле prev - указатель на предшествующий элемент:

type pointer = ^element;

element = record

info:TValue;

prev:pointer;

next:pointer;

end;

dlist = pointer;

Динамическая структура состоящая из звеньев такого типа на-

зывается двунаправленным списком. Наличие ссылки на предыдущий

элемент списка позволяет двигаться в любом направлении по спис-

ку. В поле prev заглавного звена стоит ссылка NIL, так как у

заглавного звена нет предыдущего. Иногда значением поля next

последнего звена ставят ссылку на заглавное звено, а в поле

prev заглавного звена - ссылку на последнее звено. Список замы-

кается в "кольцо". Списки такого вида называют кольцевыми.

Списки также допускают отображение на массив, например одно-

направленный список допускает такое отображение:

type elem = record

info:TValue;

next:integer;

end;

list = array [1..10] of elem;

var L:list;

use,free:integer;

где поле next - указатель на расположение (индекс) следующе-

го элемента в массиве, а переменная use указывает на первый

элемент списка. Также используется список свободных элементов,

тоже связанных между собой. Переменная free указывает на первый

элемент списка свободных элементов. Отображение на массив явля-

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

ограничивается максимальным числом, т.е. размером массива. Сле-

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

Для удобной работы над списком определяются следующие базо-

вые операции:

Init(L) - создание списка.

Insert(L,n,v) - вставка элемента v в список под номером n.

Delete(n) - удаление n-го элемента списка или удаление эле-

мента по имени.

Print(L) - печать списка.

Find(L,v) - поиск элемента в списке.

Обработка элементов списка сводится к корректировке соот-

ветствующих ссылок. Списки также активно используются для орга-

низации еще более сложных структур данных, например очереди.

2.5 Оч _ередь

Очередь - упорядоченный, одномерный, динамически изменяемый

набор компонент, в котором включение новых компонент произво-

дится с одного конца очереди, а доступ и исключение с другого.

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

ляется динамическим объектом и длинна ее не фиксируется. Так

как в Pascal нет структурного типа очередь, его можно отобра-

зить на уже имеющиеся структуры: файл и массив. Отображение

очереди из целых чисел на массив можно реализовать так:

const N=10;

type Qel:integer;

Queue: record

first,last:integer;

body: array [1..N] of Qel;

end;

где first и last - указатели на первый и последний элемент

очереди соответственно, а N - максимальное число компонент оче-

реди. Отображение на массив накладывает ограничение на длину

очереди, кроме того программист сам запрещает себе прямой дос-

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

дующие процедуры:

Init(Q) - процедура создания очереди Q.

Empty(Q) - логическая функция, если очередь пуста Empty вы-

дает значение true, если нет - false.

Pop(Q) - процедура, выталкивающая первый элемент очереди Q.

Top(Q) - функция, выдающая значение первого элемента очереди.

Push(Q,v) - процедура, добавляющая новый элемент v типа Qel

в конец очереди Q.

Print(Q) - процедура, распечатывающая содержимое очереди.

Size(Q) - функция, выдающая число компонент (длину) очереди.

Отображение очереди на файл выглядит так:

type T = Qel;

Queue = file of T;

Операции над очередью определяются также как и при отображе-

нии на массив, а обработка элементов ведется с использованием

буферной переменной. При таком отображении время на операции

тратится больше, так как файл приходится все время "перематы-

вать".

На Pascal очередь может быть организована и как двунаправ-

ленный список:

type T = Qel;

pointer = ^T;

Queue = record

info:T;

pred,sled:pointer;

end;

где pred и sled - указатели на предыдущий и следующий эле-

мент очереди. Операции над очередью при такой организации опре-

деляются аналогично.

2.6 _Стек

Стек - структура данных, в которой можно добавлять и уда-

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

последний добавленный элемент. Как и очередь стек в Pascal мож-

но организовать в виде линейного списка:

type pointer = ^elem;

elem = record

info:TValue;

sled:pointer;

end;

Stask = pointer;

или отображения на массив:

const N=10;

type Stask = record

tp:integer;

body:array [1..N] of TValue;

end;

Для работы со стеком реализуются процедуры:

Init(S) - процедура создания стека S.

Empty(S) - логическая функция, выдающая true если стек пуст

и false если в нем есть элементы.

Push(S,v) - процедура вставляющая новый элемент v в стек.

Pop(S) - процедура выталкивающая верхний элемент из стека.

Top(S) - функция, возвращающая значение верхнего элемента

стека.

Size(S) - функция,возвращающая число элементов стека.

Display(S) - процедура, распечатывающая содержимое стека.

Имея эти базовые процедуры довольно просто реализовать про-

цедуры: вставки элемента в стек под каким-то номером

(Insert(S,v,n)) и удаления элемента из стека по значению

(Remove(S)). Надо заметить, что стек - одна из наиболее исполь-

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

решении различных задач.

2.7 _Дек

Deque (double-ended queue) - двухсторонняя очередь, структу-

ра данных, где элементы могут добавляться и удаляться с обоих

концов. Дек является и стеком и очередью одновременно. При реа-

лизации должны быть определены операции: вставка нового элемен-

та в начало дека, вставка нового элемента в конец дека, удале-

ние (или просмотр) элемента из начала дека, удаление элемента

из конца дека.

2.8 _Графы

Множество объектов соединенных произвольным образом, но не

более чем одной линией связи между двумя объектами - называется

графом.Связный граф - когда имеется путь между двумя вершинами,

ориентированный граф - в котором линии связи имеют определенное

направление.При использовании графов часто возникает проблема

поиска пути между двумя вершинами.

В Pascal удобно для этой цели представлять граф в виде мат-

рицы смежности, в которой хранится информация о связях между

вершинами графа.Если граф содержит N вершин, то матрица смеж-

ности - квадратная булевская матрица N*N, в которой

М(i,j)=true, если есть связь между i-ой и j-ой вершинами и

М(i,j)=false в противном случае. Для неориентированных графов

матрица смежности симметрична.

Граф с К вершинами можно также представить в виде К списков,

соответствующих вершинам и содержащих номера вершин с которыми

у данной есть связь.Если граф меняется в процессе обработки,

т.е. добавляются и удаляются вершины и линии связи, то удобнее

использовать списки.

Графы применяются в задачах машинного проектирования и в

создании систем искусственного интеллекта.

2.9 _Деревья

Дерево - частный случай графа.Структура определяется рекур-

сивно,образованная данным элементом, называемым корнем дерева,

и конечным списком с переменным числом элементов - деревьев то-

го же типа, называемых поддеревьями. Двоичным или бинарным де-

ревом называется дерево состоящее из корня, правого и левого

поддеревьев.

В Pascal двоичное дерево можно определить так:

type BTree = ^BNode;

BNode = record

info:TValue;

left,right:BTree;

end;

При анализе структур данных, заданных в виде дерева, приме-

няются различные способы просмотра и перебора узлов.Основная

особенность каждого обхода заключается в том, что просматрива-

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

обрабатывается ровно один раз.

Для бинарного дерева определены три способа обхода: прямой

или префиксный (корень - левое поддерево - правое поддере-

во),обратный или инфиксный (левое поддерево - корень - правое

поддерево) и концевой или постфиксный (левое поддерево - правое

поддерево - корень).

При обходе дерева используются рекурсивные процедуры или

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

на наличие поддеревьев (LTAG и RTAG). Введение дополнительных

указателей не приводит к большому увеличению затрат памяти, но

позволяет при обходе отказаться от стека.

Надо отметить,что любое дерево общего вида можно представить

в виде двоичного, надо в исходном дереве у каждого узла соеди-

нить его сыновей от старшего к младшему и убрать все связи узла

с сыновьями, оставив только связь со старшим сыном.

Над деревьями удобно определить операции: чтение информаци-

онной части из узла дерева, создание дерева, присоединение к

узлу нового поддерева, удаление поддерева.

Особенно полезны деревья при сортировке.Алгоритм состоит в

том, что при просмотре данных очередной элемент помещается в

двоичное дерево. Ключ нового элемента сравнивается с ключом те-

кущего узла.Если указатель текущего узла NIL, то указатель на

новый узел добавляется в то место откуда был извлечен NIL.Если

ключ нового узла меньше ключа текущего узла, то поиск места для

нового узла продолжается в левом поддереве, если больше - в

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

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

Деревья применяются также при интерпритации и вычислении

как арифметических, так и логических.

Теперь рассмотрим области применения сложных структур дан-

ных.Одной из таких областей является процесс создания компиля-

торов, который отработан достаточно хорошо.

Исходный текст разбивается на лексемы (идентификаторы, конс-

танты, знаки операций). Лексемы заносятся в таблицы, а в тексте

лексема заменяется ссылкой на элемент таблицы, таким образом

текст программы заменяется на последовательность лексем. Для

того, чтобы один и тот же идентификатор заменялся ссылкой на

один и тот же элемент таблицы, необходлимо для каждого анализи-

руемого идентификатора просматривать все встретившиеся ранее.

Для ускорения этого поиска применяются: упорядочение элементов

таблицы (сортировка) для дальнейшего бинарного поиска, хеш-ад-

ресация и некоторые другие способы.Для хранения последователь-

ности лексем используют массивы и списки.

Следующим этапом после замены текста программы на цепочку

лексем является синтаксический анализ, при котором широко ис-

пользуются стеки, таблицы и строки.

В операционных системах распространены такие сложные струк-

туры данных, как очереди. Операционная система вынуждена под-

держивать несколько очередей: очередь процессов готовых к вы-

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

(например к принтеру).

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

равления базами данных (СУБД). СУБД могут накапливать информа-

цию о большом числе объектов, описание которых содержат разные

сведения.

Свойства объектов могут выступать в роли ключей (например

фамилия служащего) и тогда по этим свойствам объекты могут быть

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

Для описания объектов обычно используют записи, которые в

свою очередь могут содержать ссылку на список из записей.

Наконец,еще одной областью применения являются задачи с ис-

пользованием разреженных матриц (с относительно небольшим чис-

лом ненулевых элементов).Иногда при нехватке оперативной памяти

бывает выгодно хранить только ненулевые элементы, применяя раз-

личные методы упаковки (в три массива, в один массив, с помощью

связного списка и т.д.).

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

шении используемых структур данных. Удачный выбор структуры

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

трудоемкость разработки и повышает надежность.

2.10 С П И С О К И С П О Л Ь З О В А Н Н Ы Х

И С Т О Ч Н И К О В

1. В.М.Брябрин. Программное обеспечение персональных

ЭВМ, М., "Наука", 1990.

2. Н.Вирт. Програмирование на языке Модула-2,

М., "Мир", 1987.

3. К.Кристиан. Введение в операционную систему UNIX,

М., "Финансы и статистика", 1985.

4. М.И.Беляков, Ю.И.Рабовер, А.Л.Фридман.

Мобильная операционная система,М.,"Радио и связь",

1991.

5. Ф.Л.Бауэр, Г.Гооз, Информатика, т.2, М., "Мир",

1990.

6. В.Г.Абрамов, Н.П.Трифонов, Г.Н.Трифонова,

Введение в язык паскаль,М., "Наука",1988.

7. И.З.Луговая, Л.Н.Чернышов, С.М.Юдин,

Динамические структуры данных языка паскаль, М.,

издательство МАИ, 1988.

8. Л.Н.Чернышов, С.М.Юдин, Инструментальная система

ИНФОРТ и работа с динамическими структурами данных,

М., издательство МАИ, 1984.

9. Лекции, семинары, консультации по АЯП.

superbotanik.net

Курсовая работа - Алгоритмические языки и программирование

Московский авиационный институт

(технический университет)

------------------------

Кафедра вычислительной математики и программирования

К У Р С О В А Я Р А Б О Т А

по курсу

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

2 семестр

Студент: Xaлиулов.А.Р

Группа: 08-106

Руководитель: Никулин С.П.

Оценка:

Дата:

Москва 1995

1. 2ВВЕДЕНИЕ

Цель курсовой работы — проверить знания студента по

пройденному за второй семестр материалу. Студент должен владеть

основами работы в операционной системе UNIX, знать ее основные

команды и возможности, иметь представление об ЭВМ семейства VAX,

архитектуре и основных принципах работы.

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

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

матриц, организацию и работу с линейными списками.

Цель оформления отчетов по курсовой работе — привить студентам

навыки правильного оформления научно-технических отчетов,

программной и технической документации в соответствии со

стандартами.

2. Р Е Ф Е Р А Т

«Алгоритмы и структуры данных языка Pascal»

2.1 Введение

Любая программа, выполняемая на ЭВМ, обрабатывает данные с

целью получения требуемого результата. В современных языках

программирования (Pascal,C,Modula-2,Ada) имеются базовые типы

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

вых; они облегчают составление программ для решения сложных за-

дач, однако не избавляют программиста от проблем разработки ал-

горитмов и выбора подходящей структуры данных.

При разработке алгоритма выбирается некоторая удобная абс-

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

операций над этим абстрактным типом данных.

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

трактной структуры данных с помощью структуры данных языка

программирования (отображение на массив, на файлы).Если задача

позволяет, целесообразнее использовать более простые структуры

данных.К таким традиционным структурам данных, допускающих

простое и эффективное представление на ЭВМ, относятся массивы,

строки, записи, стеки, списки, деревья, таблицы, графы, файлы.

Очень часто язык содержит лишь некоторые из перечисленных

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

щихся.Так в Pascal граф можно представить с помощью массива или

списка, строку с помощью массива или списка.

Теперь последовательно рассмотрим вышеперечисленные структу-

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

языку Pascal.

2.2 _Массив

Переменная или константа, имеющая структуру массива, являет-

ся совокупностью элементов одного и того же типа. Каждая от-

дельная компонента массива может быть явно обозначена, доступ к

ней может осуществлятся по одному или нескольким индексам.Число

компонент массива определяется при его описании и во время ра-

боты программы не меняется. В Pascal массив является стандарт-

ным типом данных. Его объявление может иметь вид:

type massiv = array [1..10,1..10] of integer;

или packed array [1..10,1..10] of integer;

var M:massiv;

где М — массив размером 10*10 из целых чисел, а доступ к

компонентам осуществляется по индексам i и j. Возможность дина-

мического задания массива, как в Modula-2, в Pascal отсутству-

ет. Количество компонент массива, их тип должны задаваться явно

т.е. задаваться до начала работы программы. Массивы находят ши-

рокое применение при решении многих задач, в том числе и для

отображения более сложных структур данных.

2.3 _Последовательные файлы

Слово «файл» в языке Pascal употребляется для объектов сос-

тоящих из компонент одного и того же типа. В любой момент вре-

мени непосредственно доступна (для чтения и записи) только одна

компонента, другие становятся доступными по мере продвижения по

файлу. Таким образом, чтобы прочитать элемент файла необходимо

просмотреть все элементы стоящие до него. Такие файлы называют-

ся файлами последовательного доступа или последовательными фай-

лами. Длинна файла не фиксируется и может меняться в процессе

выполнения программы.

Файловый тип в Pascal — это единственный тип значений, пос-

редством которого данные, обрабатываемые программой, могут быть

получены извне, а результаты переданы во внешний мир.

В Pascal файловый тип задается следующим образом:

type T = TValue;{ тип компоненты файла }

< имя файлового типа > = file of T;

или packed file of T;

Как обычно, файловый тип может быть введен в употребление в

разделе типов, как было описано выше, либо непосредственно за-

дан при описании переменных, например:

var myfile: file of T;

Файлы, имена которых включаются в список заголовка програм-

мы, называются внешними файлами, они существуют вне программы.

Если же имена файлов не внесены в список заголовка программы,

то такие файлы существуют только во время выполнения программы

и называются внутренними. Внутренние файлы носят в основном

вспомогательный характер. Стандартный ввод осуществляется из

файла input, а вывод в файл output.

Для доступа к отдельным элементам файла в Pascal введены

специальные процедуры. Оператор процедуры rewrite(f) устанавли-

вает файл в режим записи, если раньше в этот файл были записаны

какие-то данные, то они теряются. Оператор процедуры write(f,x)

записывает в файл f очередную компоненту x, после чего окно

сдвигается на следующую позицию.

Если какой-то, компоненты которого уже записаны ранее, необ-

ходимо прочитать, то для этого в Pascal используются стандартные

процедуры reset и read. Оператор процедуры reset(f) переводит

файл f в режим чтения и устанавливает окно на первую пози-

цию файла. Оператор процедуры read(f,v) присваивает переменной

v значение текущей компоненты из файла f и передвигает окно на

следующую позицию. Процедура reset может применятся к одному и

тому же файлу несколько раз и при этом содержимое его не изме-

няется.

Если необходимо разделить копирование текущего элемента и

передвижение окна, используют стандартные процедуры с использо-

ванием буферной переменной. Она обозначается f_, где f — имя

файла. Тогда при чтении копируется значение елемента из окна

е:=f_ и окно сдвигается оператором процедуры get(f). При запи-

си сначала буферной переменной присваивается значение нового

элемента файла f_:=e и окно сдвигается оператором процедуры

put(f).

Работа с файлом может проходить либо в режиме записи, либо в

режиме чтения.Для определения конца файла в Pascal имеется

стандартная логическая функция eof (end of file).

Операция конкатенации двух файлов и отношение равенства над

файлами в Pascal не определены, но их достаточно просто реали-

зовать средствами языка.

2.4 _Списки

Использование только статических объектов при программирова-

нии может вызывать определенные трудности, так как не всегда

удается получить эффективную программу, а эффективность при ре-

шении многих задач является главным фактором. Иногда до работы

программы мы не знаем не только размера значения объекта, но и

даже того, будет ли он существовать или нет. Такого рода прог-

раммные объекты, которые возникают при выполнении программы или

размер которых изменяется во время выполнения программы, назы-

вают динамическими. Язык Pascal предусматривает возможность

составления эффективных программ с использованием динамических

объектов. При этом динамический объект не может иметь собствен-

ного имени, так как все идентификаторы должны быть описаны в

соответствующих разделах программы. Поэтому в Pascal принято не

именовать, а обозначать динамический объект и введен специаль-

ный ссылочный тип. Значением этого типа является ссылка на

программный объект, по которой осуществляется прямой доступ к

этому объекту. Динамический объект обозначается присоединением

символа _ к имени переменной-ссылки на этот объект:

type T = integer;{тип динамического объекта}

pointer = ^T;{имя ссылочного типа — pointer}

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

var p:pointer;

Значениями ссылочного типа являются значения адресов единиц

оперативной памяти конкретной машины. Значение NIL принадлежит

любому ссылочному типу. Оно указывает на отсутствие связи с

объектом. Сам динамический объект порождается с помощью стан-

дартной процедуры new, фактическим параметром которой является

ссылка на этот объект. Выполнение процедуры new(p) порождает

динамический объект типа Т, т.е. процедура new ищет в оператив-

ной памяти незадействованную до этого момента область памяти

подходящего размера и присваивает переменной-ссылке p значение

адреса начала этой области.

В языке Pascal также определена специальная процедура

dispose, уничтожающая динамический объект, т.е. высвобождающая

область памяти, зарезервированной под этот объект. Динамические

объекты размещающиеся на внешних носителях обычно имеют струк-

туру файла.

С помощью ссылочного типа можно создавать динамические

структуры самого разнообразного характера, например линейные

списки.

Структура данных, где каждый информационный элемент снабжает-

ся ссылкой на следующий за ним, называется связным списком. В

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

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

список как единый объект. Однонаправленный список из целых чи-

сел на Pascal можно организовать так:

type TValue = integer;

pointer = ^element;

element = record

info:TValue;

next:pointer;

end;

list = pointer;

где поле next — указатель на следующий элемент списка. Ука-

затель последнего элемента равен NIL. Однако при использовании

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

никнуть определенные трудности. По однонаправленному списку

можно двигаться только в одну сторону — от первого элемента к

последнему. Между тем нередко необходимо произвести обработку

элементов, предшествующих элементу с заданным свойством. Для

устранения этого неудобства в каждый элемент добавляется еще

одно поле prev — указатель на предшествующий элемент:

type pointer = ^element;

element = record

info:TValue;

prev:pointer;

next:pointer;

end;

dlist = pointer;

Динамическая структура состоящая из звеньев такого типа на-

зывается двунаправленным списком. Наличие ссылки на предыдущий

элемент списка позволяет двигаться в любом направлении по спис-

ку. В поле prev заглавного звена стоит ссылка NIL, так как у

заглавного звена нет предыдущего. Иногда значением поля next

последнего звена ставят ссылку на заглавное звено, а в поле

prev заглавного звена — ссылку на последнее звено. Список замы-

кается в «кольцо». Списки такого вида называют кольцевыми.

Списки также допускают отображение на массив, например одно-

направленный список допускает такое отображение:

type elem = record

info:TValue;

next:integer;

end;

list = array [1..10] of elem;

var L:list;

use,free:integer;

где поле next — указатель на расположение (индекс) следующе-

го элемента в массиве, а переменная use указывает на первый

элемент списка. Также используется список свободных элементов,

тоже связанных между собой. Переменная free указывает на первый

элемент списка свободных элементов. Отображение на массив явля-

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

ограничивается максимальным числом, т.е. размером массива. Сле-

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

Для удобной работы над списком определяются следующие базо-

вые операции:

Init(L) — создание списка.

Insert(L,n,v) — вставка элемента v в список под номером n.

Delete(n) — удаление n-го элемента списка или удаление эле-

мента по имени.

Print(L) — печать списка.

Find(L,v) — поиск элемента в списке.

Обработка элементов списка сводится к корректировке соот-

ветствующих ссылок. Списки также активно используются для орга-

низации еще более сложных структур данных, например очереди.

2.5 Оч _ередь

Очередь — упорядоченный, одномерный, динамически изменяемый

набор компонент, в котором включение новых компонент произво-

дится с одного конца очереди, а доступ и исключение с другого.

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

ляется динамическим объектом и длинна ее не фиксируется. Так

как в Pascal нет структурного типа очередь, его можно отобра-

зить на уже имеющиеся структуры: файл и массив. Отображение

очереди из целых чисел на массив можно реализовать так:

const N=10;

type Qel:integer;

Queue: record

first,last:integer;

body: array [1..N] of Qel;

end;

где first и last — указатели на первый и последний элемент

очереди соответственно, а N — максимальное число компонент оче-

реди. Отображение на массив накладывает ограничение на длину

очереди, кроме того программист сам запрещает себе прямой дос-

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

дующие процедуры:

Init(Q) — процедура создания очереди Q.

Empty(Q) — логическая функция, если очередь пуста Empty вы-

дает значение true, если нет — false.

Pop(Q) — процедура, выталкивающая первый элемент очереди Q.

Top(Q) — функция, выдающая значение первого элемента очереди.

Push(Q,v) — процедура, добавляющая новый элемент v типа Qel

в конец очереди Q.

Print(Q) — процедура, распечатывающая содержимое очереди.

Size(Q) — функция, выдающая число компонент (длину) очереди.

Отображение очереди на файл выглядит так:

type T = Qel;

Queue = file of T;

Операции над очередью определяются также как и при отображе-

нии на массив, а обработка элементов ведется с использованием

буферной переменной. При таком отображении время на операции

тратится больше, так как файл приходится все время «перематы-

вать».

На Pascal очередь может быть организована и как двунаправ-

ленный список:

type T = Qel;

pointer = ^T;

Queue = record

info:T;

pred,sled:pointer;

end;

где pred и sled — указатели на предыдущий и следующий эле-

мент очереди. Операции над очередью при такой организации опре-

деляются аналогично.

2.6 _Стек

Стек — структура данных, в которой можно добавлять и уда-

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

последний добавленный элемент. Как и очередь стек в Pascal мож-

но организовать в виде линейного списка:

type pointer = ^elem;

elem = record

info:TValue;

sled:pointer;

end;

Stask = pointer;

или отображения на массив:

const N=10;

type Stask = record

tp:integer;

body:array [1..N] of TValue;

end;

Для работы со стеком реализуются процедуры:

Init(S) — процедура создания стека S.

Empty(S) — логическая функция, выдающая true если стек пуст

и false если в нем есть элементы.

Push(S,v) — процедура вставляющая новый элемент v в стек.

Pop(S) — процедура выталкивающая верхний элемент из стека.

Top(S) — функция, возвращающая значение верхнего элемента

стека.

Size(S) — функция, возвращающая число элементов стека.

Display(S) — процедура, распечатывающая содержимое стека.

Имея эти базовые процедуры довольно просто реализовать про-

цедуры: вставки элемента в стек под каким-то номером

(Insert(S,v,n)) и удаления элемента из стека по значению

(Remove(S)). Надо заметить, что стек — одна из наиболее исполь-

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

решении различных задач.

2.7 _Дек

Deque (double-ended queue) — двухсторонняя очередь, структу-

ра данных, где элементы могут добавляться и удаляться с обоих

концов. Дек является и стеком и очередью одновременно. При реа-

лизации должны быть определены операции: вставка нового элемен-

та в начало дека, вставка нового элемента в конец дека, удале-

ние (или просмотр) элемента из начала дека, удаление элемента

из конца дека.

2.8 _Графы

Множество объектов соединенных произвольным образом, но не

более чем одной линией связи между двумя объектами — называется

графом.Связный граф — когда имеется путь между двумя вершинами,

ориентированный граф — в котором линии связи имеют определенное

направление.При использовании графов часто возникает проблема

поиска пути между двумя вершинами.

В Pascal удобно для этой цели представлять граф в виде мат-

рицы смежности, в которой хранится информация о связях между

вершинами графа.Если граф содержит N вершин, то матрица смеж-

ности — квадратная булевская матрица N*N, в которой

М(i,j)=true, если есть связь между i-ой и j-ой вершинами и

М(i,j)=false в противном случае. Для неориентированных графов

матрица смежности симметрична.

Граф с К вершинами можно также представить в виде К списков,

соответствующих вершинам и содержащих номера вершин с которыми

у данной есть связь.Если граф меняется в процессе обработки,

т.е. добавляются и удаляются вершины и линии связи, то удобнее

использовать списки.

Графы применяются в задачах машинного проектирования и в

создании систем искусственного интеллекта.

2.9 _Деревья

Дерево — частный случай графа.Структура определяется рекур-

сивно, образованная данным элементом, называемым корнем дерева,

и конечным списком с переменным числом элементов — деревьев то-

го же типа, называемых поддеревьями. Двоичным или бинарным де-

ревом называется дерево состоящее из корня, правого и левого

поддеревьев.

В Pascal двоичное дерево можно определить так:

type BTree = ^BNode;

BNode = record

info:TValue;

left,right:BTree;

end;

При анализе структур данных, заданных в виде дерева, приме-

няются различные способы просмотра и перебора узлов.Основная

особенность каждого обхода заключается в том, что просматрива-

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

обрабатывается ровно один раз.

Для бинарного дерева определены три способа обхода: прямой

или префиксный (корень — левое поддерево — правое поддере-

во), обратный или инфиксный (левое поддерево — корень — правое

поддерево) и концевой или постфиксный (левое поддерево — правое

поддерево — корень).

При обходе дерева используются рекурсивные процедуры или

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

на наличие поддеревьев (LTAG и RTAG). Введение дополнительных

указателей не приводит к большому увеличению затрат памяти, но

позволяет при обходе отказаться от стека.

Надо отметить, что любое дерево общего вида можно представить

в виде двоичного, надо в исходном дереве у каждого узла соеди-

нить его сыновей от старшего к младшему и убрать все связи узла

с сыновьями, оставив только связь со старшим сыном.

Над деревьями удобно определить операции: чтение информаци-

онной части из узла дерева, создание дерева, присоединение к

узлу нового поддерева, удаление поддерева.

Особенно полезны деревья при сортировке.Алгоритм состоит в

том, что при просмотре данных очередной элемент помещается в

двоичное дерево. Ключ нового элемента сравнивается с ключом те-

кущего узла.Если указатель текущего узла NIL, то указатель на

новый узел добавляется в то место откуда был извлечен NIL.Если

ключ нового узла меньше ключа текущего узла, то поиск места для

нового узла продолжается в левом поддереве, если больше — в

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

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

Деревья применяются также при интерпритации и вычислении

как арифметических, так и логических.

Теперь рассмотрим области применения сложных структур дан-

ных.Одной из таких областей является процесс создания компиля-

торов, который отработан достаточно хорошо.

Исходный текст разбивается на лексемы (идентификаторы, конс-

танты, знаки операций). Лексемы заносятся в таблицы, а в тексте

лексема заменяется ссылкой на элемент таблицы, таким образом

текст программы заменяется на последовательность лексем. Для

того, чтобы один и тот же идентификатор заменялся ссылкой на

один и тот же элемент таблицы, необходлимо для каждого анализи-

руемого идентификатора просматривать все встретившиеся ранее.

Для ускорения этого поиска применяются: упорядочение элементов

таблицы (сортировка) для дальнейшего бинарного поиска, хеш-ад-

ресация и некоторые другие способы.Для хранения последователь-

ности лексем используют массивы и списки.

Следующим этапом после замены текста программы на цепочку

лексем является синтаксический анализ, при котором широко ис-

пользуются стеки, таблицы и строки.

В операционных системах распространены такие сложные струк-

туры данных, как очереди. Операционная система вынуждена под-

держивать несколько очередей: очередь процессов готовых к вы-

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

(например к принтеру).

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

равления базами данных (СУБД). СУБД могут накапливать информа-

цию о большом числе объектов, описание которых содержат разные

сведения.

Свойства объектов могут выступать в роли ключей (например

фамилия служащего) и тогда по этим свойствам объекты могут быть

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

Для описания объектов обычно используют записи, которые в

свою очередь могут содержать ссылку на список из записей.

Наконец, еще одной областью применения являются задачи с ис-

пользованием разреженных матриц (с относительно небольшим чис-

лом ненулевых элементов).Иногда при нехватке оперативной памяти

бывает выгодно хранить только ненулевые элементы, применяя раз-

личные методы упаковки (в три массива, в один массив, с помощью

связного списка и т.д.).

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

шении используемых структур данных. Удачный выбор структуры

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

трудоемкость разработки и повышает надежность.

2.10 С П И С О К И С П О Л Ь З О В А Н Н Ы Х

И С Т О Ч Н И К О В

1. В.М.Брябрин. Программное обеспечение персональных

ЭВМ, М., «Наука», 1990.

2. Н.Вирт. Програмирование на языке Модула-2,

М., «Мир», 1987.

3. К.Кристиан. Введение в операционную систему UNIX,

М., «Финансы и статистика», 1985.

4. М.И.Беляков, Ю.И.Рабовер, А.Л.Фридман.

Мобильная операционная система, М.,«Радио и связь»,

1991.

5. Ф.Л.Бауэр, Г.Гооз, Информатика, т.2, М., «Мир»,

1990.

6. В.Г.Абрамов, Н.П.Трифонов, Г.Н.Трифонова,

Введение в язык паскаль, М., «Наука»,1988.

7. И.З.Луговая, Л.Н.Чернышов, С.М.Юдин,

Динамические структуры данных языка паскаль, М.,

издательство МАИ, 1988.

8. Л.Н.Чернышов, С.М.Юдин, Инструментальная система

ИНФОРТ и работа с динамическими структурами данных,

М., издательство МАИ, 1984.

9. Лекции, семинары, консультации по АЯП.

www.ronl.ru

Реферат - Алгоритмические языки и программирование

Московский авиационный институт

(технический университет)

------------------------

Кафедра вычислительной математики и программирования

К У Р С О В А Я Р А Б О Т А

по курсу

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

2 семестр

Студент: Xaлиулов.А.Р

Группа: 08-106

Руководитель: Никулин С.П.

Оценка:

Дата:

Москва 1995

1. 2ВВЕДЕНИЕ

Цель курсовой работы — проверить знания студента по

пройденному за второй семестр материалу. Студент должен владеть

основами работы в операционной системе UNIX, знать ее основные

команды и возможности, иметь представление об ЭВМ семейства VAX,

архитектуре и основных принципах работы.

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

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

матриц, организацию и работу с линейными списками.

Цель оформления отчетов по курсовой работе — привить студентам

навыки правильного оформления научно-технических отчетов,

программной и технической документации в соответствии со

стандартами.

2. Р Е Ф Е Р А Т

«Алгоритмы и структуры данных языка Pascal»

2.1 Введение

Любая программа, выполняемая на ЭВМ, обрабатывает данные с

целью получения требуемого результата. В современных языках

программирования (Pascal,C,Modula-2,Ada) имеются базовые типы

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

вых; они облегчают составление программ для решения сложных за-

дач, однако не избавляют программиста от проблем разработки ал-

горитмов и выбора подходящей структуры данных.

При разработке алгоритма выбирается некоторая удобная абс-

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

операций над этим абстрактным типом данных.

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

трактной структуры данных с помощью структуры данных языка

программирования (отображение на массив, на файлы).Если задача

позволяет, целесообразнее использовать более простые структуры

данных.К таким традиционным структурам данных, допускающих

простое и эффективное представление на ЭВМ, относятся массивы,

строки, записи, стеки, списки, деревья, таблицы, графы, файлы.

Очень часто язык содержит лишь некоторые из перечисленных

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

щихся.Так в Pascal граф можно представить с помощью массива или

списка, строку с помощью массива или списка.

Теперь последовательно рассмотрим вышеперечисленные структу-

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

языку Pascal.

2.2 _Массив

Переменная или константа, имеющая структуру массива, являет-

ся совокупностью элементов одного и того же типа. Каждая от-

дельная компонента массива может быть явно обозначена, доступ к

ней может осуществлятся по одному или нескольким индексам.Число

компонент массива определяется при его описании и во время ра-

боты программы не меняется. В Pascal массив является стандарт-

ным типом данных. Его объявление может иметь вид:

type massiv = array [1..10,1..10] of integer;

или packed array [1..10,1..10] of integer;

var M:massiv;

где М — массив размером 10*10 из целых чисел, а доступ к

компонентам осуществляется по индексам i и j. Возможность дина-

мического задания массива, как в Modula-2, в Pascal отсутству-

ет. Количество компонент массива, их тип должны задаваться явно

т.е. задаваться до начала работы программы. Массивы находят ши-

рокое применение при решении многих задач, в том числе и для

отображения более сложных структур данных.

2.3 _Последовательные файлы

Слово «файл» в языке Pascal употребляется для объектов сос-

тоящих из компонент одного и того же типа. В любой момент вре-

мени непосредственно доступна (для чтения и записи) только одна

компонента, другие становятся доступными по мере продвижения по

файлу. Таким образом, чтобы прочитать элемент файла необходимо

просмотреть все элементы стоящие до него. Такие файлы называют-

ся файлами последовательного доступа или последовательными фай-

лами. Длинна файла не фиксируется и может меняться в процессе

выполнения программы.

Файловый тип в Pascal — это единственный тип значений, пос-

редством которого данные, обрабатываемые программой, могут быть

получены извне, а результаты переданы во внешний мир.

В Pascal файловый тип задается следующим образом:

type T = TValue;{ тип компоненты файла }

< имя файлового типа > = file of T;

или packed file of T;

Как обычно, файловый тип может быть введен в употребление в

разделе типов, как было описано выше, либо непосредственно за-

дан при описании переменных, например:

var myfile: file of T;

Файлы, имена которых включаются в список заголовка програм-

мы, называются внешними файлами, они существуют вне программы.

Если же имена файлов не внесены в список заголовка программы,

то такие файлы существуют только во время выполнения программы

и называются внутренними. Внутренние файлы носят в основном

вспомогательный характер. Стандартный ввод осуществляется из

файла input, а вывод в файл output.

Для доступа к отдельным элементам файла в Pascal введены

специальные процедуры. Оператор процедуры rewrite(f) устанавли-

вает файл в режим записи, если раньше в этот файл были записаны

какие-то данные, то они теряются. Оператор процедуры write(f,x)

записывает в файл f очередную компоненту x, после чего окно

сдвигается на следующую позицию.

Если какой-то, компоненты которого уже записаны ранее, необ-

ходимо прочитать, то для этого в Pascal используются стандартные

процедуры reset и read. Оператор процедуры reset(f) переводит

файл f в режим чтения и устанавливает окно на первую пози-

цию файла. Оператор процедуры read(f,v) присваивает переменной

v значение текущей компоненты из файла f и передвигает окно на

следующую позицию. Процедура reset может применятся к одному и

тому же файлу несколько раз и при этом содержимое его не изме-

няется.

Если необходимо разделить копирование текущего элемента и

передвижение окна, используют стандартные процедуры с использо-

ванием буферной переменной. Она обозначается f_, где f — имя

файла. Тогда при чтении копируется значение елемента из окна

е:=f_ и окно сдвигается оператором процедуры get(f). При запи-

си сначала буферной переменной присваивается значение нового

элемента файла f_:=e и окно сдвигается оператором процедуры

put(f).

Работа с файлом может проходить либо в режиме записи, либо в

режиме чтения.Для определения конца файла в Pascal имеется

стандартная логическая функция eof (end of file).

Операция конкатенации двух файлов и отношение равенства над

файлами в Pascal не определены, но их достаточно просто реали-

зовать средствами языка.

2.4 _Списки

Использование только статических объектов при программирова-

нии может вызывать определенные трудности, так как не всегда

удается получить эффективную программу, а эффективность при ре-

шении многих задач является главным фактором. Иногда до работы

программы мы не знаем не только размера значения объекта, но и

даже того, будет ли он существовать или нет. Такого рода прог-

раммные объекты, которые возникают при выполнении программы или

размер которых изменяется во время выполнения программы, назы-

вают динамическими. Язык Pascal предусматривает возможность

составления эффективных программ с использованием динамических

объектов. При этом динамический объект не может иметь собствен-

ного имени, так как все идентификаторы должны быть описаны в

соответствующих разделах программы. Поэтому в Pascal принято не

именовать, а обозначать динамический объект и введен специаль-

ный ссылочный тип. Значением этого типа является ссылка на

программный объект, по которой осуществляется прямой доступ к

этому объекту. Динамический объект обозначается присоединением

символа _ к имени переменной-ссылки на этот объект:

type T = integer;{тип динамического объекта}

pointer = ^T;{имя ссылочного типа — pointer}

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

var p:pointer;

Значениями ссылочного типа являются значения адресов единиц

оперативной памяти конкретной машины. Значение NIL принадлежит

любому ссылочному типу. Оно указывает на отсутствие связи с

объектом. Сам динамический объект порождается с помощью стан-

дартной процедуры new, фактическим параметром которой является

ссылка на этот объект. Выполнение процедуры new(p) порождает

динамический объект типа Т, т.е. процедура new ищет в оператив-

ной памяти незадействованную до этого момента область памяти

подходящего размера и присваивает переменной-ссылке p значение

адреса начала этой области.

В языке Pascal также определена специальная процедура

dispose, уничтожающая динамический объект, т.е. высвобождающая

область памяти, зарезервированной под этот объект. Динамические

объекты размещающиеся на внешних носителях обычно имеют струк-

туру файла.

С помощью ссылочного типа можно создавать динамические

структуры самого разнообразного характера, например линейные

списки.

Структура данных, где каждый информационный элемент снабжает-

ся ссылкой на следующий за ним, называется связным списком. В

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

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

список как единый объект. Однонаправленный список из целых чи-

сел на Pascal можно организовать так:

type TValue = integer;

pointer = ^element;

element = record

info:TValue;

next:pointer;

end;

list = pointer;

где поле next — указатель на следующий элемент списка. Ука-

затель последнего элемента равен NIL. Однако при использовании

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

никнуть определенные трудности. По однонаправленному списку

можно двигаться только в одну сторону — от первого элемента к

последнему. Между тем нередко необходимо произвести обработку

элементов, предшествующих элементу с заданным свойством. Для

устранения этого неудобства в каждый элемент добавляется еще

одно поле prev — указатель на предшествующий элемент:

type pointer = ^element;

element = record

info:TValue;

prev:pointer;

next:pointer;

end;

dlist = pointer;

Динамическая структура состоящая из звеньев такого типа на-

зывается двунаправленным списком. Наличие ссылки на предыдущий

элемент списка позволяет двигаться в любом направлении по спис-

ку. В поле prev заглавного звена стоит ссылка NIL, так как у

заглавного звена нет предыдущего. Иногда значением поля next

последнего звена ставят ссылку на заглавное звено, а в поле

prev заглавного звена — ссылку на последнее звено. Список замы-

кается в «кольцо». Списки такого вида называют кольцевыми.

Списки также допускают отображение на массив, например одно-

направленный список допускает такое отображение:

type elem = record

info:TValue;

next:integer;

end;

list = array [1..10] of elem;

var L:list;

use,free:integer;

где поле next — указатель на расположение (индекс) следующе-

го элемента в массиве, а переменная use указывает на первый

элемент списка. Также используется список свободных элементов,

тоже связанных между собой. Переменная free указывает на первый

элемент списка свободных элементов. Отображение на массив явля-

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

ограничивается максимальным числом, т.е. размером массива. Сле-

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

Для удобной работы над списком определяются следующие базо-

вые операции:

Init(L) — создание списка.

Insert(L,n,v) — вставка элемента v в список под номером n.

Delete(n) — удаление n-го элемента списка или удаление эле-

мента по имени.

Print(L) — печать списка.

Find(L,v) — поиск элемента в списке.

Обработка элементов списка сводится к корректировке соот-

ветствующих ссылок. Списки также активно используются для орга-

низации еще более сложных структур данных, например очереди.

2.5 Оч _ередь

Очередь — упорядоченный, одномерный, динамически изменяемый

набор компонент, в котором включение новых компонент произво-

дится с одного конца очереди, а доступ и исключение с другого.

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

ляется динамическим объектом и длинна ее не фиксируется. Так

как в Pascal нет структурного типа очередь, его можно отобра-

зить на уже имеющиеся структуры: файл и массив. Отображение

очереди из целых чисел на массив можно реализовать так:

const N=10;

type Qel:integer;

Queue: record

first,last:integer;

body: array [1..N] of Qel;

end;

где first и last — указатели на первый и последний элемент

очереди соответственно, а N — максимальное число компонент оче-

реди. Отображение на массив накладывает ограничение на длину

очереди, кроме того программист сам запрещает себе прямой дос-

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

дующие процедуры:

Init(Q) — процедура создания очереди Q.

Empty(Q) — логическая функция, если очередь пуста Empty вы-

дает значение true, если нет — false.

Pop(Q) — процедура, выталкивающая первый элемент очереди Q.

Top(Q) — функция, выдающая значение первого элемента очереди.

Push(Q,v) — процедура, добавляющая новый элемент v типа Qel

в конец очереди Q.

Print(Q) — процедура, распечатывающая содержимое очереди.

Size(Q) — функция, выдающая число компонент (длину) очереди.

Отображение очереди на файл выглядит так:

type T = Qel;

Queue = file of T;

Операции над очередью определяются также как и при отображе-

нии на массив, а обработка элементов ведется с использованием

буферной переменной. При таком отображении время на операции

тратится больше, так как файл приходится все время «перематы-

вать».

На Pascal очередь может быть организована и как двунаправ-

ленный список:

type T = Qel;

pointer = ^T;

Queue = record

info:T;

pred,sled:pointer;

end;

где pred и sled — указатели на предыдущий и следующий эле-

мент очереди. Операции над очередью при такой организации опре-

деляются аналогично.

2.6 _Стек

Стек — структура данных, в которой можно добавлять и уда-

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

последний добавленный элемент. Как и очередь стек в Pascal мож-

но организовать в виде линейного списка:

type pointer = ^elem;

elem = record

info:TValue;

sled:pointer;

end;

Stask = pointer;

или отображения на массив:

const N=10;

type Stask = record

tp:integer;

body:array [1..N] of TValue;

end;

Для работы со стеком реализуются процедуры:

Init(S) — процедура создания стека S.

Empty(S) — логическая функция, выдающая true если стек пуст

и false если в нем есть элементы.

Push(S,v) — процедура вставляющая новый элемент v в стек.

Pop(S) — процедура выталкивающая верхний элемент из стека.

Top(S) — функция, возвращающая значение верхнего элемента

стека.

Size(S) — функция, возвращающая число элементов стека.

Display(S) — процедура, распечатывающая содержимое стека.

Имея эти базовые процедуры довольно просто реализовать про-

цедуры: вставки элемента в стек под каким-то номером

(Insert(S,v,n)) и удаления элемента из стека по значению

(Remove(S)). Надо заметить, что стек — одна из наиболее исполь-

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

решении различных задач.

2.7 _Дек

Deque (double-ended queue) — двухсторонняя очередь, структу-

ра данных, где элементы могут добавляться и удаляться с обоих

концов. Дек является и стеком и очередью одновременно. При реа-

лизации должны быть определены операции: вставка нового элемен-

та в начало дека, вставка нового элемента в конец дека, удале-

ние (или просмотр) элемента из начала дека, удаление элемента

из конца дека.

2.8 _Графы

Множество объектов соединенных произвольным образом, но не

более чем одной линией связи между двумя объектами — называется

графом.Связный граф — когда имеется путь между двумя вершинами,

ориентированный граф — в котором линии связи имеют определенное

направление.При использовании графов часто возникает проблема

поиска пути между двумя вершинами.

В Pascal удобно для этой цели представлять граф в виде мат-

рицы смежности, в которой хранится информация о связях между

вершинами графа.Если граф содержит N вершин, то матрица смеж-

ности — квадратная булевская матрица N*N, в которой

М(i,j)=true, если есть связь между i-ой и j-ой вершинами и

М(i,j)=false в противном случае. Для неориентированных графов

матрица смежности симметрична.

Граф с К вершинами можно также представить в виде К списков,

соответствующих вершинам и содержащих номера вершин с которыми

у данной есть связь.Если граф меняется в процессе обработки,

т.е. добавляются и удаляются вершины и линии связи, то удобнее

использовать списки.

Графы применяются в задачах машинного проектирования и в

создании систем искусственного интеллекта.

2.9 _Деревья

Дерево — частный случай графа.Структура определяется рекур-

сивно, образованная данным элементом, называемым корнем дерева,

и конечным списком с переменным числом элементов — деревьев то-

го же типа, называемых поддеревьями. Двоичным или бинарным де-

ревом называется дерево состоящее из корня, правого и левого

поддеревьев.

В Pascal двоичное дерево можно определить так:

type BTree = ^BNode;

BNode = record

info:TValue;

left,right:BTree;

end;

При анализе структур данных, заданных в виде дерева, приме-

няются различные способы просмотра и перебора узлов.Основная

особенность каждого обхода заключается в том, что просматрива-

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

обрабатывается ровно один раз.

Для бинарного дерева определены три способа обхода: прямой

или префиксный (корень — левое поддерево — правое поддере-

во), обратный или инфиксный (левое поддерево — корень — правое

поддерево) и концевой или постфиксный (левое поддерево — правое

поддерево — корень).

При обходе дерева используются рекурсивные процедуры или

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

на наличие поддеревьев (LTAG и RTAG). Введение дополнительных

указателей не приводит к большому увеличению затрат памяти, но

позволяет при обходе отказаться от стека.

Надо отметить, что любое дерево общего вида можно представить

в виде двоичного, надо в исходном дереве у каждого узла соеди-

нить его сыновей от старшего к младшему и убрать все связи узла

с сыновьями, оставив только связь со старшим сыном.

Над деревьями удобно определить операции: чтение информаци-

онной части из узла дерева, создание дерева, присоединение к

узлу нового поддерева, удаление поддерева.

Особенно полезны деревья при сортировке.Алгоритм состоит в

том, что при просмотре данных очередной элемент помещается в

двоичное дерево. Ключ нового элемента сравнивается с ключом те-

кущего узла.Если указатель текущего узла NIL, то указатель на

новый узел добавляется в то место откуда был извлечен NIL.Если

ключ нового узла меньше ключа текущего узла, то поиск места для

нового узла продолжается в левом поддереве, если больше — в

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

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

Деревья применяются также при интерпритации и вычислении

как арифметических, так и логических.

Теперь рассмотрим области применения сложных структур дан-

ных.Одной из таких областей является процесс создания компиля-

торов, который отработан достаточно хорошо.

Исходный текст разбивается на лексемы (идентификаторы, конс-

танты, знаки операций). Лексемы заносятся в таблицы, а в тексте

лексема заменяется ссылкой на элемент таблицы, таким образом

текст программы заменяется на последовательность лексем. Для

того, чтобы один и тот же идентификатор заменялся ссылкой на

один и тот же элемент таблицы, необходлимо для каждого анализи-

руемого идентификатора просматривать все встретившиеся ранее.

Для ускорения этого поиска применяются: упорядочение элементов

таблицы (сортировка) для дальнейшего бинарного поиска, хеш-ад-

ресация и некоторые другие способы.Для хранения последователь-

ности лексем используют массивы и списки.

Следующим этапом после замены текста программы на цепочку

лексем является синтаксический анализ, при котором широко ис-

пользуются стеки, таблицы и строки.

В операционных системах распространены такие сложные струк-

туры данных, как очереди. Операционная система вынуждена под-

держивать несколько очередей: очередь процессов готовых к вы-

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

(например к принтеру).

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

равления базами данных (СУБД). СУБД могут накапливать информа-

цию о большом числе объектов, описание которых содержат разные

сведения.

Свойства объектов могут выступать в роли ключей (например

фамилия служащего) и тогда по этим свойствам объекты могут быть

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

Для описания объектов обычно используют записи, которые в

свою очередь могут содержать ссылку на список из записей.

Наконец, еще одной областью применения являются задачи с ис-

пользованием разреженных матриц (с относительно небольшим чис-

лом ненулевых элементов).Иногда при нехватке оперативной памяти

бывает выгодно хранить только ненулевые элементы, применяя раз-

личные методы упаковки (в три массива, в один массив, с помощью

связного списка и т.д.).

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

шении используемых структур данных. Удачный выбор структуры

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

трудоемкость разработки и повышает надежность.

2.10 С П И С О К И С П О Л Ь З О В А Н Н Ы Х

И С Т О Ч Н И К О В

1. В.М.Брябрин. Программное обеспечение персональных

ЭВМ, М., «Наука», 1990.

2. Н.Вирт. Програмирование на языке Модула-2,

М., «Мир», 1987.

3. К.Кристиан. Введение в операционную систему UNIX,

М., «Финансы и статистика», 1985.

4. М.И.Беляков, Ю.И.Рабовер, А.Л.Фридман.

Мобильная операционная система, М.,«Радио и связь»,

1991.

5. Ф.Л.Бауэр, Г.Гооз, Информатика, т.2, М., «Мир»,

1990.

6. В.Г.Абрамов, Н.П.Трифонов, Г.Н.Трифонова,

Введение в язык паскаль, М., «Наука»,1988.

7. И.З.Луговая, Л.Н.Чернышов, С.М.Юдин,

Динамические структуры данных языка паскаль, М.,

издательство МАИ, 1988.

8. Л.Н.Чернышов, С.М.Юдин, Инструментальная система

ИНФОРТ и работа с динамическими структурами данных,

М., издательство МАИ, 1984.

9. Лекции, семинары, консультации по АЯП.

www.ronl.ru

Реферат - Алгоритмические языки и программирование

1. 2ВВЕДЕНИЕ

Цель курсовой работы - проверить знания студента по пройденному за второй семестр материалу. Студент должен владеть основами работы в операционной системе UNIX, знать ее основные команды и возможности, иметь представление об ЭВМ семейства VAX, архитектуре и основных принципах работы. Решая задачи курсовой работы, необходимо изучить различные методы сортировки, двоичный поиск, способы хранения разреженных матриц, организацию и работу с линейными списками. Цель оформления отчетов по курсовой работе - привить студентам навыки правильного оформления научно-технических отчетов, программной и технической документации в соответствии со стандартами.

2. Р Е Ф Е Р А Т "Алгоритмы и структуры данных языка Pascal"

2.1 Введение

Любая программа, выполняемая на ЭВМ, обрабатывает данные с целью получения требуемого результата. В современных языках программирования (Pascal,C,Modula-2,Ada) имеются базовые типы данных и средств построения структурных типов данных из базо- вых; они облегчают составление программ для решения сложных за- дач,однако не избавляют программиста от проблем разработки ал- горитмов и выбора подходящей структуры данных. При разработке алгоритма выбирается некоторая удобная абс- трактная структура данных и алгоритм разрабатывается в терминах операций над этим абстрактным типом данных. После разработки алгоритма выбирается представление абс- трактной структуры данных с помощью структуры данных языка программирования (отображение на массив, на файлы).Если задача позволяет,целесообразнее использовать более простые структуры данных.К таким традиционным структурам данных, допускающих простое и эффективное представление на ЭВМ, относятся массивы, строки, записи, стеки, списки, деревья, таблицы, графы, файлы. Очень часто язык содержит лишь некоторые из перечисленных структур, а остальные приходится представлять с помощью имею- щихся.Так в Pascal граф можно представить с помощью массива или списка, строку с помощью массива или списка. Теперь последовательно рассмотрим вышеперечисленные структу- ры данных и их представление через более прстые применимо к языку Pascal.

2.2 _Массив Переменная или константа, имеющая структуру массива, являет- ся совокупностью элементов одного и того же типа. Каждая от- дельная компонента массива может быть явно обозначена, доступ к ней может осуществлятся по одному или нескольким индексам.Число компонент массива определяется при его описании и во время ра- боты программы не меняется. В Pascal массив является стандарт- ным типом данных. Его объявление может иметь вид: type massiv = array [1..10,1..10] of integer; или packed array [1..10,1..10] of integer; var M:massiv; где М - массив размером 10*10 из целых чисел, а доступ к компонентам осуществляется по индексам i и j. Возможность дина- мического задания массива, как в Modula-2, в Pascal отсутству- ет. Количество компонент массива, их тип должны задаваться явно т.е. задаваться до начала работы программы. Массивы находят ши- рокое применение при решении многих задач, в том числе и для отображения более сложных структур данных.

2.3 _Последовательные файлы Слово "файл" в языке Pascal употребляется для объектов сос- тоящих из компонент одного и того же типа. В любой момент вре- мени непосредственно доступна (для чтения и записи) только одна компонента, другие становятся доступными по мере продвижения по файлу. Таким образом, чтобы прочитать элемент файла необходимо просмотреть все элементы стоящие до него. Такие файлы называют- ся файлами последовательного доступа или последовательными фай- лами. Длинна файла не фиксируется и может меняться в процессе выполнения программы. Файловый тип в Pascal - это единственный тип значений, пос- редством которого данные, обрабатываемые программой, могут быть получены извне, а результаты переданы во внешний мир. В Pascal файловый тип задается следующим образом: type T = TValue;{ тип компоненты файла }= file of T; или packed file of T; Как обычно, файловый тип может быть введен в употребление в разделе типов, как было описано выше, либо непосредственно за- дан при описании переменных, например: var myfile: file of T;

Файлы, имена которых включаются в список заголовка програм- мы, называются внешними файлами, они существуют вне программы. Если же имена файлов не внесены в список заголовка программы, то такие файлы существуют только во время выполнения программы и называются внутренними. Внутренние файлы носят в основном вспомогательный характер. Стандартный ввод осуществляется из файла input, а вывод в файл output. Для доступа к отдельным элементам файла в Pascal введены специальные процедуры. Оператор процедуры rewrite(f) устанавли- вает файл в режим записи, если раньше в этот файл были записаны какие-то данные, то они теряются. Оператор процедуры write(f,x) записывает в файл f очередную компоненту x, после чего окно сдвигается на следующую позицию. Если какой-то, компоненты которого уже записаны ранее, необ- ходимо прочитать,то для этого в Pascal используются стандартные процедуры reset и read. Оператор процедуры reset(f) переводит файл f в режим чтения и устанавливает окно на первую пози- цию файла. Оператор процедуры read(f,v) присваивает переменной v значение текущей компоненты из файла f и передвигает окно на следующую позицию. Процедура reset может применятся к одному и тому же файлу несколько раз и при этом содержимое его не изме- няется. Если необходимо разделить копирование текущего элемента и передвижение окна, используют стандартные процедуры с использо- ванием буферной переменной. Она обозначается f, где f - имя файла. Тогда при чтении копируется значение елемента из окна е:=f и окно сдвигается оператором процедуры get(f). При запи- си сначала буферной переменной присваивается значение нового элемента файла f:=e и окно сдвигается оператором процедуры put(f). Работа с файлом может проходить либо в режиме записи, либо в режиме чтения.Для определения конца файла в Pascal имеется стандартная логическая функция eof (end of file). Операция конкатенации двух файлов и отношение равенства над файлами в Pascal не определены, но их достаточно просто реали- зовать средствами языка.

2.4 _Списки Использование только статических объектов при программирова- нии может вызывать определенные трудности, так как не всегда удается получить эффективную программу, а эффективность при ре- шении многих задач является главным фактором. Иногда до работы программы мы не знаем не только размера значения объекта, но и даже того, будет ли он существовать или нет. Такого рода прог- раммные объекты, которые возникают при выполнении программы или размер которых изменяется во время выполнения программы, назы- вают динамическими. Язык Pascal предусматривает возможность составления эффективных программ с использованием динамических объектов. При этом динамический объект не может иметь собствен- ного имени, так как все идентификаторы должны быть описаны в соответствующих разделах программы. Поэтому в Pascal принято не именовать, а обозначать динамический объект и введен специаль- ный ссылочный тип. Значением этого типа является ссылка на программный объект, по которой осуществляется прямой доступ к этому объекту. Динамический объект обозначается присоединением символа к имени переменной-ссылки на этот объект: type T = integer;{тип динамического объекта} pointer = ^T;{имя ссылочного типа - pointer} Переменная-ссылка должна быть описана в разделе var: var p:pointer; Значениями ссылочного типа являются значения адресов единиц оперативной памяти конкретной машины. Значение NIL принадлежит любому ссылочному типу. Оно указывает на отсутствие связи с объектом. Сам динамический объект порождается с помощью стан- дартной процедуры new, фактическим параметром которой является ссылка на этот объект. Выполнение процедуры new(p) порождает динамический объект типа Т, т.е. процедура new ищет в оператив- ной памяти незадействованную до этого момента область памяти подходящего размера и присваивает переменной-ссылке p значение адреса начала этой области. В языке Pascal также определена специальная процедура dispose, уничтожающая динамический объект, т.е. высвобождающая область памяти, зарезервированной под этот объект. Динамические объекты размещающиеся на внешних носителях обычно имеют струк- туру файла. С помощью ссылочного типа можно создавать динамические структуры самого разнообразного характера, например линейные списки. Структура данных,где каждый информационный элемент снабжает- ся ссылкой на следующий за ним,называется связным списком. В списке предусмотрено заглавное звено. Указатель списка, значе- нием которого является ссылка на заглавное звено, представляет список как единый объект. Однонаправленный список из целых чи- сел на Pascal можно организовать так: type TValue = integer; pointer = ^element; element = record info:TValue; next:pointer; end; list = pointer; где поле next - указатель на следующий элемент списка. Ука- затель последнего элемента равен NIL. Однако при использовании однонаправленных списков для решения некоторых задач могут воз- никнуть определенные трудности. По однонаправленному списку можно двигаться только в одну сторону - от первого элемента к последнему. Между тем нередко необходимо произвести обработку элементов, предшествующих элементу с заданным свойством. Для устранения этого неудобства в каждый элемент добавляется еще одно поле prev - указатель на предшествующий элемент: type pointer = ^element; element = record info:TValue; prev:pointer; next:pointer; end; dlist = pointer; Динамическая структура состоящая из звеньев такого типа на- зывается двунаправленным списком. Наличие ссылки на предыдущий элемент списка позволяет двигаться в любом направлении по спис- ку. В поле prev заглавного звена стоит ссылка NIL, так как у заглавного звена нет предыдущего. Иногда значением поля next последнего звена ставят ссылку на заглавное звено, а в поле prev заглавного звена - ссылку на последнее звено. Список замы- кается в "кольцо". Списки такого вида называют кольцевыми. Списки также допускают отображение на массив, например одно- направленный список допускает такое отображение: type elem = record info:TValue; next:integer; end; list = array [1..10] of elem; var L:list; use,free:integer; где поле next - указатель на расположение (индекс) следующе- го элемента в массиве, а переменная use указывает на первый элемент списка. Также используется список свободных элементов, тоже связанных между собой. Переменная free указывает на первый элемент списка свободных элементов. Отображение на массив явля- ется менее удачным, так как количество элементов списка заранее ограничивается максимальным числом, т.е. размером массива. Сле- довательно список перестает быть динамической структурой. Для удобной работы над списком определяются следующие базо- вые операции:

Init(L) - создание списка. Insert(L,n,v) - вставка элемента v в список под номером n. Delete(n) - удаление n-го элемента списка или удаление эле- мента по имени. Print(L) - печать списка. Find(L,v) - поиск элемента в списке.

Обработка элементов списка сводится к корректировке соот- ветствующих ссылок. Списки также активно используются для орга- низации еще более сложных структур данных, например очереди.

2.5 Оч _ередь Очередь - упорядоченный, одномерный, динамически изменяемый набор компонент, в котором включение новых компонент произво- дится с одного конца очереди, а доступ и исключение с другого. Длинной очереди называется количество ее компонент. Очередь яв- ляется динамическим объектом и длинна ее не фиксируется. Так как в Pascal нет структурного типа очередь, его можно отобра- зить на уже имеющиеся структуры: файл и массив. Отображение очереди из целых чисел на массив можно реализовать так: const N=10; type Qel:integer; Queue: record first,last:integer; body: array [1..N] of Qel; end; где first и last - указатели на первый и последний элемент очереди соответственно, а N - максимальное число компонент оче- реди. Отображение на массив накладывает ограничение на длину очереди, кроме того программист сам запрещает себе прямой дос- туп к элементам массива. Для работы с очередью реализуются сле- дующие процедуры:

Init(Q) - процедура создания очереди Q. Empty(Q) - логическая функция, если очередь пуста Empty вы- дает значение true, если нет - false. Pop(Q) - процедура, выталкивающая первый элемент очереди Q. Top(Q) - функция, выдающая значение первого элемента очереди. Push(Q,v) - процедура, добавляющая новый элемент v типа Qel в конец очереди Q. Print(Q) - процедура, распечатывающая содержимое очереди. Size(Q) - функция, выдающая число компонент (длину) очереди.

Отображение очереди на файл выглядит так: type T = Qel; Queue = file of T; Операции над очередью определяются также как и при отображе- нии на массив, а обработка элементов ведется с использованием буферной переменной. При таком отображении время на операции тратится больше, так как файл приходится все время "перематы- вать". На Pascal очередь может быть организована и как двунаправ- ленный список: type T = Qel; pointer = ^T; Queue = record info:T; pred,sled:pointer; end; где pred и sled - указатели на предыдущий и следующий эле- мент очереди. Операции над очередью при такой организации опре- деляются аналогично.

2.6 _Стек Стек - структура данных, в которой можно добавлять и уда- лять элементы данных, при этом непосредственно доступен только последний добавленный элемент. Как и очередь стек в Pascal мож- но организовать в виде линейного списка: type pointer = ^elem; elem = record info:TValue; sled:pointer; end; Stask = pointer; или отображения на массив: const N=10; type Stask = record tp:integer; body:array [1..N] of TValue; end; Для работы со стеком реализуются процедуры:

Init(S) - процедура создания стека S. Empty(S) - логическая функция, выдающая true если стек пуст и false если в нем есть элементы. Push(S,v) - процедура вставляющая новый элемент v в стек. Pop(S) - процедура выталкивающая верхний элемент из стека. Top(S) - функция, возвращающая значение верхнего элемента стека. Size(S) - функция,возвращающая число элементов стека. Display(S) - процедура, распечатывающая содержимое стека.

Имея эти базовые процедуры довольно просто реализовать про- цедуры: вставки элемента в стек под каким-то номером (Insert(S,v,n)) и удаления элемента из стека по значению (Remove(S)). Надо заметить, что стек - одна из наиболее исполь- зуемых структур данных, которая оказывается весьма удобной при решении различных задач.

2.7 _Дек Deque (double-ended queue) - двухсторонняя очередь, структу- ра данных, где элементы могут добавляться и удаляться с обоих концов. Дек является и стеком и очередью одновременно. При реа- лизации должны быть определены операции: вставка нового элемен- та в начало дека, вставка нового элемента в конец дека, удале- ние (или просмотр) элемента из начала дека, удаление элемента из конца дека.

2.8 _Графы Множество объектов соединенных произвольным образом, но не более чем одной линией связи между двумя объектами - называется графом.Связный граф - когда имеется путь между двумя вершинами, ориентированный граф - в котором линии связи имеют определенное направление.При использовании графов часто возникает проблема поиска пути между двумя вершинами. В Pascal удобно для этой цели представлять граф в виде мат- рицы смежности, в которой хранится информация о связях между вершинами графа.Если граф содержит N вершин, то матрица смеж- ности - квадратная булевская матрица N*N, в которой М(i,j)=true, если есть связь между i-ой и j-ой вершинами и М(i,j)=false в противном случае. Для неориентированных графов матрица смежности симметрична. Граф с К вершинами можно также представить в виде К списков, соответствующих вершинам и содержащих номера вершин с которыми у данной есть связь.Если граф меняется в процессе обработки, т.е. добавляются и удаляются вершины и линии связи, то удобнее использовать списки. Графы применяются в задачах машинного проектирования и в создании систем искусственного интеллекта.

2.9 _Деревья Дерево - частный случай графа.Структура определяется рекур- сивно,образованная данным элементом, называемым корнем дерева, и конечным списком с переменным числом элементов - деревьев то- го же типа, называемых поддеревьями. Двоичным или бинарным де- ревом называется дерево состоящее из корня, правого и левого поддеревьев. В Pascal двоичное дерево можно определить так: type BTree = ^BNode; BNode = record info:TValue; left,right:BTree; end; При анализе структур данных, заданных в виде дерева, приме- няются различные способы просмотра и перебора узлов.Основная особенность каждого обхода заключается в том, что просматрива- ются все узлы дерева в некотором порядке, причем каждый узел обрабатывается ровно один раз. Для бинарного дерева определены три способа обхода: прямой или префиксный (корень - левое поддерево - правое поддере- во),обратный или инфиксный (левое поддерево - корень - правое поддерево) и концевой или постфиксный (левое поддерево - правое поддерево - корень). При обходе дерева используются рекурсивные процедуры или стек.В прошитых деревьях используются дополнительные указатели на наличие поддеревьев (LTAG и RTAG). Введение дополнительных указателей не приводит к большому увеличению затрат памяти, но позволяет при обходе отказаться от стека. Надо отметить,что любое дерево общего вида можно представить в виде двоичного, надо в исходном дереве у каждого узла соеди- нить его сыновей от старшего к младшему и убрать все связи узла с сыновьями, оставив только связь со старшим сыном. Над деревьями удобно определить операции: чтение информаци- онной части из узла дерева, создание дерева, присоединение к узлу нового поддерева, удаление поддерева. Особенно полезны деревья при сортировке.Алгоритм состоит в том, что при просмотре данных очередной элемент помещается в двоичное дерево. Ключ нового элемента сравнивается с ключом те- кущего узла.Если указатель текущего узла NIL, то указатель на новый узел добавляется в то место откуда был извлечен NIL.Если ключ нового узла меньше ключа текущего узла, то поиск места для нового узла продолжается в левом поддереве, если больше - в правом.После того как все данные занесены в двоичное дерево сортировки, выполняется обратный обход дерева с выводом. Деревья применяются также при интерпритации и вычислении как арифметических, так и логических.

Теперь рассмотрим области применения сложных структур дан- ных.Одной из таких областей является процесс создания компиля- торов, который отработан достаточно хорошо. Исходный текст разбивается на лексемы (идентификаторы, конс- танты, знаки операций). Лексемы заносятся в таблицы, а в тексте лексема заменяется ссылкой на элемент таблицы, таким образом текст программы заменяется на последовательность лексем. Для того, чтобы один и тот же идентификатор заменялся ссылкой на один и тот же элемент таблицы, необходлимо для каждого анализи- руемого идентификатора просматривать все встретившиеся ранее. Для ускорения этого поиска применяются: упорядочение элементов таблицы (сортировка) для дальнейшего бинарного поиска, хеш-ад- ресация и некоторые другие способы.Для хранения последователь- ности лексем используют массивы и списки. Следующим этапом после замены текста программы на цепочку лексем является синтаксический анализ, при котором широко ис- пользуются стеки, таблицы и строки. В операционных системах распространены такие сложные струк- туры данных, как очереди. Операционная система вынуждена под- держивать несколько очередей: очередь процессов готовых к вы- полнению, очередь на свопинг на диск и очереди к устройствам (например к принтеру). Сложные структуры данных используются также в системах уп- равления базами данных (СУБД). СУБД могут накапливать информа- цию о большом числе объектов, описание которых содержат разные сведения. Свойства объектов могут выступать в роли ключей (например фамилия служащего) и тогда по этим свойствам объекты могут быть отсортированы, что значительно убыстряет поиск. Для описания объектов обычно используют записи, которые в свою очередь могут содержать ссылку на список из записей. Наконец,еще одной областью применения являются задачи с ис- пользованием разреженных матриц (с относительно небольшим чис- лом ненулевых элементов).Иногда при нехватке оперативной памяти бывает выгодно хранить только ненулевые элементы, применяя раз- личные методы упаковки (в три массива, в один массив, с помощью связного списка и т.д.). Язык Pascal предоставляет весьма гибкие возможности в отно- шении используемых структур данных. Удачный выбор структуры данных влияет на простоту алгоритма, и следовательно уменьшает трудоемкость разработки и повышает надежность.

2.10 С П И С О К И С П О Л Ь З О В А Н Н Ы Х И С Т О Ч Н И К О В

1. В.М.Брябрин. Программное обеспечение персональных ЭВМ, М., "Наука", 1990.

2. Н.Вирт. Програмирование на языке Модула-2, М., "Мир", 1987.

3. К.Кристиан. Введение в операционную систему UNIX, М., "Финансы и статистика", 1985.

4. М.И.Беляков, Ю.И.Рабовер, А.Л.Фридман. Мобильная операционная система,М.,"Радио и связь", 1991.

5. Ф.Л.Бауэр, Г.Гооз, Информатика, т.2, М., "Мир", 1990.

6. В.Г.Абрамов, Н.П.Трифонов, Г.Н.Трифонова, Введение в язык паскаль,М., "Наука",1988.

7. И.З.Луговая, Л.Н.Чернышов, С.М.Юдин, Динамические структуры данных языка паскаль, М., издательство МАИ, 1988.

8. Л.Н.Чернышов, С.М.Юдин, Инструментальная система ИНФОРТ и работа с динамическими структурами данных, М., издательство МАИ, 1984.

9. Лекции, семинары, консультации по АЯП.

www.ronl.ru


Смотрите также