Дизимлер үстиндеги әмеллерге байланыслы мәселелер
1 Мәселе.
Ойлайық дизимди тексерип, онда информациялық майданы 4 ке тең болған элементлерди өшириў талап қылынған болсын.
Р арқалы жумысшы көрсеткишти белгилеп аламыз, процедура басында P = Lst. Сондай Q көрсеткиш киритемиз, ол Р дан бир элемент кейинде жүрсин. Р көрсеткиш керекли элементти тапқанда усы элемент Q ге салыстырғанда нәўбеттеги элемент сыпатында өшириледи.
Q = Nil
P = Lst
While P <> Nil do
If Info(P) = 4 then
If Q = Nil then
Pop(Lst)
FreeNode(P)
P = Lst
Else
DelAfter(Q, X)
EndIf
Else
Q = P
P = Ptr(P)
EndIf
EndWhile
2 Мәселе.
Информациялық майданы өсиў тәртибинде тәртиплестирилген дизим берилген болсын. Усы дизимге информациялық майданы Х қа тең болған сондай элемент қосыў талап қылынады, пайда болған дизимде тәртипленгенлик бузылмасын.
Ойлайық X = 16 болсын. Басланғыш шәртлер: Q = Nil, P = Lst. Жаңа элемент 3-ши ҳәм 4-ши элементлер арасына қойылыўы лазым болсын (жоқарыдағы сызылма).
Q =Nil
P = Lst
While (P <> Nil) and (X > Info(P)) do
Q = P
P = Ptr(P)
EndWhile
if Q = Nil then
Push(Lst, X)
EndIf
InsAfter(Q, X)
Келтирилген мысалларды Паскал тилинде реализация қылыў:
1-мәселе:
Q:=nil;
P:=Lst;
While P <> nil do
If P^.Info = 4 then
begin
If Q = nil then
begin
Pop(Lst);
P:=Lst;
end
Else Delafter(Q,X);
End;
Else
begin
Q:=P;
P:=P^.Next;
end;
end;
2-мәселе:
Q:=nil;
P:=Lst;
While (P <> nil) and (X > P^.Info) do
begin
Q:=P;
P:=P^.Next;
end;
{Усы жерге элемент қойылады}
If Q = nil then Push(Lst, X);
InsAfter(Q, X);
End;
Сызықлы емес байланысқан структуралар
Егер екинши көрсеткишлер элементлердиң қәлеген тәртибин анықласа, ол жағдайда еки бағытлы дизимлер де сызықлы емес байланысқан структура болады (сызылма).
LST1 – 1-ши дизим басына көрсеткиш (P1 көрсеткиш пенен бағдарланған). Ол сызықлы болып, 5 элементтен ибарат.
2-ши дизим тап сол элементлерден ибарат болып, лекин олар тәртиби қәлеген избе—излик формасында. 2-ши дизим басы 3-ши элемент болып ақыры 2-ши элемент есапланады.
Улыўма жағдайда дизим структурасындағы элемент көплеген көрсеткишлерге ийе болыўы мүмкин, яғный қәлеген сандағы элементлерге бағдарланған болыўы мүмкин.
Сызықлы емес структураның 3 парқлы белгисин ажыратыў мүмкин:
1) Структураның ҳәр бир элементи басқа қәлеген элементке мүрәжәт қылыў мүмкин, яғный қәлеген сандағы көрсеткишлер майданына ийе болыўы мүмкин.
2) Структураның берилген элементине усы структураның қәлеген сандағы элементи мүрәжәт қылыўы мүмкин.
3) Мүрәжәтлер аўырлыққа, яғный мүрәжәтлер иерархик көриниске ийе болыўы мүмкин.
Ойлайық, граф көринисиндеги дискрет система берилген болсын. Бул жерде граф түйинлери бул жағдайлар, жақлары бир жағдайдан екинши жағдайға өтиў ( қараң, сызылма).
Системаға кириў сигналы бул X. Кириў сигналына тәсир (реакция) Y шығыў сигналын пайда етиў ҳәм сәйкес жағдайға өтиў болып есапланады.
Дискрет система граф жағдайын сызықлы емес еки бағытлы дизим көринисинде сүўретлеў мүмкин. Бунда информациялық майданға система жағдайы ҳәм жақлары ҳаққындағы мағлыўматлар жазылады. Элемент көрсеткишлери система жақларын логикалық қәлиплестириўи керек (қараң, сызылма).
Жоқарыда келтирилгенлерди әмелге асырыў ушын төмендегилер орынланыўы керек:
1) Система (1, 2, 3) жағдайын сәўлелендириўши дизимлер жаратылыўы лазым;
2) Сәйкес жағдайлардан жақлар бойынша өтиўди сәўлелендириўши дизимлер жаратылыўы лазым.
Улыўма жағдайда көп бағытлы структураларды әмелге асырыў нәтийжесинде тор (сеть) пайда болады.
Қадағалаў сораўлары.
Қандай динамикалық түрлерди билесиз?
Динамикалық объектлердиң өзине тәнлиги неден ибарат?
Динамикалық структурада элементлер қандай байланысқан?
Бир бағытлы дизимлердиң өзине тәнлиги нелерден ибарат?
Сызықлы дизимлердиң ҳалқа тәризли дизимлерден парқы?
Не себептен еки бағытлы дизимлер керек?
Бир бағытлы дизимлердеги әмеллер менен еки бағытлы дизимлердеги әмеллердиң парқы?
Көрсеткиш не?
Дизим үстинде қандай стек әмеллерин орынлаў мүмкин?
Дизим үстинде қандай нәўбет әмеллерин орынлаў мүмкин?
Getnode ҳәм Freenode әмеллери неге арналған?
Элементлерди утилизация қылыўдың қандай усылларын билесиз?
Бир бағытлы дизимге элемент киритиў оның элементлери санына байланыслыма?
Элемент қосыў яки шығарыў процесси қайсы жағдайда нәтийжелирек: дизимде яки массивте?
Бир бағытлы дизимде элементлерди көриў қандай әмелге асырылады?
AVAIL нени аңлатады?
Массивке салыстырғанда бир бағытлы дизимниң кемшилиги неден ибарат?
Қандай структуралар сызықлы емес есапланады?
Сызықлы емес структуралардың өзине тәнлиги неден ибарат?
Сызықлы емес байланысқан структураларды қандай пайда етиў мүмкин?
Граф жағдайы не?
6-Лекция. Рекурсив мағлыўматлар структурасы (4 саат)
Реже:
Рекурсия ҳаққында түсиник.
Тереклер. Оларды сүўретлеў.
Бинар тереклер.
Көп өлшемли теректи бинар көриниске келтириў.
Тереклер үстиндеги әмеллер.
Рекурсив алгоритм ҳәм рекурсив мағлыўматлар структураларын көрип шығайық.
Рекурсия – сондай процесс, бунда процесстиң барыўы өзине мүрәжәт қылыў менен байланыслы болады..
Рекурсив мағлыўматлар структурасына мысал қылып сондай структураларды алыў мүмкин, усы структуралардың элементлериниң өзи де тап сондай структура болады (қараң, сызылма).
Тереклер
Терек – бул сызықлы емес байланысқан мағлыўматлар структурасы (қараң, сызылма).
Терек ўзининг төмендеги белгилери менен классификацияланады:
- теректе сондай бир элемент бар, оған басқа элементлерден мүрәжәт жоқ. Усы элементке терек тамыры делинеди;
- теректе қәлеген элементке шекли сандағы көрсеткишлер жәрдеминде мүрәжәт қылыў мүмкин;
- теректиң ҳәр бир элементи тек ғана өзинен алдыңғы келген бир элемент пенен байланысқан. Теректиң ҳәр бир түйини аралық яки терминал (жапырақ) болыўы мүмкин. Жоқарыдағы сызылмада M1, M2 - аралық, A, B, C, D, E - жапырақлар. Терминал түйинниң өзине тән классификациясы оның шақалары жоқлығында.
Бәлентлик – бул терек басқышы саны. Жоқарыдағы сызылмадағы терек бәлентлиги екиге тең.
Терек түйинлеринен шығып атырған шақалар саны түйиннен шығыў дәрежеси делинеди (Келтирилген сызылмада M1 ушын шығыў дәрежеси 2, М2 ушын болса 3 ке тең). Тереклер шығыў дәрежеси бойынша классларға ажыратылады:
1) егер максимал шығыў дәрежеси m болса, ол жағдайда бундай терек m-ши тәртипли терек делинеди;
2) егер шығыў дәрежеси 0 яки m болса, ол жағдайда толық m-ши тәртипли терек болады;
3) егер максимал шығыў дәрежеси 2 болса, ол жағдайда бундай терек бинар терек делинеди;
4) егер шығыў дәрежеси 0 яки 2 болса, ол жағдайда толық бинар терек делинеди.
Түйинлер арасындағы байланыслылықты классификациялаў ушын және төмендегише терминнен пайдаланылады: М1 – А ҳәм В элементлер ушын “ата” . А ҳәм В – болса М1 түйин “балалары”.
Тереклерди сүўретлеў
Теректиң графикалық формадағы ҳәм оның сызықлы емес дизим формасындағы аңлатылыўы
ЭЕМ ядында теректи аңлатыўдың ең қолай усылы бул оны байланысқан дизимлер көринисинде аңлатыў болып есапланады. Дизим элементи түйин мәниси ҳәм шығыў дәрежесин өз ишине алыўшы информациялық майданға ҳәмде шығыў дәрежесине тең болған көрсеткишлер майданына ийе болыўы лазым (жоқарыдағы сызылма), яғный элементиниң ҳәр бир көрсеткиши усы элементти түйин балалары болған түйинлерге бағдарын анықлайды.