FANDOM



Tablice.

Tablica jest strukturą danych. Tablica to ciągła grupa komórek w pamięci. Grupa ta posiada wspólną nazwę. Komórki pogrupowane są w typ danych, który określamy przy definicji tablicy. Do poszczególnych elementów tablicy odwołujemy się poprzez określenie nazwy tablicy i numeru pozycji odpowiedniego elementu. Elementy tablicy numerujemy od zera ( pierwszym elementem jest element zerowy). Chcąc zdefiniować tablicę 20 liczb całkowitych piszemy:

long tablicaLong[20];

Poszczególne elementy będziemy numerować od 0 do 19. Chcąc się odwołać do pierwszego elementu tablicy piszemy:

tablicaLong[0];

Numer elementu ujmowany w nawiasy kwadratowe nazywany jest indeksem. Indeks musi być liczbą całkowitą lub wyrażeniem całkowitym.

Deklaracja tablic.

Tablice zajmują miejsce w pamięci. Przy deklaracji tablicy należy określić typ elementów tablicy oraz ich ilość. Posiadając tę informację kompilator może zarezerwować odpowiednią ilość komórek pamięci. Deklaracja tablicy ma postać:

 typ_elementów nazwa_Tablicy [ ilość_elementów ];

Kilka tablic tego samego typu może być deklarowanych w tej samej linii:

int tablicaInt1 [20], tablicaInt [50];

W linii tej deklarujemy dwie tablice typu int. Jedną składającą się z 20 elementów, a drugą z 50 elementów.

Inicjowanie tablic.

Elementy tablicy mogą być inicjowane w deklaracji tablicy przez umieszczenie po niej znaku równości i rozdzielonej przecinkami listy wartości inicjujących ujętej w nawiasy klamrowe.

int tablicaInt[5]={1,2,3,4,5};

Jeśli wartości inicjujących będzie mniej niż elementów tablicy, pozostałe elementy będą zainicjowane wartością zero.

int tablicaInt[5]={5}; 

Deklaruje tablicę typu int, która ma pięć elementów. Pierwszy element tej tablicy jest jawnie inicjowany wartością 5. Pozostałe elementy tej tablicy są inicjowane niejawnie wartością zero. Do inicjacji tablic możemy również wykorzystać pętle for.

#include <iostream>
#define wTab 100
using namespace std;
int tablicaInt[wTab];
int i=0;
int x=0;
int main()
{

  for(; i<wTab; i++)
    tablicaInt[i]=i;

  cout<<"Tablica została zainicjowana liczbami:"<<endl;

  for(; x<wTab; x++)
    cout<<"Numer elementu :"<<i<<" wartosc elementu "<<tablicaInt[i]<<endl;

  return 0;
} 

Linia:

#define wTab 100

stosuje dyrektywę preprocesora #define w celu zadeklarowania stałej preprocesora wTab, której wartość wynosi 100. Stałe takie muszą być inicjowane wyrażeniem stałym i nie mogą być później modyfikowane. Stałe symboliczne nazywane są również zmiennymi tylko do odczytu. Określając liczbę elementów tablicy kompilator oczekuje wyrażenia całkowitego i stałego, dlatego możemy użyć stałej preprocesora. Wykorzystywanie stałych preprocesora do określenia wielkości tablic daje programom większą skalowalność. Nic nie stoi na przeszkodzie aby zamiast liczby 100 elementów typu int inicjowane było 1000 elementów poprzez zmianę stałej preprocesora. Gdybyśmy nie używali stałej preprocesora musielibyśmy zmienić program w 3 miejscach. Możemy się zatem przekonać, jak wygląda kod pod bibilioteką iostream po przetworzeniu przez preprocesor:

using namespace std;
int tablicaInt[100];
int i=0;
int x=0;
int main()
{

  for(; i<100; i++)
    tablicaInt[i]=i;

  cout<<"Tablica została zainicjowana liczbami:"<<endl;

  for(; x<100; x++)
    cout<<"Numer elementu :"<<i<<" wartosc elementu "<<tablicaInt[i]<<endl;

  return 0;
}

Zniknęły dyrektywy preprocesora, w miejsce słowa "wTab" została wstawiona liczba 100, czyli wartość stałej.

Wykorzystywanie tablic.

Zostałeś poproszony o napisanie programu, który zliczałby odpowiedzi na ankietę zamieszczoną w pewnym piśmie. Oto pytania, jakie zadano czytelnikom:

Co Twoim zdaniem powinno się znaleźć w naszym piśmie ?

  1. recenzje gier,
  2. opisy sprzętu,
  3. kursy programowania,
  4. nowości ze świata komputerów.

