Listă (computer)

Această intrare sau secțiune despre programare nu citează sursele necesare sau cei prezenți sunt insuficienți . Puteți îmbunătăți această intrare adăugând citate din surse de încredere în conformitate cu liniile directoare privind utilizarea surselor .

În informatică , o listă (Listă) este o structură și o dinamică abstractă a datelor (utilizarea memoriei nu este neapărat contiguă fizic) denotând o colecție omogenă sau un container de date. Accesul la un element al structurii are loc direct numai la primul element al secvenței; pentru a accesa orice element, este necesar să se scaneze secvențial toate elementele care îl preced; este o structură de date dinamică, deoarece se poate schimba în dimensiune datorită operațiilor de inserare și ștergere a elementelor, spre deosebire de cazul matricelor standard.

Operațiuni fundamentale

Operațiunile de bază oferite de o listă sunt următoarele:

• Inserare [Cost O (1) sau O ( n ) în funcție de implementare];
• Eliminare [Cost O (1) sau O ( n ) în funcție de implementare];
• Căutați [Cost O (jurnal ( n )) sau O ( n ) în funcție de implementare];
• Acces aleatoriu după index [Cost O (1) sau O ( n ) în funcție de implementare];
• Acces secvențial [Cost O (1)];
• Număr de articole [Cost O (1) sau O ( n ) în funcție de implementare].

Implementare

Exemplu de listă implementată prin structuri legate

În principal, există două implementări ale listelor. Una folosește tablouri ca suport, cealaltă folosește structuri conectate ; cele două abordări diferă prin serviciile oferite. În special, o ArrayList va oferi acces aleatoriu la costul O (1), în timp ce o LinkedList va oferi un cost O (n); pe de altă parte, o inserție într-o ArrayList ar putea costa O (n) (în cazul redimensionării sau a matricei), în timp ce pe o LinkedList va costa întotdeauna O (1).

Algoritmi de gestionare (iterativi)

• Definiția structurii:

   typedef int TKey ;
  typedef int TSat ;
  
  struct SInfo {
      Tastă cheie ;
      Satelit TSAT;
  };
  
  typedef struct SInfo TInfo ;
  
  struct TNode {
      TInfo info ;
      struct TNode * link ;
  };
  
  typedef struct TNode SNode ;
  typedef TNode * TList ;
  

• Creare:

   TList list_create () {
      return NULL ;
  }
  

• Inserare:

   TList list_insert ( TList list , TInfo info ) {
      TList curr , succ ;
      curr = NULL ;
      succ = listă ;
      
      while ( succ ! = NULL && mai mare ( info . key , succ -> info . key )) {
          curr = succ ;
          succ = succ -> link ;
      }
      
      TNode * nou ;
      new = ( TNode ) malloc ( sizeof ( TNode ));
      nou -> info = info ;
      
      if ( curr == NULL ) {
          nou -> link = list ;
          
          reveni nou ;
      } altceva {
          curr -> link = new ;
          nou -> link = succ ;
          
          lista de returnare ;
      }
  }
  

• Eliminare:

   TList list_delete ( lista TList , cheie TKey ) {
      TList curr , succ ;
      curr = NULL ;
      succ = listă ;
      
      while ( succ ! = NULL && mai mare ( key , succ -> info . key )) {
          curr = succ ;
          succ = succ -> link ;
      }
      
      if ( succ ! = NULL && egal ( cheie , succ -> info . cheie )) {
          if ( curr == NULL ) {
              list = succ -> link ;
          } altceva {
              curr = succ -> link ;
              
              gratuit ( succ );
          } lista de returnare ;
      }
  }
  

• Caută:

   T_Node * list_search ( T_List list , T_Key key ) {
      T_List curr ;
      curr = list ;
      
      while (( curr ! = NULL ) && greater_team ( key , curr -> info . tag )) {
          curr = curr -> link ;
      }
      
      if (( curr ! = NULL ) && equal_team ( key , curr -> info . tag )) {
          retur curr ;
      } altceva {
          return NULL ;
      }
  }
  

• Vizita cu tipar:

   void list_visit ( T_List list ) {
      T_List curr ;
      curr = list ;
      
      while ( curr ! = NULL ) {
          print_node ( curr -> info );
          curr = curr -> link ;
      }
  }
  

