Xo'sh, DSA shunday, to'g'rimi?

Albatta, nima uchun emas. Rostini aytsam, DSA har bir kishi o'qishdan biroz qo'rqadigan narsadir. DSA kollejda yoki har qanday texnologik ish uchun shunday narsalardan biri bo'lib, bu mavzusiz hech narsa qilib bo'lmaydi. Har bir intervyu, siz murojaat qilayotgan portfeldan qat'i nazar, DSA tushunchalarini mutlaq chuqurlikda talab qiladi.

Nomidan ko'rinib turibdiki, ma'lumotlar - bu hamma narsa haqida. Ma'lumotlarning har jihatdan qanday tuzilganligi butun mavzuning kontseptsiyasidir va algoritmlar biz ma'lumotlar tuzilmalarini soddalashtirish uchun yaratgan usullardir.

Shunday qilib, men ham hozir ikkinchi kurs talabasiman, yuqori maoshli texnologik ishga kirishni maqsad qilganman va men bu mavzudan qo'rqaman va ochig'ini aytganda, bu unchalik qiziq emas. Ushbu maqola men uchun ham turtki bo'lib, o'rnimdan turishga, mavzuni yaxshi ko'rishga (chunki bularning barchasi ma'lumotlar va men ma'lumotlar atrofida o'ynashni yaxshi ko'raman) va imkon qadar uni o'rganishga harakat qilaman. Maqola mening DSA haqidagi nazariy bilimlarim haqida tushuncha bo'ladi va men joylashtirishga tayyorgarlik ko'rganimda, yaqin kelajakda bu mavzu bizni qayerga olib borishini ko'ramiz.

Yaxshi ishlab chiqilgan ma'lumotlar strukturasi va samarali algoritm hisoblash dahshatli tushini silliq va oqlangan yechimga aylantirishi mumkin.

Ma'lumotlar tuzilmalari va algoritmlari siz tanlagan har qanday tilda, python, java, c, c++ va boshqalarda amalga oshirilishi mumkin.

Endi ma'lumotlar strukturasi nima?

Qisqa javob: "ma'lumotlar tuzilmasi" - kirish va foydalanish uchun tizimdagi ma'lumotlarni tashkil qilishning o'ziga xos vositasi.

Uzoq javob shuki, ma'lumotlar strukturasi - bu ma'lumotlarni tashkil qilish, boshqarish, qidirish va saqlashning kombinatsiyasi bo'lib, samarali kirish va o'zgartirish imkonini beruvchi bir formatga birlashtirilgan. Bu ma'lumotlar qiymatlarini, ular bilan bo'lgan munosabatlarni va tegishli funktsiyalar yoki operatsiyalarni to'playdi.

Mana haqiqiy dunyo misoli. Agar siz kutubxonaga borib, 20-asr harbiy tarixiga oid kitob topmoqchi boʻlsangiz, “Tarix” boʻlimiga kirasiz. U yerdan siz harbiy tarix uchun ajratilgan hududni topasiz, keyin 20-asrni topguningizcha xronologik tartibda saralangan kitoblarni ko'rib chiqasiz. Endi kitoblarni sizning ma'lumotlaringiz deb hisoblang va kutubxonaning kitoblarni saralash usulini ma'lumotlar tuzilmasi sifatida ko'rib chiqing va hamma narsa tayyor!

Ma'lumotlar tuzilmalari yaratilgan ma'lumotlarning katta hajmini boshqarish uchun zarur va algoritm samaradorligini oshirishda hal qiluvchi omil hisoblanadi.

Ma'lumotlar strukturasining turlari

Ma'lumotlarning chiziqli tuzilishi

Ma'lumotlarning chiziqli bo'lmagan tuzilishi

Chiziqli ma'lumotlar tuzilmalari

Chiziqli ma'lumotlar tuzilmalarida elementlar birin-ketin ketma-ket joylashadi. Elementlar ma'lum bir tartibda joylashtirilganligi sababli ularni amalga oshirish oson.

1. Massiv

Massivda xotiradagi elementlar doimiy xotirada joylashadi. Massivning barcha elementlari bir xil turdagi. Va massivlar ko'rinishida saqlanishi mumkin bo'lgan elementlarning turi dasturlash tili bilan belgilanadi.

2. Stack

