Chiziqli bog'langan ma'lumotlar

Chiziqli bog'langan ma'lumotlar Reja: Bog'langan ro'yxat nima? Yagona va ikki bog'langan ro'yxatlar Chiziqli bog'langan ro'yxatlar Bog'langan ro'yxat nima? Bog'langan ro'yxat xotirada jismoniy joylashuvi bilan buyurtma berilmagan ma'lumotlar elementlarining chiziqli to'plamidir. Buning o'rniga, har bir element ochkolar keyingisiga. Bu ma'lumotlar tuzilishi to'plamidan iborat tugunlar birgalikda a ni ifodalaydi ketma-ketlik. Eng asosiy shaklida har bir tugun quyidagilarni o'z ichiga oladi: ma'lumotlar va a ma'lumotnoma (boshqacha qilib aytganda, a havola) ketma-ketlikning keyingi tuguniga. Ushbu struktura takrorlash paytida ketma-ket har qanday pozitsiyadan elementlarni samarali kiritish yoki olib tashlashga imkon beradi. Keyinchalik murakkab variantlar qo'shimcha havolalarni qo'shib, o'zboshimchalik holatida tugunlarni yanada samarali kiritish yoki olib tashlashga imkon beradi. Bog'langan ro'yxatlarning kamchiliklari shundaki, kirish vaqti chiziqli (va qiyin) quvur liniyasi ). Tasodifiy kirish kabi tezroq kirish mumkin emas. Bog'langan ro'yxatlar eng sodda va eng keng tarqalgan ma'lumotlar tuzilmalaridan biridir. Ular bir nechta boshqa keng tarqalgan dasturlarni amalga oshirish uchun ishlatilishi mumkin mavhum ma'lumotlar turlari, shu jumladan ro'yxatlar, vayronalar, navbat, assotsiativ massivlar va S-iboralar Ushbu ma'lumotlar tuzilmalarini to'g'ridan-to'g'ri bog'langan ro'yxatni asos sifatida ishlatmasdan amalga oshirish odatiy holdir. Bog'langan ro'yxatning odatdagidan ko'ra asosiy foydasi qator ro'yxat elementlari osongina kiritilishi yoki olib tashlanishi mumkin, chunki butun tuzilmani qayta taqsimlamasdan yoki qayta tashkil qilmasdan, chunki ma'lumotlar elementlarini saqlash kerak emas tutashgan holda qatorini qayta tuzishda xotirada yoki diskda ish vaqti juda qimmat operatsiya. Bog'langan ro'yxatlar ro'yxatning istalgan nuqtasida tugunlarni kiritishga va olib tashlashga imkon beradi va buni doimiy ravishda operatsiyalar soni bilan amalga oshirishga imkon beradi, chunki havolaga avvalgi havolani qo'shish yoki o'chirish ro'yxati o'tish paytida xotirada saqlanadi. Bog'langan ro'yxatning har bir yozuvi ko'pincha element yoki tugun '. 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 ...