Warsztat

Odmiany typów podstawowych

Podsumujmy typy danych, które możesz napotkać w języku C:

char

Aby uniknąć niejednoznaczności, można stosować modyfikatory typu:

int

W świecie mikrokontrolerów 8-bitowych typ int najczęściej oznacza daną o długości 16 bitów. Zakres wynosi wtedy od -32768 do 32767 (-2¹⁵...2¹⁵-1). Jednakże może również oznaczać daną o długości 1 bajta, ponieważ to jest naturalna dana całkowita dla mikroprocesora 8-bitowego. Zwykle taki tryb wymaga włączenia w kompilatorze odpowiedniej opcji. Musisz to sobie sprawdzić w dokumentacji środowiska programowania, którego będziesz używał.

Typ int może występować z modyfikatorami (przy stosowaniu modyfikatorów nazwę int można pominąć):

float

double

long double

Definiowanie własnego typu

W języku C możesz definiować własne typy danych za pomocą słowa kluczowego typedef:

typedef nazwa_typu_istniejącego nowa_nazwa;

Na przykład: nie podoba ci się nazwa typu unsigned int. Nie ma sprawy:

/*
 Własne typy danych
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 26.10.2016
*/

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

// Definicja własnego typu
typedef unsigned int bezznakowe;

int main()
{
  // definiujemy zmienne z nową nazwą typu
  bezznakowe a,b,c;

  setlocale(LC_ALL,"");

  a = 1; b = a + 10; c = 12 * b;

  printf("%u %u %u\n", a, b, c);

  return 0;
}

W ten sposób da się pozmieniać nazwy wszystkich typów podstawowych, tylko po co? Lepszym zastosowaniem dla typedef jest tworzenie zupełnie nowych typów danych:

/*
 Własne typy danych
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 26.10.2016
*/

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

// Definicja własnego typu
typedef struct
{
  float re,im;
} complex;

int main()
{
  // definiujemy zmienne z nową nazwą typu
  complex a = {1,2};
  complex b = {2,2};
  complex c;

  setlocale(LC_ALL,"");

  c.re = a.re + b.re;
  c.im = a.im + b.im;

  printf("DODAWANIE LICZB ZESPOLONYCH\n"
         "---------------------------\n\n"
         "Liczba a = %f + j%f\n"
         "Liczba b = %f + j%f\n"
         "Suma a + b = %f + j%f\n",
         a.re,a.im,b.re,b.im,c.re,c.im);

  return 0;
}

W programie utworzyliśmy bezimienną strukturę i przypisaliśmy jej typ do nazwy nowego typu danych complex (liczba zespolona). Struktura zawiera dwa pola: re – część rzeczywista liczby zespolonej (ang. real part) i im – część urojona (ang. imaginary part). Wg nowego typu complex zdefiniowaliśmy 3 zmienne: a, b i c. Dwóm pierwszym zmiennym nadaliśmy wartości początkowe: a = 1 + j2 i b = 2 + j2. Następnie obliczyliśmy sumę liczb a i b, umieszczając wynik w zmiennej c.

Jeśli nie wiesz, czym są liczby zespolone, to dowiesz się tego w  tym rozdziale.

Typ wyliczeniowy

Bardzo przydatny jest tzw. typ wyliczeniowy (an. enumerated type). Tworzymy go za pomocą słówka kluczowego enum w sposób następujący:

enum nazwa_typu {nazwa_1, nazwa_2,...,nazwa_n};

Jak to działa? Weźmy prosty przykład:

enum weekday {sunday, monday, tuesday, wednesday, thursday, friday, saturday};

W efekcie tej definicji powstanie nowy typ danych o nazwie enum weekday (dzień tygodnia). Oprócz nazwy typu powstaje zbiór stałych o nazwach dni tygodnia. Stałe te otrzymują kolejne wartości:

Teraz na podstawie nowego typu możesz definiować zmienne i nadawać im wartości określone przez stałe:

enum weekday a,b,c;
...
a = tuesday;
...
if(b == c && b == friday) ...
...

Czy naprawdę potrzebujemy typ enum? Oczywiście, że nie. Bez niego moglibyśmy się obejść, lecz dobrze go mieć, bo jest czasem wygodny. Nasze stałe moglibyśmy zdefiniować następująco:

#define sunday 0
#define monday 1
#define tuesday 2
#define wednesday 3
#define thursday 4
#define friday 5
#define saturday 6 ...
int a,b,c;
...
a = wednesday;
...
if(b == c && b == saturday) ...
...

A teraz wyobraź sobie, że zrobiłeś drobną pomyłkę:

#define sunday 0
#define monday 1
#define tuesday 2
#define wednesday 3
#define thursday 4
#define friday 5
#define saturday 5 ...
int a,b,c;
...
a = wednesday;
...
if(b == c && b == saturday) ...
...

I już program staje się wadliwy. Typ enum nadaje stałym kolejne wartości automatycznie. Dodatkowo zadanie wykonywane jest przez kompilator, a nie przez preprocesor. Zatem można już w trakcie kompilacji wyłapać różne błędy.

Wartości stałych w typie enum możesz też sam okreslić:

enum weekday {sunday,
              monday,
              tuesday = 6,
              wednesday,
              thursday,
              friday,
              saturday};

Jeśli na liście stałych nadasz jednej z nich konkretną wartość, to wszystkie stałe, które na liście występują później, otrzymają wartości kolejne od nadanej. W tym przypadku otrzymasz:

W krańcowym przypadku możesz sam określić wartość każdej stałej:

enum weekday {sunday = 7,
              monday = 2,
              tuesday = 6,
              wednesday = 5,
              thursday = 99,
              friday = 12,
              saturday = 87};

