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
k1,k2  - pozycje zamienianych elementów

 

Dane wyjściowe

T[ ]  -  tablica n elementowa z zamienionymi elementami na pozycjach k1 i k2.

 

Lista kroków:

K01: x ← T[k1] ; zapamiętujemy chwilowo pierwszy element
K02: T[k1] ← T[k2] ; w pierwszym elemencie umieszczamy drugi element
K03: T[k2] ← 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.



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

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