Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych.
Autor artykułu: mgr Jerzy Wałaszek, wersja1.0

obrazek

Tablice w języku C++

Tablica (ang. array) jest strukturą danych zbudowaną z ciągu elementów tego samego typu. Elementy tablicy zajmują w pamięci komputera spójny obszar. Tablicę w języku C++ deklarujemy następująco:

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

Przykład:

int a[10]; // tablica o nazwie a zawierająca 10 elementów przechowujących liczbę typu int double x[100]; // tablica x o 100 elementach typu double

Elementy tablicy są numerowane. Numer elementu nosi nazwę indeksu. Indeksy w języku C++ rozpoczynają się od wartości 0. Zatem poniższa deklaracja tablicy:

int a[10];

tworzy 10 elementów:

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]

Zwróć uwagę, iż nie ma tutaj elementu a[10]. Typowym błędem w języku C++ jest utworzenie tablicy o n elementach:

int z[n];

a następnie odwoływanie się do elementu z[n], którego w tablicy nie ma. Kompilator zwykle nie zgłosi błędu. Ponieważ elementy znajdują się kolejno obok siebie w pamięci, to kompilator wyliczy adres elementu z[n] i wykona na nim operację. Ponieważ element jest poza obszarem tablicy, to zwykle w tym miejscu program przechowuje inne dane, a to może doprowadzić do trudnych w wykryciu błędów w działaniu programu - błąd objawia się w zmiennej, z którą nic nie robiliśmy - to zapis do tablicy spowodował jej modyfikację.

Elementy tablicy traktuje się jak zwykłe zmienne proste, zatem można je używać w operacjach przypisania i w wyrażeniach:

... int a[5]; // tworzymy tablicę 5 elementową ... for(i = 0; i < 5; i++) a[i] = 12 - 3 * i;


for(i = 0; i < 5; i++)

  cout << a[i] << " ";

cout << endl;

...

W powyższym programie tworzymy tablicę 5 elementową liczb całkowitych. Następnie w pętli umieszczamy w kolejnych elementach tej tablicy:

a[0] ← 12 a[1] ← 9 a[2] ← 6 a[3] ← 3 a[4] ← 0

a następnie wyświetlamy zawartość kolejnych elementów tablicy. W oknie konsoli powstanie wydruk:

12 9 6 3 0

Dzięki indeksom te same operacje możemy wykonywać na innych elementach tablicy, np. w pętli. Znacznie ułatwia to przetwarzanie dużej ilości danych.

Podstawowe operacje na tablicach

Wstawianie elementu do tablicy

Przez wstawienie elementu do tablicy rozumiemy umieszczenie go pomiędzy elementami znajdującymi się w tablicy. W operacji tej musimy najpierw przesunąć o jedną pozycję w górę wszystkie elementy o indeksach większych lub równych indeksowi wstawianego elementu, aby zrobić dla niego miejsce w tablicy. Ostatni element jest zawsze tracony.

Dane wejściowe:

n	-	liczba elementów w tablicy
T[ ]	-	tablica n elementowa, w której wykonujemy wstawianie
e	-	wstawiany element
k	-	pozycja wstawiania elementu e w tablicy T[ ], 0 ≤ k < n

Dane wyjściowe

T[ ]

tablica n elementowa ze wstawionym elementem e na pozycji k-tej

Lista kroków:

K01:	Dla i = n-1, n-2,...,k+1: wykonuj T[i] ← T[i-1]	; przesuwamy elementy ponad k o jedną pozycję w górę
K02:	T[k] ← e	; na zwolnionej pozycji k-tej wstawiamy element e
K03:	Zakończ

Operacja posiada liniową klasę złożoności obliczeniowej O(n).

Program:

// Tablice - wstawianie elementu
//------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

main()
{
  int a[10];

// wypełniamy tablicę a kolejnymi liczbami nieparzystymi

  for(int i = 0; i < 10; i++) a[i] = 1 + 2 * i;
  
// wyświetlamy indeksy elementów

  cout << "elementy :  ";
  for(int i = 0; i < 10; i++) cout << "  a[" << i << "]";
  cout << endl;
  
// wyświetlamy tablicę przed wstawieniem elementu

  cout << "przed    : ";
  for(int i = 0; i < 10; i++) cout << setw(6) << a[i];
  cout << endl;

// na pozycji 3 wstawiamy element o wartości 123
  
  for(int i = 9; i > 3; i--) a[i] = a[i - 1];
  a[3] = 123;
  
// wyświetlamy tablicę po wstawieniu elementu
  
  cout << "po       : "; 
  for(int i = 0; i < 10; i++) cout << setw(6) << a[i];
  cout << endl << endl;
    
  system("PAUSE");
}

Wstawianie elementu 123 do tablicy na pozycji 3

