Elektroda.pl
Elektroda.pl
X

Search our partners

Find the latest content on electronic components. Datasheets.com
Elektroda.pl
Please add exception to AdBlock for elektroda.pl.
If you watch the ads, you support portal and users.

język C - jak skasować element (dynamiczna alokacja pamięci)

Wawa_19_ 01 Jan 2008 17:48 2789 7
  • #1
    Wawa_19_
    Level 14  
    Mam taki problem. Mianowicie jak skasować element, który jest typu struct KrawedzGrafu z pamięci i potem ustawić odpowiednio wskaźnik na następny element:

    Code:
    struct KrawedzGrafu{
    
            int odwezla;
            int dowezla;
            int waga;
    };


    gdzie w programie stworzyłem takich elementów tyle ile jest liczba_kraw:
    struct KrawedzGrafu *wsk=(KrawedzGrafu *)malloc(liczba_kraw* sizeof(struct KrawedzGrafu));



    No i obrazowo może pokarzę:

    komórka1 komórka2 komórka3 komórka4 ...... komóka_liczba_kr
    wsk[0] ,,,, wsk[1] ,,,,, wsk[2] ,,,,, wsk[3] ,,, ...... wsk[liczba_kr-1]

    No i teraz załóżmy że chcę skasowac komórkę nr 3:
    Code:
    z=2;
    
    free((wsk+z));

    no ale też chciałbym by teraz komórka4 stała się 3 (czyli wsk[3] wskaznikiem 2 itd.)
    Jak to zrobić? Aha i tak:
    Code:

    struct KrawedzGrafu{
            int odwezla;
            int dowezla;
            int waga;
            struct KrawedzGrafu *nast
    };

    że tam wstawię sobie *nast to nie mogę zrobić, bo już siedziałem nad tym algorytmem PRIMA około 20 godzin i ponad 100 linijek kodu no i już nie chcę zmieniać stuktury KrawedzGrafu tylko innym sposobem jakby się dało.:(

    Kod proszę umieszczać w znacznikach code - krzychoocpp
  • Helpful post
    #2
    shg
    Level 35  
    Nie ma lekko. Z bloku zaalokowanego przez malloc() nie zwolnisz sobie dowolnego kawałka.

    Kiedyś męczyłem coś takiego (edytor tekstu), to zrobiłem tak, że alokowałem sobie bufory powiedzmy po 10kB (to na Amidze jeszcze, tak że 10kB to dosć dużo było ;]). Podczas ładowania pliku kolejne bufory były zapełniane (ale nie do końca, algorytm starał się układać w nich kompletne linie tekstu, a jak się jakaś nie mieściła, to przenoszona była do nowego) i w razie potrzeby alokowane nowe. Jeżeli w trakcie edycji gdzieś w połowie dokumentu na przykład brakło miejsca w aktualnym buforze, to najpierw program sprawdzał, czy jest możliwość przerzucenia całej linii do kolejnego bufora, a jak nie, to tworzył nowy i linkował za aktualnie obrabianym, a przed następnym. Kupa paprania z tym była, ale chodziło o wydajność, bo założenie było takie, że miało śmigać jak szalone na procu 7.09MHz nie powodując przy tym nadmiernej fragmentacji, ani zużycia pamięci (przy 1MB RAMu każdy kilobajt się liczył ;]).

    Jeżeli obiektów nie jest dużo (powiedzmy nie więcej jak kilkaset), to poleciłbym Ci alokowanie miejsca dla każdego elementu z osobna, zwłaszcza jeżeli nie chcesz spędzić nad tym kilku dni. Straszny overhead i tak będzie, ale tak jest najprościej. Inaczej czeka Cię w zasadzie implementacja zarządzania pamięcią, czyli takie odpowiedniki malloc() i free(), ale działające na uprzednio zarezerwowanych obszarach pamięci. Takie rozwiązanie jest dużo bardziej pracochłonne, ale działa szybciej i przede wszystkim nie "zamula" systemu.

    W Twojej strukturze jest wskaźnik tylko na następny element, średnio fajnie, bo listy jednokierunkowe nie są zbyt wydajne gdy chodzi o usuwanie elementu ze środka. Najpierw trzeba znaleźć element, który wskazywał na element usuwany (czyli poprzednik usuwanego elementu), zapisany w nim wskaźnik następnika podmienić na następnik elementu usuwanego i dopiero zwolnić pamięć elementu. Pół biedy jak usuwa się tylko jeden element, ale jak byś chciał zwalnić każdy po kolei zaczynając od końca, to za każdym razem musisz przeszukać całą listę (krótszą o jeden element w każdym kolejnym kroku, ale jednak jest to sporo "mielenia").
    Znacznie łatwiej zrobić to za pomocą listy dwukierunkowej, gdzie każdy element posiadał by zapisane adres poprzednika i następnika (a pierwszy i ostatni dla zaznnaczenia tego faktu miały by wartości odpowiednich wskaźników ustawione na null). Wtedy przy usuwaniu nie trzeba przeszukiwać całej listy, tylko od razu pobrać adresy sąsiednich elementów i w nich uaktualnić wskaźniki.

    Kwestię "zamulania" systemu małymi mallocami można rozwiązać za pomocą memory pools, Na przykład ta biblioteka:
    http://256.com/sources/mpool/
    Przeznaczona jest ona dla systemów Uniksowych i nie wiem, czy pod innym systemem będzie tak łatwa do uruchomienia. Nawet jak nie, to myślę, że google znajdzie coś odpowiedniego.

    Działa to tak, że najpierw alokujesz sobie poola, który będzie w stanie pomieścić powiedzmy 100 elementów, a potem wewnątrz poola alokujesz pojedyncze obiekty, jeżeli braknie miejsca, to alokujesz kolejnego poola.
  • #3
    Wawa_19_
    Level 14  
    Nie no moja struktura wygląda tak:
    Code:
    struct KrawedzGrafu{ 
    
            int odwezla;
            int dowezla;
            int waga;
    };

    I chodzi mi o to jak usunąć 1 komórkę z ciągu powiedzmy 10-ciu nie więcej komórek typu KrawedzGrafu. Nie wierzę, że się nie da. Napisał się pan bardzo, troszkę niepotrzebnie, ale dziękuję. Przypuszczam, że pan nie czytał mojego posta całego.
  • #5
    RhinoRace
    Level 17  
    albo zrobic liste dwukierunkowa:
    Code:
    struct elem{
    
       struct KrawedzGrafu dane;
       struct elem *nast;
       struct elem *pop;
    };

    i potem alokowac pamiec tylko dla struktury elem ;)
  • #6
    Wawa_19_
    Level 14  
    struktura moja wygląda tak i koniec:
    struct KrawedzGrafu{
    int odwezla;
    int dowezla;
    int waga;
    };
    Nie mogę jej zmieniać.
    Za dużo roboty by zmieniać całe ponad 100 linijek programu.
  • Helpful post
    #7
    shg
    Level 35  
    Wawa_19_ wrote:
    struktura moja wygląda tak i koniec:
    struct KrawedzGrafu{
    int odwezla;
    int dowezla;
    int waga;
    };
    Nie mogę jej zmieniać.
    Za dużo roboty by zmieniać całe ponad 100 linijek programu.


    To coś jest nie tak z programem. Struktury są między innymi po to, żeby można było coś do nicd dodać, a reszta programu ma tej zmiany nie "zauważyć".

    Najbardziej brutalna metoda:
    1. Zaalokować miejsce na n-1 elementów
    2. Skopiować elementy sprzed elementu usuwanego do nowego obszaru.
    3. Skopiować emlementy zza usuwanego elementu do nowego obszaru (umieszczając je za poprzednio skopiowanymi elementami)
    4. Zwolnić stary obszar pamięci.

    Tak by to mogło wyglądać. Funkcja zwraca adres nowego obszaru pamięci, o ile uda się go zaalokować. Jak się nie uda, to zwraca null, a starej tablicy nie rusza.
    Code:
    struct KrawedzGrafu *usun_element(struct KrawedzGrafu *stare_elementy, unsigned int liczba_krawedzi, unsigned int indeks_elementu_do_usuniecia) {
    
    struct KrawedzGrafu *nowy;
       /* alokacja nowej (mniejszej) tablicy */
       if((nowy = (struct KrawedzGrafu *) malloc((liczba_krawedzi - 1) * sizeof(struct KrawedzGrafu))) != 0) {
          /* przeniesienie elementów sprzed elementu usuwanego, o ile nie był to pierwszy element */
          if(indeks_elementu_do_usuniecia != 0) {
             memcpy((void *) nowy, (const void*) stare_elementy, indeks_elementu_do_usuniecia * sizeof(struct KrawedzGrafu));
          }
          /* przeniesienie elementów zza elementu usuwanego, o ile nie był to ostatni element */
          if(indeks_elementu_do_usuniecia != (liczba_krawedzi - 1)) {
             memcpy((void *) (nowy + indeks_elementu_do_usuniecia), (const void*) (stare_elementy + indeks_elementu_do_usuniecia + 1), (liczba_krawedzi - indeks_elementu_do_usuniecia - 1) * sizeof(struct KrawedzGrafu));
          }
       }
       return nowy;
    }


    Jeżeli zrobisz sobie teraz tak:
    Code:
    struct KrawedzGrafu *wsk=(KrawedzGrafu *)malloc(10 * sizeof(struct KrawedzGrafu));

    to wsk[n] będzie się odwoływał do kolejnych (0 - 9) elementów.
    Ale jeżeli teraz zrobisz powiedzmy tak:
    Code:
    struct KrawedzGrafu *wsk2;
    
    if((wsk2 = usun_element(wsk, 10, 3)) == null) {
      puts("Brak pamieci");
      cokolwiek; /* kawałek kodu sprzątającego śmieci po programie */
      exit(5);  /* aczkolwiek niekoniecznie */
    }
    wsk = wsk2;


    Od tego momentu wsk[n] dla 0 <= n < 3 będą odnosić się do pierwszych trzech elementów z poprzedniej tablicy, natomiast 3 <= n < 9 będą odnosić się do elementów, które w poprzedniej tablicy miały indeksy od 4 do 9, a w obecnej mają od 3 do 8.
  • Helpful post
    #8
    RhinoRace
    Level 17  
    zmieniac 100 lini kodu? no to bardzo duze wyzwanie :p
    nie zebym sie czepial, ale czasem jak jakis algorytm nie dziala to trzeba wymyslic nowy i go zaimplementowac i niekiedy to jest wiecej niz te 100 lini
    poza tym na pewno nie bedziesz musial zmieniac wszystkich 100 lini, tylko troche mniej - o ile dobrze go napisales, bo jak bylo to na zasadzie "a nuz zadziala" to moze byc ciezko ;)