Löschen in kreisförmige doppelt verkettete Liste verbunden mit Kopf

Question

Ich habe zwei kreisförmige doppelt verkettete Liste mit Kopf und Integer-Elemente (ungeordnet) verbunden. wollte in der ersten Liste löschen enthält die Werte in der zweiten Liste. Wie Arbeitszeiger? Wie mache ich diesen Ausschluss? Müssen Sie in der ersten Liste nach Werten suchen, um die zweite Liste zu löschen? Wie kann ich mit ihnen arbeiten? Könnte die Funktionsweise des Algorithmus erklären, um es zu lösen?

Exemple:

Ich habe zwei kreisförmigen doppelt verketteten Listen mit Kopf.

L1: 90 20 40 100 10 32 66

L2: 46 30 60 10 80 90

I die Werte in der ersten Liste gelöscht werden soll, die in den zweiten sind. Die erste Liste ist dann:

L1: 40 100 20 32 66

Ich würde gerne wissen, wie man mit dem Zeiger der Listen arbeiten, um diesen Ausschluß zu machen. Ich wollte eine Vorstellung im Pseudocode. Ich habe erstellt, um in C zu programmieren, aber ich verstehe den Algorithmus nicht. Ich muss verstehen, wie man es vorher macht.

Answer 1

Beginnen Sie mit dem Schreiben des Pseudocodes des Algorithmus und implementieren Sie dann die tatsächlichen Funktionen, die unabhängig voneinander getestet werden können.

Allgemeiner Pseudo-Code wäre so etwas wie:

for each node in list1 
{ 
    if (list2 contains node) 
    { 
     remove node from list1 
    } 
} 

Ihre Listen und Knoten der Annahme definiert ist so etwas wie:

struct Node 
{ 
    struct Node *next; 
    struct Node *prev; 
    int number; 
} 

struct List 
{ 
    struct Node *head; 
} 

// these should be instantiated somewhere 
struct List* list1; 
struct List* list2; 

So würde das Skelett der Funktion sein, so etwas wie:

struct Node* node = list1->head; 

while (node != null) 
{ 
    // prepare the next node early 
    struct Node* next = node->next; 

    // check if list2 contains a matching node 
    if (match(list2, node->number)) 
    { 
     // remove the node properly, 
     // updating whatever you need to update 
     remove(list1, node); 
    } 

    // if it's circular, check if this 
    // is the last node 
    if (next == list1->head) 
     break; 

    node = next; 
} 

So, jetzt sind Sie nur mit der Implementierung von zwei Funktionen übrig:

// returns true if any node in list contains the specified number 
bool match(struct List* list, int number); 

// removes the node from the list 
void remove(struct List* list, struct Node* node);