Біріктіру арқылы сұрыптау

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

Қарағанды техникалық университеті

Кафедра АТҚ

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

----------------------------------- ----------------------------------- ----------

----------------------------------- ----------------------------------- ----------
С++ бағдарламалау тілі бойынша практикум, курстық жұмыс
----------------------------------- ----------------------------------- ----------

----------------------------------- ----------------------------------- ----------
(пәннің атауы)
----------------------------------- ----------------------------------- ----------
Тақырып: Біріктіру арқылы сұрыптау(Merge sort)
----------------------------------- ----------------------------------- ----------

----------------------------------- ----------------------------------- ----------
Ағаш арқылы сұрыптау(Tree sort)
----------------------------------- ----------------------------------- ----------

----------------------------------- ----------------------------------- ----------

----------------------------------- ----------------------------------- ----------
Қабылдады:
----------------------------------- ----------------------------------- ----------
Сайлауқызы Ж.
----------------------------------- ----------------------------------- ----------
(баға) (оқытушының аты-жөні)
----------------------------------- ----------------------------------- ----------

----------------------------------- ----------------------------------- ----------
(қолы) (уақыты)
----------------------------------- ----------------------------------- ----------

----------------------------------- ----------------------------------- ----------
Комиссия мүшелері: Орындаған:
----------------------------------- ----------------------------------- ----------
Жамалбек Бақыт
----------------------------------- ----------------------------------- ----------
(қолы, аты-жөні) (студенттің аты-жөні)
----------------------------------- ----------------------------------- ----------
СИБ 20-2
----------------------------------- ----------------------------------- ----------

----------------------------------- ----------------------------------- ----------
(қолы, аты-жөні) (тобы)
----------------------------------- ----------------------------------- ----------

----------------------------------- ----------------------------------- ----------

----------------------------------- ----------------------------------- ----------
(сынақ кітапшасының шифрі,
----------------------------------- ----------------------------------- ----------
нұсқа)

Қарағанды 2021

. Қарағанды техникалық университеті

Факультет ФИТ "БЕКІТЕМІН"

Кафедра АТҚ Кафедра менгерушісі: ________________
(подпись)

"___" ________ 20__ж.

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

Пәні: С++ программалау семинары, курстық жұмыс

СИБ 20-2 тобының студенті Жамалбек Бақыт Серікқызы.

Тақырыбы: Біріктіру арқылы сұрыптау Merge sort, Ағаш арқылы сұрыптау Tree sort

Тапсырма берілді "__" __________________________ 2021 ж.

Жетекші: қолы

Студент: Жамалбек Б.С қолы

Мазмұны:

Кіріспе

Негізгі бөлім
1.1 Массив 5
1.2 Бір өлшемді массив 5
1.3. Екі өлшемді массив 5
2.1 Сұрыптау 6
2.2 Сұрыптаудың түрлері және қызметі 7
2.3 Біріктіру арқылы сұрыптау 8
2.4 Екілік іздеу ағашы 9
2.5 Екілік ағаш арқылы сұрыптауды жүзеге асыру 10
2.6 Ағаш арқылы сұрыптаудың тиімділігі 10
2.7 Ағаш арқылы сұрыптау жайлы қысқаша мәліметтер 11
3.1 Практикалық бөлім 13
Қорытынды 20
Қосымша А 22
Қосымша Б 26

Пайдаланылған әдебиеттер

Кіріспе

C++ тіліне мазмұн, С тіліндегі массивтер және сұрыпталу.

