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


#Misol. 4 Navbat sinfi: bog'langan ro'yxatdan foydalanish
#include
using namespace std;

class Queue

{
public:
Queue();
~Queue();
void push(int);
int pop();
void print();
private:
typedef struct Node {
Node *next;
int data;
} NODE;
NODE* head;
};

Queue::Queue()

{
head = NULL;
}

Queue::~Queue()

{
if(head == NULL) return;
NODE *cur = head;
while(cur) {
Node *ptr = cur;
cur = cur->next;
delete ptr;
}
}

void Queue::push(int n)

{
if(head == NULL) {
head = new NODE;
head->data = n;
head->next = NULL;
return;
}
NODE *cur = head;
while(cur) {
if(cur->next == NULL) {
NODE *ptr = new NODE;
ptr->data = n;
ptr->next = NULL;
cur->next = ptr;
return;
}
cur = cur->next;
}
}

void Queue::print()

{
if(head==NULL) return;
Node *cur = head;
while(cur) {
cout << cur->data << " ";
cur = cur->next;
}
cout << endl;
}

int Queue::pop()

{
if(head == NULL) {
cout << " bo'sh estack!" << endl;
return NULL;
}
NODE *tmp = head;
int value = head->data;
if(head->next) {
head = head->next;
}
//oxirgi elementni ochamiz (head)
else {
delete tmp;
head = NULL;
}
cout << "pop: " << value << endl;;
return value;
}

int main()

{
Queue *que = new Queue();
que->push(10);
que->push(20);
que->push(30);
que->push(40);
que->push(50);
que->print();
que->pop();que->print();
que->pop();que->print();
que->pop();que->print();
que->pop();que->print();
que->pop();que->print();
que->pop();que->print();
return 0;
}
Natija:
10 20 30 40 50
pop: 10
20 30 40 50
pop: 20
30 40 50
pop: 30
40 50
pop: 40
50
pop: 50