Лкция13

1.

Байланыстырылған
тізімдер: Құрылымы,
Біріктіру, Кірістіру, Жою
және Жадпен Жұмыс
Негіздері
Деректер құрылымдарының негізгі түрлерінің бірі – динамикалық,
икемді және күшті құрал

2.

1-тарау: Байланыстырылған тізім дегеніміз не?
Байланыстырылған тізім – деректер элементтері бір-бірімен сілтемелер
арқылы байланысқан динамикалық құрылым. Бұл бағдарламалаудағы
ең маңызды деректер құрылымдарының бірі болып табылады.
Әр элементте екі негізгі компонент болады: өзінің деректері және келесі
элементке сілтеме (адрес). Мысалы, телефон кітапшасындағы әрбір
контакт келесі контактіге сілтеме ретінде қарастырылады деп
елестетіңіз.
Тізім элементтері жадта бір-біріне жалғасып орналаспайды, олар
сілтемелер арқылы байланысады.

3.

2-тарау: Байланыстырылған тізімнің түрлері
Бір жақты тізім
Екі жақты тізім
Шеңберлі тізім
Әр элемент тек келесіге сілтейді.
Әр элемент алдыңғы және келесі
Соңғы элемент біріншіге сілтейді,
Ең қарапайым және жиі
элементке сілтейді. Алға және
тізім шеңбер құрайды. Циклдік
қолданылатын түрі. Тек алға қарай
артқа қозғалуға мүмкіндік береді,
деректерді өңдеуге өте ыңғайлы.
қозғалуға мүмкіндік береді.
бірақ көбірек жады қажет етеді.

4.

Байланыстырылған тізімнің визуалды
схемасы
Түйіндер мен сілтемелер арқылы деректердің қалай байланысатынын көрсететін схема:
Түйін құрылымы
Сілтемелер жүйесі
Дерек бөлігі (Data)
Head – бірінші түйінге сілтеме
Сілтеме бөлігі (Next)
Next – келесі түйінге көрсеткіш
Әр түйін жеке адреске ие
NULL – тізімнің соңы

5.

3-тарау: Біріккен тізімнің құрылымы
01
02
03
Түйін (Node)
Тізімнің басы (Head)
Соңғы түйін
Негізгі құрылымдық бірлік. Дерек
Бірінші түйінге сілтеме. Бұл тізімге
Тізімнің соңғы түйінінің next көрсеткіші
және келесі түйінге сілтеме (next)
қолжетімділіктің бастапқы нүктесі
NULL мәніне тең (бір жақты тізімде).
сақтайды. Жадта динамикалық түрде
болып табылады. Head арқылы барлық
Бұл тізімнің аяқталғанын білдіреді.
құрылады.
операциялар басталады.
Маңызды: Head көрсеткішін жоғалтсаңыз, бүкіл тізімге қолжетімділікті жоғалтасыз!

6.

4-тарау: Тізімге элемент кірістіру әдістері
1
2
3
Бастапқы орынға
кірістіру
Соңына кірістіру
Ортаға кірістіру
Тізімді басынан аяғына дейін өтіп,
Қажетті позицияға дейін өтіп,
Жаңа түйін жасалады, оның next
соңғы түйінді табу керек. Соңғы
сілтемелерді қайта бағыттау
көрсеткіші ағымдағы head-ке
түйіннің next сілтемесі жаңа
қажет. Алдыңғы түйіннің next-і
бағытталады. Содан кейін head
түйінге бағытталады. Уақыт
жаңа түйінге, жаңа түйіннің next-і
жаңа түйінге ауыстырылады.
күрделілігі – O(n).
келесі түйінге бағытталады.
Уақыт күрделілігі – O(1).

7.

5-тарау: Тізімнен элемент жою тәсілдері
Бастапқы элементті жою
Head келесі түйінге ауыстырылады. Жойылатын түйіннің жадысы босатылады. Ең жылдам операция – O(1).
Ортадағы элементті жою
Алдыңғы түйіннің next сілтемесі жойылатын түйіннің келесі түйініне бағытталады. Жойылатын түйіннің
жадысы босатылады.
Соңғы элементті жою
Соңғыдан бір алдыңғы түйінді табу керек. Оның next көрсеткіші NULL болады. Соңғы түйіннің жадысы
босатылады.
Барлық жою операцияларында жадты дұрыс босату өте маңызды!

8.

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

9.

