Witam
Dostałem zadanie: zaimplementować algorytmy grafowe (na listach) i zmierzyć ich czas działania. Stworzyłem do tego własną klasę TLista (gdyż standardowe listy z STL’a nie spełniały pewnych, bardziej szczegółowych, warunków zadania) i dopisałem wszystkie potrzebne mi funkcję do obsługi tej klasy.
I teraz problem jest taki, że każdy z algorytmów jaki napisałem, po zakończeniu swojego działania, nie zwalnia pamięci, mimo że tam gdzie trzeba używam delete, erase(), czy clear(). Być może jeśli pokaże wam jedną przykładową funkcję algorytmu który stworzyłem, będzie potrafili mi wskazać linijkę która odpowiada za nie kasowanie pamięci, albo czego brakuje.
Oto przykładowy algorytm Kruskala wraz z kodem tych funkcji, które alokują dodatkową pamięć lub mogą być po części odpowiedzialne za problem (czyli bez sortowanieKruskal(), drukuj(), pobierzCzas()):
funkcja Kruskal
#include "Lista.h" //deklaracja klasy
#include "Kruskal.h" //algorytmy pomocnicze, w tym algorytm sortowania
#include "Czas.h" //do funkcji pobierzCzas()
#include "Na_ekran.h" //do funkcji drukuj() do formatowania tekstu i wypisywania na ekran
#include
#include
using namespace std;
double * TLista::Kruskal(int ileRazy)
{
double * czas = new double[ileRazy];
drukuj("Przygotowanie do algorytmu... ");
double poczatekC, koniecC;
TWezel * aktualny = NULL;
vector * krawedzie = NULL; //przechowuje zbior wszystkich krawedzi (w tym wagi oraz wierzcholki polaczone z krawedzia)
int * numerDrzewa = NULL; //przechowuje informacje, do jakiego (numeru) drzewa nalezy i-ty wierzcholek
int v; //licznik krawedzi
int lewy, prawy; //lewy, prawy wierzcholek danej krawedzi
int i, j;
while(ileRazy--)
{
v = 0;
krawedzie = new vector[E];
numerDrzewa = new int[V];
for(i = 0; i < V; i++)
numerDrzewa[i] = i; //zgodnie z algorytmem, na poczatku wszystkie drzewa sa jednowierzcholkowe i maja numer wierzholka
//Poczatek algorytmu
//--------------------------------------------------
drukuj("Algorytm w toku... ", ileRazy);
poczatekC = pobierzCzas();
for(i = 0; i < V; i++)
{
aktualny = przeszukaj(i);
for(j = 0; j < aktualny->Nastepny.size(); j++)
{
krawedzie[v].push_back(abs(aktualny->Waga[j]));
krawedzie[v].push_back(aktualny->Index);
krawedzie[v].push_back(aktualny->Nastepny[j]->Index);
v++;
}
}
sortowanieKruskal(krawedzie, v);
for(i = 0; i < v; i++)
{
lewy = krawedzie[i][1];
prawy = krawedzie[i][2];
if(numerDrzewa[lewy] != numerDrzewa[prawy])
this->dodajKrawedzDoDrzewa(numerDrzewa, lewy, prawy);
}
//Koniec algorytmu
//---------------------------------------------
koniecC = pobierzCzas();
if(ileRazy > 0) drukuj("Przygotowanie do powtorzenia algorytmu... ");
else drukuj("Konczenie algorytmu... ");
for(i = 0; i < v; i++)
{
krawedzie[i].erase(krawedzie[i].begin(), krawedzie[i].end());
krawedzie[i].clear();
}
delete [] krawedzie;
krawedzie = NULL;
delete [] numerDrzewa;
numerDrzewa = NULL;
czas[ileRazy] = koniecC - poczatekC;
}
drukuj("Algorytm Kruskala...Zakonczony ");
return czas;
}
funkcja przeszukaj
#include "Lista.h"
#include
using namespace std;
TLista::TWezel * TLista::przeszukaj(int index) //TWezel, to analogiczny wezel z list znanych z STL
{
//zmienna 'znaleziono' jest statyczna, poniewaz pewne algorytmy wywoluja ta funkcje kilkukrotnie pod rzad dla tego samego 'index'
//dlatego przetrzymywanie wartosci 'znaleziono' po wyjsciu z funkcji, moze przyspieszyc niektore przeszukiwania
static TWezel * znaleziono = poczatek;
//celowe sprawdzenie przed tworzeniem innych obiektow funkcji i sprawdzenie czy 'znaleziono' nie wskazuje juz na 'index'
if(znaleziono->Index == index)
return znaleziono;
else znaleziono = NULL;
//----------------------------------------------
vector nastepniki;
TWezel * aktualny = NULL;
bool * odwiedzone = new bool[V];
stack > stos;
odwiedzone = new bool[V];
for(int i = 0; i < V; i++)
odwiedzone[i] = false;
aktualny = poczatek;
nastepniki.clear();
nastepniki.push_back(aktualny);
podajSasiadow(&nastepniki, aktualny);
odwiedzone[aktualny->Index] = true;
while(znaleziono == NULL)
{
while(nastepniki.size() > 1)
//'>1' z racji tego, ze nastepniki[0] == aktualny, a kazdy kolejny to szukani sasiedzi,
//wiec jesli sa sasiedzi, to rozmiar 'nastepniki' musi byc >1
{
aktualny = nastepniki[nastepniki.size() - 1];
if(aktualny->Index == index)
{
znaleziono = aktualny;
break;
}
nastepniki.pop_back();
if(odwiedzone[aktualny->Index] == false)
{
stos.push(nastepniki);
nastepniki.clear();
nastepniki.push_back(aktualny);
podajSasiadow(&nastepniki, aktualny);
odwiedzone[aktualny->Index] = true;
}
}
if(!stos.empty() && znaleziono == NULL)
{
nastepniki = stos.top();
stos.pop();
}
}
delete [] odwiedzone;
odwiedzone = NULL;
return znaleziono;
}
funkcja podajSasiadow
#include "Lista.h"
void TLista::podajSasiadow(vector * sasiedzi, TWezel * wezel)
{
size_t rozmiar;
int i;
rozmiar = wezel->Nastepny.size();
for(i = 0; i < rozmiar; i++)
sasiedzi->push_back(wezel->Nastepny[i]);
rozmiar = wezel->Poprzedni.size();
for(i = 0; i < rozmiar; i++)
sasiedzi->push_back(wezel->Poprzedni[i]);
}
funkcja dodajKrawedzDoDrzewa
#include "Lista.h"
void TLista::dodajKrawedzDoDrzewa(int * drzewo, int l, int p)
{
int mniejszy, wiekszy;
mniejszy = min(drzewo[l], drzewo[p]);
wiekszy = max(drzewo[l], drzewo[p]);
for(int i = 0; i < V; i++)
if(drzewo[i] == wiekszy) drzewo[i] = mniejszy;
}
Proszę raczej nie analizować kodu pod kątem poprawności algorytmu, czy jego optymalizacji. Wolałbym o podpowiedzenie, gdzie może występować ów błąd, który sprawia, że po wyjściu z funkcji Kruskal() pamięć, którą alokuje i używa algorytm np. przy vector czy stack (przy przeszukiwaniu), nie jest zwalniana.
Zadanie wykonuje na Visual Studio 2008 Professional (ale po kompilacji, otwieram exe z dysku z folderu Release, nie przez VS, gdyż w ten sposób algorytmy działają szybciej), na systemie Windows 7 Professional 64-bit.
Czekam na jakieś podpowiedzi z waszej strony :lol:
I chociaż nie było to dużo, to jednak mniej więcej właśnie tyle zostawało, przy każdy wywołaniu tej funkcji przez algorytm. A jak wywoływałem ileś tam tysięczny raz z kolei bez wyłączenia programu, to w końcu się pamięć zapychała i to o to właśnie chodziło. Teraz działa dobrze.
taka mała rzecz, a cieszy:P