t: integer;
Стекке элемент қосу үшін көрсеткіштің мәнін бірге үлкейту керек,
сосын массив элементіне у-тен t индексі бар ақпаратты енгізу керек:
t:=t+l;
stack[t] := у;
Стектен элементті жою
у := stack[t];
t:=1;
Бұнда t 1-ден кіші және MS-тен үлкен бола алмайтынын ескеру керек.
Осыдан, стектің бос болуына және толып кетуіне бақылау жасау керек.
If t=0 then { }
else begin у := stack[t]; t := t - 1 end;
if t=ms then { }
else begin t := t + 1; stack[t] := у end;
Кезек көрсетілімі
Сонымен қатар, кезек массив ретінде көрсетіле алады, бірақ оған тағы
екі көрсеткіш керек болады: f – кезектің басы үшін және г – соңы үшін.
Бейнелеуі :
const mq = 100;
var queue : array [ 1 ..mq] of tt;
var f, r: integer;
Кезекке элементті қосу стектегідей жасалады:
queue[r] := у; r := r + 1;
Бұнда r тек қана өсе алады. Кезектен элементті жою тура осылай
болады:
у := queue[f]; f := f+ 1;
Кезектің ағымдағы ұзындығы r – f-ға тең.
Сырғып кетпеу үшін кезекті сақинаға тұйықтайды. Сақиналық кезекте
queue[mq]-дан кейін логикалық түрде queue[1] жүреді. Бірақ бұнда егер r=f
болса, онда кезек не толып кеткен, не бос. Бірмәнділікті болдырмау үшін
соңғы элементті толтырмайды және бұл жағдай толып кету деп есептеледі.
Сақиналық кезекке элемент қосу:
if r=mq then r:= 1
else r := г + 1;
if r=f then { }
else queue[r] := y;
Сақиналық кезектен элементті жою:
if r = f then { }
else begin у := queue[r];
if f = mq then f:=l else f:=f+ 1;
end;
Кезектегі элементтер санын анықтау:
If r
else k := г – f
Ұсынылатын әдебиет:
1 Стек, очередь и дек как Полустатические структуры
2 Представление полустатических структур с помощью массивов
2. Вирт Н. Алгоритмы и структуры данных.- М.: Мир, 1988.
3. Вирт Н. Алгоритмы+ структуры данных= программы.-М.: Мир, 1985.
4. Ленгстайм Й., Огенстайм М., Тененбаум А. Структуры данных для
персональных ЭВМ.- М.: Мир,1989.
5. Флорес И. Структуры и управление данными.- М.: Финансы и
статистика,1982.
6. Стоун Г. С., Сиворек Д. П. Введение в организацию ЭВМ и
структуры данных. – М.: Машиностроение, 1980.
8. Яворский В. В., Богушевская А. А. Структуры данных и алгоритмы
их обработки.- Караганда: КарГТУ, 2004.- 150с.
СӨЖ-ге арналған бақылау жұмыстары
1.
Жартылай статикалық құрылымдар. Тізім ұғымы.
2.
Стек мәліметтер құрылымы ретінде.
3.
Кезек және дек мәліметтер құрылымы ретінде.
4.
Массив көмегімен жартылай статикалық құрылымдарды
көрсету.
5.
Стек мәліметтердің логикалық құрылымы ретінде.
6.
Кезек және дек логикалық құрылымдары ретінде.
7.
Тізім көмегімен жартылай статикалық құрылымдарды
көрсету.
8.
Стек мәліметтердің физикалық құрылымы ретінде.
9.
Кезек және дек мәліметтердің физикалық құрылымдары
ретінде.
5 БӨЛІМ СЫЗЫҚТЫ ДИНАМИКАЛЫҚ ҚҰРЫЛЫМДАР
Дәріс жоспары
1 Динамикалық құрылымдардың негізгі қасиеттері
2 Массив арқылы байланысты тізімнің жүзеге асырылуы
3 Сақиналы байланысты тізім
4 Сызықты екібайланысты тізім
5.1 Динамикалық құрылымдардың негізгі қасиеттері
Статикалық құрылым мен жартылайстатикалықтан айырмашылығы
динамикалық құрылымдар келесі қасиеттерге ие:
• тұрақсыздығы және оның өңдеу кезіндегі (элемент санының)
күтілмеген
өлшемі. Динамикалық құрылымның өлшемі 0-ден бастап қандай
да бір міндеттің спецификасымен немесе машинаның қатынай алатын
жадысының көлемімен анықталатын мәнге дейін өзгере алады.
• жадыдағы құрылымның элементтерінің физикалық сыбайлылығының
болмауы. Элементтердің логикалық тізбегі элементтердің өзінде сақталатын
бір немесе бірнеше көрсеткіштердің (байланыстардың) көмегімен нақты
түрде беріледі.
Екінші қасиетпен байланысты, динамикалық құрылымды алатын жады
үздіксіз облысты көрсетпейді. Динамикалық құрылымның элементтері ретсіз
түрде
шашылып
тасталған.
Бұның
салдары
статикалық
және
жартылайстатикалықпен
салыстырғанда
динамикалық
құрылымның
элементтеріне қатынаудың қиындай түсуі. Басқа жағынан, бұндай схема
иілмелі және көбінесе жадыдағы жеңісті қамтамасыз етеді.
Динамикалық құырылымдар әдетте алдында айтылған байланысты
тізімдер ретінде көрсетіледі. Сондықтан оларды көбінесе тізімдік
құрылымдар деп атайды. Бұндай тізімде әрбір элемент тізімнің келесі
элементінің адресі немесе нөмірі көрсетілетін қосымша өріспен қамтамасыз
етіледі
Сур.11
Байланысты тізім – элементтері ретінде элементтердің өзінде
сақталатын көрсеткіш көмегімен бір-бірімен логикалық байланысқан бірдей
форматты жазбалар болатын құрылым.
Қарапайым байланысты тізімдер – бірбайланысты (бір көрсеткіш),
екібайланысты (екі).
Негізінде көрсеткіштер бұдан да көп болуы мүмкін.
Бірбайланысты тізімде әрбір элемент екі өрістен тұрады: мазмұнды
және көрсеткіш өрісі.
Мазмұнды өрісте мәліметтер сақталады (жалпы жағдайда бұл жазба).
Көрсеткіш өрісі тізімнің келесі элементінің адресін сақтайды.
Көрсеткіш бойынша келесі элементке қатынау мүмкіндігін аламыз, ал одан
кезекті элементке және т.с.с. Соңғы элементтің көрсеткіш өрісінде нөлдік
немесе тізімнің соңын дәлелдейтін бос көрсеткіштің арнайы белгісі болуы
керек (біздің мысалда 0). Сонымен қатар, тізім басының көрсеткіші болу
керек. Ол оның логикалық құрылымының көрсеткіші болуы керек.
ЭЕМ жадысында ақпаратты сақтаудың екі қарастырылған
формаларын салыстыра отырып, мынаны ескеруге болады:
1) байланысты тізімдер байланыстарды сақтау үшін қосымша жадыны
талап етеді. Кейбір кезде бұл маңызды. Бірақ та көбінесе элементте байланыс
өрісіне арналған бос орын бар болады, егер барлық слотты тұтастай алмаса.
Достарыңызбен бөлісу: |