C-өте танымал, қарапайым және қолдануға икемді әмбебап бағдарламалау тілі. Бұл құрылымдық бағдарламалау тілі, ол машинадан тәуелсіз және әртүрлі қосымшаларды, Windows сияқты операциялық жүйелерді және Oracle database, Git, Python аудармашысы және басқалары сияқты көптеген күрделі бағдарламаларды жазу үшін кеңінен қолданылады.
"С" - Құдайдың бағдарламалау тілі деп айтылады. C бағдарламалау үшін негіз деп айтуға болады. Егер Сіз "С" ұғымын білсеңіз, "с" ұғымын қолданатын басқа бағдарламалау тілдерін білуді оңай түсінуге болады"
Компьютерлік жад механизмдерімен тәжірибе жинау өте маңызды, өйткені бұл С бағдарламалау тілімен жұмыс жасау кезінде маңызды аспект болып табылады.
Неліктен С тілі басқа тілдерге қарағанда оңай, әрі қол жетімді?
Олай айтуымыздың себебі С++ тілінің компиляторын бар жоғы 256 кб көлем арқылы жазып шығуға болады. Қордағы түйінді сөздер саны да көп емес. С тілін ойлап тапқанда Дэннис Ритчи 27 түйінді сөз енгізген. Өзгерістер орын алып ANSI C стандартында тағы біраз түйінді сөздер қосылған болатын.
С тілінің артықшылықтары:
Нысанға бағытталған бағдарламалауды қолдау (OOP). OOP кодты жеңілдетуге және тезірек жазуға көмектеседі. OOP туралы мақалалардың үлкен циклі.
Жоғары жылдамдық.
Деректермен төмен деңгейде жұмыс істеу мүмкіндігі, яғни аппараттық құралға жақын деңгейде. Осының арқасында с++ тілінде драйверлер, микроконтроллерлер жазуға болады.
Танымалдық:
С++ үшін көптеген кітапханалар мен компиляторлар жасалды.
C++ барлық жерде дерлік қолданылады.
С++ синтаксисі C, C# және Java синтаксисіне ұқсас, сондықтан бұл тілдер арасында ауысу оңай.
Кемшіліктері
Қауіпсіздік: c++ үлкен әрекет еркіндігін береді, бірақ сізді қателіктерден сақтамайды. Жадқа оңай қол жеткізу оны хакерлік шабуылдар кезінде ғана емес, сонымен қатар ұқыпсыз жұмыс кезінде де осал етеді.
Платформаға тәуелділік: C++ тілінде портативті кодты жазу (әртүрлі платформаларда жұмыс істейтін) өте қиын.
Синтаксис қатаң және" сөзбе-сөз": код кейбір басқа тілдерге қарағанда нашар оқылады (мысалы, Python-да).
Қиындық: с++ күрделі синтаксисі және кішкентай стандартты кітапханасы бар, сонымен қатар көрсеткіштерді және жадпен жұмыс істеуді түсіну керек, сондықтан оны үйрену оңай емес, әсіресе нөлден.
Сонымен, c++ - бұл оңай тіл емес. Бұл тез, танымал, көптеген мүмкіндіктер береді, оны барлық жерде қолдануға болады, ал c++ бағдарламашылары орта есеппен басқа әзірлеушілерге қарағанда көбірек алады. Бірақ мұның бәрі күрделі синтаксиспен және көрсеткіштер мен жадпен жұмыс істейтін бір пакетте келеді.

Негізгі бөлім

1.1 Массив

Келесі кезекте бізде "Массивтер" тақырыбы.
С++ тіліндегі "массив" дегеніміз не және қандай қызмет атқарады?

Массив дегеніміз-іргелес жад ұяшықтарына орналастырылған бір типтегі элементтер сериясы, оларды жеке идентификаторға индекс қосу арқылы жеке-жеке байланыстыруға болады.
Бұл дегеніміз, мысалы, int типінің бес мәні 5 түрлі айнымалыны жарияламай массив ретінде жариялануы мүмкін (әрқайсысы өз идентификаторымен). Оның орнына, массивті қолдана отырып, бес Int мәні іргелес жад ұяшықтарында сақталады және барлық бесеуі тиісті индексі бар бірдей идентификаторды қолдана отырып қол жетімді болады.
Массивтің жеке деректер ұяшығы массив элементі деп аталады. Массивтің элементтері кез-келген түрдегі деректер болуы мүмкін. Массивтерде бір немесе бірнеше өлшем болуы мүмкін. Өлшеу санына байланысты массивтер бір өлшемді массивтерге, екі өлшемді массивтерге, үш өлшемді массивтерге және т.б. n өлшемді массивке бөлінеді. Көбінесе бағдарламалауда бір өлшемді және екі өлшемді массивтер қолданылады, сондықтан біз тек осы массивтерді қарастырамыз.

1.2 Бір өлшімді массив

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

1.3 Екі өлшемді массив

