[WikiDyd] [TitleIndex] [WordIndex

Uwaga: starsze wykłady są niżej

WA 17.12.2013

Na początku obejrzeliśmy, jak można zrobić kalkulator onp prościej - przechowując i przekazując tylko napisy, które mogą przechowywać zarówno zmienne, jak i stałe (liczby).

Kod jest tutaj.

Następnie zajęliśmy się testowaniem poprawnego zarządzania pamięcią. Omówiliśmy pokrótce wykorzystanie programu valgrind do kontroli pamięci.

W9 10.12.2013

Zastanawialiśmy się, jak dodać do kalkulatora obsługę zmiennych i jednoargumentowych funkcji. Dalej męczyliśmy był kalkulator ONP - dodając do niego poszczególne moduły i próbując je implementować. Okazało się, że decyzja o przechowywaniu na stosie i przekazywaniu pomiędzy modułami zróżnicowanych obiektów doprowadziła do dużej komplikacji kodu.

Kod jest tutaj

W8 03.12.2013

Mówiliśmy o podziale programu na pliki i o projektowaniu kodu metodą zstępującą (top-to-down). Przykładem, który męczyliśmy był kalkulator ONP - podzieliliśmy go na analizator leksykalny, analizator składni i stos i implementowaliśmy poszczególne moduły.

Kod jest tutaj

W7 26.11.2013

Na początku pisali Państwo kartkówkę: zadaniem było zaimplementowanie funkcji wyszukującej pierwszy element wektora większy od zadanej liczby i zwracającej indeks tego elementu lub -1 jeśli wszystkie elementy wektora są od zadanej liczby mniejsze. Przykładowe rozwiązanie:

   1 int wiekszy( double t[], int n, double x ) {
   2         int i;
   3         for( i = 0; i < n; i++ )
   4                 if( t[i] > x )
   5                         return i;
   6         return -1;
   7 }

W trakcie wykładu omawialiśmy dynamiczne struktury danych tworzone za pomocą wskaźników. Powtórzyliśmy tworzenie list linowych, a następnie zastosowaliśmy drzewo poszukiwań binarnych do tworzenia wzorca wypełnienia macierzy tworzonej na podstawie siatki trójkątnych elementów skończonych. Pliki źródłowe zawiera archiwum sppat_tree.zip.

W6 19.11.2013

Omawialiśmy konstrukcję wzorca wypełnienia macierzy tworzonej na podstawie siatki trójkątnych elementów skończonych. Pliki źródłowe zawiera archiwum sppat.zip.

Jako pracę domową powinni Państwo poprawić funkcję add_non_zero_in_order tak, aby zlikwidować dodawanie duplikatu na pierwszej pozycji.

W5 12.11.2013

Zaczęliśmy od Makefile (skryptu programu make do poprzedniego projektu:

CFLAGS = -Wall --ansi -pedantic

all: rl test

rl: rl.o cont.o
        $(CC) $(CFLAGS) $^ -o rl

test: rl x+1
        ./rl x+1

rl.o: cont.h

cont.o: cont.h

.PHONY: clean

clean: 
        -rm *.o rl

Znaleźliśmy też (przez testowanie) i poprawiliśmy błąd w funkcji rl z poprzedniego wykładu

   1 int rl( cont_t * d, double *a, double *b ) {
   2         int i;
   3         double sxx= 0, sxy= 0, sx= 0, sy= 0;
   4         for( i = 0; i < d->n; i ++ ) {
   5                 sxx += d->d[i].x * d->d[i].x;
   6                 sxy += d->d[i].x * d->d[i].y;
   7                 sx += d->d[i].x;
   8                 sy += d->d[i].y;
   9         }
  10         *a = ( d->n * sxy - sx * sy ) / ( d->n * sxx - sx * sx );
  11         *b = ( sxx * sy - sxy * sx ) / ( d->n * sxx - sx * sx );
  12         return 1;
  13 }

Oto archiwum z całym mini-projektem regresji liniowej: rl.zip.

Następnym zadaniem było przerobienie kontenera tak, aby przechowywać w nim plik, który następnie posortowaliśmy. Przy okazji przyjrzeliśmy się funkcjom operującym na napisach. Archiwum z plikami źródłowymi: sortfile.zip.

W4 5.11.2013

Kontener:

   1 #ifndef _CONT_H_
   2 #define _CONT_H_
   3 
   4 typedef struct p {
   5         double x;
   6         double y;
   7 } pair_t;
   8 
   9 typedef struct {
  10         int size; // capacity
  11         int n;    // actual size
  12         pair_t *d; // data
  13 } cont_t;
  14 
  15 cont_t * init_cont( int );
  16 
  17 int cont_resized( cont_t * );
  18 
  19 #endif
  20 

   1 #include <stdlib.h>
   2 
   3 #include "cont.h"
   4 
   5 cont_t *init_cont( int initial_size ) {
   6         cont_t *c = malloc( sizeof *c );
   7         if( c == NULL )
   8                 return NULL;
   9         (*c).d = malloc( initial_size * sizeof * (c->d) );
  10   if( c->d == NULL ) {
  11                 free( c );
  12                 return NULL;
  13         }
  14   c->size = initial_size;
  15         c->n = 0;
  16         return c;
  17 }
  18 
  19 int cont_resized( cont_t *c ) {
  20         pair_t * nd = realloc( c->d, 2*c->size*sizeof *nd );
  21         if( nd == NULL )
  22                 return 0;
  23         else {
  24                 c->d = nd;
  25                 c->size *= 2;
  26                 return 1;
  27         }
  28 }

Czytanie i sortowanie punktów

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 
   4 #include "cont.h"
   5 
   6 int cmp( const void *a, const void *b ) {
   7         pair_t *pa = (pair_t*)a;
   8         pair_t *pb = (pair_t*)b;
   9         if( pa->x < pb->x )
  10                         return -1;
  11         else if ( pa->x > pb->x )
  12                         return 1;
  13         else
  14                         return 0;
  15 }
  16 
  17 int main( int argc, char ** argv ) {
  18 #ifdef DEBUG
  19         int n = argc > 1 ? atoi(argv[1]) : 10;
  20         cont_t *dane = init_cont( n );
  21 #else
  22         cont_t *dane = init_cont( 4 );
  23 #endif
  24         int i;
  25 
  26 #ifdef DEBUG
  27         printf( "dane=%p\n", dane );
  28         printf( " wielkosc=%d\n", dane->size );
  29         printf( " wypelnienie=%d\n", dane->n );
  30         printf( " dane->d=%p\n", dane->d );
  31 
  32         if( cont_resized( dane ) ) {
  33                 printf( " nowa wielkosc=%d\n", dane->size );
  34                 printf( " dane->d=%p\n", dane->d );
  35         }
  36 #endif
  37 
  38         FILE *in = argc > 1 ? fopen( argv[1], "r" ) : stdin;
  39 
  40         double x,y;
  41 
  42         while( fscanf( in, "%lf %lf", &x, &y ) == 2 ) {
  43                 if( dane->size == dane->n && !cont_resized( dane) ) {
  44                         fprintf( stderr, "Nie ma miejsca na tyle danych\n" );
  45                         return EXIT_FAILURE;
  46                 }
  47                 dane->d[dane->n].x = x;
  48                 dane->d[dane->n].y = y;
  49                 dane->n++;
  50         }
  51         fclose( in );
  52 
  53         qsort( dane->d, dane->n, sizeof * dane->d, cmp );
  54 
  55         for( i= 0; i < dane->n; i++ )
  56                 printf( "%g %g\n", dane->d[i].x, dane->d[i].y );
  57 
  58         printf( " akt. wielkosc kontenera=%d, wypelnienie=%d\n", dane->size, dane->n );
  59 
  60         return 0;
  61 }

Regresja liniowa (http://pl.wikipedia.org/wiki/Regresja_liniowa)

   1 int rl( cont_t * d, double *a, double *b ) {
   2         int i;
   3         double sxx= 0, sxy= 0, sx= 0, sy= 0;
   4         for( i = 0; i < d->n; i ++ ) {
   5                 sxx += d->d[i].x * d->d[i].x;
   6                 sxy += d->d[i].x * d->d[i].y;
   7                 sx += d->d[i].x;
   8                 sy += d->d[i].y;
   9         }
  10         *a = ( d->n * sxy - sx*sy ) / ( d->n *sxx - sx *sx );
  11         *b = ( sxx * sy - sxy*sy ) / ( d->n *sxx - sx *sx );
  12         return 1;
  13 }

W3 29.10.2013

#include <stdio.h>
#include <stdlib.h>

#define INIT_SIZE 8

int main( int argc, char **argv ) {
  double *t = NULL;
  int n = 0;
  int size = 0;
  int i;
  FILE *in = argc > 1 ? fopen( argv[1], "r" ) : stdin;
  
  t= malloc( INIT_SIZE * sizeof *t );
  if( t == NULL ) {
    fprintf( stderr, "Nie ma pamięci i koniec!\n" );
    return 1;
  }
  size = INIT_SIZE;

  while( fscanf( in, "%lf", &t[n] ) == 1 ) {
    n++;
    if( n == size ) {
      double *nt = malloc( 2*size * sizeof *nt );
      int i;
      if( nt == NULL ) {
        fprintf( stderr, "Nie ma pamięci i koniec!\n" );
        return 1;
      }
      size *= 2;
      for( i= 0; i < n; i++ )
        nt[i] = t[i];
      free(t);
      t = nt;
      fprintf( stderr, "Resize: %d -> %d\n", size/2, size );
    }
  }

  for( i= 0; i < n; i += 2 )
    printf( "%g %g\n", t[i], t[i+1] );

  return 0;
}

#include <stdio.h>
#include <stdlib.h>

#define INIT_SIZE 8

double *resize( double *t, int *size, int n ) {
  double *nt = malloc( 2*(*size) * sizeof *nt );
  int i;
  if( nt == NULL ) {
    return NULL;
  }
  *size *= 2;
  for( i= 0; i < n; i++ )
    nt[i] = t[i];
  free(t);
#ifdef DEBUG
  fprintf( stderr, "Resize: %d -> %d\n", *size/2, *size );
#endif
  return nt;
}

void insort( double *v, int np ) {
/* v zawiera np par liczb.
   Sortujemy rosnaco wg drugiej liczby z pary */
  int i, j;
  double t[2];

  for( i = 1; i < np; i++ ) {
    t[0]= v[2*i];
    t[1]= v[2*i+1];
    for( j = i; j > 0 && v[2*(j-1)+1] > t[1]; j-- ) {
      v[2*j] = v[2*(j-1)];     
      v[2*j+1] = v[2*(j-1)+1];
    }
    v[2*j]= t[0];
    v[2*j+1]= t[1];
  }
}

int cmpfun( const void *a, const void *b ) {
  double a2 = *((double *)a+1);
  double b2 = *((double *)b+1);
  if( a2 < b2 )
    return -1;
  else if ( a2 > b2 )
    return 1;
  else
    return 0;
}

int main( int argc, char **argv ) {
  double *t = NULL;
  int n = 0;
  int size = 0;
  int i;
  FILE *in = argc > 1 ? fopen( argv[1], "r" ) : stdin;
  
  t= malloc( INIT_SIZE * sizeof *t );
  if( t == NULL ) {
    fprintf( stderr, "Nie ma pamięci i koniec!\n" );
    return 1;
  }
  size = INIT_SIZE;

  while( fscanf( in, "%lf", &t[n] ) == 1 ) {
    n++;
    if( n == size ) {
      if( (t = resize( t, &size, n )) == NULL ) {
        free( t );
        fprintf( stderr, "Nie ma pamięci i koniec!\n" );
        return 1;
      }
    }
  }

  if( n % 2 == 1 ) {
    fprintf( stderr, "%s: Jakas kasza w strumieniu wejsciowym zamiast danych - nieparzysta liczba liczb.\n", argv[0] );
    return 1;
  }

  /*
  insort( t, n/2 );
  */

  qsort( t, n/2, 2*sizeof *t, cmpfun );

  for( i= 0; i < n; i += 2 )
    printf( "%g %g\n", t[i], t[i+1] );

  free( t );
  return 0;
}

W2 22.10.2013

#include <stdio.h>
#include <stdlib.h>

int main( int argc, char *argv[] ) {
        if( argc == 3 ) {
                /* robimy co trzeba */
                double u,i; /* napięcie i prąd */
                FILE *inp = fopen( argv[1], "r" );
                FILE *out = fopen( argv[2], "w" );
                if( inp == NULL ) {
                        fprintf( stderr, "%s: nie umiem otworzyć %s\n",
                                 argv[0], argv[1] );
                        return EXIT_FAILURE;
                }
                if( out == NULL ) {
                        fprintf( stderr, "%s: nie umiem otworzyć %s\n",
                                 argv[0], argv[2] );
                        return EXIT_FAILURE;
                }
                printf( "%s: Otworzyłem %s do czytania\n", argv[0], argv[1] );
                printf( "%s: Otworzyłem %s do pisania\n", argv[0], argv[2] );
                int n = 0;
                while( fscanf( inp, "%lf %lf", &u, &i ) == 2 ) {
                        fprintf( out, "%-15g %-15g %15g\n", u, i, u*i );
                        n++;
                }
                printf( "Przetworzyłem %d punkt%s.\n", n,
      /* końcówka wyrazu punkt zależy od liczby punktów:
         1 - punkt, x2, x3, x4 - punkty, 0 oraz x{5-0} - punktów */
                        ( n == 1 ? "" : ( n / 10 != 1 && n % 10 > 1 && n % 10 < 5 ? "y" : "ów" ) ) 
                      );
                fclose( inp );
                fclose( out );
                return EXIT_SUCCESS;
        } else {
                /* protestujemy */
                return EXIT_FAILURE;
        }
}

#include <stdio.h>
#include <math.h>
#include <string.h>

#ifndef M_PI
 #define M_PI 3.14159265
#endif

int main( int argc, char *argv[] ) {
  FILE *inp = argc > 1 ? fopen( argv[1], "r" ) : stdin;
  FILE *out = argc > 2 ? fopen( argv[2], "w" ) : stdout;

  int n = 100;         /* liczba kroków */
  double x0 = 0;       /* wartość początkowa */
  double x1 = 2*M_PI;  /* wartość końcowa */
  double dx;           /* krok */
  char fun[4] = "sin"; /* funkcja */
  int i;

  char buf[1024];

  printf( "M_PI=%g\n", M_PI );

  fgets( buf, 1024, inp );
  printf( "<%s>\n", buf );

  sscanf( buf, "%d %lf %lf %3s", &n, &x0, &x1, &fun[0] );
  printf( "Funkcja to \"%s\".\n", fun );

  dx = (x1 -x0) / (n-1);
  for( i= 0; i < n; i++ ) {
    double x = x0 + i*dx;
    fprintf( out, "%g %g\n", x, ( strcmp( fun, "sin" ) == 0 ? sin(x) : cos(x) ) );
  }

  fclose( inp );
  fclose( out );
  return 0;
}

W1 15.10.2013

/* Generator liczb losowych */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main( int argc, char **argv ) {
  int n = argc > 1 ? atoi(argv[1]) : 10;

  int i;

  if( argc > 2 )
    srand(time(NULL));

  for( i= 0; i < n; i++ ) {
    printf( "%g\n", (double) rand() / RAND_MAX );
  }

  return 0;
}

/* Genarator przykładowych danych - dwie kolumny liczb 
   pierwsza kolumna: liczby z zadanego zakresu
   druga kolumna: liczby losowe z zadanego zakresu
*/
#include <stdio.h>
#include <stdlib.h>

double drand( double min, double max ) {
        return min + (max-min)*rand()/RAND_MAX;
}

int
main ( int argc, char *argv[] )
{
        double start, stop, krok;
        double u;                       // rzędna
        int i,n;
        double min_i, max_i;

        start= argc > 1 ? atof( argv[1] ) : 0;
        stop=  argc > 2 ? atof( argv[2] ) : 1;
        krok=  argc > 3 ? atof( argv[3] ) : .01;
        min_i = argc > 4 ? atof( argv[4] ) : -1;
        max_i = argc > 5 ? atof( argv[5] ) : 1;

        srand( argc > 6 ? atoi( argv[6] ) : 0 );

        n= (stop-start)/krok+1;

  for (i= 0; i <= n; i++) {
                u= start + i * krok;
    printf ("%g\t%g\n", u, drand( min_i, max_i ) );
  }

  return 0;
}

#include <stdio.h>
#include <stdlib.h>

int main( int argc, char *argv[] ) {
        if( argc == 3 ) {
                /* robimy co trzeba */
                double u,i; /* napięcie i prąd */
                FILE *inp = fopen( argv[1], "r" );
                FILE *out = fopen( argv[2], "w" );
                if( inp == NULL ) {
                        fprintf( stderr, "%s: nie umiem otworzyć %s\n",
                                 argv[0], argv[1] );
                        return EXIT_FAILURE;
                }
                if( out == NULL ) {
                        fprintf( stderr, "%s: nie umiem otworzyć %s\n",
                                 argv[0], argv[2] );
                        return EXIT_FAILURE;
                }
                printf( "%s: Otworzyłem %s do czytania\n", argv[0], argv[1] );
                printf( "%s: Otworzyłem %s do pisania\n", argv[0], argv[2] );
                int n = 0;
                while( fscanf( inp, "%lf %lf", &u, &i ) == 2 ) {
                        fprintf( out, "%-15g %-15g %15g\n", u, i, u*i );
                        n++;
                }
                printf( "Przetworzyłem %d punkt%s.\n", n,
      /* końcówka wyrazu punkt zależy od liczby punktów:
         1 - punkt, x2, x3, x4 - punkty, 0 oraz x{5-0} - punktów */
                        ( n == 1 ? "" : ( n / 10 != 1 && n % 10 > 1 && n % 10 < 5 ? "y" : "ów" ) ) 
                      );
                fclose( inp );
                fclose( out );
                return EXIT_SUCCESS;
        } else {
                /* protestujemy */
                return EXIT_FAILURE;
        }
}

W0 8.10.2013

#include <stdio.h>

int main( int argc, char *argv[] )
{
        printf( "argv[0]=%s\n", argv[0] );

        if( argc > 1 ) {
                printf( "Cześć %s\n", argv[1] );
                return 0;
        } else {
                printf( "Cześć\n" );
                return 1;
        }
}

/* Sumator: dodaje liczby podane jako argumenty wywołania */

#include <stdio.h>
#include <stdlib.h>

double sum( double v[], int n )
{
        double s = v[--n];
        while( n-- > 0 )
                s += v[n];

        printf( "n=%d\n", n );

        /* wersje alternatywne
        double s = 0.0;
        #1
        int i;
        for( i= 0; i < n; i++ )
                s += v[i];

        #2
        i= 0;
        while( i < n ) {
                sum += v[i];
                i++;
        }
        */

        return s;
}

void pvct( double w[], int n ) 
{
        int i;
        printf( "[" );
        for( i= 0; i < n; i ++ )
                printf( " %g", w[i] );
        printf( " ]\n" );
}

void sortvct( double *w, int n ) {
        int i, j;
        for( i= 1; i < n; i++ ) {
                double tmp= w[i];
                for( j= i; j > 0 && w[j-1] > tmp; j-- )
                   w[j]= w[j-1];
                w[j]= tmp;      
        }
}

int main( int argc, char *argv[] ) {
        double w[1000];
        int m= 0;

        int i;

        for( i= 1; i < argc; i++ ) {
                w[m++]= atof( argv[i] );
        }

        pvct( w, m ); /* print vector */

        sortvct( w, m ); // sort vector incrementally

        pvct( w, m );

        printf( "suma=%g\n", sum( w, m ) );

        printf( "m=%d\n", m );

        return 0;
}

2015-09-23 06:44