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

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:



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:

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:
ż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

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.

Nie no moja struktura wygląda tak:

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.

jeżeli masz listę jednokierunkową, to najpierw musisz odnaleźć element poprzedzający ten, który musisz usunąć. Resztę masz opisaną tu: https://www.elektroda.pl/rtvforum/topic907134.html

albo zrobic liste dwukierunkowa:

i potem alokowac pamiec tylko dla struktury elem

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.

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.


Jeżeli zrobisz sobie teraz tak:

to wsk[n] będzie się odwoływał do kolejnych (0 - 9) elementów.
Ale jeżeli teraz zrobisz powiedzmy tak:


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.

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