Stack ma'lumotlar strukturasida elementlar LIFO printsipida saqlanadi. Ya'ni, stekda saqlangan oxirgi element avval o'chiriladi.

U xuddi qoziqda saqlangan oxirgi plastinka birinchi bo'lib olinadigan plitalar qozig'i kabi ishlaydi.

3. Navbat

Stackdan farqli o'laroq, navbatdagi ma'lumotlar strukturasi FIFO printsipida ishlaydi, bu erda navbatda saqlangan birinchi element birinchi bo'lib o'chiriladi.

Bu xuddi kassadagi odamlarning navbati kabi ishlaydi, bu erda navbatda turgan birinchi odam chiptani birinchi bo'lib oladi.

4. Bog'langan ro'yxat

Bog'langan ro'yxat ma'lumotlar strukturasida ma'lumotlar elementlari bir qator tugunlar orqali ulanadi. Va har bir tugun ma'lumotlar elementlarini va keyingi tugun manzilini o'z ichiga oladi.

Chiziqli bo'lmagan ma'lumotlar tuzilmalari

Chiziqli ma'lumotlar tuzilmalaridan farqli o'laroq, chiziqli bo'lmagan ma'lumotlar tuzilmalaridagi elementlar hech qanday ketma-ketlikda emas. Buning o'rniga ular bir element bir yoki bir nechta elementlarga ulanadigan ierarxik tarzda joylashtirilgan.

Chiziqli bo'lmagan ma'lumotlar tuzilmalari yana grafik va daraxtga asoslangan ma'lumotlar tuzilmalariga bo'linadi.

1. Grafik

Grafik ma'lumotlar strukturasida har bir tugun cho'qqi deb ataladi va har bir cho'qqi boshqa cho'qqilarga qirralar orqali ulanadi.

2. Daraxtlar ma'lumotlar strukturasi

Grafikga o'xshab, daraxt ham cho'qqilar va qirralarning to'plamidir. Biroq, daraxt ma'lumotlari tuzilmasida ikkita cho'qqi o'rtasida faqat bitta chekka bo'lishi mumkin.

Chiziqli va chiziqli bo'lmagan ma'lumotlar tuzilmalari

Grafik turlari

  • Null grafik
  • Trivial grafik
  • Yo'naltirilmagan grafik
  • Yo'naltirilgan grafik
  • Ulangan grafik
  • Ajratilgan grafik
  • Oddiy grafik
  • To'liq grafik
  • Tsikl grafigi
  • Tsiklik grafik
  • Asiklik grafik
  • Cheklangan grafik
  • Cheksiz grafik
  • Ikki tomonlama grafik
  • Planar grafik
  • Oddiy grafik
  • Ko'p grafik
  • Psevdo grafik
  • Eyler grafigi
  • Gamilton grafigi

Ma'lumotlar tuzilmasida grafik o'tish

Grafik o'tish - bu grafikdagi har bir cho'qqiga tashrif buyurish yoki yangilash. Ularning cho'qqilarga tashrif buyurish tartibi o'tishlarni tasniflaydi. Grafik o'tishni amalga oshirishning ikki yo'li mavjud:

  1. Breadth-First Search (BFS):Bu grafikni gorizontal ravishda kesib o'tuvchi o'tish operatsiyasi. Keyingi darajaga o'tishdan oldin u barcha tugunlarni bir darajada kesib o'tadi. U grafikning ildizidan boshlanadi va keyingi darajaga o'tishdan oldin barcha tugunlarni bir chuqurlik darajasida kesib o'tadi.
  2. First-First Search (DFS): Bu grafikni vertikal ravishda kesib o'tuvchi yana bir o'tish operatsiyasi. U grafikning ildiz tugunidan boshlanadi va orqaga qaytishdan oldin iloji boricha har bir filialni tekshiradi.

Quyidagilar daraxt ma'lumotlar strukturasining turlari:

  • Umumiy daraxt:

  • Ikkilik qidiruv daraxti
  • AVL daraxti
  • Qizil-qora daraxt
  • Spley daraxti
  • Tuzoq
  • B-daraxt
  • Minimal kenglikdagi daraxt

Keling, turli xil algoritmlarni bilib olaylik.

Lekin birinchi navbatda, kompyuter fanlari sohasidagi algoritmlar nima?

