[ЗМІСТ] [Далі] [Назад]

7. СТРУКТУРИ ДАНИХ

7.1. Множини

7.2. Множини у мовах програмування

7.3. Записи

7.4 Об’єднання

7.5. Записи та об’єднання у мовах програмування

7.6. Масиви

7.7. Масиви у мовах програмування

7.8. Файли

7.8.1 Послідовні файли

7.8.2 Файли прямого доступу

7.8.3 Текстові файли

7.9. Файли у мовах програмування

7.10 Процедурний тип даних

7. СТРУКТУРИ ДАНИХ

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

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

Домовимося про позначення. Типи даних будемо позначати грецькою літерою t, можливо, з індексами. Якщо t - тип даних, то через D_t визначимо множину величин типу t або, коротше, його область. Через ¦D_t¦ визначимо потужність множини D_t.

Ще одна угода: замість ¦D_t¦ ми будемо писати ¦t¦, а замість

f: D * D *. .. * D -> D

t₁ t₂ t_n t

та

Р: D * D *. .. * D -> D, * D, *. .. * D,

t₁ t₂ t_n t₁ t₂ t_n

відповідно

f: t₁, t₂,. .., t_n -> t (7.1)

та

Р: t₁, t₂,. .., t_n -> t₁, t₂,. .., t_n, (7.2)

називаючи вираз (7.1) типом функції f, а вираз (7.2) – типом інструкції Р.

Під структурою даних ми будемо розуміти правило отримання нового типу даних t по заданих типах t₁, t₂,..., t_n, включаючи сюди:

· правило побудови області D_t по областях D_t1, D_t2, ..., D_tn;

· визначення відношень, операцій, функцій та інструкцій, що використовують область D_t.

Таким чином, визначення нового типу даних за допомогою певної структури даних приводить до визначення нового виконавця, що успадковує можливості виконавців для типів t₁, t₂,..., t_n і, крім того, має в своєму розпорядженні нові можливості, перераховані вище.

7.1. Множини

Нехай t - деякий простий скалярний тип (скалярним називають будь-який простий тип окрім дійсного), D_t - його область. Тоді

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

¦ тип t_s = множ із t ¦

L--------------------

- це новий тип, областю D_ts якого служить множина всіх підмножин множини D_t.

Наприклад,

множ із нат;

множ із симв;

множ із 1..n.

Твердження 7.1. Якщо ¦t¦=n, то ¦множ із t¦=2ⁿ. ¦

Перерахуємо віднощення, операції, функції та інструкції, що мають справу з множинами. Нехай А, В - множини типу t_s, х – змінна типу t.

1. Операції:

- створення множини перерахуванням її елементів

[_.._, _.._, ..., _.._]: t, t, ..., t -> t_s;

тобто якщо s₁, r₁, ..., s_n, r_n - вирази типу t, то значенням виразу [s₁..r₁, ..., s_n..r_n] є множина, що складається з всіх таких d Î D_t, що s_k < d < r_k для деякого k=1,..., n; причому замість s..s будемо писати коротше s, а порожню множину визначимо []. Наприклад, нехай тип t - це тип симв. Тоді множину А, що складається з всіх маленьких латинських літер, можна утворити так

А <- ['a'..'z'].

- об'єднання двох множин

_+_: t_s, t_s -> t_s,

наприклад, А+В або А+[х];

- перетин двох множин

_*_: t_s, t_s -> t_s,

наприклад, А*В;

- різниця двох множин

_-_: t_s, t_s -> t_s,

наприклад, A-B або А-[х].

2. Функції:

- потужність

card: t_s -> нат,

наприклад, card(А)=¦А¦.

3. Відношення:

- елемент належить множині

_ в _: t, t_s -> бул,

так виразення х в А істинне, якщо х є елементом множини А;

- рівність двох множин

_=_: t_s, t_s -> бул,

наприклад, А=В;

- включення однієї множини в іншу

_<_: t_s, t_s -> бул,

вираз А<В істинний, якщо А є підмножиною В.

Маючи в своєму розпорядженні рівність і включення, отримуємо стандартний набір відношень:

А<>В = Ø(А=В);

А<=В = (А<В) V (А=В);

А>В = B<A;

А>=В = B<=A.

4. Інструкції:

- присвоєння А <- Е, де Е - вираз типу множ із t;

- взяти довільний елемент з множини

взяти з А в х

виконується так, щоб мало місце твердження

{ А=А₀ <> [] }

взяти з А в х

{ Ø(х в А) & А =А₀+[х] },

причому спроба отримання елемента порожньої множини природно призводить до відмови;

- цикл по множині

для всіх х з А повт Р кц,

де Р - інструкція, що не змінює множину А, є скороченим записом циклу (В - допоміжна змінна)

B <- А;

поки card(В)>0 повт

взяти з В в х;

Р

кц.

Теоретико-множинним виконавцем Set(t) назвемо виконавець, що реалізує тип даних множ із t.

Ось декілька прикладів описів

тип Місяць = (січ, лют, бер, кві, тра, чер, лип, сер, вер, жов, лис, гру);

змін Заняття, Сесія, Канікули: множ із Місяць

та інструкцій теоретико-множинного виконавця

Заняття <- [лют..тра, вер..гру];

Сесія <- [січ, чер];

Канікули <- [лип, сер].

Інші теоретико-множинні операції, що не увійшли до стандартного набору операцій виконавця Set(t), реалізуються з допомогою програмованих функцій.

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

