Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

obrazek

Autor artykułu: mgr Jerzy Wałaszek
Konsultacje: Wojciech Grodowski, mgr inż. Janusz Wałaszek

©2022 mgr Jerzy Wałaszek
I LO w Tarnowie

obrazek

Jeśli dotarłeś do tego miejsca i przyswoiłeś sobie przedstawiony materiał, to możesz rozpocząć naukę programowania mikrokontrolerów w języku C. Niniejszy kurs miał na celu zaznajomienie cię z podstawami języka C. Język ten jest bardzo potężny i pozwala wygodnie programować komputery zarówno duże (np. superkomputer Cray) jak i całkiem małe, jakimi są niewątpliwie mikrokontrolery. Kurs ten nie jest kompletny, jeśli chodzi o język C. Lecz takie było założenie. Nie musisz znać wszystkich tajników, lecz tylko te, które będą ci potrzebne (odnosi się to wszystkich kursów w tym artykule). A ten cel kurs spełnia.

W tym rozdziale postaram się uzupełnić twoją wiedzę o języku C. Jeśli czegoś nie rozumiesz, nie przejmuj się. Umiejętności programowania przychodzą z czasem, po napisaniu dziesiątek/setek/tysięcy programów. Pierwsze "dzieła" są zawsze ułomne. Później nabierzesz doświadczenia i twoje programy staną się bardziej profesjonalne. Najszybciej nauczysz się programować przy tworzeniu różnych projektów z mikrokontrolerami.

Warsztat

Kurs języka C

Zakończenie

SPIS TREŚCI
Podrozdziały

Typy danych w języku C

Odmiany typów podstawowych

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

char

Jest podstawowym typem danych dla znaków ASCII. Kod ASCII jest kodem 8 bitowym. Wartości char są liczbami całkowitymi. Ich zakres zależy od tego, jak kompilator traktuje standardowo typ char. Jeśli traktuje go jako liczby bez znaku, to zakres wynosi od 0 do 255. Jeśli traktuje go jako liczby ze znakiem, to zakres wynosi od -128 do -1 dla kodów rozszerzonych i od 0 do 127 dla kodów podstawowych ASCII. Standardowe traktowanie typu char należy sprawdzić w opcjach kompilatora.

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

signed char – znaki o kodach od -128 do 127
unsigned char – znaki o kodach od 0 do 255

int

Typ int jest tzw. typem standardowym (ang. generic type) dla liczb całkowitych ze znakiem. Przyjmuje się, że jest to naturalny typ liczb całkowitych dla danego mikroprocesora. W komputerach IBM stosowane są obecnie mikroprocesory 64-bitowe. Dla nich naturalnym rozmiarem danej całkowitej jest 64-bity. Zatem typ int powinien mieć rozmiar 64-bitów (8 bajtów). Jednakże ze względu na kompatybilność z komputerami wyposażonymi w procesory 32-bitowe (gdzieniegdzie się je jeszcze spotyka), typ int w CodeBlocks ma 32 bity długości, czyli 4 bajty. Zakres takich liczb wynosi od -2147483648 do 2147483647 (-231...231 - 1). W przyszłości to się zapewne zmieni i typ int będzie standardowo oznaczał liczby 64-bitowe w kodzie U2.

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 (-215...215 - 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ąć):

