Sentinelový uzel - Sentinel node

tento článek ne uvést žádný Zdroje. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Sentinelový uzel"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Leden 2016) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Tento článek může vyžadovat vyčištění setkat se s Wikipedií standardy kvality. Specifický problém je: Shrnutí může být stručnější Prosím pomozte vylepšit tento článek jestli můžeš. (Leden 2016) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

V počítačovém programování, a sentinelový uzel je konkrétně určen uzel použitý s propojené seznamy a stromy jako terminátor traverzové cesty. Tento typ uzlu nedrží ani neodkazuje na žádná data spravovaná datovou strukturou.

Výhody

Sentinely se používají jako alternativa k použití NULA jako terminátor cesty za účelem získání jedné nebo více z následujících výhod:

• Okrajově zvýšila rychlost operací
• Zvýšená datová struktura robustnost (pravděpodobně)

Nevýhody

• Okrajově zvýšila složitost algoritmu a velikost kódu.
• Pokud je přístup k datové struktuře současně (což znamená, že všechny přístupové uzly musí být chráněny alespoň pro "pouze ke čtení" ), pro implementaci založenou na sentinel musí být sentinel uzel chráněn pro „čtení a zápis“ pomocí a mutex. Tento extra mutex v několika scénářích použití může způsobit vážné snížení výkonu^[1]. Jedním ze způsobů, jak se tomu vyhnout, je ochrana struktury seznamu jako celku pro „čtení a zápis“, zatímco ve verzi s NULA stačí chránit datovou strukturu jako celek pro „jen pro čtení“ (pokud nebude následovat operace aktualizace).
• Koncept sentinel není užitečný pro záznam datové struktury na disk.

Příklady

Vyhledávání

Níže jsou uvedeny dvě verze podprogramu (implementovaného v Programovací jazyk C. ) pro vyhledání dané vyhledávací klávesy v a jednotlivě propojený seznam. První používá sentinelová hodnota NULAa druhý a (ukazatel na) sentinelový uzel Stráž, jako indikátor konce seznamu. Deklarace jednotlivě propojené datové struktury seznamu a výsledky obou podprogramů jsou stejné.

struktur sll_node {                          // jeden uzel jednotlivě propojeného seznamu   int klíč;   struktur sll_node *další;                  // indikátor konce seznamu nebo -> další uzel} sll, *První;

První verze používající NULL jako indikátor konce seznamu

 1 // globální inicializace 2 První = NULA;                              // před prvním vložením (nezobrazeno) 3  4 struktur sll_node *Vyhledávání(struktur sll_node *První, int vyhledávací_klíč) { 5     struktur sll_node *uzel; 6     pro (uzel = První;  7         uzel != NULA; 8         uzel = uzel->další) 9     {10         -li (uzel->klíč == vyhledávací_klíč)11             vrátit se uzel;                   // nalezeno12     }13     // nenalezeno14     vrátit se NULA;15 }

The pro-loop obsahuje dva testy (žluté čáry) na iteraci:

• uzel! = NULL;
• if (node-> key == search_key).

Druhá verze využívající ověřovací uzel

Globálně dostupný ukazatel stráž na záměrně připravenou datovou strukturu Stráž se používá jako indikátor konce seznamu.

 1 // globální proměnná 2 sll_node Stráž, *stráž = &Stráž; 3 // globální inicializace 4 stráž->další = stráž; 5 První = stráž;                          // před prvním vložením (nezobrazeno) 6 // Všimněte si, že indikátor sentinel musí být vždy udržován na KONCI seznamu. 7  8 struktur sll_node *SearchWithSentinelnode(struktur sll_node *První, int vyhledávací_klíč) { 9     struktur sll_node *uzel;10     stráž->klíč = vyhledávací_klíč;11     pro (uzel = První; 12         uzel->klíč != vyhledávací_klíč;13         uzel = uzel->další)14     {15     }16     -li (uzel != stráž)17         vrátit se uzel;                       // nalezeno18     // nenalezeno19     vrátit se NULA;20 }

The pro-loop obsahuje pouze jeden test (žlutá čára) na iteraci:

• uzel-> klíč! = vyhledávací_klíč;.

Implementace propojeného seznamu

Implementace propojeného seznamu, zejména jedna z kruhového, dvojnásobně propojeného seznamu, lze pozoruhodně zjednodušit pomocí ověřovacího uzlu k vymezení začátku a konce seznamu.

• Seznam začíná jediným uzlem, sentinelovým uzlem, který má následující a předchozí ukazatele na sebe. Tato podmínka určuje, zda je seznam prázdný.
• V neprázdném seznamu dává hlavní ukazatel seznamu další ukazatel sentinelového uzlu a předchozí ukazatel dává konec seznamu.

Následuje implementace kruhového seznamu dvojnásobně propojeného seznamu v Pythonu:

třída Uzel:    def __init__(já, data, další=Žádný, předchozí=Žádný) -> Žádný:        já.data = data        já.další = další        já.předchozí = předchozí    def __repr__(já) -> str:        vrátit se 'Uzel (data ={})'.formát(já.data)třída Spojový seznam:    def __init__(já) -> Žádný:        já._stráž = Uzel(data=Žádný)        já._stráž.další = já._stráž        já._stráž.předchozí = já._stráž    def pop_left(já):        vrátit se já.remove_by_ref(já._stráž.další)    def pop(já):        vrátit se já.remove_by_ref(já._stráž.předchozí)    def append_nodeleft(já, uzel) -> Žádný:        já.add_node(já._stráž, uzel)    def append_node(já, uzel -> Žádný):        já.add_node(já._stráž.předchozí, uzel)    def append_left(já, data) -> Žádný:        uzel = Uzel(data=data)        já.append_nodeleft(uzel)    def připojit(já, data) -> Žádný:        uzel = Uzel(data=data)        já.append_node(uzel)    def remove_by_ref(já, uzel):        -li uzel je já._stráž:            vyzdvihnout Výjimka("Nikdy nemůžu odstranit hlídku.")        uzel.předchozí.další = uzel.další        uzel.další.předchozí = uzel.předchozí        uzel.předchozí = Žádný        uzel.další = Žádný        vrátit se uzel    def add_node(já, kotelna, novinka) -> Žádný:        novinka.další = kotelna.další        novinka.předchozí = kotelna        kotelna.další.předchozí = novinka        kotelna.další = novinka    def Vyhledávání(já, hodnota):        já._stráž.data = hodnota        uzel = já._stráž.další        zatímco uzel.data != hodnota:            uzel = uzel.další        já._stráž.data = Žádný        -li uzel je já._stráž:            vrátit se Žádný        vrátit se uzel    def __iter__(já):        uzel = já._stráž.další        zatímco uzel je ne já._stráž:            výtěžek uzel.data            uzel = uzel.další    def reviter(já):        uzel = já._stráž.předchozí        zatímco uzel je ne já._stráž:            výtěžek uzel.data            uzel = uzel.předchozí

Všimněte si, jak add_node () metoda vezme uzel, který bude posunut novým uzlem v parametru kotelna. Pro připojení doleva je to hlava neprázdného seznamu, zatímco pro připojení doprava je to ocas. Ale kvůli tomu, jak je propojení nastaveno tak, aby odkazovalo zpět na sentinel, kód funguje i pro prázdné seznamy, kde kotelna bude sentinelovým uzlem.

Viz také

• Hodnota hlídky
• Magické číslo (programování)
• Magická struna
• Vzor nulového objektu
• Chyby při formátování a ukládání času
• Slon v Káhiře
• Kanárská hodnota
• Semipredikátový problém

Reference

Tento programování související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.