Operacje na tablicach
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.
Start
i = 1;
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
?
Stop
j = rozmiar - 1;
j >= i
?
N
T
tab[j]<tab[j-1]
?
T
T
i++;
N
j--;
N
x = tab[j];
tab[j]=tab[j-1];
tab[j-1] = x;
swap
- zamiana
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
a. Z menu File wybierz New/Project...
b. W oknie dialogowym New Project określ następujące właściwości:
i. typu projektu: Visual C#/Windows
ii. szablon: Console Application
iii. lokalizacja: Moje Dokumenty\Visual Studio 2005\Projects\
iv. nazwa projektu: Wstawianie.
v. nazwa rozwiązania: Lab7
3. Wewnątrz metody Main napisz następujący kod:
a. Utwórz obiekt tablicy piętnastoelementowej liczb rzeczywistych.
double [] tablica = new double[15];
b. 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();
}
c. 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);
}
d. 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;
}
e. 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
a. Z menu File wybierz Add/New Project...
b. W oknie dialogowym Add New Project określ następujące
właściwości:
i. typu projektu: Visual C#/Windows
ii. szablon: Console Application
iii. nazwa projektu: Wybieranie.
2. Uczyń nowo utworzony projekt projektem startowym
a. 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
a. Z menu File wybierz New/Project...
b. W oknie dialogowym New Project określ następujące właściwości:
i. typu projektu: Visual C#/Windows
ii. szablon: Console Application
iii. lokalizacja: Moje Dokumenty\Visual Studio 2005\Projects\
iv. nazwa projektu: Wybieranie.
v. nazwa rozwiązania: Lab7
3. Wewnątrz metody Main napisz następujący kod:
a. .Utwórz obiekt tablicy piętnastoelementowej liczb rzeczywistych.
double [] tablica = new double[15];
b. 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();
}
c. 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);
}
d.
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;
}
}
e.
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
a. Z menu File wybierz Add/New Project...
b. W oknie dialogowym Add New Project określ następujące właściwości:
i. typu projektu: Visual C#/Windows
ii. szablon: Console Application
iii. nazwa projektu: Binarne.
2. Uczyń nowo utworzony projekt projektem startowym
a. 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
a. Z menu File wybierz New/Project...
b. W oknie dialogowym New Project określ następujące właściwości:
i. typu projektu: Visual C#/Windows
ii. szablon: Console Application
iii. lokalizacja: Moje Dokumenty\Visual Studio 2005\Projects\
iv. nazwa projektu: Binarne.
v. nazwa rozwiązania: Lab7
3. Wewnątrz metody Main napisz następujący kod:
a.
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);
}
b.
Pobierz od użytkownika nazwę miasta do sprawdzenia
Console.Write("\n\nPodaj nazwę miasta: ");
string s = Console.ReadLine();
c. 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;
d. Póki wartość zmiennej lewy jest mniejsza lub równa od wartości
zmiennej prawy, wykonuj co następuje:
i. Jeżeli element o indeksie równym wartości zmiennej srodek
zawiera miasto takie jak podał użytkownik zakończ pętlę.
ii. 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.
iii. 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.
iv. 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;
}
e. 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.