Осы уақытқа дейін біз әрқашан шектеле алмайтын бір өлшемді массивтерді қарастырдық. Кестеден кейбір деректерді өңдеу керек делік. Кестеде екі сипаттама бар: Жолдар саны және бағандар саны. Сондай-ақ, екі өлшемді массивте массив элементтерінің санынан басқа, екі өлшемді массивтің жолдар саны мен бағандар саны сияқты сипаттамалар бар. Яғни, көзбен, екі өлшемді массив-бұл жолдар мен бағандары бар қарапайым кесте. Шын мәнінде, екі өлшемді массив -- бұл бір өлшемді массивтердің бір өлшемді массиві.

2.1 Сұрыптау

Сұрыптау-бұл бағдарламашы немесе зерттеуші қажетті кірістерді сұрыптау үшін қолданатын негізгі ұғым. Кірістерді сұрыптау іздеу, максималды және минималды элемент сияқты көптеген мәселелерді шешуді жеңілдетеді. Сұрыптау деректерді реттілікпен ұйымдастырғанымен, екі өлшемге негізделген процестің тиімділігі өте маңызды. Берілген мәліметтер бойынша сұрыптауды орындау үшін уақыт пен жад қажет.
Сұрыптау процесін кез-келген белгілі бір тәртіпте элементтерді қайта құру әдісі ретінде түсіндіруге болады, оны әрі қарай өңдеуге дайын бағдарламаның логикасымен орнатуға болады. C бағдарламалау тілінде кодқа енгізілуі мүмкін бірнеше сұрыптау алгоритмдері бар. С тілінде мүмкін болатын сұрыптау әдістерінің әр түрлі түрлері-көпіршікті сұрыптау, таңдау сұрыптау, Жылдам сұрыптау, біріктіру сұрыптау, қадаларды сұрыптау және кірістіруді сұрыптау.
Сұрыптаудың екі санатын қарастырайық.
Ішкі сұрыптау-бұл массив элементтерін бөлісу арқылы сол жерде шығарылатын сұрыптау түрі. Ішкі сұрыптаудың негізгі талабы-жадты үнемдеу
Сыртқы сұрыптау-бұл перифериялық құрылғыларда орналасқан және жедел жадқа сәйкес келмейтін деректерді сұрыптау
Айта кету керек, ішкі сұрыптау сыртқы сұрыптауға қарағанда әлдеқайда тиімді, өйткені магниттік дискілерге, таспаларға қарағанда жедел жадқа жүгінуге аз уақыт кетеді...
Орталықтандырылған компьютерлердің төрттен бір бөлігі деректерді сұрыптауға арналған деп есептелді. Себебі, алдын-ала сұрыпталған массивте мәнді табу әлдеқайда оңай. Әйтпесе, іздеу шөп шабатын жерден инені іздеуге ұқсайды.
Барлық жұмыс уақытын сұрыптау алгоритмдерін оқып, жүзеге асыратын бағдарламашылар бар. Себебі, бизнестегі бағдарламалардың басым көпшілігі дерекқорды басқаруды қамтиды. Адамдар барлық уақытта мәліметтер базасынан ақпарат іздейді. Бұл іздеу алгоритмдері өте қажет екенін білдіреді.
Сұрыптау күнделікті өмірде де, математикада да маңызды міндет болып табылады. Көбінесе сіз заттарды немесе сандарды өсу немесе кему ретімен немесе жұп тақ қатарда сұрыптауыңыз керек. Мұның бәрі сандарды немесе нысандарды қалай орналастырғыңыз келетініне байланысты. C++ стандартты шаблондар кітапханасы STL-де Sort() функциясын ұсыну арқылы сұрыптау процесіне көмектеседі. STL-бұл алдын-ала анықталған функциялар мен деректер құрылымынан тұратын кітапхана, оны пайдаланушыға ыңғайлы етеді. STL сонымен қатар контейнер сыныптарынан, алгоритмдерден және итераторлардан тұрады.

2.2 Сұрыптаудың түрлері және қызметі

