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



жүктеу 1.3 Mb.
бет1/5
Дата17.07.2017
өлшемі1.3 Mb.
  1   2   3   4   5




Қазақстан Республикасы білім және ғылым министрлігі

Семей қаласының Шәкәрім атындағы мемлекеттік университеті


3 деңгейдегі СМК құжаты


ПОӘК


ПОӘК


042.39.1.ХХ/01-2013

ПОӘК

«Мәліметтерді өңдеудің құрылымдары мен алгоритмдері» пәні бойынша оқу - әдістемелік материалдар



__.__.20__ж

№__ басылым



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

пәнін оқыту-әдістемелік кешен
5В011100 - «Информатика» мамандығына арналған

оқу - әдістемелік материалдар


Семей

2013


МАЗМҰНЫ





Глоссарий






Дәрістер






Зертханалық сабақтар






Студенттердің өздік жұмыстарының жоспары






1. Глоссарий
Мәліметтер дегеніміз - дербес компьютерде өңдеуге болатын, кез келген ақпаратты сипаттайтын мәнді немесе мәндер жиыны.

Мәліметтердің логикалық құрылымы дегеніміз - сәйес құрылымның моделі, берілу схемасы (екі өлшемді массив, тік бұрышты матрица).

Мәліметтердің физикалық құрылымы дегеніміз - құрылымды компьютер жадысына орналастыру немесе сақтау схемасы (жады ұяшықтарының тізбегі).

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

Сызықтық құрылым мәліметтер типтері – орналасуы бойынша реттелген элементтер тізімін анықтайды.

Сызықтық емес құрылым мәліметтер типтері – позициялық реттеусіз элементтерді анықтайды.

Тікелей кіру дегеніміз – элементті тікелей таңдау және тізімдегі алдыңғы элементтерге байланыссыз таңдауды айтады.

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

Реттелген сызықтық тізімде – мәліметтер бір-біріне қатысты реттеліп орналасады.

Стек дегеніміз – элементтері тізімнің төбесі деп аталатын бір жағынан ғана қосылатын немесе өшірілетін сызықтық тізімді айтамыз (соңғысы келсе біріншісі кетеді).

Шірет (очередь) дегеніміз – тізімнің басынан немесе аяғынан ғана кіруге болатын сызықтық тізім. Элементтер тізімнің соңына қойылады да басынан өшіріледі.

Очередь приоритеті дегеніміз – очередь немесе шірет типті тізім, тізімдегі объектіні өшірген кезде ең жоғары приоритетке ие объект анықталады.

Файл дегеніміз – байттар тізімі. Ол бір ағымға теңеледі, яғни, бір құрылғыдан екінші құрылғыға ауысып отыратын байттар тізбегі. Тек қана дисктік файлға тікелей кіруді жүзеге асыруға болады.

Иррархиялық құрылым – бұл деңгейлері бойынша бөлінетін элементтер жиынындағы, яғни, бір деңгейдегі элемендеңгейде бірнеше ұрпағы болуы мүмкін.

Тармақ (дерево) – бұл түпкі немесе тамыр деп аталатын бір ғана көзден тарайтын элементтері бар мәліметтер құрылымы.

Пирамида дегеніміз – тармақтың ерекше түрі. Мұнда ең үлкен элемент үнемі түпкі деңгейде тұрады.

Топ (группа) дегеніміз элементтері ешқандай реттеусіз орналасқан сызықтық емес құрылым.

Жиын дегеніміз – мәліметтер реттеусіз болғанда және мәліметтердің әрбір элементі өз алдына қайталанбайтын болғанда қолданылатын мәліметтер құрылымы.

Граф дегеніміз – төбелер жиынынан және сол төбелерді қосатын байланыстар жиынынан тұратын мәліметтер құрылымы.

Желі (сеть) дегеніміз – графтың ерекше формасы. Мұнда әрбір байланыстың өз салмағы болады.


2. Дәрістер

Дәріс 1.

Кіріспе, мәліметтер типтері

Мақсаты: Мәліметтердің өңдеудің құрылымдары мен алгоритмдеріне кіріспе. Негізгі ұғымдары. Мәліметтер типтерімен танысу. Кіру әдістері.

Соңғы 20-30 жылда құрылымдалған программалау идеялардың кең таралуы программалаудың теориясы мен практикасына үлкен әсер етіп, сәйкес алгоримдер мен программаларды жасаудағы мәліметтердің типі мен құрлымдарының ролі қайта қарауға алып келді. Осыған байланысты соңғы он жылдықта электронды есептеуіш машиналарды (ЭЕМ) программалық қамтамасыз ету саласында мамандар даярлайтын оқу орындарында мәліметтердің типтері мен құрылымдары пәні пайда болды. Бұл пән ақпараттық технологиялар саласында соған сәйкес программалық қамтамасыз етуге жоғары сапалы мамандар даярлауға мүмкіндік беретін компьютер ғылымы информатиканың фундаментальды (негізгі, түпкі) бөлімі болып саналады. Бұл курстың идеялық мазмұны программалық тілге тәуеді емес, бірақ мәліметтер құрылымын көрнекі түрде белгілеуге болатын Турбо Паскаль тілі қолданылады. Мәліметтер құрылымын кез келген программаның немесе программалық бөлімнің бөлінбес саласы болып саналады. Программаны жасауда нақтылы есепті сипаттайтын мәліметтер жиынын анықтап, есепті шешудің алгоритмін құру керек. Программаның мақсатына қарай мәліметтер әртүрлі күрделі деңгейде болуы мүмкін. Яғни жай типтерден бастап, жеткілікті типтегі күрделі құрылымдарға дейін.



Мәліметтер дегеніміз - дербес компьютерде өңдеуге болатын, кез келген ақпаратты сипаттайтын мәнді немесе мәндер жиыны. Мәліметтердің маңызды мінездемесін беретін тип болып саналады. Ол мәліметтерді компьютер жадысына беруде қолданылады және осы мәндерге орындауға болатын амалдар жиыны мен мәліметтер мәндері жиынын анықтайды. Мәліметтерді ұйымдастырудың логикалық және математикалық моделі Мәліметтер құрылымы деп аталады. Мәліметтердің логикалық құрылымы және физикалық құрылымы ұғымы бар.

