15-Laboratoriya mashg’uloti Bog'langan ro'yxat. Ikkala bog'langan ro'yxat bilan ishlash

15-Laboratoriya mashg’uloti

Bog'langan ro'yxat. Ikkala bog'langan ro'yxat bilan ishlash

Bog'langan ro'yxatlar

Bog'langan ro'yxat - bu ma'lumotlar bazasining asosiy tuzilishi, bu erda har bir element biz keyingi elementga olishimiz kerak bo'lgan ma'lumotlarni o'z ichiga oladi.

Bog'langan ro'yxatlarning massivlarga nisbatan asosiy ustunligi shundaki, havolalar bizga buyumni samarali ravishda qayta tuzish imkoniyatini beradi. Ushbu moslashuvchanlik ro'yxatdagi har qanday o'zboshimchalik bilan tezkor kirish hisobiga erishiladi, chunki ro'yxatdagi elementga kirishning yagona usuli bu havolalarni boshidanoq kuzatib borishdir.

Quyidagi misollar bog'langan ro'yxat uchun. Har bir misol ichida bizda bir nechta operatsiyalar mavjud:

Halqasimon (sikli) bog'langan ro'yxatni aniqlash (# 1)

Ikki bog'langan ro'yxatni taqqoslash (# 2)

Ikki ro'yxatning kesishishini va birlashishini topish (# 3)

2 ta alohida bog'langan ro'yxat berilgan. Berilgan ikkita bog'langan ro'yxatni birlashtirish uchun funktsiyani hosil qilamiz ketma-ket o’sish tartibda (# 5)

Berilgan ikkita bog'langan ro'yxatdan har bir Node da kattaroq element bilan yangi bog'langan ro'yxat yaratish Bir xil o'lchamdagi ikkita bog'langan ro'yxatni hisobga olgan holda, ushbu bog'langan ro'yxatlar yordamida yangi bog'langan ro'yxatni yaratish vazifasi qo'yilgan. Shart shundaki, ikkala bog'langan ro'yxat orasidagi kattaroq elementlar yangi ro'yxatiga qo'shiladi. (# 6)

#1Misol

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";

}

Natija:

10 20 30 40 50 60 70 80 90 100

ro'yxat hajmi = 10

20,30

30,50

40,70

50,90

60,10

70,30

80,50

90,70

100,90

10,10

Halqasimon
#2Misol

#include

using namespace std;

struct Node {

int data;

Node* next;

};

// faqat 1-node uchun

void initNode(struct Node *head,int n){

head->data = n;

head->next =NULL;

}

// yuborish

void addNode(struct Node *head, int n) {

Node *newNode = new Node;

newNode->data = n;

newNode->next = NULL;

Node *cur = head;

while(cur) {

if(cur->next == NULL) {

cur->next = newNode;

return;

}

cur = cur->next;

}

}
void insertFront(struct Node **head, int n) {

Node *newNode = new Node;

newNode->data = n;

newNode->next = *head;

*head = newNode;

}

struct Node *searchNode(struct Node *head, int n) {

Node *cur = head;

while(cur) {

if(cur->data == n) return cur;

cur = cur->next;

}

cout << " Node yo’q " << n << " in list.\n";

}

bool deleteNode(struct Node **head, Node *ptrDel) {

Node *cur = *head;

if(ptrDel == *head) {

*head = cur->next;

delete ptrDel;

return true;

}

while(cur) {

if(cur->next == ptrDel) {

cur->next = ptrDel->next;

delete ptrDel;

return true;

}

cur = cur->next;

}

return false;

}

/* reverse the list */

struct Node* reverse(struct Node** head)

{

Node *parent = *head;

Node *me = parent->next;

Node *child = me->next;

/* make parent as tail */

parent->next = NULL;

while(child) {

me->next = parent;

parent = me;

me = child;

child = child->next;

}

me->next = parent;

*head = me;

return *head;

}

/ * Bog'langan ro'yxatning nusxasini yaratish * /

void copyLinkedList(struct Node *node, struct Node **pNew)

{

if(node != NULL) {

*pNew = new Node;

(*pNew)->data = node->data;

(*pNew)->next = NULL;

copyLinkedList(node->next, &((*pNew)->next));

}

}
/ * Ikki bog'langan ro'yxatni solishtiring * /

/ * qaytish qiymati: bir xil (1), boshqacha (0) * /

int compareLinkedList(struct Node *node1, struct Node *node2)

{

static int flag;

/* both lists are NULL */

if(node1 == NULL && node2 == NULL) {

flag = 1;

}

else {

if(node1 == NULL || node2 == NULL)

flag = 0;

else if(node1->data != node2->data)

flag = 0;

else

compareLinkedList(node1->next, node2->next);

}
return flag;

}
void deleteLinkedList(struct Node **node)

{

struct Node *tmpNode;

while(*node) {

tmpNode = *node;

*node = tmpNode->next;

delete tmpNode;

}

}
void display(struct Node *head) {

Node *list = head;

while(list) {

cout << list->data << " ";

list = list->next;

}

cout << endl;

cout << endl;

}
int main()

{

struct Node *newHead;

struct Node *head = new Node;

initNode(head,10);

display(head);
addNode(head,20);

display(head);

addNode(head,30);

display(head);

addNode(head,35);

display(head);

addNode(head,40);

display(head);

insertFront(&head;,5);

display(head);

int numDel = 5;

Node *ptrDelete = searchNode(head,numDel);

if(deleteNode(&head;,ptrDelete))

cout << "Node "<< numDel << " deleted!\n";

display(head);
cout << " Ro'yxat teskari \n";

reverse(&head;);

display(head);
cout << " Ro'yxat ko'chirildi \n";

copyLinkedList(head,&newHead;);

display(newHead);
cout << " Ikki ro'yxatni taqqoslash ...\n";

cout << " Ikkala ro'yxat bir xilmi?\n";

if(compareLinkedList(head,newHead))

cout << " Ha, ular bir xil!\n";

else

cout << " Yo'q, bular emas!\n";

cout << endl;
numDel = 35;

ptrDelete = searchNode(newHead,numDel);

if(deleteNode(&newHead;,ptrDelete)) {

cout << "Node "<< numDel << " deleted!\n";

cout << " O'chirishdan keyin yangi ro'yxat \n";

display(newHead);

}

cout << " Ikki ro'yxatni yana taqqoslash ...\n";

cout << " Ikkala ro'yxat bir xilmi?\n";

if(compareLinkedList(head,newHead))

cout << " Ha, ular bir xil!\n";

else

cout << " Yo'q, bular emas!\n";

cout << endl;

cout << " Nusxalangan ro'yxat o'chirilish \ n ";

deleteLinkedList(&newHead;);

display(newHead);

return 0;

}

Natija:

10

10 20

10 20 30

10 20 30 35

10 20 30 35 40

5 10 20 30 35 40

5 tugun o'chirildi!

10 20 30 35 40

Ro'yxat teskari

40 35 30 20 10

Ro'yxat ko'chirildi

40 35 30 20 10

Ikki ro'yxatni taqqoslash ...

Ikkala ro'yxat bir xilmi?

Ha, ular bir xil!

35 tugun o'chirildi!

O'chirishdan keyin yangi ro'yxat

40 30 20 10

Ikki ro'yxatni yana taqqoslash ...

Ikkala ro'yxat bir xilmi?

Yo'q, ular boshqacha!

Nusxalangan ro'yxat o'chirilmoqda

#Misol.3 Navbat tuzilishi: bog'langan ro'yxatdan foydalanish

#include

#include
struct node

{

int data;

node *next;

};

typedef struct node node_t;

node_t *head = NULL;
void push(int n)

{

node_t *newNode = (node_t *)malloc(sizeof(node_t));

newNode->data = n;

newNode->next = NULL;

if(head == NULL) {

head = newNode;

return;

}
node_t *cur = head;

while(cur) {

if(cur->next==NULL) {

cur->next = newNode;

return;

}

cur = cur->next;

}

}
void pop()

{

if(head==NULL) return;

node_t *tmp = head;

head = head->next;

free(tmp);

}
void display()

{

node_t *cur = head;

while(cur) {

printf("%3d",cur->data);

cur = cur->next;

}

printf("\n");

}
int main()

{

push(1);push(2);push(3);push(4);push(5);display();

pop();display();

pop();display();

pop();display();

pop();display();

pop();display();

return 0;

}

Natija:

1 2 3 4 5

2 3 4 5

3 4 5

4 5

5