Wikibooks

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

Artykuł Dyskusja

C/Typy złożone (edytuj)

Wersja z 14:49, 15 lis 2011

Dodane 2205 bajtów ,  11 lat temu
Anulowanie wersji nr 174256 utworzonej przez Lethern (dyskusja) nie o to mi chodziło
WizualnieWikikod
m (Wycofano edycje użytkownika 46.182.96.99 (dyskusja). Autor przywróconej wersji to Trichlorometanopawlakov.)
(Anulowanie wersji nr 174256 utworzonej przez Lethern (dyskusja) nie o to mi chodziło)
 
=== Implementacja listy ===
W języku C aby stworzyć listę musimy użyć struktur. Dlaczego? Ponieważ musimy przechować co najmniej dwietrzy 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 elementLista {
struct element *next; /* wskaźnik na kolejny element listy */
unsigned longvoid *val; /* przechowywana wartość */
int size; /* ilość elementów */
} el_listy;
} 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 elementlista {
struct elementlista *next;
unsigned longvoid* val;
} el_listyList;
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;
int val = 2;
first = malloc (sizeof(el_listy));
first->lista.val = 2&val;
first->lista.next = NULL;
for (;i<=END;++i) {
/* tutaj powinien znajdować się kod, który sprawdza podzielność sprawdzanej liczby przez
że jest ona liczbą pierwszą. */
}
wypisz_listelista.wypisz(firststdout);
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">
voidtypedef wypisz_liste(el_listystruct *lista)
{
el_listy *wsk=lista; /* 1... */
void (*wypisz)(struct lista*, FILE*); /* deklaracja metody o nazwie 'wypisz' */
while( wsk != NULL ) /* 2 */
void (*wypisz_odwrotnie)(struct lista*, FILE*);
} List;
void wypisz_liste(List *lista, FILE* strumien)
{
while( lista ) /* 1 */
{
printf fprintf(strumien, "%lu\np", wsk*lista->val); /* 32 */
wsklista = wsklista->next; /* 43 */
} /* 54 */
}
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">
typedef struct lista
void dodaj_do_listy (el_listy *lista, unsigned long liczba)
{
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 = malloc (sizeof(el_listy))liczba; /* 2adres naszej zmiennej */
nowy->valnext = liczbaNULL; /* 3adres następnego elementu */
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">
typedef struct lista
int jest_pierwsza(el_listy *lista, int liczba)
{
/* ... */
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;
}
}
...
for (;i<=END;++i) {
if (lista.jest_pierwsza(first, i))
dodaj_do_listy lista.dodaj(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 elementlista {
struct elementlista *next;
unsigned longvoid* val;
void (*dodaj)(struct lista*, void*);
} el_listy;
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;
el_listyList *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 (el_listyList *lista, unsigned longvoid *liczba)
{
el_listy *wsk, *nowy;
wsk = wsk->next; /* przesuwamy wsk aż znajdziemy ostatni element */
}
nowy = malloc (sizeof(el_listy) *nowy);
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*wsk first = 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 )
{
printffprintf (strum, "%lup\n", *wsk->val);
wsk = wsk->next;
}
}
intvoid jest_pierwszawypisz_liste_odwrotnie(el_listyList *lista, intFILE* liczbastrum)
{
if(lista == NULL) return;
el_listy *wsk;
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;
}
{
unsigned long i = 3; /* szukamy liczb pierwszych w zakresie od 3 do 1000 */
short i = 2;
const unsigned long END = 1000;
first = malloc create_list(sizeof(el_listy)&i);
first->val = 2;
first->next = NULL;
for (;i!=END;++i) {
if (first.jest_pierwsza(first, i))
dodaj_do_listy (first, .dodaj(&i);
}
wypisz_liste(first.wypisz(stdout);
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">
typedef struct lista
void usun_z_listy(el_listy *lista, int element)
{
el_listy /*wsk=lista; ... */
void (*usun)(struct lista*, void*);
while (wsk->next != NULL)
} 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 */
if(lista == NULL) return;
wsk->next = usuwany->next; /* przestawiamy wskaźnik next by omijał usuwany element */
if(lista->next) usun_z_listy(lista->next, element);
free(usuwany); /* usuwamy z pamięci */
if(lista->val == element) {
} else
lista->next = {lista->next->next;
free(lista);
wsk = wsk->next; /* idziemy dalej tylko wtedy kiedy nie usuwaliśmy */
}
} /* 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|
Anonimowy użytkownik
Źródło: „https://pl.wikibooks.org/wiki/Specjalna:Różnica_mobilna/174294”