Mavzu: Halqasimon bo’glangan ro’yxatlar Reja

Halqasimon bir bog‘lamli ro‘yxatga element qo‘shish



void Add(int x)
{
Node *p=new Node; //yangi element uchun xotiradan joy ajratish
p->Next=Head;
p->info=x;
if (Head!=NULL) {
Tail->Next=p;
Tail=p;
}
else {
Head=Tail=p;
}
Halqasimon bir bog‘lamli ro‘yxat boshidan element o‘chirish algoritmi
Quyidagi rasmda ro‘yxat boshidagi elementni o‘chirish amali ko‘rsatilgan



void Del(){
Node *p=Head; //o‘chiriladigan elementni belgilab olish
Head=Head->Next; //ro‘yxat boshini keyingi elementga ko‘chirish
Tail->Next=Head; //oxirgi element ko‘rsatkichini 2-elementga ko‘chirish
delete p ; //ro‘yxat boshidagi elementni o‘chirish
}


Halqasimon bir bog‘lamli ro‘yxat ni ekranga chiqarish


void Show()
{
Node *p=Head;
while (p!=Tail)
{
cout<
info<<" ";
p=p->Next;
}
cout<
info<
}
Misol
Misol - halqasimon (tashqaridan) bog'langan ro'yxatni aniqlash
/ * Ushbu kod quyidagilarga ega * /
/ *
1. Node larni qo'shish
2. Ro'yxat hajmini qaytaradigan funktsiya
3. Ro'yxatni dumaloq qilib tuzish (tsikl)
4. Halqasimon ro'yxatni aniqlash
5. Rekursiv bosib chiqarish
* /
#include
using namespace std;

struct Node

{
int data;
Node * next;
};

Node *root = 0;

void addNode(int n)

{
if(root==0) {
root = new Node;
root->data = n;
root->next = 0;
return;
}
Node *cur = root;
while(cur) {
if(cur->next == 0) {
Node *ptr = new Node;
ptr -> data = n;
ptr -> next = 0;
cur -> next = ptr;
return;
}
cur = cur->next;
}
}

void makeCircular()

{
if(!root || !root->next) return;
Node *cur = root;
while(cur) {
if(cur->next == 0) {
cur->next = root;
return;
}
cur = cur->next;
}
}

int sizeOfList()

{
Node *cur = root;
int size = 0;
while(cur) {
size++;
if(cur->next == 0) {
return size;
}
cur = cur->next;
}
return size;
}

bool detectCircular()

{
// Ro'yxat halqasimon bo'lmasligi mumkin deb taxmin qilamiz

if(!root || !root->next) return false;

Node *ptr1 = root;
Node *ptr2 = root;

while(ptr1 && ptr2) {

ptr1 = ptr1->next;
ptr2 = ptr2->next;
if(ptr2) {
ptr2 = ptr2->next;
if(!ptr2) return false;
}
else {
return false;
}
cout << ptr1->data << "," << ptr2->data << endl;
if(ptr1==ptr2) {
return true;
}
}
return false;
}

void printRecursive(Node *ptr)

{
if(!ptr) {
cout << endl;
return;
}
cout << ptr->data << " ";
printRecursive(ptr->next);
}

int main(int argc, char **argv)

{
addNode(10);addNode(20);addNode(30);addNode(40);addNode(50);
addNode(60);addNode(70);addNode(80);addNode(90);addNode(100);

printRecursive(root);

cout << "size of list = " << sizeOfList() << endl;

makeCircular();

if(detectCircular()) cout <<"Circular\n";

else cout << "Normal\n";

}



Foydalanilgan adabiotlar

1. 
   Майкл Томас, Пратик Пател, Алан Хадсон, Доналд Болл(мл.) Секреты программирования для Internet на Java.- Ventana Press, Ventana Communications Group, U. S.A.,1996, Издательство "Питер Пресс", 1997
   
2. 
   Волш Основы программирования на Java для World Wide Web.- IDG Books Worldwide, Inc.,1996, Издательство "Диалектика",1996