Sentinel nod

Den här artikeln handlar om datorprogrammeringskonstruktionen. För kroppsdelen, se Sentinel lymfkörtel .
Ej att förväxla med sentinelvärde .

Inom datorprogrammering är en sentinel-nod en specifikt designad nod som används med länkade listor och träd som en terminator för genomgångsväg. Denna typ av nod innehåller eller refererar inte till någon data som hanteras av datastrukturen.

Fördelar

Sentinels används som ett alternativ framför att använda NULL som sökvägsavslutare för att få en eller flera av följande fördelar:

  • Marginellt ökad hastighet i verksamheten
  • Ökad datastruktur robusthet (förmodligen)

Nackdelar

  • Marginellt ökad algoritmisk komplexitet och kodstorlek.
  • Om datastrukturen nås samtidigt (vilket innebär att alla noder som nås måste skyddas åtminstone för "read-only" ), för en sentinelbaserad implementering måste sentinelnoden skyddas för "läs-skriva" av en mutex . Denna extra mutex i ganska många användningsscenarier kan orsaka allvarlig prestandaförsämring. Ett sätt att undvika det är att skydda liststrukturen som helhet för "läs-skriva", medan det i versionen med NULL räcker att skydda datastrukturen som helhet för "skrivskyddad" (om en uppdateringsoperation inte kommer Följ).
  • Sentinel-konceptet är inte användbart för inspelning av datastrukturen på disk.

Exempel

Sök i en länkad lista

