Wstęp do programowania w języku C/Instrukcja for

Tablice

Dotychczas rozważaliśmy tylko zmiene, na których można było zapamiętywać tylko pojedyncze wartości z typu określonego podczas deklaracji zmiennej. Większość języków programowania umożliwia grupowanie zmiennych w większe struktury. W języku C mamy dwa rodzaje "grupowań": tablice (ang. arrays) i struktury ang. structures. Tablica jest strukturą danych zawierającą skończoną liczbę elementów tego samego typu. Żeby zadeklarować tablicę musimy podać jej rozmiar (długość) i typ elementów. Rozmiar może być dowolnym wyrażeniem typu całkowitego o argumentach będących stałymi.

Przykład:

int a[10]; /* Deklaracja 10-elementowej tablicy a */

W trakcie pracy nad programem rozmiar tablicy może ulegać zmianie. Dlatego bardziej elegancko i bezpiecznie jest zdefiniować długość tablicy jako stałą, np.

#define N 10

int a[N];

Do elementów tablicy odwołujemy się podając nazwę tablicy i indeks elementu w nawiasach kwadratowych. Elementy tablicy są w C zawsze indeksowane od 0.

Przykład:

a[0] = 1;
printf("%d\n", a[5]);
++a[i];

Przykład:

W N-elementowej tablicy liczb całkowitych należy znaleźć pozycje elementu o największej wartości.

/* int a[N] - dana tablica liczb calkowitych. */
int i, i_max, max;

i_max = 0;
max = a[0];
i = 1;
while (i < N) /*Nzm.: a[i_max]= max =
                MAX(a[0],\ldots,a[i-1]) & i <= N*/
{
  if (a[i] > max){
    i_max = i;
    max = a[i];
  }
  i++; /* Rownowazne i = i+1; */
}
/* a[i_max] = max = Max(a[0],...a[n-1]) */

Instrukcja for

Powyższą pętle while można zastąpić przez najsilniejszą z pętli języka C - pętlę for. Pętla for w języku C ma postać:

for (exp1; exp2; exp3) instrukcja

Poza nielicznymi wyjątkami jest ona równoważna następującej konstrukcji z pętlą while

expr1; while (expr2) { instrukcja; expr3; }

Przykład:

for (i = 10; i > 0; i--)
  printf("%d^2 = %d\n", i, i*i);

Oto kilka standardowych sposobów użycia instrukcji for.

1. "Liczenie" od 0 do n-1.

   for ( i = 0; i<n; i++ ) ...

2. "Liczenie" od 1 do n.

   for ( i = 1; i<=n; i++ ) ...

3. "Liczenie" od n-1 do 0.

   for ( i = n-1; i>=0; i-- ) ...

4. "Liczenie" od n do 1.

   for ( i = n; i>0; i-- ) ...

Każde z 3 wyrażeń w pętli for może być pominięte. Jeżeli brakuje expr2 to dozór pętli przyjmuje zawsze wartość 0. Zapiszmy teraz fragment programu liczenia maksimum z użyciem pętli for.

/* int a[N] - dana tablica liczb calkowitych. */
int i, i_max, max;

i_max = 0;
max = a[0];
for ( i = 1; i < N; i++)
/*Nzm.: a[i_max]=max=MAX(a[0],\ldots,a[i-1]) & i <= N*/
  if (a[i] > max){
    i_max = i;
    max = a[i];
  }
/* a[i_max] = max = Max(a[0],...a[n-1]) */

Operacje na tablicach

Oto kilka przykładów typowych operacji na tablicach.

1. Zerowanie tablicy.

   for ( i = 0; i<N; i++ ) a[i] = 0;

2. Czytanie danych do tablicy.

   for ( i = 0; i<N; i++ ) scanf("\%d", &a[i]);

3. Sumowanie elementów tablicy.

    sum = 0; for (i = 0; i<N; i++) sum += a[i];

Algorytmy sortowania

Wróćmy teraz do naszego programu znajdowania (pozycji) elementu maksymalnego. Można go użyć do sortowania elementów w tablicy. Najpierw znajdujemy element największy i zamieniamy go z ostatnim w tablicy. Następnie wśród pierwszych N-1 elementów znajdujemy element największy i zamieniamy go z przedostatnim w tablicy, itd. Taki algorytm sortowania nosi nazwę "Sortowania przez selekcję".

/* Sortowanie przez selekcje. */

#include <stdio.h>

#define N 10

main()
{
  int a[10]; /* Sortowana tablica. */
  int i, i_max, max, j;

  /* Wczytanie danych. */
  printf("Podaj %d liczb calkowitych", N);
  printf(" oddzielonych spacjami.\n");
  for ( i = 0; i < N; i++ )
    scanf("%d", &a[i]);
  printf("Ciag do posortowania:\n");
  for ( i = 0; i < N; i++ )
    printf("%d, ", a[i]);
  printf("\n");

  /* Wlasciwe sortowanie. */
  for ( j = N-1; j > 0; j-- ){
  /* Nzm.: a[0],\ldots,a[j]<=a[j+1]<=...<=a[N-1] */
    max = a[0];
    i_max = 0;
    for ( i = 1; i <= j; i++ )
    /* Nzm.: a[i_max]=max=MAX(a[0],\ldots,a[i-1]) */
      if ( a[i] > max ){
        max = a[i];
        i_max = i;
      }
    a[i_max] = a[j];
    a[j] = max;
  }

  /* Wypisanie wynikow. */
  printf("Ciąg posortowany:\n");
  for ( i = 0; i < N; i++ )
    printf("%d, ", a[i]);
  printf("\n");

  return 0;

}

Najlepszym algorytmem do sortowania krótkich ciągów jest "Sortowanie przez wstawianie". W tym algorytmie przeglądamy sortowaną tablicę od strony lewej do prawej sortując najpierw prefiks 1-elementowy, potem 2-elementowy, 3-elementowy, itd. Sortowanie prefiksu k-elementowego polega na przesunięciu wszystkich elementów większych od k-tego o jedną pozycję w prawo. W zwolnione miejsce wstawiamy element k-ty.

/* Sortowanie przez wstawianie. */

#include <stdio.h>

#define N 10

main()
{
  int a[10]; /* Sortowana tablica. */
  int i, j, v;

  /* Wczytanie danych. */
  printf("Podaj %d liczb calkowitych", N);
  printf(" oddzielonych spacjami.\n");
  for ( i = 0; i < N; i++ )
    scanf("%d", &a[i]);
  printf("Ciag do posortowania:\n");
  for ( i = 0; i < N; i++ )
    printf("%d, ", a[i]);
  printf("\n");

  /* Wlasciwe sortowanie. */
  for ( i = 1; i < N; i++ ){
  /* Nzm.: a[0]<=...<=a[i-1] */
    v = a[i];
    for ( j = i; (j > 0) && (a[j-1] > v) ; j-- )
    /* Nzm.: v < a[j+1],\ldots,a[i] */
      a[j] = a[j-1];
    a[j] = v;
  }

  /* Wypisanie wynikow. */
  printf("Ciag posortowany:\n");
  for ( i = 0; i < N; i++ )
    printf("%d, ", a[i]);
  printf("\n");

  return 0;

}