рефераты
Главная

Рефераты по рекламе

Рефераты по физике

Рефераты по философии

Рефераты по финансам

Рефераты по химии

Рефераты по хозяйственному праву

Рефераты по цифровым устройствам

Рефераты по экологическому праву

Рефераты по экономико-математическому моделированию

Рефераты по экономической географии

Рефераты по экономической теории

Рефераты по этике

Рефераты по юриспруденции

Рефераты по языковедению

Рефераты по юридическим наукам

Рефераты по истории

Рефераты по компьютерным наукам

Рефераты по медицинским наукам

Рефераты по финансовым наукам

Рефераты по управленческим наукам

Психология и педагогика

Промышленность производство

Биология и химия

Языкознание филология

Издательское дело и полиграфия

Рефераты по краеведению и этнографии

Рефераты по религии и мифологии

Рефераты по медицине

Рефераты по сексологии

Рефераты по информатике программированию

Краткое содержание произведений

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

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

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

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

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

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

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

                          по курсу

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

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


© 2012 Рефераты, курсовые и дипломные работы.