Zmienna zbudowana na podstawie zdefiniowanego typu wyliczeniowego jest zwykle typu int. Jednak nie licz na to zbytnio, ponieważ w definicji typu wyliczeniowego określono jedynie, że zmienna wynikowa będzie takiego typu, który pomieści wszystkie wartości stałych.

/*
 Typ wyliczeniowy
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 30.10.2016
*/

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

enum boolean {False,True};

int main()
{
  setlocale(LC_ALL,"");

  printf("%d\n",sizeof(enum boolean));

  return 0;
}

Również kompilator nie kontroluje wartości nadawanym zmiennym typu enum:

/*
 Typ wyliczeniowy
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 30.10.2016
*/

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

enum boolean {False,True};

int main()
{
  enum boolean a,b,c;

  setlocale(LC_ALL,"");

  a = False; // OK
  b = True;  // OK
  c = 3;     // ??? też OK!
  printf("%d %d %d\n", a, b, c);

  return 0;
}

Stała jest wartością, która nie zmienia się w trakcie wykonywania programu. Stałe możemy tworzyć na kilka sposobów:

#define nazwa wartość

Jest to dyrektywa preprocesora, która przyporządkowuje nazwie pewną stałą wartość. Dzięki niej możemy łatwo zdefiniować w programie wartości logiczne:

#define FALSE 0
#define TRUE 1

Od tego momentu każde wystąpienie słowa FALSE będzie równoważne z 0, a każde wystąpienie słowa TRUE będzie równoważne z 1. Podmiana następuje przed kompilacją pliku źródłowego.

const typ zmienna = wartość;

W ten sposób tworzymy zmienną, której wartości nie można w programie zmieniać. Zaletą w stosunku do poprzedniego sposobu jest to, iż stałą tworzy kompilator, zatem może wyłapać on różne błędy.

Sens takiej konstrukcji dla prostej zmiennej może nie być zbyt duży. Lecz wyobraź sobie, że chcemy w programie zainicjować np. tablicę struktur (czasem się z takiego tworu korzysta):

/*
 Stałe
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 30.10.2016
*/

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

struct triplex
{
  float a,b,c;
};

int main()
{
  const struct triplex cs = {3.1415,2.7728,1.4312};
  struct triplex t[10];
  int i;

  setlocale(LC_ALL,"");

  for(i = 0; i < 10; i++) t[i] = cs;
  t[5].a = 6.2833;
  t[5].b = 3.0;
  t[5].c = 0.22;
  for(i = 0; i < 10; i++)
    printf("Struktura nr %d\n"
           "a = %6.4f b = %6.4f c = %6.4f\n\n",
           i, t[i].a, t[i].b, t[i].c);

 return 0;
}

enum {nazwa, nazwa,...};
enum {nazwa=wartość, nazwa=wartość, ...};

Typ wyliczeniowy tworzy automatycznie zestaw stałych typu całkowitego. Stałym można przypisywać kolejne wartości lub wartości wybrane. Utworzone w ten sposób stałe można wykorzystać do dowolnego celu:

/*
 Stałe
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 30.10.2016
*/

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

int main()
{
  enum {up,down,left,right};
  int d;

  setlocale(LC_ALL,"");

  d = up+down+left+right;
  printf("%d\n\n",d);

  return 0;
}

Literały

Literał jest zapisem liczby. Np. 15 jest literałem liczby dziesiętnej. Ponieważ w języku C mogą występować różne typy danych, istnieją dla nich odpowiednie literały:

int

• dziesiętnym, zapis normalny, np. 1267, -12844
• ósemkowym, zapis poprzedzony cyfrą 0, np. 033, -0777
• szesnastkowym, zapis poprzedzony przedrostkiem 0x lub 0X, np. 0xff, -0XAF3
• dwójkowym, zapis poprzedzony przedrostkiem 0b lub 0B, np. 0b11101, -0B101

unsigned int

long int

unsigned long int

/*
 Stałe
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 30.10.2016
*/

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

int main( )
{
  unsigned long long a;

  setlocale(LC_ALL,"");

  a = 30000000000ul;
  printf("%llu\n\n", a);

  return 0;
}

Wyrażenia stałe

Wyrażenie jest stałe (ang. constant expression), jeśli jego wartość da się policzyć w czasie kompilacji. Tego typu wyrażenia są przez kompilator obliczane i zamieniane na stałą o wartości wyrażenia. Dzięki temu mikroprocesor nie musi obliczać wartości takiego wyrażenia podczas działania programu. Przyspiesza to wykonywanie programu oraz skraca jego kod.

W świecie mikrokontrolerów wyrażenia stałe często używane są do ustawiania bitów w rejestrach.

Na przykład instrukcja:

r = (1 << 5) | (1 << 3) | (1 << 2);

jest równoważna instrukcji:

r = 0b101100;

Pierwszy sposób stosuje się dla poprawienia czytelności operacji.

Najpierw wyjaśnijmy sobie pojęcie liczby losowej (ang. random number) i jej zastosowania.

Liczba losowa to taka, której zakres znamy (np. od 1 do 6 dla oczek wyrzucanych na kostce do gry), lecz nie potrafimy przewidzieć konkretnej wartości, ponieważ jest losowa (jak wynik rzutu kostką – taką niezafałszowaną). Mówimy, że dana wartość pojawia się z pewnym prawdopodobieństwem. Prawdopodobieństwo (a właściwie rachunek prawdopodobieństwa) jest terminem matematycznym pochodzących z teorii gier, która, co ciekawe, wcale obecnie nie służy tylko i wyłącznie do grania w gry, a nawet jest jedną z najważniejszych teorii matematycznych. Rachunek prawdopodobieństwa jest używany przez poważne teorie fizyczne (np. teorię kwantową), ekonomiczne i socjologiczne.

Nie wnikając zbyt głęboko w aspekty matematyczne, określmy prawdopodobieństwo jako liczbę P z zakresu od 0 do 1. Prawdopodobieństwa wiążą się z konkretnymi zdarzeniami:

• wypadnięcie na kostce sześciu oczek,
• otrzymanie w pokerze 4 asów
• wyrzucenie orzełka monetą
• oberwanie meteorytem między oczy podczas przechadzki w parku.

Prawdopodobieństwo P równe 0 oznacza zdarzenie niemożliwe, czyli takie, które w żaden sposób nie może zajść.

Prawdopodobieństwo P równe 1 oznacza zdarzenie pewne, czyli takie, które wystąpi na pewno.

Jeśli weźmiemy zbiór n zdarzeń (np. 6 zdarzeń wyrzucenia kostką od jednego do 6 oczek) i stanowią one zbiór kompletny (tzn. w danym doświadczeniu nie może wystąpić żadne inne zdarzenie spoza tego zbioru), to suma ich prawdopodobieństw jest równa 1, czyli pewnikiem jest, że zawsze któreś z tych zdarzeń na pewno wystąpi.

Na przykład, przy rzucie kostką mamy 6 możliwych zdarzeń (pomijamy zdarzenia typu: kostkę złapał kot i uciekł z nią):

1. Wypadło 1 oczko
2. Wypadły 2 oczka
3. Wypadły 3 oczka
4. Wypadły 4 oczka
5. Wypadło 5 oczek
6. Wypadło 6 oczek

Każde z tych zdarzeń jest jednakowo prawdopodobne i zakładamy, że zawsze któreś z nich wystąpi. Mamy zatem:

Wynika z tego, że każde ze zdarzeń wypadnięcia określonej liczby oczek posiada prawdopodobieństwo ¹/₆. Nie rozum tego w ten sposób, że co 6 rzutów zawsze wypadnie ci 6 oczek. Tak dobrze nie ma. Jeśli jednak wykonasz 6 milionów rzutów dobrą (tzn nieoszukaną) kostką, to powinno ci wypaść w tej liczbie około 1 miliona szóstek (im więcej rzutów tym liczba szóstek będzie bardziej zbliżona do ¹/₆ liczby wszystkich rzutów).

Jeśli każde z możliwych zdarzeń ma takie samo prawdopodobieństwo wystąpienia, to mówimy, że rozkład tych prawdopodobieństw jest równomierny.

Jak zauważyłeś, liczby losowe stosowane mogą być do symulacji wyników losowych. Jednak jest z nimi jeden kłopot: nie da się ich tworzyć programowo. Powodem jest to, iż liczba losowa nie jest wynikiem żadnego wyrażenia, w którym nie występują inne liczby losowe. I dostajemy błędne koło.

Jednym ze sposobów tworzenia liczb losowych w mikrokontrolerach jest wykorzystanie tzw. liczników/timerów (są to układy wewnątrz mikrokontrolera, które zliczają impulsy pochodzące z różnych źródeł) oraz współpracy z użytkownikiem. Człowiek dla mikrokontrolera jest bardzo powolną istotą i, co ważniejsze, nieprzewidywalną. Jeśli licznik zlicza impulsy o bardzo dużej częstotliwości, to jego stan zmienia się miliony razy na sekundę. Gdy użytkownik naciśnie np. jakiś przycisk, to mikrokontroler może w tym momencie odczytać stan licznika i otrzymać w ten sposób dobrą liczbę losową (nie wiadomo, kiedy użytkownikowi przyjdzie ochota nacisnąć przycisk, dlatego stan licznika jest nieprzewidywalny, a zatem losowy).

Jednak co zrobić, jeśli nie mamy wolnego licznika, a musimy generować liczby pseudolosowe? Z pomocą przychodzi tzw. generator liczb pseudolosowych.

Generator liczb pseudolosowych (ang. pseudorandom number generator) jest funkcją, która zwraca wartości wyglądające jak liczby losowe (to jak to właśnie łaciński przedrostek pseudo = jakby), lecz nimi nie będące. Jak to rozumieć? Otóż chodzi o to, że taka funkcja tworzy ciąg liczb, które można uznać za losowe, ponieważ na pierwszy rzut oka nie widać pomiędzy nimi jakiś zależności. W rzeczywistości taka zależność jest i jeśli znamy jedną liczbę pseudolosową, to możemy sobie wygenerować wszystkie następne. Co więcej, liczby pseudolosowe tworzą ciąg wartości, który powtarza się po pewnym okresie (np. po wygenerowaniu 4 miliardów liczb, otrzymujemy od nowa ten sam ciąg).

Jeśli cię zainteresował ten temat, to odsyłam do obszernego artykułu o generatorach liczb pseudolosowych, który znajduje się w naszym serwisie.

Wróćmy na ziemię. W języku C masz dostęp do generatora liczb pseudolosowych za pomocą dwóch funkcji:

srand(ziarno);

Funkcja srand( ) inicjuje generator liczb pseudolosowych. Jeśli mikrokontroler jest wyposażony w zegar czasu rzeczywistego, który działa na zasilaniu bateryjnym i mierzy czas niezależnie od wykonującego się programu, to jako ziarna można użyć wartości odczytanej z zegara jako liczby typu int. Funkcji srand( ) używamy w programie tylko jeden raz na samym początku.