Мәліметтердің логикалық құрылымы дегеніміз - сәйес құрылымның моделі, берілу схемасы (екі өлшемді массив, тік бұрышты матрица). Мұнда әрбір элементте индекс болады.

Мәліметтердің физикалық құрылымы дегеніміз - құрылымды компьютер жадысына орналастыру немесе сақтау схемасы (жады ұяшықтарының тізбегі).

Мәліметтердің барлық жиынын екіге бөлуге болады: Статикалық және динамикалық құрылым мәліметтері.



Статикалық құрылым мәліметтері – жай және күрделі болуы мүмкін. Олар қандай да бір заңдылық бойынша жай құрылымдарда қалыптасады. Құрылым элементтерінің өзара орналасуы мен өзара байланысы әрқашан тұрақты болып қалады.

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

Стандартты типтер мәліметтері

файлдар

Байланыспаған динамикалық құрылым



Байланысқан дин. құрылым

Сызықтық


Мәліметтер

Статикалық құрылым мәліметтері

Динамикалық құрылым мәліметтері

Программалаушы.анықтайтынмәлімет

массив

құрылым


бірігу

айналмалы

Тармақталған құрылым


Мәліметтердің типтерін сызықтық құрылымды мәліметтер типтері және сызықтық емес мәліметтер типтері деп бөлуге болады.

Сызықтық құрылым мәліметтер типтері – орналасуы бойынша реттелген элементтер тізімін анықтайды.

Сызықтық емес құрылым мәліметтер типтері – позициялық реттеусіз элементтерді анықтайды.

Тікелей кіру дегеніміз – элементті тікелей таңдау және тізімдегі алдыңғы элементтерге байланыссыз таңдауды айтады.

Индукциялық кіру

Тізбектей кіру
Топтаса кіру

жиын


Мәліметтер типтері

Сызықтық құрылым мәліметтер типт.

Сызықтық емес құрылым мәлім.тип.

Тікелей кіру

массив

құрылым


файл

графиктік

Сөздік

FLASH таблица



Тізім

Стек


шірет

тармақталған

пирамида


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

А[0], А[1], А[2], …, А[n]

Массивтермен жұмыс жасауда элементтерге кіруді ұйымдастыру маңызды әрекет болып саналады.

Элементке логикалық деңгейде кіру үшін – массив аты мен элемент индексі керек. Ал физикалық деңгейде жұмыс жасауда элемент адресін массив атымен ізделіп отырған элемент индексі мен оның ұзындығына қарай есептеп шығару қажет болады.



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

FLASH кестекілтпен байланысты мәліметтерді сақтайды. Кілт – мәліметтерді табу үшін қолданылатын бүтін санды индекске трансформацияланады. Кілт бүтін болуы мүмкін емес.

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

Сызықтық құрылым мәліметтер типтері – мәліметтерге тізбектей кіруді пайдаланғанда мәліметтердің динамикалық құрылымы болып табылады да, келесі қасиеттерге ие болады:

  1. өлшемнің тұрақсыздығы ;

  2. жадыдағы элементтер құрылымдарының физикалық реттілігінің жоқтығы.

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

Реттелген сызықтық тізімде – мәліметтер бір-біріне қатысты реттеліп орналасады. Стек дегеніміз – элементтері тізімнің төбесі деп аталатын бір жағынан ғана қосылатын немесе өшірілетін сызықтық тізімді айтамыз (соңғысы келсе біріншісі кетеді).

Шірет (очередь) дегеніміз – тізімнің басынан немесе аяғынан ғана кіруге болатын сызықтық тізім. Элементтер тізімнің соңына қойылады да басынан өшіріледі.

Очередь приоритеті дегеніміз – очередь немесе шірет типті тізім, тізімдегі объектіні өшірген кезде ең жоғары приоритетке ие объект анықталады.

Файл дегеніміз – байттар тізімі. Ол бір ағымға теңеледі, яғни, бір құрылғыдан екінші құрылғыға ауысып отыратын байттар тізбегі. Тек қана дисктік файлға тікелей кіруді жүзеге асыруға болады.

Иррархиялық құрылым – бұл деңгейлері бойынша бөлінетін элементтер жиынындағы, яғни, бір деңгейдегі элемендеңгейде бірнеше ұрпағы болуы мүмкін.

Тармақ (дерево) – бұл түпкі немесе тамыр деп аталатын бір ғана көзден тарайтын элементтері бар мәліметтер құрылымы.

Пирамида дегеніміз – тармақтың ерекше түрі. Мұнда ең үлкен элемент үнемі түпкі деңгейде тұрады.

Топ (группа) дегеніміз элементтері ешқандай реттеусіз орналасқан сызықтық емес құрылым.

Жиын дегеніміз – мәліметтер реттеусіз болғанда және мәліметтердің әрбір элементі өз алдына қайталанбайтын болғанда қолданылатын мәліметтер құрылымы.

Граф дегеніміз – төбелер жиынынан және сол төбелерді қосатын байланыстар жиынынан тұратын мәліметтер құрылымы.

Желі (сеть) дегеніміз – графтың ерекше формасы. Мұнда әрбір байланыстың өз салмағы болады.
Дәріс 2.

Мәліметтер құрылымдарымен жасалатын әрекеттер

Мақсаты: Мәліметтер құрылымдарымен жасалатын әрететтермен танысу. Алгоритмдер анализі және программаларды орындау уақыты ұғымдары.
Құрылымдағы мәліметтер қандай да бір әрекеттер көмегімен өңделеді. Мәліметтер құрылымдарын таңдау осы әрекеттер орындайтын жиілікке тәуелді болады. Мәліметтерді өңдеуде келесі әрекеттер маңызды рольге ие болады:

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

  2. Іздеу. Яғни берілген мәні бар элементтердің орнын табу.

  3. Қыстырып қою. Яғни құрылымға жаңа элементтер кіргізу.

  4. Өшіру . Құрылымдағы элементті алып тастау.



