lista dodanie nowego elementu tylko wytlumaczenie kodu

[flowers_evil]

Witam,
mam taki kod funkcji która dołącza nowy element do listy i kilki rzeczy w niej nie rozumiem tj:

Kod: Zaznacz cały

int push(int x)
{
 Element_t *nowy = (Element_t *) malloc ( sizeof (Element_t) );     //tutaj tworzymy nowy element ale czy nie wystarczyłoby tylko : Element_t *nowy 
 
 if (!head)              // nie bardzo rozumiem ten zapis .. czyli co jest różne od głowy ??
 {
            nowy->next = NULL;
            nowy->prev = NULL;
            nowy->element = x;
            head = nowy;     
            tail = nowy;        // tutaj powstaje lista która składa się z jednego elementu
                                   // tego nowego to rozumiem 
 }
  else
   {
       Element_t *tmp;    //nie bardzo rozumiem ta druga połowe kodu wiec czy ktos                
       tmp = head;         //może wytlumaczyc co się dzieje w każdej linijce? zaczynajac od tej
       nowy->next = head;
       nowy->prev = NULL;
       nowy->element = x;
       (tmp->prev)=nowy;
       head = nowy;
            
   }
return 0;
}            

Dziękuje za pomoc

[Crizz]

Linijka 3: nie wystarczyłoby.

Kod: Zaznacz cały

Element_t *nowy;

to deklaracja wskaźnika na obiekt typu Element_t. W ten sposób informujemy kompilator, że być może w dalszej części programu będziemy korzystać ze zmiennej o nazwie nowy. Ta zmienna na razie pokazuje na losowe miejsce w pamięci (czyli zawiera "śmieci").

Kod: Zaznacz cały

Element_t *nowy = (Element_t *) malloc ( sizeof (Element_t) );

to deklaracja tego samego wskaźnika połączona z definicją. Tworzymy wskaźnik o nazwie "nowy" i od razu każemy mu pokazywać na nowo utworzony obiekt dynamiczny typu Element_t (dla którego rezerwujemy pamięć funkcją malloc). Czy to miał być C++? Jeśli tak, to dziś w C++ nie korzysta się raczej z funkcji malloc; zamiast niej używa się operatora new, tzn.:

Kod: Zaznacz cały

Element_t *nowy = new Element_t;

Linijka 6: w C++ każda niererowa wartość jest prawdą, natomiast wartość zero jest fałszem. W związku z tym wskazana linijka jest równoważna z:

Kod: Zaznacz cały

if(head==NULL); 

bo rozumiem, że head jest wskaźnikiem na Element_t. (UWAGA: kiedy tworzymy nową pustą listę, należy to robić w następujący sposób: Element_t head=NULL; w przeciwnym wypadku head pokazuje znów na losowe miejsce w pamięci i mało prawdopodobne jest, ze akurat na NULL - tu wewnątrz funkcji nie ma z tym akurat problemu).

Linijki od 17:

Kod: Zaznacz cały

  else
   {
       Element_t *tmp; //deklarujemy nowy wskaźnik o nazwie tmp        
       tmp = head; //ustawiamy go na to samo, na co pokazuje head, czyli  na głowę listy
       nowy->next = head; //pole next nowego elementu ma pokazywać na głowę (bo wstawiamy nowy element na początek listy - głowa staje się drugim elementem listy
       nowy->prev = NULL; //skoro nowy element jest nową głową, to jego pole prev ma pokazać na NULL
       nowy->element = x; //wstawiamy do nowego elementu wartość klucza
       (tmp->prev)=nowy; //pole prev dotychczasowej głowy listy ma wskazywać na nowy element
       head = nowy; //wskaźnik head teraz już pokazuje na nową głowę listy
           
   }
return 0;
}           

[Konikov]

Kod: Zaznacz cały

 Element_t *nowy = (Element_t *) malloc ( sizeof (Element_t) );     //tutaj tworzymy nowy element ale czy nie wystarczyłoby tylko : Element_t *nowy

Dając malloc'a inicjalizujesz pamięć. Samo napisanie:

Kod: Zaznacz cały

Element_t *nowy

mówi TYLKO I JEDYNIE, że nazwa "nowy" oznacza wskaźnik na Element_t. NIE inicjalizuje to w żadnym stopniu pamięci dla obiektu, który wskazuje "nowy". Z kolei jak tak napiszemy, to mamy wskaźnik, a także zajmujemy odpowiednią ilość miejsca na Element_t i ów wskaźnik ustawiamy na to miejsce.

Kod: Zaznacz cały

 if (!head)              // nie bardzo rozumiem ten zapis .. czyli co jest różne od głowy ??

if(coś) <- sprawdza, czy coś jest zerem. Jeśli nie, to wynik jest prawdą. Jeśli "coś" jest wskaźnikiem, to takie wyrażenie jest prawdziwe, jeśli "coś" jest zainicjowane (na coś już wskazuje). Null == 0.

Kod: Zaznacz cały

            tail = nowy;        // tutaj powstaje lista która składa się z jednego elementu
                                   // tego nowego to rozumiem 

Nie ma jeszcze żadnego elementu (bo nie ma głowy!), więc tworzymy listę jednoelementową ;]

Kod: Zaznacz cały

  else
   {
       Element_t *tmp;          
       tmp = head;        // pod obiekt tymczasowy podpinamy to, na co wskazuje obecna głowa (widzę, że głowa jest wskaźnikiem
       nowy->next = head; // ustawiamy "następny" naszego nowego elementu na obecną głowę
       nowy->prev = NULL; // obecny nie będzie miał poprzednika (sam będzie nową głową)
       nowy->element = x; // przypisujemy mu wartość przekazaną funkcji
       (tmp->prev)=nowy; // starej głowie, którą trzymamy w "tmp" wpisujemy nową jako element poprzedni
       head = nowy; // nowa głowa - "nowy" ;]
            
   }

[flowers_evil]

tutaj :

Kod: Zaznacz cały

 tail = nowy;        // tutaj powstaje lista która składa się z jednego elementu
                                   // tego nowego to rozumiem 

chodziło mi o to że rozumiem jakby pierwszą część kodu od 6 do 12 linijki nie tylko tą 12

[Konikov]

tutaj :

Kod: Zaznacz cały

 tail = nowy;        // tutaj powstaje lista która składa się z jednego elementu
                                   // tego nowego to rozumiem 

chodziło mi o to że rozumiem jakby pierwszą część kodu od 6 do 12 linijki nie tylko tą 12

Tak, cały ten pierwszy blok po if jest utworzeniem listy jednoelementowej. Wiem, jak to czasem może być z pozornym zrozumieniem, więc i tak pokrótce omówiłem ;]

Najlepiej sobie zasymulować takie rzeczy na kartce, krok po kroku.