Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

[C] lista dwukierunkowa, lista cykliczna

flowers_evil 22 Wrz 2010 18:36 4559 10
  • #1 22 Wrz 2010 18:36
    flowers_evil
    Poziom 8  

    witam
    mam taką treść zadania :

    wiedząc, że zmienna wskaźnikowa o nazwie ptr wskazuje na adres dowolnego elementu listy dwukierunkowej , napisz procedurę która utworzy z istniejącej listy, liste cykliczną. Określ typ elementu listy. Lista przechowuje wartosci typu float.Poprawnie sbudowana funkcja powinna zawierać tylko jeden argument-ptr.

    Code:
    typedef struct Element_t
    
    {
           float element;
           Element_t *next;
           Element_t *prev;
    };

    Element_t *ptr;

    ptr->next=tail;
    ptr->prev=head;

    head=ptr;
    tail=ptr;





    ja to tak rozumiem ze ptr ma być i głową i ogonem ale nie wiem czy tak to zrobić.

    dana jest lista 2 kier. Na której 1 element wskazuje zmienna wskaźnikowa head. Lista przechowuje wartosci float. Napsiz fukcje która usunie z listy pierwszy znaleziony element którego wartość przechowywana spełnia nierowność: -1,5<wartosc elem<5. Argumentem funkcji jest tylko wskaźnik head funkcja zwraca pozycje usuniętego elementu.

    Code:


    # include <stdio.h>
    # include <stdlib.h>

    typedef struct Element_t
    {
           float element;
           Element_t *next;
           Element_t *prev;
    };

    Element_t *head;


    void usuń(Element_t *rob)

    {
       Element_t *prev_1, *next_1;
       
       prev_1 = rob->prev;
       next_1 = rob->next;
       
       free(rob);
     
       if ((prev_1<5 && (-1,5<next_1) )
       {head=NULL; tail=NULL; return;}
       
       if ((prev_1)&&(next_1))

       {
        prev_1->next = next_1;
        next_1->prev = prev_1;     
       }
       
       if (prev_1==NULL) {head = next_1; next_1->prev=NULL;}
       if (next_1==NULL) {tail = prev_1; prev_1->next=NULL;}
    }

    funkcje wzięłam z innego programu i troche pozmieniałam... ale nie wiem czy ona działa na pewno dobrze.

    0 10
  • Pomocny post
    #2 22 Wrz 2010 22:37
    szelus
    Specjalista - Mikrokontrolery

    No nie bardzo.
    ad.1. Lista cykliczna, czyli zapętlona. Aby zapętlić listę dwukierunkową mając wskaźnik na jej dowolny element, musisz przejść całą listę w przód aby znaleźć ostatni element i w tył, aby znaleźć pierwszy element, a następnie zmienić wskaźniki next ostatniego elementu aby wskazywał na pierwszy i prev pierwszego elementu, aby wskazywał na ostatni.

    ad.2. Też musisz przejść po liście aby odnaleźć ten element do usunięcia. Słyszałaś o pętlach? Poza tym, z wartościami musisz porównywać wartość elementu, a nie wskaźnik na element.
    --
    A i jeszcze definicja typu prawie dobrze, ale składnia typedef wymaga podania nazwy deklarowanego typu po definicji. Ponieważ struktura zawiera pola odwołujące się do niej samej (wskaźniki), to albo trzeba je definiować przez użycie bezpośrednio nazwy struktury, albo w dwóch krokach, tzn:

    Code:

    typedef struct s_element
    {
        float element;
        struct s_element *next;
        struct s_element *prev;
    } Element_t;

    lub
    Code:

    typedef struct s_element Element_t;
    struct s_element
    {
        float element;
        Element_t *next;
        Element_t *prev;
    };

    0
  • #3 23 Wrz 2010 09:58
    flowers_evil
    Poziom 8  

    ad 1.

    Code:



    typedef struct s_element
    {
        float element;
        struct s_element *next;
        struct s_element *prev;
    } Element_t;

    Element_t *head, *tail;
    Element_t *ptr;
    Element_t *tmp; // zmienna wykorzystywana przez funkcję

    tmp=ptr;



    if((tmp->prev)!=NULL)/////teraz próbuję dojść do głowy
                 
    {
       while(tmp!=NULL)
       {
        head=tmp;
        tmp=tmp->prev;
         
        head->prev=tail;   /// jak już jestem na głowie to robie że jego prev jest wskazaniem na ogon


        }
    }     
    else     //albo już jestem na głowie

    {
    head=tmp;
     head->prev=tail; //robie to samo co wyżej
    }

     

    if((tmp->next)!=NULL) // teraz szukam ogonka
       {
             while(tmp!=NULL)
            {
               tail=tmp;
                tmp=tmp->next;
               tail->next=head; // jak juz jestem na ogonie to robie ze jego next jest wskazaniem na głowę
              }
       }     
    else 
    {        // albo już jestem na ogonku
    tail=tmp;
    tail->next=head;  // jak już jestem na ogonku to robię to co wyżej
    }


    0
  • #4 23 Wrz 2010 10:12
    maciek_slon
    Poziom 29  

    I to działa? Bo, cytując klasyka, "ja tu widzę niezły burdel"*

    * "Seksmisja"

    0
  • Pomocny post
    #5 23 Wrz 2010 10:16
    szelus
    Specjalista - Mikrokontrolery

    No już jest dużo lepiej. Tylko:
    a/ zrób z tego funkcję, coś w rodzaju:

    Code:

    void make_cyclic( Element_t *ptr )
    {
    ...
    }

    b/ wstrzymaj się z podmienianiem do momentu, jak już znajdziesz głowę i ogon (czyli po zakończeniu obu pętli).

    Dodatkowo można trochę uprościć usuwając if-y przed pętlami, wystarczy zmienić warunek pętli, np.
    Code:

    while (tmp->prev != NULL)
    {
        tmp = tmp->prev;
    }
    head = tmp;

    0
  • Pomocny post
    #6 23 Wrz 2010 10:21
    maciek_slon
    Poziom 29  

    I uwaga jedna ode mnie - pisząc pętle uważaj na to, co wrzuasz DO pętli, a co chcesz wykonywać POZA nią. W Twoim obecnym kodzie w pętli każdemu elementowi przypisujesz tail jako poprzednik, a powinno to być zrobione raz, po skończeniu (co też wynika z Twojhego komentarza).

    Dodatkowo tak jak poprzednik napisał - przypisania na końcu. W chwili obecnej jako poprzednik do head przypisujesz tail, który nie jest zainicjowany (a więc są to jakieś przypadkowe dane z pamięci)

    Dodano po 2 [minuty]:

    A, no i jeszcze jedna uwaga, ale to już bonus - na początku sprawdzaj, czy ptr (podany argument) nie jest NULLem. Jeśli ktoś poda do funkcji NULLa, to pięknie się ona wykrzaczy (w obecnej postaci)

    0
  • #7 23 Wrz 2010 11:54
    flowers_evil
    Poziom 8  

    Pozmieniałam i jak teraz ?

    Code:



    typedef struct s_element
    {
        float element;
        struct s_element *next;
        struct s_element *prev;
    } Element_t;

    Element_t *head, *tail;
    Element_t *ptr;
    Element_t *tmp; // zmienna wykorzystywana przez funkcję

    tmp=ptr;

    void cykliczna( Element_t *ptr )
    {
         
         
         while (tmp->prev != NULL)
       
              {
                 
                   tmp=tmp->prev;
                     
               }     
            head=tmp;
            head->prev=tail;
     

       while (tmp->next != NULL)
              {
               
               tmp=tmp->next;
               
              }
        tail=tmp;
        tail->next=head;
    }

    0
  • Pomocny post
    #8 23 Wrz 2010 12:40
    szelus
    Specjalista - Mikrokontrolery

    Programowanie nie wybacza drobnych błędów. Przyjrzyj się dokładnie, co napisałaś i czytaj dokładnie uwagi.

    Code:

    typedef struct s_element
    {
        float element;
        struct s_element *next;
        struct s_element *prev;
    } Element_t;

    void cykliczna( Element_t *ptr )
    {
        Element_t *head, *tail;
        Element_t *tmp; // zmienna wykorzystywana przez funkcję

        if (ptr == NULL)
        {
            return;
        }

        tmp=ptr;

        while (tmp->prev != NULL)
        {
               tmp=tmp->prev;
        }     
        head=tmp;
     
        tmp = ptr;
        while (tmp->next != NULL)
        {
               tmp=tmp->next;
        }
        tail=tmp;

        // dopiero teraz tail pokazuje na ostatni element!!!
        head->prev = tail;
        tail->next=head;
    }

    Wiesz, dlaczego tak? Czy to Twój pierwszy w życiu kawałek programu?

    0
  • #9 23 Wrz 2010 13:00
    flowers_evil
    Poziom 8  

    Rozumiem wszystko prócz tego :

    Code:
      if (ptr == NULL)
    
        {
            return;
        }

    bo jeśli ptr jest nullem to wtedy co ? funckja nie zwraca nic tak ?

    Code:

        head=tmp;
        tail=tmp;


    po tych linijkach tmp jest zarówno głową jak i ogonem ?


    Tak można powiedzieć , że to mój pierwszy "program "

    0
  • Pomocny post
    #10 23 Wrz 2010 13:10
    szelus
    Specjalista - Mikrokontrolery

    flowers_evil napisał:
    Rozumiem wszystko prócz tego :
    Code:
      if (ptr == NULL)
    
        {
            return;
        }

    bo jeśli ptr jest nullem to wtedy co ? funckja nie zwraca nic tak ?

    To dobra praktyka inżynierska. Jeśli ktoś przekaże NULL jako argument to funkcja nic po prostu nie zrobi. To rozwiązanie minimalistyczne. Ewentualnie można by zwracać jakiś kod błędu itp. Co by się mogło stać bez takiego zabezpieczenia napisał Maciek wyżej.
    Cytat:

    Code:

        head=tmp;
        tail=tmp;


    po tych linijkach tmp jest zarówno głową jak i ogonem ?

    Przecież te linijki nie są obok siebie, to raz. Podstawienie działa w lewo, to dwa.
    Chyba teraz ja nie nadążam za Twoim tokiem rozumowania...

    0
  • #11 23 Wrz 2010 13:18
    flowers_evil
    Poziom 8  

    Dobra teraz już rozumiem po prostu
    head=tmp i to zostaje jkaby w pamięci potem zajmujemy się znowu tmp i znajdujemy tail za pomocą niego .
    I wtedy mamy głowe i ogon i na koniec łączymy je żeby była to lista cykliczna

    0