Складні структури даних в паскалі

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

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

     кафедра ... 
 
 
 
 

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

     ЗАПИСи 
 

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

                    Виконала

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

                    Керівник

                    ...... 
                     
                     
                     

     Черкаси 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].

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

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

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

№ Прізвище  І.П. Оцінка
1. Пархоменко  Л.І. 5 3 4
2. Удовенко О.В. 5 5 5
3. Чиж П.П 4 4 5
 

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

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

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

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

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

     Для представлення такої різнорідної, але логічно пов'язаної інформації зручно використовувати комбінований тип. Необхідно відзначити, що в даному випадку окремі компоненти комбінованого типу, через їхню різну природу, не можуть ідентифікуватися порядковими номерами (індексами), як у масивах; тому для позначення компонентів використовуються індикатори. Таким чином, опис комбінованого типу являє собою список описів його елементів (які називаються також полями запису); кожен опис схожий на опис простої змінної [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; 

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

     R.F,

     де R - змінна комбінованого типу;

     F - ідентифікатор поля.

     Незалежно від кількості оголошених змінних типу "запис", поля кожної змінної називаються однаково, відповідно до шаблона. Оскільки імена полів "сховані" усередині типу, вони можуть збігатися з іменами "зовнішніх" змінних і поля в інших описах записів, наприклад: 

      type PointRecType = RECORD

      X,Y : Integer

      END;

      ColorPointRecType = RЕСОRD

      X,Y:Integer;

      Color:Word

      END;

      var X,Y :Integer; Point :PointRecType;

      ColorPoint :ColorPointRecType; 

     У програмі X,Point.X, ColorPoint.X - зовсім різні  значення.

     Записи  в Паскалі можуть мати так звану варіантну частину. Це означає, що в межах одного типу можна задати декілька різних структур. Безпосередній вибір однієї зі структур буде визначатися контекстом або сигнальним значенням [2, c. 64]. Варіантні поля при завданні шаблону запису вказуються після того, як перераховані всі поля фіксованого типу й оформляються особливим чином:  

     TYPE

     VRecType = RECORD {Тип запису  з варіантами}

     Number :Byte;

     case Measure : Char of {Ознака  одиниць виміру  довжини}

     'д','Д':(INChes : Word); {В дюймах}

     'с','С':(cantimeters :LongInt); {В сантиметрах}

     '?':(Comment1,Comment2 : String[16]) {Тексти - коментарі}

     END;   

     В прикладі запису є звичайне фіксоване  поле Number, і поле-селектор Measure, обрамлене словами CASE і OF, після чого йде перерахування варіантів 3-го поля в круглих дужках. Вміст поля-селектора визначає, який саме варіант буде обраний при роботі з записом. В  один й той же момент доступні поля тільки одного з можливих варіантів, в залежності від значення, привласненого полю - селектору. Усі варіанти розташовуються в одному й тому ж самому місці пам'яті, а розмір цього місця визначається самим об'ємним варіантом – в даному випадку 2*(16+1) байтів для поля String[16].

     Поле-селектор можна ігнорувати, звертаючись до кожного з полів варіантів - те саме значення буде трактуватися відповідно до типу поля. В такому випадку завжди існує можливість помилок, які ніяк не діагностуються, але якщо не помилятися, то можна зі зручністю використовувати варіантні записи для збереження різних варіантів наприклад, як у наведеному прикладі, одиниць виміру довжини [3, c. 88].

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

      TYPE

      VRecType = RECORD

      Number :Byte;

      case Byte of

      1:(INChes : Word); {В дюймах}

      2:(cantimeters :LongInt); {В сантиметрах}

      3:Comment1,Comment2 : String[16]) {Тексти - коментарі}

      END;   

     Значення  констант в процесі опису в  цьому випадку - чиста формальність і можуть бути будь-якими неповторюваними  в межах типу Byte [7, c. 105]. При відмовленні від поля-селектора під час роботи програми вже не можна визначити, який варіант повинний використовуватися в даний момент і так звичайно працюють при необхідності різнотипного представлення тих самих даних:  

      TYPE

      CharArrayType = Array[1..4] of char;

      VAR

      V4:RECORD

      case Boolean of

      True : (C:CharArrayType);

      False: (B1,B2,B3,B4 :Byte)

      END;   

     Поля B1..B4 дозволяють працювати з ASCII - кодами символів, а поля З[1]..C[4] - із символами, не прибігаючи до явного перетворення типів.

     Змінні  типу "запис" можуть брати участь тільки в операціях присвоювання, а їх поля - у будь-яких дозволених для їхнього типу операціях [1, c. 103].

     Для полегшення роботи з полями записів  у Паскалі введений оператор приєднання WITH з наступним синтаксисом використання:

     WITH Ім.’яЗмінноїЗапису DO Оператор;

     Усередині оператора звертання до полів  уже виробляється без вказівки імені  змінної:  

      VAR

      DemoRec : RECORD X,Y :Integer END;

      WITH DemoRec DO

      begin

      X:=0;Y:=129;

      End;   

     При використанні всередині WITH "незаписних" змінних необхідно стежити, щоб їх імена не збігалися із "записними". При необхідності "розв'язки" всередині WITH до співпадаючих зовнішніх імен необхідно дописати перед ними через крапку, ім'я програми чи модуля в якому вони описані: 

      PROGRAM MAIN;

      VAR X,Y :Integer;

      RecXY :RECORD X,Y :Integer END;

      begin

      WITH RecXY DO begin

      X:=3.14*Main.X;

      Y:=3.14*Main.Y end;

      end;  

     Якщо  одне з полів запису - теж запис, можна поширити оператор приєднання на декілька полів всередину, перелічивши їх через кому, але всередині тіла оператора можна буде звертатися тільки до останніх полів: 

      WITH Имязаписи, Поле_Запис  DO

      begin

      Звертання до імен полів Поля_Запис

      end;

 

      РОЗДІЛ 3. ДЕМОНСТРАЦІЙНІ ПРИКЛАДИ

     3.1 Приклад 1.

 

 Дано два комплексних  числа. Знайти комплексне число, що є  сумою даних чисел. Використовувана структура даних - запис [14, c. 116].

  

