[ANSI C] Stos - dodawanie i zdejmowanie elementu, wyświetlanie stosu

0

Witam, mam za zadanie napisać strukturę ze stosem oraz funkcje obsługujące go czyli pop (zdjęcie elementu ze stosu) oraz push ( umieszczenie elementu na stosie). Przejrzałem pokaźną liczbę materiałów, jednak mam wrażenie, że to jeden z najgorzej dla kogoś początkującego wytłumaczonych tematów w tym języku. Albo też tylko ja nie rozumiem tego : P Po próbnych wywołaniach, teoretycznie wszystko się kompiluje, funkcje nie powodują przy używaniu błędów ale np po użyciu push, dodaje sobie elementy, jednak zarówno pop jak i print nie widzą efektu i wybijają, że stos jest pusty :c
Reasumując, gdyby ktoś mógł poprawić te funkcje i wyjaśnić łopatologicznie co co robi i dlaczego będę niezmiernie wdzięczny.

Na początek jak wygląda u mnie struktura dla stosu:

typedef struct wezel{
	int liczba;
	struct wezel *nast;
}wezel; 

No i funkcje:

 /*funkcja umieszczająca element na szczycie stosu*/
wezel *push(wezel *stos, int element){
	wezel* biezacy;
	if((biezacy=(wezel*)malloc(sizeof(wezel)))==NULL)
	return stos;
	else{
		biezacy->liczba=element;
		biezacy->nast=stos;
		stos=biezacy;
	}
	return stos;
}
/*funkcja zdejmująca element ze szczytu stosu*/
wezel *pop(wezel *stos,int element){
wezel *tmp;
if(stos!=NULL){
tmp=stos;
element=tmp->liczba;
stos=tmp->nast;
free(tmp);
return stos;
}
else{
fprintf(stderr,"Błąd brak danych\n");
return stos ;}
}
 

Oraz wyświetlanie stosu:

 
/*funkcja drukująca na stdout cały stos- wstawiam na wszelki wypadek, bo może tu jest problem*/
void print(wezel *stos){
	if(stos==NULL)
	printf("Brak elementów\n");
	else
		do{
			printf("%5d\n",stos->liczba);
			stos=stos->nast;
		}while (stos!=NULL);
	
}

Bonusowo załączam jak wyglądają u mnie wywołania tych funkcji w mainie:

 
print(stos);
push(stos,element);
pop(stos,element);

Pozdrawiam, draggie.

1

Tak na pierwszy rzut oka jest ok, ale chyba widzisz że NIGDZIE nie korzystasz z wartości zwracanej przez push i pop? No bo zrobiłeś push, zmienił ci się "wierzchołek stosu" a ty w main() cały czas masz stary wierzchołek. Albo robisz:

stos = push(stos, element);
stos = pop(stos, element);

Albo, co bardziej sensowne, szczególnie dla pop(), bo warto byłoby żeby pop zwracało zdjetą wartość!, przekazujesz do tych funkcji wskaźnik do wskaźnika na wierzchołek stosu. W ten sposób mozesz zmienic wierzchołek z wnętrza funkcji :)

0

Jesteś pierwszą osobą, która dała mi odpowiedź w sposób przyswajalny : D Jeszcze jakbyś mi tak pokazał jak to się robi z tymi wskaźnikami do wskaźnika, bo o ile teorię znam to w praktyce nigdy ich nie użyłem i nie wiem jak to zrobić. Bo po zmianie tych dwóch linijek, program wciąż nie działa jak powinien.

Napiszę szerzej bo dzieją się rzeczy, których nie rozumiem. Przy wywołaniu push i podaniu danych wszystko jest pozornie okej, ale gdy chcę wyświetlić stos otrzymuję liczbowo adres komórki pamięci, kiedy użyję pop i znowu dodam element to już mogę go wyświetlić, jednak dodać mogę tylko jeden element.

2

