Стек құрылымы

Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 13 бет
Таңдаулыға:

ҚАЗАҚСТАН РЕСПУБЛИКАСЫ БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНИСТІРЛІГІ
Л.Н. Гумилев атындағы Еуразия ұлттық университеті
Ақпараттық технологиялар факультеті
Компьютерлік және программалық инженерия кафедрасы

Алгоритмдер және деректер құрылымы пәні

К У Р С Т Ы Қ ЖҰ М Ы С

6B06104 - Есептеу техникасы және бағдарламалық қамтамасыз ету мамандығының
В057-6104-20-09 тобының студенті

Аңсат Амандық ________________
тегі А.Ә. қолы

Нұр - Сұлтан 2022

Мазмұны

Кіріспе
3
1. AVL - ағашын баланыстау.солға үлкен бұру
4
2. Стек құрылымы. Тізбек түріндегі стек
8
3. Практикалық тапсырма
12
4. Қорытынды
16
5. Қолданылған әдебиеттер тізімі
17

Кіріспе
Алгоритмдер және деректер құрылымы пәнін оқу нәтижесінде программалау технологиясының жоғарғы деңгейі - динамикалық құрылымдарды қолдану алгоритмдері меңгерілді.
Алгоритмдер және деректер құрылымы пәнін меңгеру кезінде келесі динамикалық құрылымдардың әдістері мен қолдану жолдары қарастырылды:
Бір және екі жақты байланысқан тізбектер;
Стек және кезек динамикалық құрылымдары;
Сұрыптау алгоритмдері;
Екілік іздеу ағаштары (AVL ағашы, қызыл-қара ағаш, үйме ағашы);
Екілік іздеу ағаштарын теңестірудің (оңға және солға, кіші және үлкен бұрулардың) алгоритмдері;
Хэш функциялардың үлгілері;
Хэш кестелерін құру және кестедегі қайшылықтарды шешу;
Компьютер жадысында графты анықтаудың жолдары;
Графтарды тереңінен және көлденеңінен қарастыру алгоритмдері.

Курыстық жұмыстың бірінші бөлімінде AVL - ағашын баланыстау
солға үлкен бұру болды. Бұл бөлімде баланыстау солға бұру туралы кодттармен таныстық және оның сандық сұлбаларымен таныс болдық.Және сол үлкен бұру ол кішкене оңға бұру қарағанда ққиындау екен,но сызбасымен түсініп кетуге болады

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

Курстық жұмыстың үшінші бөлімінде программалау есеп болды. Есеп толығымен орындалды. Есептің берілгені қызыл қара ағаш құру керек және сол ағаштағы [10,40] аралағындағы жұп сандардың мәнді табу болды. Код толығымен жазылып есептің нәтижесі шықты. Есепте көптеген алгоритмдер қолданылды. Олар онға, солға бұру және ағашты теңестіру секілді алгоритмдер қолданылды. Соңында есептің берілгені бойынша шарт жазылып есептің натижесін толығымен шығарып алдым. Жәнеде есепте қызыл қара ағаштың суретін салу керек болған олда толығымен орындалды.

1. AVL - ағашын баланыстау.Солға үлкен бұру

Ағаш мінсіз теңдестірілген деп аталады, егер оның әрбір шыңы үшін сол және оң жақ ішкі ағаштардағы төбелер саны 1-ден аспайтын болса.
Егер іздеу ағашы тамаша теңдестірілген болса, онда тіпті ең нашар жағдайда, O(log2n) уақытында сіз оның кез келген кілттік мәні бар шыңды таба аласыз немесе ондай шыңның жоқтығын біле аласыз. Толық толтырылған деңгейлері бар тамаша теңдестірілген ағашта соңғы деңгей ағаш түйіндерінің жартысынан көбін қамтиды. Мысалы, 4, 6, 2, 1, 5, 3, 7 мәндерінің тізбегі келесідей тамаша теңдестірілген ағашты береді:

Бұл ағашта 7 түйін бар, соңғы деңгейде 4 түйін бар. Егер бір түйінге қол жеткізу үшін 1 бірлік уақыт қажет болса, онда 4 түйінге 1 бірлікте, 2-ге және 6-ға - 2 бірлікке, 1, 3, 5, 7-ге - 3 бірлікте жетуге болады. Яғни, ең нашар. жағдайда, 3 бірлік қажет уақыт, орта есеппен: (1+2*2+3*4)7 = 2,4 уақыт бірлігі (log 2n=log 8=3).
Бұрыннан бар ағашты теңдестірілген ағашқа келтіру - күрделі процесс. Ағаш өсіп келе жатқанда (әр түйінді қосқаннан кейін) теңестіру оңайырақ. Дегенмен, мінсіз тепе-теңдік талабы бұл процесті ағаштың барлық түйіндеріне әсер ете алатын өте күрделі етеді.
Ағаш тепе-теңдігінің тағы бір анықтамасын 1962 жылы кеңес математиктері Адельсон-Вельский мен Ландис ұсынған. Ағаш теңдестірілген деп аталады, егер әрбір түйін үшін оның екі ішкі ағашының биіктігі 1-ден аспайтын болса ғана. Осы шартты қанағаттандыратын ағаштар AVL ағаштары деп аталады.
AVL теңдестірілген ағаштардың мысалдары:

AVL теңдестірілмеген ағаштардың мысалдары:

Әрбір ағаш түйіні үшін теңгерім ұпайын осы түйіннің оң және сол ішкі ағаштарының биіктігі арасындағы айырмашылық ретінде анықтауға болады. hR оң жақ ішкі ағаштың биіктігі, hL сол жақтың биіктігі болсын. Егер ағаш AVL теңдестірілсе, онда әрбір түйін үшін hR - hL = 1.
AVL ағашындағы hR - hL тепе-теңдік көрсеткіші келесі мәндерді қабылдауы мүмкін:

