Einfügen eines Knotens vor einem bestimmten Knoten in doppelt verknüpfte Liste

Ich versuche, einen Knoten vor einem bestimmten Knoten einzufügen. Aber ich bin nicht in der Lage, die erforderliche Ausgabe zu erhalten.Einfügen eines Knotens vor einem bestimmten Knoten in doppelt verknüpfte Liste

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

struct node{ 

    int data; 
    struct node* prev; 
    struct node* next; 
}; 

void insert_beg(struct node** head, int new_data){ 
    struct node* temp = (struct node*)malloc(sizeof(struct node)); 
    temp->data = new_data; 

    if(*head == NULL){ 

     temp->next = *head; 
     temp->prev = NULL;   
     *head = temp; 
    } 
    else{ 
     temp->next = *head;  
     (*head)->prev = temp; 
     *head = temp; 
    } 
} 

void insert_before(struct node* next_node,int new_data){ 
    struct node* temp = (struct node*)malloc(sizeof(struct node)); 
    temp->data = new_data; 

    if(next_node == NULL) 
     printf("Invalid!!!!"); 


    temp->prev = next_node->prev; 
    temp->next = next_node; 
    next_node->prev = temp; 

    if(temp->prev!=NULL) 
     temp->prev->next = temp; 
} 

void printList(struct node* head){ 

    if(head == NULL) 
     printf("The list is empty\n"); 
    else 
     { 
      while(head!=NULL){ 

       printf("%d\n",head->data);    
       head = head->next;    
       } 
     } 
} 

int main(){ 

    struct node* head = NULL; 
    printList(head);  
    insert_beg(&head,10); 
    insert_beg(&head,20); 
    insert_before(head,70); 
    insert_beg(&head,30); 

    printList(head); 
}

Hier Ich versuche, einen Knoten einzufügen (mit Daten = 70) vor dem 20.

Ausgang: 30,20,10

Erwartete Ausgabe: 30,70,20, 10

Quelle

2016-08-01 oldDoctor

Lies nur 'main', aber ich sehe nicht, wie du vor dem ersten Punkt in der Liste einfügen kannst, ohne die Adresse (' & head') zu übergeben, da die 'head'-Variable aktualisiert werden muss. – user3386109

Wenn Sie insert_before anrufen, ist der neue Knoten der neue Kopf, wenn der angegebene Knoten der Kopf ist. Sie müssen also die Adresse head übergeben, um sie zu ändern.

Was Sie gerade jetzt sieht wie folgt aus:

head 
    | 
    v 
------   ------   ------ 
- 30 - ---> - 20 - ---> - 10 - 
------ <--- ------ <--- ------ 
       ^
------   | 
- 70 - ---------| 
------

Um dies zu beheben, die Adresse head in den Parametern insert_before umfassen.

void insert_before(struct node **head, struct node *next_node, int new_data){ 
    struct node* temp = malloc(sizeof(struct node)); // don't cast the return value of malloc 
    temp->data = new_data; 

    if(next_node == NULL) 
     printf("Invalid!!!!"); 


    temp->prev = next_node->prev; 
    temp->next = next_node; 
    next_node->prev = temp; 

    if(temp->prev!=NULL) { 
     temp->prev->next = temp; 
    } else { 
     *head = temp; 
    } 
}

Dann es so nennen:

insert_before(&head,head,70);

Quelle

2016-08-01 19:45:26 dbush

Aber was, wenn der gegebene Knoten nicht Kopf ist? – oldDoctor

@oldDoctor Es funktioniert immer noch wie erwartet. Tatsächlich funktioniert Ihr ursprünglicher Code solange der angegebene Knoten nicht "head" ist. In der aktualisierten Funktion ist das erste Argument immer die Adresse von "head" und das zweite Argument ist der Knoten, vor dem Sie den neuen Knoten platzieren möchten. – dbush

Sie tun alles, right.But Sie eine Sache in insert_before fehlen, wenn der übergebene Parameter next_node Kopf ist, dann werden Sie einen Knoten vor Kopf Einfügen werden . Daher müssen Sie diesen neu hinzugefügten Knoten eine head machen.

Quelle

2016-08-01 19:50:16

Aber was, wenn der übergebene Parameter nicht Kopf ist? – oldDoctor

Einfügen eines Knotens vor einem bestimmten Knoten in doppelt verknüpfte Liste

Antwort

Verwandte Themen