Иккинчи индексни шакллантиришнинг бир қанча усуллари мавжуд: - Иккинчи индексни шакллантиришнинг бир қанча усуллари мавжуд:
1.zanjirlar usuli(тўғридан-тўғри боғлаш (direct chaining) , tashqi yoki ochiq heshlashtirish) 2.Ochiq adreslash( yopiq heshlashtirish) 1-usul - Энг содда йўлларидан бири бу – биринчи H(k) индекслари бир ҳил бўлган барча қаторни бир-бирига боғлаш, яъни боғланган рўйхат каби. Ҳосил бўлган рўйхат элементлари асосий жадвалда жойлашиши ҳам, жойлашмаслиги ҳам мумкин. i –pozitsiyada hesh –qiymatlari bitta i qiymatga teng bo’lgan elementlar ro’yhatining boshi ga ko’rsatkich saqlanadi. - i –pozitsiyada hesh –qiymatlari bitta i qiymatga teng bo’lgan elementlar ro’yhatining boshi ga ko’rsatkich saqlanadi.
Agar bunday elementlar yoq bo’lsa, i- pozitsiyaga NULL yoziladi. Бундай ҳолатда рўйхат элементлари жойлашган хотира тўлалик (тўлиб- тошиш, переполнение) соҳаси дейилади. - Бундай ҳолатда рўйхат элементлари жойлашган хотира тўлалик (тўлиб- тошиш, переполнение) соҳаси дейилади.
- 2-usul- da esа берилган жадвални берилган қаторида керакли элемент мавжуд бўлмаса, токи керакли элемент топилгунча ёки бўш қаторга боргунча бошқа қаторларини кўриб чиқилади.
Masalan - Masalan
- Klyuch 002 ga 2ta qiymat davogar bo’layapti, ulardan biriga dastlabki topilgan bo’sh joy topiladi/
Агар қараб чиқиш бўш қаторгача бориб етса, у ҳолда кўрсатилган калит берилган жадвалда йўқ деб ҳисобланади. - Агар қараб чиқиш бўш қаторгача бориб етса, у ҳолда кўрсатилган калит берилган жадвалда йўқ деб ҳисобланади.
- Табиийки, ихтиёрий берилган калит учун индекслар кетма-кетлиги иккинчи уринишда бир ҳил бўлиши лозим. Бундай ҳолатда қараб (кўриб) чиқиш алгоритми қуйидаги схемада ишлайди:
h = H(k) i = 0 repeat - h = H(k) i = 0 repeat
- if T(h) = k
- then элемент топилди
- else if T(h) = free
- then элемент жадвалда йўк
- else {зиддият} i := i + 1
- h := H(k) + G(i)
- endif endif
- until топилди, ёки жадвалда йўқ.
Do'stlaringiz bilan baham: |