[c] lista jednokierunkowa

[FEMO]

czy umiałby ktoś wytłumaczyć lub zna jakąś dobrą strone gdzie jest wytłumaczone łopatologicznie jak się tworzy liste jednokierunkową która wczytuje tylko liczby całkowite (liczby na liście nie mogą się powtarzać) i żeby można było po zakończeniu w pisywania liczb
zliczyć ilość w prowadzonych liczba.

za pomoc z góry dziękuje

[soku11]

Sa dwie mozliwosci tworzenia listy. Na tablicy oraz na wskaznikach. Na tablicy ciezko jest zrobic usuwanie, wiec polecam robic na wskaznikach. Mozna jeszcze wstawiac odrazu sortujac, albo normalnie. Napisze jak to zrobic wtawiajac normalnie, bez sortowania. Wtedy:
Tworzysz sobie strukture bedaca jednym wezlem takiej listy:

Kod: Zaznacz cały

typedef struct Node
{
  int Value;              /* Wartosc przechowywana */
  struct Node* Next;  /* Wskaznik na nastepny element */
} Node;

Z takich polaczonych pol bedzie sie skladac twoja lista. Ma ona wskaznik na nastepny element, jest wiec jednokierunkowa.
Teraz mozesz albo zrobic sobie jakis wskaznik na pierwszy element, albo zrobic druga strukture bedaca juz ta twoja lista. Ja preferuje drugi wariant, gdyz mozna odrazu dodac sobie zmienna do zliczania elementow (zeby pozniej nie latac w kolko po liscie). Tak wiec robisz sobie kolejna strukture:

Kod: Zaznacz cały

typedef struct List
{
  unsigned int Size; /* Zmienna na ilosc wezlow w strukturze */
  Node* First;        /* Wskaznik na pierwszy element */
} List;

Teraz wystarczy dopisac do tej implementacji funkcje:

Kod: Zaznacz cały

void ListInit(List* list)
{
  if(!list)    /* Taka kontrola bledow */
    return;
  
  list->Size=0;       /* 0 elementow na poczatku */
  list->First=NULL; /* Lista pusta - nie ma poczatku */
}

int ListInsert(List* list,int value)
{
  Node* Tmp=NULL; /* Do przechodzenia po liscie */
  Node* End=NULL;  /* Do trzymania konca listy */
  Node* New=NULL; /* Do trzymania wskaznika na nowy wezel */

  if(!list)          /* Nie ma listy - nie ma gdzie wstawiac - zwroc blad */
    return -1;

  Tmp=End=list->First;
  while(Tmp)
  {
    if(Tmp->Value==value) /* Konflikt wartosci */
      break;
    End=Tmp;                 /* Zapamietaj wczesniejszy wezel - do wtawiania na koniec */
    Tmp=Tmp->Next;       /* Przejdz do nastepnego wezla */
  }

  if(Tmp)    /* Jesli nie przeszlismy calej listy - znaleziono jakis element o danym kluczu */
    return -2; /* Blad - klucz istnieje */

  New=(Node*)malloc(sizeof(Node)); /* Stworz dynamicznie nowy wezel */
  if(!New)
    return -3; /* Blad allokacji pamieci */

  New->Next=NULL;  /* Uzueplnij dane wezla */
  New->Value=value; 
  ++(list->Size);      /* Zwieksz ilosc elementow w liscie */

  if(!End) /* Nie ma konca - wstaw na pierwszy element listy */
  {
    list->First=New;
    return 0;
  }
  
  /* Wstaw na koniec */
  End->Next=New;
  return 0;
}

Pozostale funkcje (szukanie, kasowanie wedlug klucza, kasowanie calej listy, zliczanie kluczy) pozostawiam do napisania jako cwiczenie. Pozdrawiam.

[FEMO]

czy node to nazwa struktury? czy zamiast node mozna wpisać jakąś inną nazwe?

co zanczy tmp i malloc oraz o co chodzi z tym kluczem?

[adek05]

node

to z angielskiego węzeł.
Możesz to nazywać jak chcesz, ale tak się przyjęło nazywać elementy list, drzew i stąd FEMO użył tej nazwy.

[FEMO]

jakie biblioteki się do tego wykorzystuje i czy nie powinno się tu czegoś na początku zadeklarować?

[soku11]

malloc jest funkcja rezerwujaca tyle bajtow ile sie jej poda jako argument. Uzywajac jej w konkekscie malloc(sizeof(Node)) rezerwuje sobie potrzebna pamiec na jeden wezel, oraz zwraca wskaznik na poczatek tej pamieci. Tmp, to nazwa zmiennej. Tmp od angielskiego temporary - tymczasowy Ogolnie w tym przykladzie potrzebne jest chyba tylko stdlib.h, bo tam jest deklaracja funkcji malloc. Aby stworzyc pusta liste tworzysz zmienna typu List, oraz ja czyscisz napisana przezemnie metoda:

Kod: Zaznacz cały

int main()
{
  List lista1;

  ListInit(&lista1);

  /*ListInsert(&lista1,5);
  ...
  */


  ListDelete(&lista1);
  return 0;
}

Nie ma jeszcze metody ListDelete, a on powinna kasowac cala liste (przechodzic od elementu list->First do konca (NULL).

Pozdrawiam.

[FEMO]

próbowałem skompilować to co mi podałeś i mi pokazuje że nie zadeklarowano:
node tmp end list new listinit
}; to też mi zaznacza

może robie coś nie tak

[soku11]

Racja, zapomnialem dopisac jednej rzeczy przy typedefach - juz poprawilem
Kod poprawny + funkcja do kasowania:

Kod: Zaznacz cały

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

typedef struct Node
{
  int Value;
  struct Node* Next;
} Node;

typedef struct List
{
  unsigned int Size;
  Node* First;
} List;

void ListInit(List* list)
{
  if(!list)
    return;

  list->Size=0;
  list->First=NULL;
}

int ListInsert(List* list,int value)
{
  Node* Tmp=NULL;
  Node* End=NULL;
  Node* New=NULL;

  if(!list)
    return -1;

  Tmp=End=list->First;
  while(Tmp)
  {
    if(Tmp->Value==value)
      break;
    End=Tmp;
    Tmp=Tmp->Next;
  }

  if(Tmp)
    return -2;

  New=(Node*)malloc(sizeof(Node));
  if(!New)
    return -3;

  New->Next=NULL;
  New->Value=value;
  ++(list->Size);

  if(!End)
  {
    list->First=New;
    return 0;
  }

  End->Next=New;
  return 0;
}

void ListClear(List* list)
{
  Node* ToDelete=NULL;
  Node* Next=NULL;

  if(!list || list->Size==0)
    return;

  ToDelete=Next=list->First;
  while(ToDelete)
  {
    Next=ToDelete->Next;
    free(ToDelete);
    ToDelete=Next;
  }
  list->First=NULL;
  list->Size=0;
}

int main(void)
{
  List lista1;

  ListInit(&lista1);

  ListInsert(&lista1,10);
  ListInsert(&lista1,20);
  ListInsert(&lista1,30);
  ListInsert(&lista1,40);

  ListClear(&lista1);

  return 0;
}

Pozdrawiam.

[FEMO]

czegoś tu nie rozumiem po co czyścić pustą liste bo jakoś elementów nie moge dodać

[soku11]

Kod pisalem z glowy, bez sprawdzania czy wszystko na 100% dziala... Twoje pytanie tez nie rozumiem... Tworzac obiekt typu List tworzysz strukture ze wskaznikiem na pierwszy element oraz licznikiem ilosci wezlow. Tak sie sklada, ze najczesciej taka lista ma w sobie smieci, wiec trzeba najpierw wyczyscic zawartosc (wskaznik na NULL, size na 0). Po to jest funkcja ListInit(). Dalej wstawiam jakies elementy, a na koncu po sobie sprzatam, czyli kasuje wszystkie zaalokowane dynamicznie wezly w liscie i ustawiam rozmiar na 0 i wskaznik na NULL (tak jak bylo na poczatku).

Nie wiem czy o to chodzilo... Pozdrawiam.

[FEMO]

no właśnie jak do tej listy wstawić jakieś elementy ?

[adek05]

Masz zadeklarowaną f-cję

Kod: Zaznacz cały

int ListInsert(List* list,int value)

Zatem wywołując ListInsert(lista, wartość) wstawisz daną wartość do podanej listy.

[FEMO]

no jakoś nie bardzo bo po kompliacji po jawia mi się czarny ekran i jak coś wcisne to się zamyka program

[soku11]

Radze pouczyc sie jezyka, bo naprawde chyba wogole go nie umiesz... A dlaczego niby ma ci cos wyswietlac?? Czy napisales cos, zeby ci ta liste wyswietlalo?? W programowaniu nie dzieje sie nic, dopoki sam czegos nie napiszesz... Lista owszem - jest, ale w pamieci. Chcesz ja wyswietlic, napisz funkcje ktora to robi i po sprawie. Pozdrawiam.

[FEMO]

nie umiem tworzyć list jednokierunkowych jakbym umiał napisać funkcje która mi wyświetli tą liste to bym tu nie pisał