Kas yra praleidimo sąrašas?

Praleidžiamasis sąrašas yra tikimybinė duomenų struktūra. Praleidžiamasis sąrašas naudojamas surūšiuotam elementų ar duomenų sąrašui su susietu sąrašu saugoti. Tai leidžia efektyviai peržiūrėti elementų ar duomenų procesą. Vienu žingsniu jis praleidžia kelis viso sąrašo elementus, todėl jis vadinamas praleidimo sąrašu.

Praleidžiamasis sąrašas yra išplėstinė susieto sąrašo versija. Tai leidžia vartotojui labai greitai ieškoti, pašalinti ir įterpti elementą. Jį sudaro pagrindinis sąrašas, kuriame yra elementų rinkinys, kuris palaiko tolesnių elementų nuorodų hierarchiją.

Praleisti sąrašo struktūrą

Jis yra dviejų sluoksnių: apatinis sluoksnis ir viršutinis sluoksnis.

Žemiausias praleidžiamo sąrašo sluoksnis yra įprastas surūšiuotas susietas sąrašas, o viršutiniai praleisto sąrašo sluoksniai yra tarsi „greitinė eilutė“, kurioje elementai praleidžiami.

Praleisti sąrašo sudėtingumo lentelė

Praleisti sąrašo veikimas

Paimkime pavyzdį, kad suprastume praleisto sąrašo veikimą. Šiame pavyzdyje turime 14 mazgų, todėl šie mazgai yra padalinti į du sluoksnius, kaip parodyta diagramoje.

Apatinis sluoksnis yra bendra linija, jungianti visus mazgus, o viršutinis sluoksnis yra greitoji linija, jungianti tik pagrindinius mazgus, kaip matote diagramoje.

Tarkime, kad šiame pavyzdyje norite rasti 47. Pradėsite paiešką nuo pirmojo greitosios eilutės mazgo ir toliau vykdysite greitąją eilutę, kol rasite mazgą, kuris yra lygus 47 arba didesnis nei 47.

Pavyzdyje matote, kad 47 greitojoje eilutėje nėra, todėl ieškote mazgo, mažesnio nei 47, o tai yra 40. Dabar eikite į įprastą eilutę naudodami 40 ir ieškote 47, kaip parodyta diagramoje.

Pastaba: radę tokį mazgą „greičiausioje eilutėje“, iš šio mazgo pereinate į „įprastą juostą“ naudodami žymeklį ir kai ieškote mazgo įprastoje eilutėje.

Praleisti sąrašą pagrindinės operacijos

Praleidimo sąraše yra šių tipų operacijos.

Įdėjimo operacija:Jis naudojamas norint pridėti naują mazgą į tam tikrą vietą konkrečioje situacijoje.Ištrynimo operacija:Jis naudojamas norint ištrinti mazgą konkrečioje situacijoje.Paieškos operacija:Paieškos operacija naudojama ieškant konkretaus mazgo praleidimo sąraše.

Įterpimo operacijos algoritmas

 Insertion (L, Key) local update [0...Max_Level + 1] a = L → header for i = L → level down to 0 do. while a → forward[i] → key forward[i] update[i] = a a = a → forward[0] lvl = random_Level() if lvl > L → level then for i = L → level + 1 to lvl do update[i] = L → header L → level = lvl a = makeNode(lvl, Key, value) for i = 0 to level do a → forward[i] = update[i] → forward[i] update[i] → forward[i] = a 

Ištrynimo operacijos algoritmas

 Deletion (L, Key) local update [0... Max_Level + 1] a = L → header for i = L → level down to 0 do. while a → forward[i] → key forward[i] update[i] = a a = a → forward[0] if a → key = Key then for i = 0 to L → level do if update[i] → forward[i] ? a then break update[i] → forward[i] = a → forward[i] free(a) while L → level > 0 and L → header → forward[L → level] = NIL do L → level = L → level - 1 

Paieškos operacijos algoritmas

 Searching (L, SKey) a = L → header loop invariant: a → key level down to 0 do. while a → forward[i] → key forward[i] a = a → forward[0] if a → key = SKey then return a → value else return failure 

1 pavyzdys: Sukurkite praleidimo sąrašą, norime įterpti šiuos raktus į tuščią praleidimo sąrašą.

1. 6 su 1 lygiu.
2. 29 su 1 lygiu.
3. 22 su 4 lygiu.
4. 9 su 3 lygiu.
5. 17 su 1 lygiu.
6. 4 su 2 lygiu.

Metai:

1 žingsnis: Įdėkite 6 su 1 lygiu

2 žingsnis: Įdėkite 29 su 1 lygiu

3 veiksmas: Įdėkite 22 su 4 lygiu

4 veiksmas: Įdėkite 9 su 3 lygiu

5 veiksmas: Įdėkite 17 su 1 lygiu

6 veiksmas: Įdėkite 4 su 2 lygiu

2 pavyzdys: Apsvarstykite šį pavyzdį, kuriame norime ieškoti 17 rakto.

Metai:

Praleisti sąrašo pranašumai

1. Jei norite įterpti naują mazgą į praleidimo sąrašą, jis įterps mazgą labai greitai, nes praleidimo sąraše nėra sukimų.
2. Praleidimo sąrašą paprasta įdiegti, palyginti su maišos lentele ir dvejetainiu paieškos medžiu.
3. Sąraše labai paprasta rasti mazgą, nes jame mazgai saugomi surūšiuota forma.
4. Praleidžiamo sąrašo algoritmą galima labai lengvai modifikuoti konkretesnėje struktūroje, pavyzdžiui, indeksuojamuose praleidžiamuose sąrašuose, medžiuose ar prioritetinėse eilėse.
5. Praleidžiamasis sąrašas yra tvirtas ir patikimas.

Praleisti sąrašo trūkumai

1. Tam reikia daugiau atminties nei subalansuotam medžiui.
2. Atvirkštinė paieška neleidžiama.
3. Praleidžiamajame sąraše mazgas ieškoma daug lėčiau nei susietame sąraše.

Praleisti sąrašo programos

1. Jis naudojamas paskirstytose programose ir atspindi nuorodas ir sistemą paskirstytose programose.
2. Jis naudojamas dinaminei elastinei lygiagrečiai eilei įgyvendinti su mažu užrakto varžymu.
3. Jis taip pat naudojamas su QMap šablonų klase.
4. Praleidžiamo sąrašo indeksavimas naudojamas atliekant vidutines problemas.
5. Praleidžiamasis sąrašas naudojamas delta kodavimo įrašymui Lucene paieškoje.