Kontenery to niezłe miejsce na metaprogramowanie, chociaż osobiście nie lubię void*magic http://ideone.com/xM8EdP
program:

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

#define DEF_LinkedList(T) \ 
	typedef struct _LinkedList##T{ \
		T value; \
		struct _LinkedList##T *next; \
	} LinkedList##T; \
	LinkedList##T *LinkedList##T##_New(const T *value){ \
		LinkedList##T *result = calloc(0, sizeof(LinkedList##T)); \
		memcpy(&result->value, value, sizeof(T)); \
		return  result; \
	} \
	void LinkedList##T##_Free(LinkedList##T *list) { \
		LinkedList##T *prev; \
		while(prev = list){ \
			list = list->next; \
			free(prev); \
		}  \
		free(list); \
	} \
	LinkedList##T *LinkedList##T##_Top(LinkedList##T *list){ \
		if(!list) return NULL; \
		while(list->next) list = list->next; \
		return list; \
	}\
	int LinkedList##T##_Push(LinkedList##T *list, const T *value){ \
		if(list == NULL) return LinkedList##T##_New(value); \
		LinkedList##T *top = LinkedList##T##_Top(list); \
		top->next = LinkedList##T##_New(value); \
		return list; \
	} \
	void LinkedList##T##_ForEach(const LinkedList##T *list, void(*op)(const T *)){ \
		while(list){ \
			op(&list->value); \
			list = list->next; \
		} \
	}
	
typedef int Int;
DEF_LinkedList(Int);
	

void printOp(const int *v){
	printf("%i", *v);
}

int main(void) {
	LinkedListInt *list;
	int i;
	for(i = 0; i <= 10; ++i)
		list = LinkedListInt_Push(list, &i);
		
	LinkedListInt_ForEach(list, printOp);
	
	LinkedListInt_Free(list);
	return 0;
}

stdout:012345678910

0
void push(wezel** stos, int element){
    wezel* biezacy;
    if((biezacy=(wezel*)malloc(sizeof(wezel)))==NULL)
    return;
    else{
        biezacy->liczba=element;
        biezacy->nast=*stos;
        *stos=biezacy;
    }
}

Ale w main oczywiście musisz mieć ręcznie utworzony 1 element stosu lub przynajmniej:

wezel* lista = NULL;
0

Analogicznie przerobiłem funkcję pop

 void pop(wezel **stos,int element){
wezel *tmp;
if(stos!=NULL){
tmp=*stos;
element=tmp->liczba;
*stos=tmp->nast;
free(tmp);
return ;
}
else{
fprintf(stderr,"Błąd brak danych\n");
return  ;}
}

Jednak zarówno przed przerobieniem funkcji jak i po efekt jest wciąż ten sam, nie wiem jak przetworzyć na ten wskaźnik do wskaźnika funkcję wyświetlającą, może to ona jest błędna ? Wciąż po dodaniu elementu wyświetla adres pamięci, nie mogę też dalej dodać więcej niż jednego elementu bez użycia funkcji pop : C

0

Wstawiam cały kod, może lepiej będzie Ci pokazać co jest nie tak.

 #include <stdio.h>
#include <stdlib.h>
typedef struct wezel{
	int liczba;
	struct wezel *nast;
}wezel;

/*funkcja umieszczająca element na szczycie stosu*/
void push(wezel **stos, int element){
	wezel* biezacy; /*tymczasowa komorka*/
	if((biezacy=(wezel*)malloc(sizeof(wezel)))==NULL)/*gdyby stos był pusty*/
	return ;
	else{
		biezacy->liczba=element;    /*przypisanie do komorki stosu pobranej wartosci*/
		biezacy->nast=*stos;       /*przypisanie aktualnej informacji do stosu*/
		*stos=biezacy;                  
	}
}

/*funkcja zdejmująca element ze szczytu stosu*/
void pop(wezel **stos,int element){
wezel *tmp;
if(stos!=NULL){
tmp=*stos;
element=tmp->liczba;
*stos=tmp->nast;
free(tmp);
return ;
}
else{
fprintf(stderr,"Błąd brak danych\n");
return  ;}
}

/*funkcja drukująca na stdout cały stos*/
void print(wezel *stos){
	if(stos==NULL)
	printf("Brak elementów\n");
	else
		do{
			printf("%5d\n",stos->liczba);
			stos=stos->nast;
		}while (stos!=NULL);
	
}
/*pomocnicza funkcja sprawdzająca czy stos nie jest pusty*/

void empty(wezel *stos){
	if(stos==NULL)
	printf("Stos pusty\n");
	else
	printf("Stos nie jest pusty\n");
}


int main(){
	wezel *stos=NULL;
	char wybor=0;
	int element=0;
	printf("Kalkulator RPN\nDostepne funkcje:\n");
	printf("1   2   3   #   q\n4   5   6   $\n7   8   9   &\n0           ?\n");
	do{
	printf("~");
	scanf("%s",&wybor);
	switch(wybor){
		case '?':
			print(stos);
			break;
		case 'l':
			printf("Podaj liczbę:");
			scanf ("%d",&element);
			push(&stos,element);
			break;
		case '#':
			pop(&stos,element);
			break;
		case 'e':
			empty(stos);
			break;
		default:
			fprintf(stderr,"Błąd, zły wybór\n");
			break;
	}
}
while(wybor!='q');
}
2

OMG chłopie, zrobiłeś taki błąd że bez debugera to bym nigdy nie zobaczył.

scanf("%s",&wybor);

Tu masz błąd. Otóż nie bierzesz pod uwagę że wczytanie C-stringa jest zakańczane 0 żeby było wiadomo gdzie ten string się kończy. A że masz miejsce tylko na 1 chara to to 0 zostanie wpisane w kawałek pamięci OBOK twojego chara. Czyli na przykład tam gdzie mamy wierzchołek stosu :D Quick fix to dać

char wybor[2];

a w switchu i while dać wybor[0].

Ale generalnie C/C++ to są języki gdzie trzeba rozumieć co sie robi, szczególnie jak sie ma wskaźniki gdzieś. Na przyszłość polecam debugger, bo bez niego może być trudno ;)

2
draggie13 napisał(a):
...
	if((biezacy=(wezel*)malloc(sizeof(wezel)))==NULL)/*gdyby stos był pusty*/
...

Jakiś sabotażysta ci ten komentarz wsadził?

Przeróbka na szybko:

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

typedef struct node_ node;
struct node_
  {
   int value;
   node *next;
  };
typedef struct stack_ stack;
struct stack_
  {
   node *head;
  };


void push(stack *s,int value)
  {
   node *tmp=(node*)malloc(sizeof(node));
   if(!tmp) exit(fprintf(stderr,"brak pamieci"));
   tmp->value=value;
   tmp->next=s->head;
   s->head=tmp;
  }
 
int pop(stack *s)
  {
   node *tmp=s->head;
   if(!tmp) exit(fprintf(stderr,"pobranie z pustego stosu"));
   s->head=tmp->next;
   int value=tmp->value;
   free(tmp);
   return value;
  }
 
void print(stack *s)
  {
   for(node *i=s->head;i;i=i->next) printf("%d\n",i->value);
  }
 
int empty(stack *s)
  {
   return !(s->head);
  }
 
