logo elektroda
logo elektroda
X
logo elektroda
REKLAMA
REKLAMA
Adblock/uBlockOrigin/AdGuard mogą powodować znikanie niektórych postów z powodu nowej reguły.

[C] Jak usuwać elementy z listy jednokierunkowej cyklicznej?

Kostek7 20 Mar 2009 23:49 5229 8
REKLAMA
  • #1 6310174
    Kostek7
    Poziom 27  
    Posty: 1245
    Pomógł: 92
    Ocena: 61
    Mam problem z usuwaniem elementow z listy jednokierunkowej cykilcznej. Funkcja ma usuwać element na który w danym momencie wskazuje wskaźnik i przesuwac go na nastepny element. Jak to zrobić ?
    Zakładam że struktura listy jest taka :
    
    struct lista                      
    {                                  
    	int wartosc;                   
    	struct lista *nastepny;        
    };
    

    A wzkaźnik pokazujacy obecny element nazywam marker->nastepny. I jest on odpowiedniego typu.
  • REKLAMA
  • #2 6310347
    KowalD
    Poziom 17  
    Posty: 290
    Pomógł: 13
    Ocena: 3
    no jesli dobrze rozumiem, to chyba bedizesz musial... hmmm... "przeleciec" cala liste, az dotrzesz do elementu, ktorego wskaznik 'nastepny' wskazuje na ten element, ktory chcesz usunac... wtedy wykorzystujac ten wskaznik skasowac ten element (zwolnic pamiec), wskaznik ustawic na element na ktory wskazywal ten usuniety elemnt :D... i tak samo ustawic ten 'zewnetrzny' wskaznik, ktory okreslal element do usuniecia :)... taka jest moja zagmatwana opinia ;)...
  • REKLAMA
  • #3 6310413
    mykhaylo
    Poziom 14  
    Posty: 102
    Pomógł: 5
    Ocena: 5
    Wzorując się na powyższej "zagmatwanej opinii" stworzyłem coś takiego
    
    Node* start;
    
    void add(int value) {
    	if(start->Value == NULL) {
    		start->Value = value;
    	} else {
    		Node* node = (Node*)malloc(sizeof(Node)), *tmp = start;
    		node->Value = value;
    		node->Next = NULL;
    		while(tmp->Next != NULL)
    			tmp = tmp->Next;
    		tmp->Next = node;
    	}
    }
    
    void remove(int value) {
    	Node* tmp = start;
    	if(start->Value == value) {
    		start = start->Next;
    		free(tmp);
    		return;
    	}
    	Node* last = start;
    	while((tmp = tmp->Next) != NULL) {
    		if(tmp->Value == value) {
    			last->Next = tmp->Next;
    			free(tmp);
    			return;
    		}
    		last = tmp;
    	}
    }
    
    void showList() {
    	Node* tmp = start;
    	while(tmp != NULL) {
    		printf("%d\n", tmp->Value);
    		tmp = tmp->Next;
    	}
    }
    
    int main(int argc, char* argv[])
    {
    	start = (Node*)malloc(sizeof(Node));
    	start->Next = NULL;
    	start->Value = NULL;
    	for(int i = 0; i < 5; i++)
    		add(i * 10 + 1);
    	showList();
    	printf("Usuwam 1, 21, 41\n");
    	remove(1);
    	remove(21);
    	remove(41);
    	showList();
    	return 0;
    }

    Oczywiście to nie jest jedyne możliwe rozwiązanie. Można zrobić dwa publiczne pola: jedno będzie przetrzymywać wskaźnik na początek(aktualna wersja), drugi będzie wskazywać na ostatni dodany wiersz(może to przyspieszyć dodawanie).
    Ale to już akademickie rozważania.
  • REKLAMA
  • #4 6313125
    ETI_MASTA
    Poziom 1  
    Posty: 1
    Cos mi sie zdaje ze SPOJ nie chce przyjac zadania ;>
  • #5 6313409
    Kostek7
    Poziom 27  
    Posty: 1245
    Pomógł: 92
    Ocena: 61
    Naprawiłem wczoraj błąd w kodzie i tak dla pewności tłukłem w kod danymi testowymi z zadania w n kombinacjach dobre 15 min. Nic strasznego się nie stało program dzałał, nie wywalił pętlenia się w żadnym miejscu, niestety SPOJ nie chce przyjąć go jest przekroczony limit czasu :_(. Czyli wspomniane wyżej pętlenie, a nie wiem gdzie szukać błędów :_( Mam jeszcze czas do poniedziałku ale wątpię ze coś znajdę skoro nie wiem gdzie szukać. :_(
  • REKLAMA
  • #6 6313790
    BoskiDialer
    Poziom 34  
    Posty: 1530
    Pomógł: 353
    Ocena: 42
    Usuwanie z listy jednokierunkowej jest zależne od struktury. Jeśli przez aktualny obiekt rozumiemy ten, który jest pod wskaźnikiem to usuwanie wymaga przeszukania listy od początku(w celu znalezienia poprzednika). Jeśli jednak przez aktualny element rozumiemy element następny do tego pod wskaźnikiem, to można w czasie stałym usunąć obiekt (wskaźnik wskazuje na poprzednika, a więc mamy go od razu). W takim przypadku jednak odwołania do elementów będą się lekko komplikować (zamiast obj->value będzie obj->next->value) oraz będzie wymagany jeden nadmiarowy węzeł, niejako poprzedzający pierwszy. Jednak najprostszym sposobem na usuwanie w czasie stałym jest zrobienie z listy jednokierunkowej listę dwukierunkową. Jeśli ważne jest dodawanie elementów na początek/koniec oraz usuwanie z początku/końca w czasie stałym, to można dołożyć jeden nagłówek/węzeł którym zepnie się listę dwukierunkową w cykl i operacje radykalnie się upraszczają.
  • #8 6314496
    lord_dagoth
    Poziom 25  
    Posty: 860
    Pomógł: 68
    Ocena: 6
    Niech zgadne... projekt z Algorytmów i struktur danych? ;)
    Tylko czemu lista jednokierunkowa? Mieliśmy robić na dwukierunkowej :P
  • #9 6314546
    Dr.Vee
    VIP Zasłużony dla elektroda
    Posty: 1784
    Pomógł: 307
    Ocena: 76
    Kostek7 napisał:
    while(scanf("%s", dzialanie))
    czy to poprawna funkcja jesli
    dzialanie to tablica char ?

    Nie.
    Zauważ, że scanf zwraca liczbę przetworzonych konwersji, lub EOF w przypadku gdy nie wykonano żadnej konwersji lub błędu wejścia wyjścia. Zgodnie ze standardem wartość EOF jest ujemna.

    Poprawnie byłoby w takim przypadku:
    while(scanf("%s", dzialanie) == 1) /* ... */

    Pozdrawiam,
    Dr.Vee

Podsumowanie tematu

✨ Dyskusja dotyczy problemu usuwania elementów z jednokierunkowej listy cyklicznej w języku C. Struktura listy zawiera pole wartości i wskaźnik na następny element. Usuwanie elementu, na który wskazuje wskaźnik (marker->nastepny), wymaga znalezienia poprzednika elementu do usunięcia, co w jednokierunkowej liście wymaga przejścia całej listy. Zaproponowano rozwiązanie polegające na iteracji do elementu, którego wskaźnik 'nastepny' wskazuje na usuwany element, zwolnieniu pamięci i aktualizacji wskaźników. Przedstawiono przykładowy kod funkcji dodawania i usuwania elementów z listy, jednak implementacja nie jest cykliczna i może powodować przekroczenie limitu czasu w zadaniu SPOJ. Wskazano, że usuwanie w czasie stałym jest możliwe, jeśli wskaźnik wskazuje na poprzednika usuwanego elementu lub jeśli lista jest dwukierunkowa z dodatkowym węzłem nagłówkowym, co upraszcza operacje na liście cyklicznej. Poruszono także kwestie poprawnego użycia funkcji scanf do wczytywania łańcuchów znaków.
Wygenerowane przez model językowy.
REKLAMA