39023

116

ROZDZIAŁ 19. TYPY ZŁOŻONE

Implementacja listy

W języku C aby stworzyć listę musimy użyć struktur. Dlaczego? Ponieważ musimy przechować co naj mniej dwie wartości:

1.    pewną zmienną (np. liczbę pierwszą z przykładu)

2.    wskaźnik na kolejny element listy

Przyjmijmy, że szukając liczb pierwszych nie przekroczymy możliwości typu unsigned long:

typedof struct element {

struct element *next; /• wskaźnik na kolejny element listy »/ unsigned long val; /* przechowywana wartość */

} el.listy;

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 pnigramu 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.

sinclude <stdio.h>

Sinclude <stdlib.h> typedef struct element { struct olomont *next; unsigned long val;

} el.listy;

el.listy *first; /* pierwszy element listy »/

int main O

{

unsigned long i - 3; /• szukamy liczb pierwszych u zakresie od 3 do 1000 •/

const unsigned long END - 1000;

first ■ malloc (sizeof(el.listy));

first->val - 2;

first->next ■ NULL;

for (;i<-END;~i) {

/• tutaj powinien znajdować się kod, który sprawdza podzielność sprawdzanej liczby przez

poprzednio znalezione liczby pierwsze oraz dodaje liczbę do listy u przypadku stwierdzenia że jest ona liczbą pierwszą. */

>

wypisz_liste(first); return 0;

Na początek zajmiemy się wypisywaniem listy. W tym celu będziemy musieli "odwiedzić" każdy element listy. Elementy listy są połączone polem next, aby przeglądnąć listę użyjemy następującego algorytmu:

1.    Ustaw wskaźnik roboczy na pierwszym elemencie listy

2.    Jeśli wskaźnik ma wartość NULL. przerwij

3.    Wypisz element wskazywany przez wskaźnik

4.    Przesuń wskaźnik na element, który jest wskazywany przez pole next