int main()
  {
   stack S={NULL};
   int what=0,value;
   for(;;)
     {
      printf("kalkulator>");
      scanf("%c",&what);
      switch(what)
        {
         case '?':
            if(empty(&S)) printf("Stos pusty\n\n"); 
            else print(&S);
         break;
         case '<':
            scanf(" %d",&value);
            push(&S,value);
            printf("Wrzucono %d\n\n",value);
         break;
         case '>':
            if(empty(&S)) printf("Stos pusty\n\n"); 
            else printf("Pobrano %d\n\n",pop(&S));
         break;
         case '!': 
            return 0;
         default:
            printf("Brak wybranej opcji, dostepne\n");
            printf("? - pokaz stos\n");
            printf("< # - wrzuc liczbe #\n");
            printf("> - zdemij liczbe\n");
            printf("! - koniec programu\n\n");
         break;
        }
      while(getchar()!='\n') {}
     }
  }
0
scanf("%c",&what);

Z tym to bym uważał, bo to trochę zależne od środowiska i od tego jak odpalasz ;) Zauważ że w interaktywnej konsoli wciskasz "enter" i ci ten znak nowej linii zostanie w buforze, w efekcie może cię nie zapytać np. o liczbę do wpisania ;)

0

Niezmiernie dziękuję za pomoc, zaczynam nawet rozumieć trochę zawiłości tych stosów, jednak mam jeszcze jedno zadanie, które wydawało się łatwe a jednak zupełnie takie nie jest, mianowicie jak można w miarę łatwo zrobić funkcję zamieniającą kolejnością dwa elementy na stosie tzn mamy stos {2} {3} i chcę mieć {3} {2}, jak by ktoś naprowadził jak to może wyglądać?

Próbowałem to zrobić z pomocą pop i push ale kasuje mi to moje elementy

	pop(&stos,element);
				wsk1=stos;
				lib1=element;
				pop(&stos,element);
				wsk2=stos;
				lib2=element;
				push(&wsk2,lib2);
				push(&wsk1,lib1); 

Oraz deklaracje dodatkowych elementów do zapamiętania pobranych ze stosu wartości

 wezel *wsk1,*wsk2;
	int lib1,lib2;
0

Jak to jak? pop,pop,push, push ;] Tylko zrób ten kod po ludzku jakoś. Niech pop nie przyjmuje tego drugiego argumentu tylko niech zwraca inta (zamiast voida).

0

Napisałem w ten sposób

                  
                                int lib1;
                                pop(&stos,element);
				lib1=stos->liczba;
				pop(&stos,element);
				push(&stos,element);
				push(&stos,lib1); 

Działa, ale mogę tego użyć raz tzn mając stos {1} {2}, zamieniam otrzymuję {2} {1}. Tylko jeśli użyję go znowu żeby otrzymać to co miałem to dostaję {2} {2}

1
  1. Dostałeś podpowiedź: pop,pop,push, push, robiłeś: pop, jakiś chrzan, pop,push, push więc nie ma prawa działać.
  2. pop(&stos,element); - to nie ma prawa działać jeżeli napisano to w C
  3. Poza tym podejrzewam że mimo że każdy rozsądny programista załatwi to właśnie w ten sposób w zadaniu chodzi aby zrobić to na wskaźnikach.
1

@draggie13 omg chłopie, czemu ty sobie utrudniasz życie, serio? Zróbże to po ludzku!

int pop(wezel **stos){
  wezel *tmp;
  if(stos!=NULL){
    tmp=*stos;
    element=tmp->liczba;
    *stos=tmp->nast;
    free(tmp);
    return element;
  }
  else{
    fprintf(stderr,"Błąd brak danych\n");
    return  -1;
  }
}

void push(wezel **stos, int element){
    wezel* biezacy = (wezel*)malloc(sizeof(wezel));
    if(biezacy!=NULL){
        biezacy->liczba=element;
        biezacy->nast=*stos;
        *stos=biezacy;         
    }
}

I teraz po prostu

push(&stos,1);
push(&stos,2);
int e1 = pop(&stos); //zdejmujemy 2
int e2 = pop(&stos); //zdejmujemy 1
push(&stos, e1); //kładziemy 2
push(&stos, e2); //kładziemy 1

1 użytkowników online, w tym zalogowanych: 0, gości: 1