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

t1.fio=”Abdullayev Abdulla”;

Yozuvlar ustida turli amallarni bajarish mumkin.

• 
  Maydonlariga qiymat o’zlashtirish
  
• 
  Solishtirish
  
• 
  Maydonlarining toifasidan kelib chiqqan xolda maydonlar ustida amal bajarish mumkin.
  

Quyida ba’zi bir misollarni keltiramiz, unda myCar nomli yozuivning maydonlariga qiymatla o’zlashtiriladi:

struct Car

{

    int x_coor;

    int y_coor;

    string name;

};

Car myCar;

 

myCar.x_coor = 40;

myCar.y_coor = 40;

myCar.name = "Porche";

Yozuvlar bilan ishlashga doir to’lkiq dastur matnini keltiramiz:

#include

using namespace std;

 

struct PlayerInfo {

    int skill_level;

    string name;

};

using namespace std;

 

int main() {

  PlayerInfo players[5];

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

        cout << "Please enter the name for player : " << i << '\n';

        cin >> players[ i ].name;

        cout << "Please enter the skill level for " << players[ i ].name << '\n';

        cin >> players[ i ].skill_level;

    }

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

        cout << players[ i ].name << " is at skill level " << players[i].skill_level << '\n';

    }

}
Ko’pincha funksiyalar bilan ishlaganda strukturalarni funksiyalarning argument sifatida uzatishga to’g’ri keladi yoki strukturalarni funksiyada qaytarishga extiyoj tug’iladi. Bunday hollarda quyidagicha yondashish mumkin.

struct EnemySpaceShip {     int x_coordinate;     int y_coordinate;     int weapon_power; }; EnemySpaceShip getNewEnemy()

{

    EnemySpaceShip ship;

    ship.x_coordinate = 0;

    ship.y_coordinate = 0;

    ship.weapon_power = 20;

    return ship;

}

Bu yerda funksiya ship nomli local yozuv nusxasini yaratadi va maydonlarga qiymatlar beriladi. Endi yangi o’zgaruvchini xosil qilish uchun quyidagini keltirish mumkin:

EnemySpaceShip ship = getNewEnemy();

Bu o’zgaruvchini funksiyaga uzatish mumkin:

EnemySpaceShip upgradeWeapons (EnemySpaceShip ship)

{

    ship.weapon_power += 10;

    return ship;

}

O’zgaruvchi maydonlariga o’zgartirish kiritilgach, uni albatta funksiyada qaytarish kerak, aks holda u qilingan o’zgarish yo’qolishi mumkin.

Quyida shu misolni to’liq dastur matnini keltiramiz;

struct EnemySpaceShip {

    int x_coordinate;

    int y_coordinate;

    int weapon_power;

};

 

EnemySpaceShip getNewEnemy() {

    EnemySpaceShip ship;

    ship.x_coordinate = 0;

    ship.y_coordinate = 0;

    ship.weapon_power = 20;

    return ship;

}

 

EnemySpaceShip upgradeWeapons(EnemySpaceShip ship) {

    ship.weapon_power += 10;

    return ship;

}

 

int main() {

    EnemySpaceShip enemy = getNewEnemy();

    enemy = upgradeWeapons(enemy);

}

Bundan tashqari strukturalarga ko’rsatkichlar xam yaratish mumkin:

#include

 

using namespace std;

 

struct xampl {

    int x;

};

 

int main()

{

    xampl structure;

    xampl *ptr;

 

    structure.x = 12;

    ptr = &structure;

    cout<< ptr->x;

    cin.get();

}
Jadvallar

Jadval - bu yozuvlarning chekli to’plamidir. Jadval ham statik tuzilma bo’lib, uning elementlari bir xil toifaga ega. Jadval yozuvlar massividan tashkil topadigan tuzilma hisoblanadi.

Uni yuqoridagi misoldan foydalanib dasturda quyidagicha idodalaymiz:

EnemySpaceShip name[20];

Bu yerda name nomli 20 ta elementdan iborat massiv yaratildi va uning elementlari EnemySpaceShip struktura ko’rinishida bo’ladi. Xar bir elementning

int x_coordinate;

     int y_coordinate;

     int weapon_power;

kabi maydonlari mavjud. Jadvalni bironta qatoriga murojaat massiv elementiga mos indeksi orqali va undan keyin aynan kerakli maydoniga (.) nuqta bilan murojaat amalga oshiriladi.

	int x_coordinate	int y_coordinate	int weapon_power
