«Мәліметтерді өңдеудің құрылымдары мен алгоритмдері»

Бағытталмаған графтар үшін х, у қабырғасы у,х қабырғасына тең болады. Сондықтан олар үшін көршілестік матрицасы әрқашан симметриялы. Оларда алдыңғы граф үшін матрица мынадай:

1 2 4 5

3 6


Бағытталмаған граф үшін көршілестік матрица:

2 4

5

3 5

Тақырыбы: Сызықты байланысқан мәліметтер құрылымдарын ұйымдастыру және олармен жүргізілетін амалдар.

Массив дегеніміз мәліметтердің құрылымдалған жиыны. Ол жалпы аты бар, бір типті элементтердің белгіленген санының реттелген жиынтығын сипаттау үшін қолданылады. Массив элементтерін белгілеу үшін массив айнымалысы аты және индексі қолданылады. Жұмысты орындамас бұрын массив типті айнымалыларды қолдануды және сипаттау ережелерін үйрену керек.

1. 
   Бұл есепті шешудің алгоритмдерінің біреуінің мәні массивті жол бойынша қарап, әрбір жолда (0:сан) жұбын тауып, содан кейін олардың өзара орынын ауыстырып, осылайша жолда мұндай жұптар қалмағанға дейін жалғастыруда.
   
2. 
   Программаның паскальда жазылуы:
   
3. 
   program маs_1;
   

V: array[1..100,1..100] of integer;

m,n, i,j, c: integer;

flag: boolean;

begin

<массив өлшемін енгізу m*n>

<массив ұяшықтарын толтыру>

for i:=1 to m do

repeat

flag:= true;

for j:=1 to n-1 do

if (v[i,j]=0) and (v[i,j+1]<>0) then begin

flag:= false;

end;

until flag;

readln;

Бірінші жолды реттейміз:

Блок-схеманың алгоритмы бүтіндей:

5. Паскальдағы программа:

program mas_1;

var

m,n, i,j, c: integer;

flag: boolean;

begin

for i:= 1 to m do

for j:= 1 to n do begin

write('V[',i,',',j,']= '); readln(V[i,j]);

end;

for i:=1 to m do

flag:= true;

for j:=1 to n-1 do

if (v[i,j]=0) and (v[i,j+1]<>0) then begin

c:=v[i,j]; v[i,j]:=v[i,j+1]; v[i,j+1]:=c;

flag:= false;

end;

until flag;

for j:= 1 to n do write(V[i,j]:2);

writeln

end;

end.

1. 
   Массив типті айнымалылар қалай анықталады?
   
2. 
   Бір өлшемді, екі өлщемді массивтің жекелеген элементіне кіру қалай жүзеге асырылады?
   
3. 
   Массивтың элементтері экранға қалай шығарылады?
   
4. 
   Екі өлшемді массивты экранға матрица түрінде шығаратын программа фрагментін келтір.
   
5. 
   X : Array[0..1, 0..1, 0..1, 0..1, 0..1, 0..1] of Integer алты өлшемді массивына неше сан жазуға болады?
   

1. 
   а1,а2,а3 бұтін сандары берілген. Бүтін санды [bij]i,j=1,2,3 матрицасын алу керек, мұнда bij=ai-3aj.
   
2. 
   [aij]i=1,…10; j=1,…12 – бүтін санды матрицасын алу керек, aij=i+2j.
   
3. 
   N өлшемді квадрат матрица берілген. Бас диагональдан жоғары, төмен орналасқан нольдік элементтер санын тап.
   
4. 
   n * m өлшемді матрица берілген. b векторын алу керек, онда элементтер былай есептеледі: - сәйкес жолдардың элементтерінің көбейтіндісі; - сәйкес бағандардың арифметикалық ортасы; сәйкес жолдардың ең үлкен және ең кіші элементтерінің айырмасы; - бағандағы алғашқы теріс элементтердің мәндері.
   
5. 
   A[1..m,1..n] екі өлшемді массив берілген. Элементтері тең болатын B[1..m] бір өлшемді массивын жасау: - жолдардың элементтер қосындысына; - жолдардың элементтер көбейтіндісіне; - жолдардың элементтерінің арифметикалық орталарынына.
   
6. 
   Берілген массивте жұп орында тұрған элементтерді тақ орында тұрған элементермен орынын ауыстыру.
   
7. 
   Берілген массивтің элементтерін кері ретпен орналастыр (бірінші элементті соңғымен, екіншісін оның алдыңғысымен, т.с.с., егер, массив элементтерінің саны тақ болса, ортаңғысы өзгеріссіз қалады).
   

Тақырыбы:Ағаш типті мәліметтер құрылымдарын ұйымдастыру.

Тармақтың элементтері түйін деп аталады. Ағаш тәрізді құрылым түпкі деп аталатын алғашқы бір түйіннен басталатын көптеген түйіндер жиынтығын құрайды.

0-деңгей 1-деңгей 2-деңгей 3-деңгей

Мұнда ағаштың түбірі дегеніміз – ары қарай түбірі болмайтын төбесі, яғни мұндағы А. Әрбір тармақтың бір ғана түбірі болады. Тармақтың ең төменгі түйіндері E, F, G, H жапырақ деп аталады. Егер тармақтың элементі жапырақ болмаса, онда оны тармақтың ішкі түйіні немесе төбесі деп аталады. Бос тармақ дегеніміз – ешқандай төбесі жоқ тармақты атаймыз. Балалық төбесі деп – тармақта орналасқан өзінің ата-аналық төбесінен төмен қарай тұрған және онымен тікелей байланысқан төбені атаймыз. Мысалға, егер i төбесі F төбесіне қатысты балалық төбесі болса, онда F төбесі I төбесіне қатысты ата-аналық төбе деп аталады.

Балалық түйіндер және олардың балалық түйіндері ұрпақ деп аталады. Мысалға, E, F және I, J B – түйінінің ұрпақтары.

Тектері бұл түйіннің ата-аналары немесе ата-әжелері.

Тармақтың әрбір түйіні осы түйіннен және барлық ұрпақтарынан тұратын бұтақтың түбірі болып табылады. Мысалы, В төбесі E,F,I,J деңгейінің түйіні. Мысалға, F түйіні F,I,J түйіндерінен тұратын бұтақтың түбірі болып табылады. G түйіні ұрпақсыз бұтақтың түйіні. А түйіні өзі тармақ болып табылатын бұтақтың түбірі.

Кез келген түйіннен түйіннен бастап оның ұрпақтарына қарай жүру белгілі бір жол бойымен жүзеге асады. Мысалға, А түбірінен бастап F түйініне дейінгі жол A,B,F төбелерінен өтеді. Кез келген түйіннен оның ұрпақтарына баратын жол жалғыз ғана болады. Түйіннің деңгейі дегеніміз – ол түбірден осы осы түйінге дейінгі жолдың ұзындығы. Мысалға, А түбірінің деңгейі 0-ға тең. Түбірдің әрбір баласының деңгейі 1-ге тең. Мысалға F түйіні 2 деңгейдегі ұзындығы 2-ге тең түйін болып табылады.

Тармақтың тереңдігі дегеніміз – оның кез келген түйінінің максимальды деңгейі немесе тармақтың тереңдігі дегеніміз ол түбірден бастап түйінге дейінгі ең ұзақ жолдың ұзындығы.
Тармақ тәрізді құрылымды беру әдістері

Тармақтарды берудің 4 түрлі әдісі бар:

1. 
   графтар
   
2. 
   кірістірілген жақшалар
   
3. 
   кірістірілген жиындар
   
4. 
   кесінді тізбектер.
   

4. 
   Кірістірілген жиындар.
   

F J

D H

жұбы. Мұндағы V-төбелердің құр емес жиыны. E - қабырғалар жиыны. Яғни, төбелер жұбы немесе қабырғалары жиыны деп аталатын мәліметтер элементтері жиынынан тұрады. Төбелер қалаларды көрсететін болса, қабырғалар арасындағы жолдарды көрсетеді.

1250 900

450
Егер е жұптары реттелмеген болса, яғни жолдардағы қозғалыс екі бағытта да жүретін болса, онда граф бағдарланбаған әйтпесе бағдарланған деп аталады. Егер қабырғалардың бір бөлігі бағытталған немесе бағдарланған болса, мұндай графтар аралас графтар деп аталады.

V_1, V_{2, ...,} V_n төбелерінің тізімі жол деп аталады. Мұндағы барлық i үшін 1<=i<=n, V_i,V_i+1 қабырғалары болады.

Бағдарланған графта V_1, V_{2, ...,} V_n төбелердің тізімі.

V₁V₂, V₂ V₃,...,V_n-1 V_n бағытталған доға түрінде болады. Графтардағы жол қарапайым деп аталады, егер графтардың төбелері әртүрлі болса. Жолдың ұзындығы осы жолды құрайтын қабырғалардың санына тең болса.

V_i және V_j төбелері байланған деп аталады егер, осы төбелер үшін V_i+1,V_i+2,.., V_j жолы бар болса. Граф байланысшы граф деп аталады егер, оның кез келген төбелер жұптары үшін оларды қосатын қарапайым жол болса.

Цикл дегеніміз - ұзындығы бірден кем болмайтын бір төбеден басталып сол төбеден аяқталатын қарапайым жол.

Графтардағы тармақ дегеніміз – бұл циклсыз графтар. Графтар өлшенген деп аталады егер, графтың әрбір қабырғасына мәні немесе салмағы жазылса.

Мысалға, салмақ ретінде қалалардың арасындағы арақашықтық немесе қандай да бір жұмыстың жүргізілу уақыты алынады.

Графтарды берудің келесідей әдістері бар:

6. 
   Инцидиенттік матрицасы.
   
7. 
   Көршілестік матрицасы.
   
8. 
   Салмақтық матрицасы.
   
9. 
   Қабырғалар тізімі.
   
10. 
    Көршілестік тізімі.
    

Қандай да бір нақтылы есепті шығару үшін қолдану қолайлылығына қарай осы әдістердің кез келгенін пайдалануға болады.

жүктеу/скачать 1,51 Mb.

Достарыңызбен бөлісу: