[c] lista jednokierunkowa

FEMO
Użytkownik
Użytkownik
Posty: 348
Rejestracja: 13 lut 2007, o 17:15
Płeć: Mężczyzna
Lokalizacja: warszawa
Podziękował: 163 razy

[c] lista jednokierunkowa

Post autor: FEMO » 21 gru 2008, o 15:05

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
Użytkownik
Użytkownik
Posty: 6607
Rejestracja: 16 sty 2007, o 19:42
Płeć: Mężczyzna
Podziękował: 119 razy
Pomógł: 1822 razy

[c] lista jednokierunkowa

Post autor: soku11 » 21 gru 2008, o 15:45

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.
Ostatnio zmieniony 21 gru 2008, o 21:34 przez soku11, łącznie zmieniany 2 razy.

FEMO
Użytkownik
Użytkownik
Posty: 348
Rejestracja: 13 lut 2007, o 17:15
Płeć: Mężczyzna
Lokalizacja: warszawa
Podziękował: 163 razy

[c] lista jednokierunkowa

Post autor: FEMO » 21 gru 2008, o 16:45

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
Użytkownik
Użytkownik
Posty: 450
Rejestracja: 3 kwie 2007, o 18:38
Płeć: Mężczyzna
Lokalizacja: Biała Podlaska
Podziękował: 12 razy
Pomógł: 68 razy

[c] lista jednokierunkowa

Post autor: adek05 » 21 gru 2008, o 17:27

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
Użytkownik
Użytkownik
Posty: 348
Rejestracja: 13 lut 2007, o 17:15
Płeć: Mężczyzna
Lokalizacja: warszawa
Podziękował: 163 razy

[c] lista jednokierunkowa

Post autor: FEMO » 21 gru 2008, o 17:49

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

soku11
Użytkownik
Użytkownik
Posty: 6607
Rejestracja: 16 sty 2007, o 19:42
Płeć: Mężczyzna
Podziękował: 119 razy
Pomógł: 1822 razy

[c] lista jednokierunkowa

Post autor: soku11 » 21 gru 2008, o 17:57

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
Użytkownik
Użytkownik
Posty: 348
Rejestracja: 13 lut 2007, o 17:15
Płeć: Mężczyzna
Lokalizacja: warszawa
Podziękował: 163 razy

[c] lista jednokierunkowa

Post autor: FEMO » 21 gru 2008, o 21:25

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
Użytkownik
Użytkownik
Posty: 6607
Rejestracja: 16 sty 2007, o 19:42
Płeć: Mężczyzna
Podziękował: 119 razy
Pomógł: 1822 razy

[c] lista jednokierunkowa

Post autor: soku11 » 21 gru 2008, o 21:37

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.
Ostatnio zmieniony 21 gru 2008, o 23:46 przez soku11, łącznie zmieniany 1 raz.

FEMO
Użytkownik
Użytkownik
Posty: 348
Rejestracja: 13 lut 2007, o 17:15
Płeć: Mężczyzna
Lokalizacja: warszawa
Podziękował: 163 razy

[c] lista jednokierunkowa

Post autor: FEMO » 21 gru 2008, o 23:39

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

soku11
Użytkownik
Użytkownik
Posty: 6607
Rejestracja: 16 sty 2007, o 19:42
Płeć: Mężczyzna
Podziękował: 119 razy
Pomógł: 1822 razy

[c] lista jednokierunkowa

Post autor: soku11 » 21 gru 2008, o 23:50

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
Użytkownik
Użytkownik
Posty: 348
Rejestracja: 13 lut 2007, o 17:15
Płeć: Mężczyzna
Lokalizacja: warszawa
Podziękował: 163 razy

[c] lista jednokierunkowa

Post autor: FEMO » 22 gru 2008, o 13:56

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

adek05
Użytkownik
Użytkownik
Posty: 450
Rejestracja: 3 kwie 2007, o 18:38
Płeć: Mężczyzna
Lokalizacja: Biała Podlaska
Podziękował: 12 razy
Pomógł: 68 razy

[c] lista jednokierunkowa

Post autor: adek05 » 22 gru 2008, o 15:53

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
Użytkownik
Użytkownik
Posty: 348
Rejestracja: 13 lut 2007, o 17:15
Płeć: Mężczyzna
Lokalizacja: warszawa
Podziękował: 163 razy

[c] lista jednokierunkowa

Post autor: FEMO » 22 gru 2008, o 17:14

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

soku11
Użytkownik
Użytkownik
Posty: 6607
Rejestracja: 16 sty 2007, o 19:42
Płeć: Mężczyzna
Podziękował: 119 razy
Pomógł: 1822 razy

[c] lista jednokierunkowa

Post autor: soku11 » 23 gru 2008, o 13:26

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
Użytkownik
Użytkownik
Posty: 348
Rejestracja: 13 lut 2007, o 17:15
Płeć: Mężczyzna
Lokalizacja: warszawa
Podziękował: 163 razy

[c] lista jednokierunkowa

Post autor: FEMO » 23 gru 2008, o 17:21

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

ODPOWIEDZ