Name[0]	Name[o]. x_coordinate=35	Name[o]. y_coordinate=15	Name[o].weapon_power =12
Name[1]	Name[1]. x_coordinate=45	Name[1]. y_coordinate=42	Name[1].weapon_power =3
…

Misol. Funksiyalar bilan ishlashda jadvallarni kirish argument sifatida ishlatishga to’g’ri keladi. Quyida ana shunday holatga misol keltiramiz.

#include

using namespace std;

 

struct Size

{

int breast;

int waist;  

int hips;  

};

 

struct WonderfulWoman

{

char name[64];

int age;

int height;

int weight;

Size volume;  

bool engKnowledge;

};

 

void showData(const WonderfulWoman Obj[], int amount);

 

int main(){

const int amountOfGirl = 7;

WonderfulWoman Woman[amountOfGirl] = {};

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

cin.getline(Woman[i].name, 32);

cin >> Woman[i].age;

cin >> Woman[i].height;

cin >> Woman[i].weight;

cout << "english(1 - yes, 0 - no): ";

cin >> Woman[i].engKnowledge;

cin >> Woman[i].volume.breast;

cin >> Woman[i].volume.waist;

cin >> Woman[i].volume.hips;

cin.get();

cout << endl;

}

  showData(Woman, amountOfGirl);

  return 0;

}

 

void showData(const WonderfulWoman Obj[], int amount){

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

cout << i + 1 << '\t' << Obj[i].name << '\t' << Obj[i].age<< '\t' << Obj[i].height << '\t' << Obj[i].weight << '\t'<< Obj[i].volume.breast << '/' << Obj[i].volume.waist << '/' << Obj[i].volume.hips<< '\t' << Obj[i].engKnowledge << endl;

}

}
Bu yerda bitta strukturaning ichidagi maydon o’z navbatida boshqa strukturaga tegishli o’zgaruvchi olingan. Bunday yozuvlarga murakkab yozuvlar deyiladi, ya’ni yozuvning elementlarini o’zi ham yozuv hisoblanadi. Bu holatda murakkab ierarxik MT vujudga keladi.

Jadval ustida massiv ustida bajariladigan amallar o’rinli, lekin jadval elementiga emas, elementi maydoniga qiymat beriladi.

• 
  Element kiritish, o’chirish
  
• 
  Element maydoni qiymatlarini o’zgartirish
  
• 
  Jadval elementlarini solishtirish, bunda 2 ta yozuvning mos maydonlari qiymatlari solishtiriladi.
  

Nazorat savollar.

1. Qanday tuzilmalar statik tuzilma hisoblanadi?

2. Massiv nima?

3. Yozuv nima va uning xususiyatlari?

4. Murakkab yozuv nima?

5. Jadval nima va uning dasturda ifodalanishi qanday?

Asosiy internet manbalar

1. 
   SKYLINE UNIVERSITY COLLEGE.
   

http://www.teach-ict.com/as_as_computing/ocr/H447/F453/3_3_5/data_structures/miniweb/pg3.htm

2. 
   Osnovы programmirovaniye na S++ dlya nachinayuщix http://purecodecpp.com/archives/category/strukturi_c. 2015 yil.
   

Tavsiya etiladigan internet manbalar:

1. 
   http://cppstudio.com/post/5377/
   
2. 
   http://easy-code.ru/lesson/structures-in-cpp
   
3. 
   http://www.cprogramming.com/tutorial/lesson7.html
   

3-ma’ruza.

Yarimstatik ma’lumotlar tuzilamasi. Navbat, stek va dek.
Reja.

1. 
   Yarimstatik ma’lumotlar tuzilmalari.
   
2. 
   Stek tuzilmasi va uni dasturda amalga oshirish, ustida amal bajarish
   
3. 
   Navbat tuzilmasi va dasturda ifodalanishi, ustida amal bajarilishi
   
4. 
   Deklar. Ustida amal bajarish
   

Kalit so’zlar: navbat, stek, dek, yarimstatik tuzilmalar.
Yarimstatik ma’lumotlar tuzilmalari