Cұрыптаудың түрлеріне келетін болсақ, біз атап өтетін сұрыптаулар ең көп таралған сұрыптау түріне жатады. Яғни программалық кодқа сұрыптау қажет болған кезде жиі қолданылатын сұрыптау әдістері болып табылады.
1.Көпіршікті сұрыптау(Bubble sort)
2.Кірістіру арқылы сұрыптау(Insertion sort)
3.Таңдау арқылы сұрыптау(Selection sort)
4.Біріктіру арқылы сұрыптау(Merge sort)
5.Ағаш арқылы сұрыптау(Tree sort)
Келесі кезекте біз жоғарыда аталған сұрыптау түрлеріне қысқаша тоқтала кетсек.
Ең алдымен "Көпіршікті сұрыптау".
Көпіршікті сұрыптау-сұрыптау әдістерінің ең қарапайымы.
Көпіршікті сұрыптау техникасында тізімдегі элементтердің әрқайсысы көрші элементпен салыстырылады. Сонымен, егер А тізімінде n элементтер болса, онда A[0] A[1], A[1] A[2] және басқалармен салыстырылады.
Салыстырудан кейін, егер бірінші элемент екіншіден үлкен болса, онда екі элемент орын ауыстырады.Көпіршікті сұрыптау-сұрыптау әдістерінің ең қарапайымы.
Көпіршікті сұрыптау техникасында тізімдегі элементтердің әрқайсысы көрші элементпен салыстырылады. Сонымен, егер А тізімінде n элементтер болса, онда A[0] A[1], A[1] A[2] және басқалармен салыстырылады.
Салыстырудан кейін, егер бірінші элемент екіншіден үлкен болса, онда екі элемент орын ауыстырады. Осылайша сұрыптау жүзеге асады.
Келесі кезекте бізде "Кірістіру арқылы сұрыптау".
Кірістіру сұрыптау-бұл қарапайым сұрыптау алгоритмі, ол сіздің қолыңыздағы ойын карталарын сұрыптауға ұқсас жұмыс істейді. Массив іс жүзінде сұрыпталған және сұрыпталмаған бөліктерге бөлінеді. Сұрыпталмаған бөліктің мәндері таңдалады және сұрыпталған бөлікте дұрыс орналасады.
Алгоритм
N Өлшем массивін өсу ретімен сұрыптау:
1: массив бойынша arr[1] - ден arr[n] - ге дейін Итерация жасаңыз.
2. Ағымдағы элементті (кілтті) алдыңғы элементпен салыстырыңыз.
3: Егер негізгі элемент бұрынғыдан кіші болса, оны алдыңғы элементтермен салыстырыңыз. Ауыстырылатын элемент үшін орын жасау үшін үлкен элементтерді бір позицияға жоғары жылжытыңыз.
Мінә осылай кірістіру арқылы сұрыптау жүзеге асады.
Келесі сұрыптау түрі ол "Таңдау арқылы сұрыптау".
Таңдау арқылы сұрыптау алгоритмі сұрыпталмаған бөліктен ең аз элементті (өсіп келе жатқан тәртіпті ескере отырып) бірнеше рет тауып, оны басына қою арқылы массивті сұрыптайды. Алгоритм берілген массивте екі ішкі массивті қолдайды.
1) қазірдің өзінде сұрыпталған массив.
2) сұрыпталмаған қалған қосалқы массив.
Таңдауды сұрыптаудың әр итерациясында сұрыпталмаған ішкі массивтен ең аз элемент (өсу ретін ескере отырып) таңдалады және сұрыпталған ішкі массивке ауысады.
Сұрыптаудың басқа түрлеріне мен өзімнің жұмысымда толығырақ тоқтала кеттім.

2.3 Біріктіру арқылы сұрыптау

C ++ Merge Sort - массивті немесе бүтін сандар тізімін сұрыптауға арналған салыстыруға негізделген тиімді алгоритм.
Біріктіруді сұрыптау әдісі бөлу және жеңу техникасына негізделген. While жиынтығын кішірек бөліктерге бөлеміз және оларды сұрыпталған рет бойынша үлкен бөліктерге біріктіреміз. Бұл сондай-ақ ең нашар жағдай үшін өте тиімді, өйткені уақыттың күрделілігі аз және ең нашар жағдайда.
Анықтама бойынша, егер тізімде бір ғана элемент болса, ол сұрыпталады. Сұрыптауды біріктіру, содан кейін кіші сұрыпталған тізімдерді біріктіріп, жаңа тізімнің сұрыпталуын сақтайды. Бұл Джон фон Нейман 1945 жылы ойлап тапқан бөлу және жеңу алгоритмі. Енді сіз бөлу және жеңу әдісі дегенді ойландыратын шығарсыз.
С ++ тілінде сұрыптауды біріктіру алдымен массивті тең жартыға бөледі, содан кейін оларды сұрыпталған тәртіппен біріктіреді.
Біріктіру арқылы сұрыптау элементтерге қол жетімділік дәйекті түрде жүзеге асырылатын деректер құрылымдары үшін пайдалы (мысалы, ағындар үшін). Мұнда массив шамамен екі тең бөлікке бөлінеді және олардың әрқайсысы бөлек сұрыпталады. Содан кейін сұрыпталған екі массив біреуіне біріктіріледі.

