[WikiDyd] [TitleIndex] [WordIndex

Języki i metodyka programowania I

Przykłady z wykładów w semestrze jesiennym 2008

Uwaga: wykłady są ułożone według dat: najnowszy na górze, najstarszy na dole.

13 stycznia 2009

Analizowaliśmy wpływ stosowanych algorytmów i struktur danych na szybkość działania programu. Demonstrowaliśmy to na przykładzie dwóch implementacji kontenera do przechowywania prostych struktur danych. Napisaliśmy generator pozwalający automatycznie wygenerować dużą liczbę danych testujących, a następnie porównywaliśmy dwie implementacje kontenera: za pomocą powiększającej się tablicy (posortowanej lub nie) oraz za pomocą hasza.

Kod źródłowy dostępny jest tutaj.

6 stycznia 2009

Rozmawialiśmy o rekurencji: kiedy stosować, kiedy nie, jak ważny jest warunek zakończenia i kontrola głębokości.

Rozważania ilustrowaliśmy tworzeniem kodu obsługującego listę liniową.

Pierwsze podejście to lista przechowująca liczby całkowite:

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <assert.h>
   4 
   5 typedef struct e
   6 {
   7   int data;
   8   struct e *nast;
   9 } elem_t, *list_t;
  10 
  11 list_t
  12 wstaw (list_t lista, int nowy)
  13 {
  14   elem_t *ne = malloc (sizeof *ne);
  15   ne->data = nowy;
  16   ne->nast = lista;
  17   return ne;
  18 }
  19 
  20 list_t
  21 dodaj (list_t lista, int nowy)
  22 {
  23   elem_t *ne = malloc (sizeof *ne);
  24   ne->data = nowy;
  25   ne->nast = NULL;
  26   if (lista == NULL)
  27     return ne;
  28   else {
  29     list_t it = lista;
  30     while (it->nast != NULL)
  31       it = it->nast;
  32     it->nast = ne;
  33     return lista;
  34   }
  35 }
  36 
  37 list_t
  38 dodaj_r (list_t lista, int nowy)
  39 {
  40   if (lista == NULL) {
  41     elem_t *ne = malloc (sizeof *ne);
  42     ne->data = nowy;
  43     ne->nast = NULL;
  44     return ne;
  45   }
  46   else {
  47     lista->nast = dodaj_r (lista->nast, nowy);
  48     return lista;
  49   }
  50 }
  51 
  52 list_t
  53 wstaw_rosn (list_t lista, int nowy)
  54 {
  55   if (lista == NULL || lista->data >= nowy) {
  56     elem_t *ne = malloc (sizeof *ne);
  57     ne->data = nowy;
  58     ne->nast = lista;
  59     return ne;
  60   }
  61   else {
  62     lista->nast = wstaw_rosn (lista->nast, nowy);
  63     return lista;
  64   }
  65 }
  66 
  67 void
  68 plist (FILE * out, char *h, list_t lista)
  69 {
  70   fprintf (out, "%s: ", h);
  71   while (lista != NULL) {
  72     fprintf (out, "%d -> ", lista->data);
  73     lista = lista->nast;
  74   }
  75   assert (lista == NULL);
  76   fprintf (out, "NULL\n");
  77 }
  78 
  79 void
  80 plist_r (FILE * out, list_t lista)
  81 {
  82   if (lista != NULL) {
  83     plist_r (out, lista->nast);
  84     fprintf (out, "%d -> ", lista->data);
  85   }
  86   else {
  87     fprintf (out, "NULL\n");
  88   }
  89 }
  90 
  91 
  92 int
  93 main (int argc, char **argv)
  94 {
  95   list_t lw = NULL;
  96   list_t l = NULL;
  97   list_t ls = NULL;
  98 
  99   while (--argc) {
 100     int x = atoi (*++argv);
 101     l = dodaj_r (l, x);
 102     lw = wstaw (lw, x);
 103     ls = wstaw_rosn (ls, x);
 104   }
 105 
 106   plist (stdout, "l", l);
 107   plist (stdout, "lw", lw);
 108   plist (stdout, "ls", ls);
 109   return 0;
 110 }

Drugi, bardziej ambitny przykład to uogólnienie listy tak, aby mogła przechowywac dowolne obiekty.

Plik nagłówkowy:

   1 #ifndef _OLISTA_H_IS_INCLUDED_
   2 #define _OLISTA_H_IS_INCLUDED_
   3 
   4 typedef struct e
   5 {
   6   void *data;
   7   struct e *nast;
   8 } elem_t, *list_t;
   9 
  10 list_t wstaw (list_t lista, void *nowy);
  11 
  12 list_t dodaj (list_t lista, void *nowy);
  13 
  14 list_t wstaw_rosn (list_t lista, void *nowy,
  15                    int fcmp (const void *, const void *));
  16 
  17 void plist (FILE * out, char *h, list_t lista,
  18             void pdata (FILE *, const void *));
  19 
  20 #endif
  21 

Implementacja:

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <assert.h>
   4 
   5 #include "olista.h"
   6 
   7 list_t
   8 wstaw (list_t lista, void *nowy)
   9 {
  10   elem_t *ne = malloc (sizeof *ne);
  11   ne->data = nowy;
  12   ne->nast = lista;
  13   return ne;
  14 }
  15 
  16 list_t
  17 dodaj (list_t lista, void *nowy)
  18 {
  19   elem_t *ne = malloc (sizeof *ne);
  20   ne->data = nowy;
  21   ne->nast = NULL;
  22   if (lista == NULL)
  23     return ne;
  24   else {
  25     list_t it = lista;
  26     while (it->nast != NULL)
  27       it = it->nast;
  28     it->nast = ne;
  29     return lista;
  30   }
  31 }
  32 
  33 list_t
  34 wstaw_rosn (list_t lista, void *nowy, int fcmp (const void *, const void *))
  35 {
  36   if (lista == NULL || fcmp (lista->data, nowy) >= 0) {
  37     elem_t *ne = malloc (sizeof *ne);
  38     ne->data = nowy;
  39     ne->nast = lista;
  40     return ne;
  41   }
  42   else {
  43     lista->nast = wstaw_rosn (lista->nast, nowy, fcmp);
  44     return lista;
  45   }
  46 }
  47 
  48 void
  49 plist (FILE * out, char *h, list_t lista, void pdata (FILE *, const void *))
  50 {
  51   fprintf (out, "%s: ", h);
  52   while (lista != NULL) {
  53     pdata (out, lista->data);
  54     fprintf (out, " -> ");
  55     lista = lista->nast;
  56   }
  57   assert (lista == NULL);
  58   fprintf (out, "NULL\n");
  59 }

I przykład - listy liniowe: przechowująca liczby całkowite i napisy w jednym programie.

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <assert.h>
   5 
   6 #include "olista.h"
   7 
   8 void
   9 druk (FILE * o, const void *p)
  10 {
  11   int x = *((int *) p);
  12   fprintf (o, "%d", x);
  13 }
  14 
  15 int
  16 por (const void *a, const void *b)
  17 {
  18   int xa = *(int *) a;
  19   int xb = *(int *) b;
  20   return xa - xb;
  21 }
  22 
  23 int
  24 rop (const void *a, const void *b)
  25 {
  26   int xa = *(int *) a;
  27   int xb = *(int *) b;
  28   return xb - xa;
  29 }
  30 
  31 void
  32 druknap (FILE * o, const void *n)
  33 {
  34   fprintf (o, "\"%s\"", n);
  35 }
  36 
  37 int
  38 pornap (const void *a, const void *b)
  39 {
  40   char *na = (char *) a;
  41   char *nb = (char *) b;
  42   return strcmp (na, nb);
  43 }
  44 
  45 int
  46 main (int argc, char **argv)
  47 {
  48   list_t ls = NULL;
  49   list_t sl = NULL;
  50   list_t ln = NULL;
  51   int t[1000];
  52   int i = 0;
  53   int j;
  54 
  55   while (--argc) {
  56     int x = atoi (*++argv);
  57     t[i] = x;
  58     ls = wstaw_rosn (ls, &t[i], por);
  59     sl = wstaw_rosn (sl, &t[i], rop);
  60     ln = wstaw_rosn (ln, *argv, pornap);
  61     i++;
  62   }
  63 
  64   for (j = 0; j < i; j++)
  65     printf ("%d, ", t[j]);
  66   printf ("\n");
  67 
  68   plist (stdout, "ls", ls, druk);
  69   plist (stdout, "sl", sl, druk);
  70   plist (stdout, "ln", ln, druknap);
  71   return 0;
  72 }

23 grudnia 2008

Zabawę rozpoczęliśmy od kartkówki, która pozwoliła Państwu wymiernie powiększyć dorobek punktowy. Zadanie polegało na znalezieniu błędów w podanym poniżej (już poprawionym) kodzie:

double mean( double v[], int n ) /* BYŁO '{' */
/* mean value of a vector */
{
  double m= 0; /* BYŁO 'double m;' */
  int i;
  for( i= 0; i < n; i++ )
    m += v[i];
  return n==0? 0 : m/n; /* BYŁO 'return m;' */
}

Następnie zajęliśmy się analizą zadania, polegającego na napisaniu parsera programów w C tworzącego drzewo wywołań funkcji. Chcieliśmy na jego przykładzie pokazać, jak istotna jest właściwa dekompozycja problemu na podzadania i jak należy wykorzystywac hierarchiczne podejście do problemu, aby poradzić sobie z jego złożónością.

Wyjaśniliśmy sobie, że taki program należy starannie zaprojektować, zwracając uwagę na wyróżnienie poszczególnych zadań (funkcji) i stworzenie specjalnych modułów odpowiedzialnych za poszczególne fragmenty funkcjonalności. Stwierdziliśmy, że na pewno potrzebne będą moduły:

main

moduł sterujący całością

skład

przechowujący dane (tablicę funkcji zawierającą informacje o miejscu definicje, deklaracjach i użyciach)

analizator składni

wykrywający w kodzie linie zawierające def., dekl. i użycie funkcji

analizator leksykalny

przekształcający plik tekstowy (ciąg znaków) w ciąg symboli leksykalnych interesujących z perspektywy rozwiązania postawionego problemu

lista słów kluczowych

stwierdzający, czy dany identyfikator jest, czy nie jest słowem kluczowym

Najtrudniejszym i jednocześnie najciekawszym zadaniem jest stworzenie analizatora składni. Można zaproponować następującą jego postać:

   1 #include <stdio.h>
   2 #include <ctype.h>
   3 
   4 #include "alex.h"
   5 #include "fun_stack.h"
   6 
   7 #define MAXINDENTLENGHT 256
   8 
   9 void analizatorSkladni( char * inpname ) {
  10 
  11   FILE * in = fopen( inpname, "r" );
  12 
  13   int nbra = 0;
  14   int npar = 0;
  15 
  16         alex_init4file( in );
  17 
  18   lexem_t lex;
  19 
  20         lex = alex_nextLexem();
  21         while( lex != EOFILE ) {
  22      switch( lex ) {
  23                                 case INDENT: {
  24                   char * fname= alex_indent();
  25                   lexem_t nlex = alex_nextLexem();
  26                   if( nlex == OPEPAR ) {
  27                      npar++;
  28                      put_on_fun_stack( npar, fname );
  29                   } else {
  30                      lex= nlex;
  31                      continue;
  32                   }
  33                 }
  34                 break;
  35         case CLOPAR: {
  36                   if( top_of_funstack() == npar ) {
  37                     lexem_t nlex = alex_nextLexem();
  38                     if( nlex == OPEBRA )
  39                       store_add_def( get_from_fun_stack(), alex_getNL(), inpname );
  40                     else if( nbra == 0 ) 
  41                       store_add_proto( get_from_fun_stack(), alex_getNL(), inpname );
  42                     else
  43                       store_add_call( get_from_fun_stack(), alex_getNL(), inpname );
  44                   } 
  45                   npar--;
  46                 }
  47                 break;
  48         case OPEPAR: npar++;
  49                                                                 break;
  50                                 case OPEBRA: nbra++;
  51                 break;
  52         case CLOBRA: nbra--;
  53                 break;
  54         case ERROR : {
  55                 fprintf( stderr, "\nBUUUUUUUUUUUUUUUUUUUUUU!\nW pliku %s (linia %d) są błędy składni. Zabieram zabafki i idę do sfojej piaskownicy!\n\n", inpname, alex_getNL() );
  56                                                                 exit( 1 );
  57                                                                 }
  58                 break:
  59         default:
  60                 break;
  61                 }
  62     lex = alex_nextLexem();
  63   }
  64 }

Wykład zakończyliśmy szkicem analizatora leksykalnego:

   1 #ifndef _ALEX_H_IS_INCLUDED_
   2 #define _ALEX_H_IS_INCLUDED_
   3 
   4 #include <stdio.h>
   5 
   6 typedef enum { ERROR, OTHER, EOFILE, OPEBRA, CLOBRA, INDENT, OPEPAR, CLOPAR } lexem_t;
   7 
   8 void    alex_init4file( FILE * );
   9 lexem_t alex_nextLexem( void );
  10 char *  alex_indent( void );
  11 int     alex_getNL();
  12 
  13 #endif
  14 

   1 #include "alex.h"
   2 
   3 #include <ctype.h>
   4 
   5 static int  nl= 0;
   6 static char indent[256];
   7 static FILE *ci= NULL;
   8 
   9 void    alex_init4file( FILE *in ) {
  10    nl= 0;
  11    ci= in;
  12 }
  13 
  14 lexem_t alex_nextLexem( void ) {
  15   int c;
  16   while( (c= fgetc(ci)) != EOF ) {
  17     if( isspace( c ) )
  18                         continue;
  19                 else if( c == '\n' )
  20                         nl++;
  21     else if( c == '(' )
  22                         return OPEPAR;
  23     else if( c == ')' )
  24       return CLOPAR;
  25     else if( c == '{' )
  26                         return OPEBRA;
  27     else if( c == '}' )
  28                         return CLOBRA;
  29     else if( isalpha( c ) ) {
  30       int i= 1;
  31       indent[0] = c;
  32       while( isalnum( c= fgetc(ci) ) )
  33                                 indent[i++] = c;
  34                         indent[i] = '\0';
  35       return isKeyword(indent) ? OTHER : INDENT;
  36                 } else if( c == '"' ) {
  37       /* Uwaga: tu trzeba jeszcze poprawic obsluge nowej linii w trakcie napisu
  38          i \\ w napisie 
  39       */
  40       int cp = c;
  41                         while( (c= fgetc(ci)) != EOF && c != '"' && cp == '\\' ) {
  42                                 cp = c;
  43       }
  44       return c==EOF ? EOFILE : OTHER; 
  45     } else if( c == '/' ) {
  46       /* moze byc komentarz */
  47                 } if( isdigit( c ) || c == '.' ) {
  48       /* liczba */
  49                 } else {
  50       return OTHER;
  51                 }
  52         }       
  53   return EOFILE;
  54 }
  55 
  56 char *  alex_indent( void ) {
  57    return indent;
  58 }
  59 
  60 int     alex_getNL() {
  61         return nl;
  62 }

16 grudnia 2008

Kończyliśmy projekt mailspy. Kodu nazbierało się sporo, więc zamieszczam go w postaci załącznika. Zawiera zzipowane wszystkie źródła, makefile i przykładowe dane. Jest tutaj

Ważnym tematem, o który tylko zahaczyliśmy, były wyrażenia regularne: teoria, praktyka.

Omawialiśmy prototyp programu, który ,,rozbiera" log pocztowy przy pomocy wyrażeń regularnych:

   1 #include <stdio.h>
   2 #include <string.h>
   3 #include <regex.h>
   4 
   5 void
   6 pchars (char *s, int from, int to)
   7 {
   8   int i;
   9   printf ("\"");
  10   for (i = from; i < to; i++)
  11     printf ("%c", *(s + i));
  12   printf ("\"");
  13 }
  14 
  15 
  16 int
  17 main (int argc, char **argv)
  18 {
  19   FILE *in = argc > 1 ? fopen (argv[1], "r") : stdin;
  20   char buf[1024];
  21   regex_t preg;
  22   regmatch_t pmatch[9];
  23 
  24   int comp = regcomp (&preg,
  25                       "^([A-Z][a-z]+)[  ]*([0-9]+)[      ]*([0-9]+):([0-9]+):([0-9]+).*Passed CLEAN.*<([^>]*)>....<([^>]*)>",
  26                       REG_EXTENDED);
  27   /*
  28      int comp= regcomp( &preg, "^([A-Z][a-z]+[  ]*[0-9]+[        ]*[0-9]+:[0-9]+:[0-9]+).*Passed CLEAN.*<([^>]*)>....<([^>]*)>", REG_EXTENDED );
  29    */
  30 
  31   if (comp != 0) {
  32     printf ("regcomp returned %d\n", comp);
  33   }
  34 
  35   while (fgets (buf, 1024, in) != NULL) {
  36     if (regexec (&preg, buf, 9, pmatch, 0) == 0) {
  37       int i;
  38       for (i = 0; pmatch[i].rm_so != -1; i++) {
  39 #ifdef DEBUG
  40         printf ("%d(%d-%d):", i, pmatch[i].rm_so, pmatch[i].rm_eo);
  41 #endif
  42         pchars (buf, pmatch[i].rm_so, pmatch[i].rm_eo);
  43         printf ("\t");
  44       }
  45       printf ("\n");
  46     }
  47   }
  48   return 0;
  49 }

Na jego podstawie napisaliśmy funkcję przetwarzającą log, co faktycznie było ostatnim ważnym etapem projektu mailspy.

Podsumowując zasady, o których pamietamy tworząc program:

Na koniec kartkówka: proszę napisać funkcję, która dostaje napis o postaci <klucz>=<wartosc> a zwraca samą wartość (napis).

   1 #include <stdio.h>
   2 
   3 char *
   4 value (char *keqv)
   5 {
   6   while (*keqv != '\0')
   7     if (*(keqv++) == '=')
   8       return keqv;
   9   return keqv;
  10 }
  11 
  12 int
  13 main (int argc, char **argv)
  14 {
  15   while (--argc) {
  16     printf ("%s\n", value (*++argv));
  17   }
  18   return 0;
  19 }

9 grudnia 2008

Piszemy program przeglądający logi poczty i wybierający z nich maile od/do podanych użytkowników. Program składa się z następujących modułów:

Działamy metodą zstępującą (top-to-down - od ogółu do szczegółu). Zaczynamy od funkcji main, do której stopniowo będziemy dopisywać kawałki.

main.c

   1 #include <stdio.h>
   2 #include "process_opts.h"
   3 #include "string_list.h"
   4 #include "process_log.h"
   5 #include "make_output.h"
   6 #include "store.h"
   7 
   8 void print_help( char *prog, FILE *out ) 
   9 {
  10         fprintf( out, "Shows mail of selected users.\n"
  11                 "Usage: %s -l <log-file> -u <list-of-users-file>\n"
  12                 "Output goes to stdout\n",
  13            prog );
  14 }
  15 
  16 void print_error( char *prog, char *msg ) 
  17 {
  18         fprintf( stderr, "%s: ERROR: %s\n", prog, msg );
  19 }
  20    
  21 
  22 int
  23 main( int argc, char ** argv ) 
  24 {
  25         FILE * maillog = fopen( process_opts( argc-1, argv+1, "-l" ), "r" );
  26   FILE * ulist   = fopen( process_opts( argc-1, argv+1, "-u" ), "r" );
  27 
  28   if( maillog == NULL || ulist == NULL ) {
  29                 print_help( argv[0], stderr );
  30                 return 1;
  31         } else {
  32     string_list_t *users;
  33     users = read_string_list( ulist );
  34     fclose( ulist );
  35     if( users == NULL || users->used == 0 ) {
  36                         print_help( argv[0], stderr );
  37                         return 2;
  38                 }
  39                 if( ! init_store( 8 ) ) {
  40                         print_error( argv[0], "Can not init storage for mail info" );
  41       return 3;
  42                 }
  43     process_log( maillog );
  44     fclose( maillog );
  45     make_output( users );
  46     return 0;
  47   }
  48 }

Teraz kawałki:

email.c

   1 #include "email.h"
   2 #include <stdlib.h>
   3 
   4 void dispose_email( email_t * e )
   5 {
   6   free( e->from );
   7   free( e->to );
   8   free( e );
   9 }

email.h

   1 #ifndef _EMAIL_H_IS_INCLUDED_
   2 #define _EMAIL_H_IS_INCLUDED_
   3 
   4 #include <time.h>
   5 
   6 typedef struct {
   7         char *from;
   8   char *to;
   9   struct tm sent_at;
  10 } email_t;
  11 
  12 void dispose_email( email_t * e );
  13 
  14 #endif
  15 

make_output.c

   1 #include "make_output.h"
   2 #include "store.h"
   3 
   4 void make_output( string_list_t * l )
   5 {
   6         int i;
   7         for( i= 0; i < l->used; i++ ) {
   8     int n;
   9     email_t * list;
  10                 printf( "%s\n", l->s[i] );
  11     n = mail_from( l->s[i], list );
  12     printf( "\tsent %d emails\n", n );
  13     n = mail_to( l->s[i], list );
  14     printf( "\treceived %d emails\n", n );
  15   }
  16 }

make_output.h

   1 #include "string_list.h"
   2 
   3 void make_output( string_list_t * l );

process_log.c

   1 #include "process_log.h"
   2 
   3 void process_log( FILE * log )
   4 {
   5 }

process_log.h

   1 #include <stdio.h>
   2 
   3 void process_log( FILE * log );

process_opts.c

   1 #include "process_opts.h"
   2 #include <string.h>
   3 
   4 char * process_opts( int argc, char **argv, char *opt )
   5 {
   6         int i;
   7   for( i= 0; i < argc; i++ )
   8                 if( strcmp( argv[i], opt ) == 0 ) {
   9                         if( i+1 < argc )
  10                                 return argv[i+1];
  11                         else
  12                                 return "";
  13                 }
  14         return NULL;
  15 }

process_opts.h

   1 #ifndef _PROCESS_OPTS_H_IS_INCLUDED_
   2 #define _PROCESS_OPTS_H_IS_INCLUDED_
   3 
   4 char * process_opts( int argc, char **argv, char *opt );
   5 
   6 #endif
   7 

store.c

   1 #include "store.h"
   2 
   3 #include <stdlib.h>
   4 
   5 static email_t ** store = NULL;
   6 static int allocated = 0;
   7 static int used = 0;
   8 
   9 int init_store( int size )
  10 {
  11   if( size <= 0 )
  12                 size= 1024;
  13 
  14   if( (store= malloc( size * sizeof *store)) == NULL )
  15                 return 0;
  16 
  17   allocated = size;
  18         used = 0;
  19   return 1;
  20 }
  21 
  22 void free_store( void )
  23 {
  24         if( store != NULL ) {
  25                 int i;
  26                 for( i= 0; i < used; i++ )
  27                         dispose_email( store[i] );
  28     free( store );
  29                 allocated = used = 0;
  30   }
  31 }
  32 
  33 static
  34 int realloc_store( void ) 
  35 {
  36         email_t ** new_store = realloc( store, 2*allocated );
  37   if( new_store == NULL )
  38                 return 0;
  39         else {
  40                 store= new_store;
  41                 allocated *= 2;
  42                 return 1;
  43         }
  44 }
  45 
  46 int add_email( email_t * email ) {
  47   if( used == allocated && realloc_store() == 0 )
  48                 return 0;
  49         else {
  50                 store[used++] = email;
  51                 return 1;
  52         }
  53 }
  54 
  55 int mail_from( char *address, email_t * list )
  56 {
  57         return 0;
  58 }
  59 
  60 
  61 int mail_to( char * address, email_t * list )
  62 {
  63   return 0;
  64 }

store.h

   1 #ifndef _STORE_H_IS_INCLUDED_
   2 #define _STORE_H_IS_INCLUDED_
   3 
   4 #include "email.h"
   5 
   6 int init_store( int size );
   7 
   8 void free_store( void );
   9 
  10 int add_email( email_t * email );
  11 
  12 int mail_from( char *address, email_t * list );
  13 
  14 int mail_to( char * address, email_t * list );
  15 
  16 #endif
  17 

string_list.c

   1 #include "string_list.h"
   2 #include <string.h>
   3 #include <stdlib.h>
   4 
   5 #define LIST_BASE_LENGTH 512
   6 #define MAXSTRLEN 512
   7 
   8 static string_list_t *
   9 alloc_string_list (void)
  10 {
  11   string_list_t *tmp = malloc (sizeof *tmp);
  12   if (tmp == NULL)
  13     return NULL;
  14   else {
  15     if ((tmp->s = calloc (LIST_BASE_LENGTH, sizeof *tmp->s)) == NULL) {
  16       free (tmp);
  17       return NULL;
  18     }
  19     tmp->allocated = LIST_BASE_LENGTH;
  20     tmp->used = 0;
  21     return tmp;
  22   }
  23 }
  24 
  25 static string_list_t *
  26 realloc_string_list (string_list_t * l)
  27 {
  28   char **tmp = realloc (l->s, 2 * l->allocated);
  29   if (tmp == NULL)
  30     return NULL;
  31   else {
  32     l->allocated *= 2;
  33     return l;
  34   }
  35 }
  36 
  37 void
  38 free_string_list (string_list_t * l)
  39 {
  40   int i;
  41   for (i = 0; i < l->used; i++)
  42     free (l->s[i]);
  43   free (l->s);
  44   free (l);
  45 }
  46 
  47 string_list_t *
  48 read_string_list (FILE * in)
  49 {
  50   string_list_t *tmp = alloc_string_list ();
  51   char buf[MAXSTRLEN];
  52   int i = 0;
  53 
  54   if (tmp == NULL)
  55     return NULL;
  56 
  57   while (fgets (buf, MAXSTRLEN, in) != NULL) {
  58     int l = strlen (buf) - 1;   /* strip \n */
  59     if (l > 0) {
  60       if( i == tmp->allocated ) {
  61                                 string_list_t *resized = realloc_string_list( tmp );
  62         if( resized == NULL ) {
  63                                         free_string_list( tmp );
  64                                         return NULL;
  65                                 }
  66                         }
  67       buf[l] = '\0';
  68       if ((tmp->s[i] = malloc (l + 1)) == NULL) {
  69         free_string_list (tmp);
  70         return NULL;
  71       }
  72       strcpy (tmp->s[i], buf);
  73       i++;
  74     }
  75   }
  76   tmp->used = i;
  77   return tmp;
  78 }

string_list.h

   1 #ifndef _STRING_LIST_H_IS_INCLUDED_
   2 #define _STRING_LIST_H_IS_INCLUDED_
   3 
   4 #include <stdio.h>
   5 
   6 typedef struct {
   7         char **s;
   8   int allocated;
   9   int used;
  10 } string_list_t;
  11 
  12 string_list_t * read_string_list( FILE * in );
  13 
  14 void free_string_list( string_list_t * );
  15 
  16 #endif
  17 

Powyższy kod, zebrany razem, kompiluje się i ,,działa":

CFLAGS = -Wall --pedantic -ansi -g

main: main.o store.o email.o process_opts.o string_list.o process_log.o make_output.o
  $(CC) $(CFLAGS) -o $@ $^

wrk1: wrk1.o
  $(CC) $(CFLAGS) -o $@ $^

.PHONY: clean
clean:
  -rm *.o *~ main

części - wybierania danych z logu poczty.

log wygląda tak

Dec  9 07:22:04 res amavis[26282]: (26282-09) Blocked SPAM, [117.95.9.204] <tillv@barbarajordan.com> -> <obywatelska@hfhrpol.waw.pl>, quarantine: spam-akBlck87Eucw.gz, Message-ID: <1e6e019dbd9a$3f1adebb$919c7f0b@barbarajordan.com>, mail_id: akBlck87Eucw, Hits: 40.208, 549 ms
Dec  9 07:22:05 res amavis[26294]: (26294-08) Passed CLEAN, [206.104.153.178] <Starwood@mail3.rap.tns-online.com> -> <BARBARAGRABOWSKA@HFHRPOL.WAW.PL>, Message-ID: <66cdf801c959c6$70aca890$b2daa8c0@toldmz.nfor.com>, mail_id: lAjQKT5hrlhU, Hits: 4.501, queued_as: 250 OK id=1L9vyv-0006tJ-NI, 907 ms
Dec  9 07:22:08 res imapd[26496]: Authenticated user=jstar host=oer.iem.pw.edu.pl [194.29.146.107]
Dec  9 07:22:08 res imapd[26497]: Authenticated user=veater host=oer.iem.pw.edu.pl [194.29.146.107]
Dec  9 07:22:08 res imapd[26435]: Killed (lost mailbox lock) user=jstar host=static-62-233-197-6.devs.futuro.pl [62.233.197.6]

Rozpoczniemy od programu-prototypu, który w wyizolowanym, prostym otoczeniu pozwoli nam się nauczyć, jak wyciągnąć z logu najpierw odpowiednie linie, a potem wyciąć z nich kawałki.

wrk1.c

   1 #include <stdio.h>
   2 #include <string.h>
   3 
   4 int
   5 main( int argc, char **argv )
   6 {
   7   FILE * in = argc > 1 ? fopen( argv[1], "r" ) : stdin;
   8   char buf[1024];
   9 
  10   while( fgets( buf, 1024, in) != NULL ) {
  11      if( strstr( buf, "Passed CLEAN" ) != NULL ) {
  12        char m[4];
  13        int d;
  14        int ho,mi,se;
  15        char mail[256];
  16        char *tmp;
  17        if( sscanf( buf, "%s %d %d:%d:%d", m, &d, &ho, &mi, &se ) == 5 ) {
  18                                  printf( "godz: %d:%d:%d dzien %d %s ", ho, mi, se, d, m );
  19          if( (tmp= strchr( buf, '<' )) != NULL ) {
  20            if( sscanf( tmp+1, "%s", mail ) == 1 ) {
  21              mail[strlen(mail)-1]= '\0';
  22              printf( "from %s", mail );
  23            }
  24          }
  25          printf( "\n" );
  26                          }
  27        
  28        
  29      }
  30         }
  31 
  32         return 0;
  33 }

2 grudnia 2008

Robimy solver. Zdefiniujemy typ danych - układ równań liniowych (Linear Equations System), dodamy funkcję czytającą i f. rozwiązującą.

   1 #ifndef _LIN_EQ_SYS_IS_INCLUDED_
   2 #define _LIN_EQ_SYS_IS_INCLUDED_
   3 
   4 #include "mat.h"
   5 
   6 typedef struct {
   7   nxn_mat_t * A;
   8   n_vec_t *b;
   9 } linEqSys_t;
  10 
  11 linEqSys_t * read_linEqSys( FILE * );
  12 n_vec_t * solve_linEqSys( linEqSys_t * s );
  13 
  14 #endif
  15 

Teraz implementacja:

   1 #include "lineqsys.h"
   2 #include <stdlib.h>
   3 
   4 linEqSys_t * read_linEqSys( FILE * in ) 
   5 {
   6         linEqSys_t * tmp = malloc( sizeof *tmp );
   7         if( tmp == NULL )
   8                 return NULL;
   9 
  10         if( (tmp->A = read_nxn_mat_t( in ) ) == NULL ) {
  11                 free( tmp );
  12                 return NULL;
  13         }
  14 
  15         if( (tmp->b = read_n_vec_t( in ) ) == NULL ) {
  16                 free_nxn_mat_t( tmp->A );
  17                 free( tmp );
  18                 return NULL;
  19         }
  20 
  21         return tmp;
  22 }
  23 
  24 static toUpperTriangle( linEqSys_t * s ) 
  25 {
  26   int i,j,k;
  27         int n = s->b->n;
  28   double *a = s->A->v;
  29   double *b = s->b->v;
  30         if( s->A->n != n )
  31                 return 0;  /* 0 means fail */
  32   /* loop over columns to be eliminated */
  33         for( j= 0; j < n-1; j++ ) {
  34     double d = a[j*n+j];   /* divisor */
  35     /* loop over rows under diagonal */
  36                 for( i= j+1; i < n; i++ ) {
  37        double m = a[i*n+j]; /* multiplier */
  38        /* loop over row elements */
  39        for( k= j; k < n; k++ )
  40                                         a[i*n+k] -= a[j*n+k]*m/d;
  41        b[i] -= b[j]*m/d;
  42                 }
  43         }
  44   test_print_nxn_mat_t( s->A, stdout );  
  45   test_print_n_vec_t( s->b, stdout );  
  46 }
  47 
  48 static n_vec_t * backSubst( linEqSys_t * s ) {
  49   int i,j;
  50   int n = s->b->n;
  51   n_vec_t *r = make_n_vec_t( n );
  52   double *a= s->A->v;
  53   double *b= s->b->v;
  54   double *x;
  55   if( r == NULL )
  56                 return NULL;
  57   r->n = n;
  58   x = r->v;
  59   for( i= n-1; i >= 0; i-- ) {
  60     double p= 0;
  61                 for( j= n-1; j > i; j-- )
  62                         p += a[i*n+j]*x[j];
  63                 x[i] = (b[i]-p) / a[i*n+i];
  64         }
  65   return r;
  66 } 
  67 
  68 n_vec_t * solve_linEqSys( linEqSys_t * s ) 
  69 {
  70         if( s == NULL || s->A == NULL || s->b == NULL || s->A->n != s->b->n )
  71                 return NULL;
  72 
  73         if( toUpperTriangle( s ) )
  74                 return backSubst( s );
  75         else
  76                 return NULL;
  77 }

I testujemy:

   1 #include "lineqsys.h"
   2 
   3 int
   4 main (int argc, char **argv)
   5 {
   6   FILE *in = argc < 2 ? stdin : fopen (argv[1], "r");
   7 
   8   n_vec_t *x;
   9 
  10   linEqSys_t *leqs = read_linEqSys(in);
  11 
  12   test_print_nxn_mat_t (leqs->A, stdout);
  13 
  14   test_print_n_vec_t (leqs->b, stdout);
  15 
  16         x = solve_linEqSys( leqs );
  17 
  18   test_print_n_vec_t( x, stdout );
  19 
  20   return 0;
  21 }

Makefile się przyda:

CFLAGS = -I ../w6/

test: test2
        ./test2 ../w6/m1.dane

test2: test2.o lineqsys.o ../w6/mat.o 
        $(CC) -o test2 $^

I przykładowe dane testowe. Ze dwa zestawy co najmniej.

Pierwszy (daje w wyniku x1=1, x2=1)

2
1 1
1 -1
2
2
0

Drugi (x1=1, x2=2, x3=-3)

3
1 1 1
0 2 1
7 0 1
3
0
1
4

25 listopada 2008

1. Podział programu na moduły: "Po pierwsze funkcjonalność!"

Celem jest napisanie prostego programu rozwiązującego układy równań metodą eliminacji Gaussa. Rozpoczniemy od zdefiniowania podstawowych typów danych: macierzy i wektora. Dla tych typów rozpoczniemy definiowanie podstawowych operacji.

   1 #ifndef _MAT_H_IS_INCLUDED_
   2 #define _MAT_H_IS_INCLUDED_
   3 
   4 #include <stdio.h>
   5 
   6 /* Square matrix: n rows x n columns */
   7 typedef struct {
   8         int n;
   9         double *v;   /* coefficients stored row after row */
  10 } nxn_mat_t;
  11 
  12 /* n-elent vector */
  13 typedef struct {
  14         int n;
  15   double *v;
  16 } n_vec_t;
  17 
  18 /* Basic operations for matrices */
  19 nxn_mat_t * make_nxn_mat_t( int );  /* mem. alloc */
  20 void free_nxn_mat_t( nxn_mat_t * ); /* mem. disposal */
  21 nxn_mat_t * read_nxn_mat_t( FILE * ); /* read mat. from file */
  22 
  23 /* Test print of a matrix */
  24 void test_print_nxn_mat_t( nxn_mat_t *, FILE * );
  25 
  26 /*Basic operations for vectors */
  27 n_vec_t * make_nxn_vec_t( int );
  28 void free_n_vec_t( n_vec_t * );
  29 n_vec_t * read_n_vec_t( FILE * );
  30 
  31 #endif
  32 

Teraz implementacja:

   1 #include "mat.h"
   2 #include <stdlib.h>
   3 
   4 nxn_mat_t * make_nxn_mat_t( int n ) {
   5         if( n > 0 ) {
   6                 nxn_mat_t * tmp;
   7           if( (tmp = malloc( sizeof * tmp ) ) == NULL )
   8                 return NULL;
   9     if( (tmp->v = malloc( n*n * sizeof * (tmp->v) )) == NULL ) {
  10                   free( tmp );
  11                   return NULL;
  12           }
  13     return tmp;
  14         } else
  15                 return NULL;
  16 }
  17 
  18 n_vec_t * make_n_vec_t( int n ) {
  19         if( n > 0 ) {
  20                 n_vec_t * tmp;
  21           if( (tmp = malloc( sizeof * tmp ) ) == NULL )
  22                 return NULL;
  23     if( (tmp->v = malloc( n * sizeof * (tmp->v) )) == NULL ) {
  24                   free( tmp );
  25                   return NULL;
  26           }
  27     return tmp;
  28         } else
  29                 return NULL;
  30 }
  31 
  32 void free_nxn_mat_t( nxn_mat_t * tmp ) {
  33         if( tmp->v != NULL )
  34                 free( tmp->v );
  35         free( tmp );
  36 }
  37 
  38 void free_n_vec_t( n_vec_t * tmp ) {
  39         if( tmp->v != NULL )
  40                 free( tmp->v );
  41         free( tmp );
  42 }
  43 
  44 nxn_mat_t * read_nxn_mat_t( FILE *in )
  45 {
  46         int n;
  47   nxn_mat_t * tmp;
  48   int i,j;
  49 
  50   fscanf( in, "%d", &n );
  51   if( (tmp = make_nxn_mat_t(n)) == NULL )
  52                 return NULL;
  53 
  54   tmp->n = n;
  55         for( i= 0; i < n; i++ )
  56                 for( j= 0; j < n; j++ )
  57                         if( fscanf( in, "%lf", tmp->v+i*n+j) != 1 ) {
  58         free_nxn_mat_t( tmp );
  59                                 return NULL;
  60                         }
  61 
  62         return tmp;
  63 }
  64 
  65 n_vec_t * read_n_vec_t( FILE *in )
  66 {
  67   int n;
  68   n_vec_t * tmp;
  69   int i;
  70 
  71   fscanf( in, "%d", &n );
  72   if( (tmp = make_n_vec_t(n)) == NULL )
  73                 return NULL;
  74 
  75   tmp->n = n;
  76         for( i= 0; i < n; i++ )
  77                 if( fscanf( in, "%lf", tmp->v+i) != 1 ) {
  78       free_n_vec_t( tmp );
  79                         return NULL;
  80                 }
  81 
  82         return tmp;
  83 }
  84 
  85 void test_print_nxn_mat_t( nxn_mat_t *m, FILE * out ) {
  86         int i,j;
  87         fprintf( out, "\n[\n" );
  88         for( i= 0; i < m->n; i++ ) {
  89                 for( j= 0; j < m->n; j++ )
  90                         fprintf( out, "\t%g", m->v[i*m->n+j] );
  91                 fprintf( out, "\n" );
  92         }
  93         fprintf( out, "]\n" );
  94 }

Ponieważ staramy się testować kod jak najszybciej, a więc już teraz przystępujemy do stworzenia pierwszego testu, który przeczyta i wpisze macierz:

   1 #include "mat.h"
   2 
   3 int
   4 main (int argc, char **argv)
   5 {
   6   FILE *in = argc < 2 ? stdin : fopen (argv[1], "r");
   7 
   8   nxn_mat_t *mm = read_nxn_mat_t (in);
   9   n_vec_t *mv = read_n_vec_t (in);
  10 
  11   test_print_nxn_mat_t( mm, stdout );
  12   return 0;
  13 }

Do testowania przydadzą się jakieś dane, bo wielokrotne ich wpisywanie jest nieefektywne. Przykładowa zawartość pliku z danymi:

3
1.1 1.2 1.3
2.1 2.2 2.3
3.1 3.2 3.3
3
10
20
30

18 listopada 2008

1. Powtórka z make, potoki

# makefile
COPT = -Wall -pedantic -ansi

all: domain fun fun2

domain: domain.c
  ${CC} ${COPT} -o $@ -lm $^

fun: fun.c
  ${CC} ${COPT} -o $@ -lm $^

fun2: fun2.c
  ${CC} ${COPT} -o $@ -lm $^

.PHONY: test
test: test_x2 test_sin

test_sin: all
  -rm sin
  ./domain -3.2 3.2 30000 | ./fun sin > sin
  gnuplot sin.gpt
  rm sin
  ./domain -6.4 6.4 10000 | ./fun2 sin > sin
  gnuplot sin.gpt
  rm sin

test_x2: all
  -rm x2
  ./domain -1 4 10 | ./fun > x2
  gnuplot x2.gpt
  rm x2

clean:
  rm -rf sin x2 fun fun2 domain *.o

# x2.gpt
plot 'x2' w linespoints
pause 5

# sin.gpt
plot 'sin' w linespoints
pause 5

2. Napisy

   1 #include <stdio.h>
   2 
   3 int
   4 strlen1( char *s )
   5 {
   6   int l= 0;
   7   while( *s != '\0' ) {
   8     s++;
   9     l++;
  10   }
  11   return l;
  12 }
  13 
  14 int
  15 strlen2( char *s )
  16 {
  17   char *p= s;
  18   while( *p++ )
  19     ;
  20   return p-s;
  21 }
  22 
  23 int
  24 main( int argc, char **argv )
  25 {
  26   while( --argc ) {
  27     ++argv;
  28     printf( "strlen1: Argument \"%s\" ma dlug=%d\n", *argv, strlen1( *argv ) );
  29     printf( "strlen2: Argument \"%s\" ma dlug=%d\n", *argv, strlen2( *argv ) );
  30   }
  31   return 0;
  32 }

   1 #include <stdio.h>
   2 #include <string.h>
   3 
   4 /*
   5  * MAXLINES must be defined during compilation
   6  */
   7 #ifndef MAXLINES
   8 #error MAXLINES must be defined during compilation (use -DMAXLINES=<your value>)
   9 #endif
  10 
  11 #define MAXLINELENGTH 500
  12 
  13 int
  14 main( int argc, char **argv )
  15 {
  16   char buff[MAXLINES][MAXLINELENGTH];
  17   int n= 0;
  18   int i;
  19   int maxl= 0;
  20   char (*maxl_pointer)[MAXLINELENGTH] = NULL;
  21   FILE *in = argc > 1 ? fopen( argv[1], "r" ) : stdin;
  22 
  23   if( in == NULL ) {
  24     printf( "Longest line lenght finder\n\n"
  25             "Usage: %s  [ <filename> ]\n\n"
  26             "\t<filename> - name of an existing text file\n\n"
  27             "\tFile should not have more than %d lines\n"
  28             "\tLine lenght must not exceed %d characters\n",
  29             argv[0], MAXLINES, MAXLINELENGTH-2 );
  30     return 1;
  31   }
  32 
  33   while( fgets( buff[n], MAXLINELENGTH, in ) != NULL )
  34     ++n;
  35 
  36   printf( "%s: got %d lines\n", argv[0], n );
  37 
  38   maxl = 0;
  39   for( i= 0; i < n; i++ ) {
  40     int cl = strlen( buff[i] );
  41     if( cl > maxl ) {
  42       maxl = cl;
  43       maxl_pointer = buff + i;
  44     }
  45   }
  46   if( maxl_pointer != NULL )
  47     printf( "%s: longest line (%d characters): %s", *argv, maxl, *maxl_pointer );
  48   else
  49     printf( "%s: no lines in input stream?!\n", *argv );
  50 
  51   return 0;
  52 }

   1 #include <stdio.h>
   2 #include <string.h>
   3 #include <stdlib.h>
   4 
   5 void
   6 sort_lines( char *tab, size_t size, int n, int (*cmpf)( char *, char * ) )
   7 {
   8   int i;
   9   int j;
  10   char *tmp= malloc( size );
  11   for( i= 1; i < n; i++ ) {
  12     memmove( tmp, tab+i*size, size );
  13     for( j= i; j > 0 && cmpf( tmp, tab+(j-1)*size ) < 0; j-- )
  14       memmove( tab+j*size, tab+(j-1)*size, size );
  15     memmove( tab+j*size, tmp, size );
  16   }
  17   free( tmp );
  18 }
  19 
  20 #define MAXLINES      1000
  21 #define MAXLINELENGTH 500
  22 
  23 int
  24 strlen_cmp( char *a, char *b )
  25 {
  26   int la= strlen( a );
  27   int lb= strlen( b );
  28   return la-lb;
  29 }
  30 
  31 int
  32 fc_cmp( char *a, char *b )
  33 {
  34   return *a - *b;
  35 }
  36 
  37 int
  38 main( int argc, char **argv )
  39 {
  40   char buff[MAXLINES][MAXLINELENGTH];
  41   int n= 0;
  42   int i;
  43   FILE *in = argc > 1 ? fopen( argv[1], "r" ) : stdin;
  44 
  45   if( in == NULL ) {
  46     printf( "Line sorter\n\n"
  47             "Usage: %s  [ <filename> ]\n\n"
  48             "\t<filename> - name of an existing text file\n\n"
  49             "\tFile should not have more than %d lines\n"
  50             "\tLine lenght must not exceed %d characters\n",
  51             argv[0], MAXLINES, MAXLINELENGTH-2 );
  52     return 1;
  53   }
  54 
  55   while( fgets( buff[n], MAXLINELENGTH, in ) != NULL )
  56     ++n;
  57 
  58   sort_lines( buff, MAXLINELENGTH, n, strlen_cmp );
  59 
  60   for( i= 0; i < n; i++ )
  61     printf( "%d: %s", i, buff[i] );
  62 
  63   return 0;
  64 }

4 listopada 2008

1. Struktury, zwracanie złożonych danych przez funkcję, powtórzenie o stosie i stercie:

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <float.h>
   4 #include <math.h>
   5 
   6 struct double_vec {
   7   int n;
   8   double *v;
   9 };
  10 
  11 struct double_vec *
  12 vec_gen( int n, double start, double end )
  13 {
  14   int i;
  15   double dx;
  16 
  17   struct double_vec * v = malloc( sizeof *v );
  18   if( v == NULL )
  19     return NULL;
  20 
  21   (*v).v = malloc( n * sizeof * (*v).v );
  22 
  23   if( v->v == NULL ) {
  24     free( v );
  25     return NULL;
  26   }
  27 
  28   v->n = n;
  29   dx = ( end - start ) / ( n - 1 );
  30 
  31   for( i= 0; i < n; i++ )
  32     v->v[i] = start + i * dx;
  33 
  34   return v;
  35 }
  36 
  37 void
  38 vec_print( FILE *out, struct double_vec *v, char *fmt )
  39 {
  40   int i;
  41   for( i = 0; i < v->n; i++ )
  42     fprintf( out, fmt, v->v[i] );
  43 }
  44 
  45 int
  46 main( int argc, char ** argv )
  47 {
  48     double a = argc < 2 ? 0 : atof( argv[1] );
  49     double b = argc < 3 ? 1 : atof( argv[2] );
  50     int    n = argc < 4 ? 5 : atoi( argv[3] );
  51 
  52     struct double_vec *v = vec_gen( n, a, b );
  53 
  54     if( v != NULL ) {
  55       vec_print( stdout, v, "%g\n" );
  56       return 0;
  57     } else
  58       return 1;
  59 }

2. Wskaźniki do funkcji

   1 #include <stdio.h>
   2 #include <math.h>
   3 #include <string.h>
   4 
   5 double
   6 x2( double x )
   7 {
   8   return x*x;
   9 }
  10 
  11 int
  12 main( int argc, char ** argv )
  13 {
  14   double (*fptr)( double );
  15   double x;
  16 
  17   fptr = x2;
  18 
  19   if( argc > 1 ) {
  20     if( strcmp( argv[1], "sin" ) == 0 )
  21       fptr= sin;
  22     else if( strcmp( argv[1], "cos" ) == 0 )
  23       fptr= cos;
  24     else if( strcmp( argv[1], "log" ) == 0 )
  25       fptr= log;
  26     else {
  27       fprintf( stderr, "Unknown function: \"%s\"\n", argv[1] );
  28       return 1;
  29     }
  30   }
  31   while( scanf( "%lf", &x ) == 1 )
  32     printf( "%g %g\n", x, (*fptr)( x ) );
  33 
  34   return 0;
  35 }

3. Wskaźniki do funkcji jako argumenty funkcji

   1 #include <stdio.h>
   2 #include <math.h>
   3 #include <string.h>
   4 
   5 double
   6 x2( double x )
   7 {
   8   return x*x;
   9 }
  10 
  11 void
  12 process_vector( double *v, int n, double *result, double (*processor)( double ) )
  13 {
  14   int i;
  15   for( i= 0; i < n; i++ )
  16     result[i]= processor( v[i] );
  17     /*
  18      *    result[i]= (*processor)( v[i] );
  19      */
  20 }
  21 
  22 int
  23 main( int argc, char ** argv )
  24 {
  25   double (*fptr)( double );
  26   double x[100000];
  27   double y[100000];
  28   int i;
  29   int n;
  30 
  31   fptr = x2;
  32 
  33   if( argc > 1 ) {
  34     if( strcmp( argv[1], "sin" ) == 0 )
  35       fptr= sin;
  36     else if( strcmp( argv[1], "cos" ) == 0 )
  37       fptr= cos;
  38     else if( strcmp( argv[1], "log" ) == 0 )
  39       fptr= log;
  40     else {
  41       fprintf( stderr, "Unknown function: \"%s\"\n", argv[1] );
  42       return 1;
  43     }
  44   }
  45   n= 0;
  46   while( scanf( "%lf", x+n ) == 1 )
  47     n++;
  48 
  49   process_vector( x, n, y, fptr );
  50 
  51   for( i= 0; i < n; i++ )
  52     printf( "%g\t%g\n", *(x+i), *(y+i) );
  53 
  54   return 0;
  55 }

28 października 2008

Tematyka: Komunikacja pomiędzy funkcjami - c.d., wskaźniki a tablice

Najpierw pisali Państwo kartkówkę. Zadanie brzmiało:

Proszę napisać funkcję, która dostaje wektor liczb całkowitych i zamienia w nim wszystkie liczby dodatnie na liczbę 1, wszystkie ujemne na -1, a zera pozostawia bez zmian.

Wyniki kartkówki można sprawdzić w bazie danych https://oceny.iem.pw.edu.pl

Przykładowe rozwiązania:

   1 void
   2 rozwiazanie1 (int v[], int n)
   3 {
   4   int i;
   5   for (i = 0; i < n; i++)
   6     if (v[i] < 0)
   7       v[i] = -1;
   8     else if (v[i] > 0)
   9       v[i] = 1;
  10 }
  11 
  12 void
  13 rozwiazanie2 (int v[], int n)
  14 {
  15   while (--n >= 0)
  16     if (v[n] < 0)
  17       v[n] = -1;
  18     else if (v[n] > 0)
  19       v[n] = 1;
  20 }

Potem zajęliśmy się funkcją zamieniającą miejscami wartości dwóch zmiennych. Pokazaliśmy, że można jej użyć także do zamiany dwóch elementów wektora (mówiliśmy o związkach wektorów i wskaźników):

   1 #include <stdio.h>
   2 
   3 void
   4 swap (int *px, int *py)
   5 {
   6   int tmp = *px;
   7   *px = *py;
   8   *py = tmp;
   9 }
  10 
  11 void
  12 print_int_vector (FILE * out, int v[], int n, char *name)
  13 {
  14   int i;
  15   fprintf (out, "%s = [ ", name);
  16   for (i = 0; i < n; i++)
  17     fprintf (out, "%2d ", v[i]);
  18   fprintf (out, "]\n");
  19 }
  20 
  21 int
  22 main ()
  23 {
  24   int iv[] = { 0, 10, 20, 30, 40, 50, 60, 70, 80, 90 };
  25 
  26   print_int_vector (stdout, iv, sizeof iv / sizeof iv[0], "iv");
  27 
  28   swap (iv, iv + 5);
  29 
  30   print_int_vector (stdout, iv, sizeof iv / sizeof iv[0], "iv");
  31 
  32   swap( &iv[1], & iv[8] ); /* albo tak: swap( iv+1, iv+8 ); */
  33   
  34   print_int_vector (stdout, iv, sizeof iv / sizeof iv[0], "iv");
  35 
  36   return 0;
  37 
  38 }

Następnie eksperymentowaliśmy, używając tej samej funkcji do zamiany elementów innego typu, niż wynika to z deklaracji argumentów formalnych. Na tej podstawie wyjaśnialiśmy sobie niuanse arytmetyki na wskaźnikach:

   1 #include <stdio.h>
   2 
   3 void
   4 swap (int *px, int *py)
   5 {
   6   int tmp = *px;
   7   *px = *py;
   8   *py = tmp;
   9 }
  10 
  11 void
  12 print_int_vector (FILE * out, int v[], int n, char *name)
  13 {
  14   int i;
  15   fprintf (out, "%s = [ ", name);
  16   for (i = 0; i < n; i++)
  17     fprintf (out, "%d ", v[i]);
  18   fprintf (out, "]\n");
  19 }
  20 
  21 void
  22 print_char_vector( FILE * out, char v[], int n, char * name )
  23 {
  24   int i;
  25   fprintf (out, "%s = [ ", name);
  26   for (i = 0; i < n; i++)
  27     fprintf (out, "%c ", v[i]);
  28   fprintf (out, "]\n");
  29 }
  30 
  31 
  32 int
  33 main ()
  34 {
  35   int iv[] = { 0, 10, 20, 30, 40, 50, 60, 70, 80, 90 };
  36   char cv[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j' };
  37 
  38   print_int_vector (stdout, iv, sizeof iv / sizeof iv[0], "iv");
  39 
  40   swap (iv, iv + 5);
  41 
  42   print_int_vector (stdout, iv, sizeof iv / sizeof iv[0], "iv");
  43 
  44   print_char_vector(stdout, cv, sizeof cv / sizeof cv[0], "cv" );
  45 
  46   swap (cv, cv+2);
  47         
  48   print_char_vector(stdout, cv, sizeof cv / sizeof cv[0], "cv" );
  49 
  50   return 0;
  51 
  52 }

Kolejna wersja programu zawiera uniwersalną funkcję zamieniającą - aswap:

   1 #include <stdio.h>
   2 #include <string.h>
   3 
   4 #define MAXSWAPSIZE 1024
   5 
   6 void
   7 aswap (char *px, char *py, size_t size)
   8 {
   9   char buff[MAXSWAPSIZE];
  10   if( size <= MAXSWAPSIZE ) {
  11     memmove( buff, px, size );
  12     memmove( px, py, size );
  13     memmove( py, buff, size );
  14   }
  15 }
  16 
  17 void
  18 print_int_vector (FILE * out, int v[], int n, char *name)
  19 {
  20   int i;
  21   fprintf (out, "%s = [ ", name);
  22   for (i = 0; i < n; i++)
  23     fprintf (out, "%d ", v[i]);
  24   fprintf (out, "]\n");
  25 }
  26 
  27 void
  28 print_char_vector( FILE * out, char v[], int n, char * name )
  29 {
  30   int i;
  31   fprintf (out, "%s = [ ", name);
  32   for (i = 0; i < n; i++)
  33     fprintf (out, "%c ", v[i]);
  34   fprintf (out, "]\n");
  35 }
  36 
  37 int
  38 main ()
  39 {
  40   int iv[] = { 0, 10, 20, 30, 40, 50, 60, 70, 80, 90 };
  41   char cv[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j' };
  42 
  43   print_int_vector (stdout, iv, sizeof iv / sizeof iv[0], "iv");
  44 
  45   aswap (iv, iv + 5, sizeof iv[0]);
  46 
  47   print_int_vector (stdout, iv, sizeof iv / sizeof iv[0], "iv");
  48 
  49   print_char_vector(stdout, cv, sizeof cv / sizeof cv[0], "cv" );
  50 
  51   aswap (cv, cv+5, sizeof cv[0]);
  52         
  53   print_char_vector(stdout, cv, sizeof cv / sizeof cv[0], "cv" );
  54 
  55   return 0;
  56 
  57 }

W tym momencie odeszliśmy od głównego toru wykładu i porozmawialiśmy o dynamicznej alokacji pamięci, zmiennych automatycznych, stosie i o tym jak napisać funkcję, która utworzy nowy wektor o zadanej wielkości. Napisaliśmy, jako przykład, funkcję kopiującą wektor:

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 
   4 int *
   5 copy (int v[], int n)
   6 {
   7   int *copy;
   8   int i;
   9 
  10   if( (copy = malloc (n * sizeof *copy)) == NULL )
  11     return NULL;
  12 
  13   for (i = 0; i < n; i++)
  14     copy[i] = v[i];
  15   return copy;
  16 }
  17 
  18 int
  19 main (int argc, char **argv)
  20 {
  21   int v1[1000]; /* NIE ROBIMY TAK: = malloc( 1000 * sizeof *v1 ); */
  22   int n = argc > 1 ? atoi (argv[1]) : 10;
  23 
  24   int *v2;
  25 
  26   int i;
  27 
  28   for (i = 0; i < n; i++)
  29     v1[i] = 10 * i;
  30 
  31   v2 = copy (v1, n);
  32 
  33   if (v2 != NULL) {
  34       for (i = 0; i < n; i++)
  35         printf ("%d ", v2[i]);
  36       printf ("\n");
  37 
  38       free (v2);
  39   }
  40 
  41   return 0;
  42 }

Po tej dygresji wróciliśmy do programu testującego funkcję zamieniającą i przerobiliśmy także funkcję drukującą wektor wg pomysłu wykorzystanego w aswap:

   1 #include <stdio.h>
   2 #include <string.h>
   3 
   4 #define MAXSWAPSIZE 1024
   5 
   6 void
   7 aswap (char *px, char *py, size_t size)
   8 {
   9   char buff[MAXSWAPSIZE];
  10   if( size <= MAXSWAPSIZE ) {
  11                 memmove( buff, px, size );
  12     memmove( px, py, size );
  13     memmove( py, buff, size );
  14   }
  15 }
  16 
  17 void
  18 print_any_vector (FILE * out,
  19                   char *v, int n, size_t size,
  20                   char *fmt, char *name)
  21 {
  22   int i;
  23   fprintf (out, "%s = [ ", name);
  24   for (i = 0; i < n; i++)
  25     fprintf (out, fmt, *(v+i*size));
  26   fprintf (out, "]\n");
  27 }
  28 
  29 int
  30 main ( )
  31 {
  32   int iv[] = { 0, 10, 20, 30, 40, 50, 60, 70, 80, 90 };
  33   char cv[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j' };
  34 
  35   print_any_vector (stdout, (char*)iv, sizeof iv / sizeof iv[0], sizeof iv[0], "%d ", "iv");
  36 
  37   aswap ((char*)iv, (char*)(iv + 5), sizeof iv[0]);
  38 
  39   print_any_vector (stdout, (char*)iv, sizeof iv / sizeof iv[0], sizeof iv[0], "%d ", "iv");
  40 
  41   print_any_vector (stdout, cv, sizeof cv / sizeof cv[0], sizeof cv[0], "'%c', ", "cv");
  42 
  43   aswap (cv, cv+5, sizeof cv[0]);
  44         
  45   print_any_vector (stdout, cv, sizeof cv / sizeof cv[0], sizeof cv[0], "%c ", "cv");
  46 
  47   return 0;
  48 
  49 }

na sam koniec obejrzeli jeszcze Państwo makro, które wygląda i robi to samo, co funkcja aswap, ale w inny sposób:

   1 #include <stdio.h>
   2 #include <string.h>
   3 
   4 #define swap( T, A, B ) { T tmp = *(A); *(A) = *(B); *(B) = tmp; }
   5 
   6 void
   7 print_any_vector (FILE * out,
   8                   char *v, int n, size_t size,
   9                   char *fmt, char *name)
  10 {
  11   int i;
  12   fprintf (out, "%s = [ ", name);
  13   for (i = 0; i < n; i++)
  14     fprintf (out, fmt, *(v+i*size));
  15   fprintf (out, "]\n");
  16 }
  17 
  18 int
  19 main ( )
  20 {
  21   int iv[] = { 0, 10, 20, 30, 40, 50, 60, 70, 80, 90 };
  22   char cv[] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j' };
  23 
  24   print_any_vector (stdout, (char*)iv, sizeof iv / sizeof iv[0], sizeof iv[0], "%d ", "iv");
  25 
  26   swap (int, iv, iv + 5);
  27 
  28   print_any_vector (stdout, (char*)iv, sizeof iv / sizeof iv[0], sizeof iv[0], "%d ", "iv");
  29 
  30   print_any_vector (stdout, cv, sizeof cv / sizeof cv[0], sizeof cv[0], "'%c', ", "cv");
  31 
  32   swap (char, cv, cv+5);
  33         
  34   print_any_vector (stdout, cv, sizeof cv / sizeof cv[0], sizeof cv[0], "%c ", "cv");
  35 
  36   return 0;
  37 
  38 }

21 października 2008

Tematyka: Komunikacja pomiędzy funkcjami

Rozpoczęliśmy od skopiowania plików z poprzedniego wykładu i modyfikacji skryptu makefile tak, aby automatycznie porządkować katalog (usuwać niepotrzebne pliki). W tym celu dodaliśmy do makefile nową regułę:

clean:
  rm *.o *~ a.out

Potem przeszliśmy do rozbudowy funkcjonalności programu tak, aby było możliwe podanie jako argumentu nazwy pliku (a program przeczyta zawarte tam liczby i obliczy ich sumę). Poprawiona funkcja main:

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include "sum.h"
   4 #include "sio.h"
   5 
   6 int
   7 main (int argc, char *argv[])
   8 {
   9   double liczby[1000];
  10   int n;
  11 
  12   if( argc == 1 )
  13     n = stdin2double_vec (liczby);
  14   else if( argc == 2 )
  15     n = file2double_vec(argv[1], liczby );
  16   else
  17     n = argv2double_vec (argv, argc, liczby);
  18 
  19   if (n >= 0)
  20     {
  21       printf ("mamy %d liczb\n", n);
  22       double_vec2stdout (liczby, n);
  23       printf ("sum = %f\n", sum (liczby, n));
  24     }
  25   else
  26     {
  27       printf ("Podano złe argumenty - niektóre nie są liczbami!\n");
  28     }
  29 
  30   return 0;
  31 
  32 }

i nowa funkcja:

   1 int
   2 file2double_vec( char * filename, double v[] )
   3 {
   4     int n= 0;
   5     double x;
   6     FILE* input = fopen( filename, "r" );
   7 
   8     if( input == NULL )
   9       return -1;
  10 
  11     while( fscanf( input, "%lf", &x ) == 1 )
  12       v[n++] = x;
  13 
  14     return n;
  15 }

Doszliśmy do wniosku, że ta funkcja jest bardzo podobna do stdin2double_vec. Dodatkowo nie podobała nam się diagnostyka błędów. Poprawiliśmy to wszystko i mamy: program

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include "sum.h"
   4 #include "sio.h"
   5 
   6 #define MAXINPUTDATASIZE 100
   7 
   8 int
   9 main (int argc, char *argv[])
  10 {
  11   double liczby[MAXINPUTDATASIZE+1];  /* +1 bo jesteśmy aż za bardzo ostrożni */
  12   int n;
  13 
  14   if (argc == 1)
  15     n = file2double_vec (stdin, liczby, MAXINPUTDATASIZE);
  16   else if (argc == 2)
  17     {
  18       FILE *inp = fopen (argv[1], "r");
  19       if (inp == NULL)
  20   {
  21     printf ("Uwaga: nie mogę otworzyć pliku %s do czytania.\n",
  22       argv[1]);
  23     return -1;
  24   }
  25       n = file2double_vec (inp, liczby, MAXINPUTDATASIZE);
  26       fclose (inp);
  27     }
  28   else
  29     n = argv2double_vec (argv, argc, liczby );
  30 
  31   if (n >= 0)
  32     {
  33       double s = sum( liczby, n );
  34       printf ("mamy %d liczb\n", n);
  35       double_vec2stdout (liczby, n);
  36       printf ("sum = %f\n", s);
  37     }
  38   else if (n == -1)
  39     {
  40       printf ("Podano złe dane wejsciowe - niektóre nie są liczbami!\n");
  41     }
  42   else
  43     printf ("Podano zbyt wiele danych wejściowych!\n");
  44 
  45 
  46   return 0;
  47 
  48 }

i funkcje (wszystkie - cały plik sio.h i cały sio.c)

   1 int argv2double_vec( char *argv[], int argc, double v[] );
   2 
   3 void double_vec2stdout( double [], int );
   4 
   5 int file2double_vec( FILE *, double v[], i

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include "sio.h"
   4 
   5 int
   6 argv2double_vec( char *argv[], int argc, double v[] )
   7 {
   8   int i;
   9   double x;
  10   for( i = 1; i < argc; i++ ) {
  11     if( sscanf( argv[i], "%lf", &x ) == 1 )
  12       v[i-1] = x;
  13     else
  14       return -1;
  15   }
  16 
  17   return argc-1;
  18 }
  19 
  20 int
  21 file2double_vec( FILE *input, double v[], int maxvlgt )
  22 {
  23     int n= 0;
  24     double x;
  25 
  26     while( fscanf( input, "%lf", &x ) == 1 && n < maxvlgt )
  27       v[n++] = x;
  28 
  29     if( feof(input) )
  30       return  n;
  31     else if( n == maxvlgt )
  32       return -2;
  33     else if( n > maxvlgt )
  34       return -13;
  35     else
  36       return -1;
  37 
  38 }
  39 
  40 void
  41 double_vec2stdout( double v[], int n )
  42 {
  43   int i;
  44   printf( "[ " );
  45   for( i = 0; i < n; i++ )
  46     printf( "%g ", v[i] );
  47   printf("]\n" );
  48 }

Przy okazji poprawialiśmy też makefile - ostateczna postać:

sumator: main.o sum.o sio.o
  cc -o sumator main.o sum.o sio.o

main.o: main.c sum.h sio.h
  cc -c -Wall main.c

sum.o: sum.c sum.h
  cc -c -Wall sum.c

sio.o: sio.c sio.h
  cc -c -Wall sio.c

test: sumator
  ./sumator 1 2 3 4 5 6 7 8 9.992

filetest: danePrzykladowe
  ./sumator danePrzykladowe

clean:
  rm *.o *~ sumator

I zrobiliśmy sobie generator produkujący dużo danych do testów:

   1 #include <stdio.h>
   2 
   3 int
   4 main ()
   5 {
   6   int i;
   7   for (i = 0; i < 20000; i++)
   8     printf ("%f\n", (double) i / 251 + 644. * i / 73);
   9   return 0;
  10 }

Na koniec zajęliśmy się przekazywaniem argumentów do funkcji przez wartość. Pokazaliśmy, że funkcja

   1 void
   2 swap( double v[], int i, int j )
   3 {
   4    double tmp = v[i];
   5    v[i] = v[j];
   6    v[j] = tmp;
   7 }

rzeczywiście zamieni dwa elementy, natomiast funkcja

   1 void
   2 swap( double x, double y )
   3 {
   4    double tmp = x;
   5    x = y;
   6    y = tmp;
   7 }

nie zamieni wartości argumentów aktualnych, a jedynie wartości ich kopii.

Na koniec powiedzieliśmy sobie o wskaźnikach i pokazaliśmy funkcję, która potrafi zamienić wartości argumentów:

   1 void
   2 swap2( double* ax, double* ay )
   3 {
   4    double tmp = *ax;
   5    *ax = *ay;
   6    *ay = tmp;
   7 }

14 października 2008

Tematyka: Funkcja jako narzędzie abstrakcji algorytmu, podział programu na pliki, pliki nagłówkowe, wprowadzenie do make

Zrefaktoryzowana wersja sumatora - rozbicie na funkcje:

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 
   4 double
   5 sum( double v[], int n )
   6 {
   7   int i;
   8   double s = 0;
   9 
  10   for( i = 0; i < n; i++ )
  11     s += v[i];
  12 
  13   return s;
  14 }
  15 
  16 int
  17 main( int argc, char * argv[] )
  18 {
  19    int i;
  20    double liczby[1000];
  21 
  22    for( i= 1; i < argc; i++ ) {
  23       liczby[i-1] = atof( argv[i] );
  24    }
  25 
  26    printf( "sum = %g\n", sum( liczby, argc-1) );
  27 
  28    return 0;
  29 
  30 }

Wersja ostateczna: program rozbity na kilka plików:

   1 /* main.c - program główny */
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include "sum.h"
   5 #include "sio.h"
   6 
   7 int
   8 main( int argc, char * argv[] )
   9 {
  10    double liczby[1000];
  11    int n;
  12 
  13    if( argc > 1 )
  14      n= argv2double_vec( argv, argc, liczby );
  15    else
  16      n= stdin2double_vec( liczby );
  17 
  18    if( n >= 0 ) {
  19       printf( "mamy %d liczb\n", n );
  20       double_vec2stdout( liczby, n );
  21       printf( "sum = %f\n", sum( liczby, n ) );
  22    } else {
  23       printf( "Podano złe argumenty - niektóre nie są liczbami!\n" );
  24    }
  25 
  26    return 0;
  27 
  28 }

   1 /* sum.h */
   2 double sum( double [], int );

   1 /* sum.c */
   2 #include "sum.h"
   3 
   4 double
   5 sum( double v[], int n )
   6 {
   7   int i;
   8   double s = 0;
   9 
  10   for( i = 0; i < n; i++ )
  11     s += v[i];
  12 
  13   return s;
  14 }

   1 /* sio.h */
   2 int argv2double_vec( char *argv[], int argc, double v[] );
   3 
   4 void double_vec2stdout( double [], int );
   5 
   6 int stdin2double_vec( double v[] );

   1 /* sio.c */
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include "sio.h"
   5 
   6 int
   7 argv2double_vec( char *argv[], int argc, double v[] )
   8 {
   9   int i;
  10   double x;
  11   for( i = 1; i < argc; i++ ) {
  12     if( sscanf( argv[i], "%lf", &x ) == 1 )
  13       v[i-1] = x;
  14     else
  15       return -1;
  16   }
  17 
  18   return argc-1;
  19 }
  20 
  21 int 
  22 stdin2double_vec( double v[] ) 
  23 {
  24    int n= 0;
  25    double x;
  26    while( scanf( "%lf", &x ) == 1 )
  27      v[n++] = x;
  28    return n;
  29 }
  30 
  31 void
  32 double_vec2stdout( double v[], int n )
  33 {
  34   int i;
  35   printf( "[ " );
  36   for( i = 0; i < n; i++ )
  37     printf( "%g ", v[i] );
  38   printf("]\n" );
  39 }

Makefile:

a.out: main.o sum.o sio.o
  cc main.o sum.o sio.o

main.o: main.c sum.h sio.h
  cc -c -Wall main.c

sum.o: sum.c sum.h
  cc -c -Wall sum.c

sio.o: sio.c sio.h
  cc -c -Wall sio.c

test:
  ./a.out 1 2 3 4 5 6 7 8 9.992

7 października 2008

Tematyka: Wprowadzenie do C, pierwszy program, funkcja main i jej argumenty

Echo - wersja ostatnia

   1 #include <stdio.h>
   2 
   3 int
   4 main( int argc, char * argv[] )
   5 {
   6   int i;
   7 
   8   for( i= 0; i < argc; i++ )
   9     printf( "argv[%d]=\"%s\"\n", i, argv[i] );
  10 
  11   /*
  12   printf( "\n" );
  13   */
  14 
  15   return 0;
  16 }

Suma

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 
   4 int
   5 main( int argc, char * argv[] )
   6 {
   7    int i;
   8    double s = 0;
   9    double x;
  10 
  11    for( i= 1; i < argc; i++ ) {
  12       x = atof( argv[i] );
  13       s += x;
  14    }
  15 
  16    printf( "sum = %g\n", s );
  17 
  18    return 0;
  19 
  20 }

2015-09-23 06:43