Podstawy programowania.
7. Przetwarzanie jednorodnych struktur danych (tablice).
7. Przetwarzanie jednorodnych struktur danych (tablice)
Zagadnienia: Złożone struktury danych - typ tablicowy. Inicjowanie tablic. Przykłady
przetwarzania tablic. Przekazywanie tablic jako argumentów funkcji.
Złożone struktury danych - typ tablicowy
Tablica [20], [21], [16], [22] jest jednorodną strukturą danych składającą się z
elementów tego samego typu:
" zajmuje ciągły obszar pamięci,
" dostęp do elementów za pośrednictwem indeksów (liczb określających położe-
nie elementu w tablicy),
" numeracja (indeksacja) elementów rozpoczyna się od zera,
" elementy tablicy mogą być dowolnego typu (wszystkie tego samego) nazywa-
nego typem bazowym,
" nie ma ograniczeń na liczbę wymiarów - indeksów.
Składnia:
typ_elementu identyfikator_tablicy[wymiar_1][wymiar_2]....[wymiar_n];
" typ_elementu (tablicy) - jest zdefiniowanym lub jednym z predefiniowanych ty-
pów danych,
" wymiar_1 - wymiar_n - wyrażenia skalarne o określonej wartości. Na podsta-
wie wymiarów wyliczany jest podczas kompilacji rozmiar tablicy w sensie zaję-
tości pamięci (statyczny przydział pamięci).
Tablica jednowymiarowa
identyfikator tablicy - t
int t[9]; // 9cio elementowa tablica liczb całkowitych
liczność elementów (rozmiar)
typ elementów tablicy t.
" Numeracja elementów:
t[0], t[1], t[2], t[3], ..., t[8] t[9] // t[9] jest niedostępne  indeksy od 0
" Dostęp do elementów tablicy:
nadanie wartości elementowi tablicy
int i = 1, w, t[9]; // i - indeks tablicy t
t[i] = 23; // co oznacza t[1] = 23.
pobranie wartości elementu tablicy
w = t[i]; // zmienna w przyjęła wartość 23.
tablica dwuwymiarowa
identyfikator tablicy - j
double j[4][3]; // tablica liczb rzeczywistych
liczność kolumn (rozmiar)
liczność wierszy (rozmiar)
typ elementów tablicy j
" Numeracja elementów:
j[0][0], j[0][1], j[0][2], j[0][3]
j[1][0], j[1][1], j[1][2]
j[2][0], j[2][1], j[2][2]
j[3][0], j[3][1], j[3][2]
j[4][0]
" Dostęp do elementów tablicy:
nadanie wartości elementowi tablicy
int w = 1, k = 2; // w - indeks wiersza, k - indeks kolumny
double z, j[4][3];
j[w][k] = 12.34; // co odpowiada j[1][2] = 12.34.
pobranie wartości elementu tablicy
z = j[1][2]; // zmienna w przyjęła wartość 12.34
Uwaga!
Nazwa tablicy jest stałą mającą znaczenie adresu jej pierwszego elementu (adre-
su pamięci dla elementu t[0]). W tablicy dwuwymiarowej (np. double j[4][3]) adre-
sem poczÄ…tku tablicy jest adres jej pierwszego elementu (j[0][0]).
Inicjowanie tablic
Składnia:
definicja_tablicy = { lista wartości początkowych };
Na przykład:
int t[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
int k[ ] = { 5, 6, 7 }; /* k[0] = 5; k[1] = 6; k[2] = 7; */
int n[4][3] = { {1, 2, 3}, {4, 5, 6} };
Znacznik końca napi-
su (stała NULL.).
char nazwa[10] =  Turbo C ;
nr znaku 0 1 2 3 4 5 6 7 8 9
napis  T  u  r  b  o    C  \0
char nz[ ] = {  T ,  u ,  r ,  b ,  o ,   ,  C ,  \0 };
Uwagi:
" Przy definicji tablicy z jednoczesną jej inicjacją nie jest konieczne określenie
rozmiaru tablicy - zostanie on określony na podstawie liczności elementów listy
inicjacyjnej (int k[ ] = { 5, 6, 7 };).
" Lista wartości inicjujących nie może zawierać więcej elementów niż rozmiar ta-
blicy.
" Jeżeli wartości inicjujących jest mniej niż elementów tablicy, wówczas pozostałe
elementy są w tablicach liczbowych i znakowych inicjowane wartością zero.
" Przy inicjowaniu tablicy dwuwymiarowej na liście inicjacyjnej dane umieszcza
się blokami w kolejności wierszy {{blok wiersza 0}, {blok wiersza 1}, ...};
np. int n[4][3] = {{1, 2, 3}, {4, 5, 6}}; zatem elementy wierszy 3 i 4 zostanÄ… zaini-
cjowane wartością zero (int n[4][3] = {{1, 2, 3}, {4, 5, 6},{0, 0, 0},{0, 0, 0}}).
" Przy inicjacji tablicy łańcuchem znaków w postaci  ...  (char nazwa[10] =  tur-
bo c ;) dokładany jest automatycznie znak końca napisu - stała NULL ( \0 ).
" Przy inicjacji tablicy znakami (char nz[ ] = {  t ,  u ,  r ,  b ,  o ,   ,  c ,  \0 };) należy
zadbać o dostawienie znaku końca napisu stała NULL.
Przykłady przetwarzania tablic
#define MAX 100
void main()
{
int t[MAX];
for(int i = 0; i < MAX; ++i) // zerowanie elementów tablicy
t[i] = 0;
}
2
void main()
{
char nazwa[ ] =  turbo c ;
int i = 0;
while(nazwa[i] != '\0') // while(nazwa[i] != NULL)
{ // lub krócej while(nazwa[i])
nazwa[i] = nazwa[i] - ('a' - 'A');
++i;
}
}
//---------------------------------------------------------------------------------------------
#define MAXW 4
#define MAXK 3
void main()
{
int n[MAXW][ MAXK] = { {1, 2, 3}, {4, 5, 6}, {10, 23, 13}, {7, 9, 8}};
int w, k, max = n[0][0];
for(w = 0; w < MAXW; w++)
for(k = 0; k < MAXK; ++k) // szukanie w tablicy n wartości największej
if(n[w][k] > max)
max = n[w][k];
}
Przekazywanie tablic jako argumentów funkcji
Gdy argumentem funkcji jest nazwa tablicy, wówczas do funkcji przekazane zo-
staje położenie początku tablicy. Stanowi to odstępstwo od zasady przekazywania
argumentów przez wartość. Kod wewnątrz funkcji operuje na  oryginale tablicy i ma
możliwość zmieniania jej zawartości. Przykładem niech będzie obliczenie i zapamię-
tanie w tablicy wyrazów ciągu Fibonacciego.
void fibo(int n int t[ ])
{
for(int i = 1;i <= n; ++i)
if (i < 3)
t[i] = 1; // lub prościej t[i] = (i < 3 ? 1 : t[i-1] + t[i-2]);
else
t[i] = t[i-1] + t[i-2];
}
main()
{
int ile = 10, tf[ile+1]; // element tf[0] nie wykorzystywany;
fibo(ile, tf);
for(int j = 1; j <= ile; j++)
cout <<  \n\rF( << j <<  ) =  << tf[j];
}
Przykład cw07
Zaprojektować algorytm (rys.7.1) oraz na jego podstawie funkcję konwersja
przekształcania liczby d (całkowita bez znaku) z systemu dziesiętnego na system o
podstawie p. Cyfry (wartość r) przekształconej liczby w postaci znakowej należy, za-
pamiętać w tablicy t. W ciągu cyfr w tablicy t najmłodsza cyfra zajmuje pozycję skraj-
nie prawą, zaś najstarsza cyfra - lewą. Na zapamiętanie cyfr przewidziano w tablicy t
max pozycji. Niedobór cyfr należy uzupełnić do oczekiwanej liczności cyframi zero
3
(zera na pozycjach nieznaczących). Dla systemów liczenia o podstawie p > 9 reszty
o wartościach 10, 11, 12, & , p-2, p-1 należy zastąpić kolejnymi literami alfabetu: A,
B, C, &
Szkic rozwiÄ…zania:
while (d > 0)
{
1. r = d % p //reszta z dzielenia d przez p
2. d = d / 2 część całkowita z dzielenia jest kolejną wartością d
3. przekształcić wartość cyfry r na cyfrę w postaci znakowej i zapamiętać
na kolejnej pozycji w tablicy t.
}
Przykład konwersji liczby dziesiętnej d = 1756 na liczbę trzynastkową (p = 13)
i d p r znak
1 1756 : 13 1  1
2 135 : 13 5  5
3 10 : 13 10  A
0 rn
Liczba w systemie trzynastkowym w postaci znakowej zapisana na przykład na
ośmiu pozycjach w tablicy t przedstawia się nastepująco
pozycja 0 1 2 3 4 5 6 7 8
znak  0  0  0  0  0  A  5  1  \0
Przy zamianie wartości cyfry na cyfrę w postaci znaku można wykorzystać fakt,
że kody ASCII stanowią typ uporządkowany. Cyfry i początkowe litery (wielkie) alfa-
betu majÄ… kody:
kod 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
znak  0  1  2  3  4  5  6  7  8  9  :  ;  <  =  >  ?  @  A  B
Przyjmując za punkt odniesienia kod  0 to dla wartości cyfry r < 10 (reszta z
dzielenia) odpowiadać będzie kod  0 + r. Dla r > 9 odpowiednio  0 +r + 7 ponieważ
pomiędzy kodem 9 a kodem litery A występuje 7 znaków.
Opis obiektów:
" parametry: d  liczba całkowita bez znaku,
p  podstawa systemu liczenia,
max  liczba cyfr w napisie;
" wynik: t - liczba w postaci max znakowego napisu;
" robocze: i - licznik iteracji,
r - reszta z dzielenia d przez p.
4
Algorytm
konwersja
1
i = 1
2
nie
i <= max
tak
3
r = d % p
4
6
nie
r > 9 t[max-i] = '0'+r
tak
5
t[max-i] = '0'+r+7
7
d = d / 2
8
i = i + 1
9
t[max] = '\0'
koniec
Rysunek 7.1. Algorytm konwersji liczby dziesiętnej całkowitej na liczbę w system o podstawie p
5
Program
/*T%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%W%
Q% PROGRAM: liczby v1.0 Q%
Q% ZADANIE: tworzy środowisko do testowania funkcji konwersja, Q%
Q% DANE: ldz - liczba dziesiętna z przedziału 0..255, Q%
Q% podstawa - systemu liczenia, Q%
Q% WYNIKI: liczby w postaci znakowej w systemach liczenia od 2 do p, Q%
Q% AUTOR: ................... 2003.12.10 Q%
Q% PLIK: cw07.cpp Q%
Z%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%]%*/
#include
#include
#include
#define MAX_LD 255 // max wartość danej
#define DLB 8 // max dług. łańcucha
#define MAX_P 18 // max podstawa
/*T%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%W%
Q% FUNKCJA: konwersja Q%
Q% ZADANIE: zamiana liczby dziesiętnej na liczbę w postaci Q%
Q% znakowej w systemie liczenia o danej podstawie p, Q%
Q% PARAMETRY: d - liczba do zamiany, Q%
Q% p  podstawa systemu liczenia, Q%
Q% max  liczba cyfr w napisie, Q%
Q% WYNIKI: t  liczba w postaci max znakowego napisu. Q%
Z%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%]%*/
void konwersja(char t[], int d, int p, int max)
{
int I = 1, r;
while(i <= max)
{
r = d % p; // ASCII & 789:;<=>?@ABC&
if (r > 9) // +7 oznacza 'A' - '9' = 7
t[max - i] = '0' + r + 7;
else
t[max - i] = '0' + r;
d /= p;
i++;
}
t[max] = '\0';
}
main()
{
int ldz, podstawa; // liczba dziesiętna , podstawa syst. liczenia
char lb[DLB+1]; // liczba po konwersji w postaci napisu
textbackground(LIGHTGRAY); clrscr();
textcolor(WHITE);
gotoxy(25,2);
cprintf("Systemy liczenia");
do
{
textcolor(WHITE);
gotoxy(15,4);
cprintf("Liczba [0 ... %d] do zamiany ",MAX_LD);
textbackground(BLACK);
cprintf(" ");
gotoxy(wherex()-4,4);
scanf("%d",&ldz);
textbackground(LIGHTGRAY);
}
while (ldz <= 0 || ldz > MAX_LD);
6
do
{
textcolor(WHITE);
gotoxy(15,5);
cprintf("Podstawa [0 ... %d] ",MAX_P);
textbackground(BLACK);
cprintf(" ");
gotoxy(wherex()-4,5);
scanf("%d",&podstawa);
textbackground(LIGHTGRAY);
}
while (podstawa <= 0 || podstawa > MAX_P);
textbackground(LIGHTGRAY);
textcolor(YELLOW);
for (int j = 2; j <= podstawa; ++j)
{
gotoxy(15,wherey()+1);
konwersja(lb,ldz,j, DLB);
cprintf("%s%d %s",(j<10?" " : ""),j,lb);
}
gotoxy(wherex()+10,wherey());
textcolor(GREEN);
cprintf("Naciśnij klawisz Enter");
getch();
}
Przykład cw07a
Dana jest tablica t[ ], w której zapisano n liczb naturalnych. Elementy tablicy
uporządkowane są w kolejności rosnącej (t[i+1] > t[i] dla i " [0, n-2]). Zaprojektować
algorytm (rys. 7.2) oraz moduł (funkcję) o nazwie szukaj - wyszukiwania elementu,
którego wartość jest równa zadanej liczbie x. W przypadku znalezienia takiego ele-
mentu należy zwrócić jego numer (indeks elementu tablicy t), w przeciwnym razie
należy przekazać liczbę -1 jako informację, że poszukiwanie zakończone zostało
niepowodzeniem (liczby x nie odnaleziono).
Szkic metody wyszukiwania przez podział
while (liczność elementów tablicy w obszarze poszukiwań jest większa od zera)
{
1. podział t na połowę,
2. określenie, w której połowie leży szukana wartość x,
3. jeżeli szukana wartość nie leży w obydwu połowach to element środkowy
jest elementem poszukiwanym - koniec poszukiwań,
4. zawężenie obszaru poszukiwań do właściwej połowy.
}
5. liczby nie odnaleziono - koniec poszukiwań.
x
t sr
min max
min = sr +1 sr max
min sr max = sr - 1
7
Algorytm
szukaj
1
min = 0
max = n-1
brak = 1
2
nie
(min d" max)
oraz brak
tak
3
sr = (min+max)/2
4
5
tak
max = sr-1 x < t[sr]
nie
6
7
tak
min = sr+1 x > t[sr]
nie
8
wynik = sr
brak = 0
9
tak
10
brak = 1 wynik = - 1
nie
koniec
Rysunek 7.2. Algorytm przeglądania przez podział
Opis obiektów
" parametry: t[ ] - uporzÄ…dkowana rosnÄ…co tablica liczb,
n - liczność elementów tablicy t,
x - liczba szukana;
" wynik: wynik - numer elementu tablicy (lub wartość -1);
" robocze: min - indeks pierwszego elementu przeszukiwanego obszaru tablicy,
max - indeks ostatniego elementu przeszukiwanego obszaru tablicy,
sr - indeks środkowego elementu przeszukiwanego obszaru tablicy.
8
Program
/*T%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%W%
Q% PROGRAM: test Q%
Q% ZADANIE: środowisko do testowania funkcji "szukaj"  szukania w Q%
Q% uporządkowanej tablicy liczb całkowitych zadanej liczby x,Q%
Q% WYNIKI: nr - położenie (indeks) szukanej w tablicy liczby, Q%
Q% nr = -1 oznacza niepowodzenie wyszukiwania, Q%
Q% AUTOR: ................... Q%
Q% PLIK: cw07a.cpp Q%
Z%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%]%*/
#include
#include
#include
#define MAX_T 100 // max liczba elementów
int szukaj(long t[],int n,long int x); // zapowiedz
funkcji "szukaj"
main() // środowisko do testowania funkcji " szukaj "
{
int wynik, n,nr;
long kod; // szukany numer oraz tablica z numerami
long numery[MAX_T] ={ 48082212, 48101212, 52083112,54111134,56051295,
70072378, 71072372,74092313,77113044, 83011290 };
n = 10; // liczba pozycji z wpisanymi do tablicy numerami
textbackground(LIGHTGRAY);
clrscr();
textcolor(WHITE);
gotoxy(20,2);
cprintf("PrzeglÄ…danie skorowidza");
do // wprowadzenie numeru
{
gotoxy(5,4);
cprintf("Podaj numer: ");
textbackground(BLACK);
gotoxy(20,4);
cprintf(" XXXXXXXX ");
gotoxy(21,4);
wynik = scanf("%ld",&kod);
textbackground(LIGHTGRAY);
}
while ( wynik != 1);
nr = szukaj(numery,n,kod);
if ( nr != -1)
{
gotoxy(10,6);
cprintf("Numer %ld występuje na pozycji %d",kod, nr);
}
else // zwraca liczbÄ™ -1
{
gotoxy(10,6);
cprintf("Numer %ld nie występuje w skorowidzu", kod );
}
gotoxy(10,20);
cprintf("Naciśnij klawisz Enter");
getch();
}
9
/*T%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%W%
Q% FUNKCJA: szukaj Q%
Q% ZADANIE: sprawdzenie metodą podziału na połowy czy w uporządko- Q%
Q% wanej rosnąco tablicy t[] występuje wartość x. Q%
Q% Jeżeli istnieje (t[i] == x) -> zwraca wartość i Q%
Q% w przeciwnym razie zwróć wartość  1, Q%
Q% PARAMETRY: n - liczba elementów w tablicy t[], Q%
Q% t[] - tablica z danymi, Q%
Q% x - szukana liczba, Q%
Q% WYNIK: numer elementu z wartością szukana lub  1. Q%
Z%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%]%*/
int szukaj(long t[],int n,long int x)
{
int min = 0, sr, max = n - 1, wynik, brak = 1;
while((min <= max)&& brak))
{
sr = (min + max)/2; // cześć całkowita z dzielenia
if ( x < t[sr] ) // szukany numer w przedziale
max = sr - 1;
else
if( x > t[sr] ) // szukany numer w przedziale <środek, max>
min = sr + 1;
else
{
wynik = sr; // znaleziono szukany numer
brak = 0;
}
}
if(brak)
wynik = -1; // nie znaleziono
return(wynik);
}
Przykład cw07b
Zaprojektować algorytmy (rys. 7.3 oraz 7.4) a na ich podstawie funkcje do
transpozycji (funkcja zamien) oraz mnożenia (funkcja mnożenie) macierzy dwuwy-
miarowych.
Opis problemu.
MacierzÄ… liczbowÄ…1 o wymiarze m×n nazywa siÄ™ podwójny ciÄ…g liczbowy {aik},
gdzie i przybiera wartości liczbowe i = 1, 2, & , m, zaś k = 1, 2, & , n. Macierz zapisu-
je siÄ™ w postaci prostokÄ…tnej tablicy o m wierszach i n kolumnach.
a11 a12 ... a1k ... a1n
a21 a22 ... a2k ... a2n
... ... ... ... ... ...
A = [aik ]= [aik ] =
m×n
ai1 ai2 ... aik ... ain
... ... ... ... ... ...
am1 am2 ... amk ... amn
Element aik znajduje się na przecięciu i-tego wiersza i k-tej kolumny. Pierwszy z
dwu wskaz
ników stojący przy a oznacza numer wiersza, drugi zaś numer kolumny.
MacierzÄ… transponowanÄ… wzglÄ™dem macierzy A o wymiarze m×n i elementach
aik nazywa siÄ™ takÄ… macierz B o wymiarze n×m o elementach bik, dla której zachodzi
równość bik = aki (i = 1, & , n; k = 1, & m).
1
Tadeusz Trajdos-Wróbel  Matematyka dla inżynierów . WNT Warszawa 1965.
10
Transpozycja macierzy jest więc  obrotem macierzy dokoła przekątnej , tzn. tej
prostej, na której leżą wyrazy o obu jednakowych wskaz
nikach.
Macierz2 transponowaną względem A oznacza się AT.
a11 ... a1n a11 ... am1
A = ... ... ... , AT = ... ... ...
am1 .... amn an1 .... anm
Algorytm
transpozycja
1
i = 1
tak
2
i <= m
nie
3
k = 1
6
k = k+1
tak
4 5
k <= n
b[k][i] = a[i][k]
nie
7
i = i + 1
koniec
Rysunek 7.3. Algorytm transpozycji macierzy
Opis obiektów
" parametry: a[m][n] - tablica danych - macierz do transpozycji,
m - liczba wierszy tablicy a,
n - liczba kolumn tablicy a;
2
Transponowana macierz kolumnowa staje siÄ™ macierza wierszowÄ… i odwrotnie. Macierz symetryczna nie ulega
zmianie przy transpozycji. Macierz ukośnie symetryczna ulega wskutek transpozycji pomnożeniu przez mi-
nus jeden.
11
" wynik: b - transponowana macierz a;
" robocze: i - numer wiersza tablicy,
k - numer kolumny tablicy.
Iloczynem macierzy A o wymiarze m×p i macierzy B o wymiarze p×n nazywa
siÄ™ macierz C o wymiarze m×n której elementy cik wyrażąjÄ… siÄ™ za pomocÄ… elemen-
tów (czynników) aik i bik następująco:
p
cik = bjk
"aij
j=1
NawiazujÄ…c do terminologii rachunku wektorowego: element cik iloczynu macie-
rzy3 A i B jest iloczynem skalarnym i-tego wiersza pierwszej macierzy i k-tej kolumny
drugiej macierzy.
.. b1k ..
.. .. .. .. .. .. ..
.. b2k ..
..
.. .. ..
ai1 ai2 .. aij .. aip × = .. .. cik .. ..
.. bik ..
..
.. .. ..
.. .. .. .. .. .. ..
.. bpk ..
Warunek dotyczący wymiarów obu czynników mówi, że pierwsza macierz musi
mieć tyle kolumn, ile wierszy ma druga oraz, że iloczyn ma tyle wierszy, ile ma ich
pierwszy czynnik, zaÅ› tyle kolumn, ile ma ich drugi czynnik.
Opis obiektów
" parametry: a[m][p] - tablica danych - macierz A,
m - liczba wierszy tablicy a,
p - liczba kolumn tablicy a,
b[p][n] - tablica danych - macierz B,
p - liczba wierszy tablicy b,
n - liczba kolumn tablicy b;
" wynik: c[m][n] - macierz C - iloczyn macierzy A × B,
m - liczba wierszy tablicy c,
n - liczba kolumn tablicy c;
" robocze: i - numer wiersza tablicy a,
k - numer kolumny tablicy b,
j - numer kolumny tablicy a oraz wiersza tablicy b,
r - suma iloczynów  wartość elementu tablicy c.
3
Mnożenie macierzy nie jest przemienne. Z faktu AB = C nie wynika wykonalność działania BA, które jest
wykonalne wtedy, gdy A ma wymiar m×n, a B wymiar n×m.
12
Algorytm
mnozenie
1
i = 1
2
nie
i <= m
tak
3
k = 1
4 tak 5
k <= n r = 0
nie
6
j = 1
9
j = j + 1
tak
7
8
j <= p r = r + a[i][j] * b[j][k]
nie
10
c[i][k] = r
11
k = k + 1
12
i = i + 1
koniec
Rysunek 7.4. Algorytm mnożenia macierzy
13
Program
/*T%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%W%
Q% PROGRAM: macierz Q%
Q% ZADANIE: środowisko do testowania funkcji transponowania i Q%
Q% mnożenia macierzy, Q%
Q% WYNIKI: macierz tb  transponowana macierz ta, Q%
Q% tc  iloczyn macierzy ta i tb, Q%
Q% AUTOR: ................... Q%
Q% PLIK: cw07b.cpp Q%
Z%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%]%*/
#include
#include
#include
#include
#define MAXW 10 // max liczba wierszy tablicy
#define MAXK 10 // max liczba kolumn tablicy
#define MAX_LICZBA_STR 6 // max dlug liczby po konwersji na napis
/*T%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%W%
Q% FUNKCJA: transpozycja Q%
Q% ZADANIE: transpozycja macierzy t - zamiana wierszy z Q%
Q% odpowiadajacymi im kolumnami, Q%
Q% PARAMETRY: t1 - tablica danych - macierz do transpozycji, Q%
Q% lw, lk - liczba wierszy i kolumn tablicy t1, Q%
Q% WYNIK: t2 - transponowana macierz t1. Q%
Z%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%]%*/
void transpozycja(float t1[MAXW][MAXK],float t2[MAXK][MAXW],int lw, int lk)
{
int k, w;
for ( w = 1; w <= lw; w++)
for ( k = 1; k <= lk; k++)
t2[k-1][w-1] = t1[w-1][k-1];
}
/*T%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%W%
Q% FUNKCJA: mnozenie Q%
Q% ZADANIE: mnożenie macierzy a przez macierz b, Q%
Q% PARAMETRY: a[m][p] - macierz a o m wierszach i p kolumnach, Q%
Q% b[p][n] - macierz b o p wierszach i n kolumnach, Q%
Q% WYNIK: c[m][n] - macierz c o m wierszzch i n kolumnach. Q%
Z%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%]%*/
void mnozenie(float a[MAXW][MAXK],float b[MAXK][MAXW],float c[MAXW][MAXW],
short m, short p, short n)
{
int i,j,k;
float r;
for ( i = 1; i <= m; i++) // przeglad po wierszach
{
for (k = 1; k <= n; k++) // przeglad po kolumnach
{
r = 0;
for (j = 1; j <= p; j++)
r += a[i-1][j-1]*b[j-1][k-1]; // wiersz a x kolumna b
c[i-1][k-1] = r;
}
}
}
14
/*T%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%W%
Q% FUNKCJA: czytaj Q%
Q% ZADANIE: wprowadzanie danych do tablicy t. Ze względu na Q%
Q% niewielki obszar wyswietlania danych ich wartość jest Q%
Q% ograniczana do przedziału [-100.0 ... 100.0], Q%
Q% PARAMETRY: (xp,yp) - wsp lewego g. narożnika obszaru wyświetlania Q%
Q% lw, lk - liczba wierszy i kolumn tablicy t, Q%
Q% nazwa - nazwa tablicy (wyswietlana podczas wprowadzania, Q%
Q% WYNIK: t  tablica danych. Q%
Z%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%]%*/
void czytaj(float t[MAXW][MAXK], char nazwa, int lw, int lk, int xp, int
yp)
{
unsigned short w,k;
char wiersz[MAXK*MAX_LICZBA_STR],liczba[MAX_LICZBA_STR];
float s; // wporwadzany element tablicy
clrscr();
for (wiersz[0] = '\0',w = 1; w <= lw; wiersz[0] = '\0',w++) //wiersze
for (k = 1; k <= lk; k++) // kolumny
{
do
{
gotoxy(xp,yp); cprintf("%c[%d][%d] = ",nazwa,w,k);
textbackground(BLACK);
gotoxy(wherex()+10,wherey()); cprintf(" ");
gotoxy(wherex()-5,1); scanf("%f",&s); t[w-1][k-1] = s;
}
while(fabs(s)>=100.0);
textbackground(LIGHTGRAY);
sprintf(liczba,"%5.1f",s); // zapis liczby jako napis
strcat(wiersz,liczba); // kompletowanie wiersza danych
strcat(wiersz," ");
gotoxy(xp,yp+w+1); cprintf("%s",wiersz); //wiersz danych
}
}
/*T%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%W%
Q% FUNKCJA: pisz Q%
Q% ZADANIE: wyprowadzanie danych z tablicy t Q%
Q% PARAMETRY: (xp,yp) - wsp lewego g. narożnika obszaru wyświetlania Q%
Q% lw, lk - liczba wierszy i kolumn tablicy t, Q%
Q% nazwa - nazwa tablicy, Q%
Q% WYNIK: t  tablica danych. Q%
Z%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%]%*/
void pisz( float t[MAXW][MAXK], char nazwa[], int lw, int lk, int xp,
int yp)
{
unsigned short w,k;
char wiersz[MAXK*MAX_LICZBA_STR],liczba[MAX_LICZBA_STR];
clrscr();
cprintf(" ............ %s ............",nazwa);
gotoxy(xp+10,yp);
for (wiersz[0] = '\0',w = 1; w <= lw; wiersz[0] = '\0',w++) // wiersze
for (k = 1; k <= lk; k++) // kolumny
{
sprintf(liczba,"%5.1f",t[w-1][k-1]); // zapis liczby jako napis
strcat(wiersz,liczba);
strcat(wiersz," ");
gotoxy(xp,yp+w+1); cprintf("%s",wiersz);
}
}
15
/*T%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%W%
Q% FUNKCJA: czekaj Q%
Q% ZADANIE: wyświetla komunikat, a następnie oczekuje na reakcję Q%
Q% PARAMETRY: (x,y) - wsp. poczÄ…tku napisu Q%
Q% napis - wyświetlany komunikat. Q%
Z%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%P%]%*/
void czekaj(int x, int y, char napis[])
{
gotoxy(x, y);
cprintf("%s", napis);
while(kbhit()) // pobranie wszystkich znaków z wejścia
getch();
while(!kbhit()); // oczekiwanie na naciśniecie klawisza
getch();
}
//-------------------------------------------------------------------
main()
{
float ta[MAXW][MAXK],tb[MAXK][MAXW],tc[MAXW][MAXW]; // tablica liczb
int ilewA, ilekA, ilekB;
double r;
char linia[MAXK*MAX_LICZBA_STR],liczba[MAX_LICZBA_STR];
textbackground(LIGHTGRAY); clrscr();
textcolor(BLACK);
gotoxy(15,1); cprintf("Przykład transpozycji i mnożenia macierzy");
gotoxy(5,3); cprintf("Liczba [1...%d] wierszy A: ", MAXW);
scanf("%d",&ilewA);
gotoxy(5,4); cprintf("Liczba [1...%d] kolumn A: ", MAXK);
scanf("%d",&ilekA);
gotoxy(5,5); cprintf("Liczba [1...%d] kolumn B: ", MAXK);
scanf("%d",&ilekB);
window(10,7,70,24);
czytaj(ta,'A',ilewA,ilekA,6,1);
zamien(ta,tc,ilewA,ilekA);
pisz(tc,"A transponowana",ilekA,ilewA,6,1);
czekaj(20,24, "Naciśnij dowolny klawisz" );
czytaj(tb,'B',ilekA,ilekB,6,1);
mnozenie(ta, tb, tc, ilewA, ilekA,ilekB);
pisz(tc,"C = A X B",ilewA,ilekB,6,1);
window(1,1,80,25);
czekaj(20,24, "Naciśnij dowolny klawisz" );
}
Ćwiczenia
1. Jakie wartości zawierać będą zmienne po wykonaniu kodu.
main() main()
{ {
int y = 0, a[ ] = {3, -1, -4, 5}, i, n = 3; int y = 0, a[ ] = {1, 4, 0, -5, 0};
for ( i = n ; i >= 0; i = i - 1 ) int n = 0;
y += a[i] > 0 ? ; -a[i] : a[i]; while ( a[n] != 0 )
} y = y + a[n++];
// y = .................... i = ................... } // y = ........... n = ...........
2. Zdefiniowano tablicÄ™ int t[9][10].
" liczność elementów tablicy t wynosi: a) 10, b) 90, c) 9;
" ostatni wiersz tablicy t ma numer: a) 10, b) 9, c) 8;
" ostatnia kolumna tablicy t ma numer: a) 10, b) 9, c) 8.
3. Tablicę int t[M] o M elementach wypełniono liczbami całkowitymi. Zaprojektować
sekwencję instrukcji umożliwiających wyznaczenie numeru elementu zawierają-
16
cego liczbę najmniejszą oraz numeru elementu zawierającego liczbę największą.
Na podstawie wyznaczonych numerów elementów należy określić odległość po-
między tymi liczbami (tzn. ile elementów tablicy dzieli te liczby).
4. Tablicę int p[Z] o Z elementach wypełniono liczbami całkowitymi. Zaprojektować
sekwencję instrukcji umożliwiających zamianę zawartości elementów:
p[0] z p[Z-1], następnie: p[1] z p[Z-2] itd.
5. Dwuwymiarową tablicę k zainicjowano wartościami
int k[ ][ ] = { {1, 2, 3}, {4, 5, 6}, {10, 23, 13}, {7, 9, 8}};
" liczność wierszy tablicy k wynosi: a) 4, b) 3, c) 2;
" liczność kolumn tablicy k wynosi: a) 4, b) 3, c) 2;
" wartość 23 wskazuje element : a) k[2][1], b) k[3][2], c) k[2][3].
6. DwuwymiarowÄ… (kwadratowÄ…) tablicÄ™ int t[M][M] o M wierszach i M kolumnach
wypełniono liczbami całkowitymi. Zaprojektować sekwencję instrukcji umożliwia-
jącą wyliczenie sumy liczb z elementów leżących na przekątnej głównej (elementy
przekątnej głównej mają taki sam numer wiersza i kolumny t[0][0], t[1][1], t[2][2],
..., t[M-1][M-1]).
7. DwuwymiarowÄ… (kwadratowÄ…) tablicÄ™ int t[M][M] o M wierszach i M kolumnach
wypełniono liczbami całkowitymi. Zaprojektować sekwencje instrukcji umożliwia-
jącą wyliczenie sumy liczb z elementów leżących na przekątnej pomocniczej
(elementy przekÄ…tnej pomocniczej majÄ… indeksy t[0][M-1], t[1][M-2], t[2][M-3], ...,
t[M-1][0]).
8. Dwuwymiarową tablicę int t[M][M] o M wierszach i M kolumnach wypełniono licz-
bami całkowitymi. Zaprojektować sekwencję instrukcji umożliwiającą zamianę od-
powiadających sobie elementów leżących na przekątnej głównej i przekątnej po-
mocniczej (t[0][0] z t[0][M-1], ...).
17