Алгоритмдер анализі және программаларды

орындау уақыты
Бір есепті шешуге арналған әртүрлі алгоритмдерді салыстыру үшін программаның орындалу уақытын жуық мөлшерде анықтау үшін алгоритмдердің математикалық анализі қолданылады. Қолданбалы есептерді шешу процесінде есеп шығарудың неғұрлым жақын алгоритмін таңдау керек болады. Мұнда алгоритм келесі талаптарды қанағаттандыруы керек:

  1. Түсінуге жеңіл, программалық кодқа және орындауға, аударуға жеңіл болуға тиіс.

  2. Компьютер ресурстарын тиімді пайдалану және орындалу жылдамдығы неғұрлым тез болуы керек.

Программаның орындалу уақытына келесі факторлар әсер етеді:

  1. Алғашқы ақпаратты программаға енгізу.

  2. Орындалып жатқан программаның компилияцияланған кодының сапасы.

  3. Программаның орындалуында пайдаланылып жатқан жатқан машиналық инструкциялар.

  4. Сәйкес программа алгоритмінің уақытша күрделілігі.

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

Программаның орындалу уақыты алғашқы мәліметтердің мөлшеріне тәуелді. Мысалға, массивтегі ең кіші элементті табу бұл мәліметтер элементтерін салыстыруға негізгі операция немесе амал. N элементтерін массиві үшін алгоритмге N-1 салыстыру қажет болады және оның орындалу уақыты Т-ге пропорционал. Алгоритмдердің уақыт бойынша күрделілігін 0 символика деген қолданылады. Мысалы, егер қандай да бір программаның орындалу уақыты Т(n) О(n2) ретке ие болса, бұл дегеніміз қандай да бір С әлде n0 константалар болып, n0-дан үлкен немесе тең болатын n константалар үшін Т(n)<=cn теңсіздігі орындалады. Яғни, орындалу уақыты ең аз дәрежеде өсетін программаларды таңдап алуы керек. Бұл дегеніміз, неғұрлым өсу дәрежесі аз болса, компьютердің шығарып отырған есептің өлшемі соғұрлым көп болады деген сөз. Программаның орындалу уақытын теориялық түрде табу күрделі математикалық есеп, оның шешілу үшін бірнеше базалық принциптерді білу керек. Алдымен 3 маңызды ережелерді қарастырамыз:


        1. Тұрақты көбейткіштер уақыт бойынша күрделі реттік анықтау үшін маңызды емес, яғни О(k*f)=0.

        2. Көбейткіштер ережесі: екі функцияның уақыт бойнша күрделі реттің көбейткіштері олардың күрделіліктің О(f*g)=O(f)*O(g).

        3. Қосындылар ережесі: функцияның уақыт бойынша күрдел реттің қосындылары қосылғыштардың ең үлкенінің ретіне тең болады. О(n+n+n)=O(n).



Программалар анализінің ережелері:

  1. Меншіктеу, оқу және жазу операторларының орындалу уақыты О(1) ретке ие болады.

  2. Операторлар тізбегінің орындалу уақыты қосындылар ережесі бойынша анықталады.

  3. Шартты оператордың орындалу уақыты шартты түрде орындалып отырған оператордың орындалу уақытынан тұрады. Логикалық өрнекті есептеу уақыты – жалпы О(1) ретке ие болады. Барлық шарт конструкциясының уақыты логикалық өрнекті есептеу уақытынан және логикалық өрнек, ақиқаты және жалған мәндерді қабылдауда жүзеге асатын операторларды орындауға қажет ең көп уақыттан тұрады.

  4. Циклдарды орындау уақыты – цикл денесі оператордың орындалу уақытынан және циклды тоқтату шартын есептеудің уақытынан тұратын барлық цикл итерацияларының уақытын қосқанға тең болады.

Сұрыптауға жататын элементтер саны кіретін мәліметтер көлемге өлшем бірлігі болып ткабылады. Мұндағы соңғы үш оператор О(1) орындалу ретіне ие болады. Қосындылар дәрежесіне сәйкес бұл операторлар топтары О(мах(1,1,1))=О(1).



Егер операторы үшін логикалық өрнекті тексеру О(1) уақыт ретіне тең болады. Соңғы 5 оператор тобының, яғни ішкі циклдің орындалу ретін қарастырамыз, бұл операторлар үшін әрбір итеракциядағы орындалу уақыты О(1)-ге ие болады. Цикл n-1 рет орындалады. Сондықтан, көбейткіш ережесі бойынша циклдің барлық орындалу уақыты: О((n-1)*1)=O(n*1).

Сыртқы циклді қарастырамыз: сыртқы цикл n-1 рет орындалады, сондықтан программаның жалпы қосынды орындалу уақыты формуламен анықталады және О(n2) ретке ие болады. Жалпы О функциясының мәні берілгендер құрылымы алгоритмдер үшін полиномдық, логорифмдік және экспоненциалдық функциялар ішінен таңдап алынады.


Дәріс 3.
Массивтерді сұрыптау алгоритмдері. Таңдау көмегімен сұрыптау. Ауыстыру арқылы сұрыптау.

Мақсаты: Массивтерді сұрыптау алгоритмдері ұғымдары, олардың түрлерімен танысу. Таңдау арқылы сұрыптау жүргізу. Ауыстыру арқылы сұрыптау әдісімен танысу.
Массивтерді сұрыптау алгоритмдері 4-ке бөлінеді:

  1. Таңдау арқылы сұрыптау.

  2. Ауыстыру арқылы сұрыптау (көпіршік әдіісі).

  3. Қою арқылы арқылы сұрыптау.

  4. Тез сұрыптау.


