Стек құрылымы
ҚАЗАҚСТАН РЕСПУБЛИКАСЫ БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНИСТІРЛІГІ
Л. Н. Гумилев атындағы Еуразия ұлттық университеті
Ақпараттық технологиялар факультеті
Компьютерлік және программалық инженерия кафедрасы
Алгоритмдер және деректер құрылымы пәні
К У Р С Т Ы Қ ЖҰ М Ы С
«6B06104 - Есептеу техникасы және бағдарламалық қамтамасыз ету» мамандығының
В057-6104-20-09 тобының студенті
Аңсат Амандық
тегі А. Ә. қолы
Нұр - Сұлтан 2022
Мазмұны
Кіріспе
«Алгоритмдер және деректер құрылымы» пәнін оқу нәтижесінде программалау технологиясының жоғарғы деңгейі - динамикалық құрылымдарды қолдану алгоритмдері меңгерілді.
«Алгоритмдер және деректер құрылымы» пәнін меңгеру кезінде келесі динамикалық құрылымдардың әдістері мен қолдану жолдары қарастырылды:
- Бір және екі жақты байланысқан тізбектер;
- Стек және кезек динамикалық құрылымдары;
- Сұрыптау алгоритмдері;
- Екілік іздеу ағаштары (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- стектің ең жоғарғы элементтерін санмен көрсетілгендей жылжытыңыз немесе айналу әдісімен жылжытыңыз.
Стек концепциясының бағдарламалық жасақтамасы сәйкесінше айнымалы немесе тақырып көрсеткіші арқылы жоғарғы орын бақыланатын массивтер мен байланыстырылған тізімдер арқылы орындалады. Көптеген бағдарламалау тілдері стек енгізуді қолдау үшін кірістірілген мүмкіндіктерді қамтамасыз етеді.
Аппараттық стектер жадты бөлу және тіркелген бастапқы және өлшемді пайдалана отырып қол жеткізу мақсатында жүзеге асырылады. Стек регистрлері стек көрсеткішінің мәнін сақтау үшін қолданылады.
Стек қалай жүзеге асырылады?
Стек массив немесе байланыстырылған тізім арқылы оңай жүзеге асырылуы мүмкін. Кез келген жағдайда деректер құрылымын стек ретінде анықтайтын нәрсе іске асыру емес, интерфейс: пайдаланушыға элементтерді массивке немесе байланыстырылған тізімге шығаруға немесе басқа бірнеше көмекші әрекеттерді орындауға ғана рұқсат етіледі.
Стек диаграммамен нені түсіндіреді?
Стек - элементтердің бір типті реттелген тізімі. Бұл барлық кірістірулер мен жоюларға тізімнің бір соңында ғана рұқсат етілген сызықтық тізім.
Тізімдерден айырмашылығы, біз біріккен стек элементіне кіре алмаймыз. Біз заттарды арнайы әдістермен қоса немесе жоя аламыз. Жинақта сонымен қатар тізімдер сияқты әдіс бар. Сонымен қатар, стекте итераторы жоқ.
Жинақты түсіндіруге арналған ең көп кездесетін ұқсастық - бұл тақталар жинағы. Біз қанша тақтайшаларға қарамастан, біз әрқашан жоғарғы жақтан аламыз. Таза тақтайшалар жинақтың үстіне қойылады, сонымен қатар біз әрқашан бірінші болып, соңғысын бірінші болып шығарамыз.
Біреу табақшаны қабылдаған кезде, оны одан да жоғарыдан жояды. Бұл тақталардың ретпен өңделетіні, оған қарама-қарсы болған.
Енді, стек қалай жұмыс істейтінін түсінген кезде біз бірнеше шарттармен таныстырамыз. Стекке элементті қосу операциясы «итеру», жою - «POP» деп аталады. Соңғы қосылған элемент жинақтың жоғарғы жағы немесе «жоғарғы» деп аталады және оны «PEEK» операциясын пайдаланып көруге болады.
Процессор мен жад - бұл компьютердің негізгі құрылымдық элементтері. Процессор пәрменді орындайды, жад мекенжайларын басқарады, осы мекен-жайлардың мәндерін алып, өзгертеді және өзгертеді. Бағдарламалау тілінде мұның бәрі айнымалылар мен олардың құндылықтарына айналады. Жинақтың мәні және бірінші болып (Lifo) соңғы тұжырымдамасы өзгеріссіз қалады.
Қысқартулар LIFO енді бұрынғыдай жиі пайдаланылмайды. Мүмкін, тізімдер нысандарға айналды, ал қажет болған жағдайда, біріншіден бірінші болып (FIFO) кезекте қолданылады. Мәліметтер түрлерінің динамикасы өзектілігін жоғалтты, бірақ өрнектерді орындау кезінде оның маңыздылығын жоғалтты, бірақ оның түрі оны қолдану кезінде анықталады.
Стек - дерексіз деректер түрі емес, нақты механизм. Процессор деңгейінде бұл «қозғалтқыш», ол негізгі процессор циклінің жұмысын нақтылайды және толықтырады. Аздап арифметикалық, стек қарапайым және айқын жұмыс ережелерін бекітеді. Бұл сенімді және қауіпсіз.
Стектің сипаттамалық қасиеттері - бұл оның мөлшері мен ұзындығы. Процессор деңгейінде бәрі бит жылдамдығымен, жад және оған қол жеткізу физикасы арқылы анықталады. Қызықты ерекшелік пен дәстүр: стек өсуде, яғни жад мекенжайларын азайту бағытында және жад және деректер жады жоғарылайды. Бұл әдетте, бірақ міндетті емес.
3. Программалау есебі
Есептің берілгені:
Кездейсоқ жолмен алынған [0, 50] аралығындағы қайталанбайтын n бүтін саннан тұратын қызыл-қара ағашты құру керек. Қызыл - қара ағаштың суретін салу керек. Ағаштағы [10, 40] аралығындағы жұп сандардың ең үлкенін табу керек.
#include <iostream>
using namespace std;
typedef enum { BLACK, RED }nodeColor;
struct rbNode {
rbNode* left;
rbNode* right;
rbNode* parent;
nodeColor color;
int data;
};
#define NIL &nullbytak
rbNode nullbytak = { NIL, NIL, 0, BLACK, 0 };
rbNode* root = NIL;
void rotateLeft(rbNode* x)
{
rbNode* y = x->right;
x->right = y->left;
if (y->left != NIL) y->left->parent = x;
if (y != NIL) y->parent = x->parent;
if (x->parent)
{
if (x == x->parent->left) x->parent->left = y;
else x->parent->right = y;
}
else root = y;
y->left = x;
if (x != NIL) x->parent = y;
}
void rotateRight(rbNode* x)
{
rbNode* y = x->left;
x->left = y->right;
if (y->right != NIL) y->right->parent = x;
if (y != NIL) y->parent = x->parent;
if (x->parent)
{
if (x == x->parent->right) x->parent->right = y;
else x->parent->left = y;
}
else root = y;
y->right = x;
if (x != NIL) x->parent = y;
}
void insertFixup(rbNode* x)
{
while (x != root && x->parent->color == RED)
{
if (x->parent == x->parent->parent->left)
{
rbNode* y = x->parent->parent->right;
if (y->color == RED)
{
x->parent->color = BLACK;
y->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
}
else
{
if (x == x->parent->right)
{
x = x->parent;
rotateLeft(x) ;
}
x->parent->color = BLACK;
x->parent->parent->color = RED;
rotateRight(x->parent->parent) ;
}
}
else
{
rbNode* y = x->parent->parent->left;
if (y->color == RED)
{
x->parent->color = BLACK;
y->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
}
else
{
if (x == x->parent->left)
{
x = x->parent;
rotateRight(x) ;
}
x->parent->color = BLACK;
x->parent->parent->color = RED;
rotateLeft(x->parent->parent) ;
}
}
}
root->color = BLACK;
}
rbNode* insertrbNode(int data) //енгізу
{
rbNode* current, * parent, * x;
current = root;
parent = 0;
while (current != NIL)
{
if (data == current->data) return (current) ;
parent = current;
current = (data < current->data) ? current->left : current->right;
}
x = (rbNode*) malloc(sizeof(rbNode) ) ;
x->data = data;
x->parent = parent;
... жалғасыСіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
- Іс жүргізу
- Автоматтандыру, Техника
- Алғашқы әскери дайындық
- Астрономия
- Ауыл шаруашылығы
- Банк ісі
- Бизнесті бағалау
- Биология
- Бухгалтерлік іс
- Валеология
- Ветеринария
- География
- Геология, Геофизика, Геодезия
- Дін
- Ет, сүт, шарап өнімдері
- Жалпы тарих
- Жер кадастрі, Жылжымайтын мүлік
- Журналистика
- Информатика
- Кеден ісі
- Маркетинг
- Математика, Геометрия
- Медицина
- Мемлекеттік басқару
- Менеджмент
- Мұнай, Газ
- Мұрағат ісі
- Мәдениеттану
- ОБЖ (Основы безопасности жизнедеятельности)
- Педагогика
- Полиграфия
- Психология
- Салық
- Саясаттану
- Сақтандыру
- Сертификаттау, стандарттау
- Социология, Демография
- Спорт
- Статистика
- Тілтану, Филология
- Тарихи тұлғалар
- Тау-кен ісі
- Транспорт
- Туризм
- Физика
- Философия
- Халықаралық қатынастар
- Химия
- Экология, Қоршаған ортаны қорғау
- Экономика
- Экономикалық география
- Электротехника
- Қазақстан тарихы
- Қаржы
- Құрылыс
- Құқық, Криминалистика
- Әдебиет
- Өнер, музыка
- Өнеркәсіп, Өндіріс
Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор #1 болып табылады.
Ақпарат
Қосымша
Email: info@stud.kz