[WikiDyd] [TitleIndex] [WordIndex

Języki i metodologia programowania I, laboratorium

Temat 4: Wskaźniki

Wymagania wstępne: Kernighan i Ritchie: rozdziały: 5.1, 6.5, 6.7

Program szczegółowy: testowanie i modyfikacje programu wykorzystującego listę liniową jednokierunkową do odwracania kolejnosci wprowadzanych liczb.

Program pobieramy przy pomocy instrukcji

która utworzy między innymi katalog jimp1/temat4 i pobierze do niego pliki źródłowe. W miejscu [LOGIN] wprowadzamy własną nazwę użytkownika oraz podajemy własne hasło.

Przechodzimy do tego katalogu (cd jimp1/temat4) zawierający przykładową implementację. Następnie tworzymy program wykonywalny przy pomocy polecenia

i uruchamiamy test za pomoca polecania

   1    /** Program tworzacy liste liniowa jednokierunkowa
   2        zawierajaca liczby calkowite
   3        jstar@iem.pw.edu.pl 14.02.2002
   4    */
   5    #include <stdio.h>
   6    #include <stdlib.h>
   7 
   8    typedef struct elem {     /* element listy: */
   9       int liczba;            /* przechowywana liczba */
  10       struct elem *nastepny;  /* wskaznik na nastepna strukture */
  11    } elem_t;
  12 
  13    typedef elem_t *list_t;     /* lista jest wskaznikiem na pierwszy element */
  14 
  15    list_t sll_wstaw( list_t l, elem_t* e ) { /* wstawia e na poczatek listy l */
  16       e->nastepny= l;
  17       return e;
  18    }
  19 
  20    list_t sll_dodaj( list_t l, elem_t* e ) { /* wstawia e na koniec listy l */
  21       e->nastepny= NULL; /* na wszelki wypadek */
  22       if( l == NULL ) /* lista jest pusta, wiec e bedzie lista */
  23          return e;
  24       else {
  25          list_t iterator= l;  /* przegladamy liste, az dojdziemy do konca */
  26          while( iterator->nastepny != NULL ) /* ostatni element to taki, za ktorym nic nie ma */
  27             iterator= iterator->nastepny;
  28          iterator->nastepny= e;
  29          return l;
  30       }
  31    }
  32 
  33    /* dla porownania rekurencyjna wersja wstawiajaca element na koniec listy */
  34    list_t sll_dodaj_rekurencyjnie( list_t l, elem_t* e ) { /* wstawia e na koniec listy l */
  35       if( l == NULL ) { /* lista jest pusta, wiec e bedzie lista */
  36          e->nastepny= NULL; /* na wszelki wypadek */
  37          return e;
  38       } else {
  39          l->nastepny= sll_dodaj_rekurencyjnie( l->nastepny, e );
  40          return l;
  41       }
  42    }
  43 
  44    main( int argc, char *argv ) {
  45       int x;               /* do przechowywania kolejnej liczby */
  46       list_t tmp;          /* zmienna robocza */
  47       list_t lista= NULL;  /* to jest lista - poczatkowo pusta */
  48 
  49       while( scanf( "%i", &x ) == 1 ) /* dopoki sa liczby */
  50          if( (tmp= malloc( sizeof( elem_t ) )) == NULL ) { /* sprobuj utworzyc kolejna strukture */
  51             /*  tmp == NULL oznacza brak pamieci */
  52             fprintf( stderr, "Brak pamieci na przechowanie %i!\n", x );
  53             exit( 1 );
  54          } else {
  55             /* mamy kolejna strukture, wypelniamy ja: */
  56             (*tmp).liczba= x;
  57             tmp->nastepny= NULL;
  58             /* wstawiamy na poczatek listy */
  59             lista= sll_wstaw( lista, tmp );
  60          }
  61 
  62       /* elementy sie skonczyly, wypisujemy liste */
  63       printf( "Oto nasza lista:\n" );
  64       tmp= lista;
  65       while( tmp != NULL ) {
  66          printf( "%i\n", tmp->liczba );
  67          tmp= tmp->nastepny;
  68       }
  69       printf( "Koniec naszej listy.\n" );
  70 
  71       /* teraz sprzatamy, tj. zwalniamy pamiec */
  72       while( lista != NULL ) {
  73          tmp= lista;
  74          lista= lista->nastepny;
  75          free( tmp );
  76       }
  77 
  78       return 0;
  79    }

A. sprawdzić, jak działa program:

a) w wersji podstawowej,

b) po zastąpieniu wywołania sll_wstaw przez sll_dodaj

c) po zastąpieniu wywołania sll_wstaw przez sll_dodaj_rekurencyjnie

B. napisać rekurencyjną i iteracyjną funkcję do wypisywania listy:

a) od początku

b) od końca

C. napisać rekurencyjną funkcję wstawiającą elementy w określonym porządku (np. sortując elementy rosnąco)

D. napisać funkcję sprzątającą, tj. taką która otrzymuje jako argument pierwszy element listy i która zwalnia pamięć po wszystkich jej elementach włącznie z pierwszym

E. napisać funkcję sortującą gotową listę, funkcja otrzymuje jako argument pierwszy element listy, (można wykorzystać funkcję napisaną w punkcie C)

F. zmodyfikować listę jednokierunkową na listę dwukierunkową oraz dostosować do nowej wersji wszystkie dotychczasowe funkcje,


2015-09-23 06:43