Jeśli mikrokontroler nie posiada takiego zegara, to można wykorzystać pośrednio pamięć EPROM, która jest dostępna praktycznie w każdym mikrokontrolerze. Pamięć EPROM pamięta dane nawet po wyłączeniu zasilania. W pamięci tej tworzymy prosty licznik, którego zawartość zwiększamy o 1 (lub o inną wartość) przy każdym uruchomieniu programu. Następnie stan tego licznika wykorzystujemy jako ziarno dla funkcji srand( ). Zagwarantuje to, że przy każdym uruchomieniu otrzymamy inny ciąg liczb pseudolosowych.

rand();

Funkcja jest bezargumentowa. Każde wywołanie daje liczbę pseudolosową z zakresu od 0 do 32767, czyli 15 najstarszych bitów wygenerowanej liczby pseudolosowej. Dlaczego tak dziwnie? Chodzi o rozkład. Stwierdzono, że te 15 bitów daje lepszą równomierność generowanych liczb niż inne bity liczby pseudolosowej tworzonej w generatorze.

Obie funkcje są zdefiniowane w pliku nagłówkowym stdlib.h.

Uruchom program:

/*
 Liczby pseudolosowe
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 31.10.2016
*/

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

#define MAXC 78

int main()
{
  int i;

  setlocale(LC_ALL,"");

  srand((int)time(NULL)); // inicjujemy generator LCG
  for(i = 0; i < 40; i++) printf("%d\n",rand());

  return 0;
}

W programie użyto nowej funkcji time( ), która odczytuje czas. Funkcja ta zwykle nie jest dostępna we wszystkich mikrokontrolerach, ponieważ zależy od konkretnej konfiguracji sprzętowej. Funkcja time( ) zwraca liczbę sekund, które upłynęły od północy pierwszego stycznia 1970 roku (całkiem sporo). Jej wartość zmienia się co jedną sekundę. Parametrem jest wskaźnik miejsca w pamięci, w którym zostanie utworzona struktura opisująca czas. Jeśli w parametrze przekażemy wskaźnik pusty (NULL), to nic nie będzie tworzone, ponieważ NULL nie wskazuje żadnego obiektu. Tutaj wykorzystujemy time( ) do zainicjowania generatora pseudolosowego. Dzięki temu, przy każdym uruchomieniu programu otrzymamy inny ciąg liczb pseudolosowych. W ramach ćwiczenia spróbuj usunąć z programu wywołanie srand( ) i sprawdź co się stanie (program uruchom kilkakrotnie).

Funkcja rand( ) generuje liczby z zakresu od 0 do 32767 (0...2¹⁵-1). Co zrobić, jeśli potrzebujesz innego zakresu, np. od a do b? Aby z a otrzymać b należy do a dodać liczbę (b - a). Zatem liczby otrzymywane z rand( ) musisz zredukować do zakresu od 0 do  (b - a). Pomoże ci w tym operacja modulo (%), czyli reszta z dzielenia. Aby otrzymać resztę z dzielenia w zakresie od 0 do (b - a) należy wynik z rand( ) podzielić przez (b - a) + 1. Otrzymujemy ostateczny wzór:

a + rand( ) % (b - a + 1)

Na przykład, chcesz generować wyniki rzutów kostką. Wyrażenie pseudolosowe o wartościach od 1 do 6 jest następujące (a = 1, b = 6):

Uruchom program:

/*
 Liczby pseudolosowe
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 31.10.2016
*/

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

#define MAXC 78

int main()
{
  int i;

  setlocale(LC_ALL,"");

  srand((int)time(NULL)); // inicjujemy generator LCG
  for(i = 1; i <= 40; i++)
  printf("Rzut nr %2d, liczba oczek %d\n", i, 1+rand()%6);

  return 0;
}

Kolejny program "rzuca" kostką 6 milionów razy, i sprawdza, czy wypadło około miliona każdej z możliwych liczby oczek.

/*
 Liczby pseudolosowe
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 31.10.2016
*/

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

#define MAXC 78

int main()
{
  int t[] = {0,0,0,0,0,0},i;

  setlocale(LC_ALL,"");

  srand((int)time(NULL)); // inicjujemy generator LCG
  for(i = 0; i < 6000000; i++) t[rand()%6]++;
  for(i = 0; i < 6; i++)
  printf("%d: %7d\n", i + 1, t[i]);

  return 0;
}

Liczby pseudolosowe często stosujemy do mieszania zawartości tablic. Zadanie to rozwiązujemy następująco:

Uruchom program:

/*
 Liczby pseudolosowe
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 31.10.2016
*/

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

int main()
{
  int t[] = {0,1,2,3,4,5,6,7,8,9},i,i1,i2,x;

  setlocale(LC_ALL,"");

  srand((int)time(NULL)); // inicjujemy generator LCG
  printf("Przed: ");
  for(i = 0; i < 10; i++) printf("%2d",t[i]);

  // mieszamy
  for(i = 0; i < 30; i++)
  {
    i1 = rand() % 10; // losujemy indeksy
    i2 = rand() % 10;
    x  = t[i1]; t[i1] = t[i2]; t[i2] = x;
  }
  
  printf("\n\nPo : ");
  for(i = 0; i < 10; i++) printf("%2d",t[i]);
  printf("\n\n");

  return 0;
}

Za pomocą mieszania możesz napisać prosty program losujący liczby Multilotka (20 z 80).

/*
 Liczby pseudolosowe
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 31.10.2016
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <locale.h>

int main()
{
  char m[80],r[10],x;
  int i,j,k,i1,i2;

  setlocale(LC_ALL,"");

  // inicjujemy generator LCG
  srand((int)time(NULL));

  // Wypełniamy tablicę bil m[]
  for(i = 0; i < 80; i++) m[i] = i + 1;

  for(k = 1; k <= 10; k++)
  {
      printf("Lowanie Multilotka nr %d\n",k);
    // mieszamy bile
    for(i = 0; i < 240; i++)
    {
      // losujemy indeksy
      i1 = rand() % 80;
      i2 = rand() % 80;

      // zamieniamy bile
      x = m[i1]; m[i1] = m[i2]; m[i2] = x;
    }
    
    // losujemy 20 pierwszych bil
    memcpy(r, m, 10);

    // sortujemy wylosowane bile rosnąco
    for(i = 8; i >= 0; i--)
    {
      x = r[i];
      for(j = i + 1; j < 10; j++)
        if(x <= r[j]) break;
        else r[j - 1] = r[j];
      r[j - 1] = x;
    }

    printf("Wyniki:");
    for(i = 0; i < 10; i++) printf(" %02d", r[i]);
    printf("\n\n");
  }
  
  return 0;
}

Specyfikacja %02d w tekście formatującym funkcji printf( ) oznacza format dziesiętny w polu o długości dwóch znaków z zerami wiodącymi.

Inne ciekawe zastosowanie liczb pseudolosowych wiąże się z szyfrowaniem tekstu. W czasie II Wojny Światowej Kwatera Główna Führera stosowała specjalną maszynę szyfrującą o nazwie Ultra.

Zasada działania tej maszyny polegała na tym, iż kody znaków były mieszane z ciągiem liczb pseudolosowych, które generowała maszyna na podstawie wprowadzonego wcześniej klucza oraz innych ustawień. My możemy postąpić podobnie: liczby pseudolosowe będzie generował generator pseudolosowy języka C. Kluczem natomiast będzie ziarno dla tego generatora. Jak napisaliśmy wcześniej, jeśli zainicjujemy generator takim samym ziarnem pseudolosowym, to wygeneruje on identyczny ciąg liczb pseudolosowych. Aby się o tym przekonać, uruchom poniższy program:

/*
 Liczby pseudolosowe
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 31.10.2016
*/

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

int main()
{
  int t = (int)time(NULL); // zapamietujemy czas
  int i,j;

  setlocale(LC_ALL,"");

  for(i = 1; i < 10; i++)
  {
    srand(t); // ustawiamy generator LCG
    for(j = 0; j < 19; j ++) printf(" %03d", rand() % 1000);
    printf("\n\n");
  }
  
  return 0;
}

Program generuje 10 ciągów liczb pseudolosowych. Ponieważ przed generacją każdego ciągu inicjujemy generator pseudolosowy tym samym ziarnem, to generuje on za każdym razem taki sam ciąg liczb.

Na tym fakcie oprzemy algorytm szyfrujący/deszyfrujacy. Kluczem będzie wartość ziarna pseudolosowego jako liczba całkowita. Drugi fakt, to działanie sumy symetrycznej. Jeśli zastosujemy tę operację dwukrotnie z tym samym argumentem, to wynik wróci do postaci wyjściowej:

Zatem szyfrowanie lub deszyfrowanie polega na operacji różnicy symetrycznej kodu ASCII znaku z liczbą pseudolosową z generatora. Uruchom poniższy program:

/*
 Liczby pseudolosowe
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 31.10.2016
*/

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

int main()
{
  int key,i;
  char t[80];

  setlocale(LC_ALL,"");

  printf("Wpisz klucz: "); scanf("%d", &key);
  printf("Wpisz tekst (do 79 liter):\n\n");
  gets(t); // to usuwa znak \n z wejścia
  gets(t); // to odczytuje właściwy wiersz

  // inicjujemy generator pseudolosowy
  srand(key);

  // szyfrujemy lub deszyfrujemy
  for(i = 0; t[i]; i++) t[i] ^= rand() % 32;

  // wyświetlamy wynik:
  printf("\n%s\n\n", t);

  return 0;
}

W programie użyto dwukrotnie funkcji gets( ). Jest to konieczne, ponieważ funkcja scanf( ) nie usuwa ze strumienia wejściowego znaku \n, który tam powstaje po naciśnięciu klawisza Enter, gdy użytkownik wprowadzi klucz. Z tego powodu pierwsza funkcja gets( ) odczyta pusty wiersz. Dopiero druga funkcja gets( ) odczyta właściwy wiersz do szyfrowania lub deszyfrowania. Oto wynik działania programu:

Jak widzisz, cała potężna maszyna Ultra sprowadza się we współczesnym świecie do kilku linijek kodu w języku C.

Zwykle zmienna oznacza daną umieszczoną w pamięci komputera. Daną tą inicjuje i zmienia mikroprocesor, gdy życzy sobie tego program. Czasem taką często używaną zmienną mikroprocesor umieszcza w swojej pamięci podręcznej, aby mieć do niej szybki dostęp. Wtedy przy odwołaniu do zmiennej nie sięga on do pamięci, w której zmienna się znajduje, tylko do swojej szybkiej pamięci podręcznej, gdzie ją tymczasowo przechowuje, Zwykle jest to działanie pożądane. Jednak nie zawsze. W mikrokontrolerach w obszarze pamięci znajdują się tzw. rejestry. Zapis lub odczyt danych z tych rejestrów może wywoływać różne działania. Niektóre z tych rejestrów odzwierciedlają poziomy logiczne, które panują na wyprowadzeniach mikrokontrolera lub stan operacji wykonywanych przez urządzenia we/wy, w które są wyposażane mikrokontrolery. Poziomy te mogą z kolei ustawiać urządzenia zewnętrzne, z którymi w danym układzie współpracuje mikrokontroler. Taki rejestr może zmieniać sam swoją zawartość, bez udziału programu. Dodatkowo zmiana ta może się odbywać w dowolnym momencie. Z tego powodu mikrokontroler nie powinien buforować zawartości takiej zmiennej w swojej pamięci podręcznej. Każdy dostęp do zmiennej tego typu musi być wykonany na rzeczywistej komórce pamięci, inaczej mikrokontroler mógłby "przegapić" zmiany wywołane przez urządzenia wewnętrzne lub zewnętrzne.

Na szczęście język C przewiduje takie sytuacje i każdą zmienną możesz opatrzyć słówkiem angielskim słówkiem volatile (ulotny):

volatile typ zmienna;
typ volatile zmienna;

Od tego momentu mikroprocesor będzie zawsze odwoływał się bezpośrednio do zmiennej w pamięci. Nawet, gdy włączysz optymalizacje kodu.

Ze zmiennymi ulotnymi spotkasz się przy programowaniu tzw. przerwań (ang. interrupts).

Język C posiada instrukcję goto, która może wykonać skok w inne miejsce kodu w obrębie funkcji. Najczęściej wykorzystuje się ją przy wychodzeniu z zagnieżdżonych pętli. Najlepszym sposobem używania instrukcji goto jest nieużywanie jej wcale! Jest to opinia doświadczonych programistów. Język C jest językiem strukturalnym, a goto burzy tę cechę. Programy pisane z goto bardzo szybko stają się nieczytelne i co gorsza nieprzewidywalne w działaniu (kod nadużywający goto zamiast rozwiązań strukturalnych nosi nazwę kodu spagetti). Ale skoro taka instrukcja jest, podamy przynajmniej, jak należy ją poprawnie używać.

Składnia jest następująca:

goto etykieta;

Etykieta jest nazwą, którą umieszczamy w programie w miejscu, do którego należy wykonać skok. Za nazwą etykiety należy wpisać dwukropek. Etykieta musi znajdować się w tej samej funkcji, w której umieszczono rozkaz goto. Nie wolno wykonywać skoków pomiędzy różnymi funkcjami.

/*
 Skoki
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 4.11.2016
*/

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

int main()
{
  int a;

  setlocale(LC_ALL,"");

jeszcze_raz: // tu jest miejsce docelowe skoku

  printf("Wpisz liczbe od 1 do 9: ");
  scanf("%d", &a);
  if(a < 1 || a > 9) goto jeszcze_raz; // skok
  printf("Dziekujemy, wpisana liczba to %d\n", a);

  return 0;
}

To samo da się otrzymać bez używania goto:

/*
 Skoki
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 4.11.2016
*/

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

int main()
{
  int a;

  setlocale(LC_ALL,"");

  while(1)
  {
    printf("Wpisz liczbe od 1 do 9: ");
    scanf("%d", &a);
    if(a < 1 || a > 9) continue;
    printf("Dziekujemy, wpisana liczba to %d\n", a);
    break;
  }

  return 0;
}

Wskaźnik jest po prostu adresem obiektu w pamięci, o czym pisaliśmy już wcześniej. Zwykle wskaźnik wskazuje dane, np. liczbę całkowitą, zmiennoprzecinkową, strukturę, tablicę, itp.

Funkcja również jest obiektem w pamięci i posiada swój adres. Pod tym adresem umieszczony jest kod funkcji, czyli ciąg rozkazów dla mikroprocesora, które ten wykonuje, gdy program daną funkcję wywoła. Z tego powodu nic nie stoi na przeszkodzie, aby istniały również wskaźniki do funkcji. Jednak musisz pamiętać, że wskaźnik w języku C to nie tylko sam adres (taki wskaźnik też istnieje: void *). To również typ wskazywanego obiektu. Wskaźnik do danej całkowitej nie jest tym samym co wskaźnik do danej zmiennoprzecinkowej. Chodzi o to, iż kompilator musi wiedzieć, jak ma interpretować daną wskazywaną przez wskaźnik. Również arytmetyka wskaźników odwzorowuję tę cechę: np. dodanie do wskaźnika liczby 1 oznacza przesunięcie jego adresu o tyle, ile wynosi rozmiar wskazywanego obiektu. Jest to bardzo przydatne przy odwoływaniu się do tablic, w których elementy są umieszczone w pamięci jeden obok drugiego.

Aby użyć danej funkcji, kompilator musi wiedzieć o niej kilka rzeczy:

• Liczbę argumentów
• Typy poszczególnych argumentów
• Typ zwracanego wyniku

Definicja wskaźnika do funkcji (ang. function pointer) wygląda następująco:

typ_wyniku (* wskaźnik)(typy_argumentów);

Na przykład, poniższa definicja:

float (*calc)(int *, float);

Definiuje wskaźnik o nazwie calc, który będzie wskazywał funkcję zwracającą w wyniku daną typu float i posiadającą dwa parametry: pierwszy typu wskaźnik do danej całkowitej int; drugi typu float.

Wskaźnik po utworzeniu należy odpowiednio zainicjować. Do tego celu wykorzystujemy znany nam już operator adresu & oraz nazwę funkcji, którą wskaźnik ma wskazywać.

wskaźnik = &funkcja;

Wywołanie funkcji, którą wskazuje wskaźnik wygląda następująco:

wskaźnik(argumenty);

lub

(* wskaźnik)(argumenty);

Uruchom poniższy program (przykład nieco naciągany, ale pokazujący ideę stosowania wskaźników do funkcji):

/*
 Wskaźniki do funkcji
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 5.11.2016
*/

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

// Zmienna globalna
void (* func)(int);

// Prototypy funkcji
void f1(int);
void f2(int);

// Dwie funkcje, które będzie wskazywał func
void f1(int a)
{
  printf("Jestem w funkcji f1( ), a = %d\n", a);
  func = &f2;
}

void f2(int a)
{
  printf("Jestem w funkcji f2( ), a = %d\n", a);
  func = &f1;
}