Сұрыптау немесе объектілер тізімін реттеу деп осы объектілердің қандай да бір сызықтық реттілікке қатысты өсуі мен кемуі бойынша орындауды айтамыз. Сұрыптаудың мәні сонда жазулар тізімінің реттілігін кілттік өріс мәндері кемімейтін тізбек құратындай етуіміз керек. Басқа сөзбен айтқанда R1, R2, .. , Rn жазулары кілттік мәндері K1, K2,…,Kn орналасуы керек. Ki12<….n.

Мұнда реттелген тізбектегі кілттердің бірдей мәндері бар жазулар бір-бірімен қатар орындалады. Сұрыптау әдістері 2 категорияға бөлінеді:

- массивтерді сұрыптау (ішкі сұрыптау)

- тізбектелген файлдарды сұрыптау (сыртқы сұрыптау).

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

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


Мысалға, 50,20,40,75,35 массив берілген.

0-жүріс. 20-ны таңдаймыз. Оны А0-мен ауыстырамыз (А0=50).

20,50,40,75,35.

1-жүріс. 35 таңдаймыз. Оны А1-мен орын ауыстырамыз.

20,35,40,75,50.

2-жүріс. 40 таңдаймыз. Оны А2-мен орын ауыстырамыз.

20,35,40,75,50.

3-жүріс. 50 таңдаймыз. Оны А3-пен орын ауыстырамыз.

20,35,40,50,75.
Соңғы қалған 75 саны ең үлкен элемент сұрыпталып шыққанда:

20,35,40,50,75.


Сұрыптау – массив өлшеміне ғана тәуелді салыстырулардың белгіленген санына ие болуы керек. i-ші жүрісте (A… A)-ге дейінгі элементтердің салыстырулар саны (n-1-(i+1)+1)=n-i-1 тең болады.

Салыстырулардың жалпы саны мына формуламен анықталады:

Алгоритмнің күрделілігі – О(n) тең болады.




Ауыстыру арқылы сұрыптау.
Ауыстыру арқылы сұрыптау. N элементтен тұратын а массивін айырбастау арқылы сұрыптау үшін немесе көпіршік әдісімен сұрыптау үшін n-ші жүріс қажет. Әрбір жүрісте көршілес екі элемент салыстырылады және егер 1-сі үлкен болса немесе 2-не тең болса, онда бұл элементтер орындарымен ауысады. әрбір жүрістің аяғында ең кіші элемент ішкі тізімнің жоғарғы жағына көтеріліп отырады. Бұл қайнап жатқан судың ішіндегі ауаның көбікшесіне ұқсас. Сондықтан көпіршік әдісі деп аталады.

Мысал. Массив:

50,20,40,75,35

0-жүріс. 50 мен 20салыстырылады.

20,50,40,75,35

1-жүріс. 50 мен 40 салыстырылады

20,40,50,75,35

2-жүріс. 50 мен 70 реттелген, сондықтан қалады.

20,40,50,70,35

3-жүріс.75 пен 35 салыстырылады.

20,40,50,35,75

4-жүріс. 50 мен 35 салыстырылады

20,40,35,50,75

5-жүріс. 40 пен 35 салыстырылады

20,35,40,50,75

20 мен 30 реттелген

20,35,40,50,75 болып реттеледі.
Массивтегі жүрістер саны минимальды немесе максимальды элемент қай жерде орналасқанына байланысты. Мұнда бірінен кейін бірі келетін жүрістердің бағытын ауыстыру арқылы жылдамдатуға болады. Мұндай алгоритм Шейкер сұрыптауы деп аталады.

Есептеу күрделілігі. Массив реттелген болған жағдайда бүкіл тізім бойынша 1 ғана жүріс өтеді. Мұнда тиімділігі О(n)-ға тең. Ал ең тиімсіз жағдайда i-1 жүріс орындалады және i-ші жүрісте n-i-1 салыстыру жүргізіледі. Ең тиімсіз жағдайда тиімділігі О(n2) тең. Жалпы жағдайда таңдау арқылы сұрыптау көбікше арқылы сұрыптауға қарағанда ауыстырылатын сан аздығымен тиімді болады. Шейкер сұрыптау алгоритмі элементтердің барлығы немесе көпшілігі сұрыпталған жағдайда пайдаланған тиімді.
Дәріс 4.

Қою арқылы сұрыптау. Тез сұрыптау

Мақсаты: Қою арқылы сұрыптау әдісімен танысу. Тез сұрыптау әдісімен танысу. Сұрыпталған элементтерді біріктіру әреекттерін орындау.

Қою арқылы сұрыптау – келесі процеске ұқсас. Карточкаларға аттарды жазып, карточкаларды алфавит бойынша өзіне керекті орынға қыстырып қою арқылы реттеу. Мысалға:

50,20,40,75,35 массивін қыстыру арқылы сұрыптау керек.

50 элементінен бастаймыз. 20-ны 0 позициясына қыстыру, 50-ді 1 позициясына жылжыту.

40-ты 1 позициясына қыстыру, 50-ді 2 позицияға жылжыту.

75-ті 3 позициясына қыстыру.

35-ті 1 позициясына қыстыру, қалғандарын оңға қарай жылжыту.

Есептеу күрделілігі: жалпы салыстырулар саны -ге тең. Ең жақсы жағдайда, яғни тізім реттелген жағдайда күрделілігі О(n)-ге , ал жаман жағдайда О(n2)-ге тең.
Бинарлық қоюлар арқылы сұрыптау.

Бұл жай енгізулермен сұрыптаудың жақсартылған варианты. Жаңа элементті қосуға қажетті дайын тізбек реттелген болып, енгізу орнын неғұрлым жылдам табуға негізделген. Ол үшін дайын тізбектің ортаңғы элементі ізделіп, ары қарай ортасынан бөлу қашан енгізу орыны анықталғанша жалғаса беретін бинарлық іздеу жүргізіледі.



