Рӯйхатҳои пайваста

Печать

Хотира барои элементҳои массив яклухт ҷудо карда мешавад, яъне ҳамаи элементҳои массив дар як блоки бефосилаи хотираи фаврӣ паси ҳамдигар, пайдарпай ҷойгир карда мешаванд. Бар акси чунин тарзи ҷойгиркунии маълумот дар хотираи фаврӣ, тарзи дигари ҷойгиркунии маълумот мавҷуд аст, ки онро рӯйхати пайваста (linked list) меноманд. Дар рӯйхати пайваста барои ҳар як элементи он дар хотираи фаврӣ блоки алоҳидаю ҷудогонаи хотира банд карда мешавад. Элементи рӯйхати пайвастаро гиреҳ (node) низ меноманд. Дар рӯйхати пайваста барои байни ҳам пайваст кардани гиреҳҳо аз ишораҳо (pointers) истифода мебаранд.

Ҳар як гиреҳ аз ду қисм иборат аст: майдони додашудаҳо (data field) ва майдони минбаъд (next field). Дар майдони додашудаҳо маълумоти зарурӣ нигоҳ дошта мешавад. Дар майдони минбаъд ишоракунак ба гиреҳи навбати нигоҳ дошта мешавад. Барои ҳар як гиреҳ хотира ба воситаи оператори new ҷудо карда мешавад ва баъди гум шудани зарурият ба ин гиреҳ бояд, ки хотираи бандшуда ба воситаи оператори delete озод карда шавад.

Яъне барномасоз сохтор ё синферо муайян мекунад, ки он иборат аст аз тағйирёбандаҳои маълумоти заруриро нигоҳдоранда ва ишоракунак ба сохтор ё синфи муайян шудаистода.

Поездро ба хотир оред. Гиреҳи якуми рӯйхати пайваста ба локомотиви поезд монанд аст. Локомотив бо вагони аввал ва вагонҳо бо ҳам бо васлкунакҳои махсус пайваст шудаанд. Ишоракунакҳо ба васлкунакҳо монанданд. Ҳар вақте ки ба охири поезд вагони нав ҳамроҳ карда мешавад, аз васлкунак истифода мебаранд. Айнан ҳамин тавр, баъди бо оператори new ҷудо кардани хотира ба гиреҳи нав, ба ишоракунаки гиреҳи охирони рӯйхати пайваста суроғаи гиреҳи навбати бахшида мешавад. Ишоракунак ин мисли ақрабак ба ягон чиз дар хотира аст, на худи он чиз. Зарур аст, ки ба ишоракунаки гиреҳи охирони рӯйхати пайваста NULL бахшида шавад, бо мақсади пешгирӣ кардани ишора ба ҷои тасодуфии хотира. Вагарна дар рафти иҷроиш барнома шикаст хурданаш мумкин аст.

Барномаеро меорем, ки дар он сохтори рӯйхати пайваста ва гиреҳи аввали он муайян карда мешаванд:

//namuna40.cpp
using namespace std;
#include <iostream>
struct node {
int x;
node *next;
};
int main() {
node *first;
first=new node;
first->x=1;
first->next=NULL;
return 0;
}

Дар аввали ин мисол гиреҳи якум эълон карда шуда node *first, ба он ба воситаи first=new node дар хотираи фаврӣ ҷой чудо карда мешавад. Дар майдони додашудаҳои гиреҳи якум адади 1 сабт карда мешавад: first->x=1. Дар майдони минбаъди он ишоракунак ба NULL баробар карда шудааст: first->next=NULL. Ин мисол ҳамчун намунаи ибтидои кор бо рӯйхатҳои пайваста хизмат мекунад.

