Wikibooks

C/Typy złożone: Różnice pomiędzy wersjami

Przeglądaj historię interaktywnie
← poprzednia edycjanastępna edycja →
Usunięta treść Dodana treść
WizualnieWikikod
Lethern (dyskusja | edycje)
8268 edycji
m Wycofano edycje użytkownika 46.182.96.99 (dyskusja). Autor przywróconej wersji to Trichlorometanopawlakov.
Linia 265:
 
=== Implementacja listy ===
W języku C aby stworzyć listę musimy użyć struktur. Dlaczego? Ponieważ musimy przechować co najmniej trzydwie wartości:
# wskaźnik na pewną zmienną (np. liczbę pierwszą z przykładu)
# wskaźnik na kolejny element listy
# rozmiar listy
Przyjmijmy, że szukając liczb pierwszych nie przekroczymy możliwości typu unsigned long:
<source lang="c">
typedef struct Listaelement {
struct element *next; /* wskaźnik na kolejny element listy */
voidunsigned long *val; /* przechowywana wartość */
} el_listy;
int size; /* ilość elementów */
} List;
</source>
 
Zacznijmy zatem pisać nasz eksperymentalny program, do wyszukiwania liczb pierwszych. Pierwszą liczbą pierwszą jest liczba 2 Pierwszym elementem naszej listy będzie zatem struktura, która będzie przechowywała liczbę 2. Na co będzie wskazywało pole next? Ponieważ na początku działania programu będziemy mieć tylko jeden element listy, pole next powinno wskazywać na NULL. Umówmy się zatem, że pole next ostatniego elementu listy będzie wskazywało NULL - po tym poznamy, że lista się skończyła.
<source lang="c">
#include <stdio.h>
#include <stdlib.h>
typedef struct listaelement {
struct listaelement *next;
void*unsigned long val;
} Listel_listy;
List lista;
el_listy *first; /* pierwszy element listy */
int main ()
Linia 292 ⟶ 291:
unsigned long i = 3; /* szukamy liczb pierwszych w zakresie od 3 do 1000 */
const unsigned long END = 1000;
first = malloc (sizeof(el_listy));
int val = 2;
lista.first->val = &val2;
lista.first->next = NULL;
for (;i<=END;++i) {
/* tutaj powinien znajdować się kod, który sprawdza podzielność sprawdzanej liczby przez
Linia 300 ⟶ 299:
że jest ona liczbą pierwszą. */
}
lista.wypiszwypisz_liste(stdoutfirst);
return 0;
}
Linia 311 ⟶ 310:
# Przesuń wskaźnik na element, który jest wskazywany przez pole next
# Wróć do punktu 2
Nasza lista ma być dwukierunkowa, więc użyjemy algorytmu odwrotnego:
# Sprawdź, czy lista nie jest pusta
# Jeśli tak, to wyjdź z funkcji
# W przeciwnym wypadku, sprawdź czy istnieje następny element listy
# Jeśli tak, to jest uruchamiana rekurencja tak, by pierwszy argument wskazywał na następny element listy
# Wypisz element wskazywany przez pierwszy argument
# W funkcji nic już więcej nie umieszczamy, nie pobieramy w niej tak jak poprzednio następnego elementu
Nato
<source lang="c">
typedefvoid structwypisz_liste(el_listy *lista)
{
el_listy *wsk=lista; /* ...1 */
while( wsk != NULL ) /* 2 */
void (*wypisz)(struct lista*, FILE*); /* deklaracja metody o nazwie 'wypisz' */
void (*wypisz_odwrotnie)(struct lista*, FILE*);
} List;
void wypisz_liste(List *lista, FILE* strumien)
{
while( lista ) /* 1 */
{
fprintfprintf (strumien, "%plu\n", *listawsk->val); /* 23 */
listawsk = listawsk->next; /* 34 */
} /* 45 */
}
void wypisz_liste_odwrotnie(List *lista, FILE *strumien)
{
if (lista == NULL) return;
if (lista->next) wypisz_liste_odwrotnie(lista->next, strumien);
fprintf(strumien, "%p", *lista->val);
}
</source>
Linia 348 ⟶ 328:
# nadać polu next ostatniego elementu listy wartość NULL
# w pole next ostatniego elementu listy wpisać adres nowo przydzielonego obszaru
Odwrotnie (na potrzeby listy dwukierunkowej):
# znaleźć pierwszy element i zapamiętać go w zmiennej
# skopiować w pole val w pierwszym elemencie dane
# nadać polu next pierwszego elementu listy stary pierwszy element
 