unsigned int liczby całkowite bez znaku. Zakres zależy od rozmiaru int: 4-bajty – 0...4294967296 (0...232 - 1) ; 2-bajty – 0...65535 (0...216 - 1) ; 1-bajt – 0...255 (0...28 - 1).
short int oznacza tzw. krótką liczbę całkowitą, która nie może posiadać więcej bitów od typu int. Jeśli typ int jest 32-bitowy, to typ short jest zwykle 16-bitowy. Jeśli typ int jest 16-bitowy, to typ short może być 16-bitowy lub 8-bitowy (należy sprawdzić z konkretnym kompilatorem).
unsigned short int krótka liczba całkowita bez znaku. Rozmiar taki sam jak dla short.
long int długa liczba całkowita. Zwykle rozmiar jest dwa razy dłuższy od rozmiaru int, lecz np. w CodeBlocks long int oznacza dokładnie to samo, co int, czyli liczbę 4-bajtową. Jeśli typ int oznacza liczby 2-bajtowe, to typ long int będzie oznaczał liczby 4-bajtowe. Jeśli typ int oznacza liczby 1-bajtowe, to typ long int będzie oznaczał liczby 2-bajtowe.
unsigned long int długa liczba całkowita bez znaku. Rozmiar taki sam jak dla long int.
long long int bardzo długa liczba całkowita. Zwykle ma rozmiar cztery razy dłuższy od rozmiaru int. W CodeBlocks typ long long int oznacza daną 64-bitową (8 bajtów) o zakresie od -9223372036854775808 do 9223372036854775807 (-263 ... 263 - 1). Typ long long int może nie być dostępny na danej platformie (np. PIC). Jeśli typ int jest 16-bitowy, to typ long long int jest 64-bitowy. Jeśli typ int jest 8-bitowy, to typ long long int jest 32-bitowy.
unsigned long long int bardzo długa liczba całkowita bez znaku. Długość taka sama jak dla long long int. Dla 8-bajtów zakres wynosi od 0...18446744073709551615 (0...264 - 1).

float

Jest typem zmiennoprzecinkowym, który pozwala używać liczb ułamkowych. Precyzja wynosi 7...8 cyfr. Oznacza to, że jeśli zapis liczby wymaga więcej niż 7 cyfr, to cyfra ósma i dalsze mogą nie zostać zapamiętane dokładnie.  Zakres danych typu float wynosi: ± 3.4 · 10± 38. W pamięci dana typu float zajmuje 4-bajty.

double

Jest typem zmiennoprzecinkowym podwójnej precyzji. Na dużych komputerach dana typu double zajmuje w pamięci 8-bajtów i ma zakres: ± 1.7 · 10± 308. Precyzja wynosi około 15 cyfr (stąd nazwa double, czyli podwójny, ponieważ typ ten posiada dwa razy więcej cyfr znaczący w porównaniu z float). Na małych komputerach typ double jest taki sam jak float.

long double

Jest typem zmiennoprzecinkowym o rozszerzonej precyzji. Typ ten nie jest wszędzie dostępny. Współczesny mikroprocesor Pentium (lub AMD) tak naprawdę składa się z dwóch procesorów: procesora podstawowego, który wykonuje program oraz koprocesora arytmetycznego, który wykonuje obliczenia na liczbach zmiennoprzecinkowych. Te dwa procesory ściśle ze sobą współpracują. Aby zminimalizować błędy obliczeń, koprocesor arytmetyczny stosuje wewnętrznie format 10-bajtowy (80-bitów) dla przetwarzanych liczb zmiennoprzecinkowych. Ten format nazywamy właśnie long double. Dane typu long double mają precyzję 20 cyfr i zakres: -1,1 × 104932 do 1,1 × 104932. W małych systemach nie ma zwykle koprocesora arytmetycznego i typ long double albo nie jest dostępny, albo jest taki sam jak double, czyli typy float, double i long double oznaczają te same dane zmiennoprzecinkowe o rozmiarze 4 bajtów.

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};

nazwa_typu określa nazwę dla definiowanego typu wyliczeniowego.
nazwa_i wewnątrz klamerek podajemy ciąg nazw dla stałych, którym zostaną nadane kolejne wartości całkowite począwszy od zera w górę.

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:
sunday ← 0
monday ← 1
tuesday ← 2
wednesday ← 3
thursday  ← 4
friday ← 5
saturday ← 6

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:
sunday ← 0
monday ← 1
tuesday ← 6
wednesday ← 7
thursday  ← 8
friday ← 9
saturday ← 10

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;
}

Pola bitowe

Pola bitowe (ang. bit fields) umożliwiają tworzenie danych, które zajmują określoną liczbę bitów, co z kolei pozwala efektywniej wykorzystać pamięć komputera. Definicja pól bitowych opiera się na definicji struktury i wygląda następująco:
struct nazwa_typu
{
  typ_całkowity nazwa_pola_1 : rozmiar_1;
  typ_całkowity nazwa_pola_2 : rozmiar_2;
  ...
  typ_całkowity nazwa_pola_n : rozmiar_n;
};

nazwa_typu określa nazwę dla definiowanego typu pól bitowych. Jeśli nie chcemy definiować typu, a jedynie zmienną, to nazwę typu można pominąć, tworzą w ten sposób bezimienną strukturę. Wyjaśnienie napotkasz w przykładach.
typ_całkowity określa sposób interpretacji danych umieszczonych w polu bitowym. Możliwe wartości to: int, unsigned int lub signed int (to samo co int).
nazwa_pola określa nazwę, poprzez którą będziemy sie odwoływali do określonego pola bitowego.
rozmiar określa liczbę bitów, którą pole zajmie.

Jak to działa? Struktura tyle danych typu int, aby pomieściły w sobie wszystkie pola bitowe. Załóżmy, że zdefiniowaliśmy następującą strukturę:
struct flags
{
  unsigned a : 1, b : 3, c : 2, d : 1;
};

W strukturze zawarte są 4 pola bitowe: a jednobitowe, b trzybitowe, c dwubitowe oraz d jednobitowe. Liczba użytych bitów wynosi: 1 + 3 + 2 + 1 = 7, zatem mieszczą się w jednej danej typu int. Rozmiar struktury zależy od rozmiaru typu int. W Code::Blockcs będzie to 4 bajty:
/*
 Pola bitowe
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 30.10.2016
*/

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

struct flags
{
  unsigned a : 1, b : 3, c : 2, d : 1;
};

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

  printf("%d\n", sizeof(struct flags));

  return 0;
}

W pamięci pola te są rozmieszczone w pierwszym bajcie struktury następująco (gdy typ int ma rozmiar 4 bajtów):

Numer bitu 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10   9   8   7   6   5   4   3   2   1   0
Pole nieużywane d c b a

Pola bitowe są traktowane tak samo jak pola struktur (którymi przecież są). Możesz umieszczać w nich dane oraz używać ich w wyrażeniach. Jedynym ograniczeniem jest to, iż nie można uzyskać adresu pola bitowego oraz nie można go zainicjować w trakcie tworzenia zmiennej.
/*
 Pola bitowe
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 30.10.2016
*/

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

struct flags
{
  unsigned a : 1, b : 3, c : 2, d : 1;
};

int main()
{
  struct flags f; // tworzymy zmienną z polami bitowymi

  setlocale(LC_ALL,"");

  f.a = 1;
  f.c = 3;
  f.d = 0;
  f.b = f.a + f.c + f.d;
  printf("%d\n",f.b);

  return 0;
}

Jeśli wynik przekracza rozmiar pola, to zostanie obcięty do rozmiaru pola. Innymi słowy: jeśli w strukturze zdefiniowałeś pole 3 bitowe, a chcesz w nim umieścić daną np. 4 bitową 11012 (dziesiętnie 13), to w polu zostaną umieszczony tylko 3 najmłodsze bity, czyli 1012 (dziesiętnie 5):
/*
 Pola bitowe
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 30.10.2016
*/

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

struct flags
{
  unsigned a : 1, b : 3, c : 2, d : 1;
};

int main()
{
  struct flags f; // tworzymy zmienną z polami bitowymi

  setlocale(LC_ALL,"");

  f.b = 13;
  printf("%d\n",f.b);

  return 0;
}

Pola bitowe nie muszą leżeć obok siebie. Możesz wprowadzić między nimi przerwy. Przerwę definiujesz podając tylko jej rozmiar. Na przykład definicja:

struct flags
{
  unsigned : 3, a : 2, : 5;
  int b : 5;
};

