Дзеянні над элементамі масіву

Структуры даных і праца з імі сродкамі мовы Pascal

Парадкавыя тыпы

У групу парадкавых тыпаў аб’яднаны цэлалікавыя, сімвальны, лагічны, пералічальны і інтэрвальны тыпы. Гэта зроблена таму, што яны валодаюць наступнымі ўласцівасцямі:

1) усе магчымыя значэнні парадкавага тыпу ўяўляюць сабой абмежаванае ўпарадкаванае мноства;

2) да любога парадкавага тыпу можна прымяняць стандартную функцыю Ord, якая ў якасці выніку вяртае парадкавы нумар канкрэтнага значэння ў дадзеным тыпе;

3) да любога парадкавага тыпу можна прымяняць стандартныя функцыі Pred і Sucс, якія вяртаюць адпаведна папярэдняе і наступнае значэнні;

4) да любога парадкавага тыпу могуць быць прыменены стандартныя функцыі Low і High, якія вяртаюць найменшае і найбольшае значэнні велічынь дадзенага тыпу.

Структураваныя тыпы даных вызначаюць упарадкаваную сукупнасць скалярных пераменных і характарызуюцца тыпам сваіх кампанентаў.

Мноствы

Тып «мноства» ўтвараецца спецыяльнай канструкцыяй:

SET OF базавы_парадкавы_тып

Мноства ў мове Pascal – гэта абмежаваная (<=256 элементаў) сукупнасць папарна розных аб’ектаў аднаго скалярнага парадкавага тыпу (Word, Integer, Shorting), які называецца базавым. Скалярныя тыпы Byte і Char уводзяцца мовай і могуць быць асновай для пабудовы мностваў, бо іх колькасць роўна 256.

Базавы тып задаецца пералічэннем, дыяпазонам ці іменем тыпу.

TYPE

SetOfChar = SET OF Char; {мноства з сімвалаў}

SetOfByte = SET OF Byte; {мноства з лікаў}

SetOfDigit = SET OF 0..9; {мноства - інтэрвал лікаў}

SetOfDChar = SET OF '0'..'9';{мноства - інтэрвал сімвалаў}

VAR

SChar: SetOfChar;

SByte: SetOfBYTE;

SDigit: SetOfDigit;

Кожны аб’ект у мностве называецца элементам мноства. Калі мноства не мае элементаў, яно называецца пустым. Вобласць значэнняў тыпу «мноства» – набор разнастайных падмностваў, якія складзены з элементаў базавага тыпу.

Выява мноства:

Спроба абвешчаным пераменным надаць значэнні, якія не ўваходзяць у базавае мноства, выклікае праграмнае перарыванне. Напрыклад:

SDigit:= [0,2,4,6,8];

SDigit:= [10]; {памылка}

SChar:= ['a'..'z','A'..'Z','б','г'];

SChar:= [2]; {памылка}

Парадак чаргавання элементаў унутры дужак не мае значэння, таксама як не мае значэння колькасць паўтарэнняў элемента. Напрыклад:

Schar:= ['a', 'a', 'а', 'а'] эквівалентна аднаразоваму ўпамінанню сімвала 'a'.

Прыклад.

VAR

x: Byte;

S: SET OF Byte;

...

x:= 3;

S:= [1, 2, x];

S:= S+[x+1];

Мноства можа пашырацца ці скарачацца па ходу праграмы. Існуюць працэдуры Exclude і Include, якія адпаведна выдаляюць і дабаўляюць элемент у мноства. Працэдура Include(S, i) выдаляе з мноства S элемент, зададзены параметрам і. Працэдура Exclude(S, i) дабаўляе да мноства S элемент, зададзены параметрам і.

Аперацыі над мноствамі (накшталт матэматычных), якія вызначаны ў мове Pascal, прадстаўлены ў наступных трох табліцах.

Аб’яднанне мностваў (тое, што ўваходзіць у 1-е і 2-е мноствы)	Рысунак

У матэматыцы	У мове Pascal
Абазначэнне	Прыклад	Абазначэнне	Прыклад

