C Corrispondente di implementazione della lista collegata e coerenza tra puntatore e puntatore

1

Per ottenere un po 'di pratica in C, sto scrivendo alcune funzioni di base per operare su un elenco collegato di int. Ho iniziato con funzioni che accettavano come "elenco" un puntatore al nodo principale. Ora, mi trovo a correre in sempre più occasioni in cui ho sia bisogno di limitare le specifiche della funzione più di quanto vorrei, o ho bisogno di usare un puntatore a un puntatore al nodo principale per consentire l'alterazione / rimozione del nodo principale in un modo coerente con il modo in cui modifico / rimuovo altri nodi.

È preferibile che tutte le funzioni accettino una "lista" nella stessa forma, come un puntatore a un puntatore, piuttosto che accettare un puntatore al nodo? O forse dovrei cambiare il modo in cui penso a modificare / rimuovere il nodo principale per evitare di dover cambiare il puntatore?

Ad esempio, se scrivo una funzione remove che rimuove tutte le istanze del dato int, e il valore del nodo head è quello int, vedo alcune scelte ovvie:

  1. Posso passare un puntatore a un puntatore e spostare il puntatore testa sul nodo successivo non rimosso.

  2. Posso passare un puntatore e posso spostare il valore del nodo successivo non rimosso, ad esempio nodo x, nel nodo principale e rimuovere il nodo x insieme ad altri nodi che contengono il valore da rimuovere . Questo fallisce nel caso in cui l'elenco sia costituito da un solo nodo che contiene il valore, quindi devo limitare le specifiche per escludere questo caso.

Nel caso in cui passassi un puntatore a un puntatore per questa funzione, dovrei cambiare tutte le altre funzioni per accettare un puntatore a un puntatore?

Ci sono degli standard per cose come questa o spetta a me? (Fingendo ovviamente che questo codice sia importante in qualche modo per qualcuno diverso da me e che, in quella terra fantastica, possa essere usato da altre persone senza conoscere il funzionamento interno delle funzioni, al di là delle loro firme.)

    
posta bazuzi 20.10.2014 - 03:18
fonte

2 risposte

6

Ci sono tre opzioni che posso vedere.

  1. Utilizzare una struttura "list head" che non contenga dati, ma semplicemente punta su "la lista" (come sottolineato da Jonathan Eunice in un commento, questo significa che hai un posto per tutti gli eventuali dati extra che potresti eventualmente raccogliere e significa che non hai più bisogno di puntatori per i puntatori)
  2. Utilizza il puntatore a puntatore che hai identificato
  3. Restituisce sempre il "nuovo" valore di lista e fa uso del valore restituito.

Come esempio del terzo modello:

struct list { int val; struct list *next; }

struct list *drop_head(struct list *lst)
{
  struct list *rv = lst->next;
  free(lst);
  return rv;
}

void blah()
{
  struct list *my_list;
  /* imagine interesting code here */
  my_list = drop_head(my_list);
  /* imagine more interesting code here */
}
    
risposta data 23.10.2014 - 13:30
fonte
0

Ho scritto un programma simile per l'elenco collegato in C, è necessario ottenere il puntatore ai puntatori in tutte le funzioni per renderlo coerente su tutte le funzioni, perché la rimozione e la creazione di una nuova testa o coda richiederebbe un puntatore al puntatore. Comunque puoi fare enum per i puntatori di coda e testa. esempio dal mio codice:

enum LIST_PTR {
    LIST_HEAD =0,
    LIST_TAIL
};
struct node {
  struct node *NextNode; // Pointer to next node
  int data; // node data.
};

void enqueue(struct node** head, struct node** tail,int data);
int dequeue(struct node** head, struct node** tail);
int getCount(struct node** head, struct node** tail);
int destroyList(struct node** head, struct node** tail);

quindi puoi dichiarare e utilizzare o collegare l'elenco nel modo seguente

struct node* my_list[2];
my_list[0]=my_list[1]=NULL;

getCount(&my_list[LIST_HEAD],&my_list[LIST_TAIL]);

assicurati di assegnare i puntatori a NULL o ti sto dicendo per esperienza, avrai un errore di seg di cui non avrai idea!

    
risposta data 22.10.2014 - 21:36
fonte

Leggi altre domande sui tag