2016-06-22 13 views
-3

Ich habe seit einiger Zeit versucht, meine pop() -Funktion ordnungsgemäß funktionieren zu lassen, aber aus irgendeinem seltsamen Grund ist alles, was es tut, nichts. Hier ist meine Stack-Deklaration & function.L.E. Ich habe auch die Push-Funktion hinzugefügt.Pop() Funktion für Stapel in C

typedef struct node 
{ 
    int v; 
    struct node* next; 
}Node; 

void push(Node **l,int val) 
{ 
    Node *p = (Node *)calloc(1,sizeof(Node)); 
    p->v = val; 
    Node *aux=*l; 
    if(aux == NULL) 
    { 
     *l = p; 
     return; 
    } 
    while(aux->next != NULL) 
     aux = aux->next; 
    aux->next = p; 
} 

void pop(Node **l) 
{ 
    if(*l != NULL) 
    { 
    Node *aux,*prev; 
    prev = *l; 
    aux = prev->next; 
    if(aux == NULL) 
     free(prev); 
    else 
    { 
     while(aux->next != NULL) 
     { 
     prev = aux; 
     aux = aux->next; 
     } 
     prev->next = NULL; 
     free(aux); 
    } 
    } 
} 

Und ich nenne es mit

Node *stack = NULL; 
pop(&stack); 
+4

Es tut nichts, weil Sie die Funktion zurückzukehren gesagt, wenn die –

+0

gleich 'NULL' gebene Wert ist in @self argumentieren bitte. Btw Ich entfernte diesen Teil und es funktioniert immer noch nicht –

+0

Das ist nicht dein Problem, aber warum nennst du 'free' auf' prev-> v' und 'aux-> v'? Das 'v'-Member wird nicht als Zeiger auf irgendetwas deklariert; Ordnen Sie ihr das Ergebnis von 'malloc' oder' calloc' zu? –

Antwort

1

Es würde helfen, um zu sehen, wie Sie Elemente auf den Stapel schieben. Wenn Sie wirklich anrufen pop ohne eine push zuerst, nun, dann ist es nicht angenommen,, etwas zu tun, ist es?

Dieses Bit macht mich nervös:

Sie setzen prev-*stack, und wenn nichts prev folgt, können Sie es kostenlos. Beachten Sie, dass seit prev == *stack auch *stack freigegeben wurde, so dass der Zeiger jetzt ungültig ist. Wenn Sie versuchen, auf diesen Zeiger in Ihrem Aufrufer zuzugreifen, rufen Sie Undefined Behavior auf.

Es sieht so aus, als würden Sie Ihre Liste an der Spitze des Stapels machen; Ich werde Ihnen jetzt sagen, dass Sie Ihr Leben viel einfacher machen wird, wenn Sie die Liste Kopf die Spitze des Stapels machen, so dass Ihre Schübe und Pops wie folgt aussehen:

bool push(Node **l, int val) 
{ 
    Node *p = calloc(1, sizeof *p); 
    if (p) 
    { 
    p->v = val; 
    p->next = *l; // set p to point to the current head of the list 
    *l = p;   // make p the new head of the list 
    } 
    return p != NULL; // will return false if the calloc (and by extenion, 
}     // the push operation) fails. 

bool pop(Node **l, int *v) 
{ 
    Node *p = *l;  // p points to head of list 
    if (!p) 
    return false; 

    *v = p->val;  // get value in current node 
    *l = p->next; // make the next element the new list head 
    p->next = NULL; // sever the old list head 
    free(p);  // and deallocate it 

    return true; 
} 

Keine Liste Traversals, keine Notwendigkeit, aktuelle und vorherige Knoten zu verfolgen. Alles, was Sie interessiert, ist der Kopfknoten. Die Aussage p->next = NULL; ist nicht unbedingt notwendig, da wir sofort danach freigeben. Ich mag es, weil es offensichtlich macht, dass wir aus der Listep entfernt haben, aber wenn Sie die Zyklen nicht verschonen wollen, können Sie es weglassen.

bearbeiten

Ich hatte Recht über diesen Code, nervös zu sein.

Also hier ist im Grunde, was passiert - wenn Sie genau ein Element in dem Stapel haben, können Sie den Kopf der Liste frei, aber Sie nicht den Wert des Listenzeigers (*stack im ursprünglichen Code aktualisieren, *l in der letzten Bearbeitung). Der Wert der stack Variable in main ist unverändert, und jetzt ist es ungültig - der Speicher an dieser Adresse ist nicht mehr zugeordnet. Wenn Sie also das nächste Mal push anrufen, sieht es, dass *l nicht NULL ist, und versucht, die (nicht vorhandene) Liste zu durchlaufen.

An diesem Punkt ist das Verhalten nicht definiert; buchstäblich alles kann passieren. Auf meinem System nach dem ersten push hat stack den Wert 0x501010. Ich mache eine pop, die free s Speicher, aber nicht den Wert von stack. Auf der nächsten push, *l ist nicht NULL, also setze ich (*l)->next auf was auch immer malloc zurück, was in meinem Fall ist ...0x501010 wieder. So ist *l0x501010 und (*l)->next ist 0x501010. Wenn ich versuche, einen anderen Gegenstand zu drücken, komme ich in eine Endlosschleife (== p->next).

Um dies zu beheben, müssen Sie die Liste Zeiger auf NULL ein, nachdem Sie free es:

Node *aux,*prev; 
prev = *l; 
aux = prev->next; 
if(aux == NULL) 
{ 
    free(prev); 
    *l = NULL; 
    return; 
} 
+0

Vielen Dank für Ihre Hilfe John.Ich dachte, dass die Verwendung dieses Stück Code, die Sie von meinem Code hervorgehoben nur meinen Stapel freigeben .. Ich wusste nicht, dass dies "undefined Verhalten" verursachen könnte. ..Ich habe vergessen, die Push-Funktion einfügen, sorry dafür (ich habe jetzt bearbeitet). Ich wusste von dieser Technik, die du mir gezeigt hast, aber ich bin stur, um herauszufinden, warum es nicht so funktioniert, wie ich es versucht habe. Wenn Sie Zeit haben, mir wenigstens einen Hinweis zu geben, wäre ich noch dankbarer. –

+0

@CostiIvan: Sie sagen, die 'Pop'-Funktion macht nichts; Wie geschrieben, gibt es keinen Wert zurück oder schreibt keine Ausgabe an die Konsole. Wie also stellen Sie fest, dass es nichts tut? Verfolgen Sie die Ausführung mit einem Debugger? Überprüfe du den Wert des 'stack'-Zeigers in dem, was' pop' genannt wird? –

+0

Ich überprüfe den Wert jedes Mal, wenn Pop aufgerufen wird, ja. Z.B. Wenn ich einen Wert im Stapel habe und ich pop() verwende, bekomme ich entweder diesen exakten Wert oder einen zufälligen Wert. Wenn ich> 1 Wert mit pop() habe keinen Effekt ... –