Руйхатхои пайваста
Хотира барои элементхои массив яклухт чудо карда мешавад, яъне хамаи элементхои массив дар як блоки бефосилаи хотираи фаври паси хамдигар, пайдарпай чойгир карда мешаванд. Бар акси чунин тарзи чойгиркунии маълумот дар хотираи фаври, тарзи дигари чойгиркунии маълумот мавчуд аст, ки онро руйхати пайваста (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. Кодеро тартиб дихед, ки пеш аз гирехи аввалаи руйхати пайваста гирехи навро пайваст мекунад.