[WikiDyd] [TitleIndex] [WordIndex

Języki i metodologia programowania I, laboratorium

Temat 3. Tablice wielowymiarowe

Tematyka: tablice wielowymiarowe

Wymagania wstępne: Kernighan i Ritchie: rozdziały: 5.1-5.8

Program szczegółowy:

Teksty programów:

   1 /* Trojkat Pascala: demonstracja tablic dwuwymiarowych
   2    jstar@iem.pw.edu.pl 2002.12.12
   3    Program dydaktyczny.
   4 
   5    Trojkat Pascala to macierz dwuwymiarowa, budowana wg.
   6    nastepujacego schematu:
   7     w n-tym wierszu jest n+1 elementow,
   8     skrajne elementy to jedynki,
   9     pozostale spelniaja zaleznosc: pt(i,j)= pt(i-1,j-1) + pt(i-1,j)
  10    ( czyli:
  11           1
  12          1 1
  13         1 2 1 
  14        1 3 3 1
  15       1 ..... 1
  16 
  17      W naszym programie przechowujemy ja w postaci macierzy:
  18       1
  19       1 1
  20       1 2 1
  21       1 3 3 1
  22       1 4 6 4 1 
  23       .....
  24      ktora, jak widac, moze miec rozna liczbe elementow w wierszu.
  25    )
  26 */
  27 
  28 #include <stdio.h>
  29 #include <stdlib.h>
  30 
  31 #define MAX_N  10
  32 
  33 /* Funkcje generuja trojkat Pascala o n wierszach
  34    w okreslonej przez drugi argument strukturze danych
  35 */
  36 
  37 /* Pierwsza wersja: statyczna tablica dwuwymiarowa
  38 */
  39 void pascaltriangle_s( int n, int pt[][MAX_N] ) {
  40    int i,j;
  41 
  42    if( n >= MAX_N )
  43       return;
  44 
  45    for( i= 0; i < n; i++ ) {
  46       pt[i][0]= 1;
  47       for( j= 1; j < i; j++ )
  48          pt[i][j]= pt[i-1][j-1] + pt[i-1][j];
  49       pt[i][i]= 1;
  50    }
  51 }
  52 
  53 /* Druga wersja: dynamiczna tablica dwuwymiarowa
  54 */
  55 void pascaltriangle_d( int n, int* pt[] ) {             
  56    int i,j;
  57 
  58    for( i= 0; i < n; i++ ) {       
  59       if( (pt[i]= malloc( sizeof(int)*(i+1) )) == NULL )
  60          return;
  61       pt[i][0]= 1;   
  62       for( j= 1; j < i; j++ )       
  63          pt[i][j]= pt[i-1][j-1] + pt[i-1][j];   
  64       pt[i][i]= 1;   
  65    }   
  66 }
  67 
  68 /* Trzecia wersja: wskaznik (wektor)
  69 */
  70 void pascaltriangle_v( int n, int** pt_p ) {
  71    int i,j;
  72    int *pt;
  73 
  74    /* alokacja pamieci: trojkat o glebokosci n ma (n+1)*n/2 elementow */
  75    if( (pt= malloc( sizeof *pt * (n+1)*n/2 )) == NULL )
  76       return;
  77 
  78    for( i= 0; i < n; i++ ) {
  79       *(pt+(i+1)*i/2)= 1;   /* lacznie w poprzednich wierszach jest (i+1)*i/2 elementow */
  80       for( j= 1; j < i; j++ )
  81          *(pt+(i+1)*i/2+j)= *(pt+(i-1)*i/2+j-1) + *(pt+(i-1)*i/2+j);
  82       *(pt+(i+1)*i/2+i)= 1;
  83    }
  84 /* wydruk kontrolny - aby go uaktywnic trzeba kompilowac
  85    program ze zdefiniowanym parametrem TEST:
  86    cc -DTEST pt.c
  87 */
  88 #ifdef TEST
  89    for( i= 0; i < (n+1)*n/2; i++ )
  90       fprintf( stderr, "%4i ", *(pt+i) );
  91    fprintf( stderr, "\n" );
  92 #endif
  93    *pt_p= pt;
  94 }
  95 
  96 /* Prawda, ze wypelnianie wektora nie wyglada zbyt czytelnie ?
  97    W funkcji main posluzymy sie do tego celu zdefiniowanym tu makrem PT:
  98 */
  99 
 100 #define PT(pt,i,j) ( *((pt)+((i)+1)*(i)/2+(j)) )  /* dostep do pt(i,j) */
 101 
 102 /* Makro PT tez jes nieczytelne, ale jego zastosowanie juz tak. */
 103 
 104 main( int argc, char **argv ) {
 105    int n= argc > 1 ? atoi( argv[1] ) : 10;
 106 
 107    int pts[MAX_N][MAX_N];
 108    int *ptd[10*MAX_N];
 109    int *ptp;
 110 
 111    int i,j;
 112 
 113 
 114    /* Tworzymy trojkaty przy pomocy roznych metod: 
 115 
 116       Prosze zwrocic uwage na rozne ograniczenia co do wartosci n
 117    */
 118 
 119    fprintf( stderr, "Tworze Trojkat Pascala w statycznej tablicy:\n" );
 120    if( n >= MAX_N ) {
 121       fprintf( stderr, "Zbyt duze n=%i, powinno byc <%i -- nie moge utworzyc TP\n", n, MAX_N );
 122    } else {
 123 
 124       pascaltriangle_s( n, pts );
 125 
 126       fprintf( stderr, "utworzony TP\n" );
 127       for( i= 0; i < n; i++ ) {
 128          for( j=0; j <= i; j++ )
 129             printf( "%4i ", pts[i][j] );
 130          printf( "\n" );
 131       }
 132       printf( "---\n" );
 133    }
 134 
 135    fprintf( stderr, "Tworze Trojkat Pascala w tablicy wskaznikow:\n" );
 136    if( n >= 10*MAX_N ) {
 137       fprintf( stderr, "Zbyt duze n=%i, powinno byc <%i -- nie moge utworzyc TP\n", n, MAX_N );
 138    } else {
 139 
 140      pascaltriangle_d( n, ptd );
 141 
 142      fprintf( stderr, "utworzony TP\n" );
 143      for( i= 0; i < n; i++ ) {
 144         for( j=n-1; j > i; j-- )
 145            printf( "   " );
 146         for( j=0; j <= i; j++ )
 147            printf( "%4i ", *(ptd[i]+j) );
 148         printf( "\n" );
 149       }
 150       printf( "---\n" );
 151    }
 152 
 153    fprintf( stderr, "Tworze Trojkat Pascala w wektorze:\n" );
 154    pascaltriangle_v( n, &ptp );
 155          
 156    fprintf( stderr, "utworzony TP\n" );
 157    for( i= 0; i < n; i++ ) {        
 158       for( j=0; j <= i; j++ )
 159          printf( "%4i ", PT( ptp, i,j ) );  /* makro PT pozwala dostac sie
 160                                                do (i,j) elementu trojkata Pascala
 161                                                wskazywanego przez ptp */
 162       printf( "\n" );
 163    }
 164    printf( "---\n" );
 165 
 166    return 0;
 167 }

Macierz 2D przechowywana w formie wektora wskaźników na kolumny.

Plik nagłówkowy:

   1 #ifndef _MATRIX_H
   2 #define _MATRIX_H
   3 
   4 typedef struct {
   5   double **p;  /* pointers to columns */
   6   int rn;
   7   int cn;
   8 } matrix_t;
   9 
  10 /** zrob (zaalokuj pamiec) macierz o zadanych wymiarach */
  11 matrix_t make_matrix( int rn, int cn );
  12 
  13 /** wstaw a[i][j] = x */
  14 int insert( matrix_t *a, int i, int j, double x );
  15 
  16 /** pobierz a[i][j] */
  17 double get( matrix_t *a, int i, int j );
  18 
  19 #include <stdio.h>
  20 
  21 /** wypisz macierz */
  22 void print( matrix_t *a, FILE *out );
  23 
  24 #endif
  25 

Implementacja:

   1 #include "matrix.h"
   2 #include <stdlib.h>
   3 
   4 matrix_t make_matrix( int rn, int cn )
   5 {
   6         matrix_t nm;
   7 
   8         int i;
   9 
  10         nm.p = malloc( cn * sizeof * nm.p );
  11 
  12         for( i= 0; i < cn; i++ )
  13                 nm.p[i] = malloc( rn * sizeof * nm.p[i] );
  14 
  15         nm.cn = cn;
  16         nm.rn = rn;
  17 
  18 
  19         return nm;
  20 }
  21 
  22 int insert( matrix_t *a, int i, int j, double x )
  23 {
  24   if( i >= 0 && i < (*a).rn && j >= 0 && j < (*a).cn ) {
  25     (*a).p[j][i] = x;
  26         return 0;
  27         } else {
  28                 return 1;
  29         }
  30 }
  31 
  32 double get( matrix_t *a, int i, int j )
  33 {
  34         return a->p[j][i];
  35 }
  36 
  37 void print( matrix_t *a, FILE *out )
  38 {
  39         int i,j;
  40         
  41         fprintf( out, "%d x %d [\n", a->rn, a->cn );
  42 
  43         for( i= 0; i < a->rn; i++ ) {
  44                 for( j= 0; j < a->cn; j++ )
  45                         fprintf( out, "\t%g", a->p[j][i] );
  46                 fprintf( out, "\n" );
  47         }
  48         fprintf( out, "]\n" );
  49 }

Test:

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include "matrix.h"
   4 
   5 int
   6 main( int argc, char **argv )
   7 {
   8   int n = argc > 1 ? atoi( argv[1] ) : 5;
   9   int m = argc > 2 ? atoi( argv[2] ) : 5;
  10 
  11   matrix_t a = make_matrix( n, m );
  12 
  13   int i, j;
  14 
  15   for( i= 0; i < n; i++ )
  16     for( j= 0; j < m; j++ )
  17       insert( &a, i, j, i*10.+j );
  18 
  19   print( &a, stdout );
  20 
  21   printf( "a[%d][%d]=%g\n", n/2, m/2, get( &a, n/2, m/2 ) );
  22 
  23   return 0;
  24 }

2015-09-23 06:43