PROGRAM Summa (Input,Output);

      type

         Complex = Record

                      RE: Real;

                      IM: Real

                   end;

      var  X,Y: Complex;   { Вхідні параметри }

             S: Complex;   { Результат          }

   BEGIN

      WriteLn ('Уведіть дійсну  і мниму частину  комплексного числа  X :');

      Read (X.RE,X.IM); WriteLn;

      WriteLn ('Уведіть дійсну  і мниму частину  комплексного числа  Y :');

      Read (Y.RE,Y.IM); WriteLn;

      S.RE:=X.RE+Y.RE; S.IM:=X.IM+Y.IM;

      Write ('Перед Вами - результат... ', S.RE:5:2,' + i',S.IM:5:2)

   END.

     3.2 Приклад 2.

     Програма, що демонструє роботу оператора приєднання With [12, c. 94].  

        PROGRAM  Wit (Input,Output);

           type

              R = Record         { R - ім'я комбінованого  типу }

                     X: Real;

                     Y: Char

                  end;

              Q = Record         { Q - ім'я комбінованого  типу }

                     A: Integer; { A - ім'я поля }

                     B: R

                  end;

           var U: Q;

               X: Integer;

               A: Char;

        BEGIN

           U.A:=2; U.B.X:=7.3; U.B.Y:='І';   { Ініціалізація змінних  комбінованого типу }

           WriteLn ('Уміст поля A ... ',U.A); { Інший спосіб ініціалізації  }

           WriteLn; WriteLn 1  0('     Використання оператора With...');

           With  1  0U  1  0do

              begin

                 A:=1; B.X:=6.7; B.Y:='A'; WriteLn ('Уміст  поля A 1.. ',A,', ')

              end;

           A:='C'; WriteLn ('а значення  змінної A ... ',A)

        END.

     3.3 Приклад 3.

     Копіювання  одного запису в іншу [11, c. 315]. 

        PROGRAM  Copyrovanie (input,output);

           type

              P = Record

                     n      : integer;

                     FIO    : string[12];

                     Otsenka: array[1..3] of integer

                  end;

           var V,VCopy: P;

        BEGIN

           V.n:= 5; V.FIO:= 'Зеніт';  { Ініціалізація змінної  V комбінованого типу }

           V.Otsenka[1]:= 4; V.Otsenka[2]:= 5; V.Otsenka [3]:= 3;

           VCopy := V;        { Запис V скопійований  у запис VCopy! }

           WriteLn('Гляньте, чи правильно ми скопіювали... ');

           Write (VCopy.n,' ',VCopy.FIO,' ',VCopy.Otsenka[1],' ',

                            VCopy.Otsenka[2],' ',VCopy.Otsenka[3]); WriteLn

        END.

     3.4 Приклад 4.

     Нижче наведена демонстраційна програма, яка  показує основні моменти роботи з комбінованими типами даних, а саме:

     a) опис масиву записів; 

     b) ініціалізацію масиву записів; 

     c) передача значень комбінованого  типу в процедуру і повернення  результатів в основну програму.

     Постановка  задачі: дано масив записів, який складає з двох елементів. Запис має три поля: речовинного, цілого і символьного типів. Необхідно знайти для кожного елемента масиву суму вмісту "цілого" і "речового" полів [9, c. 130]. 

        PROGRAM Demostr;

           type

              R = 1..2;

              Q = Record           { Q - ім'я комбінованого типу }

                   Logic: Boolean;         { Ім'я   поля : Logic  }

                   Tchislo: Integer;       { Ім'я   поля : Tchislo}

                   Coffi: Real;            { Ім'я  поля : Coffi  }

                end;              { Після імені поля - тип поля }