int main()
{
  int i;

  setlocale(LC_ALL,"");

  func = &f1;
  for(i = 1; i < 10; i++) func(i);

  return 0;
}

Program działa następująco:

Wyszukiwanie binarne

Wskaźniki do funkcji są wykorzystywane przez kilka funkcji bibliotecznych. Jedna z nich realizuje tzw. wyszukiwanie binarne (ang. binary search). Funkcję tę wykorzystuje się na większych mikrokontrolerach, które posiadają dużo pamięci RAM.

Zwykłe wyszukiwanie liniowe (ang. linear search) polega na przeglądaniu kolejnych elementów tablicy i porównywaniu ich z wartością poszukiwaną. Jeśli zostanie znaleziona, to zatrzymujemy dalsze przeszukiwanie tablicy i zwracamy wskaźnik elementu, którego wartość jest równa poszukiwanej. Jeśli natomiast osiągniemy ostatni element element tablicy i poszukiwanej wartości w tablicy nie znajdziemy, to zwracamy wskaźnik pusty NULL.

Dla dużych tablic czas wyszukiwania elementu jest statystycznie liniowo proporcjonalny do ilości elementów n, dlatego algorytm ten nosi nazwę wyszukiwania liniowego. O takim algorytmie mówimy, że ma liniową złożoność obliczeniową. Jeśli liczba elementów tablicy wzrośnie np. 256 razy, to średni czas wyszukiwania elementu również wzrośnie około 256 razy.

Okazuje się, że można znacznie przyspieszyć czas wyszukiwania elementu, jeśli tablica będzie posortowana np. rosnąco. Postępujemy wtedy następująco:

Zakres poszukiwań definiują dwa indeksy: i_p (indeks początku) i i_k (indeks końca):

Komórki tablicy od t[i_p] do t[i_k] nazwijmy partycją. Partycja będzie zawierała komórki, jeśli i_p≤ i_k. Jeśli ten warunek nie jest spełniony, mamy pustą partycję, wtedy kończymy i zwracamy adres pusty NULL.

Wyznaczamy komórkę leżącą w środku partycji. Jej indeks oznaczmy jako i_s (indeks środka):

Sprawdzamy, czy komórka t[i_s] zawiera poszukiwaną wartość. Jeśli tak, to kończymy, zwracając adres tej komórki.

Jeśli nie, to wykorzystujemy fakt uporządkowania tablicy. Skoro elementy są uporządkowane rosnąco, to na prawo od komórki t[i_s] mamy elementy równe lub większe od niej. Na lewo mamy elementy równe lub mniejsze od t[i_s]:

Sprawdzamy teraz jak się ma poszukiwana wartość do  t[i_s]. Wiemy, że nie jest równa, bo to sprawdziliśmy wcześniej. Może być zatem albo mniejsza od t[i_s], albo większa od t[i_s]. Jeśli jest mniejsza, to na pewno nie pojawi się na prawo od t[i_s], ponieważ tam są elementy większe lub równe t[i_s] (ze względu na uporządkowanie tablicy). Skoro tak, to za nową partycję przyjmujemy elementy o indeksach od i_p do i_s-1:

Czyli, i_p zostawiamy w spokoju, a w i_k umieszczamy i_s-1.

Jeśli poszukiwana wartość jest większa od t[i_s], to będziemy jej poszukiwać na prawo od t[i_s], ponieważ na lewo są elementy mniejsze lub równe t[i_s]. Za nową partycję przyjmiemy elementy o indeksach od i_s+1 do i_k:

Zwróć uwagę, że dwa porównania powodują ograniczenie do połowy ilość elementów do przeszukania. Po wyznaczeniu nowej partycji proces poszukiwania powtarzamy aż do znalezienia elementu lub do osiągnięcia partycji pustej.

Okazuje się, że tak skonstruowany algorytm wyszukuje daną w czasie proporcjonalnym do log₂n. Jest to bardzo korzystne. Jeśli liczba elementów wzrośnie 256, to średni czas wyszukiwania wzrośnie jedynie log₂256 = 8 razy! O  takim algorytmie mówimy, że ma złożoność obliczeniową logarytmiczną. Wyszukiwanie binarne stosuje się zwykle dla dużych tablic – przy kilku elementach zysk jest niewielki w porównaniu z algorytmem wyszukiwania liniowego.

W bibliotece standardowej (plik nagłówkowy stdlib.h) jest funkcja bsearch( ), która realizuje wyszukiwanie binarne w tablicy i posiada następującą składnię:

bsearch(poszukiwane, tablica, liczba_elementów, rozmiar, funkcja_porównawcza);

int funkcja(const void * a, const void * b);

Funkcja bsearch( ) zwraca w wyniku adres elementu tablicy (jako void *), który zawiera poszukiwaną wartość, lub NULL, jeśli w tablicy poszukiwanej wartości nie ma.

Uruchom program:

/*
 Wskaźniki do funkcji
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 8.11.2016
*/

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

#define MAX 160

// Funkcja porównująca
//--------------------
int comp(const void * a, const void * b)
{
  return *(int *) a - * (int *) b;
}

int main()
{
  int t[MAX],i,s,*p;

  setlocale(LC_ALL,"");

  // inicjujemy generator pseudolosowy
  srand((int)time(NULL));

  // w t umieszczamy ciąg rosnący:
  t[0] = rand() % 10; // pierwsza liczba 0...9
  for(i = 1; i < MAX; i++)
    t[i] = t[i - 1] + (rand() % 4);

  // losujemy element
  s = t[0] + rand() % (t[MAX - 1] - t[0] + 1);

  // szukamy
  p = bsearch(&s,t,MAX,sizeof(t[0]),comp);

  // wypisujemy wyniki:
  for(i = 0; i < MAX; i++)
  if(p == &t[i]) printf("[%3d]",t[i]);
  else           printf(" %3d ",t[i]);
  printf("\n\n");
  if(p) printf("%d jest w t[%d]\n\n", s , p-t);
  else  printf("%d nie ma w t[]\n\n",s);

  return 0;
}

