Implementazione di liste collegate XOR

Nov 10 2020

Sto cercando di risolvere la seguente domanda per prepararmi a un'intervista xD

Un elenco collegato XOR è un elenco collegato doppiamente più efficiente in termini di memoria. Invece di ogni nodo che contiene i campi successivo e precedente, contiene un campo denominato entrambi, che è uno XOR del nodo successivo e del nodo precedente. Implementare una lista collegata XOR; ha un add (elemento) che aggiunge l'elemento alla fine, e un get (index) che restituisce il nodo all'indice.

Suggerire come migliorare questa implementazione. Grazie in prima.

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int value;
    long both;
    
} StNode; 
typedef StNode *pStNode;

pStNode add(pStNode lastNode, int value)
{
    pStNode newNode = (StNode *) malloc(sizeof(StNode));
    newNode->value = value;
    
    //[both]=value of previous node pointer if it is last node
    newNode->both = (long)lastNode; 
    
    //calculating previous node [both] value
    lastNode->both = (long)newNode ^ lastNode->both;
    
    return newNode;
}

pStNode get(pStNode headNode, int index)
{    
    pStNode prevNode;
    pStNode currNode;
    long tmp;
    
    //special handling
    //case: cur=1, prev=0
    //we have set previous node of head node value to be 0 manually
    currNode = (StNode *) ((headNode->both) ^ 0);
    prevNode = headNode;
    
    //skim through linked list
    for(int i=2; i<=index; i++)
    {
        tmp = (long)prevNode;
        prevNode = currNode;
        currNode = (StNode *)(currNode->both ^ tmp);
    }
    
    return currNode;
}


int main() {  
    
    //I named first node as headNode, and last node as tailNode
    //create head node with both=0 since there is no previous node to it
    pStNode headNode = (StNode *) malloc(sizeof(StNode));
    headNode->both = 0; 
    headNode->value = 2;
    
    //assign pointers
    pStNode tailNode = headNode;
    
    //lets add 10 nodes after head, and assign values
    for(int i=3; i<13; i++)
    {
        tailNode = add(tailNode, i);
    }
    
    //get node value where index=3
    pStNode iNode = get(headNode, 3);
    printf( "result: %d\n",  iNode->value);
    
    return 0;
}

Risposte

7 TobySpeight Nov 10 2020 at 20:29

longnon è necessariamente una buona scelta di tipo intero per memorizzare i puntatori - fortunatamente <stdint.h>ci fornisce uintptr_tche è garantito essere abbastanza ampio per questo scopo (preferire sempre un tipo senza segno quando si lavora con operazioni bit per bit).

Non mi piace nascondere i tipi di puntatore dietro typedef come pStNode. Penso che sia più chiaro usare direttamente il tipo di puntatore o un puntatore a const StNodedove appropriato. Ad esempio, get()dovrebbe prendere un puntatore a const.

Non è necessario (e generalmente considerato poco saggio) lanciare il risultato di malloc(). void*può essere assegnato a qualsiasi tipo di puntatore in C.

Manca parecchio dal codice che mi aspetterei da qualcosa che afferma di essere un'implementazione dell'elenco. Non esiste una funzione per rimuovere gli elementi e l'unico accessorio fornito è il getter ad accesso casuale dalle prestazioni scarse.

In particolare, non hai fornito next()e prev()funzioni, che mi aspetto di vedere se vuoi dimostrare che entrambe le direzioni di attraversamento funzionano correttamente.

Perché get()accetta un numero intero con segno per l'indice? Sembra che i valori negativi siano tutti equivalenti a 0; dovremmo farli funzionare o accettare invece un tipo non firmato. Inoltre, possiamo tranquillamente ridurre l'ambito di tmpto all'interno del ciclo.

È meglio scrivere main()come un prototipo di funzione int main(void)(cioè senza prendere argomenti, piuttosto che un numero non specificato di argomenti). E a differenza di altre funzioni, main()non è necessario restituire un valore per il successo, quindi quella riga può essere omessa.