Московский авиационный институт
(технический университет)
------------------------
Кафедра вычислительной математики и программирования
К У Р С О В А Я Р А Б О Т А
по курсу
"Алгоритмические языки и программирование"
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. Однако при использовании
однонаправленных списков для решения некоторых задач могут воз-