tworzy strukturę, w której są dwa pola bitowe: a trzybitowe i b pięciobitowe. Pole a przechowuje liczby całkowite bez znaku od 0 do 7. Pole b przechowuje liczby całkowite ze znakiem od -16 do 15. Pierwsze trzy bity struktury są nieużywane, również 5 bitów pomiędzy polami a i b nie jest używane. Całość wygląda następująco:

Numer bitu 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10   9   8   7   6   5   4   3   2   1   0
Pola bitowe nieużywane b nieużywane a nieużywane
/*
 Pola bitowe
 (C)2016 mgr Jerzy Wałaszek
 Data utworzenia: 30.10.2016
*/

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

struct flags
{
  unsigned : 3, a : 3, : 5;
  int b : 5;
};

int main()
{
  struct flags f; // tworzymy zmienną z polami bitowymi

  setlocale(LC_ALL,"");

  f.a = 6;
  f.b = -12;
  printf("%d %d\n", f.a, f.b);

  return 0;
}
Na początek:  podrozdziału   strony 

Stałe

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

Są to liczby ze znakiem z zakresu zależnego od rozmiaru typu int. Liczby te mogą być zapisane w następujących systemach:

unsigned int

Liczby całkowite bez znaku. Dla uniknięcia niejednoznaczności zapis liczby kończymy znakiem u lub U, np. 40000u, 0xff76u.

long int

Liczby całkowite długie. Na końcu zapisu dodajemy l lub L: -2000000000L.

unsigned long int

