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

Мұндағы тізбектегі соңғы элементтің көрсеткіш өрісі 0 деген мәнге ие болады. Тізімдә сипаттау үшін үш түрлі көрсеткіш пайдаланған. Тізбектің бірінші элементінің көрсеткіші - head. Тізбектің соңғы элементінің көрсеткіші – rear. Тізбектің ағымдағы элементінің көрсеткіші – ptr. Head деген көрсеткіші бар элементсіз тізім 0 деген мәнге ие болады, себебі тізбектің кез келген элементіне кіру үшін басынан бастап қарау қажет.

Тізімді қалыптастыру. Бұл жағдайда тізімге элементті қосу аяғынан басталады немесе аяғында жүргізіледі.

1. 
   Байланған тізімнен өту.
   
2. 
   Тізімді тазалау.
   
3. 
   Элементті енгізу схемасы.
   

Көптеген қосымшаларда мәліметтердің реттелген тізімін қолдану қажет болады. Оның элементтері өспелі немесе кемімелі ретте орналасқан болуы тиіс. Жаңа элементтің дұрыс орнын анықтау үшін қыстыып қою алгоритмі тізімді сканерлеп өтеді. Одан кейін барып қою жүзеге асады. Мысалы: 60,65,74,82 тізімі берілген.

2. 
   50 санын тізімге енгіземіз.
   

Тізімдегі бірінші элемент – 60. Оның мәні 50-ден үлкен, сондықтан жаңа элемент тізімнің басына қойылады.

3. 
   70 санын тізімге енгізу керек. Мұнда 74 саны 70-тен үлкен тізімдегі бірінші элемент. Сондықтан қыстырып қою мына брйынша жүзеге асырылады:
   

4. 
   90 санын тізімге енгіземіз. Тағы барлық тізім тексеріледі. Онда элементтің ішінде мәні 90-нан кіші элемент жоқ. Сондықтан 90 тізімнің ең соңына қоыслады.
   

head Null Null

head

Циклдық тізімнің бір жетістігі бұл элементтерге кез келген жерде элементтерге кіруге болатындығында. Ал кемшілігі тізіммен жүрген кезде байқамаса ақырсыз циклге кіріп кетуге болады. Циклдық тізім сызықтық тізімге қарағанда құрылымы неғұрлым иілгіш болып келеді. Ол тізімде жүруді кез келген жағдайда бастауға мүмкіндік береді және оны бастапқы позицияға дейін жалғастыруға болады.
Екі байланысты сызықтық тізім

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

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

beg

2 байланысты тізімнен элементті алып тастау схемасы:

rex




Стектер
Стек дегеніміз ұзындық айнымалысының тізбектелген тізімі. Ондағы элементтерді алып тастау немесе қосу тек қана бір жағынан жүргізіледі. Стектерді кейде магазиндер деп те атайды. Стектерді белгілеу үшін көбінесе LIFO деген абревидуоа қолданылады. LIFO – Last in /first out (соңғы кіргенде бірінші шығады). Стектер тізімнің төбесінде кіруге болатын элементтерді сақтау үшін қолданылады. Стектің құрылымы полкадағы (сөредегі) кітаптар жиынына ұқсас болады. Мысалға: мұнда ең жоғарғы затты алуға болады немесе жаңа затты ең үстіне қосуға болады. Стек құрылымында элементтерді қосу және алып тастау операциялары маңызды орын алады.

Push операциясы стектің төбесіне немесе ең жоғарғы жағына элемент қосады. Ал Pop операциясы элементті өшіреді. Сонда мына құрылымдарды сызамыз:

Стектер екі әдіспен жүзеге асуы мүмкін:

1. 
   массив негізінде
   
2. 
   көрсеткіштер көмегімен
   

Стекті бір өлшемді массив негізінде жүзеге асыруды – стек өлшемі массивті максимальды элементтер санымен шектестіреді. Ал стекті көрсетулер көмегімен жүзеге асыруды – стек мөлшері - бос жадының кіруге болатын көмегімен шектеледі.

Стек құрылымын келесі графиктік түрде беруге болады:

Стек төбесі

1. 
   Элементті стекке қосу.
   
2. 
   Элементті стектен өшіру (өшіріліп отырған элементтің мәнін берумен бірге)
   
3. 
   Жоғарғы элементтің мәнін беру.
   
4. 
   Стекті тазалау.
   
5. 
   Стек элементтің санын басып шығару.
   

1. 
   Жадымен жұмыста. Мысалға, printf және scanf функциялары жұмысы стекті пайдалануға негізделген.
   
2. 
   Сөйлем поендром болатындығын немесе болмайтындығын анықтау үшін қолданылады. Полендром дегеніміз – түзу және кері бағытта бірдей оқылатын жол. Мысалға, 121, ара.
   
3. 
   Әртүрлі негіздегі мәліметтерді шығару үшін.
   
4. 
   Электронды калькуляторлар жасауда.
   

Аббревиатура қысқарған сөздердің бас әрпін алып жазатын қысқарған сөздер. FIFO – соңынан кіру, басынан шығару. Мысалға, шіреттегі коиенттерге қызмет көрсетуді алуға болады. Шіреттермен жұмыс істегенде бастапқы және срңғы позицияларға арнайы көрсетулер қолданылады. Бұл көрсетулер шіретке элемент қосқанда және шіреттен элементті өшіргенде қолданылады. Шіреттің басы шіреттегі бірінші элементпен анықталады. (front) – алғашқы. Ал шіреттің соңы шіреттегі соңғы элементтен кейінгі орын (rear - соңғы).

Шіреттерде екі әдіспен жүзеге асады:

1. массивтер негізінде

2. көрсеткіштер көмегімен.

Шіреттер де стектер сияқты элементтің саны шектелмейді. Алайда, егер стекті жүзеге асыру үшін массив қолданса, онда толық шірет шарты пайда болуы мүмкін. Шіретті массивтер негізінде екі әдіспен жүзеге асыруға болады:

1. Сызықтық шірет (линейная)

2. Сақиналық шірет (кольцевая)

Жай ғана сызықтық шірет бір өлшемді массив негізінде жасалады. Шіреттегі бір элементті алып тастағанда қалған элементтің барлығы 1 позицияға алға жылжиды.

Элементті қосу:

front rear

front rear

front rear

front rear

front front

rear

D-ны қосу Е-ні қосу

Front

Null

1. 
   Шіретке элементті қосу
   
2. 
   Шіреттен элементті алып тастау (өшірілген элементтің мәнін беру)
   
3. 
   Бірінші элементтің мәнін беру.
   
4. 
   Шіретті тазалау
   
5. 
   Шірет элементінің санын беру.
   

1. 
   Компьютерлік модельдеуде (банктегі клиент шіретін модельдеу)
   
2. 
   Көп адамдар қолданылатын операциялық жүйелерде.
   
3. 
   Мәліметтерді сұрыптауда
   

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

Ең алдымен 2 өшіріледі.

2,1,5,4,3

орындалу реті

Элемент 1 20

Элемент 2 0

Элемент 3 40

Элемент 4 30

Элемент5 20

2,1,5,4,3

Пиоритеттер шіретін әрбір шіреттер приоритеті үшін қолданылатын бірнеше шіреттер түрінде беруге болады. Приоритеттер шіретін процестеп, тізімге жазатын және одан кейін приоритеттер реті бойынша орындайтын операциялық жүйеде қолдануға болады.

Тармаќтыњ элементтері т‰йін деп аталады. Аѓаш тєрізді ќ±рылым т‰пкі деп аталатын алѓашќы бір т‰йіннен басталатын кµптеген т‰йіндер жиынтыѓын ќ±райды.

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 түрлі әдісі бар:

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

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

F J

D H

1. 
   екілік тармақта әрбір төбенің екіден артық балалық түйіні болмайды.
   
2. 
   кез келген төбенің балалық төбелері оң жақ балалық төбе және сол жақ балалық төбе болып бөлінеді. (Бұл тармақтардың графтық берілуіне қатысты айтылады. Кез келген тармақтарды оған сәйкес екілік тармақ ретінде беруге болады)
   

Оң жақ бұтақ

Сол жақ бұтақ
Екілік тармақ кез келген n деңгейде бірден бастап 2ⁿ түйіндерге дейін болуы мүмкін. Тармақтардың тығыздығы дегеніміз – тармақтың түйіндерінің оның тереңдігіне қатысты саны.

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

Туындаған тармақтар, аяқталған тармақтар тығыздық шеткі шаралары немесе өлшемдері болып табылады. n тереңдіктегі аяқталған 2-к тармақ дегеніміз – 0-дан бастап n-1 –ге дейінгі әрбір деңгейі түйіндерінің толық жиыны бар және n деңгейіндегі барлық жапырақтары сол жағынан орналасқан екілік тармақтарды айтамыз. Толық тармақ дегеніміз – бұл n деңгейді 2ⁿ түйіндерде тұратын аяқталған бинарлық тармақ.

Туындалған тармақ Аяқталған тармақ

Толық тармақ

(2-деңгей)




Тармақтың тереңдігі дегеніміз – оның түбірінен ең шеткі түйініне дейінгі ең ұзын жолдың ұзындығы болады. Мысалға, n түйіні бар туындалған тармақ үшін ең ұзақ жол ұзындығы n-1-ге тең болады. Сонда 5 түйіні бар тармақтың максимальды тереңдігі 4-ке тең болады. N түйіні бар аяқталған тармақ үшін log₂n-ң бүтін бөлігіне тең болады. Мысалы, егер тармақтың 10000 элементі болса, n=10000, онда тереңдігі - int(log₂1000)= int(13,28)=13.
Екілік тармақтың құрылымы.

Екілік тармақты компьютер жадысына берудің екі түрлі жолы бар.

1. 
   Кәдімгі массивті пайдалана отырып тізбектеп беру
   
2. 
   Динамикалық құрылым ретінде беру.
   

Егер n түйіні массивтің TREE[k] элементін алатын болса, онда оның сол жақтағы балалық түйіні TREE[2K+1], ал оң жақтағы блалық түйіні - TREE[2K+2].

Кемшіліктері:

1. Тармақтың өлшемі массив өлшемімен шектелетін болады.

2. Тығыздығы көп емес тармақты сақтау үшін көп бөлігі пайдасыз қалатын үлкен массив керек болады.

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

Айталық, бізге n түйіні бар минимальды биіктікпен тармақ салу керек. Ол үшін барлық деңгейлердегі түйіндердің ең жоғарғы мүмкін санын, ең төменгісін санамағанда білуіміз керек. Идеал балансталған тармақ - бұл ең төменгісін санамағандағы барлық деңгейлердегі түйіннің ең жоғарғы мүмкін саны бар тармақ. Идеалды балансталған тармақта әрбір түйін үшін түйіндер саны оң және сол жақ бұтақта айырмашылығы бірге ғана тең болады. N түйіні берілгенде идеалды балансталған тармақты жасаудың алгоритмі:

1. 
   түбір ретінде бір түйінді алу.
   
2. 
   nl=n/2 түйіні бар сол жақ бұтақ салу (осы алгоритм көмегімен)
   
3. 
   nr=n-nl-1 оң жақ бұтақ салу (алгоритм көмегімен)