Есептеу күрделілігі: Енгізу орыны табылады егер, al<=item<=ar болса. Соңында іздеу интервалы 1 ге тең болуы керек; бұл дегеніміз I элементтерден тұратын интервал ортасынан (log2i) рет бөлінеді деген сөз.

Салыстырулардың минимальды саны барлық элементтер кері ретпен орналасқанда, ал максимальды саны олардың осы кезде реттелген болғанында талап етіледі.



Тез сұрыптау
Тез сұрыптау әдісі – күнделікті тәжірибеден алынған.

Мысалы: Аттары бойынша алфавиттік карточкалар жиынын қандай да бір әріпке қатысты, мысалы К, екі кіші жиынға бөлуге болады. Барлық К-дан кіші немесе тең тең болатын бір жиынға, К-дан үлкен болатын бір жиынға бөлеміз. Одан кейін әрбір жиын тағы да екіге бөлінеді т.с.с. Тез сұрыптау алгоритмінде орталық элементті анықтап, сол арқылы бөлу әдісі қолданылады. Яғни, алғашқы массив екіге бөлінеді. Орталық элементтен үлкен және орталық элементтен кіші. Тура осы әрекет алынған массивтің 2 бөлігіне де жүргізіледі. Осылайша бөліне береді. Әрбір бөлікте бір ғана қалғанша жалғастырамыз.

Сұрыптау принципі:

Массивтің орталық элементі таңдап алынады. Массивтің барлық элементтері солдан оңға және оңнан солға қарай қарап өтіледі.

І. Солдан оңға қарай қозғалғанда A[scan up] деген элементті іздейміз және бұл элемент орталық элементтен үлкен болуы керек, оның позициясын есімізге сақтап аламыз. Оңнан солға қарай қозғалғанда A[scan down] деген элементті іздейміз. Ол элемент орталық элементтен кіші немесе тең болады. Позициясын есте сақтаймыз. Табылған элементтердің орындарын ауыстырамыз және scan up және scan down индекстері қиылысқанша іздеуді жалғастырамыз.

1-этапты орындап болғаннан кейін алғашқы масситің элементтері орталық элементке бөлінеді.

2-этапта 1-этаптың әрекеттері массивтің оң жақ және сол жақ бөліктері үшін жеке-жеке орындалады.

3-этапта осы әрекеттердің барлығы 4 бөлігі үшін жеке-жеке орындалады.

4-этапта 4 бөлігі жеке-жеке орындалады.

Есептеу күрделілігі. Тиімділік анализі кей жағдайда ғана мүмкін болады. Айталық, массив элементтер саны n=2 (K=log2n) 1-сканерлеуде n-1 салыстыру жүргізіледі. Оның нәтижесінің өлшемі өлшемді ішкі тізім пайда болады. Өңдеудің келесі фазасында әрбір ішкі тізім үшін n/2 салыстыру қажет болады. Осылайша, бөлу процесі табылған ішкі тізімдер тек бір ғана элементтер тұрғанша К жүрістен кейін аяқталады. Мұндағы салыстырулардың жалпы саны мына формуламен анықталады: n*k=n*log2n. Жалпы түрдегі тізім үшін есептеу күрделілігі – О(n log2n) тең болады. Ал ең нашар жағдайда орталық элемент ең кіші элемент болғанда есептеу күрделігі O(n2) тең болады.
Сұрыпталған тізбектерді біріктіру
Екі А жіне В реттелген тізімдер берілген. Оның ұзындықтары сәйкесінше m және n. Біріктіру нәтижесінде ұзындығы m және n болатын С реттелген тізімін алу қажет. әрбір элемент бойынша біріктіру жүргізіледі. Ағымдағы өткізу нүктесі әрбір тізімнің басына орналасады. Ағымдағы нүктедегі мәндер салыстырылады. Нәтижесінде солардың кішісі массивке көшіріледі. Тізбектегі мән өңделіп болғаннан кейін келесі санға бір қадам жасалады да, салыстыру жалғастырылады.

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


Сұрыпталған тізбектерді біріктіру алгоритмі


  1. Бір тізбек немесе тізбектің екеуі де біткенше келесі әрекеттерді орындау керек. Яғни, егер 1-тізбектің 1-элементі 2-тізбектің элементіне тең немесе кіші болса, онда оны шығатын тізбекке жазып қойып, 1-тізбектің келесі элементіне көшу керек. Әйтпесе, шығатын тізбекке 2-тізбектің элементін жазып, 2-тізбектің келесі элементіне көшу керек. Одан кейін шығатын тізбектің келесі элементіне көшу керек.

Егер біреуі аяғына дейін өңделмесе, онда сол қалдықты шығатын тізбекке көшіру керек.

Дәріс 5.

Тізімдерде іздеу әректтерін жүргізу

Мақсаты: Тізбектерде элементті іздеу ұғымын енгізу.
Іздеу (поиск) екіге бөлінеді:

  1. Тізбектеліп іздеу.

  2. Бинарлық іздеу.




  1. Тізбектеліп іздеу. Тізбектеліп іздеудің мағынасы элементтерді тізбекпен таңдап алуды және элементтерді кілт мәнімен салыстырудан тұрады.

Функция парамертлер ретінде массивті, элементтер санын және кілт мәнін алады. Сәйкес элементтің индексін қайталайды, егер іздеу сәтсіз болса, -1 мәнін береді. Тізбектеліп іздеу кез келген тізбек үшін қолайлы, тізбектеліп іздеудің орталық тиімділігі O(n) тең болады.




  1. Бинарлық іздеу.