Sortowanie szybkie

Sortowanie bąbelkowe oraz sortowanie przez wstawianie sortują tablicę w czasie proporcjonalnym do kwadratu liczby elementów n². Oznacza to, że jeśli zwiększysz liczbę elementów w tablicy 16 razy, to czas sortowania wzrośnie 16² = 256 razy. Dla małych tablic nie jest to zbyt istotne. Jednak przy dużych tablicach (np. długiej serii pomiarów z jakiegoś czujnika) czas przetwarzania może okazać się zbyt długi. Tutaj z pomocą przychodzi nam algorytm sortowania szybkiego (ang. quick sort), który został opracowany przez brytyjskiego informatyka Tony'ego Hoare'a.

Algorytm sortowania szybkiego opiera się na zasadzie dziel i zwyciężaj (ang. divide and conquer). W informatyce wiele problemów da się szybciej rozwiązać, jeśli przyjmiemy jakąś mądrą strategię postępowania. Z mojego doświadczenia wynika, że często algorytm prosty działa długo na danym zestawie danych, a algorytm bardziej zaawansowany działa dużo szybciej. Zasada dziel i zwyciężaj składa się z trzech etapów:

1. Duży problem podziel na mniejsze podproblemy.
2. Każdy z podproblemów rozwiąż osobno.
3. Rozwiązania podproblemów połącz ze sobą, tak aby utworzyły rozwiązanie problemu głównego.

Jak to się ma do sortowania? Załóżmy, że mamy partycję startową (patrz poprzedni rozdział) zdefiniowaną przez indeksy i_p (początek) i i_k (koniec):

Partycja ta obejmuje wszystkie elementy tablicy od t[i_p] do t[i_k].  Jeśli partycja jest pusta, i_p > i_k, to kończymy. Inaczej w partycji wybieramy dowolny element, który nazwiemy sobie piwotem v (elementem zwrotnym):

Następnie elementy partycji przenosimy, tak aby przed piwotem znalazły się elementy mniejsze lub mu równe, a za piwotem elementy większe lub mu równe.  Oczywiście końcowa pozycja piwota może ulec zmianie w stosunku do jego pozycji pierwotnej:

Zwróć uwagę, że element będący piwotem znajduje się już na swoim właściwym miejscu, tzn. nie musimy go już nigdzie przenosić w tablicy. Reszta elementów jest częściowo uporządkowana (względem piwota, lecz nie względem siebie). Umówmy się, że powstają w ten sposób dwie nowe partycje: lewa o indeksach od i_p do i_v-1 i prawa o indeksach od i_v+1 do i_k. Każdą z  tych partycji sortujemy w ten sam sposób, tzn. wyznaczamy w nich piwoty i reorganizujemy elementy, tak aby przed piwotem znalazły się elementy mniejsze lub równe, a za piwotem elementy większe lub równe. Powstaną teraz 4 partycje:

Każdą z nowych partycji sortujemy w ten sam sposób. Za każdym razem uporządkowanie zbioru rośnie (rozwiązanie małych problemów, czyli sortowanie partycji, przybliża nas do rozwiązania problemu głównego, czyli posortowania całego zbioru). Gdy partycje staną się puste lub jednoelementowe, sortowanie można przerwać, a zbiór będzie posortowany. Okazuje się, że tak przeprowadzone sortowanie wykonuje się w czasie proporcjonalnym do n·log₂(n). Jest to dużo korzystniejsze od n². Jeśli zwiększymy liczbę elementów 16 razy, to czas sortowania wzrośnie 16·log₂16 = 16·4 = 64 razy (poprzednio wzrost wyniósł 16² = 256 razy). O takim algorytmie mówimy, że ma złożoność obliczeniową liniowo-logarytmiczną.

Jeśli cię ten temat zainteresował, to przeczytaj nasz artykuł o sortowaniu szybkim.

W bibliotece standardowej (plik nagłówkowy stdlib.h) jest funkcja qsort( ), która dokonuje sortowania szybkiego tablicy. Posiada następującą składnię:

qsort(tablica, liczba_elementów, rozmiar, funkcja_porównawcza);

int funkcja(const void * a, const void * b);

Uruchom program:

/*
 Wskaźniki do funkcji
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 8.11.2016
*/

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

#define MAX 200

// Funkcja porównująca
//--------------------
int comp(const void * a, const void * b)
{
  return *(int *) a - * (int *) b;
}

int main()
{
  int t[MAX],i;

  setlocale(LC_ALL,"");

  // inicjujemy generator pseudolosowy
  srand((int)time(NULL));
  // w t umieszczamy ciąg liczb pseudolosowych 100...999:
  for(i = 0; i < MAX; i++) t[i] = 100 + (rand() % 900);
  printf("PRZED SORTOWANIEM SZYBKIM:\n\n");
  for(i = 0; i < MAX; i++) printf("%4d",t[i]);
  printf("\n\n");
  // sortujemy szybko
  qsort(t,MAX,sizeof(t[0]),comp);
  printf("PO SORTOWANIU SZYBKIM:\n\n");
  for(i = 0; i < MAX; i++) printf("%4d",t[i]);
  printf("\n\n");

  return 0;
}

To już wszystko w tym kursie. Więcej na temat języka C możesz poznać z licznych kursów w Internecie.