3. Stack mit Pointer

Stack mit Pointer

  • D

    Hi.

    Ich möchte einen Stack bauen, der nur mit Pointern arbeitet. Bisher verwende ich folgenden Code:

    typedef struct{
		int* stackPtr;
		int* firstPtr;
	} stack;

stack* mainPtr;
stack s;

stack* newStack() {
	stack* refPtr;
	refPtr = &s;
	s.firstPtr = s.stackPtr;
	return refPtr;
}

void push(stack* refPtr, int val) {
	stack s = *refPtr;
	++refPtr;
	*s.stackPtr = val;
	mainPtr=refPtr;
}

int main() {
	mainPtr = newStack();
	push(mainPtr,13);
	return 0;

}

    Das Programm compiliert ohne Fehler, stürzt jedoch bei Ausführung ab und ich weiß einfach nicht, woran das liegt.

    Kann mir jemand bitte sagen, was ich falsch mache?

    0
  • _

    Fehlermeldung? Zeile?

    0
  • K
     

    #include <iostream> 

struct stack
{
    int* stackPtr; 
    int* firstPtr; 
}; 

stack* mainPtr; 
stack s; 

stack* newStack()
{ 
    stack* refPtr; 
    refPtr = &s; 
    s.firstPtr = s.stackPtr; 
    return refPtr; 
} 

void push(stack* refPtr, int val)
{ 
    stack s = *refPtr; 
    ++refPtr; 
    s.stackPtr = new int(val); 
    mainPtr=refPtr; 
} 

int main()
{ 
    mainPtr = newStack(); 
    push(mainPtr,13); 

    std::cin.get(); // Siehe Konsolen-FAQ!
}

    Zeile 24?

    0
  • Mod

    Deine Stackelemente liegen (und jetzt nicht durch die Namensgebung verwirren lassen) auf dem Programmstack. Und da darfst du nicht einfach wild herumschreiben. Du musst deinen Stack mittels new auf dem Heap konstruieren.

    0
  • V

    dbdevil schrieb:

    Ich möchte einen Stack bauen, der nur mit Pointern arbeitet.

    Das wird so leider nichts. Ich sehe kein new und keinen Speicherplatz, wo die ints landen können. Es reicht nicht, einen Zeiger zu haben, um dort einen int abzulegen, der Zeiger muß auch auf Speicherplatz zeigen, der Dir gehört.

    0
  • K

    volkard schrieb:

    der Zeiger muß auch auf Speicherplatz zeigen, der Dir gehört.

    ReadProcessMemory()? :p

    0
  • S

    dbdevil schrieb:

    typedef struct{
		int* stackPtr;
		int* firstPtr;
	} stack;

    Das kann man in C++ auch abkürzen:

    struct stack {
  ...
};

    Was bedeutet genau "mit Zeigern"? Willst Du eine einfach-verkette Liste für den Stack benutzen oder ein "dynamisches" Array? Worauf sollen stackPtr und firstPtr zeigen?

    stack* mainPtr;
stack s;

    Globale Variablen sind schlecht.

    stack* newStack() {
	stack* refPtr;
	refPtr = &s;
	s.firstPtr = s.stackPtr;
	return refPtr;
}

    Wofür ist s.firstPtr=s.stackPtr; ? Diese Variablen wurden nie "richtig" initialisiert. Da sie statische Lebenszeit besitzen, sind es Nullzeiger.

    void push(stack* refPtr, int val) {
	stack s = *refPtr;
	++refPtr;
	*s.stackPtr = val;
	mainPtr=refPtr;
}

    s ist eine lokale Kopie
    refPtr zeigt irgendwo ins Nirvana
    *s.stackPtr derefereziert einen Nullzeiger.
    mainPtr wird auch ungültig.

    int main() {
	mainPtr = newStack();
	push(mainPtr,13);
	return 0;
}

    Das Programm compiliert ohne Fehler, stürzt jedoch bei Ausführung ab und ich weiß einfach nicht, woran das liegt.

    Dass ein Programm kompiliert ist noch keine Garantie dafür, dass man keine Fehler gemacht hat, wie Du siehst.

    Wiederhole aus Deinem C++ Buch das Kapitel über Zeiger. Mach Dir klar, dass Zeiger nicht automatisch auf irgendwas zeigen, wo man hinschreiben darf. Du bist dafür selbst verantwortlich.

    Gruß,
    SP

    0
  • D

    Huhu.

    Danke Sebastian Pizer - das war hilfreich. Der firstPtr war ursprünglich dazu gedacht eine Funktion isEmpty() zu bauen. Der mainPtr war nur für Testzwecke angelegt und hätte auch nicht global sein müssen.

    Ich habe es jetzt anders geschrieben und es funktioniert:

    typedef struct{
		int* stackPtr;
		int top;
	} stack;

