|
Quyida keltirilgan ma’lumotlar tuzilmalari dasturlashda eng ko’p qo’llaniladigan tuzilmalardir. Ularga:
1. Massiv (Array)
2. Bog’langan ro’yhat (Linked List)
3. Navbat (Queue)
4. Stek (Stack)
5. Hash jadvallar (Hash tables)
6. Daraxtlar (Trees)
7. Graflar (Graph)
kiradi. Biz bu bo’limda boshidagi 5 ta tuzilma bilan yaqindan tanishib, ularning kuchli va kuchsiz tomonlari va ularni qanday holatlarda ishlatish ma’qulligi haqida gaplashib o’tamiz. Qolgan ikkita tuzilma murakkabroq bo’lib ular o’z ichida yana ko’plab turlarga bo’linib ketadi. Shuning uchun ularni keyinroqqa qoldiramiz.
Bundan tashqari barcha tuzilmalarning hamma joyda ingliz tilidagi nomi ishlatilgani va ularning nomi odatda tarjima qilinmaganligi sababli keyingi o’rinlarda men ularning asosan ingliz tilidagi nomlarini ishlataman.
Turli xildagi ma’lumotlar tuzilmalari nima uchun kerak?
Ma’lumotlar tuzilmalari nimaligi haqida qisman tasavvurga ega bo’ldingiz va ularning asosiy turlari bilan ham tanishib oldingiz. Lekin, shu joyga kelib agar sizda “Nima uchun ma’lumotlarning turli xil tuzilmalari kerak?” “Nima uchun bir turdagi universal ma’lumotlar tuzilmalaridan foydalanib qo’ya qolsa bo’lmaydi?” degan savol tug’ilmagan bo’lsa, bu yaxshi emas.) Keling endi shu savolga javob topishga harakat qilamiz.
Undan oldin ma’lumotlar tuzilmalari ustida asosiy bajarilishi mumkin bo’lgan amallarni ko’rib chiqaylik. Bularga ma’lumotlarni
Ko’rib chiqish (Traversing)
O’qib olish (Retrieving)
Kiritish (Insertion)
O’chirish (Deletion)
Qidirish (Search)
Saralash (Sorting)
Birlashtirish (Merging)lar kiradi.
Turli xildagi ma’lumotlar tuzilmalarida esa yuqoridagi amallar turlicha tezlikda amalga oshadi.
Masalan oddiyroq misol olaylik, array uchun ma’lumotni o’qib olish uchun O(1) vaqt sarflansa, uni kiritish yoki o’chirish uchun O(n) vaqt sarflanadi. Linked listda esa bular aksincha. Shuning uchun, masalan, sizning dasturingizda ma’lumotlar ko’p kiritilib, o’chirilsayu lekin kam o’qilsa, bunda ma’lumotlarni saqlashda arraydan foydalangandan ko’ra linked list qulayroq hisoblanadi. Lekin, ko’pincha holatda bir necha ma’lumotlar tuzilmalarini o’zini birlashtirgan gibrid ma’lumotlar tuzilmalaridan ham foydalaniladi. Bu haqida keyingi darslarimizda batafsil to’xtalib o’tamiz.
Shu bilan bugungi ma’lumotlar tuzilmalari bilan tanishuv darsimizni tugatamiz va keyingi darsda arraylar va linked listlar haqida batafsil gaplashamiz.
Векторлар ва уларни хоссалари. 2таусул билан 2 та вектор хосил килишдастуринитузинг
Agar siz shu paytgacha C++ da “toza” massivlardan foydalangan bo‘lsangiz, siz ko‘p narsani yo‘qotdingiz. “Sof” massivlar deganda men C++ tilida massivlardan maxsus funksiya va usullarsiz odatiy foydalanishni nazarda tutyapman. Ushbu maqolani o'qib bo'lgach, siz massivlar bilan qanday qilib yuqori darajada ishlashingiz mumkinligini bilib olasiz, massivlarni (e'lon qilish, ishga tushirish, qidirish, saralash va boshqa ko'plab operatsiyalar) bir necha qatorda qayta ishlashingiz mumkin.
Xo'sh, C ++ da Vektor nima? Oddiy qilib aytganda, vektorni dinamik massivni taqlid qiluvchi mavhum model sifatida tasvirlash mumkin. Hali bu ta'rifni o'rganishning hojati yo'q, endi biz mashq qilishni boshlaymiz va sizga hamma narsa aniq bo'ladi.
Agar biz dasturimizda vektorlardan foydalanmoqchi bo'lsak, sarlavha faylini kiritishimiz kerak :
Vektorni quyidagicha e'lon qilish mumkin:
1
2
|
std::vector myVector; // int
myVector.reserve(10); // int
|
Misoldan ko'rinib turibdiki, vektorlar nomlar maydonidir std. Aslida, bu ikki yozuv quyidagi kabi yozishga teng:
1
|
int myVector[10]; // обычное объявление массива
|
Bir qarashda vektor deklaratsiyasi ancha og'irroq bo'lib chiqdi. Biroq, vektorlar juda kuchli funksionallikni yashiradi, buni oddiy C ++ massivlari haqida aytib bo'lmaydi . Bundan tashqari, vektor bir qatorda e'lon qilinishi mumkin, masalan:
1
|
std::vector myVector(10);
|
Ushbu yozuv avvalgi ikkitasiga teng, ya'ni bu erda biz 10tipdagi elementlarda boshlang'ich o'lchamli vektorni e'lon qildik int. Bundan tashqari, vektorni e'lon qilishning bu usuli nafaqat xotirani ajratadi, balki vektorning barcha elementlarini nol bilan ishga tushiradi. Mana bir misol:
1
2
3
4
5
6
7
8
9
10
11
|
#include
#include // подключаем модель Векторов
using namespace std;
int main()
{
vector myVector(10); // объявляем вектор размером в 10 элементов и инициализируем их нулями
// вывод элементов вектора на экран
for(int i = 0; i < myVector.size(); i++)
cout << myVector[i] << ' ';
return 0;
}
|
u holda dasturning natijasi boshqacha bo'ladi, chiqish oqimida hech narsa ko'rinmaydi, chunki vektor elementlarining dastlabki ishga tushirilishi yo'q, ya'ni vektorni e'lon qilishning bu usuli tezroq bo'ladi. Vektorlarni e'lon qilishning ushbu ikki usuli o'rtasidagi farq shu erda.
Yuqoridagi bir nechta paragraflarda men vektorning dastlabki hajmini eslatib o'tdim. Nima uchun boshlang'ich o'lcham? Chunki vektorning o'lchami etarli bo'lmasa, vektor yangi elementlarni qo'shganda, uning hajmini qayta hisoblashda avtomatik ravishda ortadi. Bu juda qulay, chunki biz ko'pincha dastur ishlashi uchun zarur bo'lgan massiv hajmini oldindan aytib bo'lmaydi. Ushbu misolni biroz keyinroq batafsil ko'rib chiqamiz.
Vektorni nusxalash qanchalik oson ekanligini ko'ring:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include
#include // подключаем модель Векторов
using namespace std;
int main()
{
vector myVector1(10);
// вывод элементов вектора на экран
cout << "Входной массив: ";
for(int i = 0; i < myVector1.size(); i++) {
myVector1[i] = i;
cout << myVector1[i] << ' ';
}
cout << "\nСкопированный массив: ";
vector myVector2(myVector1); // при объявлении второго вектора, копируется - первый
for(int i = 0; i < myVector2.size(); i++) {
myVector2[i] = i;
cout << myVector2[i] << ' ';
}
return 0;
}
|
massiv1 == massiv2
Dastur natijasiga ko'ra, 14- qatorda vektorning nusxasi yaratilganligini aniq ko'rishingiz mumkin myVector1. Ikki massivni taqqoslaydigan dasturni ko'rib chiqing:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include
#include
using namespace std;
int main()
{
vector array1(3);
// инициализируем элементы вектора array1
array1[0] = 4;
array1[1] = 2;
array1[2] = 1;
vector array2(3);
// инициализируем элементы вектора array2
array2[0] = 4;
array2[1] = 2;
array2[2] = 1;
// сравниваем массивы
if (array1 == array2) {
cout << "array1 == array2" << endl;
}
return 0;
}
|
Natija:
Kirish massivi: 0 1 2 3 4 5 6 7 8 9
Nusxalangan massiv: 0 1 2 3 4 5 6 7 8 9
Shunday qilib, biz massivlarni biz uchun odatiy tarzda ishga tushirdik,
Do'stlaringiz bilan baham: |
