Wikibooks

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

Artykuł Dyskusja

C/Typy złożone (edytuj)

Wersja z 03:34, 16 lis 2011

Usunięte 2125 bajtów ,  11 lat temu
revert, wytłumaczenie jest w dyskusji, odnieś się do niej najpierw. przed dalszą edycją prosze napisać na stronie dyskusji modułu odpowiedź na moje wątpliwości
WizualnieWikikod
(poprawienie błędów)
(revert, wytłumaczenie jest w dyskusji, odnieś się do niej najpierw. przed dalszą edycją prosze napisać na stronie dyskusji modułu odpowiedź na moje wątpliwości)
=== Implementacja listy ===
W języku C aby stworzyć listę musimy użyć struktur. Dlaczego? Ponieważ musimy przechować co najmniej dwie wartości:
# wskaźnik na pewną zmienną (np. liczbę pierwszą z przykładu)
# wskaźnik na kolejny element listy
Przyjmijmy, że szukając liczb pierwszych nie przekroczymy możliwości typu unsigned long:
 
Przyjmijmy, że szukając liczb pierwszych użyjemy nieznanego typu danych:
<source lang="c">
typedef struct Listaelement {
struct Listaelement *next; /* wskaźnik na kolejny element listy */
voidunsigned long *val; /* przechowywana wartość */
} Listel_listy;
</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 ()
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
że jest ona liczbą pierwszą. */
}
lista.wypiszwypisz_liste(stdoutfirst);
return 0;
}
# 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>
# 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); /* 2 */
nowy->val = liczbamalloc (sizeof(el_listy)); /* adres naszej zmiennej2 */
nowy->nextval = NULLliczba; /* adres następnego elementu3 */
nowy->next = NULL; /* 4 */
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)
{
Listel_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;
}
}
...
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>
 
#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)
{
Listel_listy *wsk, *nowy;
wsk = lista;
while (wsk->next != NULL)
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)
{
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)
{
Listel_listy *wsk;
wsk = lista;
while (wsk != NULL) {
if ((liczba%*((int*)wsk->val))==0) return 0;
wsk = wsk->next;
}
{
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;
}
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>
 
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|
Lethern
8268

edycji

Źródło: „https://pl.wikibooks.org/wiki/Specjalna:Różnica_mobilna/174341”