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

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

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


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


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


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


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


по курсу


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


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

Сохранить в соц. сетях:
Обсуждение:
comments powered by Disqus

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

Слов:3450
Символов:28166
Размер:55.01 Кб.