Yarimstatik ma’lumotlar tuzilmalari deb nomlangan shunaqa tuzilmalar borki, ular ba’zi bir xususiyatlari bilan statik tuzilmalarga, ba’zi bir xususiyatlari bilan dinamik tuzilmalarga o’xshagan bo’ladi. Ya’ni dastur bajarilishi mobaynida tuzilma uzunligining o’zgaruvchanligi dinamiklik xususiyati bo’lsa, elementlari xotirada ketma-ket joylashishi statik tuzilmalarga o’xshash bo’ladi. Yarimstatik ma’lumotlar tuzilmasi bir xil toifadagi elementlar ketma-ketligi hisoblanadi va unga

• 
  Steklar
  
• 
  Navbatlar
  
• 
  Deklar
  

kiradi. Deyarli barcha zamonaviy dasturlash tillarida yuqorida keltirilgan tuzilmalat bilan ishlash uchun kutubxonalar mavjud. Va ular konteyner ko’rinishida realizatsiya qilingan. Shuni aytib o’tish kerakki, bu yarimstatik tuzilmalarni dasturda statik tuzilma ko’rinishida xam va dinamik tuzilma ko’rinishida xam ifodalash mumkin, faqat yarimstatiklik shartlarini buzmagan holda, ya’ni bu tuzilmalarning barchasida ixtiyoriy elementlarga tashqaridan murojaat qilib bo’lmaydi.

Steklar

Stek - chiziqli ma’lumotlar tuzilmasi bo’lib, ma’lumotlarni kiritish va chiqarish uning bir tomonidan amalga oshiriladi. Bunday stek kafeteriyadagi tarelkalar to’plamini eslatadi. Yangi elementlar stekning uchiga qo’yiladi va yuqori qismidan olinadi. Oxirgi qo’yilgan element stek uchidan birinchi bo’lib olinadi. Shu sababli, stek LIFO (last in first out) tuzilishidagi ma’lumotlar tuzilmasi bo’ladi, ya’ni, “oxirgi kelgan birinchi ketadi” prinsipi bo’yicha ishlaydi.

Stek o’lchami cheklangan bo’lsa, elementni stekka qo’yilishi stekda kamida bitta elementga joy bo’lgan holdagina amalga oshiriladi. Shuning uchun stek ustida amal bajarishdan oldin stek holatini tekshirish lozim bo’ladi,ya’ni

• 
  Stekka element kiritilishidan oldin joy borligini tekshirish;
  
• 
  Stekdan elementni o’chirishdan oldin element borligini tekshirish.
  

Steklar bilan ishlash uchun C++ tilida tayyor kutubxona mavjud bo’lib, unga dastur boshida #include deb murojaat qilish kerak. Dasturda stek e’lon qilish uchun quyidagicha yozish kerak.

Stack <toifa> stek_nomi;

Misol uchun,

Stack stek1;

Stekda quyidagi amallar o’rinli:

• 
  Clear() - Stekni tozalash.
  
• 
  isEmpty() – Stekni bo’shlikka tekshirish
  
• 
  push(el) - stekka element kiritish.
  
• 
  pop() – Stekdan element o’chirish.
  
• 
  topEl() - stekni uchidagi elementni o’chirmasdan o’qib olish.
  

Ulardan foydalanish esa quyidagicha:

stek1.push(x) – x ni stekka tashlash;

Stekka element qo’shish va chiqarish amallari quyidagi 4.1 – rasmda ko’rsatib berilgan.

4
.1 – rasm. Stekda bajarilgan amallar ketma – ketligi.

Unda bo’sh stekka 10 soni kiritilgan. Keyin stekka 5 soni kiritilgan, bu son 10 ni ustiga joylashadi, undan keyin chiqarish amali bajarilganda, stekdan 5 soni o’chiriladi. Chunki u 10 sonining yuqorisida joylashgan edi va 5 soni stekdan chiqariladi. Stekka 15 va 7 soni ketma - ket qo’yilgandan so’ng, eng yuqorida 7 soni bo’ladi. Natijada chiqarish operatsiyasi amalga oshirilganda 7 soni stekni tark etadi. Chiqarish amalidan keyin stekda 10 soni 15 ning ostida qoladi.

Umuman olganda, stek ma’lumotlar saqlashda va ma’lumotlar to’plamidan elementlar teskari tartibda chiqarib olinadigan holatlarda ko’p foydalaniladi.

Stekning qo’llanilishlariga misol qilib dasturda ajratkichlarni moslashtirishni olish mumkin. Bu juda ham muhim masala. Chunki, ajratkichlar ixtiyoriy kompilyatorning qismi hisoblanadi. Agar ajratkichlar bir– biriga moslashtirilmagan bo’lsa, hech bir dastur to’g’ri ishlamaydi.

