Міністерство освіти і науки України

     Черкаський  державний університет ім. Б. Хмельницького 
 
 

     кафедра ... 
 
 
 
 

     СКЛАДНІ СТРУКТУРИ ДАНИХ  В ПАСКАЛІ.

     ЗАПИСи 
 

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

Виконала

студентка ...

Керівник

...... 
 
 
 

     Черкаси 2003

 

ЗМІСТ 

 

      ВСТУП

     Мова  Паскаль відноситься до парадигми  структурного програмування. Це значить, що поняття «структура» входить у програму не тільки на рівні загальної її побудови, але і передбачає структурування самої логіки й даних якими оперує мова програмування. Перш за все, даний принцип знайшов своє застосування в типізації мови, тобто наділенні її жорсткою системою визначених типів, комбінуючи які кваліфікований програміст може створювати свої власні типи, причому вже не тільки прості (атомарні), але і складні конструкції, які представляють собою – структури даних.

     Це  дуже важливо, оскільки моделювання  різноманітних реальних процесів являє собою одну з основних областей застосування ЕОМ. Моделювання завжди приводить до абстракції, тобто до спрощеного (чи узагальненого) представлення об'єктів, їх властивостей і відносин в залежності від поставленої задачі. Деякі такі абстрактні об'єкти через свої корисні якості стали надзвичайно «популярними». Вони одержали точну специфікацію і з тих пір стали називатися абстрактними типами даних (або АТД). Однак абстракція за своїм означенням має за свою першочергову мету абстрагування від багатьох несуттєвих факторів, у тому числі і від того, як цей абстрактний об'єкт представити в ЕОМ. Цим власне і зайнялися мови програмування, що, по суті, є деякою проміжною ланкою між ідеями людини і можливостями машини. Саме тут і отримали значне поширення вищезгадані структури даних.

 

     РОЗДІЛ 1. ОГЛЯД СТРУКТУРНИХ  ТИПІВ В ПАСКАЛІ

     По  способі організації і типу компонент  виділяють чотири основні різновиди  структурованих типів:

