[C]implementacja stosu,problem ze zrzumieniem jednej rzeczy

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

#define W 100

/*
Zaimplementuj stos używając tablicy. Funkcje muszą przyjmować wskaźnik do tablicy przechowującej elementy stosu.
Jak można zaimplementować stos tak żeby funkcje top, pop, push nie potrzebowały przy każdym wywołaniu znać długości tablicy elementów?
 */

int top(int *stos);
int pop(int *stos);
void push(int *stos, int elem);

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

	int stos[W]; //maksymalna możliwa wielkość kopca
	stos[0] = 0; //obecna wielkośc kopca (wartownik)
	int operacja;
	int elem;

	while(1) {

		printf("Jaką operację chcesz wykonać?\n 1 - podam Ci element, który jest na szczycie stosu.\n 2 - usunę element ze szczytu stosu.\n 3 - dodam podany przez Ciebie element na szczyt stosu. 0 -koniec\nCo więc wybierasz?\n\nWykonaj: ");
		scanf("%d", &operacja);

		if(operacja==1) {
			if(stos[0]==0) printf("\nStos jest pusty!");
			else printf("\nElement na szcycie stosu to: %d",top(stos));
		}
		else if(operacja==2) {

			if(stos[0]==0) printf("\nStos jest pusty, nie można usunąć żadnego elementu!");
			else printf("\nElement usunięto, na stosie pozostało %d elementów", pop(stos));

		}
		else if(operacja==3) {

			printf("\n\nJaki element chcesz dodaj do stosu?\nDodaj: ");
			scanf("%d", &elem);

			if(stos[0]<W) push(stos,elem);
			else printf("\nStos jest przepełniony!");

		}

		else if(operacja==0)
		break;

		else printf("\n\nNie ma takiej operacji!");




	}


	return 0;

}

int top(int *stos) {

	int i=stos[0];

	return stos[i];

}
int pop(int *stos) {

	int i=stos[0];

	stos[0]=i-1;

	return i-1;

}
void push(int *stos, int elem) {

	int i=stos[0];

	stos[i+1]=elem;
	stos[0]=i+1;

}

nie rozumiem jak dziala to int i=stos[0];
jakim cudem to w funkcji np. top sprawia ze dziala ona poprawnie?

0

stos[0] zawiera wysokość stosu. Przy każdym wrzucaniu nowego elementu wielkość zostaje zwiększona, a przy zdejmowaniu zmniejszona.
W funkcji top zostaje pobrana ilość elementów, a następnie za jej pomocą pobierana wartość. Tak więc dla top[0] = 1 na szczycie stosu leży element znajdujący się w top[1] itd.

0

ale dlaczego stos[0] to jest wysokosc stosu, a nie pierwszy element tablicy stos ?

0

Bo tak to ktoś zaimplementował. LOL
Masz jak byk napisane w kodzie:

stos[0] = 0; //obecna wielkośc kopca (wartownik)
0

no tak :), ale dlaczego to zwraca element na szczycie stosu?

int i=stos[0];

return stos[i]; - jaki cudem to jest szczytowy element?
bierzemy nagle zmienna i i przypisujemy jej wartosc pierwszego elementu tablicy stos. Dlaczego stos[wartosci pierwszego elementu tablicy] to szczyt stosu?

0

Bo ktos zaimplementowal ten stos tak, ze pierwsza wartosc oznacza ilosc elementow. Czyli indeks[pierwsza wartosc] oznacza top stosu.

0

stos[0] to ilość elementów na stosie. Skoro elementy wrzucamy do tablicy po kolei (na pozycje 1,2,3,...) i za każdym razem, wrzucając na stos zwiększamy stos[0] to siłą rzeczy jeśli wrzucimy na stos np. 5, 10 i 15 to mamy:

stos[0] == 0

wrzucamy 5
stos[0] == 1
stos[1] ==5 <-- top stosu

wrzucamy 10
stos[0] == 2
stos[1] == 5
stos[2] == 10 <-- top stosu

wrzucamy 15
stos[0] == 3
stos[1] == 5
stos[2] == 10
stos[3] == 15 <-- top stosu

W związku z czym jeśli zwrócimy stos[stos[0]] to zwrócimy zawsze top stosu.

0

dzieki, wreszcie zalapalem :)

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