2.1 - сурет- Біріктіру арқылы сұрыптаудың процесі

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

2.4 Екілік іздеу ағашы

Екілік (екілік) ағаш дегеніміз - әрбір элемент - ағаштың алдындағы немесе түбірі (астындағы) - кем дегенде екі басқа элемент (Мұрагер) сәйкес келетін реттелген мәліметтер құрылымы. Сонымен қатар, әр предшественник үшін келесі ереже орындалады: сол жақ Мұрагер әрқашан кішірек, ал оң жақ Мұрагер әрқашан предшественниктен үлкен немесе оған тең.
"Предшественник" және "Мұрагер" орнына "ата-ана "және" ұл " терминдері де қолданылады. Ағаштың барлық элементтері "түйіндер" деп те аталады. Ағашқа жаңа элемент қосылған кезде, ол төменгі түйіндермен дәйекті түрде салыстырылады, осылайша орнына енгізіледі. Егер элемент = түбір болса - ол оң жаққа қарай жүреді, біз оны оң ұлымен салыстырамыз, әйтпесе ол сол жаққа қарай жүреді, сол жақпен салыстырамыз және тағы басқалар, салыстыруға болатын ұлдары болған кезде.
Ағаш ( * ) сияқты көп немесе аз болуы мүмкін, тек екі негізгі бұтақ ( * * ) болуы мүмкін, ал егер кіріс тізбегі сұрыпталған болса, онда ағаш сызықтық тізімге енеді. Егер біз ағашты "сол жақ ұл - ата - ана-оң жақ ұл" ережесі бойынша рекурсивті түрде айналып өтсек,онда барлық элементтерді массивке жазып, біз Өсу реті бойынша тапсырыс аламыз. Ағашты сұрыптау идеясы осыған негізделген. Толығырақ, айналып өту ережесін сол жақ субтрагты қалай айналып өту керек - тамырды алып тастау - оң субтрагты айналып өту деп тұжырымдауға болады, мұнда "айналып өту" рекурсивті процедурасы ата-ана түйінімен соқтығысып, түйіннің ұлдары болмаса, басқа элемент береді.
Ағаштарды сұрыптау - сұрыпталатын элементтерден екілік іздеу ағашын құрып, содан кейін элементтер сұрыпталған тәртіппен шығуы үшін ағашты (ретімен) айналдыратын сұрыптау алгоритмі. Оның әдеттегі қолданысы элементтерді желіде сұрыптау болып табылады: әр енгізуден кейін элементтер жиынтығы сұрыпталған тәртіпте қол жетімді.
Ағаштарды сұрыптауды бір реттік сұрыптау ретінде пайдалануға болады, бірақ ол киксорсқа тең келеді, өйткені екі бөлшектеу элементтері де рекурсивті айналымға негізделген, және куксорс өз орнында жасалынған және үстеме шығындары аз болғандықтан, кворксортқа қарағанда оның артықшылығы шамалы. Ол өзін-өзі теңестіретін ағашты қолданатын ең нашар күрделілікке ие, бірақ одан да көп.

2.5 Екілік ағаш арқылы сұрыптауды жүзеге асыру

2.2-сурет- Ағаш арқылы сұрыптауды жүзеге асыру

Жылдам сұрыптауға сәйкес келетін ағаштардан айырмашылығы, олар
құрылымдар тек бастапқы файлдың көлеміне байланысты және мәндерге тәуелді емес кілттер. Жоғарғы диаграммада 32 элементтен тұратын файлды сұрыптау көрсетілген. Алдымен 16 элементтен тұратын екі файлды (рекурсивті) ретке келтіру, содан кейін оларды біріктіру жүзеге асырылады.
16 элементтен тұратын файлдар (рекурсивті) сұрыптау арқылы сұрыпталады (рекурсивті)

