6.5 Сақиналы екібайланысты тізімді құру алгоритмі
Есеп. Жазбалардан тұратын файл берілген. Өрістердің біреуі – қандай
да бір белгі (кілт). Белгінің керек мәніне ие барлық жазбалардан мәліметтер
жинағындағы реті бойынша тізбекті динамикалық екібайланысты сақиналы
тізім құру керек. Динамикалық тізімдерден екі деректер жинағына (ДЖ)
мәліметтерді жазып алу: біреуі – тізім басынан соңына дейін – ДЖ1, басқасы
– керісінше тізбекте – ДЖ2.
Қадамды бөлшектеу принципін қолдана отырып, алгоритм құрып
көрейік. Басты кезеңдерді бөліп алайық.
Кезең 1. Белгінің талап ететін мәндеріне ие ДЖ1 жазбаларынан екілік
сақиналы динамикалық тізім құру керек.
Кезең 2. Тізімді басынан соңына қарап шығғу жолымен тізімнен
ақпаратты ДЖ2-ге шығару.
Кезең 3. Тізімді соңынан басына қарап шығу арқылы ақпаратты кері
тізімнен ДЖ2-ге шығару
1 кезеңді бөлшектейік.
Бірінші жалған элемент құру. Оған тізім басының көрсеткіші Ғ пен
тізім соңының көрсеткіші R-ді адрестеу. Жалған элементтің тік және кері
көрсеткіштерін бос қылу.
1.2. Бағдарламаға таңдау белігісінің мәнін енгізу.
1.3. Әзірше файлдың соңы емес:
1.3.1. Жазбаны оқу
1.3.2. Егер жазбада белгінің қажет мәні бар болса, онда 1.3.2.1.
Онда оны тік және кері тізімдерге қосу
1.4. Көрсеткіштердің қайтаадрестелу тізімінен жалған элементті алып
тастау.
1.5. Тік және кері тізімдерді сақинаға тұйықтау. 2, 3 кезеңдерді
бөлшектеу қажет емес.
Айнымалыларды бейнелеуді келтірейік.
TYPE ZAP = RECORD
……
PR: Т;
…….
END;
PTR=^SP;
SP = RECORD
INF:ZAP;
LI:PTR;
L2:PTR
END;
VARK,J,F,R:PTR;
REC:ZAP;
FZ1, FZ2, FZ3 : FILE OF ZAP;
N : INTEGER; тізім элементтерінің санауышы
PZ:T;
1.1 - 1.5. б. бөлшектейміз
1.1. NEW(K);
K^.LI :=NIL; K^.L2 -NIL;
F:=K;R:=K;
1.2. READLN(PZ);
1.3. WHILE NOT EOF(fzl) DO BEGIN
1.3.1 READ(FZ1,REC);
1.3.2 IF REC.PR = PZ THEN BEGIN
1.3.2.1 J:=K;NEW(K);
K^.INF:=REC;
K^.L1:=NIL;
K^.L2 := J;
J^.Ll:=K;
R:=K;
N :=N + 1
END;
1.4. K:=F;
F:=F^.L1;
F^ .L2= nil;
DISPOSE(K);
1.5 R^.Ll:=F;
F^.L2 := R;
Енді бағдарлама:
PROGRAM SOSTSPIS;
{бейнелеу бөлімі}
BEGIN
WRITELN (' екілік сақиналы тізімді құру және шығару
бағдарламасы');
{ 1.1 - жалған элементті құру }
WRITE (' таңдау белгісін енгізу');
{ 1.2 – белгінің мәнін енгізу }
ASSIGN (FZl,’NDl’); ASSIGN (FZ2,'ND2
’
); ASSIGN
(FZ3,’ND3');
RESET (FZ1); REWRITE (FZ2); REWRITE (FZ3);
N:=0;
{1.3 – тізім құру}
IF n>0 THEN BEGIN
{ 1.4 – жалған элементті жою}
{ 1.5 – тік және кері сақинаны тұйықтау }
{2 – тізімді басынан соңына дейін қарап шығу }
{ 3 – тізімді соңынан аяғына дейін қарап шығу }
END ELSE
WRITELN (' тізім бос');
CLOSE(FZ1); CLOSE(FZ2); CLOSE(FZ3);
END.
Ұсынылатын әдебиет
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. Тізімде анықталған негізгі операциялар.
11. Тізімді құрудың бағдарламалық жүзеге асуы.
12. Тізім соңына элемент қосудың бағдарламалық жүзеге асуы.
13. Тізімнен элементті жоюдың бағдарламалық жүзеге асуы.
14. Тізімді қарап шығу.
15. Екі байланысы бар тізімдер.
16. Сақиналы екібайланысты тізімді құрудың алгоритмі.
7 БӨЛІМ МӘЛІМЕТТЕРДІҢ АҒАШТӘРІЗДІ ҚҰРЫЛЫМДАРЫ
Дәріс жоспары
1 Негізгі түсініктер мен анықтамалар
2 ЭЕМ-де ағаштардың көрсетілімі
3 Бинарлы ағаштарға қоланылатын неігізгі операциялар
4 Қатты тармақталатын ағаштар
7.1 Негізгі түсініктер мен анықтамалар
Әртүрлі есептерде мәліметтер өзара сызықты тізбек (көлденеңінен)
құра байланысып қоймай, сонымен қатар иерархиялық (тік, яғни, әртүрлі
джеңгейлерде болады) түрде де байланысады. Арғы ата-ұрпақ типті қатынас
иерархиялық болып табылады, онда аға-қарындас – бір деңгейде сияқты.
Немесе мынадай иерархия:
Ағаш деп келесі қасиеттерге ие құрылым аталады:
1) ешқандай басқа элемент сілтелмейтін жалғыз элемент бар. Бұл
элемент түбір деп аталады.
2) әрбір элемент иерархияның келесі деңгейінің бірнеше
элементтерімен байланысты. Бұл элементтер өз кезегінде ағаштар бола алады
(ішкі ағаштар). 3) аралық деңгейдің әрбір элементі неғұрлым жоғары
деңгейдің тек қана бір элементімен пайда болған.
Ағаштың басқа элементтерге сілтелмейтін элементтері терминалды
(яғни, шекті) немесе жапырақтар деп аталады. Ал
терминалды
емес
элементтер ішкі түйіндер деп аталады.
Осылайша, ағаш мәліметтердің иерархиялық реттелген құрылымын
бейнелейді, онда алдыңғы деңгейдің (жоғарғы) элементтерінің арасындағы
байланыс байқалады немесе келесі деңгейдің элементтерімен және арғы
аталарымен – ұрпақтарымен.
Әрбір түйіні бірден көп емес "ішкі ағашқа" ие болатын тізімді ағаш
деуге болады. Сондықтан тізім солай "пайда болған ағаш" деп аталады.
Ағаш тәрізді құрылымның бірнеше бейнелеу тәсілдері бар. Мсыалы,
базалық тип Т әріптер жиыны болсын. Осындай типте қандай да бір
мақсатпен құрылған ағаштәрізді құрылымды бейнелеуге болады, мысалы:
а) қабатталған жиындармен (сур.17);
Сур. 17
Достарыңызбен бөлісу: |
