Zásobník – C / C++ – Fórum – Programujte.com

Zdravím, trošku se potýkám s problémem o správném přiřazení pointerů a práci s neznámou pamětí.

typedef struct Item{
    int value; //hodnota v zasobniku
    struct Item* prev; //predchadzajuci prvok v zasobniku
}Item;

typedef struct BrokenStack{
    Item* top;
}BrokenStack;
    
   /**
    * Metoda Pop() funguje obdobne. Pokial hodnota na vrchu zasobniku je
    * vacsia alebo rovna ako hodnota hned pod vrcholom, pop funguje
    * normalne, tj. odobere hornu polozku. V pripade, ze hodnota na vrchu je
    * mensia ako hodnota pod vrcholom, odstrani sa zo zasobniku polozka pod
    * vrcholom. Tj. odstrani sa vzdy vacsia z hodnot na vrchole a pod nim.
    * Ak je v zasobniku len jedna polozka, odstrani sa tato.
    *
    * Pop() vracia hodnotu polozky, ktora je odstranena zo zasobniku.
    *
    * V pripade zavolania pop() na prazdny zasobnik vrati sa -1;
    *
    * Vid priklad:
    *
    * Stav zasobniku:      11| 6|10| 5|
    * Volame Pop():         6|10| 5|    (11 bola vacsia ako 6) Pop() vrati hodnotu 11
    * Volame Pop():         6| 5|       (10 bola vacsia ako 6) Pop() vrati hodnotu 10
    * Volame Pop():         5|          Pop() vrati hodnotu 5
    * Volame Pop():        Empty stack! Pop() vrati -1
    *
    * Opat kontrolujte spravne ukazate a davajte si pozor na pracu s NULL.
    * Nezabudnite udrziavat korektny top. O spravne dealokovanie sa nemusite starat.
    */
    int pop(BrokenStack* s){
	Item *prvek;
	int value;
	if(s->top == NULL){
            return -1;
	}
        if(s->top == s->top->prev){
            s->top = NULL;
            s->top->prev = NULL;
            return -1;
        }else{
            if(s->top->value > s->top->prev->value){ // jestli je první prvek v zásobníku větší než předcházející
                prvek = s->top;		
                s->top = prvek->prev;
                value = prvek->value;
            }else{				// pokud není
                if(countItems(s) >= 3){		// a je jich tam víc jak 3
                    prvek = s->top->prev;
                    s->top->prev = s->top->prev->prev;
                    value = prvek->value;
                }else if(countItems(s) < 3){	// pokud není
                    prvek = s->top->prev;	// TADY TO HAVARUJE
                    value = s->top->value;
                }
            }
        }
        free(prvek);
        return value;
    }


 /**
     * @param s
     * @return pocet prvkov v zasobniku s
     */
    int countItems(BrokenStack* s){
        int count = 0;
        Item* item = s->top;
        while(item != NULL){
            count++;
            item = item->prev;
        }
        return count;
    }

Je to napsané strašně křečovitě, na ostro bych na to měl pouze hodinu a to oni počítají, že to budem max. psát 25m a pak jdem na další úlohu. Sedím nad tím 3h a něco a pořád to nemám celé.

   /**
    * Push vklada na vrchol zasobniku tak, ze pokial vkladana hodnota je
    * vacsia alebo rovna ako vrchol zasobniku(top), vklada normalne,
    * tj. prida ju nad vrchol a zmeni(top). Ak je vkladana hodnota mensia,
    * vlozi ju na prvu poziciu pod vrchol.  V pripade prazdneho zasobniku (na
    * vrchole je NULL) vkladame normalne.  Ukazku mozete vidiet na
    * nasledujucom priklade:
    *
    * Stav zasobniku:      10| 5|       (10 je na vrchu zasobniku)
    * Volame Push(11):     11|10| 5|    (11 bola vacsia ako 10)
    * Volame Push(6):      11| 6|10| 5| (6 bola mensia ako 11)
    *
    * Pri implementacii treba z argumentu value naalokovat objekt Item a spravne
    * nastavit vsetky ukazatele "prev".
    *
    * Dajte si pozor na pristupovanie ku objektom, ktore mozu byt NULL. Vzdy
    * kontrolujte, k akym objektom pristupujete.
    *
    * Dno zasobniku kontrolujete podla toho ci je ukazatiel (top alebo prev) == NULL
    */
    void push(BrokenStack* s, int value){
        Item *prvek = (Item*)malloc(sizeof(Item));

        if(s->top == NULL){
            prvek->value = value;
            prvek->prev = s->top;
            s->top = prvek;
            return;
        }

        prvek->value = value;
        prvek->prev = s->top;
        s->top = prvek;

        if(value < prvek->prev->value){
            int tmp = prvek->value;
            prvek->value = prvek->prev->value;
            prvek->prev->value = tmp;
        }

    }

Toto mi funguje, ale nemám to moc složité?

Dole jsou testy ... 1, 2, 3, 5 fungují  4,6 ne

        //Test 1.
        push(s,12);
        printf("Test 1.:");
        if(!strcmp("12|", print(s))){
             push(s,9);
			if(!strcmp("12|9|", print(s))){
				push(s,11);
				push(s,1);
				if(!strcmp("12|1|11|9|",print(s))){
					puts("OK");
				}else{
					printf("Chyba, vas stav zasobniku: %s != 12|1|11|9|\n", print(s));
				}
			}else{
				printf("Chyba, vas stav zasobniku: %s != 12|9|\n", print(s));
			}
        }else{
            printf("Chyba, vas stav zasobniku: %s != 12|\n", print(s));
        }

        //Test 2.
        BrokenStack* s2 = createStack();
        Item* h = (Item*) malloc(sizeof(Item));
        h->prev = NULL;
        h->value = 10;
        s2->top = h;
        push(s2,15);
        printf("Test 2.:");
        if(!strcmp("15|10|", print(s2))){
            puts("OK");
        }else{
            printf("Chyba, vas stav zasobniku: %s != 15|10|\n", print(s2));
        }

        //Test 3.
        int value = pop(s);
        printf("Test 3.:");
        if(!strcmp("1|11|9|",print(s))){
            if(value == 12){
				value = pop(s);
				if(!strcmp("1|9|",print(s))){
					if(value == 11){
						puts("OK");
					}else{
						printf("Pop vraci jinou hodnotu %d != 11\n",value);
					}
				}else{
					printf("Chyba, vas stav zasobniku: %s != 1|9|\n", print(s));
				}
            }else{
                printf("Pop vraci jinou hodnotu %d != 12\n",value);
            }
        }else{
            printf("Chyba, vas stav zasobniku: %s != 1|11|9|\n", print(s));
        }

        //Test 4.
        pop(s);
        value = pop(s);
        printf("Test 4.:");
        if(!strcmp("Empty stack!", print(s))){
            if(value == 1){
				value = pop(s);
				printf("Test 8.:");
				if(!strcmp("Empty stack!", print(s))){
					if(value == -1){
						puts("OK");
					}else{
						printf("Pop vraci jinou hodnotu %d != -1\n",value);
					}
				}else{
					printf("Chyba, vas stav zasobniku: %s != Empty stack!\n", print(s));
				}
            }else{
                printf("Pop vraci jinou hodnotu %d != 1\n",value);
            }
        }else{
            printf("Chyba, vas stav zasobniku: %s != Empty stack!\n", print(s));
        }

        //Test 5.
        printf("Test 5.:");
        BrokenStack* s3 = createStack();
        for(int i = 0; i < 100; i++){
            push(s3,i);
        }
        int count =  countItems(s3);
        if(count != 100){
            printf("Chyba, pocet prvkov v zasobniku: %d != 100\n", count);
        }else{
            puts("OK");
        }

        //Test 6.
        printf("Test 6.:");
        for(int i = 0; i < 50; i++){
            pop(s3);
        }
        count = countItems(s3);
        if(count != 50){
            printf("Chyba, pocet prvkov v zasobniku: %d != 50\n", count);
        }else{
            for(int i = 0; i < 50; i++){
                pop(s3);
            }
            count = countItems(s3);
            if(count != 0){
                printf("Chyba, pocet prvkov v zasobniku: %d != 0\n", count);
            }else{
                puts("OK");
            }
        }

        return 0;
    }

#1 Siggi
 

#2 ondrej39
Díky moc za video, jsem nečekal, že si dáš tu práci a nahraješ rovnou video :).

Moc nechapu, proc nestaci pro vkladani do zasobniku jen:

Item * novy = (Item*)malloc(sizeof(Item));
novy->value = value;
novy->prev = s->top; // je jedno, jestli uz na neco ukazuje nebo ne
s->top = novy;

Jedina kontrola by tam mohla byt s != NULL (jako chyba mezi zidli a klavesnici).

#4 KIIV
Pokud vím, tak normální zásobník tak funguje, ale vypadá to, že oni chtěli udělat nějakej paskvil :D.

 Pak holt takto... kdyby to chteli radit, tak vymenit if za while...

Item ** kam = &(s->top); // kde budeme ukladat pointer
if ((*kam != NULL) && ((*kam)->value > value)) kam = &((*kam)->prev); // posuneme, pokud je treba
Item * novy = (Item*)malloc(sizeof(Item));
novy->value = value;
novy->prev = *kam;
*kam = novy;

EDIT: opravena chybka s tim NULL

Pop je taky mozne udelat jednoduse:

    int pop(BrokenStack* s) {
        Item ** i = &(s->top);
        if ((*i != NULL) && ((*i)->prev != NULL && ((*i)->value < (*i)->prev->value))) i = &((*i)->prev);
        if (*i != NULL) {
            int value = (*i)->value;
            Item * tmp = *i;
            *i = (*i)->prev;
            free(tmp);
            return value;
        }
        return -1;
    }

Ok děkuji za rady, ale na příspěvek č.7 bych sám asi nikdy nepřišel.