[WikiDyd] [TitleIndex] [WordIndex

Języki i metodyka programowania - kurs w sem. zimowym 2010/2011

Wykład V: 2 listopada 2010

Najpierw była kartkówka, na której mieli Państwo wykonać zadanie niewykonalne - funkcję, która zamiania wartości dwóch zmiennych ale dostaje kopie tych wartości. Wyjaśniliśmy sobie potem, że funkcja musi dostać wskaźniki do zmiennych, żeby manipulować przechowywanymi w tych zmiennych obiektami. Efektem naszych rozważań był taki programik demonstrujący działanie funkcji wymieniającej wartości dwóch zmiennych typu int:

   1 #include <stdio.h>
   2 
   3 void swap( int *x, int *y )
   4 {
   5     int t;
   6     t= *x;
   7     *x= *y;
   8     *y= t;
   9 }
  10 
  11 int
  12 main()
  13 {
  14     int a= 5;
  15     int b= 50;
  16 
  17     swap( &a, &b );
  18 
  19     printf( "Teraz %d==50, %d==5\n", a, b );
  20 
  21     return 0;
  22 }

Konsekwencją rozważań o tym, ze nazwa tablicy to w istocie stała wskaźnikowa, wskazująca na pierwszy element tablicy jest konstatacja, że funkcja może zamieniać zawartość tablicy - mówiliśmy już o tym wcześniej, ale pokazaliśmy to jeszcze raz, z pełnym zrozumieniem analizując działanie funkcji sortującej wektor zawierający liczby double. Zastosowaliśmy prosty algorytm sortowania przez wstawianie:

   1 #include <stdio.h>
   2 
   3 void sort( double t[], int n )
   4 {
   5     int i,j;
   6     double tmp;
   7         for( i= 1; i <n; i++ )  {
   8         tmp = t[i];
   9         for( j= i; j > 0 && t[j-1] > tmp; j-- )
  10             t[j]= t[j-1];
  11         t[j]= tmp;
  12     }
  13 }
  14 
  15 void wypisz_tab( double t[], int n, FILE *out ) {
  16         int i;
  17         fprintf( out, "[" );
  18         for( i= 0; i < n; i++ )
  19                 fprintf( out, " %g", t[i] );
  20         fprintf( out, " ]\n" );
  21 }
  22 
  23 int
  24 main()
  25 {
  26         double t[] = { 3.6, 7.3, 9.1, 127, 13.7, -3, -1 };
  27 
  28         int n = sizeof t / sizeof t[0];
  29 
  30         wypisz_tab( t, n, stdout );
  31 
  32         sort( t, n );
  33 
  34         wypisz_tab( t, n, stdout );
  35 
  36         return 0;
  37 }

Potem zaczęliśmy się zastanawiać nad sortowaniem innych danych - np. napisów. Doszliśmy do wniosku, że różnica polega na sposobie porównywania elementów tablicy. Efektem i ilustracją tych rozważań był następujący programik:

   1 #include <stdio.h>
   2 
   3 int strcmp( char *a, char *b ) {  /* porównuje napisy a i b, 
   4                                      zwraca l. dodatnią, gdy a > b
   5                                      zwraca 0, gdy a == b
   6                                      zwraca li. ujemną, gdy a < b */
   7     while( *a == *b && *a != '\0' ) {
   8         a++;
   9         b++;
  10     }
  11     return *b - *a;
  12 }
  13 
  14 void sort( char** t, int n )
  15 {
  16     int i,j;
  17     char* tmp;
  18     for( i= 1; i <n; i++ ) {
  19         tmp = t[i];
  20         for( j= i; j > 0 && strcmp( t[j-1], tmp ) > 0; j-- )
  21             t[j]= t[j-1];
  22         t[j]= tmp;
  23     }
  24 }
  25 
  26 void wypisz_tab( char* t[], int n, FILE *out ) {
  27         int i;
  28         fprintf( out, "[" );
  29         for( i= 0; i < n; i++ )
  30                 fprintf( out, " \"%s\"", t[i] );
  31         fprintf( out, " ]\n" );
  32 }
  33 
  34 int
  35 main( int argc, char *argv[])
  36 {
  37         wypisz_tab( argv, argc, stdout );
  38 
  39         sort( argv, argc );
  40 
  41         wypisz_tab( argv, argc, stdout );
  42 
  43         return 0;
  44 }

W następnym kroku postanowiliśmy napisać program, który wczytuje z pliku i przetwarza listę wyników kolokwium. Dane mają miec następującą postać:

Jan Kowalski 28
Adam Nowak 33
Jose Perezbardzodlugienazwiskojaktonapoludniu 78
Zosia Samosia 8
Mis Puchatek 123
Prosiaczek Beznazwiska 43
Tygrysek Tezbeznazwiskaaleinnego 89
Klapouchy Osiolek 0
Myszka Miki 12
Minnie Miki 99
Kaczor Donald 67
I Wystarczy 89

Rozpoczęliśmy od programu wczytującego te dane:

   1 #include <stdio.h>
   2 #include <string.h>
   3 #include <stdlib.h>
   4 
   5 #include "strbib.h"
   6 
   7 int
   8 main (int argc, char **argv)
   9 {
  10   FILE *in = argc > 1 ? fopen (argv[1], "r") : stdin;
  11 
  12   char imie[1024];
  13   char nazw[1024];
  14   int lp;
  15 
  16   char *elista[10000];
  17   int n = 0;
  18   int i;
  19 
  20   if (in == NULL)
  21     return 1;
  22 
  23   while (fscanf (in, "%s %s %d", imie, nazw, &lp) == 3) {
  24     char *nowenazwisko = malloc (strlen (nazw) + 1);
  25     strcpy (nowenazwisko, nazw);
  26     elista[n++] = nowenazwisko;
  27   }
  28 
  29   sort (elista, n);
  30 
  31   for (i = 0; i < n; i++)
  32     printf ("nazwisko nr %d: %s\n", i, elista[i]);
  33 
  34   return 0;
  35 }

Pokazaliśmy w nim nową funkcję - malloc - pozwalającą pobrac od systemu potrzebną ilość pamięci dynamicznie - w zależności od wielkości danych, które przetwarzamy.


2015-09-23 06:44