elementy : a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
przed : 1 3 5 7 9 11 13 15 17 19
po : 1 3 5 123 7 9 11 13 15 17

Usuwanie elementu z tablicy

Aby usunąć element z tablicy, przesuwamy o 1 pozycję w dół wszystkie elementy o indeksach większych od indeksu elementu usuwanego. W ostatnim elemencie tablicy umieszczamy zero.

Dane wejściowe:

n	-	liczba elementów w tablicy
T[ ]	-	tablica n elementowa, w której wykonujemy usunięcie
k	-	pozycja elementu do usunięcia

Dane wyjściowe

T[ ]

tablica n elementowa z elementem usuniętym na pozycji k

Lista kroków:

K01:	Dla i = k, k+1,...,n-2: wykonuj T[i] ← T[i+1]	; przesuwamy elementy ponad k o jedną pozycję w dół
K02:	T[n-1] ← 0	; na ostatniej pozycji umieszczamy 0
K03:	Zakończ

Operacja posiada liniową klasę złożoności obliczeniowej O(n).

Program:

// Tablice - usuwanie elementu
//------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

main()
{
  int a[10];

  cout << "Usuwanie elementu z tablicy na pozycji 3\n\n";
  
// wypełniamy tablicę a kolejnymi liczbami nieparzystymi

  for(int i = 0; i < 10; i++) a[i] = 1 + 2 * i;
  
// wyświetlamy indeksy elementów

  cout << "elementy :  ";
  for(int i = 0; i < 10; i++) cout << "  a[" << i << "]";
  cout << endl;
  
// wyświetlamy tablicę przed usunięciem elementu

  cout << "przed    : ";
  for(int i = 0; i < 10; i++) cout << setw(6) << a[i];
  cout << endl;

// usuwamy element z pozycji 3
  
  for(int i = 3; i < 9; i++) a[i] = a[i + 1];
  a[9] = 0;
  
// wyświetlamy tablicę po usunięciu elementu
  
  cout << "po       : "; 
  for(int i = 0; i < 10; i++) cout << setw(6) << a[i];
  cout << endl << endl;
    
  system("PAUSE");
}

Usuwanie elementu z tablicy na pozycji 3

elementy :  a[0]  a[1]  a[2]  a[3]  a[4]  a[5]  a[6]  a[7]  a[8]  a[9]
przed    :    1     3     5     7     9    11    13    15    17    19
po       :    1     3     5     9    11    13    15    17    19     0

Zamiana miejscami dwóch elementów

W różnych algorytmach sortujących występuje konieczność zamiany miejscami wybranych elementów tablicy. Operację wykonujemy w trzech krokach wykorzystując zmienną pomocniczą x.

Dane wejściowe:

T[ ]	-	tablica n elementowa, w której wykonujemy usunięcie
k₁,k₂	-	pozycje zamienianych elementów

Dane wyjściowe

T[ ]

tablica n elementowa z zamienionymi elementami na pozycjach k₁ i k₂.

Lista kroków:

K01:	x ← T[k₁]	; zapamiętujemy chwilowo pierwszy element
K02:	T[k₁] ← T[k₂]	; w pierwszym elemencie umieszczamy drugi element
K03:	T[k₂] ← x	; w drugim elemencie umieszczamy zapamiętany pierwszy element
K04:	Zakończ

Operacja posiada stałą klasę złożoności obliczeniowej O(1).

Program:

// Tablice - zamiana dwóch elementów
//----------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

main()
{
  int a[10];

  cout << "Zamiana elementu 3 z elementem 6\n\n";
  
// wypełniamy tablicę a kolejnymi liczbami nieparzystymi

  for(int i = 0; i < 10; i++) a[i] = 1 + 2 * i;
  
// wyświetlamy indeksy elementów

  cout << "elementy :  ";
  for(int i = 0; i < 10; i++) cout << "  a[" << i << "]";
  cout << endl;
  
// wyświetlamy tablicę przed zamianą elementów

  cout << "przed    : ";
  for(int i = 0; i < 10; i++) cout << setw(6) << a[i];
  cout << endl;

// zamieniamy miejscami element 3 z elementem 6
  
  int x = a[3];
  a[3] = a[6];
  a[6] = x;
  
// wyświetlamy tablicę po zamianie elementów
  
  cout << "po       : "; 
  for(int i = 0; i < 10; i++) cout << setw(6) << a[i];
  cout << endl << endl;
    
  system("PAUSE");
}

Zamiana elementu 3 z elementem 6

elementy :  a[0]  a[1]  a[2]  a[3]  a[4]  a[5]  a[6]  a[7]  a[8]  a[9]
przed    :    1     3     5     7     9    11    13    15    17    19
po       :    1     3     5    13     9    11     7    15    17    19

Zadania

Opracuj algorytm odwracający kolejność elementów tablicy.

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

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

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe