[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 6: Przetwarzanie napisów

Scenariusz

  1. Student loguje się do systemu LOP (Laboratorium Otwartego Programowania).
  2. Student przechodzi do katalogu roboczego dla zajęć LMP.
  3. Student pobiera z repozytorium kod programów.
  4. Po wyjaśnieniach prowadzącego student przystępuje do kompilacji i uruchomienia programów. Porównuje wynik działania z kodem źródłowym.
  5. Student modyfikuje programy według wskazówek prowadzącego (patrz opis szczegółowy). Powtarza próbę kompilacji i uruchomienia.
  6. Ćwiczenie zaliczeniowe: student rozszerza funkcjonalność programu według zamówienia prowadzącego.

Opis szczegółowy

W trakcie zajęć nauczymy się podstaw przetwarzania tekstu w języku C.

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ęć

lmp6.tgz

Praca nad kodem

Pierwszy program

Nasz pierwszy program wypisuje wszystkie argumenty podane w linii polecenia, ale sortuje je alfabetycznie:

   1 #include <stdio.h>  // wiadomo po co
   2 #include <stdlib.h> // qsort
   3 #include <string.h> // strcmp
   4 
   5 int
   6 alphacmp( const void *a, const void *b ) {
   7   char **ca = (char**)a;
   8   char **cb = (char**)b;
   9   return strcmp( ca, cb );
  10 }
  11 
  12 int
  13 main( int argc, char **argv ) {
  14   int i;
  15 
  16   qsort( argv+1, argc-1, sizeof *argv, alphacmp );
  17 
  18   for( i= 1; i < argc; i++ )
  19     printf( "%s\n", argv[i] );
  20 
  21   return 0;
  22 }

Funkcja qsort sortuje (algorytmem szybkim) tablicę, podaną jako pierwszy argument. Drugi argument to liczba elementów do posortowania, a trzeci - wielkość pojedynczego elementu. Ponieważ funkcja qsort nie wie, co zawiera tablica, a więc aby porównać dwa elementy wywołuje dostarczaną przez użytkownika funkcję (nazwa tej funkcji to ostatni argument przekazywany qsort-owi). Funkcja porównująca otrzymuje dwa wskaźniki na elementy tablicy - musi ,,wyłuskać" wskazywane elementy, porównać je i zwrócić całkowitą liczbę:

Funkcja qsort sortuje wektor niemalejąco według porządku (relacji) określanego przez funkcję porównującą.

Oto przykładowe wyniki uruchomienia powyższego programu:

oer:~/tmp/lmp6/gr1> cc asort.c
oer:~/tmp/lmp6/gr1> ./a.out ala ma kota a ola ma psa
a
ala
kota
ma
ma
ola
psa
oer:~/tmp/lmp6/gr1> ./a.out ala ma kota a Ola ma psa
Ola
a
ala
kota
ma
ma
psa
oer:~/tmp/lmp6/gr1> ./a.out Ala ma kota a Ola ma psa
Ala
Ola
a
kota
ma
ma
psa
oer:~/tmp/lmp6/gr1>

Zwróćmy uwagę, że porównanie wyrazów wykorzystuje kodowanie ASCII, co oznacza, że każda litera wielka jest mniejsza od każdej małej, a polskie znaki są większe od wszystkich liter angielskich.

Drobna zmiana funkcji porównującej - dodanie znaku ,,-" przed wywołaniem strcmp spowoduje, że argumenty wywołania będą sortowane niemalejąco (powinni Państwo sprawdzić to osobiście).

Drugi program

Funkcja qsort potrafi sortować dowolne tablice - wykorzystajmy to do stworzenia programu, który posortuje znaki w każdym napisie, podanym jako argument linii poleceń:

   1 #include <stdio.h>  // wiadomo po co
   2 #include <stdlib.h> // qsort
   3 #include <string.h> // strlen
   4 
   5 int
   6 charcmp( const void *a, const void *b ) {
   7   char *ca = (char*)a;
   8   char *cb = (char*)b;
   9   return  *ca - *cb;
  10 }
  11 
  12 int
  13 main( int argc, char **argv ) {
  14   int i;
  15 
  16 
  17   for( i= 1; i < argc; i++ ) {
  18     qsort( argv[i], strlen(argv[i]), sizeof( char ), charcmp );
  19     printf( "%s\n", argv[i] );
  20   }
  21 
  22   return 0;
  23 }

Kompilacja i uruchomienie:

oer:~/tmp/lmp6/gr1> cc zsort.c
oer:~/tmp/lmp6/gr1> ./a.out ala ma kota a ola ma psa
aal
am
akot
a
alo
am
aps
oer:~/tmp/lmp6/gr1>

Trzeci program

Kolejny program pokazuje sortowanie niezbyt dużego pliku tekstowego. Na jego przykładzie obejrzymy:

   1 #include <stdio.h>  // wiadomo po co
   2 #include <stdlib.h> // qsort
   3 #include <string.h> // strcmp
   4 
   5 #define BUFSIZE 8192    // zakładamy, że linie będą krótsze niż 8kB
   6 #define MAXLINES 100000 // maksymalna liczba linii
   7 
   8 int
   9 alphacmp( const void *a, const void *b ) {
  10   char **ca = (char**)a;
  11   char **cb = (char**)b;
  12   return strcmp( *ca, *cb );
  13 }
  14 
  15 int
  16 main( int argc, char **argv ) {
  17   int i;
  18   char *kopia[MAXLINES];
  19   int ile_linii;
  20 
  21   char buf[BUFSIZE];
  22 
  23   FILE *in= argc > 1 ? fopen( argv[1], "r" ) : stdin;
  24 
  25   if( in == NULL ) {
  26     fprintf( stderr, "%s: błąd: nie mogę czytać pliku %s\n", argv[0], argv[1] );
  27     return EXIT_FAILURE;
  28   }
  29 
  30   ile_linii= 0;
  31   while( fgets( buf, BUFSIZE, in ) != NULL ) {
  32     if( ile_linii < MAXLINES ) {
  33       if( (kopia[ile_linii]= malloc( (strlen(buf)+1) * sizeof( char ) )) == NULL ) {
  34         fprintf( stderr, "%s: błąd: zbyt wiele danych (brak pamięci)\n", argv[0] );
  35         return EXIT_FAILURE;
  36       }
  37       strcpy( kopia[ile_linii], buf );
  38       ile_linii++;
  39     } else {
  40       fprintf( stderr, "%s: błąd: zbyt wiele linii wejścia\n", argv[0] );
  41       return EXIT_FAILURE;
  42     }
  43   }
  44 
  45   qsort( kopia, ile_linii, sizeof *kopia, alphacmp );
  46 
  47   for( i= 0; i < ile_linii; i++ )
  48     printf( "%s", kopia[i] );
  49 
  50   return EXIT_SUCCESS;
  51 }

Dane testowe (proszę zwrócić uwagę na kropkę w ostatniej linii):

Ala
ma kota
a Ola ma
psa
.

I wynik działania:

oer:~/tmp/lmp6/gr1> cc psort.c
oer:~/tmp/lmp6/gr1> ./a.out dane.1
.
Ala
a Ola ma
ma kota
psa
oer:~/tmp/lmp6/gr1>

Ćwiczenie: sprawdzić działanie na innych danych (pliki dane.2 i dane.3, stworzyć samodzielnie duży plik - > 1MB).

Czwarty program

Ostatni przykładowy program wybiera z pliku (i wypisuje na stdout) linie zawierające słowo podane jako pierwszy argument. Nazwa pliku to drugi argument (o ile jest podany). Jeśli podamy tylko jeden argument, to program będzie czytał stdin.

   1 #include <stdio.h>  // wiadomo po co
   2 #include <stdlib.h> // qsort
   3 #include <string.h> // strstr
   4 
   5 #define BUFSIZE 8192    // zakładamy, że linie będą krótsze niż 8kB
   6 
   7 int
   8 main( int argc, char **argv ) {
   9   int ile_linii;
  10   char buf[BUFSIZE];
  11 
  12   char *str= argc > 1 ? argv[1] : NULL;
  13 
  14   FILE *in= argc > 2 ? fopen( argv[2], "r" ) : stdin;
  15 
  16   if( str == NULL ) {
  17     fprintf( stderr, "%s: błąd: proszę podac napis do wyszukiwania\n", argv[0] );
  18     return EXIT_FAILURE;
  19   }
  20 
  21   if( in == NULL ) {
  22     fprintf( stderr, "%s: błąd: nie mogę czytać pliku %s\n", argv[0], argv[2] );
  23     return EXIT_FAILURE;
  24   }
  25 
  26   ile_linii= 0;
  27   while( fgets( buf, BUFSIZE, in ) != NULL ) {
  28     ile_linii++;
  29     if( strstr( buf, str ) != NULL )
  30       printf( "%s", buf );
  31   }
  32 
  33   return EXIT_SUCCESS;
  34 }

Kompilacja i uruchomienie:

oer:~/tmp/lmp6/gr1> cc pstr.c
oer:~/tmp/lmp6/gr1> ./a.out Ala dane.1
Ala
oer:~/tmp/lmp6/gr1> ./a.out ma dane.1
ma kota
a Ola ma
oer:~/tmp/lmp6/gr1>

Ćwiczenie: proszę zmodyfikować program pstr.c tak, aby podawał numery linii, w których znaleziono napis.

Program na zaliczenie

Do wyboru przez prowadzącego:


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