Nedan finns två versioner av en subrutin (implementerad i programmeringsspråket C ) för att leta upp en given söknyckel i en enkellänkad lista . Den första använder sentinelvärdet NULL , och den andra en (pekare till) sentinelnoden Sentinel , som indikator för listans slut. Deklarationerna för den enkellänkade listdatastrukturen och resultaten för båda subrutinerna är desamma. 

                            
                       
     
   struct  sll_node  {  // en nod i den enkellänkade listan  struct  sll_node  *  nästa  ;  // end-of-list-indikator eller -> nästa nod  int-  nyckel  ;  }  sll  ,  *  först  ;

Första versionen som använder NULL som en indikator för listans slut 


                                

       
      
        
          
    
                                
    
    
     
 // global initialisering  först  =  NULL  ;  // före den första infogningen (visas inte)  struct  sll_node  *  Sök  (  struct  sll_node  *  first  ,  int  search_key  )  {  struct  sll_node  *  node  ;  for  (  nod  =  första  ;            nod  !=  NULL  ;  
 nod  =  nod  ->  nästa  )  {             if  (  nod  ->  nyckel  ==  söknyckel  ) 
 returnera  nod  ;  // found  }  // söknyckel finns inte i listan:  return  NULL  ;  }

For -loopen innehåller två tester (gula linjer) per iteration :

  • nod != NULL;
  • if (nod->nyckel == söknyckel) .

Andra versionen använder en sentinel nod

Den globalt tillgängliga pekarvakten till den avsiktligt förberedda datastrukturen Sentinel används som indikator för listans slut. 


    

  
                             // global variabel  sll_node  Sentinel  ,  *  sentinel  =  &  Sentinel  ;  // global initialisering  sentinel  ->  nästa  =  sentinel  ;  första  =  sentinel  ;  // före den första infogningen (visas inte)

Observera att pekaren alltid måste hållas i slutet av listan. Detta måste underhållas av funktionerna infoga och radera. Det är dock ungefär samma ansträngning som när man använder en NULL-pekare. 

       
      
    
      
        
          
    
 
    
       
                                
    
     
 struct  sll_node  *  SearchWithSentinelnode  (  struct  sll_node  *  först  ,  int  söknyckel  )  {  struct  sll_node  *  nod  ;  // Förbered "noden" Sentinel för sökningen:  sentinel  ->  key  =  search_key  ;  för  (  nod  =  första  ;            nod  ->  nyckel  !=  söknyckel  ;  
 nod  =  nod  -  >  nästa  )  {}  // Efterbearbetning:  if  (  nod  !=  sentinel  )  returnod  ;  // hittat  // söknyckel finns inte i listan:  return  NULL  ;  }

For -loopen innehåller endast ett test (gul linje) per iteration :

  • nod->nyckel != söknyckel; .

Python-implementering av en cirkulär dubbellänkad lista

Länkade listimplementeringar, speciellt en av en cirkulär, dubbellänkad lista, kan förenklas anmärkningsvärt med hjälp av en sentinel nod för att avgränsa början och slutet av listan.

  • Listan börjar med en enda nod, vaktpostnoden som har nästa och föregående pekare pekar på sig själv. Detta villkor avgör om listan är tom.
  • I en icke-tom lista ger vaktpostnodens nästa pekare listans huvud, och den föregående pekaren ger listans svans.

Följande är en Python-implementering av en cirkulär dubbellänkad lista:

 
        
          
          
          

       
         

 
     
          
          
          

       
         

       
         

      
         

      
         

      
          
        

      
          
        

        
           
             
          
          
          
          
         

       
          
          
          
          

      
          
          
           
              
          
           
             
         

     
          
            
             
              

     
          
            
             
               class  Node  :  def  __init__  (  self  ,  data  ,  next  =  None  ,  prev  =  None  ):  self  .  data  =  data  själv  .  nästa  =  nästa  jag  .  prev  =  prev  def  __repr__  (  self  )  ->  str  :  return  f  'Node(data=  {  self  .  data  }  )'  class  LinkedList  :  def  __init__  (  self  ):  self  .  _sentinel  =  Nod  (  data  =  Ingen  )  själv  .  _sentinel  .  nästa  =  själv  .  _sentinel  själv  .  _sentinel  .  föregående  =  själv  .  _sentinel  def  pop_left  (  self  )  ->  Nod  :  returnera  själv  .  remove_by_ref  (  self  .  _sentinel  .  next  )  def  pop  (  self  )  ->  Nod  :  return  self  .  remove_by_ref  (  self  .  _sentinel  .  prev  )  def  append_nodeleft  (  själv  ,  nod  ):  själv  .  add_node  (  själv  .  _sentinel  ,  nod  )  def  append_node  (  själv  ,  nod  ):  själv  .  add_node  (  self  .  _sentinel  .  prev  ,  node  )  def  append_left  (  jag  ,  data  ):  nod  =  Nod  (  data  =  data  )  själv  .  append_nodeleft  (  nod  )  def  append  (  själv  ,  data  ):  nod  =  Nod  (  data  =  data  )  själv  .  append_node  (  nod  )  def  remove_by_ref  (  själv  ,  nod  )  ->  Nod  :  om  noden  är  själv  .  _sentinel  :  höj  Undantag  (  'Kan aldrig ta bort sentinel.'  )  nod  .  föregående  .  nästa  =  nod  .  nästa  nod  .  nästa  .  prev  =  nod  .  föregående  nod  .  prev  =  Ingen  nod  .  nästa  =  Ingen  returnod  def  add_node  (  self  ,  curnode  ,  newnode  )  :  newnode  .  nästa  =  curnode  .  nästa  nya nod  .  prev  =  curnode  curnode  .  nästa  .  prev  =  newnode  curnode  .  nästa  =  newnode  def  search  (  själv  ,  värde  ):  själv  .  _sentinel  .  data  =  värdenod  =  själv  .  _  _sentinel  .  nästa  stund  nod  .  data  !=  värde  :  nod  =  nod  .  nästa  jag  .  _sentinel  .  data  =  Ingen  om  noden  är  själv  .  _sentinel  :  return  Ingen  returnod  def  __iter__  (  själv  )  :  nod  =  själv  .  _sentinel  .  nästa  medan  noden  inte  är  själv  .  _sentinel  :  avkastningsnod  .  _  datanod  =  nod  .  _  nästa  def  reviter  (  själv  ):  nod  =  själv  .  _sentinel  .  föregående  medan  noden  inte  är  själv  .  _sentinel  :  avkastningsnod  .  _  datanod  =  nod  .  _  föregående

Lägg märke till hur add_node() -metoden tar noden som kommer att förskjutas av den nya noden i parametern curnode . För att lägga till till vänster är detta huvudet på en icke-tom lista, medan för att lägga till till höger är det svansen. Men på grund av hur länkningen är inställd för att referera tillbaka till sentinel, fungerar koden bara för tomma listor också, där curnode kommer att vara sentinelnoden.

Sök i ett binärt träd

Allmänna deklarationer, liknande artikeln Binärt sökträd : 

                       
              
     
 

                            
                  
  struct  bst_node  {  // en nod i det binära sökträdet  struct  bst_node  *  child  [  2  ];  // vardera: ->nod eller slut-på-väg-indikator  int-  nyckel  ;  }  ;  struct  bst  {  // binärt sökträd  struct  bst_node  *  root  ;  // ->nod eller end-of-path indikator  }  *  BST  ;

Den globalt tillgängliga pekarvakten till den enda avsiktligt förberedda datastrukturen Sentinel = *sentinel används för att indikera frånvaro av ett barn . 


    

0    

                    // global variabel  bst_node  Sentinel  ,  *  sentinel  =  &  Sentinel  ;  // global initiering  Sentinel  .  barn  [  ]  =  Sentinel  .  barn  [  1  ]  =  sentinel  ;  BST  ->  rot  =  sentinel  ;  // före den första infogningen (visas inte)

Observera att pekaren alltid måste representera varje löv på trädet. Detta måste underhållas av funktionerna infoga och radera. Det är dock ungefär samma ansträngning som när man använder en NULL-pekare. 

       
      
    
      
 
        
           
            
           
              0    
        
                  
    
 
    
       
                           
    
     
 struct  bst_node  *  SearchWithSentinelnode  (  struct  bst  *  bst  ,  int  söknyckel  )  {  struct  bst_node  *  node  ;  // Förbered "noden" Sentinel för sökningen:  sentinel  ->  key  =  search_key  ;  for  (  nod  =  bst  ->  rot  ;;)  {  if  (  söknyckel  ==  nod  ->  nyckel  )  break  ;  om  söknyckel  <  nod  ->  nyckel  :  nod  =  nod  ->  barn  [  ];  // gå vänster  else  node  =  nod  ->  barn  [  1  ];  // gå höger  }  // Efterbearbetning:  if  (  nod  !=  sentinel  )  return  node  ;  // hittat  // söknyckel finns inte i trädet:  return  NULL  ;  }
Anmärkningar
  1. Med användningen av SearchWithSentinelnode förlorar sökning R/O -egenskapen. Detta innebär att i applikationer med samtidighet måste den skyddas av en mutex , en ansträngning som normalt överstiger vaktpostens besparingar.
  2. SearchWithSentinelnode stöder inte toleransen för dubbletter.
  3. Det måste finnas exakt en "nod" för att användas som vaktpost, men det kan finnas extremt många pekpinnar till det.

Se även

  1. ^ Ignatchenko, Sergey (1998), "STL-implementationer och trådsäkerhet", C++-rapport
Hämtad från " https://en.wikipedia.org/w/index.php?title=Sentinel_node&oldid=1142596105 "