Бинарлық іздеулер тек қана реттелген тізімдер үшін ғана қолданылады. Мысалы элементтер тұратын массив берілсін. Тізімнің басындағы және соңындағы элементтердің индекстері мынадай low=0 high=n-1 дейін болады. Бинарлық іздеудің алгоритмі:

  1. Массивтің ортаңғы элементінің индексін табу: mid=(low+high)/2.

  2. Орталық элементтің мәнін кілтпен салыстыру «Key». Егер салыстыру нәтижесінде сәйкестік бар болса, онда mid индексін кілтті табу үшін қолданамыз. Егер орталық элемент мәні кілттен кіші болса, онда қарастырылып отырған тізімнің оң жағындағы бөлігінде іздеу жүргіземіз. Егер керісінше үлкен болса, онда сол жақтағы бөлігінде іздеу жүргіземіз.

  3. Егер ізделіп отырған элемент тізімде жоқ болса, онда үзу индикаторын береміз.


Мысалға: Бүтін сандар тұратын А массиві берілсін. 33 кілті берілген элементі бар табу керек.

Мысал элементтері: А




0

1

2

3

4

5

6

7

8

-7

3

5

8

12

16

23

33

55

Low=0


High=8

mid=4


33>A(mid) 0 1 2 3 4 5 6 7 8

-7

3

5

8

12

16

23

33

55

mid
Low=5

High=8


mid=6

33>A(mid)


0 1 2 3 4 5 6 7 8

-7

3

5

8

12

16

23

33

55

mid

Low=7


High=8

mid=7


33=A(mid)

Сонда тізбектеліп іздеуде 8 салыстыру, ал бинарлық іздеуде 3 салыстыру жүргізіледі.


Дәріс 6.

Файлдар және сыртқы тасымалдаушылардағы мәліметтер мен операциялар.

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

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

Аппаратты тұрғыдан алғанда файл жазулары дискте сақталатын, белгілі ұзындықтағы мәліметтер блоктарын құрайды. Логикалық тұрғыдан алғанда жазулар файлда тізбектеліп орналасады.

Файлдық жүйе жекелеген жазуларға, сондай-ақ, барлық файлға толығымен кіруді жүзеге асыруға мүмкіндік береді.



Сыртқы сұрыптау

Файлдар түрінде ұйымдастырылған мәліметтерді сұрыптау сыртқы сұрыптау деп аталады. Егер файл оперативті жадыда сыймайтындай үлкен болса, онда сұрыптау - өте үлкен проблема. Барлық мәліметтерді бір массивте сақтауға болмайтындықтан, оларды сақтау үшін уақытша файлдарды қолдану керек.

Тура біріктіру арқылы сұрыптау екі реттелген тізімді біріктіретін жай біріктіру әдісін қолданады. Басты идеясы біртіндеп үлкейетін элементтер түрінде файл ұйымдастырылатынында, яғни жазулар тізбегі r1<=r2<=…<=rn жазулар тізбегі. Мысалға, 3 деген ұзындықтағы сериялармен ұйымдастырылған бүтін сандар тізбегі:
7 15 29 7 11 13 16 22 31 5 12

Мұнда соңы 3 тен кем ұзындықта болуы мүмкін, бірақ оның жазулары да сұрыпталған.


Сұрыптау алгоритмі
FC 5,15,35,30,20,45,35,5,65,75,40,50,60,70,30,40,25,10,45,55


  1. Файлды екіге бөлеміз. Оның элементтерін сәйкесінше екіге бөлеміз. Осылайша, әрбір жаңа файлда элементтер тізімі пайда болады.

  2. Ішкі тізімдерді салыстырамыз. Яғни, FA файлынан және FB файлынан бір-бір элементтен таңдап алып, жай біріктіру алгоритмін пайдалана отырып, қайтадан FC файлына жазамыз. Осылайша, барлық элементе қайтадан FC файлға ауысқанша жалғастырамыз.

FА 5,35,20,35,65,40,60,30,25,45

FВ 15,30,45,5,75,50,70,40,10,55

FC 5,15,30,35,20,45,5,35,65,75,40,50,60,70,30,40,10,25,45,55




  1. Бір қадамды қайталап, FА және FВ файлдарына екі элементті серияларды жазып шығарамыз.

FА 5,15,20,45,65,75,60,70,10,25

FВ 30,35,5,35,40,50,30,40,45,55




  1. FА және FВ файлдарындағы екі элементті серияларды FC файлына 4 элементті серияға біріктіреміз. Мұнда реттелген тізімдерді біріктіру алгоритмін пайдаланамыз.

FC 5,15,30,35, 5,20,35,45

40 50 65 75 30 40 60 70 10 25 45 55


  1. FС файлын екіге бөлетін қадамды FА және FВ файлында сәйкесінше 4 8 т.с.с элементтер серияларын құрай отырып және сериялардың әрбір жұптарын біріктіре отырып қайталаймыз. Процесс FА және FВ файлдары бір-бір реттелген тізімнен тұрғанда және олар FC сұрыпталған файлына соңғы рет бірікенде аяқталады.

Түзу бірігу сұрыптау анализі.

Сұрыптау бір элементі ішкі тізімдердің жүрістер сериясынан тұрады, әрбір жүрісте ішкі тізімнің ұзындығы екі еселенеді. Ол үшін log2n жүріс қажет болады. Түзу бірігу арқылы сұрыптау 2n log2n мәліметтерді қарауды талап етеді, сондықтан оның күрделілік реті O(n log 2n).


Табиғи бірігу арқылы сұрыптау

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



Сұрыптау алгоритмі

Алғашқыда FC алғашқы файлды және алғашқы ұзындықтағы реттелген серияларды жасау үшін оперативті жадыдағы буфер керек:



  1. Алғашқы файлдың мәліметтері буферге блок бойынша оқылады.

  2. Әрбір блок сұрыпталудың кез келген алгоритмі арқылы сұрыпталады да (мысалы, тез сұрыпталу), кезек-кезек FB және FA файлдарына көшіріліп отырады.

  3. FC файлы біткен кезде қайтадан уақытша FА және FВ файлындағы мәліметтер блоктары қайтадан біріге бастайды.

  4. Осылайша, сұрыптау жай бірігуге ұқсас жалғаса береді.

Алгоритм анализі:

Мұнда әрбір жүрістен сериялардың саны екі есе қысқарады. Сондықтан жіберулердің жалпы саны ең жаман жағдайда n log2n тең болады. Ал жалпы жағдайда одан да аз болады.


Балансталған көп жолдық бірігу

Тізбектелген сұрыпталуға кететін шығын жүрістің санына прорпорционал болады. Шығынды азайтудың бір жолы екі уақытша немесе одан да көп файлдарды пайдалану R сериялы бірігу n уақытша файлдарға бөлінгенде ішкі тізімдерден тұратын тізбек құрайды. Екінші жүріс бұл санды дейін қысқартады. Ал үшінші жүріс дейін қысқартады. Осылайша к жүрістен кейін бөлік қалады. n элементі N жүрісті бірігу мен сұрыптауда жүрістің жалпы саны k=logNn (N-жол, n-элементтер саны) тең болады. Әрбір жүрісте қайта жазудың n операциясы жүретін болғандықтан ең жаман жағдайда операцияның жалпы саны M=n logNn болады.


Дәріс 7.

Мәтіндерге тізбектеліп кіретін мәліметтердің сызықтық құрылымдық типтері.
Мақсаты: Мәтіндерге тізбектеліп кіретін мәліметтердің сызықтық құрылымдық типтері ұғымы. Байланған сызықтық тізімдер түсініктерін енгізу.
Байланған сызықтық тізімдер

Тізім дегеніміз – сандары өзгеруі мүмкін элементтердің жиынтығы. Ол шынжырдағы шығыршық іспеттес. Тізімнің ұзындығы жаңа шығыршықтар қосу арқылы көбеюі мүмкін. Жаңа элементтер тізімге тізімнің бір жерін үзіп, соған жаңа элемент қосып, қайтандан жалғау арқылы кіргізуі мүмкін. Элементтер тізіміне сол сияқты тізімді үзіп, бір шығыршықты алып қайта жалғап қойған сияқты алынып тасталады. Тізімдер үш түрлі болады:

1. Бір байланысты.

2. Циклық

3. Екі байланысты




  1. Бір байланысты сызықтық тізім.

Бір байланысты сызықтық тізім екі әдіспен жүзеге асуы мүмкін:

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

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

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


  1. Тізімді массив негізінде жүзеге асыру орындалмас бұрын тізімнің максималды өлшемін көрсетуді талап етеді.

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

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

Байланған тізімнің құрылымы келесі түрде берілуі мүмкін:


head

ptr rear NULL



Dann1

Next




Dann2

Next




Dann N-1

next




dannN

next

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


Тізімдермен жүргізілетін операциялар

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





  1. Байланған тізімнен өту.

  2. Тізімді тазалау.

  3. Элементті енгізу схемасы.



Реттелген тізімді жасау

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


60

65

74



82

1. head Null


осы тізімге 50,70,90 сандарын қою керек.


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

60

65

74



82

50

head Null


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




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

head
60

65

74



82

50

70



Null


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

60

65



74

82

50



90

head Null Null




Дәріс 8.

Циклдық тізімдер. Стектер.

Мақсаты: Стектер ұғымы енгізу. Стектердің амалдарын, қолданылу аймақтарын беру.

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

Dann1


next

Dann2


next

dannN


next

head


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

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

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

null


val

next


prev

val


next

prev


vall

next


prev

null


vall

beg

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

rex


prev

Val 1


next

prev


Vall 2

next


prev

next


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

В

В



А

А

С



А

В

А



А

Д

А



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


pushA pushB pushC Pop Pop PopD

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



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

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

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

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

Стек төбесі

N мәлімет

Көрсеткіш

n-1 мәлімет

Көрсеткіш

Көрсеткіш

2 мәлімет

Көрсеткіш

1 мәлімет



Стек операциялары

  1. Элементті стекке қосу.

  2. Элементті стектен өшіру (өшіріліп отырған элементтің мәнін берумен бірге)

  3. Жоғарғы элементтің мәнін беру.

  4. Стекті тазалау.

  5. Стек элементтің санын басып шығару.


Стектер қолданылады:

  1. Жадымен жұмыста. Мысалға, printf және scanf функциялары жұмысы стекті пайдалануға негізделген.

  2. Сөйлем поендром болатындығын немесе болмайтындығын анықтау үшін қолданылады. Полендром дегеніміз – түзу және кері бағытта бірдей оқылатын жол. Мысалға, 121, ара.

  3. Әртүрлі негіздегі мәліметтерді шығару үшін.

  4. Электронды калькуляторлар жасауда.


Дәріс 9.

Шіреттер (Очереди)

Мақсаты: Шіреттер ұғымын, шіреттердің қолданылу аймақтары, операциялары жайлы түсініктер қалыптастыру.
Шірет дегеніміз – ұзындық айнымалысының тізбектелген тізімі. Мұнда элементтерді қосу тізімнің бір жағынан жүргізіледі, ал элементтерді алып тастау келесі басынан жүргізіледі. Шіреттің принципі мынадай: FIFO – first in /first out. Бұл да аббревиатура.

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

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

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

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

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

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

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

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

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



А, В, С

А

В



С

С

front rear


Элементті өшіру

В

С



front rear
В элементін өшіру

front rear


С

D

E



F

DEF элементін қосу

front rear

Осындай модельмен жүргізіледі. Бұл модель тиімді емес. Мысалға, шіретте 1000 элемент болсын. Егер басынан 1 элемент өшірілсе (кетсе) онда 999 элемент солға қарай жылжуы керек. Мұндай жағдайда сақиналық шірет тиімді. Сақиналық шіреттің элементтері логикалық түрде шеңберге ұйымдастырылады (сақиналық). Front айнымалысы шіреттегі бір элементтің орыны болып табылады және ол өшірулерді орындаған сайын шеңбер бойымен оңға қарай жылжиды. Массив негізінде:


А

С В


С В

2. rear 1. rear front
front
A-ны өшіру

D E

С В

D


С В

rear


front front

rear


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

