Сонымен қатар, бірнеше элементтерді қолдануда бір түйінге біріктіруге
болады, сонда оларға тек қана бір байланыс қажет болады. Жадыдағы
неғұрлым маңызды анық емес ұтыс кестенің жалпы бөліктерінің
үйлесімділігіне мүмкіндік беретін байланысты тізімдерді қолдану кезінде
пайда болады;
2) байланысты тізімнің ішіндегі элементті оңай алып тастауға болады.
Бұл үшін тек қана байланысты өзгерту керек (яғни, көрсеткіш мәнін);
3) байланысты тізімнің кез келген жеріне элемент қосуға болады.
Бұның бәрі тек байланыстың өзгеруіне ғана әкеледі. (тізбекті тізімдер үшін
тізімнің бір бөлігін көшіру керек);
4) байланысты тізімдегі k-ші элементке тек қана тізімнің басынан және
алдындағы элементтерді көріп шыққан кейін ғана қатынау мүмкін. (бұл –
олардың шашылып жатқаны үшін төлем);
5) екі байланысты тізбектерді біріктіру немесе бір тізімді бірнеше
бөліктерге бөлу оңай жүзеге асырылады;
6) байланысты тізбімдердің схемасы тізбекті тізімдерге қарағанда
күрделірек құрылымдарды бейнелеуге мүмкіндік береді.
Бірбайланысты тізімнің сызықтығы оның элементтерінің барлығы
логикалық түрде сызықты орналасқандығынан шығады, яғни әрбір элемент
үшін (біріншісі мен соңғысынан басқа) жалғыз алдыңғы және жалғыз одан
кейін жүретін элементтер бар.
Бірбайланысты тізімнің физикалық құрылымы – дескрипторлар мен
жадының кейбір облысында ерікті орналасқан және көрсеткіштер көмегімен
сызықты реттелген тізбек бойында бір-бірімен байланысқан өлшемі және
форматы бойынша бірдей жазбалар жиынтығы.
Жадыда бір тізбектің элементтерінің арасында басқа тізімдердің
элементтері де болуы мүмкін.
Бірбайланысты тізімнің дескрипторы ерекше жазба түрінде жүзеге
асырылуы мүмкін және мынадай ақпараттарға ие:
• тізімнің коды;
• тізімнің аты;
• тізбект басының адресі (көрсеткіш);
• тізімдегі элементтердің ағымдағы саны;
• элементтің бейнеленуі.
Дескриптор тізімнің элементтері орналасатын жадыда бола алады,
немесе оған жадыдан басқа орын бөлінеді.
5.2 Массив арқылы байланысты тізімнің жүзеге
асырылуы
Байланысты тізімдермен жұмысты неғұрлым ыңғайлы көрсету үшін
(оның негізгі этаптары: - көршілес элементтерге көшу; - элементті қосу; -
элементті алып тастау), байланысты тізімді оның қарапайым үлгісімен
көрсетейік, яғни қосымша өрісі - келесі жазбаға көрсеткіші бар жазбалар
(құрылымдар) массивімен көрінісі. (Ұқсас үлгіні тізбекті тізімдер үшін де
қарастыруға болады, бұны өзіміз де істей аламыз).
Берілген жағдайда көрсеткіш жазбалар массивіндегі келесі элементтің
индекс мәніне ие болады.
CONSTMS=100;
TYPE SP = RECORD
INF : T
0
; { T
0
- базалық тип; мыс., JNF:CHAR болсын; }
LINK: INTEGER
END;
VAR SPISOK : ARRAY[1..MS] OF SP;
NACH : INTEGER;
K, I, J : INTEGER;
С : CHAR;
Сур. 12
Тізім элементтерінің арасында 3-5-6-9-2 ретімен логикалық байланыс
орнатылған (көрсеткіштерді қараңыз).
Соңғы элементтің белгісі – көрсеткіш мәні 0-ге тең. Тізім басының
индексі nach айнымалысында болады. Массив элементтері 1, 4, 7, 8, 10, 11,
12 тізімге енгізілбеген.
Енді мынадай түрде берілген тізімге қолданылатын негізгі операциялар
қалай жүзеге асырылатынын қарастырайық.
Тізімнің келесі элементіне көшу
i – ағымдағы элементтің индексі болсын. Онда келесі элементтің
индексін аламыз:
J:=SPISOK[1].LINK;
С := SPISOK[1].INF; - 1-ші элементтің мәні
Алдындағы элементпен байланыстың жоғалғанына назар аударайық.
Барлық тізімді басынан бастап көріп шығу
I := NACH;
WHILE I <> О DO BEGIN
С := SPISOK[1].INF;
........ { С-ні өңдеу}
I := SPISOK[1].LINK;
END;
Тізімді басынан бастап немесе аралық элементтен көріп шығу
болады, бірақ тізімнің соңына қарай.
Керек элементті іздеу
I := NACH;
WHILE (С о '...') AND (I <> 0) DO BEGIN
С := SPISOK[1].INF;
I := SPISOK[1].LINK;
END;
IF С о '...' THEN { элемент табылған жоқ }
Тізімге қосу
j индексті массив элементін тізімге L элементінен кейін қосу керек
болсын
Мысалы, j = 11, i = 6. Онда
SPISOK[J].INF := С; ақпаратты енгізу
SPISOK[J].LINK := SPISOK[1].LINK; көрсеткішті SPISOK[1].LINK
:= J; алдындағы элементтің көрсеткішін ауыстыру. Қосу мен алып тастау
берілген нөмірі бар элементтен кейін жасалады.
Тізімнен элементті алып тастау
i индексті элеменеттен кейін тұрған элементті тізімнен алып тастау
керек болсын. Мысалы, i = 3 (осыдан, j = 5 бар элементті алып тастау керек).
Бұл үшін j элементінің көрсеткішін i элементінің көрсеткішіне ауыстыру
керек.
J := SPISOK[1].LINK; жойылатын элементтің индексін таптық
SPISOK[1].LINK := SPiSOK[J].LINK; көрсеткішті ауыстырдық
С := SPISOK[J].INF; ақпаратты сақтадық.
Тізімге элементтерді қосу мен алып тастаудың циклділігіне және
айналылығына назар аударайық.
Біз әзірше тізімге қосуға арналған бос элементтің индексі қалай
анықталатынын және тізімнің босатылған элементпен не істейтінімізді
қарастырған жоқпыз.
Босатылған элемент "қоқыс" болып табылады. Бұл жағдайдан шығу –
массивтің барлық бос элементтерін бір тізімге – бос кеңістік тізіміне
байланыстыру.
Енді негізгі тізімге қосу операциясының алдында бос кеңістік тізімінен
бір элементті алу керек (әдетте бірінші – стек белгісі).
Негізгі тізімнен жою операциясынан кейін босатылған элементті бос
кеңістік тізіміне қосу операциясын енгізу керек (бұл тізімнің басына - стек).
Бос кеңістіктің тізімі стек сияқты қолданылады. Енді соңғы екі
операция келесі түрде орындалады.
1-ші элементтен кейін тізімге қосу
J := FREE; бос элемент индексі
Достарыңызбен бөлісу: |
