- •(2 Саат)
- •Пайдаланыўшы программасында ҳәм эем ядында мс классификациялаў
- •Қадағалаў сораўлары
- •Пайдаланыўшы тәрепинен анықланатуғын түрлер Саналатуғын түр
- •Шегараланған яки диапазонлы түрлер
- •1. Векторлар
- •2. Массивлер
- •3. Жазыў
- •4. Кестелер
- •(Массалық хызмет көрсетиў түрлери)
- •1. Стеклер
- •Insert (q,X) элемент қосыў әмели.
- •Байланысқан дизимлер
- •Бир бағытлы дизимлер
- •Ҳалқа тәризли бир бағытлы дизим
- •Бир бағытлы дизимлер үстинде орынланатуғын әпиўайы әмеллер
- •Еки бағытлы дизим
- •Ҳалқа тәризли еки бағытлы дизим
- •Стеклерди бир бағытлы дизимлер жәрдеминде әмелге асырыў
- •Дизимге енгизиў мүмкин болған нәўбет әмеллери
- •Getnode, Freenode әмеллерин пайда етиў ҳәм босаған элементлерди утилизация қылыў
- •Дизимлер үстиндеги әмеллерге байланыслы мәселелер
- •1 Мәселе.
- •2 Мәселе.
- •Сызықлы емес байланысқан структуралар
- •Бинар тереклер
- •Бинар теректен элементти өшириў процедурасы
- •Қадағалаў сораўлары
- •1. Избе-из излеў
- •2. Индексли избе-из излеў
- •3. Избе-из излеўдиң эффективлиги
- •4. Индексли избе-из излеўдиң эффективлиги
- •6. Табылған элементти дизим басына қосыў арқалы кестени қайта тәртиплестириў
- •7.Транспозиция усылы
- •Қадағалаў сораўлары
- •Гилтлерди сәўлелендириў.
- •Сәўлелендириў функциясини таңлаў.
- •Тосқынлықты шешиў алгоритмлери
- •Қадағалаў сораўлары
- •Пайдаланылған әдебиятлар Тийкарғы
- •Қосымша
Бинар теректен элементти өшириў процедурасы
Түйинди өширип таслаў нәтийжесинде теректиң тәртипленгенлиги бузылмаўы керек. Түйин теректе өширилип атырғанда 3 қыйлы вариант болыўы мүмкин:
1) Табылған түйин терминал (жапырақ). Бул жағдайда түйин әпиўайы түрде өширип тасланады.
2) Табылған түйин тек ғана бир балаға ийе. Ол жағдайда бала ата орнына жайластырылады.
3) Өширилип атырған түйин еки балаға ийе. Бундай жағдайда сондай бөлим тереклер звеносын табыў керек, себеби оны өширилип атырған түйин орнына қосыў мүмкин болсын. Бундай звено ҳәр дайым бар болады:
- бул яки шеп бөлим теректиң ең оң тәрептеги элементи (усы звеноға ерисиў ушын кейинги ушына шеп шақа арқалы өтип, нәўбеттеги ушларына болса, мүрәжәт NIL болмағанша, тек ғана оң шақалары арқалы өтиў зәрүр).
- яки оң бөлим теректиң ең шеп элементи (усы звеноға ерисиў ушын кейинги ушына оң шақа арқалы өтип, нәўбеттеги ушларына болса, мүрәжәт NIL болмағанша, тек ғана шеп шақалары арқалы өтиў зәрүр).
Өширилип атырған элемент шеп бөлим терегиниң ең оңындағы элемент өширилип атырған элемент ушын “Предшественник” болады ( 12 ушын – 11 болады). Мийрасхор болса оң бөлим теректиң ең шебиндеги түйини (12 ушын - 13).
Мийрасхорды табыў алгоритмин ислеп шығайық (5.9 сызылма).
p – жумысшы көрсеткиш;
q - р дан бир адым арқадағы көрсеткиш;
v – өширилип атырған түйин мийрасхорын көрсетеди;
t - v бир адым арқада жүреди;
s - v дан бир адым алдында жүреди (шеп баланы яки бос орында көрсетип барады).
Жоқарыдағы терек бойынша қарайтуғын болсақ, ақырында, v көрсеткиш 13 түйинди, s болса бос орында көрсетиўи керек.
1) Элементти излеў процедурасы арқалы өширилип атырған элементти табамыз. р көрсеткиш өширилип атырған элементти көрсетеди.
2) Өширилетуғын элементтиң орнына қойылыўшы түйинге v көрсеткиш қоямыз.
IF left (p)=nil
THEN v=right (p)
ELSE IF right (p)=nil
THEN v=left (p)
ELSE t=p
v=right (p)
s=left (v)
WHILE s<>nil
t=v
v=s
s=left (v)
END WHILE
IF t<>p
THEN WRITE (v элемент p ның баласы емес)
left (t)=right (v)
right (v)=right (p)
END IF
left (v)=left (p)
IF q=nil
THEN WRITE (v тамыр)
tree=v
RETURN
END IF
IF p=left (q)
THEN left (q)=v
ELSE right (q)=v
END IF
END IF
END IF
FREENODE (p) (усы процедура бос түйин пайда етеди, яғный өширилген элемент жайласқан яд ячейкасын тазалайды.)
RETURN
Қадағалаў сораўлары
Рекурсия не?
Терек не? Оның өзине тән қәсийетлерин айтып бериң.
Толық терек дегенде нени түсинесиз?
Теректи айланып шығыў неден ибарат?
Ҳәр қандай теректи бинар көриниске келтириў мүмкинбе?
Терек түйини қандай пайда етиледи?
Теректе қандай әмеллерди орынлаў мүмкин?
7-Лекция. Излеў (6 саат)
Реже:
Избе-из излеў
Индексли избе-из излеў
Избе-из излеўдиң эффективлиги
Индексли избе-из излеўдиң эффективлиги
Излеўди жетилистириў усыллары
Табылған элементти дизим басына қосыў арқалы кестени қайта тәртиплестириў
Транспозиция усылы
Жетилискен излеў тереги
Бинар излеў (тең екиге бөлиў усылы)
ЭЕМде мағлыўматларды қайта ислеўде излеў тийкарғы әмеллерден бири болып есапланады. Оның ўазыйпасы берилген аргумент бойынша массив мағлыўматлары ишинен усы аргументке сәйкес мағлыўматларды табыўдан ибарат.
Қәлеген мағлыўматлар жыйындысы кесте яки файл деп аталады. Қәлеген мағлыўмат (яки структура элементи) басқа мағлыўматтан қандайда бир белгиси арқалы парқ қылады. Усы белги гилт деп аталады. Гилт ҳасыл болыўы, яғный усы гилтке ийе мағлыўмат кестеде жалғыз болыўы мүмкин. Бундай ҳасыл гилтке баслағыш (биринши) гилт делинеди. Екинши гилт бир кестеде такирарлансада ол арқалы да излеўди әмелге асырыў мүмкин. Мағлыўматлар гилтин бир жерге жыйнаў (басқа кестеге) яки жазыў сыпатында аңлатып бир майданға гилтлерди жазыў мүмкин. Егер гилтлер мағлыўматлар кестесинен ажыратып алынып өз алдына файл сыпатында сақланса, ол жағдайда бундай гилтлер сыртқы гилтлер делинеди. Кери жағдайда, яғный жазыўдың бир майданы сыпатында кестеде сақланса ишки гилт делинеди.
Гилттиң берилген аргумент пенен сәйкеслигин анықлаўшы алгоритмге берилген аргумент бойынша излеў деп аталады. Излеў алгоритми ўазыйпасы керекли мағлыўматты кестеде табыў яки жоқ екенлигин анықлаўдан ибарат. Егер керекли мағлыўмат жоқ болса, ол жағдайда еки жумысты әмелге асырыў мүмкин:
мағлыўмат жоқ екенлигин индикация (белгилеў) қылыў
кестеге мағлыўматты қосыў.
Ойлайық, k – гилтлер массиви. Ҳәр бир k(i) ушын r(i) – мағлыўмат бар. Key – излеў аргументи. Оған rec - информациялық жазыў сәйкес қойылады. Кестедеги мағлыўматлардың структурасына қарап излеўдиң бир неше түрлери бар.