Федеральное агентство по образованию
Федеральное государственное учреждение высшего профессионального образования
Кафедра вычислительной математики и информационных технологий
По дисциплине
Структуры и алгоритмы компьютерной обработки данных
2009г.
Введение
Целью курсовой работы стала задача проектирования многофункциональной структуры компьютерной обработки данных. Рассмотрение и разработка программ с такими операциями как: найти расстановку пяти ферзей, при которой каждое поле шахматной доски будет находится под ударом хотя одного из них, исследовать зависимость количества сравнений в методе Шелла от выбора разных формул для вычисления шага, в Trie-дереве определить количество слов, содержащих букву А, обработка текстовых данных, хранящихся в произвольном файле на магнитном диске. Выполнение тестирования программ для нормальных, граничных и исключительных условий. А так же задачи и алгоритмы обработки большихмассивов действительных и натуральных чисел.
Глава 1. Задачи и алгоритмы обработки больших массивов действительных и натуральных чисел
1.1 ОГРАНИЧЕННЫЕ ТИПЫ
Часто приходится сталкиваться с положением, когда переменной присваивается значение некоторого типа, лежащее только внутри определенного интервала значений. Такое положение можно подчеркнуть, определив, что указанная переменная относится к ограниченному типу. Такой тип задается следующим образом
TYPET = [min..max]
где min и max —выражения, определяющие концы такого диапазона. Отметим, что операндами этих выражений могут быть только константы.
ПРИМЕРЫ
TYPHyear = [1900 „ 1999]
TYPEdigit =["0".."9"]
Однако в легальности подобных присваиваний можно удостовериться без выполнения программы лишь в тех случаях, когда речь идет о присваивании констант.
1.2 МАССИВ
Вероятно, наиболее широко известная структура данных — массив. В некоторых языках только массивы и существуют. Массив состоит из компонент, причем все они одного типа, называемого базовым. Поэтому структура массивов однородна. Кроме того, массивы относят к так называемым структурам со случайным доступом. Для того чтобы обозначить отдельную компоненту, к имени всего массива добавляется индекс, он-то и выделяет нужную компоненту. Индекс — это значение специального типа, определенного как тип индекса данного массива.
TYPE T = ARRAY[TI]OF T0
С помощью индекса можно выделить любую отдельную компоненту любого массива. Если есть переменная-массив х, то селектор для массива обозначается с помощью имени соответствующего массива, за которым следует необходимый индекс i требуемой компоненты — xi или x[i]. Из-за традиционности первого, обычного обозначения компоненты массивов стали называть переменными с индексами.
Обычный прием работы с массивами, в особенности с большими массивами, — выборочное изменение отдельных его компонент, а не конструирование полностью нового составного значения. При этом переменная-массив рассматривается как массив составляющих переменных и возможно присваивание отдельным компонентам, например, x[i,j ]:= 0.125. Хотя выборочное изменение приводит только к коррекции одной-единственной компоненты, с концептуальной точки зрения мы должны рассматривать его как изменение всего составного значения. Полученный результат может оказаться за пределами интервала, выделенного для индексов данного массива. Мы будем предполагать, что «порядочная» вычислительная система в случае ошибочного обращения к несуществующей компоненте массива должна давать некоторое предупреждающее сообщение.
Составляющие массивов сами могут быть составными значениями. Переменная-массив, компоненты которой опять же массивы, называется матрицей. Например,
М: ARRAY[1..1O] OFRow
это массив, состоящий из десяти компонент (строк), каждая из которых состоит из пяти компонент типа REAL, и называется матрицей размером 10X5 с вещественными составляющими.
Если необходимо выполнить некоторую операцию надо всеми компонентами массива или над соседними компонентами некоторой секции массива, то для этого удобно воспользоваться оператором цикла. В приведенном примере вычисляется сумма элементов и отыскивается максимальный элемент массива.
1.3 ПРЕДСТАВЛЕНИЕ МАССИВОВ
Смысл использования в программировании абстрактных понятий заключается в том, что программу можно построить, понять и проверить, основываясь на законах, управляющих именно этими понятиями.
Любое представление структуры массива заключается в отображении массива (абстрактного) с компонентами типа Т на память, которая представляет собой массив с компонентами типа WORD.
Надо учитывать следующие соображения:
1.Выравнивание уменьшает используемую память.
2.Отказ от выравнивания может привести к необходимости использования доступа к части слова.
3.Организация доступа к части слова может на столько увеличить размер оттранслированной программы, что выигрыша из-за отказа от выравнивания не будет.
В большинстве языков программирования программист не имеет возможности управлять представлением абстрактных данных.
массив файл алгоритм обработка
1.4 ПОСЛЕДОВАТЕЛЬНОСТИ
Массивы - это гибкая структура данных. Размер массива может быть очень велик и не умещаться в памяти компьютера, в этих случаях данные хранятся на магнитных носителях. Такие массивы размеры, которых очень велики, принято называть последовательностями. Последовательностный тип можно было бы описать следующим образом:
TYPET = SEQUENCEOFTo
Уже из описания ясно, что все элементы последовательности имеют один и тот же тип. Последовательность s из п элементов мы будем обозначать s= <s0, s1,s2, ..., sn-1>, причем N называется длиной последовательности. Прямое следствие бесконечности мощности последовательностного типа — невозможность выделить для соответствующей переменной память заданного размера. Вместо этого мы должны выделять память в процессе выполнения программы по мере роста последовательности. Если же последовательность уменьшается, то память можно и возвращать. В любом случае следует пользоваться некой схемой динамического распределения. Последовательности по существу присутствуют во всех приложениях вычислительных машин, они как бы вездесущи. Данные такой структуры превалируют во всех тех случаях, когда идет работа с памятями разного вида, т. е. когда данные передаются из внешней памяти, скажем дисков или лент, в оперативную, главную память и обратно.
Преимущество такой приверженности последовательному доступу, который, как бы то ни было, представляет собой серьезное ограничение, заключается в относительной простоте требуемого механизма управления памятью. Но еще более важной, если речь идет об обменах данными со вторичной памятью, выглядит возможность пользоваться эффективной техникой буферизации. Последовательный доступ позволяет нам для «перекачки» данных между памятями различного вида использовать непрерывные потоки данных. Буферизация предполагает, что части потока накапливаются в так называемых буферах, а затем, уже при заполнении всего буфера, передаются куда нужно. В результате, что особенно важно, более эффективно используется вторичная память.
Нижеприведенная часть программы показывает как обычно реализуется последовательность
DEFINITION MODULE FileSystem;
FROM SYSTEM IMPORT WORD;
CONST MaxLength = 4096:
TYPE Sequence = RECORD pos, length: CARDINAL;
eof: BOOLEAN;
a: ARRAY [0 „ Maхength-1 OF WORD
END;
PROCEDURE Open(VARf; Sequence):
PROCEDURE WriteWord(VAR f: Sequence; w; WORD)!
PROCEDURE Reset(VAR f:Sequence);
PROCEDURE ReadWord(VAR f: Sequence; VAR W; WORD);
PROCEDURE Close(VAR f: Sequence);
ENDFileSystem.
Обратите внимание, что в этом примере максимальная достижимая длина последовательности — произвольная константа. Если в какой-либо программе случится, что последовательность станет длиннее, то это будет рассматриваться не как ошибка в программе, а скорее как неадекватная реализация. С другой стороны, операция чтения за фактическим текущим концом последовательности действительно должна считаться ошибкой в программе.
1.5 СОРТИРОВКА ПОСЛЕДОВАТЕЛЬНОСТЕЙ
Прямое слияние
К сожалению, алгоритмы сортировки, приведенные в предыдущем разделе, невозможно применять для данных, которые из-за своего размера не помещаются в оперативной памяти машины и находятся, например, на внешних, последовательных запоминающих устройствах памяти, таких, как ленты или диски.
В таком случае мы говорим, что данные представляют собой (последовательный) файл.. Наиболее важный из них — сортировка с помощью слияния. Слияние означает объединение двух (или более) последовательностей в одну-единственную упорядоченную последовательность с помощью повторяющегося выбора из доступных в данный момент элементов. Слияние намного проще сортировки, и его используют как вспомогательную операцию в более сложных процессах сортировки последовательностей. Одна из сортировок на основе слияния называется простым, слиянием. Она выполняется следующим образом:
1. Последовательность а разбивается на две половины: bи с.
2. Части bи с сливаются, при этом одиночные элементы образуют упорядоченные пары.
3. Полученная последовательность под именем о вновь обрабатывается как указано в пунктах 1, 2;при этом упорядоченные пары переходят в такие же четверки.
4. Повторяя предыдущие шаги, сливаем четверки в восьмерки и т. д., каждый раз «удваивая» длинуслитых подпоследовательностей до тех пор, пока не будет упорядочена целиком вся последовательность.
Действия по однократной обработке всего множества данных называются фазой. Наименьший же подпроцесс, повторение которого составляет процесс сортировки, называется проходом или этапом.
Теперь перейдем к более детальному рассмотрению программы слияния. Данные мы будем представлять как массив, обращение к элементам которого, однако, идет строго последовательно. Если рассматривать массив как последовательность элементов, имеющих два конца, то его весьма просто можно использовать вместо двух последовательностей. Мы будем при слиянии брать элементы с двух концов массива, а не из двух входных файлов.Направление пересылки сливаемых элементов изменяется на первом проходе после каждой упорядоченной пары, на втором — после каждой упорядоченной четверки и т. д., равномерно заполняя две выходные последовательности, представляемые двумя концами одного массива. После каждого прохода массивы «меняются ролями», выходной становится входным и наоборот.