2.6 Ағаш арқылы сұрыптаудың тиімділігі

Бір элементті екілік іздеу ағашына қосу орташа O (log n) процесін алады (үлкен O белгісінде). N элементті қосу O (n log n) процесі болып табылады, ағашты сұрыптауды жылдам сұрыптау процесі құрайды. Теңгерілмеген екілік ағашқа элементті қосу ең нашар жағдайда O (n) уақытты алады: ағаш байланыстырылған тізімге ұқсас болғанда (деградацияланған ағаш).
Бұл сұрыптау алгоритмі үшін ең нашар O (n²) уақытқа әкеледі. Бұл ең жаман жағдай алгоритм әлдеқашан сұрыпталған жиынмен немесе дерлік сұрыпталған, төңкерілген немесе төңкерілген жиынмен жұмыс жасағанда пайда болады. Алайда O (n log n) күткен уақытқа массивті араластыру арқылы қол жеткізуге болады, бірақ бұл бірдей элементтерге көмектеспейді.
Нашар мінез-құлықты өзін-өзі теңдестіретін екілік іздеу ағашын қолдану арқылы жақсартуға болады. Осындай ағашты қолдана отырып, алгоритм нашар жағдайда o (n log n) өнімділікке ие, бұл оны салыстыруды сұрыптау үшін оңтайлы етеді. Алайда, ағаш сұрыптау алгоритмдері жылдам немесе динамикалық сұрыптау сияқты алгоритмдерден айырмашылығы, ағаш үшін бөлек жад бөлуді қажет етеді. Көптеген кең таралған платформаларда бұл жылдам және динамикалық сұрыптауға қарағанда өнімділікті едәуір төмендететін динамикалық жадты пайдалану керек дегенді білдіреді [сілтеме қажет]. Кеңейтілген ағашты екілік іздеу ағашы ретінде қолданған кезде, алынған алгоритм (splaysort деп аталады) қосымша сұрыптауға ие, бұл оның орындалу уақыты o (n log n) қарағанда тезірек, олар дерлік сұрыпталады.

2.7 Ағаш арқылы сұрыптау жайлы қысқаша мәліметтер

Ағаш арқылы сұрыптаудың қандай кемшіліктері бар?
Ағаш құрылымын жадқа физикалық орналастыру кезінде кем дегенде 4n қосымша жад ұяшықтары қажет.
Әр түйінде бар:
-бастапқы массив элементіне сілтемелер;
-ата-ана элементіне;
-сол және оң парақтарда.
- TreeSort әдетте қай жерде қолданылады -
- салынған ағашты осындай тапсырмалар үшін сәтті қолдануға болады;
- деректер "ағашқа" салынған;
- деректерді тікелей ағашқа оқуға болады;
- консольден немесе файлдан ағынды енгізу кезінде.
- Екілік іздеу ағашының негізгі интерфейсі үш операциядан тұрады:
FIND (K) - key = K бар жұп (key, value) сақталатын түйінді іздеу.
INSERT (K, V) -- ағашқа жұп қосу (кілт, мән) = (K, V).
REMOVE (K) - key = K бар жұп (key, value) сақталатын түйінді жою.
Бұл дерексіз интерфейс-бұл жалпы жағдай, мысалы, қолданбалы тапсырмалардан алынған интерфейстер:
"Телефон кітапшасы" - жазбаларды адамның аты бойынша іздеу және жою операциялары және жаңа жазбаны қосу операциясы бар жазбаларды сақтау (адамның аты, оның телефоны).
Domain Name Server-өзгерту және іздеу операциялары бар жұптарды сақтау (домен атауы, IP мекен-жайы).
Namespace-бұл бағдарламалау тілдерінің аудармашыларында пайда болатын айнымалы атауларды олардың мәндерімен сақтау.
Негізінен, екілік іздеу ағашы-бұл жұп кестесін (key, value) сақтай алатын және үш әрекетті қолдайтын мәліметтер құрылымы: табу, INSERT, жою.
Сонымен қатар, екілік ағаш интерфейсі ағаш түйіндерін айналып өтудің тағы үш қосымша әрекетін қамтиды: INFIX_TRAVERSE, PREFIX_TRAVERSE және POSTFIX_TRAVERSE. Олардың біріншісі кілттердің бұзылу тәртібімен ағаш түйіндерін айналып өтуге мүмкіндік береді.