A oto program realizujący to zadanie:

#include <iostream>
//inicjalizujemy stałą preprocesora określającą wielkość tablicy
//tablica ma 4 elementy
#define wTab 4
using namespace std;
//inicjalizacja zmiennych
//najpierw inicjalizujemy tablicę liczb typu int o nazwie tabOdp
int tabOdp[wTab]={0}, licz;
int main()
{

    // pętla do..while nie ogranicza ilości udzielonych odpowiedzi i gwarantuje conajmniej jedno przejście
    do
    {
        // wyświetlamy informacje dla użytkownika
        cout << endl << "Co Twoim zdaniem powinno się znalezc w naszym pismie ?" << endl
  	    	 << "1. recenzje gier" << endl << "2. opisy sprzętu," << endl <<"3. kursy programowania,"<<endl
  		     << "4. nowości ze świata komputerów." << endl << "Wprowadz -1 aby zakonczyc.\t";

        cin >> licz;

        // analiza odpowiedzi wprowadzonej przez uzytkownika
        if(licz>0 && licz<5)
           
        // zliczenie odpowiedzi indeks tablicy jest obliczany na przez wyrażenie licz-1
        // zwiększenie elementu tablicy przez operator ++
            ++tabOdp[licz-1];
        else
            if (licz == -1) 
               break;
            else
               cout << endl << "Wprowadziles bledna odpowiedz";
     }
     while (licz != -1);
     cin.get();

    // wyświetlamy wyniki
    cout<<endl<<"Wynik ankiety:"<<endl
  		<<"1. recenzje gier:"<<tabOdp[0]<<endl<<"2. opisy sprzętu :"<<tabOdp[1]
  		<<endl<<"3. kursy programowania:"<<tabOdp[2]
  		<<endl<<"4. nowości ze świata komputerów:"<<tabOdp[3]<<endl;
    cin.get();
    return 0;
}

Generowanie liczb losowych.

Do generowania liczb losowych służy funkcja rand(). Funkcja ta generuje liczbę całkowitą między 0 i RAND_MAX (stałą symboliczną zdefiniowaną w pliku nagłówkowym cstdlib). Jeśli funkcja ta wybiera liczby naprawdę losowo to każda z nich ma taką samą szansę bycia trafioną. Zakres wartości wytwarzanych przez funkcję rand() jest bardzo duży. Zwykle nie potrzebujemy aż tylu wartości. Na przykład program, który będzie symulował rzuty kostką będzie potrzebował sześć wartości. Chcąc wytworzyć liczby całkowite w zakresie od 0 do 5 używamy dzielenia modulo (%) w połączeniu z funkcją rand:

 
1+rand()%6

Nazywamy to skalowaniem. Liczba 6 jest czynnikiem skalowania. A liczba 1 jest wartością przesunięcia. Wartość przesunięcia to liczba równa pierwszej liczbie w pożądanym zakresie kolejnych liczb całkowitych.

Oto program symulujący rzut kostką 20 razy:

#include <iostream>
#include <cstdlib>
using namespace std;
short int i=1;
int main()
{
	for(; i<21; i++)
		cout<<(1+rand()%6)<<endl;

	cout<<endl;

	return 0;
}

Jeśli uruchomisz ten program kilka razy zobaczysz, że wyświetlana jest taka sama sekwencja wartości. Jest to spowodowane tym, że funkcja rand() generuje liczby pseudolosowe. Konieczne w tym wypadku jest losowanie, które jest realizowane przez funkcje srand(). Funkcja srand() pobiera jako argument liczbę unsigned int i wywołuje funkcję rand() do rozpoczęcia wytwarzania różnych sekwencji liczb losowych. Jeżeli za każdym razem chcemy losować bez konieczności wprowadzania liczby bazowej do generowania liczb losowych, możemy użyć wyrażenia:

srand(time(0));

Wyrażenie to odczytuje zegar, aby otrzymać wartość bazową dla generowania liczb losowych. Funkcja time z argumentem 0 zwraca czas jaki upłynął w sekundach od 1 stycznia 1970 roku.

Oto program zliczający rzut kostką 5000 razy. Wykorzystujący w tym celu tablicę:

#include <iostream>
#include <cstdlib>
#define wTab 7
using namespace std;
int rzut=1;
int scianka=1;
int czestosc[wTab]={0};


