Стектің логикалық құрылымы

МАЗМҰНЫ
КІРІСПЕ
І - ТАРАУ. ҚҰРЫЛЫМДАНҒАН МӘЛІМЕТ ТИПТЕРІ ТУРАЛЫ ЖАЛПЫ
1.1 Статикалық құрылым
1.2 Жартылай статикалық құрылым
1.3 Динамикалық құрылым
ІІ – ТАРАУ. MACROMEDIA FLASH ОРТАСЫНДА ЭЛЕКТРОНДЫ ОҚУЛЫҚ ЖАСАУДЫҢ
2.1 Оқу үрдісінде қолдануға арналған электронды оқу құралдары
2.2 Информатика сабағын электрондық оқытудың әдістемесі
2.3 Macromedia Flash анимациясы
2.4 Macromedia Flash көмегімен жасалған электрондық оқулық
ІІІ – ТАРАУ. ЕҢБЕКТІ ҚОРҒАУ
3.1 Еңбекті қорғау түсінігі
3.2 Жұмыс жасау кезіңдегі қауіпсіздік техникасы және еңбекті
3.3 Есептеуіш техникасымен жұмыс істеу кезіндегі
қауіпсіздік техникасы ережелері
3.4 Алғашқы медициналық көмек көрсету әдістері
ҚОРЫТЫНДЫ
ҚОЛДАНЫЛҒАН ӘДЕБИЕТТЕР ТІЗІМІ
ҚОСЫМША
КІРІСПЕ
Олар кез келген машиналық программаның базалық элементі бола алады.
Никлас Вирт
Мәлімет құрылымы және алгоритм ұғымдарынсыз программа құру мүмкін емес.
Мәлімет құрылымын жадыда физикалық деңгейде, т.б., және логикалық деңгейде,
физикалық және логикалық деңгейде оларға амалдарды қолдану;
алгоритмді өңдеуде құрылымның мағынасын көрсету.
Мәлімет құрылымы және алгоритм программаны құрайтын материалдарға жұмыс
Компьютер көмегімен шығарылатын есептер бит тілдерінде көрсетілуі сирек кездеседі.
Абстрактілі мәлімет құрылымдарын және программа алгоритмдерін сипатталуы программалық тілдерімен
Барлық программалық тілдер мәліметтер элементтеріне атау немесе идентификатор беріп
Константа және айнымалылардың атаулары программистке көмектеседі, бірақ компьютерге ол
Программалық тілдермен қабылданған мәлімет типтері натуралды және бүтін сандар,
Кейбір программалық тілдерде константа немесе айнымалы типтері компилятормен анықталады.
Программалық тілдерде типтерді қорғау компиляция этапында орындалады. Мысалы, мәлімет
Алғашқы алгоритмдер саналымды есептер типі үшін сандарды көбейту, ортақ
Алгоритмдерде қолданылатын мәлімет құрылымдары күрделі болуы мүмкін. Мәліметтің дұрыс
І - ТАРАУ. ҚҰРЫЛЫМДАНҒАН МӘЛІМЕТ ТИПТЕРІ ТУРАЛЫ ЖАЛПЫ ҰҒЫМ
1.1 Статикалық құрылым
Cтатикалық құрылым примитивті емес құрылымдар қатарына жатады. Өйткені, статикалық
Әрбір мәлімет құрылымы логикалық және физикалық деп ажыратылады. Әдетте
Программа тіліндегі статикалық құрылым құрылымданған типпен байланысты. Құрылымданған тип
Вектор
Логикалық құрылым. Вектор ( бір өлшемді массив ) –
Машиналық көрсетілім. Құрылым элементінің мекен – жайы. Вектор элементтері
Вектор Pascal программасында бір өлшемді жиым болып беріледі және
< атау >: array [n..k] of < тип >;
N – алғашқы элемент номері, ал к – соңғы
+0 +Sizeof(тип)
Атау [n] Атау [n+1]
+0 +Sizeof(тип)
Атау [n] Атау [n+1]
@ аты
@ аты – вектордың немесе сол сияқты вектордың бірінші
Мысалы: var m1: array[-2..2] of real;
Берілген вектордың жадыдағы көрінісі:
+0 +6 +12 +18 +24
m1[-2] m1[-1] m1[0] m1[1] m1[2]
m1 (байт) мекен-жайына сәйкес келетін
элемент
массив элементінің мағынасы
C, Pascal, Fortran программалық тілдерінде компиляция кезінде жады программа
Pl/1, ALGOL программалық тілдерінде жады динамикалық түрде бөлінгенде индекс
Бір уақытта вектормен толы үздіксіз жады облысындағы байт саны
ByteSize=(k-n+1)*Sizeof(тип)
Вектордың k, i элементін табу үшін вектор мекен –
ByteNumer = ( i- n ) * Sizeof (тип),
Мекен - жайы: @ ByteNumber = @ аты +
@ атауының вектордың бірінші элементінің мекен – жайы:
var МAS: array [ 5..10 ] of
Word – вектор элементінің базалық типі 2 байтты талап
@ Mas вектор элементтерінің кестесі мынандай түрде болады.
(байт) араласуы + 0 + 2 + 4 +
өріс идентификаторы MAS[5] MAS[6] MAS[7] MAS[8] MAS[9] MAS[10]
Бұл вектор жадыда орындалады: (10-5+1)+2=12 байт
Вектор элементінің 8 номермен жиыны: (8-5)+2=6
8 номерлі элемент мекен-жайы: @ Mas+6
Векторға қол жеткізуде вектор атауы және элемент номері беріледі.
@Аты[i] = @Аты + i*Sizeof(тип) - n*Sizeof(тип)
Бұл анықталым компиляция кезінде орындалмайды, өйткені i ауысымы белгісіз.
@аты[i] = A0 + i*Sizeof(тип) --
A0 = @аты - n*Sizeof(тип) --
Сақталынған параметр санын екіге дейін қысқартып, ал операция санын
Сонымен дескриптор векторында сақталынған ақпарат біріншіден қол жеткізудің уақытын
Дескрипторда векторсыз жұмыс істеуге бола ма?
Мысалы, С программалау тілінде декриптор векторы жоқ, яғни программа
@аты[i] = @аты + i*Sizeof(тип)
С программалау тілінде жұмыс істеуге әдеттенген программистер атау [i]
Біріншіден, алғашқы индексті таңдауды шектеу программист үшін қолайсыздық тудырады,
Жиымдар
Логикалық құрылым.
Жиым – мәлімет құрылымы, келесі түрде сипатталады:
бір типке жататын фиксирленген элемент тобы
әрбір элементте өзіне сәйкес ерекше индекс тобы болады
индекс саны жиым тобын анықтайды, мысалы, екі индекс –
жиым элементін шақыру жиым атымен және берілген элементтің индексі
Басқа анықтама: жиым – бұл вектор, әрбір элементі –
Жиым сипаттамасы:
< аты > : Array [n1..k1] [n2..k2] ..
Екіөлшемді жиым:
Mas2D : Array [n1..k1] [n2..k2] of < Тип >,
Mas2D : Array [n1..k1 , n2..k2] of < Тип
Екіөлшемді массивті кесте түрде көрсетуге болады: (k1-n1+1) жол және
Физикалық құрылым. Физикалық құрылым – бұл ЭЕМ жадысында жиым
Көпөлшемді жиымдар жадының шексіз облысында сақталады. Слот өлшемі жиым
Екіөлшемді жиымның жадыда байттар санын анықтайтын формула:
ByteSize = (k1-n1+1)*(k2-n2+1)*SizeOf(Тип)
Массив мекен – жайы жиымның алғашқы компонентінің бірінші байт
@ByteNumber = @mas + ByteNumber.
Мысалы:
var Mas : Array [3..5] [7..8] of
Word базалық тип элементі жадыдан 2 байт талап етеді,
(байт) араласуы өріс идентификаторы (байт) араласуы өріс идентификаторы
+ 0 Mas[3,7] + 2 Mas[3,8]
+ 4 Mas[4,7] +6 Mas[4,8]
+ 8 Mas[5,7] + 10 Mas[5,8]
Бұл жиым жадыда: (5-3+1)*(8-7+1)*2=12 байт, ал Mas [4,8] элемент
@Mas+((4-3)*(8-7+1)+(8-7)*2 = @Mas+6
Қолданылатын амалдар.
Жиымға қолданылатын физикалық құрылымның маңызды амалы – берілген элементке
(3), (4) формуласы сәйкесі және (1), (2) вектор аналогы
[B(1)..E(1)][B(2)..E(2)], жадыда жол бойынша орналасқандар, индекстері бар элемент мекен
Addr[I(1),I(2)] = Addr[B(1),B(2)] +
{ [I(1)-B(1)] * [E(2)-B(2)+1] + [I(2)-B(2)] }*SizeOf(Тип)
Mas[B(1)..E(2)][B(2)..E(2)]...[B(n)..E(n)]
алынады:
Addr[I(1),I(2),...,I(n)] = Addr[B(1),B(2),...B(n)] -
n
- Sizeof(Тип)*СУММА[B(m)*D(m)] + Sizeof(Тип)*СУММА[I(m)*D(m)]
m=1
мұнда Dm жиымға тәуелді жол бойынша орналасуы :
D(m)=[E(m+1)-B(m+1)+1]*D(m+1), мұнда m = n-1,...,1 және
Баған бойынша орналасуы:
D(m)=[E(m-1)-B(m-1)+1]*D(m-1), мұнда m = 2,...,n және
Элементтің мекен – жайын анықтауды ең қиыны үшінші (6)
бастапқы жиым мекен – жайы Addr[I(1),I(2),...,I(n)]
жиым өлшем саны – n
тұрақты минеризациялау формуласын құрайтындар. (6) формуланы құрайтын алғашқы екеуі
жиымдағы n – нің әрбіреуі
шекаралық индекс мәні – B(i), E(i)
жиым формуласын минеризациялау – D (i)
Жиымның бір анықтамасында айтылады: вектор, оның әрбір элементі
Мысалы: егер PL/1 программасындағы екіөлшемді жиым:
Declare A(10,10) BINARE FIXED;
онда: A(1,I), A(2,I), …, A(10, I) элементтен тұратын
Джокер символы «*» берілген джокер индексіне сәйкес келетін, өлшемге
Мысалы: A(*,I) = A(*,I) + 1
Жиымға қолданатын логикалық деңгейдегі амалдарға жиымды сорттау, кілт бойынша
Айлифф векторы көмегімен табылатын элемент мекен – жайы.
Жоғары көрсетілген формулаларға қарағанда көпөлшемді жиымның элемент мекен –
пайдаланса.
Бірінші деңгейдегі Айлифф векторы
Негізгі дескриптор
.
.
.
(В)
.
.
.
j1
Екінші деңгейдегі
Айлифф векторы
-1
0
1
-1
0
1
j2
B(4,-1,0) B(4,
-1,1) B(4,0,0) B(4,0,1) B(4,1,0) B(4,1,1) B(5,-1,0) B(5,-1,1) B(5,0,0) B(5,0,1)
0 1 0 1 0 1 0 1 0
1.1.1 сурет. Айлифф вектордың көмегімен көрсетілген жиым көрінісі
Кез келген өлшемдегі жиым үшін дескриптор жиыны құралады: негізгі
Берілген Айлифф әдісі бойынша алдыңғы суретте В [4..5,-1..1,0..1] үшөлшемді
Арнайы жиымдар.
Тәжірибеде жиымдардың белгілі бір себептерге байланысты жадыға толық емес,
Симметриялы жиым
Егер екіөлшемді жиымның жол саны мен баған саны тең
Тәжірибе арқылы жұмыс істеу үшін симметриялы матрицаның процедуралары келесіге
а) матрица индекстерінің вектор индекстеріне ауысуы.
ә) вектордың формальдануы және оған жоғарғы үшбұрыштың элементтерін, кірісті
б) жинақталған көріністен матрица элементтің сипаттамасын алу. Мұндай кірісті
Қиылған жиым
Қиылған жиым – көптеген элементтері өзара тең, сондықтан да
Қиылған жиымның 2 түрі бар:
математикалық бейнеленген фондық сипаттаудан ерекшеленетін элемент мекен – жайы
кездейсоқ орналасатын элементті жиым.
Жұмыс істеу кезінде қиылысқан жиымды жадыда орналасу сұрағы логикалық
Математикалық сипатталған жиымның фондық емес элементтердің мекен – жайы.
Осы жиымның түріне жататын жиымдардың орналасуы фондыққа қарағанда мағынасына
Фондық мағынасы бар элемент нольдік деп аталады. Ал фондыққа
Нольдік емес атаулар бірөлшемді жиымға сақталынады. Ал олардың кірістегі
Тәжірибеде қиылған жиыммен жұмыс жасауда келесі функциялар жасалған.
а) жиым индексін вектор индексіне өңдеу үшін
ә) ойша қорапталған 2 индекстен жиым элементін алу үщін
б) ойша қорапталған 2 индекстен жиым элементтерін жазу үшін.
Кірісті жиымдар элементтеріне назар аударуы берілген функция көмегімен орындалады.
{===== Программалық мысал 3.1 =====} Unit ComprMatr;
Interface
Function PutTab(y,x,value : integer) : boolean;
Function GetTab(x,y: integer) : integer;
Implementation
Const XM=...;
Var arrp: array[1..XM*XM div 2] of integer;
Function NewIndex(y, x : integer) : integer;
var i: integer;
begin NewIndex:=((y-1)*XM+x) div 2); end;
Function PutTab(y,x,value : integer) : boolean;
begin
if NOT ((x mod 20) and (y mod 20))
NOT ((x mod 2=0) and (y mod 2=0))
arrp[NewIndex(y,x)]:=value; PutTab:=true; end
else PutTab:=false;
end;
Function GetTab(x,y: integer) : integer;
begin
if ((x mod 20) and (y mod 20)) or
((x mod 2=0) and (y mod 2=0)) then GetTab:=0
else GetTab:=arrp[NewIndex(y,x)];
end;
end.
Мұндай матрица arrp векторында сақталады.
New Index функциясы сығылған көріністегі бір элементті х,у
Екіөлшемді матрицада индекс бойынша элементке қол жеткізу үшін
Назар аударатын жағдай, arrp жиымы, New Index функциясы
3.2 программалық мысалды есеп басқа жолмен шығарылады: матрица үшін
{==== Программалық мысал 3.2 =====}
Unit ComprMatr;
Interface
Function PutTab(y,x,value : integer) : boolean;
Function GetTab(x,y: integer) : integer;
Procedure InitTab;
Implementation
Const XM=...;
Var arrp: array[1..XM*XM div 2] of integer;
desc: array[1..XM] of integer;
Procedure InitTab;
var i : integer;
begin
desc[1]:=0; for i:=1 to XM do desc[i]:=desc[i-1]+XM;
end;
Function NewIndex(y, x : integer) : integer;
var i: integer;
begin NewIndex:=desc[y]+x div 2; end;
end.
Кездейсоқ орналасқан элементі бар қиылған массивтер.
Мұндай жиымдарға орналасуы фондыққа қарағанда ерекшілігі бар элементтер, математикалық
Ё 0 0 6 0
Ё 2 0 0 7
Ё10 0 0 0 0
Ё 0 0 12 0 0
Ё 0 0 0 3
5х7 өлшемді А матрицасы берілсін, мұнда 35 элемент, 10-ы
Кезекпен орналасу әдісі бойынша қиылған матрица көрінісі.
Қиылған матрицаның сақталуының негізгі әдісінің бірі бірөлшемді жиымдағы элементтердің
А массивінің элементінің і және j индекстеріне қол жеткізу
5б суретінде матрица жолынақол жеткізудің уақыт және жады талабына
5 суреттегі А матрицасы жады көлеміне деген талабын 2
Қиылған матрицаның құрылым байланысы әдісі бойынша көрінісі.
Қиылған матрица үшін кезекпен орналасу әдісі әдетте матрицаға орындалатын
Құрылым байланыс әдісі берілген мәлімет құрылымын басқа классификацияға ауыстырады.
K row
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10
3
5
1
4
5
7
1
3
4
7
6
9
2
7
8
4
10
12
3
5
3
5
1
4
5
7
1
3
4
7
6
9
2
7
8
4
10
12
3
5
1
2
3
4
5
6
7
8
9
10
row
i
1
3
7
8
9
1
2
3
4
5
Жолдар номері
а) б)
1.1.2 сур. Қиылған матрицаның құрылым байланысы әдәсә бойынша көрінісі.
Қиылған матрицаның көрінісі үшін MATRIX_ELEMENT (« матрица элементі »)
1.1.3 сур. Қиылған матрица көрінісі үшін ең жоғарғы формат.
7 суретте жоғары пункте сипатталғандай А матрицасы үшін ең
Баған тізімі жоғарғы шыңмен бірге жол тізімінде құрауы мүмкін.
Қос және өшіру алгоритмдерін қолдану үшін барлық жолдар және
Көпбайланысты құрылымның бағыты жоғарғы және солға нұсқауы қызық болып
1.1.4. сурет
Жиын
Логикалық құрылым. Жиын – бір типке жататын қайталанбайтын мәлімет
Физикалық құрылым. Жиын жадыда жиым биті секілді сақталынады. Мұнда
Жиынның мәлімет типі үшін бөлінгетін байт санын анықтайтын формула:
Е элементі үшін байт номерін анықтайтын формула:
ByteNumber = (E div 8)-(min div 8),
Бит номерінің осы ішкі байт формуласы:
BitNumber = E mod 8
{===== Программалық мысал 3.3 =====}
const max=255; min=0; E=13;
var S : set of byte;
ByteSize, ByteNumb, BitNumb : byte;
begin
S:=[];
S:=S+[E];
ByteSize:=(max div 8)-(min div 8)+1;
Bytenumb:=(E div 8)-(min div 8);
BitNumb:=E mod 8;
writeln(bytesize); {
writeln(bytenumb); {
writeln(bitnumb); {
end.
Сандық жиындар
Byte типі – стандарттық сандық тип, ол жиынның формальдануы
3 кестеде жиынның сақталуы көрсетілген.
(байт) араласуы Машина жадындағы байт көрінісі
( номер разряды)
@S+0
………………………….
@S+0
7
6
5
4
3
2
1
0
…………………………………………………......
255
254
253
252
251
250
249
248
7
3 - кесте.
@S – жиынның мәлімет типінің мекен – жайы. Егер
Мысалы, S : set of byte;
Бұл жағдайдағы жады мазмұны:
@S+0 - 00000000 @S+2
@S+1 - 10000000 .
@S+31 – 00000000
Символдық жиындар
Символдық жиындар жадыда сандық жиындар секілді сақталады. Бірақ мұнда
Мысалы, S : set of char; S:=['A','C'];
Бұл жағдайда S жиынның жадыда сақталуы келесідей:
@S+0 - 00000000
. . . . .
@S+8 - 00001010
Саналатын типтер элементінен тұратын жиындар.
Саналатын типі бар базалық типті жиын. Byte типі болатын
Мысалы:
Type
Video=(MDA,CGA,HGC,EGA,EGAm,VGA,VGAm,SVGA,PGA,XGA);
Var
S : set of Video;
Жадыда орын алады:
ByteSize = (9 div 8)-(0 div 8)+1=2 байт
8 суретте ауысымды S үшін жадының бөлінуі
1.1.5 сур. set of Video ауысым типі үшін жадыдан
Егер S:=[CGA,SVGA] операторы орындалса, онда жады мазмұны былай болады:
@S+0 - 10000010
@S+1 - 00000000
Интервалды типті жиын.
Интервалды типі бар базалық типті жиын секілді сақталады. Жарияланған
Мысалы:
type S=10..17;
var I: set of S;
Алғаш қарағандағы секілді бірінші элемент оннан немесе нольді биттен
Бұл жиын 1.1.6 суреттегі көріністе.
1.1.6 сур. Set of S ауысымды типтің көрінісі.
Жиынды құрастыруда интервалды тип үнемді және берілген шекараға байланысты
Мысалы:
Type S = 510..520;
Var I : S;
begin I:=[512]; end.
Ауысымды І – дің жадыдағы көрінісі:
@i+0 - 00000000 @i+1 – 00000001
Жиындарға қолданатын амалдар
S1, S2, S3: set of byte болсын. Осы жиынға
Жиындарды біріктіру: S1 + S2 екі жиын элементрерінің жиыны.
Жиындарды қиылыстыру: S1*S2 екі жиынның ортақ элементтері.
а in S1: жиын элементтерінің тиістілігінің тексерілуі: егер элемент
Жазба
Жазбаның логикалық және машиналық бейнеленуі.
Жазба - әртүрлі мәлімет типін сипаттайтын реттелген жиын өрістері.
Берілген мысал – студент мәлімет.
Объект « студент » келесі қасиеттерге ие:
«жеке номер» - оңтайлы санмен сипатталған
« аты – жөні » - жол символымен
мысалы: var
rec:record
num :byte;
name :string[20]; { аты –жөні
fac, group:string[7]; { факультет, топ
math,comp,lang :byte;
end;
Бұл құрылым жадыда екі түрдің біреуінде сипатталуы мүмкін:
а) (1.1.10 сур.) жадының үздіксіз облысын қамтитын кезектес өрістер.
1.1.10 сур.Жадыдағы ауысымды record типінің кезектес
өріс түріндегі көрінісі.
ә) өріс жазбаларының атауларын нұсқайтын байланысқан тізім түрінде. Мұндай
Ескерту: Жадыны үнемдеу үшін дескриптордағы нұсқағыштардың орнына сәйкесінше әрекеттер
С программалау тілі дескриптордағы жазбаны программа орындалғанға дейін сақталмайды.
Интегралданған мәлімет құрылымдары өріс жазбасы бола алады, яғни олар
Жазба дескрипторы
rec
student
7
Byte
1
Num
String
21
Name
String
8
Fac
String
8
Group
Byte
1
Math
Byte
1
Comp
byte
1
lang
өріс жазбаның нұсқауышы
1.1.11 сур. Жадыдағы ауысымды record типінің байланысқан тізбек түріндегі
Өріс жазбасы басқа жазба болуы мүмкін. Міндетті түрде өзі
type rec = record
f1 : integer;
f2 : char[2];
f3 : rec; end;
Компилятор мұндай жазба үшін қалай жадыны бөледі. f1 өрісі
Бірақ жазба өрісі болып осындай секілді басқа жазбаны нұсқайтын
Бұл әдіс прогрммалауда бір типті жазбалар арасында байланыс орнатуды
Жазбаға қолданылатын амалдар.
Квалификация амалы – жазба үшін таңдалынған өріс жазбасына қол
< ауысымды жазбаның атауы>. < өріс атауы>
Stud1.num және Stud1.math констркциялары сәйкесінше num және math
Таңдалынған өрістердің типіне қарай кез келген амалдар орындалады.
Көптеген программалық тілдер жеке өрістермен емес, жалпы жазбамен жұмыс
Нұсқаулары бар жазбалар.
Программамен қолданбалы есептер қатарында объект тобымен соқтығысуы мүмкін. Егер
Мұндай программалық тілдердің дамуы программистке нұсқаулары бар жазбаларды ұсынвды.
< ауысымды жазбаның атауы>. < өріс атауы>
Екінші жағдайда идентификация қиындайды.
< ауысымды – жазба аты >
Мысалдағы нұсқаулары бар жазбаны қарастырайық. Видеотерминал экранында қарапайым геометриялық
Кез келген фигураны сипаттау үшін ол сүйеніш нүктелері бар
Шеңбер үшін радиус, тіктөртбұрыш үшін параллель емес жақтар ұзындығы,
Pascal тілінде нұсқаулары бар жазба үшін есеп былай сипатталады.
type figure = record
fig_type : char; { фигура түрі
x0, y0 : word;
color : byte;
case fig_t : char of
'C': ( radius : word);
'R': (len1, len2 : word); { тіктөртбұрыш жақтарының
'T': (x1,y1,x2,y2 : word); { екі төбе координаталары }
end;
С программалау тілінді:
typedef struct
{ char fig_type;
unsigned int x0, y0; /* сүйеніш нүктенің координаталары */
unsigned char color; /* түс */
union
{ struct
{ unsigned int radius; /*
} cyrcle;
struct
{ unsigned int len1, len2; /* тіктөртбұрыш жақтарының
} rectangle;
struct
{ unsigned int x1,y1,x2,y2; /* екі төбе координаталары */
} triangle;
} fig_t;
} figure;
Шеңбер сипатталуы сақталатын программада figure типінің fig1 ауысымы анықталса,
Fig_type атауы бар өріс фигураларды идентификациялауға арналған. Мыс: «С»
Нұсқаулары бар жазба үшін жадыдан орын бөліну 12 суретте
Суретте көрсетілгендей нұсқаулары бар жазбаасты үшін ең үлкен нұсқаудың
Шеңбер тіктөртбұрыш
1.1.12 сур. Нұсқаулары бар жазбалары үшін жадыдан орын бөлінуі.
Кестелер.
Жазба туралы сөз болғанда, яғни жазба өрісі интегралданған мәлімет
Кестемен жұмыс істеу кезінде кілт бойынша жазбаға қол жеткізу
Кейде кестені фиксирленген және ауысымды жазба ұзындығымен айырады. Идентивті
Ауыспалы ұзындықтағы жазбалы кесте есепті программалауда,ғы машиналық кодтауда қолданылады.
Жартылай статикалық құрылым
Жартылай статикалық құрылымның ерекшілігі.
Жартылай статикалық құрылымның келесі белгілері бар:
оларда ауысымды ұзындық және қарапайым процедура
максимальды атау артпай, анықталған бөлімде құрылым ұзындығының ауысуы
Егер жарты статикалық құрылымды логикалық деңгейде қарастырылса, онда ол
Стектар
Стектің логикалық құрылымы.
Стек – ауыспалы ұзындығы бар кезектелген тізім. Стек шыңы
Стек үшін негізгі амал – жаңа элемент қосу (
Қосымша амалдардың да көмегі болуы мүмкін:
стекта ағымдағы элемент санын анықтау
стекті тазалау
негізгі амал комбинациясы секілді өнделетін стек шыңынан элемент оқуы
х:=pop(stack); push(stack,x)
Түсінікті болу үшін кішігірім мысал қарастырайық: стектен элементтің қосылу
а) босты
б – г) ‘A’ ‘B’ ‘C’ атты элементті кезектен
д – е) ‘C’ ‘B’ элементтерін стектен кезектен кейін
ж) ‘D’ элементін стекке қосу
1.1. суретте көрсетілгендей стекті үстелдегі кітап тобын
Стек шыңы
1.2.1. сурет Стектан элементті қосу алу
Стектің машиналық көрсетілімі және амалдардың орындалуы
Стектің көрінісі үшін статикалық жадыдан вектор секілді жады бөлінеді.
Стекке элементті қосарда нұсқауыш нұсқайтын орынға жазылады, содан кейін
Стектен элемент алу амалы стек нұсқауышының модификациясынан құралады және
Стекті тазалау амалы – алғашқы атаудың стектегі нұсқауыш жазбасына
Стектің өлшемі нұсқауыштардың әр түрлігінің есептеліне келеді.
4.1 мысалды мекен – жайдың кішіреюінеи қарай орындалатын амал
4.1 және 4.3 мысалдарында модульде құрылым элементі үшін мәлімет
const SIZE = ...;
type data = ...;
{==== Программалық мысал 4.1 ====}
{ Стек }
unit Stack;
Interface
const SIZE=...; { стек өлшемі
type data = ...; { элемент
Procedure StackInit;
Procedure StackClr;
Function StackPush(a : data) : boolean;
Function StackPop(Var a : data) : boolean;
Function StackSize : integer;
Implementation
Var StA : array[1..SIZE] of data; {
{ стек шыңынын нұсқауышы }
top : integer;
Procedure StackInit;
begin top:=SIZE; end;
Procedure StackClr;
begin top:=SIZE; end;
{ ** стекке элемент енгізу }
Function StackPush(a: data) : boolean;
begin
if top=0 then StackPush:=false
else begin { енгізу, содан кейін нұсқауышты ұлғайту }
StA[top]:=a; top:=top-1; StackPush:=true;
end; end;
{ ** стек элементін таңдау }
Function StackPop(var a: data) : boolean;
begin
if top=SIZE then StackPop:=false
else begin { нұсқауыш ұлғаяды содан кейін таңдау }
top:=top+1; a:=StA[top]; StackPop:=true;
end; end;
Function StackSize : integer; {**
begin StackSize:=SIZE-top; end;
END.
Есептеуіш жүйедегі стектер.
Есептеуіш техниканың көптеген есептері үшін стек мәлімет құрылымы ыңғайлы
Мысалы, А процедурасы болсын, ол В процедурасын шақырады, ал
Көптеген жаңартылған микропроцессорларда стек аппараты бар. Аппаратты стек ОЗУ
Көптеген (Pascal, C т.б.) программмалық тілдер стекті оған локальды
Бұл әдіс ресурсты процедураны тез өңдейді. Процедура өзін
Рекурсивті процедуралар стекта рекурсиясыз өңделе алады. 3.17 мысалда рекурсивті
{==== Программалық мысал 4.2 ====}
{ тездетілген Хоара сұрыпталуы (стек) }
Procedure Sort(a : Seq); { 3.8
type board=record
i0, j0 : integer; end;
Var i0, j0, i, j, x : integer;
flag_j : boolean;
stack : array[1..N] of board; { стек
stp : integer; { стек нұсқауышы
begin { стекке ортақ шекаралар кіреді. }
stp:=1; stack[i].i0:=1; stack[i].j0:=N;
while stp>0 do
begin i0:=stack[stp].i0; j0:=stack[stp].j0; stp:=stp-1;
i:=i0; j:=j0; flag_j:=false;{ i0 – дан j0-ға қарай
while ia[j] then
begin x:=a[i]; a[i]:=a[j]; a[j]:=x; flag_j:= not flag_j;
end;
if flag_j then Dec(j) else Inc(i);
end; if i-1>i0 then {сол жақ бөліктен
begin stp:=stp+1; stack[stp].i0:=i0; stack[stp].j0:=i-1;
end; if j0>i+1 then { оң жақ бөліктен стекке
begin stp:=stp+1; stack[stp].i0:=i+1; stack[stp].j0:=j0;
end; end;
FIFO кезегі
Кезектің логикалық құрылымы
FIFO кезегі деп ( First – In – Fist
FIFO кезегіне қолданылатын амалдар стекке қолданылатын амалдар сияқты.
FIFO кезегінің машиналық көрсетілімі және амалдардың өңделуі.
Статикалық жадыда кезекті вектормен көрсеткенде вектор параметрдің дескрипторы үшін
Кезекке элемент қосуда кезектің соңын нұсқайтын нұсқауыш жадыда кезек
Кірісті жағдайда басы және соңы нұұсқауыштары жады аймағының басын
4.3 программалық мысалында кезектің ұйымдастырылуы және оған орындалатын амалдар
{==== Программалық мысал 4.3 ====}
unit Queue;
Interface
const SIZE=...;
type data = ...;
Procesure QInit;
Procedure Qclr;
Function QWrite(a: data) : boolean;
Function QRead(var a: data) : boolean;
Function Qsize : integer;
Implementation
var QueueA : array[1..SIZE] of data; {
top, bottom : integer; { басы және
Procedure QInit;
begin top:=1; bottom:=1; end;
Procedure Qclr;
begin top:=bottom; end;
Function QWrite(a : data) : boolean; {**
begin
if bottom mod SIZE+1=top then { кезек толды }
else begin
{ жазба, сақина бойымен соңын нұсқайтын нұсқауыштың
Queue[bottom]:=a; bottom:=bottom mod SIZE+1; QWrite:=true;
end; end; { QWrite }
Function QRead(var a: data) : boolean; {** басынан
begin
if top=bottom then QRead:=false else
{ жазба, сақина бойымен басын нұсқайтын нұсқауыштың
begin a:=Queue[top]; top:=top mod SIZE + 1; QRead:=true;
end; end; { QRead }
Function QSize : integer; {** өлшемді
begin
if top