• Funksiya
  • Reja: Bog’langan ro’yxat nima? Yagona va ikki bog’langan ro’yxatlar Chiziqli bog’langan ro’yxatlar Bog'langan ro'yxat




    Download 25.61 Kb.
    bet2/4
    Sana01.11.2023
    Hajmi25.61 Kb.
    #92548
    1   2   3   4
    Bog'liq
    malumot
    Kiber xafsizlik, Mustaqil ta2022 й (3)
    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.
    Funksiya insertAfter (Tugun tugun, Tugun newNode) // tugundan keyin newNode joylashtiring newNode.next: = node.next node.next: = newNode
    Ro'yxatning boshiga qo'shish alohida funktsiyani talab qiladi. Bu yangilanishni talab qiladi birinchi tugun.
    Funksiya insertBeginning (Ro'yxat ro'yxat, Tugun newNode) // joriy birinchi tugundan oldin tugunni joylashtiring newNode.next: = list.firstNode list.firstNode: = newNode
    Xuddi shunday, bizda tugunni olib tashlash funktsiyalari mavjud keyin berilgan tugun va ro'yxatni boshidan tugunni olib tashlash uchun. Diagramma avvalgisini namoyish etadi. Muayyan tugunni topish va olib tashlash uchun avvalgi elementni yana kuzatib borish kerak.

    Funksiya removeAfter (Tugun tugun) // tugundan oldingi tugunni olib tashlang obsoleteNode: = node.next node.next: = node.next.next eskirgan tugunni yo'q qilish
    Funksiya olib tashlashBeginning (Ro'yxat ro'yxat) // birinchi tugunni olib tashlash eskirganNode: = list.firstNode list.firstNode: = list.firstNode.next // o'chirilgan tugundan o'tmish eskirgan tugunni yo'q qilish
    E'tibor bering removeBeginning () to'plamlar list.firstNode ga bekor ro'yxatdagi so'nggi tugunni olib tashlashda.
    Biz orqaga qaytishimiz mumkin emasligi sababli oldin yoki olib tashlashdan oldin operatsiyalarni amalga oshirish mumkin emas. Ro'yxatga ma'lum bir tugundan oldin qo'shilish uchun ro'yxatdan o'tishni talab qiladi, bu eng yomon ish vaqti O (n) bo'ladi.
    Ro'yxat tuzilmasining bir qismi sifatida dumga havola qilinmasa, bitta bog'langan ro'yxatni boshqasiga qo'shish samarasiz bo'lishi mumkin, chunki biz dumini topish uchun butun birinchi ro'yxatni bosib o'tib, so'ngra ikkinchi ro'yxatni bunga qo'shishimiz kerak. Shunday qilib, agar ikkita chiziqli bog'langan ro'yxat har birining uzunligi bo'lsa , ro'yxat qo'shilishi mavjud asimptotik vaqt murakkabligi ning . Lisp tillar oilasida ro'yxat qo'shilishi qo'shib qo'ying protsedura.
    Bog'langan ro'yxat operatsiyalarining ko'pgina maxsus holatlarini ro'yxatning old qismiga qo'g'irchoq element kiritish orqali yo'q qilish mumkin. Bu ro'yxat boshlanishi uchun maxsus holatlar mavjud emasligini ta'minlaydi va ikkalasini ham ko'rsatadi insertBeginning () va removeBeginning () keraksiz. Bunday holda, ro'yxatdagi birinchi foydali ma'lumotlar bu erda topiladi ro'yxat.
    Algoritmlar
    Buni taxmin qilaylik someNode - bu bo'sh bo'lmagan doiraviy yakka bog'langan ro'yxatdagi ba'zi bir tugunlar, bu kod ushbu ro'yxat bilan boshlanib takrorlanadi 

    Download 25.61 Kb.
    1   2   3   4




    Download 25.61 Kb.

    Bosh sahifa
    Aloqalar

        Bosh sahifa



    Reja: Bog’langan ro’yxat nima? Yagona va ikki bog’langan ro’yxatlar Chiziqli bog’langan ro’yxatlar Bog'langan ro'yxat

    Download 25.61 Kb.