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

Структуры даных і праца з імі сродкамі мовы 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;

Доступ да элемента masij ® 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; {вывад матрыцы ў выглядзе матрыцы}