Implementierung einer XOR-verknüpften Liste

Question

Ich versuche die folgende Frage zu lösen, um mich auf ein Interview vorzubereiten xD

Eine XOR-verknüpfte Liste ist eine speichereffizientere doppelt verknüpfte Liste. Anstelle jedes Knotens, der die Felder next und prev enthält, enthält er ein Feld mit dem Namen both, das ein XOR des nächsten Knotens und des vorherigen Knotens ist. Implementieren Sie eine verknüpfte XOR-Liste. Es hat ein add (Element), das das Element am Ende hinzufügt, und ein get (index), das den Knoten am Index zurückgibt.

Bitte schlagen Sie vor, wie diese Implementierung verbessert werden kann. Vielen Dank im Voraus.

#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;
}

Answer 1

longist nicht unbedingt eine gute Wahl des Integer-Typs zum Speichern von Zeigern - <stdint.h>bietet uns zum Glück eine, uintptr_tdie für diesen Zweck garantiert breit genug ist (bevorzugen Sie immer einen vorzeichenlosen Typ, wenn Sie mit bitweisen Operationen arbeiten).

Ich mag es nicht, Zeigertypen hinter Typedefs wie zu verstecken pStNode. Ich denke, es ist klarer, den Zeigertyp direkt zu verwenden - oder const StNodegegebenenfalls einen Zeiger auf . Zum Beispiel get()sollte ein Zeiger auf const nehmen.

Es ist unnötig (und allgemein als unklug angesehen), das Ergebnis von zu werfen malloc(). void*kann jeder Art von Zeiger in C zugewiesen werden.

In dem Code fehlt ziemlich viel, was ich von etwas erwarten würde, das behauptet, eine Implementierung der Liste zu sein. Es gibt keine Funktion zum Entfernen von Elementen, und der einzige bereitgestellte Accessor ist der leistungsschwache Getter mit wahlfreiem Zugriff.

Insbesondere haben Sie nicht zur Verfügung gestellt next()und prev()Funktionen, die ich erwarten würde , um zu sehen , wenn Sie , dass beide Richtungen von Traversal Arbeit richtig demonstrieren wollen.

Warum wird get()eine vorzeichenbehaftete Ganzzahl für den Index akzeptiert? Es scheint, dass alle negativen Werte 0 entsprechen; Wir sollten diese entweder zum Laufen bringen oder stattdessen einen vorzeichenlosen Typ akzeptieren. Außerdem können wir den Umfang tmpinnerhalb der Schleife sicher reduzieren .

Es ist am besten, main()als Funktionsprototyp zu schreiben int main(void)(dh keine Argumente anstelle einer nicht angegebenen Anzahl von Argumenten zu verwenden). Und im Gegensatz zu anderen Funktionen main()muss für den Erfolg kein Wert zurückgegeben werden, sodass diese Zeile weggelassen werden kann.

Answer 2

long both;

1. Die Verwendung eines longzum Speichern eines Cast-Zeigers kann sowohl verschwenderisch als auch zu wenig sein. Verwenden Sie einfach die dedizierten uintptr_t. Auch wenn Ihre Implementierung möglicherweise nicht vollständig C99 (MS Greets) entspricht, hat sie wahrscheinlich <stdint.h>das typedef.

pStNode newNode = (StNode *) malloc(sizeof(StNode));

Die obige Zeile zeigt drei schlechte Ideen:

1. Mehr Stücke, um den Überblick zu behalten, bedeuten mehr Komplexität, was schlecht ist. Daher ist es eine schlechte Idee, Zeiger hinter typedefs zu verstecken, es sei denn, dieser Zeigertyp wird niemals dereferenziert und ist daher der einzig wahre Typ.

2. Casting a void*ist überflüssig und fehleranfällig.
   Siehe " Werfe ich das Ergebnis von Malloc? ".

3. Nicht verwenden, es sizeof(TYPE)sei denn, dies ist unvermeidlich. Es ist fehleranfällig, es richtig zu machen, auch wenn die Typen nicht verdeckt sind. Einfach benutzen sizeof *pointer.

pStNode get(pStNode headNode, int index)

1. Es gibt einen Typ, der eindeutig als Index geeignet ist : size_t. Wenn Sie alternativ etwas signieren möchten, könnte Sie das interessieren ptrdiff_t. Obwohl ja, wenn Ihr Anwendungsfall nur wenige Knoten garantiert, intkönnte dies funktionieren.

2. Sie sollten Ihre Liste wirklich irgendwie kapseln. Derzeit erstellen Sie eine einmalige in main().
   Eine Bereinigung sollte auch möglich sein, ohne das Programm zu beenden.

3. Wenn Sie mindestens C99 verwenden, main()hat dies eine implizite return 0;.