Stack

[IltisvdT]

Hallo, ich mal wieder...

Wir sollen ein stack als array speichern. Mit malloc den Speicherplatz in 5er Schritten allokieren und das ganze mit push, pop und top "verarbeiten".

Dazu haben wir folgende Codes(z.T. vorgegeben bekommen):

Aufg1.c

#include <stdio.h>

#include <stdlib.h>

#include "stack.h"


int main() {

    push(6); push(5); push(35); push(34); 

    printf("Top: %d \n", top());

    push(3);

    printf("Top: %d \n", top());

    push(5);

    printf("Top: %d \n", top());

    push(10);

    printf("Pop: %d \n", pop());

    printf("Pop: %d \n", pop());

    printf("Top: %d \n", top());


    return 0;

}

stack.h:

void push(int);

int pop();

int top();

stack.c(unser Programm):

#include <stdio.h>

#include <stdlib.h>

#include "stack.h"



static int *stack;

static int index=0;

static int size=0,a=5,bin=0;



void push(int element)

    {

    int i=size;

    int *temp;

    int b;

    if(bin==0)

        {

        stack=malloc(sizeof(stack[a]));

        bin=1;

        }

    if(size>a)

        {

        temp=malloc(sizeof(stack[a+5]));

        printf("oooo");

        for(b=0; b<(size-1); b++)

            temp[b]=stack[b];

        printf("test");

        free(stack);

        stack=malloc(sizeof(stack[a+5]));

        printf("SSSSSSSSSSSS");

        for(b=0; b<size; b++)

            stack[b]=temp[b];

        free(temp);

        a+=5;

        }

    stack[index++]=element;

    size++;

    }


int pop()

    {

    return stack [--index];

    size--;

    }


int top()

    {

    return stack[index-1];

    }

Das Programm stürzt immer ab. Und zwar nach dem printf("test"). Nehme ich die pops raus aus der Aufg1, dann passiert folgendes:

Eigenartiger Weise stürzt er mal früher und mal später, an verschiedenen Stellen, u.a. direkt vor dem return (0) ab..

Wieso stürzt ein Programm an verschiedenen Stellen ab, ohne jegliche Veränderung und nur bei einem erneuten Aufruf?

Und an welcher Stelle liegt unser Problem?

[carstenj]

Hi,

Was davon ist denn vorgegeben? Was ist a? Was ist bin? Kommentare helfen immer, sowohl dir (später) als auch den Helfenden.

Vermutlich greifst du auf einen nicht allozierten Speicherbereich zu. Bei mir stürzt das Programm nicht ab, funktioniert ab dennoch nicht richtig, weil mit pop nicht der zuletzt auf den Stack abgelegt Wert zurückgeliefert wird.

[IltisvdT]

Also gegeben sind Aufg1.c und stack.h, stack.c sollen wir selbst schreiben.

a haben wir eingeführt um den anzufordernden Speicher jeweils um 5 zu erweitern.

bin soll lediglich als eine Art Schalter fungieren, sodass der anfangs benötigte Speicher nur einmal bereitgestellt wird und die if-Bedingung nicht wieder gestartet wird.

Ja, dass mit dem falschen Wert bei pop hatten wir auch.

Das mit dem nicht allozierten Speicher haben wir uns schon gedacht, allerdings haben wir doch den benötigten Speicher immer vorher per malloc angefordert?!

Die printfs sind lediglich um zuschauen, an welcher Stelle er abstürzt..

[unbenannt]

Eigenartiger Weise stürzt er mal früher und mal später, an verschiedenen Stellen[...]

Das passiert, wenn man vollkommen undefiniertes Verhalten herauf beschwört. Was geschieht beispielsweise beim ersten "push" in nachfolgender Zeile?

stack=malloc(sizeof(stack[a]));

[IltisvdT]

Was geschieht beispielsweise beim ersten "push" in nachfolgender Zeile?

Korrigiert mich, wenn ich irre, aber soweit ich weiß liefert malloc eine Zeiger auf eine Adresse wo ein freier speicherbereich der in malloc geforderten Größe beginnt. Und auf diese Adresse soll auch der stack-pointer zeigen. Ich weiß nicht genau, wo da vollkommen undefiniertes Verhalten sein soll. Aber ich habe nicht genug Ahnung davon um das so beurteilen zu können, aber speziell bei der ersten if-bedingung (aus der ja diese Zeile stammt) bin ich mir recht sicher....

[Klotzkopp]

Korrigiert mich, wenn ich irre, aber soweit ich weiß liefert malloc eine Zeiger auf eine Adresse wo ein freier speicherbereich der in malloc geforderten Größe beginnt.

Soweit richtig. Und welche Größe forderst du an? Was ist sizeof(stack[a])?

Ich hatte dich in deinem letzten Thread bereits darauf hingewiesen, dass du dich informieren sollst, was sizeof tut. Der Hinweis ist offenbar auf taube Ohren gefallen.

sizeof arbeitet mit Typen. Wenn du sizeof statt auf einen Typen auf einen Ausdruck anwendest, wird der Typ des Ausdrucks ermittelt, und dann dessen Größe bestimmt. Insbesondere wird der Ausdruck nicht ausgewertet. Das Ergebnis des sizeof-Operators wird zur Compilezeit ermittelt. Irgendwelche Variableninhalte zur Laufzeit können also gar keinen Einfluss auf das Ergebnis haben.

Wenn der Compiler auf sizeof(stack[a]) trifft, erkennt er, dass stack[a] kein Typ, sondern ein Ausdruck ist. Er ermittelt also den Typ des Ausdrucks. stack ist ein int*, zusammen mit dem Indexoperator wird daraus int.

sizeof(stack[a]) ist also gleichbedeutend mit sizeof(int). Das ist auf heute gängigen Plattformen 4, und damit sicher nicht das, was du beabsichtigt hast.

sizeof ist kein magisches Wunderding, das automatisch tut, was du meinst. sizeof hat eine klare Funktion, und hier ist es (wieder) falsch angewendet.

[IltisvdT]

Also das Problem mit dem sizeof haben wir gelöst.

stack=malloc(a*sizeof(int)); hoffe das ist auch gut gelöst:D

Nun bleibt das Problem, dass beim letzten Aufruf von top der falsche Wert geliefert wird. Es wird ja wahrscheinlich mit dem Wert des Index zusammenhängen, aber dieser ist bei den vorherigen Funktionsaufrufen ja richtig. Oder sehen wir das falsch?

[unbenannt]

Wenn ihr nur die mallocs angepasst habt, dann ist die push-Funktion noch immer fehlerhaft. Unter Ubuntu mit gcc kompiliert (mallocs vorher natürlich korrigiert) fliegt mir das Programm um die Ohren, sobald mehr als 5 Werte eingefügt werden.

Lasst Euch mal bei jedem push die Werte von "index" und "size" ausgeben und schaut mal, was passiert, wenn der Stack vergrößert werden muss - oder besser gesagt was einen Schritt zuvor geschehen ist.

Kleine Anmerkung zu folgender Funktion:

int pop()

    {

    return stack [--index];

    size--;

    }

Nach einem return wird kein Code mehr ausgeführt.

[IltisvdT]

Ok, size haben vor das return gesetzt.

Haben uns Index und size printen lassen, verstehen aber nicht, wo da das Problem liegen soll. Kannst du das etwas präzisieren?

[unbenannt]

Kleine Testmethode:

int main()

{

	int i;

	for (i = 0; i < 12; i++)

	{

		printf("%d. index %d, size %d\n", i, index, size);

		push(i);


	}

	return 0;

}

Ausgabe:

0. index 0, size 0

1. index 1, size 1

2. index 2, size 2

3. index 3, size 3

4. index 4, size 4

5. index 5, size 5

6. index 6, size 6

Anschließend bei mir: Absturz!

Ihr habt ein 5-elementiges Array (schätze ich zumindest mal), lasst aber zu, dass vor der Vergößerung des Arrays bereits ein Wert an Index 5 gespeichert werden soll.

[IltisvdT]

Daran lag es in der Tat! Danke sehr. Programm funktioniert nun wie gewünscht.

[unbenannt]

Kleiner Tip noch, welcher zwar nicht unbedingt für die Funktionsweise, jedoch für die Performance interessant ist:

Ihr fordert einen vergrößerten Speicherbereich für "temp" an und kopiert alle Werte aus "stack" dort hinein. Anschließend fordert ihr die gleiche Größe für "stack" an, kopiert wieder dort hinein und gebt den Speicherbereich von "temp" wieder frei. Das ist für ein manuelles Vergrößern viel zu umständlich. Ausreichend wäre, einen neuen Speicherbereich anzufordern, die Werte dort hinein zu kopieren, den alten Speicherbereich freizugeben und anschließend "stack" direkt auf den neuen Bereich zeigen zu lassen.

Noch einfacher funktioniert dies allerdings mit der Funktion "realloc", welche im Idealfall sogar den vorhandenen Speicherbereich lediglich vergrößert, wenn dies möglich ist (so wurde es mir zumindest erklärt, bzw. so habe ich es verstanden).