C++ dasturlash tilida biz quyidagi ajratkichlarga egamiz: oddiy qavslar “(“va”)”, kvadrat qavslar “[“va”]”, figurali qavslar “[“va”]”, va izoh ajratkichlar “/*” va “*/”. Quyida C++ dasturlash tilida ajratkichlar to’g’ri qo’llanilganligiga misol keltirilgan.

a = b + (c - d) * (e - f);

g[10] = h[i[9]] + (j + k) * l;

while (m < (n[8] + o)) { p = 7; /* initialize p */ r = 6; }

Quyidagi misol moslashtirilmagan ajratkichlarga misol bo’la oladi:

a = b + (c - d) * (e - f));

g[10] = h[i[9]] + j + k) * l;
while (m < (n[8) + o]) { p = 7; /* initialize p */ r = 6; }

Konkret ajratgich o’z juftligidan boshqa ajratgichlar bilan ajratilishi mumkin, ya’ni ajratkichlar ichma – ich qo’yilgan bo’lishi mumkin. Shunday qilib, ajratkich o’z juftligi bilan moslashganmi yoki yo’qligini, barcha ajratkichlar juftliklari aniqlangandan keyin bilish mumkin.

Masalan, sikldan foydalanilganda boshlang’ich qavs o’z juftligiga ega ekanligini barcha ichki qavslar juftliklari yopilgandan keyin aniqlash mumkin.

while (m < (n[8] + o))

Ajratkichlarni qiyoslash algoritmi quyidagicha:

• 
  belgilar C++ dastur matnidan o’qiladi va u ochuvchi ajratkich bo’lsa, ular stekka tashlanadi. Agar yopuvchi ajratkich bo’lsa, u ochuvchi ajrakich bilan solishtiriladi va stekdan chiqariladi.
  
• 
  Agar ular mos tushsa, qayta ishlash davom etadi, mos tushmasa qayta ishlash hatolik haqidagi habar bilan to’htatiladi.
  

Dastur ohiriga yetganda C++ dasturini qayta ishlash muvoffaqiyatli tugatilgan hisoblanadi va stek bo’sh bo’ladi. Ushbu algoritmni quyida psevdokodini keltiramiz.

Ajratkichlarning moslashuvini tekshirish kodi.

read character ch from file;
while not end of file
if ch is ‘(’, ‘[’, or ‘{’
push(ch);
else if ch is ‘)’, ‘]’, or ‘}’
if ch and popped off delimiter do not match
failure;
else if ch is ‘/’
read the next character;
if this character is ‘*’
skip all characters until “*/” is found and report an error
if the end of file is reached before “*/” is encountered;
else ch = the character read in;
continue; // go to the beginning of the loop;
// else ignore other characters;
read next character ch from file;
if stack is empty
success;
else failure;

4.2 rasmda yuqoridagi algoritmni quyidagi ifodani qayta ishlashga qo’llanganda hosil bo’lgan qayta ishlash ko’rsatilgan

s=t[5]+u/(v*(w+y));

4.2 rasmdagi birinchi ustunda sikl ohiridan keyingi belgigacha bo’lgan stek tarkibi ko’rsatilgan. Birinchi qator fayldagi va stekdagi boshlang’ich holatni ko’rsatilgan. Ch o’zgaruvchi s yozuv faylining birinchi simvoliga initsializatsiya qilinadi, siklning birinchi iteratsiyasida simvol qabul qilinmaydi. Bu holat 4.2 rasmning ikkichi qatorida ko’rsatilgan. Undan keyin tenglik belgisi o’qiladi. U ham qabul qilinmaydi, chunki u ajratkich emas. Birinchi ajratkich (kvadrat qavs ) 5-qadamda o’qiladi va stekka birinchi element bo’lib joylashadi. Ifodaning barcha elementlari o’qib chiqilgandan so’ng ajratkichlar birin – ketin stekka joylanadi, va bu jarayon oxirgi nuqta vergulgacha davom etadi.

.

4.2-rasm. Ajratkkichlar moslashtirish algoritmi yordamida s=t[5]+u/(v*(w+y)); ifodani tekshirish

