Gdzieś tutaj zaszył się chyba problem z pamięcią... Najlepiej to widać gdy jako korzeń podacie 5 - wtedy na lewo będzie 3, na prawo 6, wyświetli się wewnątrz funkcji poprawnie, natomiast w kodzie głównym wyrzuci błąd...
Sam program jest niekompletny, nie ma odśmiecania pamięci itd... To tylko wersja przed-beta właściwie, sprawdzenie algorytmu
Czy ktoś mógłby na to spojrzeć? Z góry serdecznie dziękuję
Ostatnio zmieniony 21 cze 2011, o 11:19 przez Afish, łącznie zmieniany 1 raz.
Powód:Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania.
Chyba rozumiem, wyzerowanie będącego tam już elementu (niepotrzebny NULL)... Faktycznie po skasowaniu działa. Dzięki za pomoc
Nie wziąłem pod uwagę tego, że przed dodaniem puste gałęzie korzenia i tak mają NULLa.
A to jeszcze jedno małe pytanko: czy zapis " wsk=NULL; " jest równoważy " wsk=0;" ?
Nie, nie jest. Posiłkując się stroną a konkretniej zdaniem
"initializes all its bits to zero"
wnioskujemy, że nie wiemy nic więcej o zawartości zaalokowanej pamięci. Null-pointer nie jest zdefiniowany dokładnie w standardzie, określone są tylko cechy i jego zachowanie w odpowiednich sytuacjach jak dereferencja, porównanie z innym wskaźnikiem i tak dalej. To może być wskaźnik do adresu 0 (i tak to zazwyczaj jest), do dowolnego innego miejsca, jakiś wskaźnik dwubajtowy z dodatkową flagą etc. A to oznacza, że binarnie on nie musi składać się z samych zer.
Aha... Pojawił się nowy problem, być może ma to właśnie związek z tym, że wskaźnik na NULL nie musi być zerem... Otóż dołozyłem funkcję majacą zwalniać pamięć (" void zwolnij_pamiec(struct BIN* wezel) " ), i jak w kodzie - dodaję do drzewa 50 000 elementów. W momencie rozpoczecia programu zuzycie pamięci to 748 kb (domyślam się że chodzi o kilobajty, sprawdzałem przez menedźer zadań w XP), po wstawieniu zajmował 3496kb a po zwolnieniu 2416 kb (także obserwowałem w menedźerze).
void zwolnij_pamiec(struct BIN* wezel)
{
if (wezel->prawo)
zwolnij_pamiec(wezel->prawo);
if (wezel->lewo)
zwolnij_pamiec(wezel->lewo);
wezel->prawo=NULL;
wezel->lewo=NULL;
//printf(" a ");
free(wezel); wezel=NULL;
}
Pomyślałem to tak - schodzi w prawo i lewo, odkłada się rekurencyjnie na stosie - i wtedy od końca kasuje elementy (dopóki nie ma prawego potomka, dopóki nie ma lewego, te ląduja na stosie (Dopisane: chodzi mi o to, że dla każdego elementu będzie jedna rekurencja - czyli kazdy winien być usunięty)). Teoretycznie powinien przejść przez każdy węzęł/liść (dla małych ilości tak jest, zgadza mi sie ilość elementów które podam z ilością wyświetlonych " a " ), no ale patrząc na to że pamięć dla 50 000 elementów nie wraca do początkowych 748 kb nieco mnie dziwi... Może właśnie to że if (wsk) nie znaczy to samo co if (wsk!=NULL) powoduje ten problem? Choc z drugiej strony już chwilę używam tego skrótu i przenigdy nie było problemów...
Cały program:
Ukryta treść:
#include <stdio.h>
#include <stdlib.h>
struct BIN
{
int wartosc;
struct BIN* lewo;
struct BIN* prawo;
};
struct BIN* ustaw_korzen(struct BIN*, int);
void wstaw_element(struct BIN*, int);
int szukaj_minimum(struct BIN*);
int szukaj_maksimum(struct BIN*);
void zwolnij_pamiec(struct BIN*);
int main()
{
struct BIN* korzen=NULL;
int liczba, min, maks;
char czy_dodac;
puts("Podaj wartosc dla korzenia:"); scanf("%d", &liczba); fflush(stdin);
korzen=ustaw_korzen(korzen, liczba);
Nie przejmowałbym się tym, co pokazuje menadżer zadań, a to ze względu na sposób zarządzania pamięcią przez system. Po zwolnieniu pamięć niekoniecznie musi być odliczona dla procesu, bo być może ten będzie chciał ją zaraz zająć ponownie, więc systemowi nie zależy na jak najszybszym wyczyszczeniu wszystkiego (o ile nie ma potrzeby). Jeżeli bardzo zależy Ci na sprawdzeniu, czy nie ma wycieków, to możesz użyć odpowiednich narzędzi jak valgrind lub purify. I nie, skrót if(wsk) nie powoduje błędu, bo najpopularniejsze kompilatory (czyli gcc, g++ i msvc) implementują null-pointer jako wskaźnik do adresu 0, więc wszystko jest okej.
