Федеральне агентство з освіти
Федеральне державна установа вищої професійної освіти
Кафедра обчислювальної математики та інформаційних технологій
Курсова робота
З дисципліни
Структури і алгоритми комп'ютерної обробки даних
2009р.
Введення
Метою курсової роботи стала задача проектування багатофункціональної структури комп'ютерної обробки даних. Розгляд та розробка програм з такими операціями як: знайти розстановку п'яти ферзів, при якій кожне поле шахової дошки буде знаходиться під ударом хоча одного з них, досліджувати залежність кількості порівнянь в методі Шелла від вибору різних формул для обчислення кроку, в Trie-дереві визначити кількість слів, що містять букву А, обробка текстових даних, що зберігаються в довільному файлі на магнітному диску. Виконання тестування програм для нормальних, граничних та виключних умов. А так ж завдання і алгоритми обробки великих масивів дійсних і натуральних чисел.
Глава 1. Завдання і алгоритми обробки великих масивів дійсних і натуральних чисел
1.1 ОБМЕЖЕНІ ТИПИ
Часто доводиться стикатися з положенням, коли змінної привласнюється значення деякого типу, що лежить тільки усередині певного інтервалу значень. Таке положення можна підкреслити, визначивши, що вказана змінна відноситься до обмеженому типу. Такий тип задається наступним чином
TYPE T = [min .. max]
де min і max-вирази, що визначають кінці такого діапазону. Відзначимо, що операндами цих виразів можуть бути тільки константи.
ПРИКЛАДИ
TYPHyear = [1900 "1999]
TYPE digit = ["0" .. "9"]
Однак в легальності подібних присвоювання можна упевнитися без виконання програми лише в тих випадках, коли мова йде про присвоєнні констант.
1.2 МАСИВ
Ймовірно, найбільш широко відома структура даних - масив. У деяких мовах тільки масиви і існують. Масив складається з компонент, причому всі вони одного типу, званого базовим. Тому структура масивів однорідна. Крім того, масиви відносять до так званих структурам з випадковим доступом. Для того щоб позначити окрему компоненту, до імені всього масиву додається індекс, він-то і виділяє потрібну компоненту. Індекс - це значення спеціального типу, визначеного як тип індексу даного масиву.
TYPE T = ARRAY [TI] OF T0
З допомогою індексу можна виділити будь-яку окрему компоненту будь-якого масиву. Якщо є змінна-масив х, то селектор для масиву позначається за допомогою імені відповідного масиву, за яким слідує необхідний індекс i необхідної компоненти - xi або x [i]. Через традиційності першого, звичайного позначення компоненти масивів стали називати змінними з індексами.
Звичайний прийом роботи з масивами, особливо з великими масивами, - вибіркове зміна окремих його компонент, а не конструювання повністю нового складеного значення. При цьому змінна-масив розглядається як масив складових змінних і можливо присвоювання окремих компонентів, наприклад, x [i, j]: = 0.125. Хоча вибіркове зміна приводить тільки до корекції одній-єдиній компоненти, з концептуальної точки зору ми повинні розглядати його як зміна всього складеного значення. Отриманий результат може виявитися за межами інтервалу, виділеного для індексів даного масиву. Ми будемо припускати, що В«ПоряднаВ» обчислювальна система в разі помилкового звернення до неіснуючої компоненті масиву повинна давати деякий попереджувала повідомлення.
Складові масивів самі можуть бути складовими значеннями. Змінна-масив, компоненти якою знову ж масиви, називається матрицею. Наприклад,
М: ARRAY [1 .. 1O] OF Row
це масив, що складається з десяти компонент (рядків), кожна з яких складається з п'яти компонент типу REAL, і називається матрицею розміром 10X5 з речовими складовими.
Якщо необхідно виконати деяку операцію треба всіма компонентами масиву або над сусідніми компонентами деякої секції масиву, то для цього зручно скористатися оператором циклу. У наведеному прикладі обчислюється сума елементів і відшукується максимальний елемент масиву.
1.3 ПРЕДСТАВЛЕННЯ масиву
Сенс використання в програмуванні абстрактних понять полягає в тому, що програму можна побудувати, зрозуміти і перевірити, грунтуючись на законах, керуючих саме цими поняттями.
Будь представлення структури масиву полягає у відображенні масиву (Абстрактного) з компонентами типу Т на пам'ять, яка являє собою масив з компонентами типу WORD.
Треба враховувати наступні міркування:
1. Вирівнювання зменшує використовувану пам'ять.
2. Відмова від вирівнювання може призвести до необхідності використання доступу до частини слова.
3. Організація доступу до частини слова може на стільки збільшити розмір відтранслювати програми, що виграшу через відмову від вирівнювання не буде.
В більшості мов програмування програміст не має можливості управляти поданням абстрактних даних.
масив файл алгоритм обробка
1.4 ПОСЛІДОВНОСТІ
Масиви - Це гнучка структура даних. Розмір масиву може бути дуже великий і не уміщатися в пам'яті комп'ютера, в цих випадках дані зберігаються на магнітних носіях. Такі масиви розміри, яких дуже великі, прийнято називати послідовностями. Послідовних тип можна було б описати наступним чином:
TYPE T = SEQUENCE OF T o
Вже з опису ясно, що всі елементи послідовності мають один і той же тип. Послідовність s з п елементів ми будемо позначати s = 0 , s 1 , s 2 , ..., s n -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);
END FileSystem.
Зверніть увагу, що в цьому прикладі максимальна досяжна довжина послідовності - довільна константа. Якщо в якій-небудь програмі трапиться, що послідовність стане довшим, то це буде розглядатися не як помилка в програмі, а скоріше як неадекватна реаліз...