Stekni qo’llanilishiga boshqa misol qilib, juda katta sonlarni qo’shish masalasini ko’rish mumkin. Bunday sonlar butun toifadagi o’zgaruvchilar uchun mumkin bo’lgan chegaralardan chiqib ketadi. Shuning uchun ularni qo’shish to’g’risida gap ham bo’lishi mumkin emas. Masalan, 18,274,364,583,929,273,748,459,595,684,373 va 8,129,498,165,026,350,236 sonlari berilgan. Ularni qo’shish muammosini sonlarni raqamlar qatori sifatida tasvirlab, raqami bo’yicha ikkita stekka ketma – ket joylab qo’shish mumkin bo’ladi. Bunda raqam sifatida sonlarni tartib xonalari (birlar , o’nlar, yuzlar…) olinadi. Bu algoritmning psevdokodi quyidagicha:

addingLargeNumbers()

birinchi sonning raqamlari o’qiladi va songa mos stekka joylanadi.

ikkinchi sonning raqamlari o’qiladi va songa mos stekka joylanadi.

carry = 0;

stek bo’sh bo’lmaguncha while siklidan foydalaniladi.

Har bir bo’sh bo’lmagan stekdan son chiqarib olinadi va u carry ga qo’shiladi.

Natijaviy stekka birlik qismi kiritiladi.

Carry ni o’rniga carry saqlanadi.

Agar carry nolga teng bo’lmasa natijaviy stekka joylanadi.

Natijaviy stekdan sonlar chiqariladi va ekranga yoziladi.

4.3 rasmda yuqoridagi algoritmni 592 va 3,784 sonlarni qo’shishni amalga oshirish uchun qo’llanilishi ko’rsatilgan.

1. 
   Birinchi sonning mos raqamlari 1 – stekka joylanadi va
   

ikkinchi sonning mos raqamlari 2 – stekka joylanadi. Stekdagi raqamlar tartibiga e’tibor qaratish kerak.

592 va 3,784 sonlarni qo’shishda stekning ishlatilishiga misol.

2. 
   2 va 4 lar steklardan chiqariladi va ularning yigindisi 6 natijaviy stekka kiritiladi.
   

3. 9 va 8 lar ham steklardan chiqariladi va ularning yig’indisini birlik qismi natijaviy stekka joylanadi, o’nlik qismi esa keyingi natijaga qo’shish uchun carry da saqlab qo’yiladi.

4. 5 va 7 lar ham steklardan chiqariladi va ularning yig’indisini birlik qismi natijaviy stekka joylanadi, o’nlik qismi esa keyingi natijaga qo’shish uchun carry da saqlab qo’yiladi.

5. birinchi stek bo’sh bo’lgan holda , bo’sh bo’lmagan stekdan son chiqariladi va carry ga qo’shiladi, natija natijaviy stekka joylanadi.

6. ikkala stek bo’sh bo’lsa, sonlar yig’indisi natijaviy stekdan olinadi va natija sifatida ekranga chiqariladi.

Endi ma’lumotlar tuzilmasida abstract stekni amalga oshirishni ko’ramiz. Stekni amalga oshirishni yaqqol ko’rinishi dinamik massiv, ya’ni vektorda bajarilishi mumkin.



4.4 rasm. Stekning vektorda amalga oshirilishi




4.5 rasm. Stekning bog’langan ro’yxatda amalga oshirilishi


4.6 rasm. abstract stek (a), stekni vektorda amalga oshirilishi (b) va stekni bog’langan ro’yxatda amalga oshirilishi(c) uchun amallar ketma – ketligi.
Navbatlar

Navbat bu shunday tuzilmaki, u elementlar qo’shilishi bilan kengayib boradi va elementlarni faqatgina bir tomondan qabul qiladi. Stekdan farqli holda, navbat tuzilmasi har ikkala tomondan ham ochiq hisoblanadi, lekin element kiritish bir tomondan, chiqarish esa ikkinchi tomonidan amalga oshiriladi. Navbat FIFO(first in first out – birinchi kelgan birinchi ketadi) ko’rinishidagi tuzilmadir. Navbatda ham xuddi stekdagi kabi C++ da alohida kutubxona mavjud.

#include

Navbatni dasturda e’lon qilish quyidagicha:

Queue nav1;

Navbat ustida quyidagi amallar bajariladi:

• 
  Clear() - navbatni tozalash.
  
• 
  isEmpty() – navbatni bo’shlikka tekshirish
  
• 
  enqueue(el)—el elementni navbatga joylashtirish
  
• 
  dequeue() —navbatdan birinchi elementni olish
  
