Single-linked-list.svg
Uch tugunli bog'langan ro'yxatda ikkita maydon mavjud: butun son va keyingi tugunga havola
Java misol
Bu Java bilan bog'langan ro'yxatni amalga oshirishda butun sonlarni saqlash uchun ishlatiladigan tugun sinfiga misol:
umumiy sinf IntNode {
jamoat qiymati int ;
IntNode-ga ommaviy havola;
public IntNode(int v) {qiymat = v; }
}
C dagi misol
Bu C da bog'langan ro'yxatni amalga oshirish uchun ishlatiladigan tuzilishga misol:
strukturali tugun
{
int qiymati;
strukturali tugun * keyingi;
};
Bu typedefs dan foydalanishga misol:
typedef strukturali tugun
struktura tugunlari
{
int qiymati;
tugun * keyingi;
};
Eslatma: Xuddi shu tuzilishga ishora qiluvchi elementni o'z ichiga olgan o'xshash tuzilma o'z-o'ziga havola qiluvchi tuzilma deb ataladi.
C++ tilidagi misol
Bu C++ da bog'langan ro'yxatni amalga oshirish uchun ishlatiladigan tugun sinfi tuzilishiga misol:
Tugun sinfi
{
int qiymati;
Tugun * keyingi;
};
Daraxtlarni qidirish
Qidiruv daraxti - bu daraxtga o'xshash ma'lumotlar strukturasi bo'lib, uning tugunlari saralangan to'plamdan ma'lumotlar qiymatlarini saqlashi mumkin, shuning uchun daraxt tashrif buyurish tartibida o'tganda, tugunlar saqlangan qiymatlarning ortib borish tartibida tashrif buyuriladi.
Asosiy xususiyatlar
Tugunlar deb ataladigan ob'ektlar tartiblangan to'plamda saqlanadi.
O'tish tartibida daraxtdagi ma'lumotlarni o'sish tartibida o'qiydi.
Bog'langan ro'yxat va massivlar
Massivlar bilan solishtirganda, bog'langan ma'lumotlar tuzilmalari ma'lumotlarni tartibga solish va ular uchun joy ajratishda ko'proq moslashuvchanlikni ta'minlaydi. Massivlar bilan massivning o'lchami boshida aniq ko'rsatilishi kerak, bu xotiraning potentsial yo'qotilishi yoki keyinchalik funksionallikka qandaydir tarzda xalaqit beradigan o'zboshimchalik chegarasi bo'lishi mumkin. Bog'langan ma'lumotlar strukturasi dinamik ravishda yaratilgan va hech qachon dastur talab qilganidan kattaroq bo'lmasligi kerak. Bundan tashqari, qancha joy ajratish kerakligi nuqtai nazaridan yaratish vaqtida taxmin qilishni talab qilmaydi. Bu behuda xotiraning oldini olish uchun kalit bo'lgan xususiyatdir.
Massivda massiv elementlari xotiraning ulashgan (bog'langan va ketma-ket) qismida joylashishi kerak. Ammo bog'langan ma'lumotlar tuzilmasida har bir tugunga havola foydalanuvchilarga keyingisini topish uchun kerakli ma'lumotlarni beradi. Bog'langan ma'lumotlar strukturasining tugunlari, massivlardan farqli o'laroq, ular orasidagi mantiqiy aloqalarga ta'sir qilmasdan, jismoniy xotiraning turli joylariga alohida ko'chirilishi mumkin. Ehtiyotkorlik bilan ma'lum bir jarayon yoki ip boshqa qismlarda boshqa jarayonlar yoki oqimlar ishlayotgan bo'lsa ham, ma'lumotlar strukturasining bir qismiga tugunlarni qo'shishi yoki olib tashlashi mumkin.
Boshqa tomondan, bog'langan ma'lumotlar strukturasidagi har qanday muayyan tugunga kirish har bir tugunda saqlanadigan bog'lanishlar zanjiriga rioya qilishni talab qiladi. Agar struktura n ta tugunga ega bo'lsa va har bir tugun ko'pi bilan b havolalarni o'z ichiga olsa, ba'zi tugunlarga logarifmik b n qadamdan kamroq vaqt ichida erishib bo'lmaydi, bu esa ushbu tugunlarga kirish jarayonini sekinlashtiradi - ba'zida bu sezilarli sekinlashuvni anglatadi, ayniqsa ko'p sonli tugunlarni o'z ichiga olgan tuzilmalar holatida. Ko'pgina tuzilmalar uchun ba'zi tugunlar n-1 bosqichgacha bo'lgan eng yomon stsenariyni talab qilishi mumkin. Aksincha, ko'pgina massiv ma'lumotlar tuzilmalari kirishlar sonidan qat'iy nazar, doimiy miqdordagi operatsiyalarga ega bo'lgan har qanday elementga kirish imkonini beradi.
Umuman olganda, ushbu bog'liq ma'lumotlar tuzilmalari dinamik ma'lumotlar tuzilmalari yordamida amalga oshiriladi. Bu bizga ma'lum bir joydan qayta foydalanish imkoniyatini beradi. Ushbu ma'lumotlar tuzilmalari yordamida xotiradan yanada samarali foydalanish mumkin. Xotira kerak bo'lganda ajratiladi va xotira endi kerak bo'lmasa, u ajratiladi.
Umumiy kamchiliklar
Bog'langan ma'lumotlar tuzilmalari, shuningdek, xotirani sezilarli darajada taqsimlashi mumkin (agar tugunlar alohida ajratilgan bo'lsa) va xotira pagingi va keshlash algoritmlarini buzishi mumkin (chunki ular past mos yozuvlar joylashuviga ega). Ba'zi hollarda, bog'langan ma'lumotlar tuzilmalari raqobatdosh massiv tuzilmalariga qaraganda ko'proq xotiradan (mos yozuvlar maydonlari uchun) foydalanishi mumkin. Buning sababi, tegishli ma'lumotlar tuzilmalari bir-biriga yaqin emas. Ma'lumotlar namunalarini massivlardan farqli ravishda xotiraning hamma joyidan topish mumkin.
Massivlarda n-elementga darhol kirish mumkin, bog'langan ma'lumotlar strukturasida esa biz bir nechta ko'rsatkichlarga amal qilishimiz kerak, shuning uchun elementga kirish vaqti element strukturaning qayerda joylashganiga bog'liq.
Bog'langan tuzilmalarning cheklovlarini qo'llaydigan ba'zi nazariy hisoblash modellarida, masalan, ko'rsatgich mashinasi, ko'p vazifalar cheklanmagan tasodifiy kirish mashinasi modeliga qaraganda ko'proq qadamlarni talab qilad Ma'lumotlar strukturasi - bu bir xil turdagi va/yoki mantiqiy bog'liq ma'lumotlarni saqlash va qayta ishlash imkonini beruvchi dasturiy ta'minot birligi. Ma'lumotlarni qo'shish, qidirish, o'zgartirish va o'chirish uchun ma'lumotlar strukturasi uning interfeysini tashkil etuvchi ma'lum funktsiyalar to'plamini taqdim etadi.
"Ma'lumotlar tuzilishi" atamasi bir nechta yaqin, ammo shunga qaramay turli xil ma'nolarga ega bo'lishi mumkin[1]:
Mavhum ma'lumotlar turi;
Ayrim mavhum ma'lumotlar turini amalga oshirish;
Muayyan ro'yxat kabi ma'lumotlar turining namunasi;
Funktsional dasturlash kontekstida o'zgartirishlar kiritilganda saqlanadigan noyob identifikatsiya. Turli xil versiyalarning mavjudligiga qaramay, u norasmiy ravishda yagona ma'lumotlar tuzilmasi deb ataladi.
Ma'lumotlar tuzilmalari tanlangan dasturlash tilida ma'lumotlar turlari, havolalar va ular ustida operatsiyalar yordamida shakllantiriladi.
Har xil turdagi ma'lumotlar tuzilmalari turli ilovalarga mos keladi; ularning ba'zilari muayyan vazifalar uchun tor mutaxassislikka ega. Masalan, B-daraxtlar odatda ma'lumotlar bazalarini yaratish uchun mos keladi, xesh-jadvallar esa hamma joyda turli xil lug'atlarni yaratish uchun, masalan, domen nomlarini kompyuterning Internet manzillari bilan taqqoslash uchun ishlatiladi.
Dasturiy ta'minotni ishlab chiqishda dasturlarni amalga oshirishning murakkabligi va ish sifati sezilarli darajada ma'lumotlar tuzilmalarini to'g'ri tanlashga bog'liq. Ushbu tushuncha dasturiy ta'minot arxitekturasining birinchi qatoriga algoritmlarni emas, balki ma'lumotlar tuzilmalarini qo'yadigan rasmiy ishlab chiqish usullari va dasturlash tillarini keltirib chiqardi. Ushbu tillarning aksariyati ma'lumotlar tuzilmalarini turli ilovalarda xavfsiz tarzda qayta ishlatishga imkon beruvchi modullilik turiga ega. Java, C# va C++ kabi obyektga yoʻnaltirilgan tillar bu yondashuvga misol boʻla oladi.
Python 3. Standart tip hierarchy.png
Ko'pgina klassik ma'lumotlar tuzilmalari dasturlash tillarining standart kutubxonalarida taqdim etilgan yoki to'g'ridan-to'g'ri dasturlash tillariga kiritilgan. Masalan, xesh-jadval ma'lumotlar strukturasi Lua, Perl, Python, Ruby, Tcl va boshqalar dasturlash tillariga o'rnatilgan.C++ standart andozalar kutubxonasi (STL) keng qo'llaniladi.
Ko'pgina ma'lumotlar tuzilmalari uchun asosiy qurilish bloklari massivlar, yozuvlar (C-dagi tuzilma va Paskalda yozuv), diskriminatsiyalangan birlashmalar (C-da birlashma) va havolalardir. Masalan, ikki marta bog'langan ro'yxat yozuvlar va havolalar yordamida tuzilishi mumkin, bu erda har bir kirish (tugun) ma'lumotlar va "chap" va "o'ng" tugunlarga havolalarni saqlaydi.
Funktsional va imperativ dasturlashda ma'lumotlar tuzilmalarini solishtirish
Funktsional tillar uchun ma'lumotlar tuzilmalarini loyihalash kamida ikkita sababga ko'ra imperativ tillarga qaraganda qiyinroqdir[1]:
Deyarli barcha ma'lumotlar tuzilmalari sof funktsional uslubda ishlatilmaydigan topshiriqdan og'ir foydalanadi;
Funktsional ma'lumotlar tuzilmalari yanada moslashuvchan va shuning uchun imperativ dasturlashda eski versiya shunchaki yangisi bilan almashtirilganda yo'qolsa, funktsional dasturlashda u avtomatik ravishda mavjud bo'lib qoladi. Boshqacha qilib aytganda, imperativ dasturlashda (agar siz dasturni jiddiy ravishda murakkablashtirishi mumkin bo'lgan maxsus choralarni ko'rmasangiz) ma'lumotlar tuzilmalari efemer (inglizcha efemer), funktsional dasturlarda esa odatda doimiy (inglizcha persistent) bo'ladi.
ma'lumotlar strukturasi - o'zaro bog'liq o'zgaruvchilar va ularning qiymatlari to'plami
Har qanday ma'lumotlar strukturasining ikki tomoni bor. Jismoniy ma'lumotlar strukturasi uning "haqiqatan ham" ko'rinishidagi xotirada aks ettirilishidir. Mantiqiy ma'lumotlar strukturasi dasturiy ta'minot tomonidan yaratilgan uning majoziy, mavhum tasviridir. Bundan tashqari, ikkala tasvir ham o'z xususiyatlarining turli kombinatsiyalari bilan birga mavjud bo'lishi mumkin: bir o'lchovli - ikki o'lchovli, chiziqli - chiziqli bo'lmagan va boshqalar. Odatdagi misollar:
Mantiqiy tuzilma sifatida stek indeksli massiv - stek ko'rsatkichi va yakka bog'langan ro'yxat (jismoniy tasvir) asosida amalga oshirilishi mumkin;
· heapsort mantiqiy tuzilma uchun fizik tasvir darajasidagi massivdan foydalanadi - vertikal ravishda tartiblangan ikkita bolali daraxt (8.4);
· daraxtning fizik darajadagi eng yaqin tasviri - avlodlarga ko'rsatgichlar massiviga ega bo'lgan tugun ma'lumotlarning chiziqli strukturasini - mantiqiy ketma-ketlikni ifodalash uchun ishlatilishi mumkin (8.3).
3. Ma'lumotlar strukturasi sifatida ketma-ketlik
Ketma-ketlik - bir xil turdagi ixtiyoriy (o'zgaruvchan) o'lchamdagi o'zgaruvchilarning chiziqli tartiblangan to'plami ko'rinishidagi ma'lumotlarning mantiqiy tasviri. Ketma-ketlikdagi elementning tartib raqami uning mantiqiy raqamidir (LN). E'tibor bering, mantiqiy raqam elementning xususiyati emas, balki uni joylashtirish xususiyatidir, u ketma-ketlikda turli harakatlar bilan o'zgarishi mumkin. An'anaviy "janob" ketma-ketlikdagi operatsiyalar to'plami uning tartibiga bog'liq.
61.3. Ketma-ketlik bo'yicha operatsiyalar
Ketma-ketlikning jismoniy tasviri juda boshqacha bo'lishi mumkin, masalan, ro'yxat yoki berilgan o'tish ketma-ketligi bo'lgan daraxt. Ketma-ketlikni ifodalashning eng oddiy usulini ko'rib chiqing - uning elementlari massivning birinchi n elementini ("teshiklarsiz") egallaydi. Ketma-ket elementlarning joriy sonini aniqlashning ikki yo'li mavjud:
· qo'shimcha o'zgaruvchidan foydalaning - elementlar soni hisoblagichi;
· har safar ketma-ketlik oxirining belgisi sifatida maxsus ma'noga ega bo'lgan qo'shimcha elementni qo'shing - ketma-ketlik oxiri belgisi, masalan, nol ketma-ketlik chegaralagichi.
Massiv o'zgaruvchi sifatida bu erda zarur, lekin uni ma'lumotlar strukturasi - ketma-ketlik sifatida ko'rib chiqish uchun etarli emas. Bu, shuningdek, undagi qiymatlarni saqlash qoidalarini talab qiladi: ular ham uning boshlang'ich mazmuni, ham ketma-ketlik bilan xuddi massiv bilan ishlaydigan funktsiyalar bo'yicha aniqlanishi mumkin. Shunday qilib, massiv qo'shimcha "ma'no" ga ega bo'lib, u bilan ishlaydigan qismlarni maxsus tarzda izohlash imkonini beradi.
Muntazam ketma-ketlikdan elementlarni kiritish va chiqarish operatsiyalari manzilli - ular elementning mantiqiy (seriya) raqamidan foydalanadi. Agar ketma-ketlikni faqat uning uchlari bilan o'zgartirish imkoniyatlarini cheklasak, biz stek va navbat deb ataladigan ma'lumotlar tuzilmalarini olamiz.
Stack - ketma-ketlik, elementlarni kiritish va chiqarib tashlash faqat bir uchidan amalga oshiriladi
Ketma-ketlikning boshlanishi stekning pastki qismi, elementlar qo'shiladigan va olib tashlanadigan ketma-ketlikning oxiri stekning yuqori qismi deb ataladi. Yangi elementni qo'shish (stekga yozish) operatsiyasi umumiy qabul qilingan Push (yuklash) nomiga ega, istisno qilish operatsiyasi - Pop (otishma ovozi). Push va Pop operatsiyalari manzilsizdir, chunki ularni bajarish uchun elementlarning joylashuvi haqida qo'shimcha ma'lumotlar talab qilinmaydi.
Massivdagi stek ko'rinishi. Stack odatda stekning yuqori qismidagi ketma-ketlikning oxirgi elementi - stek ko'rsatkichi - SP - stek ko'rsatkichiga ishora qiluvchi qo'shimcha o'zgaruvchiga ega massiv sifatida taqdim etiladi.
//------------------------------------------------ ------61-01.cpp
// Massivdagi stack
intsp=-1;
void push(int vv){ if (sp!=SZ-1) A[++sp]=vv; }
int pop(){ qaytar sp==-1? 0 : A[sp--]; }
int get(int k){ qaytar sp-k<0? 0 : A[sp-k]; }
Stackning yana bir muhim xususiyati uning elementlarining nisbiy adreslanishidir. Darhaqiqat, stekda saqlangan element uchun uning ketma-ketlikdagi mutlaq pozitsiyasi emas, balki stekning yuqori qismiga yoki uning toʻldirish “tarixini” aks ettiruvchi koʻrsatkichga nisbatan pozitsiyasi muhim ahamiyatga ega. Shuning uchun stek elementlari stek ko'rsatkichining joriy qiymatiga (get funktsiyasi) nisbatan murojaat qilinadi.
Dasturlashda stek xususiyatlaridan foydalanish. Dasturlashda stekning juda mashhurligi shundan iboratki, stekga elementlarni yozishning berilgan ketma-ketligi (masalan, A-B-C), ular teskari tartibda (C-B-A) olinadi. Ya'ni, bunday harakatlar ketma-ketligi funktsiya chaqiruvlarini joylashtirish, til konstruksiyalari ta'riflarini joylashtirish, uzilishlar va boshqalar kabi tushunchalarga mos keladi. Shuning uchun biz jarayonlar, tuzilmalar, ta'riflarni joylashtirish haqida gap ketganda, hamma joyda uni amalga oshirish mexanizmi mavjud. to'plam:
· funksiya chaqirilganda qaytish manzili (chaqiriqdan keyingi buyruqning manzili) stekda saqlanadi, shu bilan teskari tartibda qayta tiklanishi mumkin bo‘lgan funksiya chaqiruvlarining “tarixi” hosil bo‘ladi;
· ichki o'rnatilgan til konstruksiyalarini tahlil qilishda tarjimonlar pastga surish (stek) avtomatlaridan foydalanadilar, stek esa to'liq tahlil qilinmagan til konstruksiyalarini o'z ichiga oladi.
Ma'lumotlar stekda qanday saqlanishi haqida umumiy atama mavjud - LIFO (oxirgi kir - birinchi chiqadi - oxirgi kiruvchi, birinchi chiqadi).
Deyarli barcha kompyuterlarning arxitekturasi apparat stackidan foydalanadi. Bu kompyuterning ichki (RAM) xotirasining oddiy maydoni bo'lib, u bilan maxsus registr ishlaydi - stek ko'rsatkichi. Uning yordamida protsessor turli o'lchamdagi baytlar va mashina so'zlari to'plamidan saqlash va tiklash uchun Push va Pop operatsiyalarini bajarishi mumkin.
Uskunalar stegi va ko'rib chiqilayotgan model o'rtasidagi yagona farq uning tom ma'noda "teskari" joylashishi, ya'ni uni yuqori manzillardan past manzillarga to'ldirishdir, dastlab stek ko'rsatkichi ajratilgan xotira maydonining "yuqori" ni anglatadi. Tarixiy holatlar quyidagilardan iborat: dasturda xotirani taqsimlashning eng oddiy variantlarida buyruq segmentlari, statik ma'lumotlar xotiraning "boshidan" boshlab joylashtirildi va ularning ustida dinamik xotira segmenti "o'sdi", shuning uchun stek bor edi. boshqa uchidan boshlab joylashtirilishi kerak, ya'ni. "ostin-ustin".
| 