suma elementów na liście 2 kierunkowej i 1 kier. sprawdzenie

[flowers_evil]

witam ,
mam takie zadanie, że muszę policzyć sumę elementów na liście dwukierunkowej i jednokierunkowej

2 kierunkowa :

Kod: Zaznacz cały

Struct Element_t 
{ int element;
Element_t *next;
Element_t *prev;
}


Int Policz(element *ptr)
{
int sumacała=0;  
int suma1=0;
int suma2=0;
Element_t *head, *tail ;
Element_t *tmp=ptr;


   while(tmp->prev!=NULL)
    { 
     suma1=suma1+1;
     tmp=tmp->prev;
    }
 while (tmp->next!=NULL)
    {
      suma2=suma2+1;
      tmp=tmp->next;
     } 

return (sumacała=suma1+suma2);
}

lista 1 kierunkowa :

Kod: Zaznacz cały

Struct Element_t 
{ int element;
Element_t *next;
}


Int Policz1kier(element *ptr)
{
   Element_t *head, *tail ;
  Elemenet_t *tmp;
   int ilosc=0;
  
  while(tmp!=ptr)
 {
   ilosc =ilosc +1;
   tmp=tmp->next;
  }

return ilosc;

[Crizz]

Zacznijmy od listy jednokierunkowej.

Wskaźniki head i tail zostały zadeklarowane, ale nie są nigdzie używane. Nie jest to błąd, ale kompilator prawdopodobnie Cię ostrzeże.

Wskaźnik tmp nie został nigdzie zdefiniowany. Potem porównujesz ptr z tmp, a tmp wskazuje na losowe miejsce w pamięci. Rozumiem, że jako argument dostajemy głowę listy? Co miałaś na myśli w tym warunku:

Kod: Zaznacz cały

while(tmp!=ptr)

To miała być ilość elementów czy suma kluczy? Jeśli ilość kluczy, to powinnaś dodawać wartości kluczy kolejnych elementów do zmiennej ilosc, a nie zwiększać ją ciągle o jeden.

[flowers_evil]

while(tmp!=ptr)

tutaj miałam na myśli to że dodajemy elementy dopóki tmp jest różne od ptr bo jak będą takie same to znaczy że przeszliśmy całą listę.

Ahh zapomniałam dodać że ta jednokierunkowa jest cykliczna !!

chodziło o podanie ilości elementów.


hymm to może tak :

Kod: Zaznacz cały

int licz (Element_t *head)
{

int l=0;
Element_t *tmp=head;

while(tmp!=head)
{  tmp=tmp->next;
    l=l+1;
 }

return l;
}

[Crizz]

Cykliczność wszystko zmienia

Byłoby OK, gdyby nie ustawienie wskaźnika tmp na głowę. W ten sposób warunek przerwania pętli jest prawdziwy na samym początku, czyli wnętrze pętli nie moze się w ogóle wykonać. Ponieważ program jest prawie OK, to może pokażę, jak ja bym to zrobił:

Kod: Zaznacz cały

int licz (Element_t *head)
{

int l=0;
Element_t *tmp;
if(head) //jeśli w ogóle list ma głowę, czyli nie jest pusta - jeśli nie ma to pominiemy większosć dalszej części programu
{
    l=l+1; //bo już wiemy, że lista ma co najmniej głowę
    if(tmp=head->next) //przypisujemy wartość pola next głowy do tmp i jednocześnie sprawdzamy, czy nie jest NULL 
    {
        l=l+1; //bo już wiemy, że lista ma co najmniej dwa elementy
        while(tmp!=head) //tu już tmp nie pokazuje na głowę
        {
            tmp=tmp->next;
            l=l+1;
        }
    }        
return l;

}

Aha, są dwie interpretacje jednoelementowej listy cyklicznej, tzn.:
head->next==head (w jednoelementowej liście głowa jest spięta sama ze sobą)
head->next==NULL (w jednoelementowej liście pole next głowy pokazuje na NULL)

Ja w swoim rozwiązaniu przyjąłem tę druga interpretację.

[flowers_evil]

ok rozumiem


A lista 2 kierunkowa?
Na pewno da się prościej niż tak żeby suma składała się ze składowych ale czy tak w ogole jest dobrze ?

[Crizz]

A ta lista też jest cykliczna?

Tzn. ja do końca nie rozumiem, czemu taki sposób.

[flowers_evil]

Nie ta nie jest cykliczna .

Najpierw liczę ilość elementów w prawą stronę a potem w lewą stronę od tmp.
A potem sumuję i wychodzi suma elementów.

[Crizz]

Czyli rozumiem, że argument funkcji to dowolny element listy, niekoniecznie głowa?

Skoro tak, to tu jest ten sam problem, co przy liście jednokierunkowej - porównujesz tmp z ptr, a tmp nie ma przecież żadnej sensownej wartości, bo nie został zdefiniowany.

Warunki w pętlach powinny raczej sprawdzać, czy doszliśmy już do ogona (w przypadku poruszania się do przodu) lub też głowy (w przypadku poruszania się do tyłu). Skorzystaj z tego, czym się różni głowa i ogon od pozostałych elementów listy .

[flowers_evil]

Tak argumentem jest wskaźnik na dowolny element.

Kod: Zaznacz cały

Element_t *tmp=ptr;  // ale tutaj ustawiam że tmp jest równe ptr czyli temu elementowi od którego zaczynam zliczanie.  

  while(tmp->prev!=NULL)
  while(tmp->prev!=NULL)   // a te dwa warunki nie wystarczą ? no bo pierwszy oznacza że dopóki tmp nie jest głową to ma zliczyć elementy . A 2 że dopóki tmp nie jest ogonem to mamy liczyć elementy. Czyli jakby poruszamy się w prawą i lewą strone od elementu ptr  i zliczamy dopóki nie dojdziemy odpowiednio do ogona i głowy. 

[Crizz]

Przepraszam, chyba niepotrzebnie się przyczepiłem (coś źle przeczytałem). Te warunki są OK.

Jest jednak jeden poważny problem: w obu pętlach korzystasz z tmp. W pierwszej pętli natomiast zmieniasz go tak, że w efekcie pokazuje na sam początek (głowę) listy. Oznacza to, że w drugiej pętli przesuwasz go od głowy aż do samego ogona (a przecież nie o to chodziło). Najlepiej stwórz sobie jakiś dodatkowy wskaźnik tmp2=tmp i korzystaj z niego w drugiej pętli.

[flowers_evil]

AA rozumiem czyli dodam drugi wskaźnik tmp2 dodam go w 2 pętli i powinno być ok ?

[Crizz]

Tak.

[flowers_evil]

Dziękuje.