Stapel(stack)

[hasso]

Hallo,

Ich hab eine Aufgabe :

Entwerfen Sie ein Programm (Datenentwurf und Modulentwurf als Struktogramm) zum
Hinzufügen von beliebig vielen Elementen in einen Stapel (stack) nach Wunsch.
Als Nutzdaten sollen jeweils der Name, das Alter und das Gehalt einer Person dienen.
Sehen Sie für jedes Element des Stapels einen passenden Strukturtyp vor.
Dieses Hinzufügen soll ein separates Modul: input übernehmen.
Anschließend sollen alle Elemente des Stapels gelesen, damit ausgegeben und gelöscht
werden. Dies soll ein separates Modul: output übernehmen.

Ich hab mich in Wikipedia schlau gemacht , und hab das Prinzip LIFO (last input first out)verstanden.

Ich möchte kein Struktogramm machen sondern es programmieren..
Kann mir jemand irgendwelche Tipps geben wie man solch ein Programm am besten vorgeht, gibts funktionen die für solche Programme gedacht sind
. ??

Gruß

[mahe]

Wird wohl auf eine einfache Liste hinauslaufen.
Einfach verkettet wird höchstwahrscheinlich reichen.

Das heißt, jedes Element das du Einfügst hat neben seinen Daten auch einen Zeiger auf seinen Nachfolger. So bekommst Du eine Liste und kannst Dich durchhangeln. In Deinem Programm brauchst Du dann mindestens einen Zeiger auf das erste Element. Zusätzlich kannst Du auch einen auf das letzten Element haben.

Bei LIFO kannst Du immer am Anfang der Liste Elemente einfügen und auch am Anfang löschen. Das ist wohl auch die einfachste Variante.

[hasso]

o.k von zeiger hab ich noch wenig ahnung also ist es dringend notwendig mich erst mit zeigern auseinanderzustezen um die aufgabe lösen zu können..

hab eben mal nachgeguckt Zeiger:

Speicherbereiche können dynamisch reserviert, verwaltet und wieder gelöscht werden.
Mit Zeigern können Sie Datenobjekte direkt (call-by-reference) an Funktionen übergeben.
Es lassen sich Funktionen als Argumente an andere Funktionen übergeben.
Rekursive Datenstrukturen wie Listen und Bäume lassen sich fast nur mit Zeigern bewerkstelligen.
Es lässt sich ein typenloser Zeiger (void definieren, womit Datenobjekte beliebigen Typs verarbeitet werden können.

Wenn ich die kreterien kann müsst ich die aufgabe lösen können oder?

gruß

[goto anywhere*]

Du musst eigentlich nur folgendes wissen:
- Wie funktioniert malloc()?
- Was ist ein Stack?
- Was ist eine einfach verkettete Liste?

Eine Lösung ist dann auch rel. einfach zu programmieren:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _stackelement{
	char name[128];
	unsigned int alter;
	unsigned int gehalt;
	struct _stackelement *next;
}st_el;

st_el first_element;
int stack_empty=1;

void input(st_el new_element){
	static st_el *last_element;
	st_el *memory_for_element;

	if(stack_empty){
		first_element=new_element;
		first_element.next=NULL;
		stack_empty=0;
		last_element=&first_element;
	}
	else{
		memory_for_element=malloc(sizeof(st_el));
		*memory_for_element=new_element;
		memory_for_element->next=NULL;
		last_element->next=memory_for_element;
	}
}

void output(void){
	st_el *last_element=&first_element;
	unsigned int cnt=0;
	if(!stack_empty){
		while(last_element->next!=NULL)++cnt;
		printf(
			"%s\n%d\n%d\n\n",
			last_element->name,
			last_element->alter,
			last_element->gehalt
		);

		if(cnt!=0){
			free(last_element);
			for(last_element=&first_element;--cnt!=0;last_element=last_element->next);
			last_element->next=NULL;
		}
		else{
			strcpy(first_element.name,"");
			first_element.alter=0;
			first_element.gehalt=0;
			first_element.next=NULL;
			stack_empty=1;
		}
	}
}

int main(void){
	st_el el;

	strcpy(el.name,"Hans Meier");
	el.alter=99;
	el.gehalt=85630;
	input(el);

	output();
	getchar();
}

[hochtapel-freak]

goto anywhere; schrieb:

Du musst eigentlich nur folgendes wissen:
- Wie funktioniert malloc()?
- Was ist ein Stack?
- Was ist eine einfach verkettete Liste?

und wenn man rausgefunden hat, was ein stack ist, dann kommt man auch drauf, dass man dafür keine verkettete liste braucht.

[Tachyon]

hochtapel-freak schrieb:

goto anywhere; schrieb:

Du musst eigentlich nur folgendes wissen:
- Wie funktioniert malloc()?
- Was ist ein Stack?
- Was ist eine einfach verkettete Liste?

und wenn man rausgefunden hat, was ein stack ist, dann kommt man auch drauf, dass man dafür keine verkettete liste braucht.

Wenn die Anforderung ist, beliebig viele Elemente hinzufügen zu können, macht das aber schon Sinn...

[sothis_]

Tachyon schrieb:

hochtapel-freak schrieb:

goto anywhere; schrieb:

Du musst eigentlich nur folgendes wissen:
- Wie funktioniert malloc()?
- Was ist ein Stack?
- Was ist eine einfach verkettete Liste?

und wenn man rausgefunden hat, was ein stack ist, dann kommt man auch drauf, dass man dafür keine verkettete liste braucht.

Wenn die Anforderung ist, beliebig viele Elemente hinzufügen zu können, macht das aber schon Sinn...

warum? ein einfacher stack mit realloc() tut's auch. wenn man wirklich nur zugriff auf das erste element braucht ist dies sogar eher noch sinnvoller, als für jede anwendung gleich eine verkettete liste zu implementieren

[pedantic-freak]

sothis_ schrieb:

wenn man wirklich nur zugriff auf das erste element braucht ist dies sogar eher noch sinnvoller, als für jede anwendung gleich eine verkettete liste zu implementieren

so ist es. und dass man nur zugriff auf das oberste element hat, ist ja das, was einen stack ausmacht.

[Tachyon]

sothis_ schrieb:

Tachyon schrieb:

hochtapel-freak schrieb:

goto anywhere; schrieb:

Du musst eigentlich nur folgendes wissen:
- Wie funktioniert malloc()?
- Was ist ein Stack?
- Was ist eine einfach verkettete Liste?

und wenn man rausgefunden hat, was ein stack ist, dann kommt man auch drauf, dass man dafür keine verkettete liste braucht.

Wenn die Anforderung ist, beliebig viele Elemente hinzufügen zu können, macht das aber schon Sinn...

warum? ein einfacher stack mit realloc() tut's auch. wenn man wirklich nur zugriff auf das erste element braucht ist dies sogar eher noch sinnvoller, als für jede anwendung gleich eine verkettete liste zu implementieren

Bei großen Stracks ist realoc schädlich. Es reduziert die Performance und fragmentiert den Speicher. Da ist eine einfach-rückwärts verkettete Liste sinnvoller.
Mal davon abgesehen brauchts bei einem Stack Zugriff aufs letzte Element.

[sothis_]

Tachyon schrieb:

Bei großen Stracks ist realoc schädlich. Es reduziert die Performance und fragmentiert den Speicher. Da ist eine einfach-rückwärts verkettete Liste sinnvoller.
Mal davon abgesehen brauchts bei einem Stack Zugriff aufs letzte Element.

das problem hast du auch bei einer verketteten liste mit vielen knoten, malloc() und free() für jeden knoten aufzurufen hat den selben effekt. bei einer liste ist es das letzte element, ja. mit oberstes element meinte ich bildlich das erste element auf dem stack.

[goto anywhere*]

hasso wollte es mit einer einfach verketteten Liste realisieren, also habe ich's auch so gemacht.

[linklist-freak]

goto anywhere; schrieb:

hasso wollte es mit einer einfach verketteten Liste realisieren, also habe ich's auch so gemacht.

in hassos aufgabe ist keine verkettete gefordert. warum soll man sich's unnötig schwer machen?

[goto anywhere*]

Dann nimmt man wohl am besten gleich C++ und die STL, wenn man's auf Einfachheit absieht:

#include <iostream>
#include <cstdlib>
#include <string>
#include <stack>

typedef struct{
	unsigned int alter;
	unsigned int gehalt;
	std::string name;
}st_el;

int main(void){
	std::stack<st_el>	stack;
	st_el				el={0,0,"Name"};

	for(int cnt=0;cnt<100;++cnt)
		stack.push(el);

	for(int cnt=0;cnt<100;++cnt){
		el=stack.top(); stack.pop();
		std::cout<<el.alter<<", "<<el.gehalt<<", "<<el.name<<std::endl;
	}

	std::cin.get();
}

[Tachyon]

goto anywhere; schrieb:

Dann nimmt man wohl am besten gleich C++ und die STL, wenn man's auf Einfachheit absieht:

a) Soll er selbst einen Stack entwerfen, und nicht einen fertigen benutzen
b) Ist es durch aus ein Unterschied, ob man C oder C++ benutzt, vor allem, wenn in den Anforderungen C als Programmiersprache angegeben wird.