-1 сол жақ ішкі ағаш оң жақтан бір жоғары болса;

0 егер екі ішкі ағаштың биіктіктері бірдей болса;

1, егер оң жақ ішкі ағаш сол жақтан жоғары болса.

Ағаштың кем дегенде бір түйіні үшін бұлай болмаса, онда ағаш AVL теңдестірілмеген. Мұнда AVL-теңгерімделген және AVL-теңгерімсіз ағаштың мысалдары берілген (әр түйінде теңгерім көрсеткіші бар):

AVL теңдестірілген ағаш

АВЛ-несбалансированное дерево
Теңдестіру түйіндердің айналуы деп аталатын әрекеттер арқылы жүзеге асырылады. p, q және r көрсеткіштерін пайдаланып, р теңгерімсіз түйінді көрсетеді деп есептей отырып, айналдыру алгоритмдерін қарастырайық.

Екі рет RL бұрылысы (үлкен солға). Теңгерімсіз түйіннен R-L жолымен жүру кезінде орындалады.
Трансформация орындалады: T1C((T2BT3)AT4) Þ (T1CT2)B(T3AT4).
Алгоритм:
q=p-оңға; r=q-солға;
егер (r-бал0)
{p-бал=-1; q-bal=0;}
басқа
{p-бал=0; q-bal=1};
r-bal=0;
p-оңға=r-солға; q-сол=r-оңға;
r-сол=p; r-оң=q; p=q;
Түйіндер қосылған кезде, қосылғанға жақын теңгерімсіз балансы бар түйін үшін айналымдар орындалады. Яғни, ағашқа түйінді қосқаннан кейін тепе-теңдігі бұзылған бірнеше түйін түзілсе, айналдыру төменірек (яғни енгізілгенге жақын) үшін орындалады. Осы түйінді теңестіргеннен кейін жоғарыда орналасқан түйіндердің тепе-теңдігі қалпына келтіріледі.

AVL ағаштарын салу

4, 5, 7, 2, 1, 3, 6 мәндерінің тізбегінен алынған AVL іздеу ағашының өсу диаграммасын қарастырыңыз (пайдаланылған айналу түрін және теңгерімсіз түйіндер үшін теңгерім индексін көрсетеміз. ):
Түйінді AVL тармағына қосу кәдімгі ағашқа қосуға қарағанда орта есеппен көп уақытты қажет ететіні анық, өйткені теңгерімдеуді орындау қажет болуы мүмкін. Сондықтан, AVL ағаштарын ағаштағы түйіндерді іздеу аулауды қосу және алып тастаудан гөрі жиі кездесетін жағдайларда қолданған жөн.

2. Стек құрылымы. Тізбек түріндегі стек

Компьютер ғылымында Стек - бұл ерекше рөл атқаратын деректер құрылымдарының түрі немесе жинағы. Стектің негізгі операциялары қалқымалы элементтерді шығару және қосу болып табылады және бұл әрекеттер стектің бір шетінде орындалады. Информатикада стек LIFO (соңғы кіріс бірінші шыққан) құрылымы деп те аталады, себебі стектегі соңғы элемент бірінші болып шығады. Push және Pop әдістерінің басты ерекшелігі - стек элементтерінің тұрақты болуы. Стектен элементті жою, керісінше, жаңа элемент үшін кеңістік жасайды. Бұл ең төменгі элементтің ең ұзақ қызмет ететінін қамтамасыз етеді. Негізгі операциялардан басқа, Peek әдісі жүзеге асырылады. Бұл әдіс жоғарғы элементті жоймай мәнді қайтарады.

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

Стек - бұл аздаған әдістерді қолданатын соңғы деректер құрылымы. Push және Pop әдістерінің басты ерекшелігі - стек элементтерінің тұрақты болуы. Стектен элементті жою, керісінше, жаңа элемент үшін кеңістік жасайды. Бұл ең төменгі элементтің ең ұзақ қызмет ететінін қамтамасыз етеді.

Стек нені білдіреді?

Стек - біртекті элементтер жиынтығынан тұратын концептуалды құрылым және соңғы шыққан бірінші шығады (LIFO) принципіне негізделген. Бұл екі негізгі операциясы бар жиі қолданылатын дерексіз деректер түрі, атап айтқанда, push және pop. Басу және шығару стекке ең соңғы қосылған элемент болып табылатын ең жоғарғы элементте орындалады. Басу әрекеті элементті стекке қосады, ал қалқымалы әрекет элементті жоғарғы орыннан жояды. Стек тұжырымдамасы компьютерлерде бағдарламалауда және жадты ұйымдастыруда қолданылады.
Стек сызықтық деректер құрылымы пішіміндегі нысандар немесе элементтер тізбегін білдіреді. Стек шектелген түбінен тұрады және барлық операциялар жоғарғы позицияда орындалады. Элемент стекке push әрекеті арқылы қосылған сайын, жоғарғы мән біреуге артады, ал элемент стектен шыққанда, жоғарғы мән біреуге азаяды. Стектің жоғарғы орнына көрсететін көрсеткіш стек көрсеткіші ретінде де белгілі.

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

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

Peek -- Стектегі ең жоғарғы элементті көру.
Duplicate -- жоғарғы элементтің мәнін айнымалыға көшіріп, оны қайтадан стекке итеріңіз.
Swap -- Стектегі ең жоғарғы екі элементті ауыстырыңыз.
Rotate -- стектің ең жоғарғы элементтерін ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.