[WikiDyd] [TitleIndex] [WordIndex

Materiały zostały opracowane w ramach realizacji Programu Rozwojowego Politechniki Warszawskiej.

http://prpw.iem.pw.edu.pl/images/KAPITAL_LUDZKI.gif http://prpw.iem.pw.edu.pl/images/EU+EFS_P-kolor.gif

http://www.pr.pw.edu.pl/ jest projektem współfinansowanym przez Unię Europejską w ramach Europejskiego Funduszu społecznego (działanie 4.1.1 Programu Operacyjnego Kapitał Ludzki) i ma na celu poprawę jakości kształcenia oraz dostosowanie oferty dydaktycznej Politechniki Warszawskiej do potrzeb rynku pracy. Będzie on realizowany przez Uczelnię w latach 2008-2015.


Laboratorium metodyki programowania

Ćwiczenie 7: Funkcja jako podstawowy element programu

Scenariusz

Ćwiczenie wykonywane w parach.

  1. Studenci logują się do systemu LOP (Laboratorium Otwartego Programowania).
  2. Studenci przechodzą do katalogu roboczego dla zajęć LMP.
  3. Studenci pobierają z repozytorium kod programów.
  4. Po wyjaśnieniach prowadzącego przystępują do analizy problemu i podziału zadań.
  5. Studenci programują według wskazówek prowadzącego (patrz opis szczegółowy).

Opis szczegółowy

W trakcie zajęć przyjrzymy się dokładnie funkcjom, które są podstawowymi cegiełkami do budowy programów w C. Otrzymacie Państwo bardzo źle napisany program i pracując w zespołach dwuosobowych będziecie zmuszeni do poprawy wewnętrznej struktury tego programu z zachowaniem (co najmniej) funkcjonalności. Nazywa się to refaktoryzacją kodu.

Rozpoczęcie pracy

Zajęcia będą prowadzone na komputerze stud.iem.pw.edu.pl. W celu rozpoczęcia pracy należy zalogować się na tym komputerze za pomocą usługi ssh. Można w tym celu wykorzystać albo dostępny w każdym praktycznie systemie Unix/Linux program ssh albo klienta SSH dla systemu Windows - PuTTY. Na maszynach studenckich w IETiSIP PW można podnieść różne dystrybucje Uniksa/Linuksa lub system Windows, ale w każdej z nich jest zainstalowane oprogramowanie ssh.

Do logowania na maszynie stud.iem.pw.edu.pl należy użyć takiego samego loginu i hasła jakie wykorzystywane sa do dostępu do usług wydziałowych (poczta, e-dziekanat, itd.).

Po zalogowaniu się należy przejść do utworzonego na pierwszych zajęciach katalogu lmp:

 cd lmp

Kod do zajęć

lmp7.tgz

Praca nad kodem

Program wyjściowy

Otrzymujecie program, który wykonuje coś w rodzaju skorowidza dla podanego pliku tekstowego i listy słów. Nazwę pliku podajemy jako pierwszy, a słowa - jako kolejne argumenty w linii poleceń. Program powinien wyszukać, w których liniach występują podane słowa i dla każdego ze słów wypisać listę linii, w których występuje.

Oto przykład uruchomienia programu dla tekstu wiersza Zbigniewa Herberta ,,Przesłanie pana Cogito" (plik dane.3 z ćwiczenia nr 6):

oer:~/tmp/lmp7/gr1> ./a.out ../../lmp6/gr1/dane.3 Cogito czuwaj cogito pocieszy szli Idź idź
słowo "Cogito" wystąpiło w liniach: 3
słowo "czuwaj" wystąpiło w liniach: 38
nie napotkano słowa "cogito"
słowo "pocieszy" wystąpiło w liniach: 36
słowo "szli" wystąpiło w liniach: 5 44
słowo "Idź" wystąpiło w liniach: 5 53
słowo "idź" wystąpiło w liniach: 8 38 49
oer:~/tmp/lmp7/gr1>

A oto tekst źródłowy programu:

   1 #include <stdio.h>  // wiadomo po co
   2 #include <stdlib.h> 
   3 #include <string.h> // strstr
   4 
   5 #define BUFSIZE 8192   // zakładamy, że linie będą krótsze niż 8kB
   6 #define MAXLINII 1000  // zakładamy, że słowo będzie wystepować w nie więcej, niż 1000 liniach
   7 
   8 #define MAXSLOW 100     // skorowidz dla nie więcej, niż 100 słów
   9 
  10 char *slowa[MAXSLOW];   // słowa do wyszukiwania
  11 int ile_slow;
  12 
  13 int linie[MAXSLOW][MAXLINII]; // tu zapisujemy numery linii
  14                               // linie[i][0] to licznik
  15                               // linie[i][1] ... to nr-y linii, w których wystąpiło słowo
  16 
  17 int
  18 main( int argc, char **argv ) {
  19   int i,j;
  20   int ile_linii;
  21   char buf[BUFSIZE];
  22 
  23   FILE *in= argc > 1 ? fopen( argv[1], "r" ) : stdin;
  24 
  25   for( i= 2; i < argc; i++ ) {
  26     slowa[ile_slow]= argv[i];
  27     linie[ile_slow][0]= 0;
  28     ile_slow++;
  29   }
  30 
  31   if( ile_slow == 0 ) {
  32     fprintf( stderr, "%s: błąd: proszę podać słowa do wyszukiwania\n", argv[0] );
  33     return EXIT_FAILURE;
  34   }
  35 
  36   if( in == NULL ) {
  37     fprintf( stderr, "%s: błąd: nie mogę czytać pliku %s\n", argv[0], argv[1] );
  38     return EXIT_FAILURE;
  39   }
  40 
  41   ile_linii= 0;
  42   while( fgets( buf, BUFSIZE, in ) != NULL ) {
  43     ile_linii++;
  44     for( i= 0; i < ile_slow; i++ )
  45       if( strstr( buf, slowa[i] ) != NULL ) {
  46         linie[i][0]++;
  47         linie[i][linie[i][0]]= ile_linii;
  48       }
  49   }
  50 
  51   for( i= 0; i < ile_slow; i++ ) {
  52     if( linie[i][0] > 0 ) {
  53       printf( "słowo \"%s\" wystąpiło w liniach:", slowa[i] );
  54       for( j= 1; j <= linie[i][0]; j++ )
  55         printf( " %d", linie[i][j] );
  56       printf( "\n" );
  57     } else {
  58       printf( "nie napotkano słowa \"%s\"\n", slowa[i] );
  59     }
  60   }
  61 
  62   return EXIT_SUCCESS;
  63 }

Przytoczony powyżej program "jakoś działa" i można oczywiście zapytać "po co go poprawiać?" Otóż proszę sobie wyobrazić, że dostaliby Państwo polecenie zmodyfikowania funkcjonalności tego programu tak aby na przykład:

Przy obecnej formie programu trudno sobie wyobrazić, aby mogło nad nim jednocześnie pracować więcej osób. Jeśli jednak podzielimy kod na kawałki, każdy kawałek zajmie się odpowiednio wydzielonym fragmentem zadania, a interfejsy komunikacji zostaną dobrze określone, to:

Rozpatrzmy poprawioną wersję funkcji main, w której przeniesiono gdzie indziej wypisywanie skorowidza:

   1 #include <stdio.h>  // wiadomo po co
   2 #include <stdlib.h>        
   3 #include <string.h> // strstr       
   4 
   5 #define BUFSIZE 8192   // zakładamy, że linie będą krótsze niż 8kB
   6 #define MAXLINII 1000  // zakładamy, że słowo będzie wystepować w nie więcej, niż 1000 liniach
   7 
   8 #define MAXSLOW 100     // skorowidz dla nie więcej, niż 100 słów
   9 
  10 void wypisz_skorowidz( int ile_slow, char *slowa[], int linie[][MAXLINII] );
  11 
  12 int
  13 main( int argc, char **argv ) {
  14   int i;
  15   int ile_linii;
  16   char buf[BUFSIZE];
  17 
  18   FILE *in= argc > 1 ? fopen( argv[1], "r" ) : stdin;
  19 
  20   char *slowa[MAXSLOW];   // słowa do wyszukiwania
  21   int ile_slow;
  22   int linie[MAXSLOW][MAXLINII]; // tu zapisujemy numery linii
  23                               // linie[i][0] to licznik
  24                               // linie[i][1] ... to nr-y linii, w których wystąpiło słowo
  25 
  26   for( i= 2; i < argc; i++ ) {
  27     slowa[ile_slow]= argv[i];
  28     linie[ile_slow][0]= 0;
  29     ile_slow++;
  30   }
  31 
  32   if( ile_slow == 0 ) {
  33     fprintf( stderr, "%s: błąd: proszę podać słowa do wyszukiwania\n", argv[0] );
  34     return EXIT_FAILURE;
  35   }
  36 
  37   if( in == NULL ) {
  38     fprintf( stderr, "%s: błąd: nie mogę czytać pliku %s\n", argv[0], argv[1] );
  39     return EXIT_FAILURE;
  40   }
  41 
  42   ile_linii= 0;
  43   while( fgets( buf, BUFSIZE, in ) != NULL ) {
  44     ile_linii++;
  45     for( i= 0; i < ile_slow; i++ )
  46       if( strstr( buf, slowa[i] ) != NULL ) {
  47         linie[i][0]++;
  48         linie[i][linie[i][0]]= ile_linii;
  49       }
  50   }
  51 
  52   wypisz_skorowidz( ile_slow, slowa, linie );
  53 
  54   return EXIT_SUCCESS;
  55 }
  56 
  57 void wypisz_skorowidz( int ile_slow, char *slowa[], int linie[][MAXLINII] ) {
  58   int i,j;
  59 
  60   for( i= 0; i < ile_slow; i++ ) {
  61     if( linie[i][0] > 0 ) {
  62       printf( "słowo \"%s\" wystąpiło w liniach:", slowa[i] );
  63       for( j= 1; j <= linie[i][0]; j++ )
  64         printf( " %d", linie[i][j] );
  65       printf( "\n" );
  66     } else {
  67       printf( "nie napotkano słowa \"%s\"\n", slowa[i] );
  68     }
  69   }
  70 }

To niewielka zmiana, ale funkcja main zyskała na czytelności, a funkcję wypisz_skorowidz będzie można łatwo przenieść do innego pliku, gdzie może zacząć ją poprawiać ktoś inny, niż osoba pracująca nad funkcją main. Kolejny ruch to wyodrębnienie funkcji inicjującej skorowidz.

   1 #include <stdio.h>  // wiadomo po co
   2 #include <stdlib.h>        
   3 #include <string.h> // strstr       
   4 
   5 #define BUFSIZE 8192   // zakładamy, że linie będą krótsze niż 8kB
   6 #define MAXLINII 1000  // zakładamy, że słowo będzie wystepować w nie więcej, niż 1000 liniach
   7 
   8 #define MAXSLOW 100     // skorowidz dla nie więcej, niż 100 słów
   9 
  10 void zainicjuj_skorowidz( int argc, char **argv, int *ile_slow, char *slowa[], int linie[][MAXLINII] );
  11 
  12 void wypisz_skorowidz( int ile_slow, char *slowa[], int linie[][MAXLINII] );
  13 
  14 int
  15 main( int argc, char **argv ) {
  16   int i;
  17   int ile_linii;
  18   char buf[BUFSIZE];
  19 
  20   FILE *in= argc > 1 ? fopen( argv[1], "r" ) : stdin;
  21 
  22   char *slowa[MAXSLOW];   // słowa do wyszukiwania
  23   int ile_slow;
  24   int linie[MAXSLOW][MAXLINII]; // tu zapisujemy numery linii
  25                               // linie[i][0] to licznik
  26                               // linie[i][1] ... to nr-y linii, w których wystąpiło słowo
  27 
  28   zainicjuj_skorowidz( argc, argv, &ile_slow, slowa, linie );
  29 
  30   if( ile_slow == 0 ) {
  31     fprintf( stderr, "%s: błąd: proszę podać słowa do wyszukiwania\n", argv[0] );
  32     return EXIT_FAILURE;
  33   }
  34 
  35   if( in == NULL ) {
  36     fprintf( stderr, "%s: błąd: nie mogę czytać pliku %s\n", argv[0], argv[1] );
  37     return EXIT_FAILURE;
  38   }
  39 
  40   ile_linii= 0;
  41   while( fgets( buf, BUFSIZE, in ) != NULL ) {
  42     ile_linii++;
  43     for( i= 0; i < ile_slow; i++ )
  44       if( strstr( buf, slowa[i] ) != NULL ) {
  45         linie[i][0]++;
  46         linie[i][linie[i][0]]= ile_linii;
  47       }
  48   }
  49 
  50   wypisz_skorowidz( ile_slow, slowa, linie );
  51 
  52   return EXIT_SUCCESS;
  53 }
  54 
  55 void zainicjuj_skorowidz( int argc, char **argv, int *ile_slow, char *slowa[], int linie[][MAXLINII] ) {
  56         int i;
  57         *ile_slow= 0;
  58   for( i= 2; i < argc; i++ ) {
  59     slowa[*ile_slow]= argv[i];
  60     linie[*ile_slow][0]= 0;
  61     ++ *ile_slow;
  62   }
  63 }
  64 
  65 void wypisz_skorowidz( int ile_slow, char *slowa[], int linie[][MAXLINII] ) {
  66   int i,j;
  67 
  68   for( i= 0; i < ile_slow; i++ ) {
  69     if( linie[i][0] > 0 ) {
  70       printf( "słowo \"%s\" wystąpiło w liniach:", slowa[i] );
  71       for( j= 1; j <= linie[i][0]; j++ )
  72         printf( " %d", linie[i][j] );
  73       printf( "\n" );
  74     } else {
  75       printf( "nie napotkano słowa \"%s\"\n", slowa[i] );
  76     }
  77   }
  78 }

Przy tej modyfikacji znaleźliśmy i poprawiliśmy ...może drobny... ale jednak błąd - otóż zmienna ile_slow była dotąd inicjowana tylko niejawnie (jako obiekt globalny) - przy przeniesieniu jej do wnętrza funkcji main (jak powinno być, aby nie umożliwiać niekontrolowanego przepływu informacji między funkcjami) stawała się zmienną automatyczną i przyjmowała losową wartość, co było błędem niełatwym do wykrycia nawet w tak prostym programie.

Zwróćmy uwagę, że zmiany kodu dokonujemy drobnymi krokami - mając działający program staramy się nie pisać go od nowa, ale stopniowo przekształcać w program lepszy, cały czas kontrolując jego poprawne działanie.

Następnym etapem będzie poprawienie interfejsu pomiędzy funkcjami. Chcemy połączyć wszystkie zmienne opisujące skorowidz w jedną strukturę. Przy okazji zmienimy też sposób przechowywania numerów linii, w których wystąpiły słowa. Statyczną tablicę zastąpimy przez listy liniowe. Likwidujemy w ten sposób ograniczenia na liczbę pozycji skorowidza i liczbę linii, w których może występować słowo.

   1 #include <stdio.h>  // wiadomo po co                                                        
   2 #include <stdlib.h>                                                              
   3 #include <string.h> // strstr                                                               
   4 
   5 #define BUFSIZE 8192   // zakładamy, że linie będą krótsze niż 8kB
   6 
   7 typedef struct e {
   8         int nmbr; 
   9         struct e *next;
  10 } * list_t;            
  11 
  12 list_t dodaj_do_listy( list_t l, int n ) {
  13   // dopisuje nowy element na koniec listy l
  14   // nowy element przechowuje n (jego nmbr == n)
  15         if( l == NULL ) {                       
  16                 list_t nw= malloc( sizeof *nw );
  17                 nw->nmbr= n;                    
  18                 nw->next= NULL;                 
  19                 return nw;                      
  20         } else {                                
  21                 list_t tmp= l;                  
  22                 while( tmp->next != NULL )      
  23                         tmp= tmp->next;         
  24                 tmp->next= malloc( sizeof * (tmp->next) );
  25                 tmp->next->nmbr= n;                       
  26                 tmp->next->next= NULL;                    
  27                 return l;                                 
  28         }                                                 
  29 }                                                         
  30 
  31 typedef struct {
  32         int ile_slow;
  33         char **slowa;  
  34         int *licznik;   // w ilu liniach występują słowa
  35         list_t *linie;  // listy zawierające nr linii zawierajacych
  36 } skorowidz_t;                                                     
  37 
  38 void zainicjuj_skorowidz( int argc, char **argv, skorowidz_t *s );
  39 
  40 void dodaj_pozycje_skorowidza( skorowidz_t *skorowidz, int i, int linia );
  41 
  42 void wypisz_skorowidz( skorowidz_t *s );
  43 
  44 int
  45 main( int argc, char **argv ) {
  46   int i;                       
  47   int ile_linii;               
  48   char buf[BUFSIZE];           
  49 
  50   FILE *in= argc > 1 ? fopen( argv[1], "r" ) : stdin;
  51 
  52         skorowidz_t skorowidz;
  53 
  54   zainicjuj_skorowidz( argc, argv, &skorowidz);
  55 
  56   if( skorowidz.ile_slow == 0 ) {
  57     fprintf( stderr, "%s: błąd: proszę podać słowa do wyszukiwania\n", argv[0] );
  58     return EXIT_FAILURE;
  59   }
  60 
  61   if( in == NULL ) {
  62     fprintf( stderr, "%s: błąd: nie mogę czytać pliku %s\n", argv[0], argv[1] );
  63     return EXIT_FAILURE;
  64   }
  65 
  66   ile_linii= 0;
  67   while( fgets( buf, BUFSIZE, in ) != NULL ) {
  68     ile_linii++;
  69     for( i= 0; i < skorowidz.ile_slow; i++ )
  70       if( strstr( buf, skorowidz.slowa[i] ) != NULL ) {
  71                                 dodaj_pozycje_skorowidza( &skorowidz, i, ile_linii );
  72       }
  73   }
  74 
  75   wypisz_skorowidz( &skorowidz );
  76 
  77   return EXIT_SUCCESS;
  78 }
  79 
  80 void zainicjuj_skorowidz( int argc, char **argv, skorowidz_t * skorowidz ) {
  81         int i;
  82         skorowidz->ile_slow= argc-2;
  83         skorowidz->slowa = malloc( skorowidz->ile_slow * sizeof * skorowidz->slowa );
  84         skorowidz->licznik = malloc( skorowidz->ile_slow * sizeof * skorowidz->licznik );
  85         skorowidz->linie = malloc( skorowidz->ile_slow * sizeof * skorowidz->linie );
  86   for( i= 2; i < argc; i++ ) {
  87     skorowidz->slowa[i-2]= argv[i];
  88     skorowidz->licznik[i-2]= 0;
  89                 skorowidz->linie[i-2]= NULL;
  90   }
  91 }
  92 
  93 void dodaj_pozycje_skorowidza( skorowidz_t *skorowidz, int i, int linia ) {
  94         skorowidz->licznik[i]++;
  95         skorowidz->linie[i]= dodaj_do_listy( skorowidz->linie[i], linia );
  96 }
  97 
  98 void wypisz_skorowidz( skorowidz_t *skorowidz ) {
  99   int i,j;
 100 
 101   for( i= 0; i < skorowidz->ile_slow; i++ ) {
 102     if( skorowidz->licznik[i] > 0 ) {
 103                         list_t tmp= skorowidz->linie[i];
 104       printf( "słowo \"%s\" wystąpiło w liniach:", skorowidz->slowa[i] );
 105       while( tmp != NULL ) {
 106         printf( " %d", tmp->nmbr );
 107                                 tmp= tmp->next;
 108                         }
 109       printf( "\n" );
 110     } else {
 111       printf( "nie napotkano słowa \"%s\"\n", skorowidz->slowa[i] );
 112     }
 113   }
 114 }

Powyższy plik (indx3.c) jest znacznie dłuższy, niż pierwowzór i wydaje się bardziej skomplikowany, ale można go łatwo podzielić na trzy moduły: listę liniową, skorowidz i funkcję main. Podział jest równoważny wyodrębnieniu 4 plików (list.h, list.c, skorowidz.h, skorowidz.c). Funkcję main pozostawimy w pliku indx4.c. Cała wersja znajduje się w podkatalogu v4 repozytorium.

Aby nie przedłużać nadmiernie tego opisu obejrzyjmy tylko plik zawierający funkcję main:

   1 #include <stdio.h>  // wiadomo po co
   2 #include <stdlib.h>
   3 #include <string.h> // strstr
   4 
   5 #include "list.h"
   6 #include "skorowidz.h"
   7 
   8 #define BUFSIZE 8192   // zakładamy, że linie będą krótsze niż 8kB
   9 
  10 int
  11 main( int argc, char **argv ) {
  12   int i;
  13   int nr_linii;
  14   char buf[BUFSIZE];
  15 
  16   FILE *in= argc > 1 ? fopen( argv[1], "r" ) : stdin;
  17 
  18   skorowidz_t skorowidz;
  19 
  20   zainicjuj_skorowidz( argc, argv, &skorowidz);
  21 
  22   if( skorowidz.ile_slow == 0 ) {
  23     fprintf( stderr, "%s: błąd: proszę podać słowa do wyszukiwania\n", argv[0] );
  24     return EXIT_FAILURE;
  25   }
  26 
  27   if( in == NULL ) {
  28     fprintf( stderr, "%s: błąd: nie mogę czytać pliku %s\n", argv[0], argv[1] );
  29     return EXIT_FAILURE;
  30   }
  31 
  32   nr_linii= 0;
  33   while( fgets( buf, BUFSIZE, in ) != NULL ) {
  34     nr_linii++;
  35     for( i= 0; i < skorowidz.ile_slow; i++ )
  36       if( strstr( buf, skorowidz.slowa[i] ) != NULL ) {
  37         dodaj_pozycje_skorowidza( &skorowidz, i, nr_linii );
  38       }
  39   }
  40 
  41   wypisz_skorowidz( &skorowidz );
  42 
  43   return EXIT_SUCCESS;
  44 }

Funkcja main jest wyraźnie krótsza i bardziej czytelna. Nie ma w niej szczegółów implementacji skorowidza (te znajdują się w plikach skorowidz.*) i studiując ją łatwiej zrozumiemy, jaki jest cel programu. Pomagają w tym długie - czytelne nazwy zmiennych.

Program na zaliczenie

Należy zmodyfikować program index.c:

Modyfikacje powinny być podobne do tego, co pokazano powyżej, ale nie identyczne. Studenci powinni zaproponować inny sposób przechowywania skorowidza - w szczególności używać nie list liniowych, a wektorów o zmiennej długości do przechowywania numerów linii. Należy także poprawić wyszukiwanie słów w linii tak, aby odnajdywać słowa, a ignorować ich fragmenty.


To już prawie wszystko, ale nie wolno nam zapomnieć, że

materiały zostały opracowane w ramach realizacji Programu Rozwojowego Politechniki Warszawskiej.

http://prpw.iem.pw.edu.pl/images/KAPITAL_LUDZKI.gif http://prpw.iem.pw.edu.pl/images/EU+EFS_P-kolor.gif

http://www.pr.pw.edu.pl/ jest projektem współfinansowanym przez Unię Europejską w ramach Europejskiego Funduszu społecznego (działanie 4.1.1 Programu Operacyjnego Kapitał Ludzki) i ma na celu poprawę jakości kształcenia oraz dostosowanie oferty dydaktycznej Politechniki Warszawskiej do potrzeb rynku pracy. Będzie on realizowany przez Uczelnię w latach 2008-2015.


2015-09-23 06:44