Napiszmy zatem odpowiednią funkcję:
<source lang="c">
void dodaj_do_listy (el_listy *lista, unsigned long liczba)
typedef struct lista
{
el_listy /* ...wsk, */nowy;
void (*dodaj)(struct lista*, void*);
void (*dodaj_na_poczatku)(struct lista*, void*);
} List;
void dodaj_do_listy (List* lista, void* liczba)
{
List *wsk, *nowy;
wsk = lista;
while (wsk->next != NULL) /* 1 */
{
wsk = wsk->next; /* przesuwamy wsk aż znajdziemy ostatni element */
}
nowy = malloc (sizeof *nowy(el_listy)); /* 2 */
nowy->val = liczba; /* adres naszej zmiennej3 */
nowy->next = NULL; /* adres następnego elementu4 */
wsk->next = nowy; /* 5 */
}
void dodaj_na_poczatek_listy (List *lista, void *liczba)
{
List* first = lista;
lista->val = liczba;
lista->next = first;
}
</source>
I... to już właściwie koniec naszej funkcji (warto zwrócić uwagę, że funkcja w tej wersji zakłada, że na liście jest już przynajmniej jeden element). Wstaw ją do kodu przed funkcją main. Został nam jeszcze jeden problem: w pętli for musimy dodać kod, który odpowiednio będzie "badał" liczby oraz w przypadku stwierdzenia pierwszeństwa liczby, będzie dodawał ją do listy. Ten kod powinien wyglądać mniej więcej tak:
<source lang="c">
int jest_pierwsza(el_listy *lista, int liczba)
typedef struct lista
{
/* ... */
int (*jest_pierwsza)(struct lista*, int);
} List;
int jest_pierwsza(List *lista, int liczba)
{
el_listy *wsk;
wsk = lista;
while (wsk != NULL) {
if ((liczba % *((int*)wsk->val))==0) return 0; /* jeśli reszta z dzielenia liczby
przez którąkolwiek z poprzednio
znalezionych liczb pierwszych
jest równa zero, to znaczy, że liczba
ta nie jest liczbą pierwszą. rzutowanie tego wskaźnika na typ int* jest konieczne */
wsk = wsk->next;
}
Linia 404 ⟶ 364:
}
...
for (;i<=END;++i) {
if (lista.jest_pierwsza(first, i))
lista.dodajdodaj_do_listy (&first,i);
}
</source>
 
Zostały konstruktory i destruktory. Prosta sprawa:
<source lang="c">
List create_list(void *head)
{
List my_list;
my_list.val = head;
my_list.next = NULL;
my_list.wypisz = wypisz_liste;
my_list.dodaj = dodaj_do_listy;
my_list.jest_pierwsza = jest_pierwsza;
my_list.wypisz_odwrotnie = wypisz_liste_odwrotnie;
my_list.dodaj_na_poczatku = dodaj_na_poczatek_listy;
my_list.size = 0;
return my_list;
}
void free_list(List *lista)
{
if(lista == NULL) return;
if(lista->next) free_list(lista->next);
lista->next = lista->next->next;
free(lista);
}
</source>
 