Algoritm - bu masalani hal qilish yoki hisoblash uchun ishlatiladigan protsedura. Algoritmlar apparat yoki dasturiy ta'minotga asoslangan tartiblarda belgilangan harakatlarni bosqichma-bosqich bajaradigan ko'rsatmalarning aniq ro'yxati sifatida ishlaydi.

Algoritmlar ITning barcha sohalarida keng qo'llaniladi. Matematika va informatika fanlarida algoritm odatda takrorlanuvchi muammoni hal qiladigan kichik protseduraga ishora qiladi. Algoritmlar ma'lumotlarni qayta ishlashni amalga oshirish uchun spetsifikatsiya sifatida ham qo'llaniladi va avtomatlashtirilgan tizimlarda katta rol o'ynaydi.

Algoritm raqamlar to'plamini saralash yoki ijtimoiy tarmoqlarda foydalanuvchi kontentini tavsiya qilish kabi murakkabroq vazifalar uchun ishlatilishi mumkin. Algoritmlar odatda dastlabki kiritish va ma'lum bir hisoblashni tavsiflovchi ko'rsatmalar bilan boshlanadi. Hisoblash amalga oshirilganda, jarayon chiqish hosil qiladi.

Algoritmlar turlari:

Qidirilmoqda:

1) Ikkilik qidiruv

2) Chiziqli qidiruv

3) Birinchi qidiruv chuqurligi

4) Kenglik-Birinchi qidiruv

Tartiblash:

1) Qo'shishni saralash

2) Uyma tartiblash

3) Tanlovni saralash

4) Birlashtirish tartibi

5) Tez tartiblash

6) Sanoqni tartiblash

7) Paqirni saralash

8) Bubble Sort

9) Radix Saralash

10) Shell Sort

Grafiklar:

1) Kruskal algoritmi

2) Deykstra algoritmi

3) Bellman Ford algoritmi

4) Floyd Uorshall algoritmi

5) Topologik tartiblash algoritmi

6) To'fonni to'ldirish algoritmi

7) Prim algoritmi

Massivlar:

1) Kadane algoritmi

2) Floyd siklini aniqlash algoritmi

Daraxt:

1) AA daraxti

2) Ikkilik indeksli daraxt yoki Fenvik daraxti

5) Uyum daraxti

Boshqalar:

1) Huffman kodlash siqish algoritmi

2) Evklid algoritmi

3) Xash xaritasi algoritmi

4) Dinamik dasturlash

5) Ochko'z algoritmlari

6) Bo'lish va zabt etish algoritmlari

Xulosa

Xo'sh, birinchi navbatda, ushbu maqolada men har bir ma'lumotlar tuzilishi va algoritmi haqida qisqacha ma'lumot bermadim. DSA haqida yozish mumkin bo'lgan minglab va minglab narsalar bo'lishi mumkin. Har bir algoritmning o'ziga xos matematika va dasturlash to'plami mavjud, tahlil qismi, bir nechta yozuvlar, ba'zi juda keng tarqalgan misollar to'plami, ulardan biri xalta muammosi. Bu mavzu DAA, dizayn algoritmi va tahlili deb ataladi, bu vaqt va makon murakkabligi kabi ba'zi fundamental mavzularni birlashtiradi, ammo bu boshqa kun uchun mavzu. IShunday bo'lsa-da, joylashtirish pov dan yaxshi savollar ro'yxatini ilova qilaman. Bu yerda tekshirishingiz mumkin.



DSA by Shradha Didi & Aman Bhaiya
DSA 2,5 oy ichida Shradha Didi va Aman Bhaiya DSA Biz bilan Youtube orqali tanishing (Apna kolleji) Ushbu varaqni qanday hal qilish mumkin? Ideal...docs.google.com



Maqolaning maqsadi quyi darajadagi DSA nima haqida qisqa va tezkor tushuncha berish edi. Shu bilan keling, DSA bo'yicha muvaffaqiyat sari boshlaymiz va o'zimizni mag'rurlaylik va menga ishoning, DSA bilan bog'liq murakkab muammolarni hal qila oladigan odam, demoqchimanki, bu texnologiya olamidagi haqiqiy moslashuvchanlik.

Keyingi safargacha ishlashda, o'rganishda davom eting!!!