O’zbekiston respublikasi oliy va o’rta maxsus ta’lim vazirligi toshkent axborot texnologiyalari universiteti

2-amaliy mashg’ulot

Ro’yhat ko’rinishidagi ma’lumotlar tuzilmasi.Ommaviy xizmat ko’rsatish turlari. Navbat, stek, dek. Ular ustida amallar
Navbat. Navbat bu yarimstatik MT bo’lib, unda elementlar bir xil toifada va ketme-ketlikda joylashadi. Navbat tuzilmasining o’ziga xos xususiyati shundaki, unga elementlar bir tomondan kiritilib, boshqa tomondan chiqarib olinadi, yani FIFO – First Input First Output ko’rinishidagi tuzilma hisoblanadi.Navbatning faqat birinchi elementigagina murojaat qilish mumkin.Navbat bilan ishlash uchun queue.hkutubhonasi mavjud bo’lib, ushbu kursda undan foydalanmagan holda OXKT ni amalga oshirish talab etiladi. Navbat, stek, dekni dasturda statik yoki dinamik ko’rinishda, yani massiv yoki bog’lamli ro’yhat shaklida amalga oshirish mumkin. Keling, massiv shaklida ifodalashga misollar ko’rib chiqamiz.

Misol.Elementlari butun toifada bo’lgan navbatni elementlari o’rta qiymatini hisoblash dasturini tuzing.

#include

using namespace std;

int a[100],R=0;

int add(int s){

a[R]=s; R++;

}