stack s;

stack* newStack() {
	stack* refPtr = NULL;
	s.top = (int) 0;
	refPtr = &s;
	return refPtr;
}
void push(stack* refPtr, int val) {
	s = *refPtr;
	s.top++;
	if (s.stackPtr == NULL) {
		s.stackPtr = &val;
	}
	s.stackPtr++;
	*s.stackPtr = val;
}
    0

  • dbdevil, dein Code ist (immer noch) völliger Murks.
    Du hast die Verwendung von Zeigern immer noch nicht verstanden...

    Wenn du wirklich einen Stack in deinem Programm benötigst, dann verwende bitte std::stack<>.

    Wenn es nur ein Übungsprogramm für Zeiger sein soll, dann fange noch mal ganz von vorne an und überlege dir genau, was du in der Struktur 'stack' speichern willst.
    (mir fehlt insbesondere die Initialisierung des eigentlichen Stacks, d.h. anhand einer vorgegebenen Größe den Stack dynamisch zu erstellen).
    Außerdem solltest du zuerst auch mal den Sinn und die Verwendung von 'new' erlernen, denn dies fehlt in deinem Programm bisher...

    Anhand welchen Buchs bzw. Tutorials versuchst du denn bisher C++ zu erlernen?

    0
  • S

    dbdevil schrieb:

    typedef struct{
		int* stackPtr;
		int top;
	} stack;

    Willst Du C++ oder C programmieren?

    dbdevil schrieb:

    stack s;

    So eine globale Variable hat hier nichts zu suchen.

    dbdevil schrieb:

    stack* newStack() {
	stack* refPtr = NULL;
	s.top = (int) 0;
	refPtr = &s;
	return refPtr;
}

    Da Du einen Zeiger auf eine globale Variable zurückgibst, kannst Du scheinbar nicht mehrere Stacks gleichzeitig benutzen.

    dbdevil schrieb:

    void push(stack* refPtr, int val) {
    s = *refPtr;
    s.top++;
    if (s.stackPtr == NULL) {
        s.stackPtr = &val;
    }
    s.stackPtr++;
    *s.stackPtr = val;
}

    Zeile 2 kopiert eine stack-Struktur in die globale Struktur s
    Zeile 5 weist dem stackPtr-Element die Adresse einer lokalen kurzlebigen Variablen (val) zu, die nachdem die Funktion beendet wird aufhört zu existieren.
    Zeile 7 erhöht den Zeiger. Er zeigt nun irgendwo hin.
    Zeile 8 überschreibt *s.stackPtr -- eine Speicherstelle in der Du nichts verloren hast.

    Am besten schnappst Du Dir nochmal Dein C++ Buch, liest das Kapitel über Zeiger und Speicherverwaltung ( new , delete ) nochmal durch. Probiere dann mal zur Übung, den Stack als einfach verkette Liste zu implementieren. Du schnappst Dir dazu erst mal Stift und Zettel, malst ein paar Kästchen für Variablen auf und ein paar Pfeile für die Zeiger. Denk dran, dass nicht-statisce lokale Variablen i.d.R. kurzlebig sind. Bei einer einfach verkettenen Liste speichert jeder "Knoten" einen Zeiger auf den folgenden "Knoten" (oder einen Nullzeiger für das Ende). Hier mal ein Ansatz dazu:

    #include <iostream>

struct IntStackKnoten
{
  int wert;
  IntStackKnoten* drunter;
};

class IntStack
{
public:
  IntStack() : oben(0) {}
  ~IntStack();  // Im Destruktor musst Du "aufräumen"

  bool empty() const {return oben==0;}
  int top() const {return oben->wert;}

  void push(int);
  void pop();

private:
  IntStack(IntStack const&);            // soll undefiniert bleiben
  IntStack& operator=(IntStack const&); // soll undefiniert bleiben

  IntStackKnoten* oben;
};

IntStack::~IntStack()
{
  ... Aufräumen
}

void IntStack::push(int)
{
  ... Neuen Knoten im Freispeicher anlegen
}

void IntStack::pop()
{
  ... "Obersten" Knoten entfernen
}

int main()
{
  IntStack is;
  is.push(1);
  is.push(2);
  is.push(3);
  while (!is.empty()) {
    std::cout << is.top() << '\n';
    is.pop();
  }
}

    Die beiden Funktionen direkt unter dem "private:" definierst Du einfach nicht. Warum/Wieso/Weshalb spielt für diese Übung erstmal keine Rolle. Später solltest Du auch das nachholen.

    Gruß,
    SP

    0
Anmelden zum Antworten