Перасячэнне мностваў (тое, што агульнае ў 1-м і 2-м мноствах)

Рысунак

У матэматыцы

У мове Pascal

Абазначэнне

Прыклад

Абазначэнне

Прыклад

Рознасць мностваў (тое, што ёсць толькі ў 1-м мностве, за выключэннем таго, што ёсць у абодвух)

Рысунак

У матэматыцы

У мове Pascal

Абазначэнне

Прыклад

Абазначэнне

Прыклад

Вынік гэтых аперацый – заўсёды мноства.

Другая група аперацый – гэта аперацыі параўнання ці адносін: =, <>, >=, <=. Вынік заўсёды true ці false.

Аперацыя	Назва	Форма	Тлумачэнне: false – у адваротным выпадку
=	Праверка на роўнасць	S1=S2	True, калі S1 і S2 складаюцца з аднолькавых элементаў
<>	Праверка на няроўнасць	S1<>S2	True, калі S1 і S2 адрозніваюцца хоць адным элементам
<=	Праверка на падмноства Ì	S1<=S2	True, калі ўсе элементы S1 уваходзяць у S2 незалежна ад парадку чаргавання
>=	Праверка на падмноства É	S1>=S2	True, калі ўсе элементы S2 у S1
IN	Праверка на ўваходжанне элемента ў мноства	E IN S1 E IN […]	True, калі значэнне элемента E належыць базаваму тыпу мноства і ўваходзіць у мноства S1 ці мноства-канстанту ([...])

Аперацыю IN добра скарыстоўваць, калі трэба праверыць пападанне значэння ў дыяпазоны пералічальных тыпаў:

IF ch IN ['a'.. 'x', 'A'.. 'X'] THEN …

IF j IN [100..200] THEN

Тут скарыстаны канстанты тыпу «мноства». Гэтым спрашчаюцца лагічныя аператары. Параўнайце наступную ўмову:

C IN ['0'.. '9', 'A'.. 'Z'];

і такую:

(C>='0') AND (C<='9') OR (C>='A') AND (C<='Z');

Вартасці мностваў відавочны:

1) эканоміцца памяць, бо аб’ём памяці, які займае адзін элемент мноства, роўны 1 біту. Значыць, аб’ём мноства з 256 элементаў складае ўсяго 32 байты, а адвольнага – (MaxNum DIV 8)-(MinNum DIV 8)+1;

2) эканоміцца час, бо распрацоўшчыкі транслятараў звычайна звязваюць элементы мноства з машынным словам, у якім: код «1» – прысутнасць элемента ў мностве, «0» – адсутнасць.

Значыць, параўнанне мностваў і аперацыі над мноствамі рэалізаваны на ўзроўні апрацоўкі бітаў.

Недахопы мностваў – немагчымасць іх вываду (напрыклад, на экран) ці ўводу (напрыклад, з клавіятуры). Існуе магчымасць толькі пераканацца, што элемент належыць мноству. Аднак можна зрабіць наступнае: узяць нейкую рабочую пераменную, прабегчы па ўсіх базавых элементах пэўнага мноства і, пераканаўшыся, што элемент з мноства, друкаваць яго.

Тып «мноствы» істотна пашырае гібкасць мовы.

Тыпізаваныя канстанты тыпу «мноства»

Канстанта тыпу «мноства»:

Канстанта - элемент:

Прыклад.

CONST Xset: SET OF Char=['а', 'б', 'в'];

Разгледзім выкарыстанне даных з тыпам «мноства».

Задача. Запраграміраваць рэшата Эратасфена для пошуку простых лікаў велічыні £ 255.

Алгарытм. Сярод усёй сукупнасці лікаў ад 2 да 255 выкраслім кратныя чарговаму простаму.

PROGRAM Proct;

VAR

Prime: SET OF 2..255;

j, i, m: Integer;

BEGIN

Write ('увядзі m <= 255');

Readln (m);

Prime:= [2..m];

FOR i:= 2 TO m DO

IF i IN Prime THEN

FOR j:= 2 TO (m DIV i) DO

Prime:= Prime-[i * j];

{выключылі ўсе кратныя простаму ліку i}

Writeln ('простыя лікі <=', m);

FOR i:= 2 TO m DO

IF i IN Prime THEN Write (i:4);

END.

Заданне. Зададзена паслядоўнасць розных сімвалаў. Падлічыць, колькі сярод іх сімвалаў-лічбаў.

Алгарытм. Бяром чарговы сімвал, пакуль ён не «.». Калі ён у мностве сімвалаў-лічбаў, падлічваем яго. Раздрукоўваем вынік.

Масівы

Пераменныя тыпу «масіў», або масіў, – гэта ўпарадкаваная сукупнасць аднатыпных даных, якія захоўваюцца паслядоўна.

Тып «масіў» вызначаецца наступнай канструкцыяй:

Масіў абавязкова мае фіксаваныя памеры, якія вызначаюць, колькі элементаў захоўваецца ў ім. Любы элемент у масіве можна знайсці па яго індэксе. Індэксы – гэта выразы любога парадкавага тыпу.

Тып індэксаў паказвае, у якіх межах змяняецца індэкс масіву. Тып кампанентаў – любы вядомы тып даных.

Калі ў апісанні масіву зададзены адзін індэкс, масіў называецца аднамерным, два – двухмерным, n – n - мерным. Памеры масіву абмежаваны толькі аб’ёмам памяці. Для Turbo Pascal – гэта прыблізна 64 кб.

У секцыі TYPE можна вызначыць тыпы масіваў. Гэта будуць найменныя тыпы масіваў, якія потым скарыстоўваюцца пры вызначэннях пераменных тыпу «масіў».

Пасля аб’яўлення масіву кожны яго элемент можна апрацоўваць, указаўшы імя (ідэнтыфікатар) масіву і індэксы элемента ў квадратных дужках.

Індэксіраваныя элементы масіву называюцца індэксіраванымі пераменнымі і могуць быць выкарыстаны як простыя пераменныя.

TYPE

Array01to10 = ARRAY [ 1..10] OF Real;

Array11to20 = ARRAY [11..20] OF Real;

Гэтыя два тыпы (Array01to10 і Array11to20) па-рознаму нумаруюць свае элементы, хаця абодва ўтрымліваюць наборы з 10 значэнняў тыпу Real.

VAR

a01to10: array01to10;

a11to20: array11to20;

Доступ да i -га элемента масіву:

a01to10[i], i=1,…,10,

a11to20[i], i=11,…,20.

Прыклад 1.

CONST k=4; n=6;

TYPE TVector = ARRAY [1..4] OF Integer;

TMatrica = ARRAY [-4..4, -4..4] OF Real;

TMassiv = ARRAY [1..4] OF TVector;

VAR Matr: TMatrica;

Vect: TVector;

M: TMassiv; {масіў масіваў}

Mas: ARRAY [1..k, 1..n] OF Char;

Доступ да элемента mas_ij ® mas[i,j]. Доступ да элементаў масіву M можна ажыццявіць і так: m[i][j], і так: m[i,j].

У агульным выпадку ніхто не абавязвае аб’яўляць дыяпазон індэксаў масіву лікамі.

Прыклад 2.

TYPE

MonthType = (January, February, March, April, May);

ComplectType = ARRAY [MonthType] OF Word;

SpringType = ARRAY [March..May] OF Word;

VAR

Complect: ComplectType; {5 элементаў тыпу Word}

Spring: SpringType; {3 элементы тыпу Word}

Alpfa: ARRAY [¢A¢..¢Z¢] OF Char; {26 элементаў}

Switch: ARRAY [boolean] OF Byte; {2 элементы}

Зварот да элементаў вызначаных масіваў:

Spring[April]; Alpfa[¢X¢]; Switch[true];

Прыклад 3.

VAR

M: ARRAY [-10..0, ¢A¢..¢C¢, boolean] OF Byte;

Эквівалентны запіс:

M: ARRAY [-10..0] OF ARRAY [¢A¢..¢C¢] OF

ARRAY [boolean] OF Byte;

У апошнім выпадку M[0] – масіў-матрыца тыпу

ARRAY [¢A¢..¢C¢] OF ARRAY [boolean] OF Byte;

ці

M[0] – ARRAY [¢A¢..¢C¢, boolean] OF Byte.

M[0, ¢B¢] – гэта вектар тыпу ARRAY [boolean] OF Byte.

M[0, ¢B¢, false] – значэнне тыпу Byte.

Выкарыстоўваць жа элементы M[0], M[0, ¢B¢] даволі складана, бо трэба клапаціцца аб сумяшчальнасці тыпаў даных.

У памяці камп’ютэра масівы захоўваюцца як суцэльныя паслядоўнасці кампанентаў, пры гэтым калі ў масіве некалькі індэксаў, тады ў першую чаргу змяняецца апошні індэкс, потым перадапошні і гэтак далей да першага. Значыць, матрыцы захоўваюцца па радках:

A: ARRAY [1..5, 1..5] OF Byte;

{a[1,1], a[1,2], a[1,3],…, a[1,5], a[2,1],…, a[5,5]}

Адрас пачатку масіву ў памяці адпавядае адрасу яго першага элемента, г. зн. элемента з мінімальнымі значэннямі індэксаў.

Калі праграма ці фрагмент яе кампілюецца ў рэжыме {$R+}, тады пры звароце да элементаў масіваў будзе правярацца належнасць значэння індэкса аб’яўленаму дыяпазону, і ў выпадку памылкі (парушэнне межаў дыяпазону) узнікне памылка Range check Error.

Прыклад 4.

v: ARRAY [1..10] OF Integer;

Зварот да элемента v[11] дасць памылку на кроку кампіляцыі ў рэжыме {$R+}.

Калі ў рэжыме {$R-} узнікне аналагічная сітуацыя, праграма будзе працаваць далей, і некарэктнае значэнне індэкса можа здабыць якое-небудзь значэнне, але ўсё ж не з патрэбнага масіву. Звычайна праграму адладжваюць у рэжыме {$R+}, а эксплуатуюць пры рэжыме {$R-}.

Работа з элементам масіву займае больш часу, чым са скалярнай пераменнай, бо трэба падлічваць месцазнаходжанне элемента ў памяці. Але пры выкарыстанні масіваў праграмы становяцца больш функцыянальнымі.

Дзеянні над масівамі

Пераменная тыпу «масіў» можа ўдзельнічаць толькі ў аператары «надаць значэнне»:=. Масівы, якія ўдзельнічаюць у гэтай аперацыі, павінны быць ідэнтычнымі па структуры (для масіваў ідэнтычнасць па структуры – гэта фактычна аб’яўленне ў адным спісе):

VAR

A, B: ARRAY [1..20] OF Real;

C, D: ARRAY [1..5, 1..5] OF Word;

Аператар A:= B азначае, што адпаведным элементам масіву A надаюцца значэнні элементаў масіву B. Аператар C:= D азначае, што адпаведным элементам масіву C надаюцца значэнні элементаў масіву D. Аператар A:= D прывядзе да памылкі.

Дзеянні над элементамі масіву

Разгледзім тыповыя сітуацыі, што ўзнікаюць пры рабоце з данымі тыпу «масіў» у наступнай праграме:

CONST n=10; m=5; L=4;

VAR A, O: ARRAY [1..L] OF Real;

B: ARRAY [1..n,1..m] OF Integer;

k, i, j: Integer;

S: Real;

...

FOR i:=1 TO L DO Read(A[i]);

{ініцыялізацыя аднамернага масіву}

FOR i:=1 TO n DO

FOR j:=1 TO m DO Read(B[і,j]);

{ініцыялізацыя двухмернага масіву}

FOR i:=1 TO n DO

BEGIN

FOR j:=1 TO m DO Write(B[і,j]);

Writeln;

END; {вывад матрыцы ў выглядзе матрыцы}