verknüpfte Liste ohne Duplikate

Question

Ich habe den folgenden Code (richtig für meine einfachen Tests) für eine verknüpfte Liste für keine Duplikate, aber ich denke, es ist ein bisschen hässlich.

Kann jemand einen saubereren Weg empfehlen, den doppelten Code zu behandeln? Das aktuelle Stück in Frage:

if((val == cur->val) || (cur->next && (val == cur->next->val))) 

Aber ich denke, dass eine bessere Lösung geben könnte (die ich nicht sehen), eine andere Verwendung von Vergleichsoperatoren verwenden.

Auch kann mir jemand einen Vorschlag für eine "nützliche" Behauptung oder nach innen hier geben. Es ist schwer zu sagen, wann man etwas behaupten soll, besonders wenn du eine if-Anweisung hast, die es für dich tut.

struct Node 
{ 
    Node(int v):val(v),next(NULL){} 
    int val; 
    Node * next; 
}; 

void insert(Node ** ppHead, const int val) 
{ 
    if(ppHead == NULL) 
     return; 
    if(*ppHead == NULL || val < (*ppHead)->val) 
    { 
     Node * tmp = new Node(val); // new throws 
     tmp->next = *ppHead; 
     *ppHead = tmp; 
    } 
    else 
    { 
     Node * cur = *ppHead; 
     while(cur->next && (val > cur->next->val)) 
      cur = cur->next; 

     if((val == cur->val) || (cur->next && (val == cur->next->val))) 
      return; 

     Node * tmp = new Node(val); // new throws 
     tmp->next = cur->next; 
     cur->next = tmp; 
    } 
    return; 
} 


int _tmain(int argc, _TCHAR* argv[]) 
{ 
    Node * list = NULL; 
    int x[] = { 5, 4, 6, 7, 1, 8, 1, 8, 7, 2, 3, 0, 1, 0, 4, 9, 9 }; 
    int size = sizeof(x)/sizeof(x[0]); 
    for(int i = 0; i < size; i++) 
     insert(&list, x[i]); 
    Node * cur = list; 
    while(cur) { 
     printf (" %d", cur->val); 
     cur = cur->next; 
    } 
    printf("\n"); 
    return 0; 
} 

Answer 1

Ich würde dies mehr wie schreiben:

void insert(Node ** ppHead, const int val) 
{ 
    if (ppHead == NULL) 
     return; 
    while (*ppHead && (*ppHead)->val < val) 
     ppHead = &(*ppHead)->next; 
    if (*ppHead && (*ppHead)->val == val) 
     return; 
    Node * tmp = new Node(val); // new throws 
    tmp->next = *ppHead; 
    *ppHead = tmp; 
} 

Answer 2

Ich würde ein Verfahren in den Knoten, um die Suchoperation (* ungetesteten Code) auszuführen:

Node* Find(int value) 
{ 
    if(this.val == value) return this; 
    if(this.next == null) return null; 
    return next.Find(value); 
} 

Dann vor Sie dem Einsetzen wollen die Existenz überprüfen:

if(null == _head || null == _head.Find(value)) 
    ... add value ... 

Answer 3

Würde das funktionieren?

// Note the change from > to >= 
while(cur->next && (val >= cur->next->val)) 
{ cur = cur->next; 
} 

if (val == cur->val) 
{ return; 
} 

Answer 4

Nun, zuerst, wenn Sie für Produktionscode verwenden diese sind, sollten Sie wahrscheinlich std:: verwenden, wenn das eine Option ist.

Je mehr ich über Ihren Code denke, desto mehr denke ich, dass Sie zwei Zeiger halten sollten. Grundsätzlich eine zum aktuellen Node und eine zum vorherigen Node. Wenn cur == NULL, nach prev einfügen. Wenn cur->value == val, zurückgeben. Dann können Sie überprüfen, ob cur->value < val und wenn ja, beide Knoten voran.

Sie haben derzeit einen speziellen Code für die Verarbeitung von *ppHead == NULL. Dies ist jedoch nicht notwendig, wenn Sie stattdessen prev als Node** curPtr haben. Beginnen Sie also mit curPtr=ppHead und cur=*curPtr. Dann sollte der obige Algorithmus für die ganze Sache funktionieren.

Oder als die Person, die gerade für Sie codiert, können Sie ppHead als curPtr-Variable selbst und (* ppHead) als cur verwenden. Nicht sicher, was besser lesbar ist.