[RapIstMeinHobby]

goto anywhere; schrieb:

Dann nimmt man wohl am besten gleich C++ und die STL, wenn man's auf Einfachheit absieht:

#include <iostream>
#include <cstdlib>
#include <string>
#include <stack>

typedef struct{
	unsigned int alter;
	unsigned int gehalt;
	std::string name;
}st_el;

int main(void){
	std::stack<st_el>	stack;
	st_el				el={0,0,"Name"};

	for(int cnt=0;cnt<100;++cnt)
		stack.push(el);

	for(int cnt=0;cnt<100;++cnt){
		el=stack.top(); stack.pop();
		std::cout<<el.alter<<", "<<el.gehalt<<", "<<el.name<<std::endl;
	}

	std::cin.get();
}

kannst du mit diesem hässlichen kram bitte mal aus dem ansi c forum abhauen? danke.

[Laufentenwickler]

Entwerfe doch zuerst einen Stack mit einer Maximalhöhe, das Grundgerüst etwa so:

#define STACKMAX 100

typedef struct {
    int size;
    int data[STACKMAX];
} Stack;

void createStack(Stack* s) {...};
int pop(Stack* s);
void push(Stack* s, int val);

Hoffe das hilft. Machts doch nicht zu kompliziert. Er weiß noch nicht was Zeiger sind und ihr schlagt verkettete Listen vor. Scherzkekse. Lass die Finger davon und versuch dich an was einfachem.

[windozer]

das macht man aber mit einer liste, das wird ihm der prof in der vorlesung auch so gesagt haben. alles andere ist doch quatsch.

[goto anywhere*]

Laufentenwickler schrieb:

Entwerfe doch zuerst einen Stack mit einer Maximalhöhe, das Grundgerüst etwa so:

#define STACKMAX 100

typedef struct {
    int size;
    int data[STACKMAX];
} Stack;

void createStack(Stack* s) {...};
int pop(Stack* s);
void push(Stack* s, int val);

Hoffe das hilft. Machts doch nicht zu kompliziert. Er weiß noch nicht was Zeiger sind und ihr schlagt verkettete Listen vor. Scherzkekse. Lass die Finger davon und versuch dich an was einfachem.

Du meinst man sollte 'dynamisch' über den Haufen werfen?-Also so etwas in der Art?:

#define STACKLENGHT 10

const int POP=0;
const int PUSH=1;

typedef struct{
	unsigned int alter;
	unsigned int gehalt;
	char name[1024];
}st_el;

int stack(int push_or_pop,st_el *element){
	static st_el stack[STACKLENGHT]={0};
	static int st_ptr=0;

	if(push_or_pop==PUSH){
		if(st_ptr<STACKLENGHT){
			stack[st_ptr++]=*element;
			return 0;
		}
		else{
			return -1;
		}
	}
	else{
		if(st_ptr>0){
			*element=stack[--st_ptr];
			return 0;
		}
		else{
			return -1;
		}
	}
}

[B.B.]

windozer schrieb:

das macht man aber mit einer liste, das wird ihm der prof in der vorlesung auch so gesagt haben. alles andere ist doch quatsch.

Nö.
Vorzugsweise schätzt man die benötigte Größe ab und nimmt einen Speicherblock, der etwas größer ist.
Wird der Block trotdem mal zu klein, wählt man einen nächst größeren.
Oder noch besser, man legt einen zweiten Stack an.

[Laufentenwickler]

@goto anywhere: Nein, so meinte ich das bestimmt nicht. Eher so:

#define STACKMAX 100

typedef struct {
    int size;
    int data[STACKMAX];
} Stack;

void init(Stack* s) {
    s->size = 0;
};
int pop(Stack* s) {
    return s->data[--s->size];
};
void push(Stack* s, int val) {
    s->data[s->size++] = val;
}

...
Stack test;
init(test);
push(test, 1);
push(test, 2);
printf("%d", pop(test));
push(test, 3);
printf("%d", pop(test));
printf("%d", pop(test));

Das kann man dann noch mit Fehlererkennung (overflow, underflow) und dann durch ralloc erweitern, dann eventuell sich noch Gedanken über eine sinvolle Strategie für Stackgroße und Vergrößerung, und man hat schon was sehr brauchbares zusammen.