Probleme bei Programmieraufgabe

Kurt T. #2412666
Lesenswert?
• ▲
▼ 
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?


1
#include <stdlib.h>

2
#include <iostream>

3
#include <string>

4
using namespace std;

5


6


7
//****************************************************************************************************************************************

8


9
struct stack{ //Definiert ein Struct

10
    int size_array; //Arraygroesse

11
    int position; //Stapelgroesse (pointer zeigt auf oberstes Element)

12
    }stack_define;

13


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

15


16
//****************************************************************************************************************************************

17


18
void init() { //inizialisiert den struct dynamic_stapel

19


20
    stack_define.size_array = 2;

21
    stack_define.position =0;

22
}

23


24
//****************************************************************************************************************************************

25


26
int pop(){ // nimmt das oberste Element vom Stapel und loescht es, ebenfalls wird der Zeiger auf das Element darunter gerichtet

27
    if (stack_define.position > 0){ // Wenn es mindestens 1 Element gibt

28
        stack_define.position = stack_define.position -1;// Elemente nehmen ab

29
        dynamic_array = dynamic_array -1;

30
    }

31
    return 0; //Soll zeigen, dass der Stapel um 1 Element abnimmt    

32
}

33


34
//****************************************************************************************************************************************

35


36
void push(int element){ //legt ein neues Element oben auf den Stappel

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

38
     

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

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

41
           for (int i=0 ; i<stack_define.position ;i++){ //Umkupieren der Elemente

42
               copy_array[i] = dynamic_array[i];

43
           }

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

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

46
                 stack_define.size_array = 2*(stack_define.size_array);

47
           }

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

49
               dynamic_array[i] = copy_array[i];

50
           }       

51
     }

52
     dynamic_array = dynamic_array +1;

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

54
}

55


56
//****************************************************************************************************************************************

57


58
int size() { //gibt die groesse des Stapels an   

59
    return stack_define.position;

60
}

61


62


63
//****************************************************************************************************************************************

64


65


66
void clear() { //Loescht den ganzen Stapel

67
    delete [] dynamic_array;  

68
}

69


70


71
//****************************************************************************************************************************************

72


73


74
//Dieses Funktion implementiert eine Testumgebung f&#65533;r den Stack

75
void test() {

76
    cout << "The program has been startet without any arguments." << endl;

77
    cout << "The program enters the stack test mode:" << endl;

78
    cout << "Enter one of the commands: push, pop, end" << endl;

79
    string command;

80
    do{

81
      cin >> command;

82
      if (command == "pop"){

83
        cout << pop() << endl;

84
      } else if (command == "push"){

85
        cout << "element?";

86
        int elementToPush;

87
        cin >> elementToPush;

88
        push(elementToPush);

89
      } else if(command == "end"){

90
      } else {cout << "command not recognised"<< endl;};

91
    }while(command != "end");

92
}

93


94


95
//****************************************************************************************************************************************

96


97


98
int main(int argc, char * argv[]){

99
  init();  

100
  test();

101
  cout << "The stacksize is: "; //Gibt die groesse vom Stapel aus

102
  cout << stack_define.position;

103
  cout << "\n" << "The top element is: "; //gibt das oberste Element aus

104
  cout << *dynamic_array;

105
  clear();  

106
  return 0;

107


108
}
Beitrag melden Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Markierten Text zitieren Antwort Antwort mit Zitat
Rufus Τ. F. Persönliche Seite #2412683
Lesenswert?
• ▲
▼ 
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?
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Karl H. #2412688
Lesenswert?
• ▲
▼ 
Funtkion push

1
 void push(int element){ //legt ein neues Element oben auf den Stappel

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

3
     

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

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

6
           for (int i=0 ; i<stack_define.position ;i++){ //Umkupieren der Elemente

7
               copy_array[i] = dynamic_array[i];

8
           }

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

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

So weit so gut. Das Array existiert danach nicht mehr.
1
           while (stack_define.position > stack_define.size_array){ //Dann wird die Arraygroesse so lange verdoppelt, bis das Array groesser als die Anzahl Elemente ist.

2
                 stack_define.size_array = 2*(stack_define.size_array);

3
           }

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

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

2
               dynamic_array[i] = copy_array[i];

3
           }


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

1
     dynamic_array = dynamic_array +1;

2
     *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.
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Daniel H. #2412689
Lesenswert?
• ▲
▼ 
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
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Karl H. #2412699
Lesenswert?
• ▲
▼ 
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.
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Karl H. #2412707
Lesenswert?
• ▲
▼ 
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.
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Kurt T. #2412755
Lesenswert?
• ▲
▼ 
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]
1
#include <stdlib.h>

2
#include <iostream>

3
#include <string>

4
using namespace std;

5


6


7
//****************************************************************************************************************************************

8


9
struct stack{ //Definiert ein Struct

10
  int size_array; //Arraygroesse

11
  int position; //Stapelgroesse (pointer zeigt auf oberstes Element)

12
}stack_define;

13


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

15


16
//****************************************************************************************************************************************

17


18
void init() { //inizialisiert den struct dynamic_stapel

19


20
  stack stack_define = {2,0}; 

21
}

22


23
//****************************************************************************************************************************************

24


25
int pop(){ // nimmt das oberste Element vom Stapel und loescht es, ebenfalls wird der Zeiger auf das Element darunter gerichtet

26
  if (stack_define.position > 0){ // Wenn es mindestens 1 Element gibt

27
    stack_define.position = stack_define.position -1;// Elemente nehmen ab

28
  }

29
  return 0; //Soll zeigen, dass der Stapel um 1 Element abnimmt    

30
}

31


32
//****************************************************************************************************************************************

33


34
void push(int element){ //legt ein neues Element oben auf den Stappel

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

36
   

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

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

39
       for (int i=0 ; i<stack_define.position ;i++){ //Umkupieren der Elemente

40
         copy_array[i] = dynamic_array[i];

41
       }

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

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

44
                 stack_define.size_array = 2*(stack_define.size_array);

45
       }

46
       dynamic_array = new int[stack_define.size_array]; //Kreiert ein neues dynamisches Array.

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

48
         dynamic_array[i] = copy_array[i];

49
       }    

50
   }      

51
}

52


53
//****************************************************************************************************************************************

54


55
int size() { //gibt die groesse des Stapels an  

56
  return stack_define.position; 

57
}

58


59


60
//****************************************************************************************************************************************

61


62


63
void clear() { //Loescht den ganzen Stapel

64
  delete [] dynamic_array;  

65
}

66


67


68
//****************************************************************************************************************************************

69


70


71
//Dieses Funktion implementiert eine Testumgebung f&#65533;r den Stack

72
void test() {

73
    cout << "The program has been startet without any arguments." << endl;

74
    cout << "The program enters the stack test mode:" << endl;

75
    cout << "Enter one of the commands: push, pop, end" << endl;

76
    string command;

77
    do{

78
      cin >> command;

79
      if (command == "pop"){

80
        cout << pop() << endl;

81
      } else if (command == "push"){

82
        cout << "element?";

83
        int elementToPush;

84
        cin >> elementToPush;

85
        push(elementToPush);

86
      } else if(command == "end"){

87
      } else {cout << "command not recognised"<< endl;};

88
    }while(command != "end");

89
}

90


91


92
//****************************************************************************************************************************************

93


94


95
int main(int argc, char * argv[]){

96
  init();   

97
  test();

98
  cout << "The stacksize is: "; //Gibt die groesse vom Stapel aus

99
  cout << stack_define.position;

100
  cout << "\n" << "The top element is: "; //gibt das oberste Element aus

101
  cout << dynamic_array[stack_define.position];

102
  clear();  

103
  return 0;

104


105
}
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Karl H. #2412763
Lesenswert?
• ▲
▼ 
Dafür hast du wieder neue Fehler eingebaut

1
void init() { //inizialisiert den struct dynamic_stapel

2


3
  stack stack_define = {2,0}; 

4
}


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
1
struct stack{ //Definiert ein Struct

2
  int size_array; //Arraygroesse

3
  int position; //Stapelgroesse (pointer zeigt auf oberstes Element)

4
}stack_define;

erzeugst und in all den anderen Funktionen benutzt.

Fazit: Diese globale Variable ist nie (von dir) initialisiert worden.
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Karl H. #2412777
Lesenswert?
• ▲
▼ 
In Push

