FREE := SPISOK[J].LINK; жаңа бос элементтің индексі SPISOK[J].INF
:= С; ақпаратты енгізу
SPISOK[J].LINK := SPISOK[1].LINK; көрсеткішті енгізу
SPISOK[1].LINK := J; алдыңғы элементтің көрсеткішін өзгерту
1-ші элементтен кейін тізімнен жою
J := SPISOK[1].LINK; жойылатын элемент индексін таптық
С := SPISOK[J].INF; ақпаратты көшірдік
SPISOK[1].LINK := SPISOK[J].LINK; көрсеткішті көшірдік
енді FREE-дің алдына қосамыз:
SPISOK[J].LINK := FREE; көрсеткішке бос элементтің индексін
енгіздік
FREE := J; бос элементтің нөмірін ауыстырдық
Операциялар тағы да циклді және керісінше ретте (айналы)
орындалады.
Бірақ та осы операциялардың орындалуына қойылатын қандай да бір
шектеулер бар:
1) элементті қосу кезінде тізімнің толып кетуіне тексеріс жасау;
2) тізімде соңғысынан кейін элементті алып тастауға тексеріс жасау
керек;
3) ең бірінші элементті қалай жоюға болады?
4) бірінші элементтің алдына элементті қалай қосуға болады?
5.3 Сақиналы байланысты тізімы
Бірбайланысты тізімде қалаулы элементіңізге қатынау үшін тізімді
басынан бастап қарап шығу керек. Бұл ыңғайсыз және көп уақыт алады.
Егер элементтерді тізіммен сақинаға тұйықтаса, яғни тізімнің соңғы
элементінің көрсеткішін бірінші элементке ауыстырса, онда тізімді көріп
шығуды кез келген элементтен бастап және барлық тізімді қарап шығуға
болады. Бұндай тізім сақиналы деп аталады.
Сур.13
5.4 Сызықты екібайланысты тізім
Көбінесе сызықты тізімді көріп шығуда элементтер тізбегінің кез
келген бағытында жүру қажет болады: тізімнің соңына да, басына да.
Бұндай мүмкіндікті екібайланысты тізбек қамтамасыз етеді. Бұндай
тізімнің әрбір элементі екі көрсеткішке ие:
1) тік – тізімнің келесі элементіне;
2) кері – тізімнің алдыңғы элементінеы.
Тізім басының көрсеткішінен басқа екібайланысты тізім құрылымына
тізім соңына да көрсеткіш қосу керек (яғн, соңғы элементке). Осылайша,
екібайланысты тізімнің құрылымы келесі түрде болады (мысалда).
Сур.14
Екібайланысты тізімнің сызықтығы екі көрсеткіштің біреуі тізімнің кез
келген элементіне элементтердің реттелуін береді, керісінше, рет басқа
көрсеткішпен орнатылатындығынан шығады.
Екібайланысты тізімнің басы мен соңы логикалық түрде эквивалентті,
себебі тізім элементіне қатынау тізімнің кез келген шегінен жүзеге
асырылады. Әрбір жолдың соңында нөлдік (бос) көрсеткіш тұруы керек.
Әрбір элементте екі көрсеткіштің болуы тізімді күрделендіре түседі
және жадының қосымша шығынына әкеледі, бірақ тізімге қолданылатын
операциялардың ыңғайлы орындалуын қамтамасыз етеді.
Екібайланысты тізімнің әрі қарай жетілдіргендігі сақиналы
екібайланысты тізімге әкеледі. Онда соңғы элементтің тік көрсеткіші бірінші
элементке сілтеледі, ал бірінші көрсеткіштің кері көрсеткіші – соңғы
элементке.
Сақиналы екібайланысты тізімде тізім соңының көрсеткіші керек емес.
Екібайланысты тізімге қосу
Екібайланысты тізімге қосудың ерекшелігі алдыңғы элементтермен
қоса соңғы элементті де модификациялауда.
I индексті элементтен кейін жаңа элементті қою керек болсын.
J := FREE; бос элемент индексі
SPISOK[J].INF := С; ақпаратты енгізу
FREE := SPISOK[J].LINK; жаңа бос элементтің индексі
К := SPISOK[I].LINK1; келесі элементтің индексі
SPfSOK[l].LINK1 := J; алдыңғы элементтің көрсеткішін өзгерту
SPISOK[J].LINK1 := К; ақпаратты енгізу
SPISOK[J].LINK2 := I; келесі элементтің көрсеткіші
SPISOK[K].LINK2:=J;
Динамикалық құрылымды статикалыққа модельдедік. Бірақ, сонда да
динамикалық құрылымдарды жасаған жақсы. Ал бұл үшін жадының
динамикалық бөлінуін қарастыру керек.
Ұсынылатын әдебиет
1. Костин А.В., Шаньгин В.Ф. Организация и обработка структур
данных в вычислительных системах. – М. Высш. шк., 1987.
2. Вирт Н. Алгоритмы и структуры данных.- М.: Мир, 1988.
3. Вирт Н. Алгоритмы+ структуры данных= программы.-М.: Мир, 1985.
4. Ленгстайм Й., Огенстайм М., Тененбаум А. Структуры данных для
персональных ЭВМ.- М.: Мир,1989.
5. Флорес И. Структуры и управление данными.- М.: Финансы и
статистика,1982.
6. Стоун Г. С., Сиворек Д. П. Введение в организацию ЭВМ и
структуры данных. – М.: Машиностроение, 1980.
7. Бауэр Ф. Л., Гооз Г. Информатика. Вводный курс. В двух частях.-
М.: Мир, 1990.
8. Яворский В. В., Богушевская А. А. Структуры данных и алгоритмы
их обработки.- Қарағанды: ҚарМТУ, 2004.- 150б.
СӨЖ-ге арналған бақылау жұмыстары
1. Сызықты динамикалық құрылымдар. Байланысты тізім.
2. Байланысты тізімді массив көмегімен құру.
3. Сызықты екібайланысты тізім.
4. Екібайланысты тізімнің жүзеге асуы.
5. Тізімге элемент қосу
6. Тізімнен элементті алып тастау
7. Тізімге бірінші элементті қосу
8. Тізімнен бірінші элементті алып тастау
9. Тізімдегі бірінші элементтің алдына элемент қосу
10. Тізімнен соңғы элементті алып тастау
6 БӨЛІМ ДИНАМИКАЛЫҚ ҚҰРЫЛЫМДАРДЫ КӨРСЕТКІШТЕР
КӨМЕГІМЕН КӨРСЕТУ
Дәріс жоспары
1 Көрсеткіштер
2 Стек көрсетілімі
3 Кезек көрсетілімі
4 Динамикалық тізімдерді көрсеткіштер көмегімен жүргізу
5 Сақиналы екібайланысты тізімді құру алгоритмі
6.1 Көрсеткіштер
Мәліметтердің тізімдік құрылымының (байланысты тізімдердің,
стектердің, кезектердің, т.б.) сипаттық ерекшелігі – бұл элементтер санын
өзгерту мүмкіндігі. Бұл сан алдын-ала анықталмаған және жадыда тізімнің
бос элементтерін сақтау бір уақытта болады.
Одан да жадының динамикалық бөлінуін қолданған жақсы, яғни
тізімдік құрылымның элементі үшін жадыны оның компиляциясы емес,
элемент бағдарламаны орындау кезінде пайда болған кезде бөлсе. Бұл
жағдайда транслятор элементтердің өзіне емес динамикалық орналасқан
элементтерге жадының белгілі бір көлемін бөледі. Бұл адрестер көрсеткіштер
немесе сілтемелер деп аталады.
Достарыңызбен бөлісу: |
