Probleme bei Programmieraufgabe

[Kurt T. (kurtisblow)]

Hallo,
ich habe folgende Programmieraufgabe zu lösen:

"Implementieren sie einen Stack mit Hilfe eines dynamischen Array. 
Hierbei werden die Stackelemente in einem Array gespeichert.Jedes neue 
Stapelelement wird dabei als hinterstes Element in das Array eingefügt. 
Sollte durch eine push Operation die ursprüngliche Arragrösse 
überschritten werden, wird ein neues, doppelt so grosses Array erstellt, 
der ursprüngliche Inhalt hineinkopiert und das alte Array anschliessend 
gelöscht. Führen sie mit einem Zähler die aktuelle Anzahl Elemente mit. 
Zum Programmstart hat das dynamische Array die Gröse 2."

Nun habe ich leider Probleme mit dem Pointerarray, denn jedesmal wenn 
ich
den end Befehl im Dos aufrufe kackt mir das Programm ab. Manchmal auch 
beim Befehl pop. Kann mir jemand helfen?

#include <stdlib.h>
#include <iostream>
#include <string>
using namespace std;


//****************************************************************************************************************************************

struct stack{ //Definiert ein Struct
    int size_array; //Arraygroesse
    int position; //Stapelgroesse (pointer zeigt auf oberstes Element)
    }stack_define;

int *dynamic_array = new int[stack_define.size_array]; //Dies ist das dynamsche Array

//****************************************************************************************************************************************

void init() { //inizialisiert den struct dynamic_stapel

    stack_define.size_array = 2;
    stack_define.position =0;
}

//****************************************************************************************************************************************

int pop(){ // nimmt das oberste Element vom Stapel und loescht es, ebenfalls wird der Zeiger auf das Element darunter gerichtet
    if (stack_define.position > 0){ // Wenn es mindestens 1 Element gibt
        stack_define.position = stack_define.position -1;// Elemente nehmen ab
        dynamic_array = dynamic_array -1;
    }
    return 0; //Soll zeigen, dass der Stapel um 1 Element abnimmt    
}

//****************************************************************************************************************************************

void push(int element){ //legt ein neues Element oben auf den Stappel
     stack_define.position = stack_define.position + 1; // die Anzahl Elemente nehmen zu
     
     if (stack_define.position > stack_define.size_array){ // Wenn es mehr Elemente gibt als das Array gross ist
           int copy_array[stack_define.position]; //erstellt ein Zwischenspeicherarray
           for (int i=0 ; i<stack_define.position ;i++){ //Umkupieren der Elemente
               copy_array[i] = dynamic_array[i];
           }
           delete [] dynamic_array; //dynamic array Elemente werden geloescht
           while (stack_define.position > stack_define.size_array){ //Dann wird die Arraygroesse so lange verdoppelt, bis das Array groesser als die Anzahl Elemente ist.
                 stack_define.size_array = 2*(stack_define.size_array);
           }
           for (int i=0 ; i<stack_define.position; i++){ //Nun werden die Copy Elemente wieder in das nun groessere Array kopiert
               dynamic_array[i] = copy_array[i];
           }       
     }
     dynamic_array = dynamic_array +1;
     *dynamic_array = element; //Dem obersten Element wird der Wert von der Einageb "element" zugeordnet      
}

//****************************************************************************************************************************************

int size() { //gibt die groesse des Stapels an   
    return stack_define.position;
}


//****************************************************************************************************************************************


void clear() { //Loescht den ganzen Stapel
    delete [] dynamic_array;  
}


//****************************************************************************************************************************************


//Dieses Funktion implementiert eine Testumgebung f&#65533;r den Stack
void test() {
    cout << "The program has been startet without any arguments." << endl;
    cout << "The program enters the stack test mode:" << endl;
    cout << "Enter one of the commands: push, pop, end" << endl;
    string command;
    do{
      cin >> command;
      if (command == "pop"){
        cout << pop() << endl;
      } else if (command == "push"){
        cout << "element?";
        int elementToPush;
        cin >> elementToPush;
        push(elementToPush);
      } else if(command == "end"){
      } else {cout << "command not recognised"<< endl;};
    }while(command != "end");
}


//****************************************************************************************************************************************


int main(int argc, char * argv[]){
  init();  
  test();
  cout << "The stacksize is: "; //Gibt die groesse vom Stapel aus
  cout << stack_define.position;
  cout << "\n" << "The top element is: "; //gibt das oberste Element aus
  cout << *dynamic_array;
  clear();  
  return 0;

}

[Karl H. (kbuchegg)]

Wenn diese Initialisierung läuft

int *dynamic_array = new int[stack_define.size_array];

welchen Wert hat dann stack_define.size_array?

Hinweis: Es ist nicht der, den du glaubst.

[Rufus Τ. F. (rufus)]

Wenn das Programm "abkackt", ist es sinnvoll, das mal im Debugger laufen 
zu lassen. Damit kannst Du nämlich herausfinden, was genau 
schiefläuft.

Was mir auffällt, ist, daß Du Deine Struktur "stack_define" nirgendwo 
initialisierst, aber Dein "dynamisches Array" mit einem Element dieser 
Struktur erzeugst.

> int *dynamic_array = new int[stack_define.size_array];

Woher aber kommt der Wert, der hier in stack_define.size_array steht?

[Karl H. (kbuchegg)]

> dynamic_array = dynamic_array -1;

Autsch.

[Karl H. (kbuchegg)]

Funtkion push

 void push(int element){ //legt ein neues Element oben auf den Stappel
     stack_define.position = stack_define.position + 1; // die Anzahl Elemente nehmen zu
     
     if (stack_define.position > stack_define.size_array){ // Wenn es mehr Elemente gibt als das Array gross ist
           int copy_array[stack_define.position]; //erstellt ein Zwischenspeicherarray
           for (int i=0 ; i<stack_define.position ;i++){ //Umkupieren der Elemente
               copy_array[i] = dynamic_array[i];
           }

Du hast doch im alten Array keine stack_define.position Anzahl von 
Elementen, sondern nur stack_define.size_array

           delete [] dynamic_array; //dynamic array Elemente werden geloescht

So weit so gut. Das Array existiert danach nicht mehr.

           while (stack_define.position > stack_define.size_array){ //Dann wird die Arraygroesse so lange verdoppelt, bis das Array groesser als die Anzahl Elemente ist.
                 stack_define.size_array = 2*(stack_define.size_array);
           }

OK, kann man so machen, muss man aber nicht. Der Stack wächst nur um 1 
Element. D.h. 1 mal verdoppeln reicht völlig aus

           for (int i=0 ; i<stack_define.position; i++){ //Nun werden die Copy Elemente wieder in das nun groessere Array kopiert
               dynamic_array[i] = copy_array[i];
           }

Autsch. Das Array wurde vorher gelöscht. Es existiert nicht mehr! Du 
kannst nicht in ein nicht existierendes Array Werte reinschreiben.

     dynamic_array = dynamic_array +1;
     *dynamic_array = element; //Dem obersten Element wird der Wert von der Einageb "element" zugeordnet

Das geht gar nicht. Du veränderst dir den einzigen Pointer den du hast, 
der auf den Anfang der Daten zeigt. Diesen Pointer brauchst du aber, 
weil du ihn beim delete[] angeben musst.

[Daniel H. (danielch)]

Hello Hans,

n paar Tipps:
Zugriffe auf die Elemente des Arrays mit 
dynamic_array[stack_define.position]
anstatt mit solchen Konstrukten:
  dynamic_array = dynamic_array +1;
  *dynamic_array = element;
diese Verändern den "Basispointer" auf dein Array, wenn dieser am 
Schluss nicht mehr an den gleichen Ort zeigt, bekommst du deine 
beschriebene Fehlermeldung.

In push():
Nach dem delete []  dynamic_array; muss ein dynamic_array = new 
int[2*...]
kommen, ansonsten ist an der Stelle, wo dynamic_array hinzeigt, kein 
Speicher reserviert, das kann zu Fehlern führen. (Programmabsturz).

Wenn du diese 2 Dinge konsequent korrigierst, sollte es so 
funktionieren, wie gewünscht.

lg dänu

[Karl H. (kbuchegg)]

Alles in allem: massenhaft Fehler.

Punkt 1:
Wenn du schon eine Struktur machst, um deinen Stack zu kapseln, dann 
musst du das schon konsequent machen. Das bedeutet: Entweder alle 
Stackbeschreibungen kommen da rein oder aber du sparst dir fürs erste 
die Struktur.

Punkt 2:
mitzeichnen!
Mal dir auf einem Zettel auf, was du tust

So beginnt der Stack (wenn du ihn dann korrekt initialisierst)

    position   0
    size       2        +---+---+
    data  ------------->|   |   |
                        +---+---+

Und jetzt spielst du Computer und arbeitest dein Programm mal mit Papier 
und Bleistift auf dem Zettel durch. Du machst all das, was dir dein 
Programm vorschreibt, was du zu tun hast.

[Karl H. (kbuchegg)]

Die ganze doppelte Umkopieraktion ist sinnlos. Wozu? Mach genau das, was 
in deiner Aufgabenbeschreibung steht:

*   allokiere ein Array, das doppelt so groß ist, wie das alte
*   Kopiere die Daten aus dem alten Array ins Neue
*   delete das alte Array
*  (und was nicht in der Aufgabenbeschriebung steht)aktiviere das neue
   Array, indem du den frisch allokierten Pointer deiner
   Stack-Array-Pointer-Variablen zuweist, so das in der weiteren
   Verarbeitung dann dieses neue Array benutzt wird.

[Kurt T. (kurtisblow)]

Vielen dank erstmal für die vielen Antworten.
Ich bin noch Neugling im Programmieren, habe keinerlei Vorkentnisse an 
die Uni mitgebracht und musste vor 40 Tagen damit anfangen, daher mache 
noch sehr viele Fehler.
Dann versuche ich mal die Fehler zu beheben.

[Kurt T. (kurtisblow)]

So, habe einmal versucht eure Tipps zu nutzen und das Programm 
verändert.
Leider funktioniert es noch immer nicht, habe alles nachgeprüft 
(aufgeschrieben), finde aber keinen Fehler. Beide Compiler (Visual 2008 
und Devc++) melden keine Fehler oder Warnungen. Komischerweise sagt mir 
Visual sowiso garnichts mehr, auch keine Syntaxfehler. Bei Visual 
"kackt" mir das Programm nur beim Befehl "end" ab, bei Devc++ schon wenn 
ich den "push" Befehl eingebe. Wie genau kann ich eigentlich hier einen 
Code direkt als Code einfügen?

[cpp]

#include <stdlib.h>
#include <iostream>
#include <string>
using namespace std;


//****************************************************************************************************************************************

struct stack{ //Definiert ein Struct
  int size_array; //Arraygroesse
  int position; //Stapelgroesse (pointer zeigt auf oberstes Element)
}stack_define;

int *dynamic_array = new int[2]; //Dies ist das dynamsche Array

//****************************************************************************************************************************************

void init() { //inizialisiert den struct dynamic_stapel

  stack stack_define = {2,0}; 
}

//****************************************************************************************************************************************

int pop(){ // nimmt das oberste Element vom Stapel und loescht es, ebenfalls wird der Zeiger auf das Element darunter gerichtet
  if (stack_define.position > 0){ // Wenn es mindestens 1 Element gibt
    stack_define.position = stack_define.position -1;// Elemente nehmen ab
  }
  return 0; //Soll zeigen, dass der Stapel um 1 Element abnimmt    
}

//****************************************************************************************************************************************

void push(int element){ //legt ein neues Element oben auf den Stappel
     stack_define.position = stack_define.position + 1; // die Anzahl Elemente nehmen zu
   
   if (stack_define.position > stack_define.size_array){ // Wenn es mehr Elemente gibt als das Array gross ist
       int copy_array[stack_define.position]; //erstellt ein Zwischenspeicherarray
       for (int i=0 ; i<stack_define.position ;i++){ //Umkupieren der Elemente
         copy_array[i] = dynamic_array[i];
       }
       delete [] dynamic_array; //dynamic array Elemente werden geloescht
       while (stack_define.position > stack_define.size_array){ //Dann wird die Arraygroesse so lange verdoppelt, bis das Array groesser als die Anzahl Elemente ist.
                 stack_define.size_array = 2*(stack_define.size_array);
       }
       dynamic_array = new int[stack_define.size_array]; //Kreiert ein neues dynamisches Array.
       for (int i=0 ; i<stack_define.position; i++){ //Nun werden die Copy Elemente wieder in das nun groessere Array kopiert
         dynamic_array[i] = copy_array[i];
       }    
   }      
}

//****************************************************************************************************************************************

int size() { //gibt die groesse des Stapels an  
  return stack_define.position; 
}


//****************************************************************************************************************************************


void clear() { //Loescht den ganzen Stapel
  delete [] dynamic_array;  
}


//****************************************************************************************************************************************


//Dieses Funktion implementiert eine Testumgebung f&#65533;r den Stack
void test() {
    cout << "The program has been startet without any arguments." << endl;
    cout << "The program enters the stack test mode:" << endl;
    cout << "Enter one of the commands: push, pop, end" << endl;
    string command;
    do{
      cin >> command;
      if (command == "pop"){
        cout << pop() << endl;
      } else if (command == "push"){
        cout << "element?";
        int elementToPush;
        cin >> elementToPush;
        push(elementToPush);
      } else if(command == "end"){
      } else {cout << "command not recognised"<< endl;};
    }while(command != "end");
}


//****************************************************************************************************************************************


int main(int argc, char * argv[]){
  init();   
  test();
  cout << "The stacksize is: "; //Gibt die groesse vom Stapel aus
  cout << stack_define.position;
  cout << "\n" << "The top element is: "; //gibt das oberste Element aus
  cout << dynamic_array[stack_define.position];
  clear();  
  return 0;

}

[Karl H. (kbuchegg)]

Dafür hast du wieder neue Fehler eingebaut

void init() { //inizialisiert den struct dynamic_stapel

  stack stack_define = {2,0}; 
}

In dieser Funktionj wird eine neue Variable namens stack_define 
angelegt. Diese wird auch initialisiert. Und wenn die Funktion verlassen 
wird, wird sie wieder zerstört.

Diese funktionslokale Variable hat NICHTS mit der gleichnamigen globalen 
Variablen zu tun, die du hier

struct stack{ //Definiert ein Struct
  int size_array; //Arraygroesse
  int position; //Stapelgroesse (pointer zeigt auf oberstes Element)
}stack_define;

erzeugst und in all den anderen Funktionen benutzt.

Fazit: Diese globale Variable ist nie (von dir) initialisiert worden.

[Karl H. (kbuchegg)]

In Push

Das ist deine Funktion

void push(int element){ //legt ein neues Element oben auf den Stappel
     stack_define.position = stack_define.position + 1; // die Anzahl Elemente nehmen zu
   
   if (stack_define.position > stack_define.size_array){ // Wenn es mehr Elemente gibt als das Array gross ist
       int copy_array[stack_define.position]; //erstellt ein Zwischenspeicherarray
       for (int i=0 ; i<stack_define.position ;i++){ //Umkupieren der Elemente
         copy_array[i] = dynamic_array[i];
       }
       delete [] dynamic_array; //dynamic array Elemente werden geloescht
       while (stack_define.position > stack_define.size_array){ //Dann wird die Arraygroesse so lange verdoppelt, bis das Array groesser als die Anzahl Elemente ist.
                 stack_define.size_array = 2*(stack_define.size_array);
       }
       dynamic_array = new int[stack_define.size_array]; //Kreiert ein neues dynamisches Array.
       for (int i=0 ; i<stack_define.position; i++){ //Nun werden die Copy Elemente wieder in das nun groessere Array kopiert
         dynamic_array[i] = copy_array[i];
       }    
   }

Annahme: Du hast bereits 2 Elemente im Stack (auch wenn ich in deinem 
Code nirgends die Stelle entdecken kann, wo du das einzufügende Element 
auch tatsächlich ins Array schreibst)

So ist die Situation

  position    2
  size        2
                   +---+---+
  dynamic  ------->| 6 | 7 |
                   +---+---+

Jetzt kommt ein Aufruf von  Push( 9 )

Was passiert?

     stack_define.position = stack_define.position + 1; // die Anzahl Elemente nehmen zu

OK. Machen wir mal

  position    3
  size        2
                   +---+---+
  dynamic  ------->| 6 | 7 |
                   +---+---+

   if (stack_define.position > stack_define.size_array){ // Wenn es mehr Elemente gibt als das Array gross ist

Schau auf die Zeichnung. Ist position größer als size? position ist 3, 
size ist 2, also ist die Bedingung wahr. Das if wird genommen

       int copy_array[stack_define.position]; //erstellt ein Zwischenspeicherarray

Aha. Eine neue Variable names copy wird erzeugt. Das machen wir mal am 
Zettel


  position    3
  size        2
                   +---+---+
  dynamic  ------->| 6 | 7 |
                   +---+---+

  copy
  +---+---+---+
  |   |   |   |
  +---+---+---+

Weiter im Code. Was passiert als nächstes?

       for (int i=0 ; i<stack_define.position ;i++){ //Umkupieren der Elemente
         copy_array[i] = dynamic_array[i];
       }

das versucht position Anzahl Elemente von dynamic nach copy zu kopieren. 
Wie groß ist denn position? position hat den Wert 3. Schau auf deinen 
Zettel: dynamic hat keine 3 Elemente! Da sind nur 2!
Möööööööööp  Array Zugriff Out of Bounds!

[Karl H. (kbuchegg)]

Warum reißt du die Dinge auseinander?
Mach doch alles in die Struktur rein (und nenn deine Variablen kürzer. 
Da tippt man sich ja einen Ast ohne das es was bringt.

struct stack {
  int  top;      // an diese Stelle in den Daten wird das nächste
                 // zu pushende Element geschrieben
  int  size;     // allokierte Speichergröße des Stacks
  int *data;     // Array, welches die Stackwerte hält
}
myStack;

******
* Initialisiert den Stack
*
void init() {
  myStack.top = 0;
  myStack.size = 2;
  myStack.data = new int[ myStack.size ];
}

ganz einfach, ganz konventionell runtercoden. Ohne zu künsteln. Die 
Funktion init sorgt dafür, dass alle Member er Struktur einen gültigen 
Startwert haben.


Zur Funktion push:
Wenn du durcheinanderkommst, dann formulier dir erst mal die Funktion 
umgangssprachlich

void push( int value )
{
  // erst mal nachsehen, ob das Array vergrößert werden muss
  {
    // Ja -> es muss vergrößert werden
    // dazu wird ein neues Array mit der doppelten Größe dynamisch erzeugt

    // dann alle bisherigen Daten in dieses neue Array kopiert

    // das alte Array gelöscht

    // und der Pointer auf die neuen Daten an data zugewiesen
    // und vermerkt, dass das Array jetzt doppelt so groß ist
  }

  // Alles ok. Array ist jetzt auf jeden Fall groß genug
  // jetzt kann das zu pushende Element ins Array geschrieben werden
  // und zwar dorthin, wo uns top sagt. Denn top enthält ja immer den
  // Index an den das nächste Element zu schreiben ist

  // und zu guter letzt wird noch vermerkt, dass jetzt 1 Element mehr im Array ist
  // das nächste zu pushende Element kommt daher um 1 weiter
}

Einverstanden mit dieser umgangssprachlichen Beschreibung was zu tun 
ist? Es ist wichtig, dass du dich davon überzeugst, dass diese 
Beschreibung ein richtiges Ergebnis liefern wird! Denn das ist der Plan 
dessen wie wir uns vorstellen, dass die Funktion arbeiten soll. Und wenn 
der Plan schon nicht stimmt, dann wird auch das Programm nachher nicht 
richtig sein.

Einverstanden? Ja? Dann gehen wir daran die Details einzusetzen

void push( int value )
{
  // erst mal nachsehen, ob das Array vergrößert werden muss
  if( myStack.top >= myStack.size )
  {
    // Ja -> es muss vergrößert werden
    // dazu wird ein neues Array mit der doppelten Größe dynamisch erzeugt
    int *newData = new int [ 2 * myStack.size ];

    // dann alle bisherigen Daten in dieses neue Array kopiert
    for( int i = 0; i < myStack.size; ++i )
      newData[i] = myStack.data[i];

    // das alte Array gelöscht
    delete [] myStack.data;

    // und der Pointer auf die neuen Daten an data zugewiesen
    // und vermerkt, dass das Array jetzt doppelt so groß ist
    myStack.data = newData;
    myStack.size = 2 * myStack.size;
  }

  // Alles ok. Array ist jetzt auf jeden Fall groß genug
  // jetzt kann das zu pushende Element ins Array geschrieben werden
  // und zwar dorthin, wo uns top sagt. Denn top enthält ja immer den
  // Index an den das nächste Element zu schreiben ist
  myStack.data[top] = value;

  // und zu guter letzt wird noch vermerkt, dass jetzt 1 Element mehr im Array ist
  // das nächste zu pushende Element kommt daher um 1 weiter
  myStack.top = myStack.top + 1;
}

Und wenn ich jetzt beim Tippen hier im Forum nicht allzuviele Tippfehler 
gemacht habe, dann müsste das funktionieren.

[Läubi .. (laeubi)]

Alles in allem wäre es vermutlich ziel führenden wenn man nicht die 
ganze Aufgabe auf einen Schwung lösen will.

Ich würde erst mal mit einem statischem Array beginnen und dann mit 
einer Funktion, z.B. push beginnen. Wenn das klappt kann man den rest 
implementieren und zum Schluss die dynamische Speicherverwaltung 
dazupacken.

[Purzel H. (hacky)]

Mit einer PC-IDE kann man sehr gut durch den Singlesteppen. So findet 
man alle solchen Fehler.