[C] Listy i wskaźniki

[teusiek]

Przyjmijmy następującą deklarację:

Kod: Zaznacz cały

typedef struct ElemListy {
   int wartosc;
   struct ElemListy *nast;
} ElemListy;

Napisać program zawierający następujące funkcje:
1) ElemListy* WstawDoListyRosnacej(ElemListy* pocz, int k);
Ta funkcja ma zwrócić wskaźnik do początku listy otrzymanej przez wstawianie nowego elementu o wartości k do uporządkowanej rosnąco listy o początku z adresem pocz tak, aby nowa lista będzie nadal uporządkowana rosnąco.
2) ElemListy* Stworz();
Ta funkcja ma zwrócić wskaźnik do początku listy stworzonej z wartości wczytanych z klawiatury.
3) ElemListy* Posortuj(ElemListy* pocz);
Ta funkcja ma posortować listę o początku z adresem pocz i zwrócić posortowaną listę.

Program powinien demonstrować działanie wyżej wymienionych funkcji. Na przykład, stworzy nową listę, sortuje ją i wyświetla wartości jej elementów.

Byłbym bardzo wdzięczy za pomoc

[kalwi]

Pomoc != gotowiec

[Mariusz M]

To kolejna złota myśl twojego guru ?
Tylko że w każdej dobrej książce mamy obok teorii gotowce

Funkcje mają zwracać wskaźnik ?
Można by to napisać z wskaźnikiem na wskaźnik (bo referencja wchodzi dopiero w C++)

Aby funkcja Posortuj miała sens to trzeba dopisać inne funkcje wstawiające
jak wstawianie przed wskazanym elementem czy wstawianie za wskazanym elementem
Gdybyśmy mieli te funkcje wstawiające to funkcje Posortuj można by zrealizować
jako sortowanie przez scalanie
Przy sortowaniu list wystarczy przestawić wskaźniki i dlatego sortowanie przez scalanie
ma przewagę nad innymi metodami bo nie potrzeba dodatkowej pamięci jak w przypadku tablic
Jedyna potrzebna pamięć to ta na obsłużenie rekurencji czyli O(log n)
Jeżeli chcemy mieć listę stale posortowaną to lepszym pomysłem będzie sortowanie przez wstawianie

Nie ma żadnej funkcji do usuwania elementów ?


Używając wskaźnika na wskaźnik te funkcje mogłyby wyglądać tak

Kod: Zaznacz cały

void WstawDoListyRosnacej(ElemListy **pocz,int k)
{
     ElemListy *x;
     ElemListy *y;
     ElemListy *z;
     x=(ElemListy *)malloc(sizeof(ElemListy));
     x->wartosc=k;
     if((*pocz)==NULL)
     {
          x->nast=NULL;
          (*pocz)=x; 
     }
     else
     {
        y=(*pocz);
        z=NULL;
        while(y!=NULL && x->wartosc>y->wartosc)
        {
            z=y;
            y=y->nast;
        } 
        if(z==NULL)
        {
           x->nast=(*pocz);
           (*pocz)=x;
        }
        else
        {
          x->nast=y;
          z->nast=x;  
        }
     }
}

void Stworz(ElemListy **pocz)
{
    (*pocz)=NULL;
}

void Podziel(ElemListy *pocz, ElemListy **przod, ElemListy ** tyl)
{
     ElemListy *wolny;
     ElemListy *szybki;
     if(pocz==NULL || pocz->nast==NULL)
     {
         (*przod)=pocz;
          (*tyl)=NULL;
     }
     else
     {
         wolny=pocz;
         szybki=pocz->nast;
         while(szybki!=NULL)
         {
             szybki=szybki->nast;
             if(szybki!=NULL)
             {
                 szybki=szybki->nast;
                 wolny=wolny->nast;    
             }
          } 
         (*przod)=pocz;
         (*tyl)=wolny->nast;
          wolny->nast=NULL;      
      }  
}

ElemListy *Scal(ElemListy *l1,ElemListy *l2)
{
       ElemListy *nowyPocz=NULL;
       ElemListy *S;
       
       if(l1==NULL)  return l2;
       if(l2==NULL)  return l1;
       
       if(l1!=NULL && l2!=NULL)      // Tutaj na tę instrukcję if natrafiłem u pewnego Hindusa ale 
       {                                    //  nie wydaje mi się ona potrzebna 
           if(l1->wartosc<=l2->wartosc)
           {
                 S=l1;
                 l1=S->nast;
           }
           else
           {
                S=l2;
                l2=S->nast; 
           }                              
       } 
      nowyPocz=S;
     
      while(l1!=NULL && L2!=NULL)
      {
          if(l1->wartosc<=l2->wartosc)
          {
              S->nast=l1;
              S=l1;
              l1=S->nast;
          }
          else
         {
              S->nast->l2;
              S=l2;
              l2->S->nast;
         }
      }
      if(l1==NULL) S->nast=l2;
      if(l2==NULL) S->nast=l1;
      
      return nowyPocz;
}

void Posortuj(ElemListy **pocz)
{
    ElemListy *p1;
    ElemListy *p2;
    if((*pocz)!=NULL && (*pocz)->nast!=NULL)
    {
            Podziel((*pocz),&p1,&p2);
            Posortuj(&p1);
            Posortuj(&p2);
            (*pocz)=Scal(p1,p2)
    }   
}

Tutaj koleś nie kryje się z tym że w jego kodach są błędy

Kod: Zaznacz cały

http://www.wozna.org/students/2010-2011/algorytmy2/asd05.pdf

[url]http://www.wozna.org/students/2010-2011/algorytmy2/asd06.pdf[/url]

Tutaj jet przykład gdzie w pseudokodzie była luka a tzw gotowiec był dobrze napisany
i porównanie gotowca z pseudokodem pozwoliło szybko wyłapać tę lukę

Jakiś czas temu zebrałem przykładowe funkcje do obsługi listy
Wystarczy użyć forumowej szukajki