Operacje na tablicach w C#
Opracował dr Robert Fidytek
Operacje na tablicach w C#
Opracował dr Robert Fidytek
Przegląd zagadnień
●
Ustawianie elementów na daną wartość
●
Kopiowanie tablic
●
Odwracanie tablicy
●
Sortowanie tablicy
●
Wyszukiwanie elementów w tablicy
●
Podsumowanie i zadania sprawdzające
3
Ustawianie elementów tablicy na
daną wartość
W czasie tworzenia tablicy możemy zainicjować ją dowolnymi wartościami.
W dalszej części programu w pojedynczej instrukcji możemy nadać wartość
tylko dla pojedynczego elementu:
for
(
int
i = index; i < index + iloscElementow; i++)
{ tablica[i] = wartość; }
Metoda Clear klasy Array ustawia wybrane elementy tablicy na wartość zero,
false lub null w zależności od typu podstawowego tablicy.
int
[] tablica = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
Array
.Clear(tablica, 3, 5);
//od 3 indeksu 5 elementów
foreach
(
int
el
in
tablica)
Console
.Write(
"{0}, "
, el);
//0, 1, 2, 3, 4, 5, 6, 7, 8, 9 – numery indeksów
//1, 2, 3,
0, 0, 0, 0, 0,
9, 10 - wartości elementów tablicy
4
Kopiowanie tablic
W wielu programach istnieje potrzeba dokonania kopii tablicy, w celu jej
przetworzenia, bez modyfikacji tablicy źródłowej.
typ[] tablica1 =
new
typ[rozmiar];
typ[] tablica2 =
new
typ[rozmiar];
...
tablica1=tablica2;
Zmienne tablicowe tablica1 i tablica2 będą odwoływać się do tego samego
obiektu tablicowego.
To nie jest kopiowanie tablic !!!
Co zostanie wypisane na ekranie?
int
[] tab1 =
new
int
[5] { 1, 2, 3, 4, 5 };
int
[] tab2 =
new
int
[5] { 6, 7, 8, 9, 10 };
tab2 = tab1;
tab1[0] = 99;
Console
.Write(
"{0}, "
, tab2[0]);
5
Kopiowanie tablic
W celu utworzenia dwóch odmiennych tablic, z których jedna będzie
zawierać kopię elementów drugiej tablicy należy wykonać poniższy kod:
typ[] źródło =
new
typ[rozmiar1];
typ[] cel =
new
typ[rozmiar2];
...
for
(
int
i = 0; i < rozmiar3; i++)
{ cel[i] = źródło[i]; }
W przypadku odwołania się do nieistniejącego elemantu tablicy zostanie
zgłoszony wyjątek IndexOutOfRangeException.
Czy tablice źródło i cel muszą być takich samych rozmiarów?
Jaką wartość może przyjąć rozmiar3 w powyższym przykładzie?
6
Kopiowanie tablic
Kopiowanie tablic za pomocą metody Copy klasy Array.
Array.Copy(tablica1,indeks1, tablica2, indeks2, ilość);
tablica1 – tablica źródłowa,
tablica2 – tablica docelowa,
indeks1 – indeks, od którego będą elementy kopiowane z tablicy1,
indeks2 – indeks, od którego będą elementy kopiowane do tablicy2,
ilość – ilość kopiowanych elementów.
Przykład:
int
[] tab1 = { 10, 11,
12, 13, 14, 15,
16, 17, 18, 19 };
int
[] tab2 = { 20, 21, 22,
23, 24, 25, 26,
27, 28, 29 };
Array
.Copy(tab1,
2
, tab2,
3
, 4);
foreach
(
int
el
in
tab2)
Console
.Write(
"{0}, "
, el);
//20, 21, 22, 12, 13, 14, 15, 27, 28, 29
7
Odwracanie tablicy
Odwracanie tablicy polega na zamianie kolejności elementów tablicy.
Pierwszy staje się ostatnim, a ostatni pierwszym.
Odwracanie tablicy za pomocą metody Reverse klasy Array.
Array.Reverse(tablica, indeks, ilość);
tablica – tablica źródłowa,
indeks – indeks, od którego elementy będą odwracane,
ilość – ilość odwracanych elementów.
Przykład:
int
[] tab = { 1, 2,
3, 4, 5, 6, 7,
8, 9, 10 };
Array
.Reverse(tab, 2, 5);
foreach
(
int
el
in
tab)
Console
.Write(
"{0}, "
, el);
//1, 2, 7, 6, 5, 4, 3, 8, 9, 10,
Array
.Reverse(tab);
//odwrócenie całej tablicy
foreach
(
int
el
in
tab)
Console
.Write(
"{0}, "
, el);
//10, 9, 8, 3, 4, 5, 6, 7, 2, 1,
Metoda Reverse
działa tylko z
tablicami
jednowymiarowymi.
Próba jej użycia
do tablicy
wielowymiarowej
spowoduje
zgłoszenie wyjątku
RankException.
8
Sortowanie tablicy
Sortowaniem nazywamy proces ustawienia elementów pewnego zbioru w
określonym porządku. Sortowanie wykonuje się w celu ułatwienia
ewentualnego wyszukiwania elementów danego zbioru.
W przypadku sortowania tablic bardzo ważna jest oszczędność pamięci.
Metodę sortowania, która nie potrzebuje tworzenia dodatkowej tablicy, do
której przenosimy elementy, nazywamy sortowaniem w miejscu.
W algorytmice jest szereg metod sortujących. Jedną z najpopularniejszych,
choć niezbyt wydajną, jest metoda nazywana sortowaniem bąbelkowym.
Sortowanie bąbelkowe polega na zamianie dwóch sąsiadujących ze sobą
elementów, jeżeli względem siebie zajmują nieprawidłowe miejsca.
9
Sortowanie bąbelkowe (bubble sort)
10
Sortowanie tablicy
Sortowanie tablicy za pomocą metody Sort klasy Array.
int
[] tab = { 34, 1, 17, 21, 5, 90, 45, 67 };
Array
.Sort(tab);
foreach
(
int
el
in
tab)
Console
.Write(
"{0}, "
, el);
//1, 5, 17, 21, 34, 45, 67, 90
Metoda Sort klasy Array wykorzystuje algorytm QuickSort. (Algorytm ten
zostanie omówiony na wykładzie 10.) Za pomocą metody Sort klasy Array
można sortować tylko tablice jednowymiarowe. Podczas próby sortowania
tablicy wielowymiarowej zostanie zgłoszony wyjątek RankException.
11
Wyszukiwanie elementu w tablicy
Wyszukiwanie indeksu elementu (o danej wartości) w tablicy za pomocą
metod IndexOf i LastIndexOf klasy Array.
Array.IndexOf(tablica, element);
Array.IndexOf(tablica, element, indeks_początkowy);
tablica – tablica źródłowa,
element – wyszukiwany element tablicy,
indeks_początkowy – indeks, od którego następuje wyszukiwanie.
Metoda IndexOf przeszukuje tablicę od początku, natomiast metoda
LastIndexOf natomiast przegląda tablicę od końca.
Przykład: Znalezienie indeksów wszystkich elementów o wartości 3 w tablicy tab.
int
[] tab ={ 1, 4, 3, 5, 3, 3, 2, 1, 3, 4 };
int
i =
Array
.IndexOf(tab, 3);
while
(i != -1)
{
Console
.Write(
"{0}, "
, i);
i =
Array
.IndexOf(tab, 3, i + 1);
}
//2, 4, 5, 8
Metody IndexOf i
LastIndexOf zwracają
indeks poszukiwanego
elementu lub -1 w
przypadku jego braku.
12
Wyszukiwanie binarne
W przypadku, gdy chcemy przeszukiwać tablice posortowane, wydajność
operacji wyszukiwania można znacznie poprawić, stosując wyszukiwanie
binarne (połówkowe).
W przypadku wyszukiwania binarnego wybraną wartość porównujemy ze
środkowym elementem tablicy.
Jeżeli wartość środkowego elementu jest równa wybranej wartości,
przerywamy wyszukiwanie. Element środkowy jest szukanym elementem.
W przypadku, gdy szukana wartość jest mniejsza od wartości środkowego
elementu, żadaną wartość próbujemy znaleźć w pierwszej połowie tablicy.
Natomiast, gdy wybrana wartość jest większa od wartości środkowego
elementu, żądaną wartość próbujemy znaleźć w drógiej połowie tablicy.
Oczywiście do wyszukiwania żądanej wartości w poszczególnych częściach
tablicy stosujemy wyszukiwanie połówkowe. Wyszukiwanie kończymy w
momencie znalezienia żadanej wartości lub, gdy w wyniku podziału
otrzymamy pustą podtablicę, co jest równoważne z brakiem elementu o
żądanej wartości w przeszukiwanej tablicy.
13
Wyszukiwanie binarne
Wyszukiwanie binarne indeksu elementu (o danej wartości) w tablicy jest
realizowane za pomocą metody BinarySearch klasy Array. Metoda ta zwraca
numer indeksu wyszukiwanego elementu lub wartość ujemną, gdy tablica nie
zawiera wyszukiwanego elemantu.
Przykład:
int
[] tab ={ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int
i =
Array
.BinarySearch(tab, 2);
Console
.Write(
"i = {0}, "
, i);
Ćwiczenie:
Załóżmy, że pomyślałem dowolną liczbę naturalną z przedziału od 1 do 100 i
będę odpowiadał na pytania tylko “tak” lub “nie”.
Ile co najwyżej trzeba zadać pytań, aby zawsze odgadnąć pomyślaną przeze
mnie liczbę?
A gdybym pomyślał liczbę od 1 do 1 000 000? ...
14
Zadanie 1
//Jakie błędy popełniono w poniższym kodzie programu?
int
[,] tab1 = { 1, 1, 2, 2, 3, 3, 4, 4, 5 }
int
[,] tab2 = { 6, 6, 7, 7, 8, 8, 9, 9, 0, 0 }
Array
.Copy(tab1, 4, tab2, 5, 6);
foreach
(
int
el
in
tab2)
Console
.Write(
"{0}, "
, tab2);
15
Zadanie 2
//Co zostanie wypisane na ekranie?
const
int
N = 10;
int
[] tab =
new
int
[N] { 1, 3, 5, 7, 9, 0, 2, 4, 6, 8 };
int
i=-1, elem;
while
(++i < N / 2)
{
elem = tab[i];
tab[i] = tab[N - 1 - i];
tab[N - 1 - i] = elem;
}
foreach
(
int
el
in
tab)
Console
.Write(
"{0}, "
,el);
16
Zadanie 3
//Co realizuje poniższy kod programu?
const
int
N = 10;
int
[] tab =
new
int
[N];
int
elem;
Random
r =
new
Random
();
for
(
int
i = 0; i < N; i++) tab[i] = r.Next(1, 101);
for
(
int
j = 0; j < N; j++)
for
(
int
k = j; k < N; k++)
if
(tab[j] < tab[k])
{
elem = tab[j];
tab[j] = tab[k];
tab[k] = elem;
}
foreach
(
int
el
in
tab)
Console
.Write(
"{0}, "
,el);
17
Zadanie 4
//Jaką wartość osiągnie zmienna j?
//Co realizuje poniższy program?
const
int
I = 1;
int
[] tab =
new
int
[] {1,2,1,3,5,1,2,2,1};
int
i=-1, j = 0;
while
((i=
Array
.IndexOf(tab,I,i+1)) != -1) j++;
Console
.WriteLine(
"j={0}"
,j);
18
Zadanie 5
//Co zostanie wypisane na ekranie?
int
[] tab =
new
int
[] {9, 3, 10, 7, 1, 5, 2, 6, 4, 8,};
foreach
(
int
el
in
tab)
Console
.Write(
"{0,2}, "
, el);
Console
.Write(
"\n"
);
Array
.Clear(tab, 1, 2);
foreach
(
int
el
in
tab)
Console
.Write(
"{0,2}, "
, el);
Console
.Write(
"\n"
);
Array
.Sort(tab);
foreach
(
int
el
in
tab)
Console
.Write(
"{0,2}, "
, el);
Console
.Write(
"\n"
);
Array
.Reverse(tab, 4, 3);
foreach
(
int
el
in
tab)
Console
.Write(
"{0,2}, "
, el);
Console
.Write(
"\n"
);
Array
.Copy(tab, 2, tab, 3, 4);
foreach
(
int
el
in
tab)
Console
.Write(
"{0,2}, "
,el);
1
2
3
4
5
6
7
8
9
10
11
12
13
14