int pop(){

int t=a[0];

for(int i=0;i

a[i]=a[i+1];

R--;

return t;

}

bool isEmpty(){

if(R==0) return true; else return false;

}

bool isFull(){

if(R>=100)return true;else return false;

}

int print(){

int i=0;

while(i

int k=pop();i++;

cout<

add(k);

}

}

int main(){

int n,s;

cout<<"n=";cin>>n;

for(int i=0;i

if(!isFull()){cin>>s;

add(s);}

else{cout<<"navbat to 'ldi"; n=i;break;}

}

cout<<"\nnavbat elementlari: ";

print();

int q=0;

while(!isEmpty()) q+=pop();

cout<<"\no'rta qiymat="<

}

Misol.Navbatdagi juft qiymatli elementlardan vektor hosil qiling.

#include

#include

using namespace std;

int a[100],R=0;

int add(int s){

a[R]=s; R++;

}

int pop(){

int t=a[0];

for(int i=0;i

a[i]=a[i+1];

R--;

return t;

}

bool isEmpty(){

if(R==0) return true; else return false;

}

bool isFull(){

if(R>=100)return true;else return false;

}

int print(){

int i=0;

while(i

int k=pop();i++;

cout<

add(k);

}

}

int main(){

vector v1;

int n,s;

cout<<"n=";cin>>n;

for(int i=0;i

if(!isFull()){cin>>s;

add(s);}

else{cout<<"navbat to 'ldi"; n=i;break;}

}

cout<<"\nnavbat elementlari: ";

print();

while(!isEmpty()){

int k=pop();

if(k%2==0) v1.push_back(k);

}

cout<<"\nvektor el-lari:";

for(int i=0;i

}

Stek.Stek bu LIFO, yani Last Input First Output ko’rinishidagi tuzilma bo’lib, u bir xil toifadagi elementlar ketma-ketligi hisoblanadi.Stek bir tomoni yopiq tuzilma bo’lib, shu sababli elementlar bitta tomondan kiritilib, chiqariladi.Stekni dasturda massiv shaklida ifodalashga misol ko’ramiz.

Misol.Stekning elementlari yug’indisini hisoblang.

#include

#include

using namespace std;

int a[100],R=0;

int add(int s){

a[R]=s; R++;

}

int pop(){

R--;

return a[R];

}

bool isEmpty(){

if(R==0) return true; else return false;

}

bool isFull(){

if(R>=100)return true;else return false;

}

int print(){

vector v1;

int p=R;

cout<<"\nstek el-lari:";

for(int i=0;i


int k=pop();

cout<

v1.push_back(k);

}

cout<

for(int i=v1.size()-1;i>=0;i--) add(v1[i]);

}

int main(){

int n,s,sum=0; cout<<"n=";cin>>n;

for(int i=0;i

if(!isFull()){ cin>>s;add(s);}

print();

for(int i=0;i

sum+=pop();

cout<

}

Dek. Dek bu – Double Ended queue, yani har ikkala tomondan ochiq tuzilma bo’lib, bir xil toifadagi elementlar ikkala tomondan kiritilishi va chiqarilishi mumkin. Dekni massiv shaklida amalga oshirishga misol ko’ramiz.

Misol.Dekka n ta elementni oldin chapdan, keyin o’ng tomondan kiritish dasturini tuzing.

#include

using namespace std;

int a[100],R=0;

int add_right(int s){

a[R]=s; R++;

}

int pop_right(){

R--;

return a[R];

}

int add_left(int s){

for(int i=R;i>0;i--)

a[i]=a[i-1];

a[0]=s;R++;

}

int pop_left(){

int t=a[0];

for(int i=0;i

a[i]=a[i+1];

R--;

return t;

}

bool isEmpty(){

if(R==0) return true; else return false;

}

bool isFull(){

if(R>=100)return true;else return false;

}

int print(){

cout<<"\ndek el-lari:";

for(int i=0;i

int k=pop_left();

cout<

add_right(k);

}

cout<

}

int main(){

int n,s,sum=0; cout<<"n=";cin>>n;

for(int i=0;i

if(!isFull()){

cin>>s;

if(i%2==0)add_left(s);

else add_right(s);

}

print();}
Topshiriqlar.

1. 
   10 elementli bir o’lchamli massiv berilgan. Ushbu massiv stek xususiyatiga ega bo’lib, unga 11-element kiritilganda stek to’lib ketganini ma’lum qiluvchi dasturni tuzing.
   
2. 
   Stekda 7 ta element mavjud. Mazkur stekni elementlardan bo’shatish dasturini tuzing.
   
3. 
   Elementlar kiritilib, navbat shakllantirilsin. Navbatning oxirgi elementga teng barcha elementlarni o’chiruvchi dastur tuzilsin.
   
4. 
   Elementlar kiritilib, navbat shakllantirilsin. Navbatning o’lchami 9 ga teng va eng katta elementga teng barcha elementlarini o’chiruvchi dastur tuzilsin.
   
5. 
   Dekda 12 ta element mavjud. Elementlarni teskari tartibda joylashtirish dasturni tuzing.
   
6. 
   Elementlar kiritilib, Dek shakllantirilsin. 20 ta elementdan iborat Dekni tashkil qiluvchi dasturni tuzing.
   

3-amaliy mashg’ulot

Dinamik turdagi ma’lumotlar tuzilmasi

Chiziqli bog’langan ro’yxatlarni e’lon qilish va

ular ustida bajariladigan amallarga doir masalalar yechish
Dinamik MT dastur bajarilishi mobaynida tuzilma uzunligi va elementlari orasidagi munosabat o’zgaruvchan bo’lgan tuzilmaga aytiladi. Dinamik MT elementlari xotirada ketma -ket yacheykalarga joylashishi shart emas.Xotirada qaerda bo’sh joy mavjud bo’lsa, o’sha erga joylashtiriladi.Elementlarni xotiradan o’qib olishda ularni ketma -ketligini buzmasdan topib olish uchun har bir elementga keyingi elementning xotiradagi adresini yozib qo’yish uchun ko’rsatkichli maydon kiritiladi.Ana shunda har bir elementga qarab keying elementni toppish mumkin bo’ladi.Oxirgi elementning ko’rsatkich maydoniga NULL yoziladi.Bunday tuzilmalarga bog’langan ro’yhatlar deyiladi.Agar har bir elementda bitta ko’rsatkichli maydon mavjud bo’lsa, bunday tuzilmaga bir bog’lamli ro’yhat deyiladi.Xotirada mavjud bo’lgan ro’yhatni topish uchun uning 1-elementi adresini bilish talab etiladi.Bu adresni yozib qo’yish uchun birorta o’zgaruvchi (Lst) e’lon qilamiz.

Misol. Bir bog’lamli ro’yhar tashkil qiluvchi va ustida turli amal bajaruvchi dastur tuzing.

#include

using namespace std;

class Node{

public: int number;

Node* next;

};

int main()

{ Node* head = NULL;

Node* lastPtr = NULL;

short action = -1;

while (1)

{ cout<<"1. element qo’shish\n";

cout<<"2. ro’yhatni ko’rish\n";

cout<<"3. ro’yhat elementini o'chirish\n";

cout<<"0. chiqish\n\n";

cout<<"tanlang: ";

cin>>action;

if (action == 0) {

system("CLS");

break;}

if (action == 1)

{ system("CLS");

Node* ptr = new Node;

int numb = -1;

cout<<"son kiriting: ";

cin>>numb;

ptr->number = numb;

ptr->next = NULL;

if (head == 0)

{ head = ptr;

lastPtr = ptr;

system("CLS");

continue;

}

lastPtr->next = ptr;

lastPtr = ptr;

system("CLS");

continue;

}

if (action == 2){

Node* ptr = NULL;

if (head == 0)

{ cout<<"\t!!! ro’yhat bo’sh !!!\n\n";

system("PAUSE");

system("CLS");

continue;

}

cout<<"* * * * * ro’yhat * * * * *\n\n";

ptr = head;

while (1) {

cout<
number<<" ";

if (ptr->next == 0) break;

ptr = ptr->next;

}

cout<<"\n\n";

system("PAUSE");

system("CLS");

continue;

}

if (action == 3)

{

system("CLS");

int d;

cout<<"o'chiriladigan elementni kiriting";

cin>>d;

Node* p = head,*q;

while(p){

if(d==p->number){

if(p==head){

Node *t=p->next;

head=t;

delete(p);break;

}

else if(p==lastPtr){

q->next=NULL;

delete(p);break;

}

else {

q->next=p->next;

delete(p);break;

}

}

q=p;

p=p->next;
}

system("CLS");

cout<<"element o'chirildi";

system("pause");

continue;

}

}}

Ro„yhatlar ustida quyidagi amallarni bajarish mumkin.

- ro„yhatni shakllantirish (birinchi elementini yaratish);

- ro„yhat oxiriga yangi element qo„shish;

- berilgan kalitga mos elementni o„qish;

- ro„yhatning ko„rsatilgan joyiga element qo„shish (berilgan kalitga mos elementdan oldin yoki keyin)

- berilgan kalitga mos elementni o„chirish;

- kalit bo„yicha ro„yhat elementlarini tartibga keltirish.

Ro„yhatlar bilan ishlashda dasturda boshlang„ich elementni ko„rsatuvchi ko„rsatkich talab etiladi. Chiziqli bir bog„lamli ro„yhatlar ustida turli amallar bajarish algoritmlari va dasturlarini ko„rib chiqamiz.