Problem ze wskaźnikami (?)

pytanie zadane 20 maja 2015 w C i C++ przez Oryks Nowicjusz (210 p.)

http://wklej.org/hash/cb3e35fb417/

Witam mam problem z tym algorytmem stosu priorytetowego

Program 'wykrzacza' się wtedy gdy zmieniam głowę, jest więc jakiś problem z funkcją push, czy mógłby ktoś powiedzieć co zrobiłem źle?

Pozdrawiam

3 odpowiedzi

odpowiedź 20 maja 2015 przez Bartek85 Mądrala (7,440 p.)
wybrane 20 maja 2015 przez Oryks

Najlepsza

Uf... myślałem, że będzie lepiej, ale się pomyliłem. Zaczynamy

1) funkcja struct stackpri *push_stackpri(struct stackpri *head, int key, int prio)

- po co jest twór spr ?

- po co jest twór guard ?

- po co jest ten fragment kodu ?

    if(head)
    {
        while(spr->next)spr=spr->next;
        spr->next=guard;
        guard->prio=prio;
        guard->next=NULL;
    }

Nic nie wnosi do kodu...

2) ta sama funkcja struct stackpri *push_stackpri(struct stackpri *head, int key, int prio)

Warunek:

//...   
 else   //jeśli priorytet głowy jest mniejszy od priorytetu nowego elementu
    {
        while(tmp->next->prio!=prio) tmp=tmp->next; //aż będzie istniał następny element i priorytet następnego mniejszy od priorytetu nowego

            newel->next=tmp->next->next; //wskazanie na następny element nowego jest zmienione
            newel->nextpri=tmp->next; //podnosimy tamten element do góry
            tmp->next=newel; //cd
            if(!newel->next)tail=newel;

    }

Dane wejściowe z Twojego kodu. Przeanalizuj sobie, że uruchamiasz tą funkcję ze "stosem" który ma jeden element i wchodzisz do w/w warunku. Co się dzieje...

linia: while(tmp->next->prio!=prio) tmp=tmp->next;

skoro mamy tylko jeden element i next wskazuje na NULL'a, to dlaczego odpytujesz prio z NULL'a ? Przeciez next jeszcze nie istnieje... tutaj jest pierwsze naruszenie pamięci.

ta sama historia niżej, linia:

 newel->next=tmp->next->next;

Skoro nie ma next, to odwołania się do next->next to kolejne naruszenie pamięci.

3) Tak jak ktoś wcześniej zauważył funkcję

int stack_empty(struct stackpri *head)

używasz jak zmiennej:

if(!stack_empty)

4) Zarządzanie pamięcią. W funkcji struct stackpri *push_stackpri(struct stackpri *head, int key, int prio)

alokujesz pamięc, a kto ja później posprząta?

Okej, aby pójść krok dalej, napisz proszę jak ma działać ten Twój algorytm bo z kodu ciężko wywnioskować. Nie ma tam logiki, która jest jasna.

komentarz 20 maja 2015 przez Oryks Nowicjusz (210 p.)

1) Spr użyłem jako iteratora żeby przejść na koniec pętli. Niestety nie potrafię posługiwać się tail'em... Jak już doszedłem na koniec pętli stworzyłem wartownika, który miał służyć jako ochrona dla nowego elementu o danym priorytecie (jeśli priorytet nie występuje, to dodaje element o danym priorytecie na koniec stosu... W TYM MOMENCIE DOSTRZEGŁEM PIERWSZY BŁĄD, TZN JEŚLI BĘDĘ MIAŁ PRIORYTETY 1,3 W STOSIE I BĘDĘ CHCIAŁ WSTAWIĆ ELEMENT O PRIORYTECIE 2 TO ZOSTANIE WSTAWIONY NA KONIEC, A WIĘC WYCOFUJĘ SIĘ Z TEGO I ZARAZ ZMIENIĘ ALGORYTM. DZIĘKI, FAKTYCZNIE TO ZŁA KONCEPCJA ;)

2) Dwójka wiązała się z tym felernym wartownikiem, już zmieniłem

3)ok zmieniłem

4)nie rozumiem co mam posprzątać szczerze mówiąc...

Poprawiony kod, niestety dalej nie działa, wykrzacza mi się przy 3 wywołaniu funkcji

http://wklej.org/hash/cdb15760982/

Działa to tak, jeśli głowa nie istnieje to wstawiam ten element i przypisuję go głowie

Jeśli głowa istnieje i jej priorytet jest większy od priorytetu wstawianego to zastępuje głowę tym elementem a tamten przesuwam dalej.

Jeśli priorytet głowy jest równy priorytetowi wstawianego to głowę przesuwam do 'góry' (newel->nextpri=head;) i przypisuję głowie wstawiany element.

No i jeśli priorytet głowy jest mniejszy od priorytetu nowego elementu to szukam gdzie mogę go wstawić i tam go wstawiam

Wciąż bardzo proszę o pomoc i dziękuję za zainteresowanie :)

komentarz 20 maja 2015 przez Bartek85 Mądrala (7,440 p.)

Tak widziałem. Poniżej wklejam rozwiązanie.

http://wklej.org/id/1717253/

Nie zmieniałem całego programu(a wypadałoby), tylko elementy, które były nieprawidłowe... Zobacz czy o to Ci chodziło. Musisz się jeszcze troche podszkolić w zarządzaniu pamięcią w C/C++.

Jeżeli chodzi o moją uwagę w punklcie 4, to miałem na myśli, że pamięć którą gdziekolwiek alokujesz dynamicznie, później trzeba ją zwolnić.

malloc/free w C, oraz new/delete w C++.

komentarz 21 maja 2015 przez Oryks Nowicjusz (210 p.)

co prawda zamierzeniem było zrobienie tego za pomocą list dwuwymiarowych, ale dzięki za pomoc :)

jednak strasznie nurtuje mnie to czemu moja funkcja push nie działa, nie mogę zrobić drugiego wymiaru w ten sposób? (dodając do struktury wskaźnik na następny element o takim samym priorytecie)? :P

komentarz 21 maja 2015 przez Bartek85 Mądrala (7,440 p.)

Jasne, że możesz :)

Jak zrobisz to umiejetnie... ;) Nie ma rzeczy nie możliwych. Cokolwiek jestes w stanie wymiślić w głowie, da się to przenieść do komputera.

odpowiedź 20 maja 2015 przez MrWeb Stary wyjadacz (10,200 p.)

Ciekawe zadanie, niestety nie wiem gdzie leży błąd... Mogę tylko powiedzieć, że program się uruchomił i zakończył bez problemu na ubuntu 14.04.

Jedyny błąd jaki rzuca mi się w oczy to linijka nr 96 - używasz funkcji jak zmiennej a chyba powinieneś przekazać tej funkcji jakiś argument.