6-тарау: Тізімді қайта қарау және элементтерді іздеу
Басынан бастау
Келесіге өту
Head түйінінен бастап процесс басталады
Next сілтемесі арқылы алға жылжу
1
2
3
4
Әр түйінді тексеру
Табу немесе аяқтау
Іздеу критерийімен салыстыру жүргізіледі
Элемент табылды немесе NULL-ге жетілді
O(n)
O(1)
Іздеу күрделілігі
Бірінші элементке қолжетімділік
Мұндағы n – тізімдегі элементтер саны. Ең нашар жағдайда барлық
Head арқылы лезде қол жеткізуге болады
элементтерді қарау қажет.

10.

7-тарау: Байланыстырылған
тізімнің артықшылықтары мен
кемшіліктері
✓ Артықшылықтары
✗ Кемшіліктері
Динамикалық жады пайдалану –
өлшемі өзгеріп тұрады
Кездейсоқ қолжетімділік жоқ
(индекс бойынша)
Элементтерді оңай кірістіру және
Іздеу операциясы баяу – O(n)
жою
Қосымша жады сілтемелерге қажет
Жадыны тиімді пайдалану
Кері бағытта қозғалу қиын
Алдын-ала өлшемді білудің қажеті
Күрделірек іске асыру
жоқ
Кірістіру/жою операциялары
жылдам

11.

8-тарау: Жадпен жұмы с істеу негіздері
Динамикал ы қ бөлу
Сіл темел ер арқы л ы
байл аны с
Жады ны бос ат у
malloc() (C тілінде) немесе new
Түйіндер физикалық жадта кез
жадысын free() немесе delete
(C++ тілінде) операторлары
келген жерде орналаса алады.
арқылы босату міндетті. Жад ағып
арқылы жады бөлінеді.
Олар сілтемелер (көрсеткіштер)
кетуін болдырмау өте маңызды!
Әр түйін жадта бөлек орналасады.
Пайдаланылмайтын түйіндердің
арқылы логикалық тізбек
құрайды.
Ескерту: Жадты дұрыс басқару – бағдарламаның тұрақтылығының кепілі. Жад ағып кету жүйенің баяулауына
және апатқа әкелуі мүмкін.

12.

9-тарау: Тізімдерді біріктіру
(біріккен тізім)
Бірінші тізімді өту
Бірінші тізімнің соңғы түйінін табу үшін басынан аяғына дейін өту керек. Соңғы
түйіннің next көрсеткіші NULL болады.
Сілтемені байланыстыру
Бірінші тізімнің соңғы түйінінің next көрсеткішін екінші тізімнің head-іне бағыттау.
Осылайша екі тізім біріктіріледі.
Жаңа біріккен тізім
Нәтижесінде екі тізімнің барлық элементтері бір ғана тізімде біріктірілген.
Бірінші тізімнің head жаңа біріккен тізімнің басы болады.
Практикалық мысал: Екі студент тізімін (топ А және топ Б) біріктіріп, бір ұжымдық тізім
жасау. Немесе екі тапсырыс тізімін біріктіру.

13.

11-тарау: Тізімдермен жұмыс істеуде жиі
кездесетін қателіктер
Жадты дұрыс босатпау
Сілтемелерді дұрыс
жаңартпау
NULL көрсеткіштерді
өңдемеу
жиі кездесетін қате.
Кірістіру немесе жою кезінде
NULL көрсеткішті тексермей
Пайдаланылмайтын түйіндердің
сілтемелерді дұрыс өзгертпесе,
пайдалану бағдарламаның
жадысын босатпасаңыз, уақыт
тізімнің құрылымы бұзылады.
құлауына әкеледі (segmentation
өте келе жады толып кетуі
Түйіндер жоғалуы немесе
fault). Әрбір көрсеткішті
мүмкін. Әрбір malloc/new үшін
циклдік сілтемелер пайда болуы
пайдалану алдында NULL-ге
free/delete болуы керек.
мүмкін.
тексеру керек.
Жад ағып кету (memory leak) – ең
"Көрсеткіштермен жұмыс істеу – күшті құрал, бірақ мұқият болу керек. Қате бір сілтеме бүкіл тізімді бұза алады."

14.

Қорытынды: Байланыстырылған тізімдер – тиімді деректер құрылымы
100%
O(1)
∞
Динамикалық икемділік
Өлшемін еркін өзгерту мүмкіндігі
Кірістіру жылдамдығы
Басына қосу тез орындалады
Қолдану аясы
Көптеген алгоритмдерде қолданылады
Негізгі тұжырымдар
• Динамикалық жадыны тиімді пайдалану мен элементтерді икемді басқару
• Бағдарламалау мен алгоритмдер негізінде маңызды рөл атқарады
• Жадпен жұмыс істеу дағдыларын жетілдіру – кәсіби бағдарламашы үшін міндетті
• Дұрыс пайдалану тиімді және қуатты шешімдер береді