“Ахборот технологиялари” факультети “Ахборот технологияларини дастурий таъминоти” кафедраси “маълумотлар тузилмаси ва алгоритмлар”

боғламли рўйхатлар дейилади. Агар охирги элемент биринчи элемент кўрсаткичи билан боғланган бўлса, 
бундай рўйхатга халқасимон рўйхат дейилади. Рўйхатнинг хар бир элементи шу элементни 
идентификациялаш учун калитга эга бўлади. Калит одатда бутун сон ёки сатр кўринишида маълумотлар 
майдонининг бир қисми сифатида мавжуд бўлади. Рўйхатлар устида қуйидаги амалларни бажариш мумкин. 
- 
рўйхатни шакллантириш (биринчи элементини яратиш); 
- 
рўйхат охирига янги элемент қўшиш; 
- 
берилган калитга мос элементни ўқиш; 
- 
рўйхатни кўрсатилган жойига элемент қўшиш (берилган калитга мос элементдан олдин ёки кейин) 
- 
берилган калитга мос элементни ўчириш; 
- 
калит бўйича рўйхат элементларини тартиблаш. 
Рўйхатлар билан ишлашда дастурда бошланғич элементни кўрсатувчи кўрсаткич талаб этилади. 
Чизиқли бир боғламли рўйхатлар устида турли амаллар бажариш алгоритмлари ва дастурларини кўриб 
чиқамиз. 
Чизиқли бир томонлама йўналган рўйхатлар 
Бир боғламли рўйхат деб элементларни шундай тартибланган кетма-кетлигига айтиладики, ҳар бир 
элемент 2 та майдонга: информацион майдон info ва кўрсаткич майдони ptr га эга бўлади.
Мазкур кўринишдаги рўйхат элементи кўрсаткичини ўзига хослиги шундан иборатки, у фақатгина 
рўйхатнинг навбатдаги (ўзидан кейин келувчи) элементи адресини кўрсатади. Бир томонлама йўналтирилган 
рўйхатда энг сўнги элемент кўрсаткичи бўш, яъни NULL бўлади.
Lst – рўйхат боши кўрсаткичи. У рўйхатни ягона бир бутун сифатида ифодалайди. Баъзан рўйхат бўш 
бўлиши ҳам мумкин, яъни рўйхатда битта ҳам элемент бўлмаслиги мумкин. Бу ҳолда lst = NULL бўлади. Хозир 
чизиқли бир боғламли рўйхат хосил қилиш дастурини кўриб чиқсак. Бунинг учун биз фойдаланувчи 
томонидан яратиладиган ностандарт тип яратиб олишимиз керак. Бунинг бир қанча усуллари мавжуд, яъни 
класслар ёки структуралар билан амалга ошириш мумкин. Масалан,
 
class Node 
{ 
public: // класс маълумотларига ташқаридан бўладиган мурожаатга рухсат бериш 
int info; // информацион майдон 
Node* next;// кўрсаткичли майдон 
}; 
Бу ерда биз Node номли тоифа яратдик ва рўйхатимиз бутун сонлардан иборат. Энди рўйхат 
элементларини шу тоифа орқали эълон қилсак бўлади, яъни 
Node *lst = NULL;// рўйхат боши кўрсаткичи 
Node *last = NULL;// рўйхатга охирги келиб тушган элементни кўрсаткич 
 
Энди шу белгилашлар орқали рўйхат хосил қиламиз. 
Node * p = new Node; 
int numb = -1; 
cout<<"son kiriting: "; 
 cin>>numb;
 p->info = numb; 
 p->next = NULL; 
if (lst == NULL) { 
lst = p; 
last = p; 
} 
else{ last->next = p; 
last = p; 
} 

---

18
Бу дастурда янги элемент рўйхат охиридан келиб қўшилади. 
Бир боғламли рўйхатлар устида операциялар. 
1. Бир боғламли рўйхат бошига элемент қўйиш. 
Берилган рўйхат бошига информацион майдони D ўзгарувчи бўлган элемент қўямиз. Ушбу ишни 
амалга ошириш учун қуйидаги ишларни бажариш лозим бўлади: 
а) р кўрсаткич мурожаат қиладиган, бўш элемент яратиш. 
b) Яратилган элемент информацион майдонига D ўзгарувчи қийматини ўзлаштириш. 
с) Янги элементни рўйхат билан боғлаш: Ptr(p)=lst (lst – энди рўйхат бошини кўрсатмайди) 
d) lst кўрсаткични рўйхат бошига кўчириш. 
Ва ниҳоят: 
Энди шу алгоритмни С++ тилидаги реализациясини кўриб чиқсак.
Node * p = new Node; 
int numb = -1; 
cout<<"son kiriting: "; 
cin>>numb; 
p->info = numb; 
if (lst ==NULL){ 
p->next = NULL; 
lst = p; 
} 
else { p->next = lst; 
lst = p; 
}