• Numara:

   int node_count ( T_List list ) {
      if ( list == NULL ) {
          retur 0 ;
      } altceva {
          returnează 1 + contor_node ( listă -> link );
      }
  }
  

• Lista distrugerii:

   T_List list_destroy ( T_List list ) {
      T_List curr, succ;
      curr = list ;
      
      while ( curr ! = NULL ) {
          succ = curr -> link ;
          
          liber ( curr );
          
          curr = succ ;
      }
  }
  

Algoritmi de gestionare (recursivi)

• Creare:

   TList list_create () {
      return NULL ;
  }
  

• Inserare:

   TList list_insert ( TList list , Tinfo info ) {
      if ( list == NULL || mai mare ( list -> info . key , info . key )) {
          TNode * nou ;
          
          new = ( TNode * ) malloc ( sizeof ( TNode ));
          
          nou -> info = info ;
          nou -> link = list ;
          
          reveni nou ;
      } altceva {
          list -> link = list_insert ( list -> link , info );
          
          lista de returnare ;
      }
  }
  

• Eliminare:

   TList list_delete ( lista TList , cheie TKey ) {
      if (( list == NULL ) || gratar ( list -> info . cheie , cheie )) {
          lista de returnare ;
      } else if ( egal ( listă -> info . cheie , cheie )) {
          TList alias ;
          alias = list -> link ;
          
          gratuit ( listă );
          
          return alias ;
      } altceva {
          listă -> link = list_delete ( listă -> link , cheie );
          
          lista de returnare ;
      }
  }
  

• Caută:

   T_Node * list_search ( T_List list , T_Key key ) {
      if ( list == NULL || egal ( list -> info . cheie , cheie )) {
          lista de returnare ;
      } else if ( răzătoare ( listă -> info . cheie , cheie )) {
          return NULL ;
      } altceva {
          list_search ( list -> link , cheie );
      }
  }
  

• Vizitați cu print direct:

   void list_visit ( T_List list ) {
      if ( list ! = NULL ) {
          print_info ( listă -> informații );
          list_visit ( list -> link );
      }
  }
  

• Vizită tipărită inversă:

   void list_visit ( T_List list ) {
      if ( list ! = NULL ) {
          list_visit ( list -> link );
          
          print_info ( listă -> informații );
      }
  }
  

• Numara:

   int node_count ( T_List list ) {
      if ( list == NULL ) {
          retur 0 ;
      } altceva {
          returnează 1 + contor_node ( listă -> link );
      }
  }
  

• Lista distrugerii:

   T_List list_destroy ( T_List t ) {
  	if ( t ! = NULL )
  	{
  		list_destroy ( t -> link );
  		gratuit ( t );
  	}
  	return NULL ;
  }
  

Tipuri de liste

• Lista cu indicii
• Lista cu matrice
• Lista circulară

Elemente conexe

• Înțelegerea listei
• Structură de date
• Costul de calcul
• Multi-set

Alte proiecte

• Wikționarul conține dicționarul lemă « listă »

linkuri externe

• Lista ( EN ), în Encyclopedia Britannica , Encyclopædia Britannica, Inc.

V · D · M Algoritmi de sortare
Teorie	Teoria complexității de calcul · notație Big O · Matrice · Listă · Stivă · Coadă · Sortare comparativă · Sortare adaptivă
Algoritmi de schimb	Bubble sortare · Shaker sortare · par-impar sortare · Comb sortare · Gnome sortare · Quicksort
Algoritmi de selecție	Sortare selecție · Sortare grămadă · Smoothsort
Algoritmi de inserție	Inserția sortare · Shell sortare · copac sortare · Bibliotecă sortare · sortare Răbdare
Algoritmi de fuziune	Merge sort · Timsort
Algoritmi necomparativi	Sortare Radix · Sortare cupă · Sortare numărare · Sortare porumbel
Alți algoritmi	Sortarea de rețea · topologică sortare · sortare bitonic · clatite sortare
Algoritmi ineficienți	Sortare stupidă · Sortare Trippel

Portal IT : accesați intrările Wikipedia care se ocupă cu IT