• 
  firstEl() — navbatning birinchi elementini uni o’chirmasdan qaytaradi
  

Navbatda bajariladigan enqueue va dequeue amallari 4.7 rasmda keltirilgan. Steklardan farqli ravishda navbatlarda o’zgarishlar uning oxirida va boshida bo’lishi nazorat qilinishi lozim. Elementlar navbatga oxiridan joylashtiriladi, olish esa boshidan amalga oshiriladi.

4.7 rasm. Navbatda bajariluvchi amallar ketma – ketligi

4.8 rasm. Navbatni massivda amalga oshirilish dasturi.

4.9 rasm. Navbatni bog’langan ro’yxatda amalga oshirilish dasturi

4.10 – rasmda navbatda element qo’shish va o’chirish amallari ketma –ketligi 4.7 – rasmdagiga o’xshash ravishda ko’rsatilgan bo’lib, 4.10b da navbatni o’zgarishi massiv ko’rinishida,4.10c da bog’langan ro’yxat ko’rinishida amalga oshirilgan.

4.10 – rasm. Navbat ustida amallar bajarish.

DEK (DEQ - Double Ended Queue)

Dek so‘zi (DEQ - Double Ended Queue) ingliz tilidan olingan bo‘lib 2 ta chetga ega navbat degan ma’noni bildiradi. Dekning o’ziga xos xususiyati shundan iboratki, elementlarni yozish va o’qishni har ikkala chetidan ham amalga oshirish mumkin.

Dekni quyi chegaralari birlashtirilgan ikkita stek ko’rinishda qarash mumkin. Deklar bilan ishlash uchun ham C++ da alohida kutubxona mavjud:

#include

Deque dek1;
Dek ustida bajariladigan amallar:

• 
  boshidan element kiritish. Push_front()
  
• 
  Oxiridan element kiritish. Push_back()
  
• 
  boshidan element chiqarish. pop_front()
  
• 
  oxiridan element chiqarish. Pop_back()
  
• 
  Empty() – bo’shlikka tekshirish.
  

Dekka oid misol keltiramiz:

#include

#include

int main (){

std::deque mydeque (2,100); // two ints with a value of 100

mydeque.push_front (200);

mydeque.push_front (300);

std::cout << "mydeque contains:";

for (std::deque::iterator it = mydeque.begin(); it != mydeque.end(); ++it)

std::cout << ' ' << *it;

std::cout << '\n';

return 0;

}

Natija:

300 200 100 100
Nazorat savollar.

1. 
   Yarimstatik ma’lumotlar tuzilmasi nima va unga nimalar kiradi?
   
2. 
   Stek va uning xususiyatlari?
   
3. 
   Steklarni dasturda e’lon qilinishi?
   
4. 
   Navbat nima va dasturda qanday ifodalanadi?
   
5. 
   Dek nima va stek , navbatdaqn farqi nima? Dasturda ifodalanishi qanday?
   
6. 
   Bu tuzilmalar statik va dinamik tuzilmalardan nimasi bilan farq qiladi?
   

Adabiyotlar

1. 
   AdamDrozdek. Data structure and algorithms in C++. Fourthedition. 2013. Chapter 4.
   
2. 
   Data structure and algorithms. Made easy guide. Fast track student edition. 2014. Chapter 5,6.
   

https://play.google.com/books/reader?id=jnnCAwAAQBAJ&printsec=frontcover&output=reader&hl=ru&pg=GBS.PA8

4-mavzu.

Dinamik ma’lumotlar tuzilmasi. Chiziqli ro’yxatlar.

Reja.

1. 
   Dinamik ma’lumotlar tuzilmasi.
   
2. 
   Chiziqli bir bog’lamli ro’yhatlarvaularustidaamalbajarishalgotirmlari.
   

Kalitso’zlar: list, linked list, chiziqliro’yhatlar, birvaikkibo’glamliro’yhatlar.

Dinamikma’lumotlartuzilmasi

Bizga ma’lumki, massivlar (static tuzilmalar) dasturlash tillarida juda foydali va zaruriytu zilmadir. Lekin uning ikkita kamchiligi bor:

• 
  Uningo’lchaminidasturbajarilishimobaynidao’zgartiribbo’lmaydi;
  
• 
  Tuzilmaorasiga element kiritishuchunqolganlarinisurishkerak.
  

