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

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

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

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

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

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

по курсу

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

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. Лекции, семинары, консультации по АЯП.