Das ist deine Funktion
1
void push(int element){ //legt ein neues Element oben auf den Stappel

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

3
   

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

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

6
       for (int i=0 ; i<stack_define.position ;i++){ //Umkupieren der Elemente

7
         copy_array[i] = dynamic_array[i];

8
       }

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

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

11
                 stack_define.size_array = 2*(stack_define.size_array);

12
       }

13
       dynamic_array = new int[stack_define.size_array]; //Kreiert ein neues dynamisches Array.

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

15
         dynamic_array[i] = copy_array[i];

16
       }    

17
   }


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?


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

OK. Machen wir mal

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

1
   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


1
       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?
1
       for (int i=0 ; i<stack_define.position ;i++){ //Umkupieren der Elemente

2
         copy_array[i] = dynamic_array[i];

3
       }

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!
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Karl H. #2412800
Lesenswert?
• ▲
▼ 
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.

1
struct stack {

2
  int  top;      // an diese Stelle in den Daten wird das nächste

3
                 // zu pushende Element geschrieben

4
  int  size;     // allokierte Speichergröße des Stacks

5
  int *data;     // Array, welches die Stackwerte hält

6
}

7
myStack;

8


9
******

10
* Initialisiert den Stack

11
*

12
void init() {

13
  myStack.top = 0;

14
  myStack.size = 2;

15
  myStack.data = new int[ myStack.size ];

16
}

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

1
void push( int value )

2
{

3
  // erst mal nachsehen, ob das Array vergrößert werden muss

4
  {

5
    // Ja -> es muss vergrößert werden

6
    // dazu wird ein neues Array mit der doppelten Größe dynamisch erzeugt

7


8
    // dann alle bisherigen Daten in dieses neue Array kopiert

9


10
    // das alte Array gelöscht

11


12
    // und der Pointer auf die neuen Daten an data zugewiesen

13
    // und vermerkt, dass das Array jetzt doppelt so groß ist

14
  }

15


16
  // Alles ok. Array ist jetzt auf jeden Fall groß genug

17
  // jetzt kann das zu pushende Element ins Array geschrieben werden

18
  // und zwar dorthin, wo uns top sagt. Denn top enthält ja immer den

19
  // Index an den das nächste Element zu schreiben ist

20


21
  // und zu guter letzt wird noch vermerkt, dass jetzt 1 Element mehr im Array ist

22
  // das nächste zu pushende Element kommt daher um 1 weiter

23
}


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

1
void push( int value )

2
{

3
  // erst mal nachsehen, ob das Array vergrößert werden muss

4
  if( myStack.top >= myStack.size )

5
  {

6
    // Ja -> es muss vergrößert werden

7
    // dazu wird ein neues Array mit der doppelten Größe dynamisch erzeugt

8
    int *newData = new int [ 2 * myStack.size ];

9


10
    // dann alle bisherigen Daten in dieses neue Array kopiert

11
    for( int i = 0; i < myStack.size; ++i )

12
      newData[i] = myStack.data[i];

13


14
    // das alte Array gelöscht

15
    delete [] myStack.data;

16


17
    // und der Pointer auf die neuen Daten an data zugewiesen

18
    // und vermerkt, dass das Array jetzt doppelt so groß ist

19
    myStack.data = newData;

20
    myStack.size = 2 * myStack.size;

21
  }

22


23
  // Alles ok. Array ist jetzt auf jeden Fall groß genug

24
  // jetzt kann das zu pushende Element ins Array geschrieben werden

25
  // und zwar dorthin, wo uns top sagt. Denn top enthält ja immer den

26
  // Index an den das nächste Element zu schreiben ist

27
  myStack.data[top] = value;

28


29
  // und zu guter letzt wird noch vermerkt, dass jetzt 1 Element mehr im Array ist

30
  // das nächste zu pushende Element kommt daher um 1 weiter

31
  myStack.top = myStack.top + 1;

32
}


Und wenn ich jetzt beim Tippen hier im Forum nicht allzuviele Tippfehler 
gemacht habe, dann müsste das funktionieren.
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Läubi .. Persönliche Seite #2412861
Lesenswert?
• ▲
▼ 
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.
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren