Operacje na tablicach

Przegląd zagadnień

Na tablicach wykonuje się szereg standardowych operacji. W tym module studenci poznają różne sposoby implementacji tych operacji oraz gdzie one zostały zaimplementowane w .Net Framework. Operacje które zostaną przedstawione w tym module to:

• Ustawianie wartości elementów tablicy (po utworzeniu tablicy).

• Kopiowanie wartości elementów jednej tablicy do drugiej tablicy.

• Odwracanie tablicy.

• Ustawianie elementów tablicy w odpowiedniej kolejności - sortowanie.

• Sprawdzanie czy tablica zawiera element o danej wartości.

Uwaga:
W rozdziale tym nagminnie używane jest pojęcie metody. Pojęcie to jest dokładnie omawiane modułach 8, 9 i 10 tego kursu.

Ustawianie elementów na daną wartość

W czasie tworzenia tablicy możemy zainicjalizować jej elementy dowolnymi wartościami. W dalszej części programu w pojedynczej instrukcji możemy nadać wartość tylko pojedynczemu elementowi tablicy. W programie często istnieje potrzeba nadania pewnej grupie elementów tablicy określonej wartości. Poniższy kod przedstawia jeden z sposobów implementacji tego zadania:

...
for(int i = index; i < index + iloscElementow; i++)
{
tab[i] = wartosc;
}
...

Zmienna index zawiera numer indeksu pierwszego elementu tablicy tab, któremu zostanie nadana wartość zmiennej wartosc. Zmienna iloscElemntow zawiera ilość elementów tablicy tab, której zostanie nadana wartość zmiennej wartosc. Oczywiście wartość zmiennej index oraz wartość wyrażenia index+iloscElemntow-1 musi mieścić się w wartościach dopuszczalnych indeksów tablicy tab.

W bibliotece .Net Framework istnieje metoda Clear klasy Array, która ustawia wybrane elementy tablicy na wartość zero, flase lub null w zależności od typu podstawowego tablicy. Przykład jej użycia został zaprezentowany poniżej.

int[] tab = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
Array.Clear(tab,2,4);
foreach (int i in tab)
{
Console.Write("{0}, ",i);
}

Na ekranie, po wykonaniu powyższego kodu, zostanie wypisane:

1, 2, 0, 0, 0, 0, 7, 8, 9,

Kopiowanie tablic

W wielu programach istnieje potrzeba dokonania kopi tablicy, w celu jej przetworzenia, bez ryzyka modyfikacji tablicy źródłowej. Skopiowanie wartości jednej zmiennej tablicowej do drugiej zmiennej tablicowej, powoduje że obie zmienne tablicowe będą odwoływać się do tego samego obiektu tablicowego. Powyższy problem jest przedstawiony w poniższym kodu:

typ [] tab1 = new typ[4];
typ [] tab2 = new typ[4];
...
tab1 = tab2;

Po wykonaniu ostatniej instrukcji powyższego kodu, zmienne tablicowe tab1 i tab2 będą odwoływać się do tego samego obiektu tablicowego.

W celu utworzenia dwóch oddzielnych tablic, z których jedna będzie zawierać kopie elementów drugiej tablicy należy wykonać poniższy kod.

typ [] zrodlo = new typ[rozmiar];
typ [] cel = new typ[rozmiar];
...
for(int i=0;i<rozmiar;i++)
{
...cel[i] = zrodlo[i];
}

W przypadku kopiowaniu tablic, rozmiar (liczba elementów) tablicy do której kopiujemy elementy (tablica cel), musi być wystarczający do pomieszczenie wszystkich elementów tablicy źródłowej. Warto zwrócić też uwagę, że w powyższym kodzie, jeżeli typ jest typem referencyjnym, to w wyniku jego działania otrzymamy dwie różne tablice, ale elementy tablic będą odwoływały się do tych samych obiektów.

Przykład implementacji kopiowania tablic z określeniem liczby elementów, z podaniem numeru indeksu elementu tablicy źródłowej, który należy skopiować pierwszy oraz podaniem indeksu elementu tablicy docelowej, od którego mają być nadpisane elementy, można znaleźć w programie Kurs\Demo\Modul7\Modul7.sln projekt Kopiowanie, gdzie Kurs jest katalogiem gdzie skopiowano pliki kursu. Należy zwrócić uwagę, że w programie nie ma sprawdzenia poprawności indeksów podanych przez użytkownika, ani ilości elementów do skopiowania. W wypadku podania nieodpowiednich wartości tych zmiennych, zgłoszony zostanie wyjątek IndexOutOfRangeException.

W bibliotece .Net Framework kopiowanie tablic jest wykonywane przez metodę Copy klasy Array. Przykład jej użycia został zaprezentowany poniżej.

int[] tab1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int[] tab2 = {11,12,13,14,15,16,17,18,19 };
Array.Copy(tab1,2,tab2,4,4);
foreach (int i in tab2)
{
Console.Write("{0}, ",i);
}

W wyniku działania powyższego kodu na ekranie zostanie wypisane:

11, 12, 13, 14, 3, 4, 5, 6, 19,

Uwaga:
Do kopiowania tablic można użyć również metody Clone oraz CopyTo klasy Array. Więcej informacji na temat tych metod, można znaleźć w MSDN Library.

Odwracanie tablicy

Odwracanie tablicy polega na zmianie kolejności elementów tablicy. Pierwszy staje się ostatnim, a ostatni pierwszym.

Przykład implementacji odwrócenia tablicy można znaleźć w programie Kurs\Demo\Modul7\Modul7.sln projekt Odwracanie, gdzie Kurs jest katalogiem gdzie skopiowano pliki kursu.

W bibliotece .Net Framework odwracanie tablicy realizowane jest przez metodę Reverse klasy Array. Przykład jej użycia został zaprezentowany poniżej.

int[] tab1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9};
Array.Reverse(tab1, 2, 5);
foreach (int i in tab1)
{
Console.Write("{0}, ", i);
};

W wyniku działania powyższego kodu na ekranie zostanie wypisane:

1, 2, 7, 6, 5, 4, 3, 8, 9,

W metodzie Reverse w nawiasach okrągłych podajemy tablicę, która ma zostać odwrócona, następnie po przecinku indeks elementu, od którego należy rozpocząć odwracanie oraz ilość elementów, które zostaną odwrócone.

W bibliotece ,Net Framework istnieje również wersja metody Reverse, która odwraca całą tablicę. Przykład jej użycia został pokazany poniżej:

int[] tab1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9};
Array.Reverse(tab1);
foreach (int i in tab1)
{
Console.Write("{0}, ", i);
};

W wyniku działania powyższego kodu na ekranie zostanie wypisane:

9, 8, 7, 6, 5, 4, 3, 2, 1,

Obie wersje metody Reverse współpracują tylko z tablicami jednowymiarowymi. Próba użycia ich do tablic wielowymiarowych spowoduje zgłoszenie wyjątku RankException.

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. Na przykład w celu znalezienia określonego pliku w danym katalogu, można posortować pliki według nazwy. Podobnie hasła w słowniku, czy encyklopedii są ustawione w porządku alfabetycznym, czyli są posortowane, aby łatwo znaleźć żądane hasło.

Podczas sortowania mogą pojawić się obiekty o tej samej wartości wyznaczającej porządek - o tym samym kluczu. W przypadku takim, jeżeli metoda sortowania nie zmienia ich względnego porządku, to metodę tą nazywamy stabilną.

W przypadku sortowania tablic bardzo jest ważna 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 najprostszych, choć niestety niezbyt wydajną, jest metoda nazywana sortowaniem bąbelkowym (bubble sort). Sortowanie bąbelkowe polega na zamianie dwóch sąsiadujących ze sobą elementów, jeżeli względem siebie zajmują nieprawidłowe miejsca. Dokładny schemat działania jest przedstawiony na poniższym schemacie blokowym, natomiast przykładową implementację w języku C# można znaleźć w programie Kurs\Demo\Modul7\Modul7.sln projekt Babelki, gdzie Kurs jest katalogiem gdzie skopiowano pliki kursu.
Inne algorytmy sortowania zostaną przedstawione w dalszej części kursu.

W bibliotece .Net Framework do sortowania tablicy można użyć metody Sort klasy Array. Przykład jej użycia został zaprezentowany poniżej.

int[] tab1 = { 4, 1, 83, 41, 53, 36, 47, 18, 29};
Array.Sort(tab1);
foreach (int i in tab1)
{
Console.Write("{0}, ", i);
}

W wyniku działania powyższego kodu na ekranie pojawi się:

1, 4, 18, 29, 36, 41, 47, 53, 83,

Metoda Sort klasy Array wykorzystuje algorytm QuickSort. Algorytm ten zostanie przedstawiony w rozdziale 10 "Rekurencja". Za pomocą metody Sort klasy Array można sortować tylko tablice jednowymiarowe. Gdy spróbujemy sortować tablicę wielowymiarową zostanie zgłoszony wyjątek RankException.

Uwaga:
Metoda Sort ma różne wersje - różną listę argumentów. Więcej na temat różnych wersji metody Sort można znaleźć w MSDN Library.

Uwaga:
Przy pomocy metody Sort można sortować tylko tablice, których typ podstawowy, typ elementu tablicy, implementuje interfejs IComparable. lub IComparer, w zależności od wersji metody Sort. Więcej na temat interfejsów można znaleźć w kursie "Programowania obiektowe".

Wyszukiwanie elementu w tablicy

Algorytm znalezienia elementu tablicy, który spełnia określone kryteria lub czy ma określoną wartość, polega na wykonaniu pętli, w której sprawdzamy czy aktualny element spełnia wymagane założenia. W przypadku znalezienia elementu spełniającego wymagane założenia, przerywamy wykonywanie pętli. Algorytm taki nazywamy wyszukiwaniem liniowym. W pętli musimy również sprawdzać, czy nie został osiągnięty koniec tablicy. Osiągnięcie końca tablicy jest równoznaczne ze stwierdzeniem, że dana tablica nie zawiera elementu spełniającego wymagane założenia. Sprawdzenie czy osiągnęliśmy koniec tablicy można przenieść poza pętlę, poprawiając w ten sposób wydajność algorytmu. Realizuje się to przy założeniu, że ostatni element tablicy nie zawiera istotnych danych. Przed rozpoczęciem wyszukiwania ustawia się jego wartość tak, aby spełniała kryteria wyszukiwania. Ostatni element tablicy pełni więc rolę strażnika, a algorytmy korzystające ze strażnika nazywamy algorytmami ze strażnikiem.

Przykład z zastosowaniem wyszukiwania liniowego ze strażnikiem można znaleźć w programie Kurs\Demo\Modul7\Modul7.sln projekt Liniowe, gdzie Kurs jest katalogiem gdzie skopiowano pliki kursu.

W bibliotece .Net Framework do znalezienia indeksu elementu tablicy o określonej wartości można użyć metody IndexOf lub LastIndexOf klasy Array. Metoda IndexOf przeszukuje tablicę od początku, metoda LastIndexOf natomiast przegląda tablicę od końca. Przykład użycia metody IndexOf w celu znalezienia indeksów wszystkich elementów o danej wartości został zaprezentowany poniżej.

int[] tab1 = { 2, 5, 7, 5, 12, 6, 5};
int i = Array.IndexOf(tab1, 5);
while(i != -1)
{
Console.Write("{0}, ", i);
i = Array.IndexOf(tab1, 5 , i+1);
}

W wyniku działania powyższego kodu na ekranie pojawi się:

1, 3, 6,

Metoda IndexOf oraz LastIndexOf zwracają indeks elementu, którego wartość jest zgodna z wartością poszukiwaną. W przypadku braku takiego elementu metoda zwróci wartość -1 (tak naprawdę najmniejszy indeks minus jeden). Więcej o wartości zwracanej przez metodę będzie opisane w rozdziale 8 "Funkcje - wstęp". W powyższym przykładzie występują dwie wersje metody Sort, z dwom i trzema argumentami. W obu metodach, jako pierwszy argument podajemy zmienną tablicową zawierającą uchwyt do tablicy, którą należy przeszukać, a jako drugi argument wartość, którą szukamy. W przypadku, gdy podany jest trzeci argument, metoda IndexOf rozpocznie przeszukiwanie tablicy od elementu o indeksie równym wartości trzeciego argumentu. Oczywiście przy braku trzeciego argumentu, metoda IndexOf rozpocznie przeszukiwanie tablicy od pierwszego elementu, a LastIndexOf od ostatniego. Więcej o przesyłaniu argumentów do metody i przeciążeniu nazwy funkcji będzie w rozdziale 9 "Przesyłanie argumentów do funkcji".

Podobnie jak w przypadku sortowania, można przeszukiwać tylko tablice jednowymiarowe. Gdy spróbujemy przeszukiwać tablicę wielowymiarową zostanie zgłoszony wyjątek RankException.

Uwaga:
W celu porównania elementu z podaną wartością używa się metody Object.Equals.

Uwaga:
W bibliotece .Net Framework w klasie Array istnieją również metody Exists, FindLast, FindAll, FindIndex, FindLastIndex, które przeszukują tablicę w celu znalezienia elementów tablicy spełniające pewne kryteria. Więcej informacji na temat tych metod można znaleźć w MSDN Library.

W przypadku, gdy chcemy przeszukiwać tablice posortowane, wydajność operacji wyszukiwania można znacznie poprawić, stosując wyszukiwanie binarne inaczej nazywane połówkowym. W przypadku wyszukiwania binarnego wybraną wartość porównujemy z środkowym elementem tablicy. Jeżeli wartość środkowego elementu jest równa wybranej wartości, przerywamy wyszukiwanie. Element środkowy jest szukanym elementem. W przypadku, gdy wybrana wartość jest mniejsza od wartości środkowego elementu, żądaną wartość próbujemy znaleźć w pierwszej połowie tablicy. Gdy wybrana wartość jest większa od wartości środkowego elementu, żądaną wartość próbujemy znaleźć w drugiej 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 żądanej wartości lub, gdy w wyniku podziałów otrzymamy pustą podtablicę, co jest równoważne z brakiem elementu o żądanej wartości w tablicy.
W bibliotece .Net Framework wyszukiwanie binarne jest realizowane przez metodę BinarySearch klasy Array. Metoda ta zwraca nur indeksu elementu, którego wartość jest równa żądanej wartości. W przypadku, gdy w tablicy znajduje się kilka elementów o żądanej wartości, metoda zwróci numer indeksu tylko jednego elementu i niekoniecznie pierwszego. Gdy tablica nie zawiera elementu o żądanej wartości metoda BinarySearch zwróci wartość ujemną. Więcej na temat wartości zwracanych przez metodę można znależć w rozdziale ósmym tego kursu. Metoda ta może przeszukiwać tylko tablice jednowymiarowe. Gdy spróbujemy przeszukiwać tablicę wielowymiarową zostanie zgłoszony wyjątek RankException.

Uwaga:
Metoda BinarySearch ma różne wersje - różną listę argumentów. Więcej na temat różnych wersji metody Sort można znaleźć w MSDN Library.

Uwaga:
Przy pomocy metody BinarySearch można przeszukiwać tylko tablice, których typ podstawowy, typ elementu tablicy, implementuje interfejs IComparable. lub IComparer, w zależności od wersji metody BinarySearch. Więcej na temat interfejsów można znaleźć w kursie "Programowania obiektowe".

Pytania sprawdzające

1. Czy poniższy kod spowoduje utworzenie dwóch niezależnych tablic?
   
   char [] samogloski =
   {'a','ą','e','ę','i','o','ó','u','y'};
   char [] kopia;
   kopia = samogloski;
   
   Odp.
   Nie. W wyniku wykonania powyższego kodu dwie zmienne tablicowe samogloski i kopia będą odwoływać się do tego samego obiektu tablicowego.

2. Jakie sortowanie nazywamy sortowaniem w miejscu?
   
   Odp.
   Sortowaniem w miejscu nazywamy metodę, która nie potrzebuje tworzenia dodatkowej tablicy, do której przenosimy elementy.

3. Kiedy możemy stosować wyszukiwanie binarne?
   
   Odp.
   Wyszukiwanie binarne możemy stosować tylko do tablic posortowanych.

Laboratorium

Ćwiczenie 1:
Napisz program, który sortuje tablicę metodą przez wstawianie. Tablicę zainicjalizuj liczbami pseudolosowymi, korzystając z generatora liczb pseudolosowych:

Random r = new Random(); //utworzenie obiektu
//generatora liczb pseudolosowych
double n = r.NextDouble(); //losowanie liczby
//rzeczywistej z przedziału <0;1>

Metoda sortowania przez wstawianie (insertion sort) jest podobna do sposobu, jaki stosujemy przy układaniu kart. Tablice dzielimy na umowne dwie podtablice. Pierwsza podtablica jest posortowana. Druga podtablica jest źródłem elementów, które należy wstawić w odpowiednie miejsce w tablicy pierwszej. Oczywiście po wstawieniu elementu, rozmiar podtablicy posortowanej jest zwiększany o jeden, natomiast rozmiar podtablicy źródłowej zmniejszany o jeden. Sortowanie rozpoczynamy od założenia, że podtablica posortowana zawiera tylko jeden element - pierwszy element tablicy. Sortowanie kończymy w momencie, kiedy w podtablicy źródłowej nie ma więcej elementów.

Schemat blokowy metody sortowanie przez wstawianie znajduje się w pliku Kurs\Lab\Modul7\Start\Wstawianie.gif, gdzie Kurs jest katalogiem gdzie skopiowano pliki kursu.

1. Uruchom Visual Studio
   Naciśnij przycisk Start systemu Windows, wybierz Wszystkie Programy następnie Microsoft Visual Studio 2005/ Microsoft Visual Studio 2005.

2. Utwórz nowy projekt

1. Z menu File wybierz New/Project...

2. W oknie dialogowym New Project określ następujące właściwości:

1. typu projektu: Visual C#/Windows

2. szablon: Console Application

3. lokalizacja: Moje Dokumenty\Visual Studio 2005\Projects\

4. nazwa projektu: Wstawianie.

5. nazwa rozwiązania: Lab7

3. Wewnątrz metody Main napisz następujący kod:

1. Utwórz obiekt tablicy piętnastoelementowej liczb rzeczywistych.
   
   double [] tablica = new double[15];

2. Nadaj elementom tablicy wartości losowe z przedziału od zera do jednego, korzystając z generatora liczb pseudolosowych.
   
   Random generator = new Random();
   for(int i = 0; i < tablica.Length; i++)
   {
   tablica[i] = generator.NextDouble();
   }