Bu kamchilik bog’langan ro’yhatlar bilanishlash gaolibkeladi.Bo’glanganro’yhatlarbirxiltoifadagielementlar (tugunlar) ketma-ketligibo’lib, ularxotiradaturlijoylargajoylashtiriladivao’zarobir-biribilanko’rsatkichlimaydonlarorqalibog’lanadi. Bo’glanganro’yhatlarnidasturdaturlichaamalgaoshirishmumkn.

Bo’glanganro’yhatlardaelementlarniquyidagichaxosilqilibolamiz:

Informatsion ko’rsatkichli

maydon maydon

Information maydondafoydalanuvchiningfoydalima’lumotiyoziladi.Ko’rsatkichlimaydongakeyingielementningxotiradagiadresiyoziladi.Shundayelementlardantashkiltopadigantuzilmagachiziqlibirbog’lamliro’yhatlardeyiladi.

Bog’langanro’yhatlardamassivningkamchiliklaribartarafqilinganligisabablituzilmauzunligivaelementlarorasidagimunosabatlardasturbajarilishimobaynidao’zgaribturadi. Bu dinamiktuzilmaxususiyatihisoblanadi.Dinamiktuzilma deb:

• 
  elementlariorasidagimunosabatlar
  
• 
  tuzilmauzunligi (elementlarsoni)
  

dasturbajarilishimobaynidao’zgaribturadigantuzilmagaaytiladi. Dinamiktuzilmalardaelementlarxotiradaistalganjoydajoylashishimumkin.Shusababliularorasidagimunosabatlarko’rsatkichlarorqalibelgilanadi.Elementlartuzilmagakelibqo’shilganpaytdaxotiradanbo’sh joy qidiribtopiladivaelementlarjoylashtiriladi. Shusabablielementlarxotiradaketma-ketyacheykalardajoylashmaganbo’lishimumkin.Afar fizikxotiratanqisligisezilmasa, tuzilmauzunligioshirilishimumkin.

Bundaytuzilmalarbilanishlashningo’zigayarashaafzalliklarivakamchiliklarimavjud. Afzalligishundaki, tuzilmauzunligigaoldindanchegaraqo’yilmaydi.Unga element kiritishvao’chirishamallarimassivgaqaragandaosonkechadi. Chunkielementlarxotiragaistalganjoygajoylashtirilayotganpaytdaoldinkelibtushganelementlarjoyidanqo’zg’atilmaydi.Faqatularningko’rsatkichlarito’g’irlabqo’yiladi, xolos.

Kamchiligiesashundaki, oldindanmavjudbo’lgantuzilmanimassivlardamavjudbo’lgansaralashalgoritmlaribilansaralabbo’lmaydi, chunkiularelementlarningindekslaribilanbog’liqtushunchadir.Elementlarningindeksidegantushunchayo’qligisabablielementlargato’g’ridanto’g’rimurojaatningilojiyo’q, engog’irholatdaoxirgielementga N ta murojaatorqaliyetibboriladi.

Qidiruvamalixamxuddishunday.Ya’niengog’irholatdaoxirgielementni N ta solishtirishdatopishmumkin.

Bog’langan ro’yhatlar eng ko’p tarqalgan dinamik tuzilmalardan hisoblanadi. Ma’lumotlarni mantiqiy tasvirlash nuqtai nazaridan ro’yhatlar ikkitaga ajratiladi: chiziqli va chiziqsiz.

Chiziqli ro’yhatlarda elementlar orasidagi bog’liqlik qat’iy tartiblangan bo’ladi, ya'ni element ko’rsatkichi o’zidan oldingi yoki navbatdagi element manzilini saqlaydi.

Chiziqli ro’yhatlarga bir yoki ikki bog’lamli ro’yhatlar kiradi.

Chiziqsiz ro’yhatlarga esa ko’p bog’lamli ro’yhatlar kiradi.Umumanolganda, ro’yhat elementlari biryoki bir nechtako’rsatkichli maydonlargaegabo’lishimumkin. Vaxarbirko’rsatkichiorqaliistalganelementgamurojaatqilsa, bundayro’yhatlarchiziqsizro’yhatlardeyiladi.

Chiziqlibirbog’lamliro’yhatlarvaularustidaamalbajarishalgoritmlari

Tuzilmada elementlar o‘zidan keyingi element bilan bog‘langan bo‘lsa, bunday ro‘yhatga bir bog‘lamli ro‘yhat deyiladi. Agar har bir element o‘zidan oldingi va o‘zidan keyingi element bilan bog‘langan bo‘lsa, u holda bunday ro‘yhatlarga 2 bog‘lamli ro‘yhatlar deyiladi. Agar oxirgi element birinchi element ko‘rsatkichi bilan bog‘langan bo‘lsa, bunday ro‘yhatga halqasimon ro‘yhat deyiladi. Ro‘yhatning har bir elementi shu elementni identifikatsiyalash uchun kalitga ega bo‘ladi. Kalit odatda butun son yoki satr ko‘rinishida ma’lumotlar maydonining bir qismi sifatida mavjud bo‘ladi. 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 tartibgakeltirish.
  

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.

Mazkur ko‘rinishdagi ro‘yhat elementi ko‘rsatkichining o‘ziga xosligi shundan iboratki, u faqatgina ro‘yhatning navbatdagi (o‘zidan keyin keluvchi) elementi adresini ko‘rsatadi. Bir tomonlama yo‘naltirilgan ro‘yhatda eng so‘ngi element ko‘rsatkichi bo‘sh, ya’ni NULL bo‘ladi.

Lst – ro‘yhat boshi ko‘rsatkichi. U ro‘yhatni yagona bir butun sifatida ifodalaydi. Ba’zan ro‘yhat bo‘sh bo‘lishi ham mumkin, ya’ni ro‘yhatda bitta ham element bo‘lmasligi mumkin. Bu holda lst = NULL bo‘ladi. Hozir chiziqli bir bog‘lamli ro‘yhat hosil qilish dasturini ko‘rib chiqsak. Buning uchun biz foydalanuvchi tomonidan yaratiladigan nostandart toifa yaratib olishimiz kerak. Buning bir qancha usullari mavjud, ya’ni klasslar yoki strukturalar bilan amalga oshirish mumkin. Masalan,

class Node{

public://klassma’lumotlariga tashqaridan bo‘ladigan murojaatga ruxsat berish

int info; // informatsion maydon

Node* next;// ko‘rsatkichli maydon

};

Bu yerda biz Node nomli toifa yaratdik va ro‘yhatimiz butun sonlardan iborat. Endi ro‘yhat elementlarini shu toifa orqali e’lon qilsak bo‘ladi, ya’ni

Node *lst = NULL;// ro‘yhat boshi ko‘rsatkichi

Node *last = NULL;// ro‘yhatga oxirgi kelib tushgan elementning ko‘rsatkichi

Endi shu belgilashlar orqali ro‘yhat hosil qilamiz.

Node * p = new Node;

int numb = -1;

cout<<"son kiriting: ";

cin>>numb;

p->info = numb;

p->next = NULL;

if (lst == NULL) {

lst = p;

last = p;

}

else{ last->next = p;

last = p; }

Bu dasturda yangi element ro‘yhat oxiridan kelib qo‘shiladi.

Bir bog‘lamli ro‘yhatlar ustida amallarbajarishalgoritmlari

1. 
   Bir bog‘lamli ro‘yhat boshiga element qo‘yish
   

1-rasm. Bir bog‘lamli chiziqli ro‘yhat tuzilishi

1-rasmdagi ro‘yhat boshiga informatsion maydoniD o‘zgaruvchi bo‘lgan element qo‘yamiz. Ushbu ishni amalga oshirish uchun quyidagi amallarni bajarish lozim bo‘ladi:

a) pko‘rsatkich murojaat qiladigan, bo‘sh element yaratish (2-rasm).

2-rasm.Yangi element hosilqilish

b) Yaratilgan element informatsionmaydoniga D o‘zgaruvchi qiymatini o‘zlashtirish (3-rasm).

3-rasm.Yangi element info maydonigaqiymatkiritish

c) Yangi elementni ro‘yhat bilan bog‘lash: p->ptr=lst; (shuholatdayangi element valst– ro‘yhat boshini ko‘rsatyapti)

d) lst ko‘rsatkichni ro‘yhat boshiga ko‘chirish (4-rasm). lst=p;

Va nihoyat:

4-rasm. Ro‘yhat boshiga element qo‘shish

Endi shu algoritmni C++ tilidagi realizatsiyasini ko‘rib chiqamiz.

Node * p = new Node;

int numb = -1;

cout<<"son kiriting: ";

cin>>numb;

p->info = numb;

if (lst ==NULL){

p->next = NULL;

lst = p; }

else { p->next = lst;

lst = p;}