Боз поездро ба хотир оред. Тасаввур кунед, ки кондуктори поезд ба он фақат аз локомотив дохил шуда метавонаду халос. Барои ба вагони охирон расидан, кондуктор бояд ки ҳамаи вагонҳоро паси ҳам тай намояд. Айнан ҳамин хел, барои он ки барнома ба охири рӯйхати пайваста гиреҳи навро тавонад пайваст кунад, бояд ки аз гиреҳи якум (ё ки гиреҳи решагӣ) ба гиреҳи навбати гузарад, агар ишоракунак ба NULL баробар набошад. Аз ин гиреҳ ба гиреҳи дигар гузарад, агар ишоракунак ба NULL баробар набошад ва ҳоказо. Агар ишоракунак ба NULL баробар бошад, ин маънои ба гиреҳи охирон расидани барномаро дорад. Дар ҳамин ҳолат ба гиреҳи нав дар хотира ҷой ҷудо намуда, ба ишоракунаки гиреҳи охирони рӯйхат суроғаи гиреҳи навро мебахшанд. Дар гиреҳи нав ягон қимат сабт карда шуда, ишоракунаки гиреҳи нав ба NULL баробар карда мешавад:

//namuna41.cpp
using namespace std;
#include <iostream>
struct node {
int x;
node *next;
};
int main() {
node *first;
node *conductor;
first=new node;
first->x=1;
first->next=NULL;
conductor=first;
if(conductor!=NULL)
while(conductor->next!=NULL)
conductor=conductor->next;
conductor->next=new node;
conductor=conductor->next;
conductor->x=23;
conductor->next=NULL;
return 0;
}

Бо оператори if(conductor!=NULL) мавҷуд будани ақалан як гиреҳ (гиреҳи аввала) дар рӯйхати пайваста санҷида мешавад. Баъд ба воситаи сохтори идоракунандаи while гузариш то гиреҳи охирон таъмин карда мешавад. Гузариш аз як элемент ба элементи дигар ба воситаи оператори conductor=conductor->next иҷро карда мешавад. Баъд гиреҳи нав сохта шуда, он ба рӯйхат пайваст карда мешавад. Мисоли болоиро боз инкишоф медиҳем:

//namuna42.cpp
using namespace std;
#include <iostream>
struct node {
int x;
node *next;
};
int main() {
node *first;
node *conductor;
first=new node;
first->x=1;
first->next=NULL;
conductor=first;
if(conductor!=NULL)
while(conductor->next!=NULL)
conductor=conductor->next;
conductor->next=new node;
conductor=conductor->next;
conductor->x=23;
conductor->next=NULL;
int i;
for(i=0;i<3;i++) {
conductor->next=new node;
conductor=conductor->next;
if(conductor!=NULL) {
cout<<"Qimat baroi girehi nav: ";
cin>>conductor->x;
conductor->next=NULL;
}
}
conductor=first;
while(conductor->next!=NULL) {
cout<<conductor->x<<endl;
conductor=conductor->next;
}
cout<<conductor->x<<endl;
return 0;
}

Оператори хориҷкунии охирони cout<<conductor->x<<endl, баъди сикли while(conductor->next!=NULL) истода низ зарур аст, чунки сикл то гиреҳи охиронро дарёфтан кор мекунад ва маълумоти дар гиреҳи охирон буда, дар дохили сикл хориҷ карда намешавад.

Маслиҳат медиҳем, ки пеш аз хондани давоми ин дарс, матни namuna42.cpp-ро хубтар таҳлил карда бароед.

Барои ҳар як гиреҳ дар хотираи фаврӣ ҷои муайян ҷудо карда мешавад. Ҳангоми гум шудани зарурият дар гиреҳҳо, ҷои барои онҳо забтшударо озод кардан зарур аст. Ҳаҷми хотираи фаврӣ беинтиҳо нест! Нест кардани гиреҳҳоро масалан бо сикли зерин иҷро намудан мумкин аст:

while(first!=NULL) {
conductor=first;
first=first->next;
delete conductor;
}

САВОЛҲО БАРОИ МУСТАҲКАМКУНӢ
1. Кодеро тартиб диҳед, ки ягон гиреҳи мобайнии рӯйхати пайвастаро нест мекунад.
2. Кодеро тартиб диҳед, ки гиреҳи охирони рӯйхати пайвастаро нест мекунад.
3. Кодеро тартиб диҳед, ки байни ду гиреҳи мобайнии рӯйхати пайваста як гиреҳи навро пайваст мекунад.
4. Кодеро тартиб диҳед, ки пеш аз гиреҳи аввалаи рӯйхати пайваста гиреҳи навро пайваст мекунад.

Добавить комментарий


Защитный код
Обновить

Произведение «OFTOB.COM» публикуется на условиях лицензии Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Непортированная.