Linia 438 ⟶ 375:
#include <stdlib.h>
typedef struct listaelement {
struct listaelement *next;
void*unsigned long val;
} el_listy;
void (*dodaj)(struct lista*, void*);
void (*wypisz)(struct lista*, FILE*);
void (*dodaj_na_poczatku)(struct lista*, void*);
void (*wypisz_odwrotnie)(struct lista*, FILE*);
int (*jest_pierwsza)(struct lista*, int);
} List;
Listel_listy *first;
List create_list(void *head)
{
List my_list;
my_list.val = head;
my_list.next = NULL;
my_list.wypisz = wypisz_liste;
my_list.dodaj = dodaj_do_listy;
my_list.jest_pierwsza = jest_pierwsza;
my_list.wypisz_odwrotnie = wypisz_liste_odwrotnie;
my_list.dodaj_na_poczatku = dodaj_na_poczatek_listy;
return my_list;
}
void dodaj_do_listy (Listel_listy *lista, voidunsigned long *liczba)
{
el_listy *wsk, *nowy;
Linia 470 ⟶ 390:
wsk = wsk->next; /* przesuwamy wsk aż znajdziemy ostatni element */
}
nowy = malloc (sizeof *nowy(el_listy));
nowy->val = liczba;
nowy->next = NULL;
wsk->next = nowy; /* podczepiamy nowy element do ostatniego z listy */
}
void dodaj_na_poczatek_listy (List *lista, void *liczba)
void wypisz_liste(el_listy *lista)
{
el_listy List* first wsk= lista;
lista->val = liczba;
lista->next = first;
}
void free_list(List *lista)
{
if(lista == NULL) return;
if(lista->next) free_list(lista->next);
lista->next = lista->next->next;
free(lista);
}
void wypisz_liste(List *lista, FILE *strum)
{
List *wsk=lista;
while( wsk != NULL )
{
fprintfprintf (strum, "%plu\n", *wsk->val);
wsk = wsk->next;
}
}
voidint wypisz_liste_odwrotniejest_pierwsza(Listel_listy *lista, FILE*int strumliczba)
{
el_listy *wsk;
if(lista == NULL) return;
if(lista->next) wypisz_liste_odwrotnie(lista->next, strum);
fprintf(strum, "%p\n", *wsk->val);
}
int jest_pierwsza(List *lista, int liczba)
{
List *wsk;
wsk = lista;
while (wsk != NULL) {
if ((liczba%*((int*)wsk->val))==0) return 0;
wsk = wsk->next;
}
Linia 517 ⟶ 420:
{
unsigned long i = 3; /* szukamy liczb pierwszych w zakresie od 3 do 1000 */
short i = 2;
const unsigned long END = 1000;
first = create_listmalloc (&isizeof(el_listy));
first->val = 2;
first->next = NULL;
for (;i!=END;++i) {
if (first.jest_pierwsza(first, i))
first.dodajdodaj_do_listy (&first, i);
}
first.wypiszwypisz_liste(stdoutfirst);
free_list(first);
return 0;
}
Linia 532 ⟶ 435:
Możemy jeszcze pomyśleć, jak można by wykonać usuwanie elementu z listy. Najprościej byłoby zrobić:
wsk->next = wsk->next->next
ale wtedy element, na który wskazywał wcześniej <tt>wsk->next</tt> przestaje być dostępny i zaśmieca pamięć. Trzeba go usunąć. Zauważmy, że aby usunąć element potrzebujemy wskaźnika do '''elementu go poprzedzającego''' (po to, by nie rozerwać listy). Lista jest dwukierunkowa, więc elementy znają swoje poprzedniki. Popatrzmy na poniższą funkcję:
<source lang="c">
void usun_z_listy(el_listy *lista, int element)
typedef struct lista
{
el_listy /* ... */wsk=lista;
while (wsk->next != NULL)
void (*usun)(struct lista*, void*);
{
} List;
if (wsk->next->val == element) /* musimy mieć wskaźnik do elementu poprzedzającego */
{
void usun_z_listy(List *lista, void* element)
el_listy *usuwany=wsk->next; /* zapamiętujemy usuwany element */
{
wsk->next = usuwany->next; /* przestawiamy wskaźnik next by omijał usuwany element */
if(lista == NULL) return;
free(usuwany); /* usuwamy z pamięci */
if(lista->next) usun_z_listy(lista->next, element);
} else
if(lista->val == element) {
lista->next = lista->next->next; {
wsk = wsk->next; /* idziemy dalej tylko wtedy kiedy nie usuwaliśmy */
free(lista);
} /* bo nie chcemy zostawić duplikatów */
}
}
}
</source>
Linia 553 ⟶ 457:
 
Funkcja ta działa poprawnie tylko wtedy, gdy nie chcemy usuwać pierwszego elementu. Można to poprawić - dodając instrukcję warunkową do funkcji lub dodając do listy "głowę" - pierwszy element nie przechowujący niczego, ale upraszczający operacje na liście. Zostawiamy to do samodzielnej pracy.
 
 
Cały powyższy przykład omawiał tylko jeden przypadek listy - listę jednokierunkową. Jednak istnieją jeszcze inne typy list, np. lista jednokierunkowa cykliczna, lista dwukierunkowa oraz dwukierunkowa cykliczna. Różnią się one od siebie tylko tym, że:
* w przypadku list dwukierunkowych - w strukturze el_listy znajduje się jeszcze pole, które wskazuje na element poprzedni
* w przypadku list cyklicznych - ostatni element wskazuje na pierwszy (nie rozróżnia się wtedy elementu pierwszego, ani ostatniego)
 
<noinclude>{{Nawigacja|C|
Źródło: „https://pl.wikibooks.org/wiki/C/Typy_złożone”