int main()
{
	srand(time(0));
	//ignoruj element zero w tablicy
	for(; rzut<=5000; rzut++)
		++czestosc[1+rand()%6];

	cout<<"Scianka : "<<" czestosc wystepowania "<<endl;
	for(;scianka<wTab;scianka++)
		cout<<scianka<<" "<<czestosc[scianka]<<endl;

	cin.get();
	return 0;
}

Przekazywanie tablic do funkcji.

Chcąc przekazać tablicę do funkcji piszemy nazwę tablicy bez nawiasów np.:

#include <iostream>
#define wTab 10
using namespace std;
int tab[ wTab ]={1,4,7,5,100,150,9,34};
int i=0;
template <typename T>
void wyswietlTablice (T tablica[])
{
  for(; i<wTab; i++)
    cout<<"Element tablicy : "<<(i+1)
        <<" Wartosc elementu :"<<tablica[i]<<endl;
}
int main()
{


	cout<<"Wywolanie funkcji wyswietlTablice"<<endl;

	wyswietlTablice(tab);
	cin.get();
	return 0;
}

C++ automatycznie przekazuje tablice do funkcji przez referencję(a jak się przekonamy później wskaźnik), w związku z tym funkcja może modyfikować elementy tablicy bezpośrednio. Jest to spowodowane względami wydajnościowymi. Jeśli tablicę przekazywalibyśmy przez wartość. Kopiowanie wszystkich elementów tablicy zabierałoby dużo czasu i potrzebowałoby dużo pamięci. Poszczególne elementy tablicy są przekazywane są przez wartość w związku z tym funkcja nie modyfikuje elementu bezpośrednio, a operuje na kopii wartości bezpośrednio.

Poniższy program demonstruje przekazywanie tablic i poszczególnych elementów do tablic:

#include <iostream>
#define wTab 10
using namespace std;
//tutaj deklarujemy i inicjujemy zmienne globalne
//to tylko przykład - można to zapisać inaczej
int tab[ wTab ]={1,4,7,5,100,150,9,34};
short int i=0, x=0;
//typ danych T
template <typename T>
//metody używające typu T
void wyswietlTablice (T tablica [])
{
	for(; i<wTab; i++)
		cout<<"Element tablicy : "<<(i+1)<<endl<<"Wartosc elementu : "<<tablica[i]<<endl;
}
void modyfikujTablice (T tablica [])
{
	for(; x<wTab; x++)
		tablica[x]+=10;
}

void modyfikujElement (T &a)
{
	a*=2;
}
//metoda main
int main()
{
  cout<<"Wywolanie funkcji wyswietlTablice przed modyfikacja"<<endl;
  wyswietlTablice(tab);

  modyfikujTablice(tab);

  cout<<"Tablica po modyfikacji:"<<endl;
  wyswietlTablice(tab);

  cout<<"Element 3 tablicy przed modyfikacją:"<<tab[3]<<endl;
  modyfikujElement(tab[3]);
  cout<<"Element 3 tablicy po modyfikacji: "<<tab[3]<<endl<<"Naciśnij ENTER...";
  cin.get();

  return 0;
}


Sortowanie tablic.

Sortowanie danych jest jednym z najważniejszych zadań obliczeniowych. Powstało wiele wydajnych algorytmów, których zadaniem jest sortowanie tablic. Tutaj przedstawię dwa najprostsze algorytmy sortowania: bąbelkowe i przez selekcję.

Sortowanie bąbelkowe.

Sortowanie bąbelkowe wymaga kilku przejść przez całą tablicę. W każdym przejściu tablicy kolejne pary są porównywane. Jeżeli para znajduje się w porządku rosnącym lub wartości są identyczne ich wartości są pozostawione. Jeśli para znajduje się w porządku malejącym, wartości zamieniane są miejscami.

#include <iostream>
#define wTab 10
using namespace std;
int tab[ wTab ]={1,4,7,5,100,150,9,34,-1,120};
int i=0;
int temp;
int x=0;
int j=0;
template <typename T>
void wyswietlTablice (T tablica [])
{
	for(; i<wTab; i++)
		cout<<"Element tablicy : "<<(i+1)<<" Wartosc elementu : "<<tablica[i]<<endl;
}

void sortBab (T tablica [] )
{
	for (; x<wTab-1; x++)
	{
		for (; j<wTab-i; j++)
		{
			if(tablica[j]>tablica[j+1])
			{
				temp=tablica[j];
				tablica[j]=tablica[j+1];
				tablica[j+1]=temp;
			}
		} // for(..
	} // for(..
}
int main ()
{
	cout<<"Tablica przed posortowaniem :\n";
	wyswietlTablice(tab,wTab);
	sortBab(tab,wTab);
	cout<<"Tablica po posortowaniu :\n";
	wyswietlTablice(tab,wTab);
	cin.get();
	return 0;
}