3. Wypisz wartości elementów tablicy korzystając z pętli foreach.
   
   Console.WriteLine("Wylosowano następujące
   ¬wartości: ");
   foreach(double i in tablica)
   {
   Console.Write("{0:f3}; ", i);
   }

4. Podziel tablicę na dwie części, podtablicę źródłową i podtablicę posortowaną. Pobieraj elementy z podtablicy źródłowej, od pierwszego elementu i wstawiaj w odpowiednie miejsce w podtablicy posortowanej. Czynność powtarzaj póki podtablica posortowana nie będzie pusta.
   
   double x;
   int j;
   for (int i = 1; i < tablica.Length; i++)
   {
   x = tablica[i];
   for(j = i-1; j >= 0 && x < tablica[j]; j--)
   {
   tablica[j + 1] = tablica[j];
   }
   tablica[j + 1] =
   }
   
   Uwaga:
   Podczas wstawiania można wykorzystać wyszukiwanie połówkowe. Powyższy kod można zastąpić wtedy następującym:
   
   int j, l, p, m;
   double x;
   for (int i = 1; i < tablica.Length; i++)
   {
   x = tablica[i];
   l = 0; p = i - 1;
   while (l <= p)
   {
   m = (l + p) / 2;
   if (x < tablica[m])
   p = m - 1;
   else
   l = m + 1;
   }
   for (j = i - 1; j >= l; j--)
   {
   tablica[j + 1] = tablica[j];
   }
   tablica[j + 1] = x;
   }

5. W celu sprawdzenia poprawności działania programu wypisz wartości elementów tablicy..
   
   Console.WriteLine("\n\nElementy tablicy po
   ¬sortowaniu: ");
   foreach (double i in tablica)
   {
   Console.Write("{0:f3}; ", i);
   }
   Console.ReadKey();

4. Skompiluj i uruchom program.

Ćwiczenie 2:
Napisz program, który sortuje tablicę metodą przez wybieranie. Tablicę zainicjalizuj liczbami pseudolosowymi, korzystając z generatora liczb pseudolosowych:

Random r = new Random(); //utworzenie obiektu
//generatora liczb pseudolosowych
double n = r.NextDouble(); //losowanie liczby
//rzeczywistej z przedziału <0;1>

W metodzie sortowania przez wybieranie (selection sort) wybieramy najmniejszy element tablicy i zamieniamy go z pierwszym elementem. Powyższą operację potarzamy, nie uwzględniając pierwszego elementu tablicy Czynność powtarzamy zmniejszając liczbę elementów z których wybieramy najmniejszy oraz zwiększając indeks elementu do zamiany. Czynność kończymy, gdy do wybrania pozostaje pojedynczy element.

Schemat blokowy metody sortowanie przez wstawianie znajduje się w pliku Kurs\Lab\Modul7\Start\ Wybieranie.gif, gdzie Kurs jest katalogiem gdzie skopiowano pliki kursu.

1. Dodaj do bieżącego rozwiązania nowy projekt

1. Z menu File wybierz Add/New Project...

2. W oknie dialogowym Add New Project określ następujące właściwości:

1. typu projektu: Visual C#/Windows

2. szablon: Console Application

3. nazwa projektu: Wybieranie.

2. Uczyń nowo utworzony projekt projektem startowym

1. Zaznacz projekt Wybieranie w okienku Solution Explorer i z menu kontekstowego wybierz Set as StartUp Project.

albo, gdy rozpoczynasz laboratorium od tego ćwiczenia

1. Uruchom Visual Studio
   Naciśnij przycisk Start systemu Windows, wybierz Wszystkie Programy następnie Microsoft Visual Studio 2005/ Microsoft Visual Studio 2005.

2. Utwórz nowy projekt

1. Z menu File wybierz New/Project...

2. W oknie dialogowym New Project określ następujące właściwości:

1. typu projektu: Visual C#/Windows

2. szablon: Console Application

3. lokalizacja: Moje Dokumenty\Visual Studio 2005\Projects\

4. nazwa projektu: Wybieranie.

5. nazwa rozwiązania: Lab7

3. Wewnątrz metody Main napisz następujący kod:

1. .Utwórz obiekt tablicy piętnastoelementowej liczb rzeczywistych.
   
   double [] tablica = new double[15];

2. Nadaj elementom tablicy wartości losowe z przedziału od zera do jednego, korzystając z generatora liczb pseudolosowych.
   
   Random generator = new Random();
   for(int i = 0; i < tablica.Length; i++)
   {
   tablica[i] = generator.NextDouble();
   }

3. Wypisz wartości elementów tablicy korzystając z pętli foreach.
   
   Console.WriteLine("Wylosowano następujące
   ¬wartości: ");
   foreach(double i in tablica)
   {
   Console.Write("{0:f3}; ", i);
   }

4. Wybierz najmniejszy element tablicy i zamień go z pierwszym. Następnie powtarzaj operację z pozostałymi elementami, aż pozostanie tylko jeden element - największy.
   
   int j, min;
   double x;
   for (int i = 0; i < tablica.Length - 1; i++)
   {
   min = i;
   for (j = i + 1; j < tablica.Length; j++)
   {
   if (tablica[j] < tablica[min])
   min = j;
   }
   if (min != i)
   {
   x = tablica[i];
   tablica[i] = tablica[min];
   tablica[min] = x;
   }
   }

5. W celu sprawdzenia poprawności działania programu wypisz wartości elementów tablicy..
   
   Console.WriteLine("\n\nElementy tablicy po
   ¬sortowaniu: ");
   foreach (double i in tablica)
   {
   Console.Write("{0:f3}; ", i);
   }
   Console.ReadKey();

4. Skompiluj i uruchom program.

Ćwiczenie 3:
Napisz program, który w celu sprawdzenia czy w tablicy znajduje się element o danej wartości stosuje algorytm wyszukiwania binarnego. Użyj tablicy zawierającej napisy. Do porównania dwóch obiektów string, czy zawierają ten sam napis, użyj metody String.Compare(napis1, napis2). Metoda ta zwraca wartość mniejszą od zera, gdy napis1 "jest mniejszy" od napis2 (jest wcześniej w słowniku). Wartość zero oznacza, że obie zmienne zawierają uchwyt do obiektów z tym samym tekstem. Wartość większa od zera oznacza, że napis1 "jest większy" od napis2 (występuje później w słowniku).

1. Dodaj do bieżącego rozwiązania nowy projekt

1. Z menu File wybierz Add/New Project...

2. W oknie dialogowym Add New Project określ następujące właściwości:

1. typu projektu: Visual C#/Windows

2. szablon: Console Application

3. nazwa projektu: Binarne.

2. Uczyń nowo utworzony projekt projektem startowym

1. Zaznacz projekt Binarne w okienku Solution Explorer i z menu kontekstowego wybierz Set as StartUp Project.

albo, gdy rozpoczynasz laboratorium od tego ćwiczenia

1. Uruchom Visual Studio
   Naciśnij przycisk Start systemu Windows, wybierz Wszystkie Programy następnie Microsoft Visual Studio 2005/ Microsoft Visual Studio 2005.

2. Utwórz nowy projekt

1. Z menu File wybierz New/Project...

2. W oknie dialogowym New Project określ następujące właściwości:

1. typu projektu: Visual C#/Windows

2. szablon: Console Application

3. lokalizacja: Moje Dokumenty\Visual Studio 2005\Projects\

4. nazwa projektu: Binarne.

5. nazwa rozwiązania: Lab7

3. Wewnątrz metody Main napisz następujący kod:

1. Utwórz tablicę zawierającą nazwy miast, następnie ją posortuj i wypisz jej elementy na ekranie:
   
   string[] miasta = {"Poznań", "Warszawa",
   "Częstochowa", "Gdańsk", "Łódź", "Kraków",
   "Wrocław", "Białystok", "Szczecin"};
   Array.Sort(miasta);
   Console.WriteLine("Elementy tablicy po
   ¬sortowaniu: ");
   foreach (string miasto in miasta)
   {
   Console.Write("{0}, ", miasto);
   }

2. Pobierz od użytkownika nazwę miasta do sprawdzenia
   
   Console.Write("\n\nPodaj nazwę miasta: ");
   string s = Console.ReadLine();

3. Zadeklaruj trzy zmienne całkowite: lewy, prawy i srodek i nadaj im odpowiednio wartości: zmiennej lewy wartość zero, zmiennej prawy wartość równą górnemu indeksowi tablicy, zmiennej srodek wartość indeksu środkowego elementu tablicy.
   
   int lewy = 0, prawy = miasta.Length - 1;
   int srodek = (lewy + prawy) / 2;

4. Póki wartość zmiennej lewy jest mniejsza lub równa od wartości zmiennej prawy, wykonuj co następuje:

1. Jeżeli element o indeksie równym wartości zmiennej srodek zawiera miasto takie jak podał użytkownik zakończ pętlę.

2. Jeżeli element o indeksie równym wartości zmiennej srodek zawiera miasto, które w kolejności alfabetycznej występuje przed miastem podanym przez użytkownika, zmiennej prawy nadaj wartość zmiennej srodek pomniejszoną o jeden.

3. Jeżeli element o indeksie równym wartości zmiennej srodek zawiera miasto, które w kolejności alfabetycznej występuje po mieście podanym przez użytkownika, zmiennej lewy nadaj wartość zmiennej srodek powiększoną o jeden.

4. Zmiennej srodek nadaj wartość równą połowie sumy wartości zmiennej lewy i prawy.

int flaga;
while (lewy <= prawy )
{
flaga = String.Compare(s, miasta[srodek]);
if (flaga == 0)
{
break;
}
else
{
if (flaga < 0)
{
prawy = srodek - 1;
}
else
{
lewy = srodek + 1;
}
}
srodek = (lewy + prawy) / 2;
}

5. Jeżeli wartość zmiennej lewy jest mniejsza lub równa od wartości zmiennej prawy, wypisz na ekranie informację, że tablica zawiera podane miasto, w przeciwnym wypadku wypisz, że tablica nie zawiera podanego miasta. Następnie zatrzymaj program, aby użytkownik mógł obejrzeć wyniki.
   
   if (lewy <= prawy)
   {
   Console.Write("Podane miasto ma w tablicy
   ¬indeks {0}.", srodek);
   }
   else
   {
   Console.Write("Tablica nie zawiera podanego
   ¬miasta.");
   }
   Console.ReadKey();

4. Skompiluj i uruchom program.

Dane we: tab - tablica elementów do
sortowania - typ elementu tablicy ma
zdefiniowany operator < i =;
rozmiar - liczba int, ilość elementów

Zmienne lokalne:
i, j - liczby całkowite, int,
x - taki sam typ jak element tablicy

i<rozmiar
?

i = 1;

T

tab[j]<tab[j-1]
?

T

N

j >= i
?

j = rozmiar - 1;

Start

Stop

N

i++;

T

j--;

N

x = tab[j];
tab[j]=tab[j-1];
tab[j-1] = x;

swap
- zamiana

L

L

---