Бұл тізбектерге біреуіне оңай біріктіріледі, содан кейін сқрыптау
аяқталады. Мысал екі файлдың серияларын тарату енетін серияға қарағанда
шығыстық серияның аз санын бере алатынын көрсетеді. Бұл (i+2)-ші
серияның бірінші элементі і-ші серияның соңғы элементінен көп болғанда
болады, бұл екі серияны автоматты түрде біреуге біріктіруге әкеледі.
Сондықтан А және В-дағы шығыстық сериялардың нақты сандары қатты
ажыратылуы мүмкін. Бірақ біздің процедура сериялар жұбын біріктіріп,
сосын файлдардың біреуі басқаның қалдығын жоғалта отырып оқылған кезде
аяқталып отырады.
17 19' 13 57' 23 29' 11 59' 31 37' 7 61' 41 43' 5 67' 47 71' 2 3
13 17 19 23 29 31 37 41 43 47 57 71' 11 59
11 13 17 19 23 29 31 37 41 43 47 57 59 71
Осылайша бастапқы мәліметтер екі кезең ішінде сұрыпталады. Түзету
әдістерінің бірі – тарату операциясын лентадағы сериялар саны бірдей
болатындай етіп түзету.
Екіншісі – бірдей қылып бөлуден бас тартып, ал біріктіру
процедурасын файлдардың біреуінің соңына жеткен кезде бір серия ғана
емес, басқаның қалдығы түгел көшірілетіндей етіп өзгерту.
Біріктірудің екінші жағдайында:
PROCEDURE MERGE;
BEGIN
WHILE NOT EOF (A) AND NOT EOF (B) DO BEGIN
MERGERUN; L := L + 1;
END;
WHILE NOT EOF (A) DO
BEGIN COPYRUN (A, C); L := L + 1;
END;
WHILE NOT EOF (B) DO
BEGIN COPYRUN (B, C); L := L + 1;
END;
END;
Енді процедураларды біріктіріп, шақыратын бағдарлама жазу. Баспаға
қосу.
Ұсынылатын әдебиет
2. Вирт Н. Алгоритмы и структуры данных.- М.: Мир, 1988.
3. Вирт Н. Алгоритмы+ структуры данных= программы.-М.: Мир, 1985.
4. Ленгстайм Й., Огенстайм М., Тененбаум А. Структуры данных для
персональных ЭВМ.- М.: Мир,1989.
5. Флорес И. Структуры и управление данными.- М.: Финансы и
статистика,1982.
6. Стоун Г. С., Сиворек Д. П. Введение в организацию ЭВМ и
структуры данных. – М.: Машиностроение, 1980.
8. Яворский В. В., Богушевская А. А. Структуры данных и алгоритмы
их обработки.- Караганда: КарГТУ, 2004.- 150с.
СӨЖ-ге арналған бақылау жұмыстары
1.
Тізбекті файлдармен жұмыс кезіндегі негізгі операциялар.
2.
ОЕҚ-дағы
және
файлдағы
сұрыптаудың
негізгі
айырмашылығы.
3.
Тізбекті файлдарды сұрыптау.
4.
Тізбекті файлдарды қарапайым біріктіру әдісімен сұрыптау.
5.
Мәліметтерді өңдеу фазасы деген не?
6.
Бірктіру арқылы сұрыптаудың ауқымдылығы.
7.
Тізбекті файлдарды табиғи біріктіру әдісімен сұрыптау.
8.
Балансталған біріктірудің балансталмаған біріктіруден
айырмашылығы.
4 БӨЛІМ ЖАРТЫЛАЙСТАТИКАЛЫҚ ҚҰРЫЛЫМДАР
Дәріс жоспары
1 Стек, кезек және дек жартылайстатикалық құрылым
ретінде
2 Массив көмегімен жартылайстатикалық құрылымды
көрсету
Алдында қарастырылған оперативті құрылымдар (массивтер, жазбалар,
кестелер, жиындар) келесі қасиеттермен сипатталады:
- ол бар болған барлық уақыт ішіндегі құрылымның тұрақтылығы;
- элементтердің сыбайластығы және құрылымның барлық элементіне
бөлінген жады облысының үздіксіздігі;
- құрылым элементтерінің арасындағы қатынастардың тұрақтылығы
пен қарапайымдылығы, бұлар құрылым элементтеріне бөлінген жады
облысынан осы қатынастар туралы ақпаратты алып тастайды және оны
дескрипторларда кішігірім формада сақтайды.
Сондықтан атап өтілген құрылымдарды статикалық құрылымдар деп
атаймыз.
Енді осы қасиеттердің кейбіреуі немесе барлығы орындалмайтын
құрылымдарды қарастырайық.
Бізге енді тізімнің немесе тізімдік құрылымның жалпы түсінігі қажет
болады.
Сызықты тізбек деп х(1), х(2), ..., х(n) мәліметтер элементтерінің
реттелген тізбегін айтады, мұндағы n > 0. Әрбір элементте өрістер бірдей
саны бар.
Сызықтық тізімнің құрылымдық қасиеттері тек элементтердің
сызықты (бірөлшемді) қатысты орнымен шектеледі. Егер п > 0, онда х(1) -
бірінші элемент. Егер 1 < k < n, онда x(k) элементінің алдында x(k-l) элементі
болады, ал х(к)-тен кейін x(k+l) жүреді. X(n) – соңғы элемент.
Тізім элементтерінің реттелгендігі олардың логикалық құрылымдағы
және ЭЕМ жадысындағы тізбекті орнымен анық емес берілуі мүмкін. Бұл
тізбекті тізім.
Реттелгендікті берудің басқа тізімі – бұл элементтерде орналасқан
және әрбір элементке оның алдындағысы мен кейінгісін анықтауға мүмкіндік
беретін арнайы байланыстар мен көрсеткіштерді қолдану. Бұндай тізімдер
байланысты (байланысқан) деп аталады. (Оларды кейінірек қарастырамыз).
Егер п = const, онда сызықты тізім массивке, тізімге немесе жазбаға
ұмтылады.
Егер
п
өзгеруін
жіберсек,
онда
тұрақтылық
қасиетін
қанағаттандырмайтын мәліметтер құрылымын аламыз. Бұндай құрылымдар
жартылайстатикалық деп аталады.
Жартылайстатикалық құрылымдар арасындағы неғұрлым бізге
белгілілері стектер, кезектер, дектер. Бірақ, бұның не екенін анықтамас
бұрын, сызықты тізімнің элементтеріне қандай операциялар қолдануға
болатынын анықтайық.
Бұндай операцияларға мыналар жатады:
1) k нөмірлі элементке қатынау;
2) k нөмірлі элементтің алдына жаңа элемент қосу;
3) k нөмірлі элементті жою;
4) біріктіру арқылы екі тізімді біреуге тізбекті біріктіру;
5) тізімді екіге немесе одан көпке бөлу;
6) тізімнен өрістің берілген мәні бар элементті табу.
Неғұрлым қарапайым операциялар k = 1 немесе k = п болғанда
алынады.
Көбінесе элементтерді қосу, алу және мәндерге қатынау тек қана
бірінші немесе соңғы элементке жасалатын сызықты тізімдер кездеседі.
Стектер, кезектер және дектер дегеніміз осылар.
Стек (stack) – сызықты тізбекті тізім, бұнда элементтерді қосу, алу
және қатынау тек қана бір соңынан орындалады: k =- п, яғни тек қана соңғы
элементке қатынауға болады. Стек элементтеріне қызмет көрсету пәні мына
аббревиатурамен өрнектеледі
LIFO (Last - In - First - Out) -
"соңғы келдің – бірінші кеттің"
Стектің мысалы ретінде бұрандалы патрон магазин бола алады.
(осыдан стектің екінші атауы – магазин, сонымен қатар вагондарды ұрыптау
теміржол разъезді).
Сур. 5
Достарыңызбен бөлісу: |