• регулярний тип (масиви);
• файловий тип (файли);
• динамічні структури (множини)
• комбінований тип (запису).

    Розглянемо  коротко кожний різновид структурованих типів з метою встановлення головних відмінностей їх від записів. [13, c. 82]

     1.1 Масив

     Масив – це одно- чи багатомірна таблиця  даних одного типу. Кожен елемент  таблиці має свій індекс (в одномірному випадку) чи набір індексів (у багатомірному).

     Масив називають структурою даних з  випадковим доступом, оскільки до будь-якого  елемента масиву можна звернутися, просто вказавши його індекси, тобто  всі елементи однаково доступні в  будь-який момент часу. Масив визначається, перш за все, загальним типом його елементів та їх кількістю. Кількість елементів масиву, в свою чергу, визначається кількістю індексів і діапазоном їхньої змінюваності. Під час опису змінної типу масив під кожний елемент виділяється фіксований обсяг пам'яті, що і є головним недоліком цієї структури з двох причин:

     - по-перше, тому що в деяких  системах програмування в Паскалі  під змінну виділяється обмежена  кількість пам'яті, що не дозволяє  використовувати масиви великих  розмірів;

     - по-друге, тому що така організація  не дає можливості змінювати  розмір масиву, що приводить до  деяких незручностей, коли доводиться  марно копіювати великі обсяги  пам'яті, наприклад, при передачі  параметра-масиву підпрограмі. 

     1.2 Файли

     Файл  – динамічна структура даних, розмір якої може мінятися в процесі виконання над ним яких-небудь дій (він може дорівнюватися нулеві, що відповідає порожньому файлу). Взагалі, поняття файлу використовують і як абстракцію даних, що зберігаються в пам'яті, що дозволяє однозначно визначити їх загальні характеристики та операції над ними. Однак властивості фізичного файлу майже цілком збігаються з властивостями АТД файлу, через що абстракція в даному випадку втрачає весь зміст. Файл – структура, що складається з послідовності компонентів одного типу. Властивості послідовності визначають послідовний доступ до елементів, тобто в кожен момент часу може бути доступний тільки один елемент файлу. Основна операція над файлами – конкатенація (чи злиття) файлів – дозволяє створювати файли необмеженої довжини [8, c. 67].

     Існує кілька видів файлів в Паскалі.

     Текстові  файли трактуються як послідовності рядків змінної довжини. Наприкінці кожного рядка ставиться спеціальна ознака кінця рядка EOLN.

     Типізовані  файли – послідовності компонент визначеного типу. Довжина будь-якого елемента типізованого файлу строго визначена і незмінна, що дає можливість організувати прямий доступ до кожного компоненту. У деяких модифікаціях мови Паскаль ця дія реалізується процедурою SEEK. Також, на відміну від текстових файлів, тут не працюють процедури READLN і WRITELN, оскільки немає потреби в перекладі рядка.

     Нетипізовані  файли визначаються структурою FILE і відрізняються тим, що для них не зазначений тип компонентів. Такий підхід робить нетипізовані файлові змінні сумісними з файлами будь-яких типів, а також дозволяє організувати високошвидкісний обмін даними між оперативною і зовнішньою пам'яттю. При ініціації таких файлів процедурами RESET чи REWRITE потрібно вказувати їхню довжину в байтах, причому для досягнення максимальної швидкості обміну краще, якщо ця довжина кратна розміру фізичного сектора на зовнішній пам'яті.

     1.3 Динамічні структури

     Хоча  динаміка і не є значною рисою  мови Паскаль, все-таки існує можливість створювати динамічні об'єкти й оперувати ними. Динамічний об'єкт являє собою область пам'яті без ідентифікатора. Для звернення до цієї області створюється спеціальна змінна-посилання, котра описується в програмі. Елементами множини значень типу посилання є значення адреси оперативної пам'яті.

     Найчастіше  динамічні структури складаються  з об'єктів, що є записами з декількох  полів, один або декілька з яких є  посиланнями на такий же об'єкт. У  такий спосіб можна складати ланцюжки або більш складні структури  об'єктів, які посилаються один на одне. Розмір таких структур обмежується тільки обсягом вільної пам'яті і може легко змінюватися при видаленні і створенні об'єктів, що і визначило основну область їх застосування – моделювання нелінійних послідовних структур даних (наприклад, дерев). Однак, незважаючи на майже повну відсутність недоліків, динамічні структури все ж таки мають свої мінуси. Головний з них – відсутність наочності програми, що викликає значні труднощі при створенні особливо великих структур.

     1.4 Записи

     Запис – це зв'язана структура, яка складається з декількох елементів (полів) різних (або однакових) типів. По суті, запис дуже схожий на одномірний масив, але з елементами різних типів, крім того, доступ до конкретного поля запису здійснюється вже не через індекс, а вказівкою ідентифікатора (тобто імені) цього поля [4, c. 212].

     Крім  того, в Паскалі існує можливість змінювати тип конкретного поля в залежності від ситуації. Такі структури називаються записами з варіантами. Правда, у будь-якому  записі може бути тільки одна варіантна  частина, і, якщо вона є, її опис повинен розташовуватися за усіма фіксованими частинами. Важлива особливість варіантної частини полягає в тому, що усі варіанти як би «накладаються» один на одного, тобто кожному з них виділяється та сама область пам'яті. Це відкриває додаткові можливості перетворення типів.

 

      РОЗДІЛ 2. ВИКОРИСТАННЯ ЗАПИСІВ В ПАСКАЛІ

     В багатьох економічних і інформаційних  задачах обробляються відомості, документи, каталоги, списки. При цьому з'являється  необхідність поєднувати дані різного  типу в одну групу. Для роботи з групою даних у мові програмування Паскаль і введене поняття запис [10, c. 214].

     Запис являє собою сукупність обмеженого числа даних різного типу. Запис, на відміну від масивів і файлів, є складною структурою даних. Якщо окремо узятий масив чи файл завжди включають елементи однакового типу, то записи можуть поєднувати в одне ціле будь-яку кількість структур даних інших типів: простих змінних, масивів, множин і файлів.

     Звичайний фіксований запис складається з  одного чи декількох полів, для кожного з яких при оголошенні вказується ім'я (ідентифікатор) і тип.

     Поняття запису розглянемо на прикладі відомості  списку учнів з їх оцінками: 

 

     Кожен рядок у цій відомості складається з окремих елементів - даних різного типу:

     а) порядковий номер - ціле десяткове число;

     б) Прізвище І.П. - масив символів;

     в) Оцінка - масив цілих чисел.

     Ці  дані можна об'єднати в одну групу  і вважати записом.

     Для представлення такої різнорідної, але логічно пов'язаної інформації зручно використовувати комбінований тип. Необхідно відзначити, що в даному випадку окремі компоненти комбінованого типу, через їхню різну природу, не можуть ідентифікуватися порядковими номерами (індексами), як у масивах; тому для позначення компонентів використовуються індикатори. Таким чином, опис комбінованого типу являє собою список описів його елементів (які називаються також полями запису); кожен опис схожий на опис простої змінної [5, c. 91].

     Список  полів починається службовим словом record і повинний завершуватися службовим словом end. Оголошення запису в розділі змінних VAR має наступний вид: 

VAR ім'я запису: RECORD

ім'я  елемента 1: тип;

ім'я  елемента 2: тип;

....................

ім'я  елемента n: тип;

END; 

     Для приклада, наведеного вище, опис комбінованого  типу може виглядати в таким чином: 

VAR B: RECORD

N: INTEGER;

FIO: PACKED ARRAY[1..20] OF CHAR;

OCENKA: ARRAY[1..3] OF INTEGER;

END; 

     Розглянемо  більш універсальну форму оголошення запису - з використанням розділу типів TYPE. 

TYPE ім'я типу = RECORD

ім'я  елемента 1: тип;

ім'я  елемента 2: тип;

...................

ім'я  елемента n: тип;

END; 

VAR ім'я запису: ім'я  типу;

TYPE BEDOM=RECORD

N: INTEGER;

FIO: PACKED ARRAY[1..20] OF CHAR;

OCENKA: ARRAY[1..3] OF INTEGER;

END;

VAR B:BEDOM; 

     Доступ  до елементів (полів) записів здійснюється за допомогою конструкції, яка називається  селектором запису і що має наступний  загальний вид: