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

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

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

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

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

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

по курсу

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

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) - поиск элемента в списке.

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

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

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