процедура Get_Set (рез А: множ із t) це

змін N: нат; X: t;

поч

взяти (N); А <- [];

повт N раз

взяти (X); А <- А+[X]

кц

кп.

Ось декілька прикладів підпрограм роботи з множинами.

Приклад 7.1. Тривалість місяця невисокосного року.

функція Length_Month (M: Місяць): нат це

змін Short: множ із Місяць;

поч

Short <- [кві, чер, вер, лис];

якщо M=лют то Length_Month <- 28

інякщо M в Short то Length_Month <- 30

інакше Length_Month <- 31 кр

кр

кф.

Приклад 7.2. Максимальний елемент числової множини.

функція МaxI_Set (А: множ із n..m): ціл це

змін K, J: n..m;

поч

K <- n;

для всіх J з А повт

якщо J>K то K <- J кр

кц;

MaxI_Set <- K

кф.

Приклад 7.3. Друк елементів числової множини в порядку спадання.

процедура PrintI_Set (арг А: множ із n..m) це

змін K: n..m;

поч

поки card(А)>0 повт

K <- MaxI_Set (А); показати (K);

А <- А-[K]

кц

кп.

До числа найважливіших задач над множинами відноситься задача пошуку потрібного елемента в множині. Ось приклад процедури пошуку, де Q - функція типу: t -> бул.

процедура Search_Set (арг А: множ із a..b;

рез X: a..b; Find: бул) це

змін Exhaus: бул;

поч

X <- a; Exhaus <- X>b; Find <- Хиб;

поки Ø(Exhaus V Find) повт

якщо X в А то Find<- Q(X) кр;

якщо ØFind то

Exhaus <- X=b;

якщо ØExhaus то X <- succ(X) кр

кр

кц

{якщо Find то Q(X) інакше "(X Î А) ØQ(X)}

кп.

Вправа 7.1. Спростити процедуру пошуку, якщо відомо, що а та b належать цілому або натуральному типу, причому b строго менше максимального числа з інтервалу представлення.¦

Рішення задачі пошуку показує, що, нарівні з виконавцем Set(t) можна розглядати більш скромний виконавець Set0(t), не наділений інструкціями отримання елемента і циклу. У цьому випадку процедура отримання елемента будується аналогічно процедурі пошуку.

Крім того, задача пошуку показує спосіб організації циклу по множині, що не використовує інструкцію отримання елемента

{А < [a..b]}

X <- a; Exhaus <- X>b;

поки ØExhaus повт

якщо X в А то Р кр;

Exhaus <- X=b;

якщо ØExhaus то X <- succ(X) кр

кц.

Вправа 7.2. Спростити приведений вище цикл в умовах вправи 7.1.¦

Рішення більш складної задачі пошуку показує наступний приклад.

Приклад 7.4. Решето Ератосфена (біля 276-194 рр. до н.е.). Наступна функція реалізовує відомий спосіб отримання множини всіх простих чисел, що не перевишують n.

функція Erat (N: нат): множ із 2..N це

змін I, J: 2. N;

Р, R: множ із 2..N;

поч

R <- [2..N]; Р <- [2];

для I<-2 до N через 2 повт

R <- R-[I]

кц;

для I<-3 до N через 2 повт

якщо I в R то

Р <- Р+[I]; R <- R-[I];

для J<-I*I до N через 2*I повт

R <- R-[J]

кц

кр

кц;

Erat <- Р

кф.

7.2. Множини у мовах програмування

У мові Сі тип множина не передбачений.

У мові Паскаль тип даних множина описується оператором

type Name = set of t,

де Name - ім'я типу даних; t - базовий тип множини - будь-який скалярний тип, за винятком типу real. Базовий тип t задається обмеженням або перерахуванням.

Приклади множин:

[] - порожня множина;

[2,3,5,7,11];

['a','o','i','e'];

[1..1, 5..1] - множина що складається з одного елемента [1].

Дві множини, відмінні тільки порядком входження елементів множини, вважаються однаковими.

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

Над множинами А і В визначені наступні

Операції:

А+В: об'єднання множин;

А*В: перетин множин;

A-B: різниця множин - це множина всіх елементів з А, які не є елементами В.

Відношення:

z in А - належність елемента z множині А;

А=В - рівність множин;

А<>В - множини не співпадають;

А<=В - всі елементи А Î В;

А=>В - всі елементи В Î А.

Інструкція присвоєння А:= Е, де Е - вираз, значенням якого є множина.

Приклад 1P. Побудова множини простих чисел, які не перевершують число 255 за допомогою решета Ератосфена (задача 7.4):

program ERAT255;

const N= 255;

type Set255= set of 2..N;

var P: Set255;

I, J: 0..N;

procedure Erat (var P: Set255);

var R: Set255;

I, J: word;

begin

R:= [2..N]; P:= [2]; I:= 2;

while I<=N do begin

R:= R-[I]; I:= I+2

end;

I:= 3;

while I<=N do begin

if I in R then begin

R:= R-[I]; P:= P+[I];

if I<=N div I then begin

J:= I*I;

while J<=N do begin

R:= R-[J]; J:= J+2*I

end

end

end;

I:= I+2

end;

end;

begin

Erat (P);

J:=0; writeln('Прості числа з проміжку [1..255]');

for I:=2 to N do

if I in P then begin

write(I:4); J:=J+1;

if J mod 10 = 0 then writeln

end;

writeln

end.

[ЗМІСТ] [Далі] [Назад]