Алгоритмические языки и программирование
Цель курсовой работы - проверить знания студента по
пройденному за второй семестр материалу. Студент должен владеть
основами работы в операционной системе 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. Лекции, семинары, консультации по АЯП.