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