Bog'langan ro'yxatlar

29. Dinamik struktura xarakteristikalari. Bog‘langan ro‘yxat. Kalit so’zlar: ma’lumotlar strukturasi, dinamit tuzilma, ro’yhat.

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

30. A massiv berilgan undagi juft va toq nomerli ustunlarning joyini almashtirish blok sxemasi va dasturini tuzing.

#include
using namespace std;

int array_size;

int *str = new int[array_size];

int n = 1;

void sort(int *num, int size)

{

int b, i;

for (i = 0; i < (size & ~1); i += 2)

{

b = num[i];

num[i] = num[i + 1];

num[i + 1] = b;

}

}
void print_array(int* arr, int size)

{

for (int i = 0; i < size; i++) {

std::cout << str[i] << " ";

}

std::cout << std::endl;

}
int main()

{

int array_size;

cin>>array_size;

for (int i = 0; i < array_size; i++)

{

str[i] = n;

n++;

}

print_array(str, array_size);

sort(str, array_size);

print_array(str, array_size);

delete[] str;

return 0;

}