Liczby całkowite długie bez znaku. Na końcu zapisu dodajemy literki u i l (lub U i L): 3500000000UL.
/*
 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 = 0b10110;

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

Na początek:  podrozdziału   strony 

Liczby pseudolosowe

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ą – taka 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:

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 1/6. 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 1/6 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);
ziarno określa tzw. ziarno liczb pseudolosowych, czyli wartość na podstawie której zostanie wygenerowany ciąg pseudolosowy. Jest to wartość typu int.

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...215 - 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 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) :

1 + rand() % 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:

W pętli wykonującej się przynajmniej 3 razy tyle ile wynosi rozmiar tablicy generujemy dwa pseudolosowe indeksy. Następnie zamieniamy ze sobą elementy tablicy znajdujące się w komórkach o tych indeksach.

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.

obrazek

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 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:

  1110001001
^ 0011010111
  1101011110
  1101011110
^ 0011010111
  1110001001

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:
Wpisz klucz: 15
Wpisz tekst (do 79 liter):

Atak o świcie na pozycje wroga w kwadracie Q17XL.

Veqq5e,Ç{~ppl<by.wvdijtp>roodg$~.~}{t~trl` _'!CB0
Wpisz klucz: 15
Wpisz tekst (do 79 liter):

Veqq5e,Ç{~ppl<by.wvdijtp>roodg$~.~}{t~trl` _'!CB0

Atak o świcie na pozycje wroga w kwadracie Q17XL.

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

Na początek:  podrozdziału   strony 

Zmienne ulotne

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).

Na początek:  podrozdziału   strony 

Skoki

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;
}
Na początek:  podrozdziału   strony 

Wskaźniki do funkcji

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:

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:

Tworzymy zmienną globalną o nazwie func, która jest wskaźnikiem do funkcji niezwracającej wyniku (typ void) i posiadającej jeden argument całkowity int. Następnie umieszczamy prototypy funkcji f1() i f2(). Prototyp jest zapowiedzią funkcji. Prototypy faktycznie potrzebujemy w tym programie (a przynajmniej potrzebny jest prototyp f2()), ponieważ funkcje f1() i f(2) krzyżowo odwołują się do siebie nawzajem. Każda z nich wypisuje pewien tekst, a następnie we wskaźniku func umieszcza adres drugiej funkcji.

W programie głównym inicjujemy wskaźnik func wpisując do niego adres pierwszej funkcji f1().  Następnie w pętli wywołujemy funkcję wskazywaną przez wskaźnik func. Ponieważ po każdym wywołaniu func wskazuje inną funkcję, to w efekcie w kolejnych obiegach pętli będą wywoływane naprzemiennie funkcje f1() i f2().

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: ip (indeks początku) i ik (indeks końca):

                                 
ip                               ik

Komórki tablicy od t[ip] do t[ik] nazwijmy partycją. Partycja będzie zawierała komórki, jeśli ip ≤ ik. 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 is (indeks środka):

                                 
ip               is               ik

Sprawdzamy, czy komórka t[is] 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[is] mamy elementy równe lub większe od niej. Na lewo mamy elementy równe lub mniejsze od t[is]:

elementy ≤ t[is] t[is] elementy ≥ t[is]
                                 
ip               is               ik

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

elementy ≤ t[i] t[is] elementy ≥ t[i]
                                 
ip       is-1 is               ik

Czyli, ip zostawiamy w spokoju, a w ik umieszczamy is - 1.

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

elementy ≤ t[is] t[is] elementy ≥ t[is]
                                 
ip               is is+1         ik

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 log2n. Jest to bardzo korzystne. Jeśli liczba elementów wzrośnie 256, to średni czas wyszukiwania wzrośnie jedynie log2256 = 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);
poszukiwane wskaźnik elementu, który jest poszukiwany. Jest to wskaźnik typu const void *, który określa jedynie adres, a nie typ elementu
tablica wskaźnik pierwszego elementu tablicy. Wskaźnik typu const void *.
liczba_elementów określa liczbę elementów do przeszukania
rozmiar określa rozmiar elementu w bajtach
funkcja_porównawcza wskaźnik do funkcji porównującej elementy tablicy z wartością poszukiwaną. Ponieważ funkcja bsearch() jest uniwersalna, nie określa się typu porównywanych elementów. Wskaźnik wskazuje zatem funkcję o następującej  składni:
int funkcja(const void * a, const void * b);

Funkcja ta jako argumenty przyjmuje dwa wskaźniki typu void *, które wskazują: a – wartość poszukiwaną, b – element tablicy. Funkcja ta powinna zwracać wartości:

  • 0, jeśli a = b
  • > 0, jeśli a > b
  • < 0, jeśli a < b

Zobacz na przykładowy program, jak należy tę funkcję zdefiniować.

Funkcja bsearch() zwraca w wyniku adres elementu tablicy (jako void *), który zawiera poszukiwaną wartość, lub NUL, 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 n2. Oznacza to, że jeśli zwiększysz liczbę elementów w tablicy 16 razy, to czas sortowania wzrośnie 162 = 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 dzieli się na trzy etapy:

  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 ip (początek) i ik (koniec):

                                 
ip                               ik

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

                                 
ip         iv                     ik

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:

Partycja lewa
elementy t[iv]
t[iv] Partycja prawa
elementy t[ip]
                                 
ip         iv - 1 iv iv + 1         ik

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 ip do iv-1 i prawa o indeksach od iv+1 do ik. 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·log2(n). Jest to dużo korzystniejsze od n2. Jeśli zwiększymy liczbę elementów 16 razy, to czas sortowania wzrośnie 16·log216 = 16·4 = 64 razy (poprzednio wzrost wyniósł 162 = 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);
tablica wskaźnik pierwszego elementu tablicy do posortowania. Wskaźnik typu void *.
liczba_elementów określa liczbę elementów w sortowanej tablicy
rozmiar określa rozmiar elementu w bajtach
funkcja_porównawcza wskaźnik do funkcji porównującej elementy tablicy z wartością poszukiwaną. Ponieważ funkcja qsort() jest uniwersalna, nie określa się typu porównywanych elementów. Wskaźnik wskazuje zatem funkcję o następującej  składni:
int funkcja(const void * a, const void * b);

Funkcja ta jako argumenty przyjmuje dwa wskaźniki typu void *, które wskazują dwa elementy do porównania a i b. Funkcja ta powinna zwracać wartości:

  • 0, jeśli a = b
  • > 0, jeśli a > b
  • < 0, jeśli a < b

Funkcja qsort() nie zwraca żadnej wartości.

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. Resztę poznasz w części praktycznej, gdy będziemy programować mikrokontrolery w konkretnych projektach.

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2022 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.