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

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

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

    Кафедра вычислительной математики и программирования
              К У Р С О В А Я    Р А Б О Т А

                          по курсу

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