C LanguageListe collegate


Osservazioni

Il linguaggio C non definisce una struttura di dati dell'elenco collegato. Se si utilizza C e si necessita di un elenco collegato, è necessario utilizzare un elenco collegato da una libreria esistente (ad esempio GLib) o scrivere la propria interfaccia dell'elenco collegato. Questo argomento mostra esempi di elenchi collegati e doppi elenchi collegati che possono essere utilizzati come punto di partenza per scrivere i propri elenchi collegati.

Elenco collegato singolarmente

L'elenco contiene nodi che sono composti da un collegamento chiamato next.

Struttura dati

struct singly_node
{
  struct singly_node * next;
};

Lista doppiamente collegata

L'elenco contiene nodi composti da due collegamenti chiamati precedente e successivo. I collegamenti fanno normalmente riferimento a un nodo con la stessa struttura.

Struttura dati

struct doubly_node
{
  struct doubly_node * prev;
  struct doubly_node * next;
};

Topoliges

Lineare o aperto

inserisci la descrizione dell'immagine qui

Circolare o anello

inserisci la descrizione dell'immagine qui

procedure

legare

Unisci due nodi insieme. inserisci la descrizione dell'immagine qui

void doubly_node_bind (struct doubly_node * prev, struct doubly_node * next)
{
  prev->next = next;
  next->prev = prev;
}

Creare un elenco collegato in modo circolare

inserisci la descrizione dell'immagine qui

void doubly_node_make_empty_circularly_list (struct doubly_node * head)
{
  doubly_node_bind (head, head);
}

Creare un elenco linearmente collegato

inserisci la descrizione dell'immagine qui

void doubly_node_make_empty_linear_list (struct doubly_node * head, struct doubly_node * tail)
{
  head->prev = NULL;
  tail->next = NULL;
  doubly_node_bind (head, tail);
}

Inserimento

Supponiamo che una lista vuota contenga sempre un nodo invece di NULL. Quindi le procedure di inserimento non devono prendere in considerazione NULL.

void doubly_node_insert_between
(struct doubly_node * prev, struct doubly_node * next, struct doubly_node * insertion)
{
  doubly_node_bind (prev, insertion);
  doubly_node_bind (insertion, next);
}

void doubly_node_insert_before
(struct doubly_node * tail, struct doubly_node * insertion)
{
  doubly_node_insert_between (tail->prev, tail, insertion);
}

void doubly_node_insert_after
(struct doubly_node * head, struct doubly_node * insertion)
{
  doubly_node_insert_between (head, head->next, insertion);
}

Liste collegate Esempi correlati