Kirish Ma'lumotlar tuzilmalari

Kirish - Ma'lumotlar tuzilmalari
Ma'lumotlar strukturasi - bu kompyuterda ma'lumotlarni tashkil qilishning o'ziga xos usuli
undan samarali foydalanish mumkin. G'oya makon va vaqtni qisqartirishdir
turli vazifalarning murakkabligi.
Yaxshi ma'lumotlar strukturasini tanlash turli xil ishlarni bajarishga imkon beradi
muhim operatsiyalarni samarali bajarish. Samarali ma'lumotlar tuzilmasi minimaldan foydalanadi
strukturani qayta ishlash uchun xotira maydoni va bajarilish vaqti.
Ma'lumotlar tuzilmalari turli sohalarda qo'llaniladi, masalan:
Operatsion tizim
Grafika
Kompyuter dizayni
Simulyatsiya va boshqalar.
Kirish - Ma'lumotlar tuzilmalari
Algoritmlar dasturlardan farqli o'laroq
Muayyan vazifa uchun algoritmni “ko'rsatmalarning cheklangan ketma-ketligi, har biri
aniq ma'noga ega bo'lib, cheklangan miqdordagi harakat bilan bajarilishi mumkin
vaqt uzunligi".
Shunday qilib, algoritm inson tushunadigan darajada aniq bo'lishi kerak. Biroq,
Kompyuter tomonidan bajarilishi uchun bizga odatda a da yozilgan dastur kerak bo'ladi
qat'iy rasmiy til; va chunki kompyuterlar insonga nisbatan ancha moslashuvchan
Ma'lumki, dasturlar odatda algoritmlardan ko'ra ko'proq tafsilotlarni o'z ichiga olishi kerak.
Bu erda biz ushbu dasturlash tafsilotlarini e'tiborsiz qoldirib, dizaynga e'tibor qaratamiz
dasturlar emas, balki algoritmlar.
Algoritmlar dasturlardan farqli o'laroq
Muayyan vazifa uchun algoritmni "ko'rsatmalarning cheklangan ketma-ketligi, har biri
aniq ma'noga ega bo'lib, cheklangan miqdordagi harakat bilan bajarilishi mumkin
vaqt uzunligi".
Shunday qilib, algoritm inson tushunadigan darajada aniq bo'lishi kerak. Biroq,
kompyuter tomonidan bajarilishi uchun bizga odatda a da yozilgan dastur kerak bo'ladi
qat'iy rasmiy til; va chunki kompyuterlar insonga nisbatan ancha moslashuvchan
Ma'lumki, dasturlar odatda algoritmlardan ko'ra ko'proq tafsilotlarni o'z ichiga olishi kerak.
Bu erda biz ushbu dasturlash tafsilotlarini e'tiborsiz qoldirib, dizaynga e'tibor qaratamiz
dasturlar emas, balki algoritmlar.
Imperativ va deklarativ dasturlash
Muhokama qilingan algoritmlarni kompyuter dasturlari sifatida amalga oshirish vazifasi
muhim, albatta, lekin biz nazariy jihatlarga e'tibor qaratamiz va
amaliy dasturlash jihatlarini boshqa joyda o'rganish uchun qoldiring.
Aytgancha, biz tez-tez va dolzarb segmentlarni yozish foydali bo'ladi
algoritmlarning ayrim nazariy jihatlarini aniqlashtirish va sinab ko'rish uchun dasturlar
va ularning ma'lumotlar tuzilmalari.
Turli xil dasturlash o'rtasidagi farqni ham yodda tutish kerak
paradigmalar: Imperativ dasturlash hisoblashni quyidagicha tavsiflaydi
dastur/ma'lumotlar holatini o'zgartiruvchi ko'rsatmalar, bu erda Deklarativ
Dastursiz nimaga erishishi kerak bo'lgan dasturlash turlari
buni qanday qilishni tasvirlab beradi. Biz birinchi navbatda rivojlanish bilan shug'ullanamiz
Imperativ dasturlash yondashuviga osongina mos keladigan algoritmlar.
Psevdokod
Algoritmlarni aniq ingliz tilida tasvirlash mumkin va biz buni qilamiz
ba'zan shunday qiling.
Biroq, kompyuter olimlari uchun bu odatda osonroq va tushunarli
formatlanganlar o'rtasida kelgan biror narsadan foydalaning
Ingliz tili va kompyuter dasturi kodi, lekin ishga tushirilmaydi, chunki
ba'zi tafsilotlar o'tkazib yuborilgan.
Bu psevdokod deb ataladi, u turli shakllarda keladi. Biz
ga juda o'xshash psevdokod segmentlarini taqdim etadi
Bizni asosan qiziqtiradigan tillar, yaʼni C tilining oʻzaro oʻxshashligi
va Java, afzalligi bilan ularni osongina kiritish mumkin
ishga tushiriladigan dasturlar.
Algoritmlar bo'yicha asosiy savollar
Muayyan muammoni hal qilish algoritmini hisobga olgan holda, biz tabiiy ravishda so'rashga majbur bo'lamiz:
1. U nima qilishi kerak?
2. Haqiqatan ham u o'zi qilishi kerak bo'lgan narsani qiladimi?
3. U buni qanchalik samarali bajaradi?
Ushbu uch jihat uchun odatda ishlatiladigan texnik atamalar:
1. Spetsifikatsiya.
2. Tekshirish.
3. Ish faoliyatini tahlil qilish.
Ushbu uch jihatning tafsilotlari odatda muammoga bog'liq bo'ladi.
Spetsifikatsiya
Spetsifikatsiya muhim tafsilotlarni rasmiylashtirishi kerak
algoritm hal qilish uchun mo'ljallangan muammo. Ba'zan shunday
bog'langan ma'lumotlarning ma'lum bir ko'rinishiga asoslanadi,
va ba'zan u ko'proq mavhum tarzda taqdim etiladi.
Odatda, u qanday kirish va chiqishlarni belgilashi kerak bo'ladi
algoritm bir-biriga bog'liq, ammo buning uchun umumiy talab yo'q
spetsifikatsiya to'liq yoki noaniq.
Oddiy muammolar uchun ko'pincha aniq bir narsani ko'rish oson
algoritm har doim ishlaydi, ya'ni uning spetsifikatsiyasiga javob beradi.
Biroq, murakkabroq spetsifikatsiyalar va/yoki algoritmlar uchun,
algoritm uning spetsifikatsiyasiga javob berishi haqiqat bo'lmasligi mumkin
umuman aniq.
Sinov
Umuman olganda, bir nechta ma'lum kirishlar bo'yicha test qilish shuni ko'rsatish uchun etarli bo'lishi mumkin
algoritm noto'g'ri. Biroq, turli potentsial kirishlar soni beri
chunki ko'pchilik algoritmlar nazariy jihatdan cheksiz va amalda juda katta, shunchaki emas
Algoritm o'z talablariga javob berishiga ishonch hosil qilish uchun alohida holatlar bo'yicha test o'tkazish kerak
spetsifikatsiya. Bizga to'g'ri dalillar kerak.
Garchi biz dalillarni va invariantlar kabi foydali g'oyalarni muhokama qilsak ham, biz
odatda buni juda norasmiy tarzda qiladi (garchi, albatta, biz qilamiz
qat'iy bo'lishga harakat qiling).
Buning sababi shundaki, biz ma'lumotlar tuzilmalariga e'tibor qaratmoqchimiz va
algoritmlar. Rasmiy tekshirish usullari murakkab va odatda shunday bo'ladi
asosiy g'oyalar o'rganilgunga qadar qoldi.
Sinov va samaradorlik
Nihoyat, algoritmni bajarish samaradorligi resurslarga bog'liq
uning qanchalik tez ishlashi yoki qancha kompyuter xotirasi kabi talab qilinadi
foydalanadi.
Bu odatda muammo namunasi hajmiga, ma'lumotlar tanloviga bog'liq bo'ladi
vakillik va algoritm tafsilotlari. Darhaqiqat, bu odatdagidek
yangi ma'lumotlar tuzilmalari va algoritmlarini ishlab chiqishga yordam beradi.
Kosmik murakkablik
Uning kurs davomida algoritm tomonidan talab qilinadigan xotira maydoni miqdori
uning bajarilishi haqida. Kosmik murakkablik ko'p foydalanuvchi uchun jiddiy qabul qilinishi kerak
tizimlar va cheklangan xotira mavjud bo'lgan holatlarda.
Algoritm odatda quyidagi komponentlar uchun joy talab qiladi:
Ko'rsatmalar maydoni: bajariladigan versiyani saqlash uchun zarur bo'lgan joy