Глоссарий

Семей

МАЗМҰ НЫ

Глоссарий

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Дә рістер

Дә ріс 1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Дә ріс 2.

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

Мақ саты: Мә ліметтер қ ұ рылымдарымен жасалатын ә рететтермен танысу. Алгоритмдер анализі жә не программаларды орындау уақ ыты ұ ғ ымдары.

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

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

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

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

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

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

орындау уақ ыты

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

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

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

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

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

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

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

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

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

Программаның орындалу уақ ыты алғ ашқ ы мә ліметтердің мө лшеріне тә уелді. Мысалғ а, массивтегі ең кіші элементті табу бұ л мә ліметтер элементтерін салыстыруғ а негізгі операция немесе амал. N элементтерін массиві ү шін алгоритмге N-1 салыстыру қ ажет болады жә не оның орындалу уақ ыты Т-ге пропорционал. Алгоритмдердің уақ ыт бойынша кү рделілігін 0 символика деген қ олданылады. Мысалы, егер қ андай да бір программаның орындалу уақ ыты Т(n) О(n²) ретке ие болса, бұ л дегеніміз қ андай да бір С ә лде n₀ константалар болып, n₀-дан ү лкен немесе тең болатын 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 рет орындалады, сондық тан программаның жалпы қ осынды орындалу уақ ыты формуламен анық талады жә не О(n²) ретке ие болады. Жалпы О функциясының мә ні берілгендер қ ұ рылымы алгоритмдер ү шін полиномдық, логорифмдік жә не экспоненциалдық функциялар ішінен таң дап алынады.

Дә ріс 3.

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

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

Массивтерді сұ рыптау алгоритмдері 4-ке бө лінеді:

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

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

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

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

Сұ рыптау немесе объектілер тізімін реттеу деп осы объектілердің қ андай да бір сызық тық реттілікке қ атысты ө суі мен кемуі бойынша орындауды айтамыз. Сұ рыптаудың мә ні сонда жазулар тізімінің реттілігін кілттік ө ріс мә ндері кемімейтін тізбек қ ұ ратындай етуіміз керек. Басқ а сө збен айтқ анда R₁, R₂,.., R_n жазулары кілттік мә ндері K₁, K₂, …, K_n орналасуы керек. Ki₁< Ki₂< ….< Ki_n.

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

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

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

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

Таң дау кө мегімен сұ рыптау.

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

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

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

20, 50, 40, 75, 35.

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

20, 35, 40, 75, 50.

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

20, 35, 40, 75, 50.

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

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 салыстыру жү ргізіледі. Ең тиімсіз жағ дайда тиімділігі О(n²) тең. Жалпы жағ дайда таң дау арқ ылы сұ рыптау кө бікше арқ ылы сұ рыптауғ а қ арағ анда ауыстырылатын сан аздығ ымен тиімді болады. Шейкер сұ рыптау алгоритмі элементтердің барлығ ы немесе кө пшілігі сұ рыпталғ ан жағ дайда пайдаланғ ан тиімді.

Дә ріс 4.

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

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

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

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

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

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

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

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

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

Бинарлық қ оюлар арқ ылы сұ рыптау.

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

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

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

Тез сұ рыптау

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

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

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

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

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

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

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

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

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

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

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

Екі А жіне В реттелген тізімдер берілген. Оның ұ зындық тары сә йкесінше m жә не n. Біріктіру нә тижесінде ұ зындығ ы m жә не n болатын С реттелген тізімін алу қ ажет. ә рбір элемент бойынша біріктіру жү ргізіледі. Ағ ымдағ ы ө ткізу нү ктесі ә рбір тізімнің басына орналасады. Ағ ымдағ ы нү ктедегі мә ндер салыстырылады. Нә тижесінде солардың кішісі массивке кө шіріледі. Тізбектегі мә н ө ң деліп болғ аннан кейін келесі санғ а бір қ адам жасалады да, салыстыру жалғ астырылады.

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

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

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

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

Дә ріс 5.

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

Мақ саты: Тізбектерде элементті іздеу ұ ғ ымын енгізу.

Іздеу (поиск) екіге бө лінеді:

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

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

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

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

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

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

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

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

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

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

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

Low=0

High=8

mid=4

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

mid

Low=5

High=8

mid=6

33> A(mid)

0 1 2 3 4 5 6 7 8

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

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

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

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

4. 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Дә ріс 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 тізімі берілген.

1. head Null

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

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

head Null

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

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

head

Null

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

head Null Null

Дә ріс 8.

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

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

Циклдық тізімдер ұ ғ ымын енгізу. Олармен жү ргізілетін амалдармен танысу.

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

head

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

Екі байланысты сызық тық тізім

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

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

beg

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

rex