Sortowanie przez selekcję.

Algorytm ten jest następujący:

  1. należy znaleźć najmniejszy element i zmienić go miejscem z pierwszym,
  2. znaleźć drugi element w kolejności i zamienić go miejscem w drugim,
  3. kontynuować krok drugi aż do posortowania.
#include <iostream>
#define wTab 10
using namespace std;
const int wTab=10;
int tab[ wTab ]={1,4,7,5,100,150,9,34,-1,120};
template <typename T>
int i=0,
x=0,
j=0,
min,
temp;
void wyswietlTablice (T tablica [])
{
	for(int i=0; i<wTab; i++)
  	cout<<"Element tablicy : "<<(i+1)<<" Wartosc elementu : "<<tablica[i]<<endl;
}
void zmien (T tablica [], int indeks, int indeks1)
{
	temp=tablica[indeks];
	tablica[indeks]=tablica[indeks1];
	tablica[indeks1]=temp;
}
void sortSel (T tablica [])
{

  for (; x<wTab; x++)
	{
  	min=i;
	  for(j=i+1; j<wTab; j++)
		{
  		if(tablica[j]<tablica[min])
			{
 			 	min=j;
			}
		}
	  zmien(tablica,i,min);
  }
}



int main ()
{
	cout<<"Tablica przed posortowaniem :\n";
	wyswietlTablice(tab);
	sortSel(tab);
	cout<<"Tablica po posortowaniu :\n";
	wyswietlTablice(tab);
	cout<<"Nacisnij ENTER"<<endl;
	cin.get();
	return 0;
}

Tablice wielowymiarowe.

W C++ tablice mogą być wielowymiarowe. Typowym zastosowaniem tablic wielowymiarowych jest przedstawienie informacji pogrupowanych w wierszach i kolumnach. W tablicach wielowymiarowych chcąc wskazać element tablicy musimy określić dwa indeksy : pierwszy oznacza wiersz, a drugi kolumnę.

Tablice wymagające dwóch indeksów do zidentyfikowania określonego elementu są nazywane tablicami dwuwymiarowymi. Tablice wielowymiarowe mogą mieć więcej niż dwa indeksy. Kompilatory C++ dopuszczają 12 indeksów tablicy.

Wielowymiarowa tablica może być a zainicjowana w podobny sposób do tablicy jednowymiarowej. Chcąc utworzyć dwuwymiarową tablicę typu int, mającą dwa wiersze i dwie kolumny napiszemy (jednocześnie incjując):

int tabInt[2][2]={{1,1},{2,2}};

Wartości w nawiasach klamrowych zgrupowane są według wierszy. Chcąc przekazać tablicę wielowymiarową do funkcji musimy określić wielkość drugiego i ewentualnie następnych indeksów. Kompilator używa tych wielkości do określenia położenia w pamięci elementów wielowymiarowej tablicy. Przykładowo chcąc przekazać do funkcji wyswTab() tablicę tabInt musielibyśmy tą funkcję zadeklarować:

void wyswTab(int [][2],int );

A pierwsza linia definicji funkcji wyglądałaby tak:

 void wyswTab(int tablica[][2], int wielkosc)

Ćwiczenia.

  1. Sortowanie bąbelkowe jest mało wydajne - dopracuj ten algorytm. Aby poprawić wydajność (przecież dane w tablicy mogą być już w całości lub w części posortowane), zmodyfikuj sortowanie tak, aby na końcu każdego przebiegu sprawdzano czy zostały dokonane jakieś zmiany, jeżeli nie - dane są już uporządkowane i należy zakończyć sortowanie.
  2. Pewne przedsiębiorstwo płaci swoim sprzedawcom wynagrodzenie zależnie od wartości sprzedaży. Sprzedawcy otrzymują 690 zł + 10% swojej sprzedaży brutto w tym miesiącu. Napisz program obliczający pensję sprzedawcy w zależnośći od sprzedaży.
  3. Napisz algorytm sortowania przez selekcję w sposób rekurencyjny.
  4. Napisz program symulujący rzuty dwiema kostkami 100 razy. Powinien on wykorzystywać funkcję rand() w połączeniu z funkcją srand(). Suma tych 36 (od 2 do 12) kombinacji winna być wyświetlona w wierszach i kolumnach jak poniżej.
1 2 3 4 5 6
1
2
3
4
5
6

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Więcej z Fandomu

Losowa wiki