2.3-сурет- Блок-схема

"Quest" әдісі - берілген кілт бойынша "тереңдіктен - жоғарыдан төменге (префиксті айналып өту)" айналып өту тәсілімен екілік ағашта элементті іздеу әдісі. Бұл әдісті қолданған кезде "сканерлеу" әдісі автоматты түрде іске қосылады - айналып өту, онда осы элемент ізделеді және оны Екінші реттік әрекеттер орын алатын "квестке" қайтарады (табылған элементті кесте мен ағашқа таңдау). "Quest" әдісінің Блок-схемасы жоғарыдағы суретте көрсетілген.

4.1.Практикалық бөлім

Мен есебімде түйіннең тұратын және екілік ағаштар болып табылатын сол және оң жақ тармақтардан тұратын ағашты жасадым. Ағашқа элемент қосу процедурасы жасалды. Практикалық бөлімде есеп мазмұны және де есепте қолданылған функция, оператор тағы басқа өрнектерді сипаттап түсіндіретің боламын. Және де тағы басқа есептің негізгі болған тип түйындер жайлы тоқталатын боламыз. Вариант номер 7:
7. Кездейсоқ сандар жиынтығымен екілік іздеу ағашын құратын программа жасаңыз. Сонымен қатар, берілген мән бойынша ағаштағы түйінді қосуға, жоюға және іздеуге болады. Пернетақтадан операцияларды таңдау және кілттің мәні енгізіледі.
#include iostream
#includeconio.h
#includetime.h
using namespace std;
class node
{public:
int data;node *left;node *right;node(int data)
{this-data = data;
this-left = nullptr;
this-right = nullptr;}};
void shigaru(node *tvbir, int bos_orin = 0, int t = 0)
{int a = 4;
if (tvbir == NULL)
return;
bos_orin += a;
shigaru(tvbir-right, bos_orin, 1);
for (int i = 0; i bos_orin; i++)
{cout " ";

if (t == 1) {
cout " " tvbir-data endl;}
else if (t == 2) {
cout "\\ " tvbir-data endl; }
else {cout tvbir-data endl;}
shigaru(tvbir-left, bos_orin, 2);}

int main(){
srand(time(NULL));
setlocale(LC_ALL, "rus");
int a, b, c, d, e, f, g;
node *tvbir = new node(a = rand() % 6 + 20);
tvbir-left = new node(b = rand() % 6 + 15);
tvbir-right = new node(c = rand() % 10 + 31);
tvbir-left-left = new node(d = rand() % 4 + 10);
tvbir-left-right = new node(e = rand() % 11 + 40);
tvbir-right-left = new node(f = rand() % 6 + 25);
tvbir-right-right = new node(g = rand() % 11 + 50);
shigaru(tvbir);
cout endl endl "ELEMENT КОСУ:" endl;
tvbir-right-right-right = new node(g = rand() % 11 + 60);
tvbir-left-right-right = new node(g = rand() % 11 + 70);
shigaru(tvbir);_
getch();
return 0;}

Есепте iostream, conio.h, time.h кітапханаларды қолданып есепті қысқа әрі женіл түрге әкеліп щығаруды тырыстым.
conio.h- Есептің жауабы шығу барысыңдағы экранды ұстап тұру мақсатында қолданылатың _getch() функциясы орналысқан.
Iostream- Кітапханасыңда cin, cout еңгізу шығару операторлары жатады.
time.h- Кітапханасында srand() функциясына көмек болатың уақыт мөлшерін басқаратың time() функциясы жатады.
setlocale(LC_ALL, "rus"); - Экранда орыс әріптерің оқуға қөмеқ қөрсетқең функция.
srand()- Әр компиляция сайын экранға әр түрлі кездейсоқ сандарды шығаратын функция.
rand(); - Функцияңы қалай қолдануға болады? Мысалы: бізге а деген масситің бір элементіне rand(); функциясың қолданайық.
Nullptr- кілт сөзі меңзерді білдіреді. Бұл std :: nullptr_t түрінің мәні. nullptr тен кез-келген сілтегіш түріне және кез-келген сілтегіштің мүше түріне мағынасыз ... жалғасы

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