Mustaqil ishi mavzu: Chiziqli bog’langan ma’lumotlar

Yagona bog'langan ro'yxat
Yagona bog'langan ro'yxatlarda ma'lumotlar maydoniga ega tugunlar va shuningdek "keyingi" maydon mavjud bo'lib, ular tugunlar qatoridagi keyingi tugunga ishora qiladi. Alohida bog'langan ro'yxatlar bo'yicha bajarilishi mumkin bo'lgan operatsiyalarga qo'shish, o'chirish va o'tish kiradi.

Quyidagi kod yakka bog'langan ro'yxat oxiriga ma'lumotlar "qiymati" bilan yangi tugunni qanday qo'shishni namoyish etadi:

tugun addNode(tugun bosh, int qiymat) { tugun temp, p; // temp va p ikkita tugunni e'lon qiling temp = createNode(); // assume createNode = 0 bo'lgan yangi tugunni yaratadi va keyin NULL-ga ishora qiladi. temp->ma'lumotlar = qiymat; // tugunning ma'lumotlar qismiga element qiymatini qo'shing agar (bosh == NULL) { bosh = temp; // bog'langan ro'yxat bo'sh bo'lganda } boshqa { p = bosh; // boshni p ga belgilang esa (p->Keyingisi != NULL) { p = p->Keyingisi; // p oxirgi tugun bo'lguncha ro'yxatni kesib o'ting. Oxirgi tugun har doim NULL-ga ishora qiladi. } p->Keyingisi = temp; // Oldingi so'nggi tugunni yaratilgan yangi tugunga yo'naltiring. } qaytish bosh;}
Ikki marta bog'langan ro'yxat
"Ikki marta bog'langan ro'yxat" da har bir tugun keyingi tugun havolasidan tashqari ketma-ketlikdagi "oldingi" tugunga ishora qiluvchi ikkinchi havola maydonini o'z ichiga oladi. Ikkala havola "oldinga" (lar) va "orqaga" yoki "keyingi" va "oldingi" ("oldingi") deb nomlanishi mumkin.



Bog'langan ro'yxatlar va dinamik massivlar

Ro'yxat ma'lumotlar tuzilmalarini taqqoslash
	Bog'langan ro'yxat	Array	Dinamik qator	Balansli daraxt	Tasodifiy kirish ro'yxati	Massa daraxti
Indekslash	Θ (n)	Θ (1)	Θ (1)	Θ (log n)	Θ (log n)^[4]	Θ (1)
Qo'shish / o'chirish boshida	Θ (1)	Yo'q	Θ (n)	Θ (log n)	Θ (1)	Θ (n)
Qo'shish / o'chirish oxirida	Θ (1) oxirgi bo'lganda element ma'lum; Θ (n) qachon oxirgi element noma'lum	Yo'q	Θ (1) amortizatsiya qilingan	Θ (log.) n)	Yo'q ^[4]	Θ (1) amortizatsiya qilingan
Qo'shish / o'chirish o'rtada	qidirish vaqti + Θ (1)^[5][6]	Yo'q	Θ (n)	Θ (log.) n)	Yo'q ^[4]	Θ (n)
Bo'sh joy (o'rtacha)	Θ (n)	0	Θ (n)^[7]	Θ (n)	Θ (n)	Θ (√n)

Bog'langan ro'yxatlar dinamik massivlarga nisbatan bir qancha afzalliklarga ega. Ro'yxatning ma'lum bir nuqtasida elementni qo'shish yoki o'chirish, agar biz indikatorni tugunga indeksatsiya qilgan deb hisoblasak (o'chirilishi kerak bo'lganidan oldin yoki qo'shilish joyidan oldin) doimiy ish (aks holda bu holda) u O (n)) ga ishora qiladi, ammo tasodifiy joylarda dinamik qatorga qo'shish o'rtacha elementlarning yarmini va eng yomon holatda barcha elementlarni harakatlantirishni talab qiladi. Biror narsani "bo'sh" deb belgilash orqali doimiy ravishda massivdan elementni "o'chirish" mumkin, ammo bu sabab bo'ladi parchalanish bu takrorlashni bajarishga xalaqit beradi. Bog'langan ro'yxatlarning yana bir kamchiliklari - bu havolalar uchun zarur bo'lgan qo'shimcha joy, bu ularni ko'pincha kichik ma'lumotlar elementlari ro'yxati uchun amaliy emas qiladi. belgilar yoki mantiqiy qiymatlar, chunki havolalarni saqlash xarajatlari ma'lumotlar hajmidan ikki yoki undan ko'p marta oshishi mumkin. Aksincha, dinamik qator faqat ma'lumotlarning o'zi uchun bo'sh joyni talab qiladi (va juda oz miqdordagi boshqaruv ma'lumotlari). Bog'langan ro'yxatlarga nisbatan dinamik massivlardan foydalanishning ijobiy va salbiy tomonlarini ta'kidlaydigan yaxshi misol - bu echimini topadigan dasturni amalga oshirishdir. Jozefus muammosi. Jozefus muammosi - bu bir guruh odamlarni aylanada turishi bilan ishlaydigan saylov usuli. Oldindan belgilangan odamdan boshlab, aylana atrofida hisoblash mumkin n marta. Bir marta nUchinchi shaxsga etib boring, ularni doiradan olib tashlashingiz va a'zolarni doirani yopishingiz kerak. Jarayon faqat bitta odam qolguncha takrorlanadi. O'sha kishi saylovda g'olib chiqadi. Bu bog'langan ro'yxatning kuchli va zaif tomonlarini dinamik qatorga nisbatan ko'rsatadi, chunki agar odamlar dumaloq bog'langan ro'yxatdagi bog'langan tugunlar sifatida ko'rilsa, u holda bog'langan ro'yxat tugunlarni o'chirishga qodirligini ko'rsatadi (chunki bu faqat kerak havolalarni turli tugunlarga qayta o'rnating). Biroq, bog'langan ro'yxat olib tashlash uchun keyingi odamni topishda yomon bo'ladi va shu odam topilmaguncha ro'yxatni qidirishi kerak. Boshqa tomondan, dinamik massiv tugunlarni (yoki elementlarni) o'chirishda yomon bo'ladi, chunki u bitta elementni ro'yxatdagi barcha elementlarni alohida-alohida o'zgartirmasdan bitta tugunni olib tashlay olmaydi. Biroq, ni topish juda oson nularni to'g'ridan-to'g'ri massivdagi mavqei bilan murojaat qilish orqali doiradagi odam. Ikki marta bog'langan va dumaloq ro'yxatlarning birma-bir bog'langan chiziqli ro'yxatlarga nisbatan afzalliklari bo'lsa, chiziqli ro'yxatlar ba'zi afzalliklarga ega bo'lib, ularni ba'zi holatlarda afzal ko'radi.
Alohida bog'langan chiziqli ro'yxat a rekursiv ma'lumotlar tuzilishi, chunki u a uchun ko'rsatkichni o'z ichiga oladi kichikroq bir xil turdagi ob'ekt. Shu sababli, bir-biriga bog'langan chiziqli ro'yxatlar bo'yicha ko'plab operatsiyalar (masalan birlashma ikkita ro'yxat yoki elementlarni teskari tartibda sanash) ko'pincha juda oddiy rekursiv algoritmlarga ega, bu har qanday echimdan ancha sodda takroriy buyruqlar. Ushbu rekursiv echimlar ikki tomonlama bog'langan va doiraviy bog'langan ro'yxatlar uchun moslashtirilishi mumkin bo'lsa-da, protseduralar odatda qo'shimcha dalillarga va murakkabroq asosiy holatlarga muhtoj.
Yagona bog'langan ro'yxatlar ham ruxsat beradi dumini bo'lishish, sub-listning umumiy yakuniy qismidan ikki xil ro'yxatning terminal qismi sifatida foydalanish. Xususan, agar ro'yxatning boshiga yangi tugun qo'shilsa, avvalgi ro'yxat yangisining dumi sifatida mavjud bo'lib qoladi - bu oddiy misol doimiy ma'lumotlar tuzilishi. Shunga qaramay, bu boshqa variantlar bilan to'g'ri kelmaydi: tugun hech qachon ikki xil yoki ikki marta bog'langan ro'yxatlarga tegishli bo'lishi mumkin emas.
Xususan, so'nggi sentinel tugunlari bir-biriga bog'langan aylana bo'lmagan ro'yxatlar o'rtasida taqsimlanishi mumkin. Xuddi shu so'nggi qo'riqchi tugun uchun ishlatilishi mumkin har bir bunday ro'yxat. Yilda Lisp Masalan, har bir to'g'ri ro'yxat maxsus tugunga havola bilan tugaydi nol yoki (), kimning MOSHINA va CDR ishoratlar o'ziga ishora qiladi. Shunday qilib, Lisp protsedurasi xavfsiz tarzda amalga oshirilishi mumkin MOSHINA yoki CDR ning har qanday ro'yxat.
Xayoliy variantlarning afzalliklari ko'pincha algoritmlarning samaradorligi bilan emas, balki murakkabligi bilan cheklanadi. Dairesel ro'yxat, xususan, odatda chiziqli ro'yxat bilan birinchi va oxirgi tugunlarni ko'rsatadigan ikkita o'zgaruvchiga qo'shimcha ravishda bepul taqlid qilish mumkin.