Шіреттерді көрсеткіштер көмегімен жүзеге асыруда шірет өлшемі кіруге болатын бос жадының көлемімен шектеледі. Оны графикпен келесі түрде беруге болады:



next

Val n

next

Val n-1

next

Val 2

next

Val 1
Front

Null


Шірет объектісімен жүргізілетін операциялар


              1. Шіретке элементті қосу

              2. Шіреттен элементті алып тастау (өшірілген элементтің мәнін беру)

              3. Бірінші элементтің мәнін беру.

              4. Шіретті тазалау

              5. Шірет элементінің санын беру.

Шіреттер қолданылады:

        1. Компьютерлік модельдеуде (банктегі клиент шіретін модельдеу)

        2. Көп адамдар қолданылатын операциялық жүйелерде.

        3. Мәліметтерді сұрыптауда


Приоритеттер шіреті

Приоритеттер шіреті дегеніміз – бұл тзімнен жоғары приоритетті элемент өшірілетін шіреттің модификацияланған версиясы.

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



Элемент 1


20

Элемент 2

0


Элемент 3

40


Элемент 4

30


Элемент5

20

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

2,1,5,4,3

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

Элемент 1


20

Элемент 2

0


Элемент 3

40


Элемент 4

30


Элемент5

20













2,1,5,4,3



Элемент 1


0

Элемент 2

20


Элемент 3

20


Элемент 4

30


Элемент5

40
















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


Дәріс 10.

Ағаштар. Тармақтар.

Мақсаты: Ағаштар немесе тармақтар ұғымын енгізу, негізгі түсініктерін беру, екілік тармақ құрылымымен таныстыру.

Тармақ дегеніміз – иеархиялық құрылым құратын элементтер мен қатынастардың жиынтығы.

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



А

E

D

F

С

В

G

H

I

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



  1. графтар

  2. кірістірілген жақшалар

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

  4. кесінді тізбектер.


1. Графтар. Бәрі А түйінінен тарайды
A

B

D

H

C

E

F

I

J

G

2. Кірістірілген жақшалар:
(A(B(E,F(I,J)), C(G),D(H)))


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

А

В

C

D



F

I

J

E

H

G

4. Кесінді тізбек.
A B E I

F J


C G

D H


Көбінесе тармақтарды бейнелеу үшін графтар қолданылады.
Дәріс 11.

Екілік бинарлық тармақтар. Екілік тармақтардың құрылымы.

Мақсаты: Екілік бинарлық тармақтар ұғымын қалыптастыру . Екілік тармақтардың құрылымы беру.
Программалауда екілік тармақтар кең қолданылады. Екілік тармақтар келесі қасиеттерге ие:

  1. екілік тармақта әрбір төбенің екіден артық балалық түйіні болмайды.

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

Екілік тармақ рекурсивті құрылымды болды. Себебі әрбір түйіні өзінің астындағы бұтақтың тамыры немесе түбірі болып табылады. Оны өздері де (бұтақтың) сол жақ және оң жақ бұтақтардың түбірлері болып табылатын балалары бар. Сондықтан тармақтарды өңдеу процедуоамы көбінесе рекурсивті болып табылады. Екілік тармақ дегенімізүш қиылыспайтын ішкі жиындарға бөлінетін түйіндер жиыны. Мұнда {R} – түбірлі түйін, {L1,L2,…,Ln} – R сол жақ бұтақ, {R1, R2,…,Rn} – R оң жақ бұтақ. Яғни оны былай бейнелеуге болады.
R

L

R

L

L

L

R

Оң жақ бұтақ

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

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

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

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

(4-деңгей) (3-деңгей)

Толық тармақ

(2-деңгей)

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

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



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

        2. Динамикалық құрылым ретінде беру.

Массивті пайдалана отырып тізбектеп беруде екілік тармақ бір өлшемдік массивке қапталады. Мұндай беруде тек бір ғана TREE сызықты массиві қолданылады. Тармақтың түбірі массивтің бірінші элементі TREE[0] –де орналасады. Келесі екі балалық төбелері көршілес элементтерде орналасады. Т.с.с.

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

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

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

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

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



Көрсеткіштер өрістері – сол жақ көсеткіш және оң жақ көрсеткіш деп аталады. Себебі, олар сәйкес сол және оң тармаққа көрсетеді.

Жапырақтық түйін – сол және оң жақ түйін көрсетуде Null болады.

А

В

F

С

D

E

G

H

Left


A

Right


Left

B

Right



Null

C

Right



Null

D

Null



Left

E

Null



H

Null


Null

G

Null



Null

F

Null



Right

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



              1. түбір ретінде бір түйінді алу.

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

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

Мысалы, 1,2,3,4,5,6,7,8,9,0 сандар тізбегі үшін идеалды балансталған тармақ келесі түрде болады:

1

2

0

7

3

5

4

6

8

9

Өрнектердің екілік тармақтары


Балансталған тармаққа қосу
Ортасынан бөлу алгоритмі
Есептеу күрделілігі.

: ebook -> umkd
umkd -> «Орта ғасырдағы Азия және Африка тарихы»
umkd -> ПӘннің ОҚУ – Әдістемелік кешені «Орта ғасырдағы Азия және Африка тарихы»
umkd -> Азақстан республикасының білім және ғЫЛ
umkd -> ПӘндердің ОҚУ-Әдістемелік кешені
umkd -> Қазақстан республикасы білім және ғылым министрлігі
umkd -> Қазақстан республикасы білім және ғылым министрлігі
umkd -> 123 -беттің сі казақстан республикасы білім және ғылым министрлігі
umkd -> ПӘндердің ОҚУ-Әдістемелік кешені
umkd -> Экотоксикология» пәнінің оқу-әдістемелік кешені №1 басылым 050608-«Экология» мамандығына арналған
umkd -> Қазақстан республикасы білім және ғылым министрлігі


  1   2   3   4   5


©stom.tilimen.org 2017
әкімшілігінің қараңыз

    Басты бет