Rekurencyjne struktura danych - lista
jednokierunkowa
Rekurencyjne struktura danych - lista
jednokierunkowa
Przegląd zagadnień
Omawiając pojęcie rekurencji, stwierdziliśmy, że jest to definicja, która
odwołuje się do definiowanego przedmiotu. Powstaje pytanie, czy istnieje
możliwość definicji struktury danych, która odwoływałaby się do siebie samej.
Przeczytawszy tytuł tego rozdziału można się domyślić, że odpowiedź brzmi
tak.
W rozdziale tym studenci poznają i nauczą się:
Definiować własny typ referencyjny.
Definicję listy jednokierunkowej.
Dodawać elementy do listy.
Usuwać elementy z listy.
Listy dwukierunkowe i cykliczne.
Klasa jako rekord
Przy pomocy słowa struct definiowaliśmy nowy typ wartości (bezpośredni).
W języku C# programista może również zdefiniować własny typ referencyjny.
Realizuje to przez zastąpienie słowa struct słowem class. W celu
uniknięcia pomyłek przyjmijmy, że w dalszej części kursu struktury (rekordy)
definiowane przy pomocy słowa struct będziemy nazywali krótko
strukturami, natomiast struktury definiowane za pomocą słowa class klasami.
Jest to ogólnie przyjęta nomenklatura stosowana w odniesieniu do języka C#.
Do klas możemy stosować wszystko to, co zostało do tej pory powiedziane na
temat struktur.
Główna różnica między klasami a strukturami jest taka, że pola (składowe)
przedstawiciela klasy, czyli obiektu, są zawsze "przechowywane" na
zarządzanej stercie, nawet wtedy, gdy pole jest typu bezpośredniego. Przydział
pamięci dla obiektu jest pokazany na rysunku na slajdzie.
Deklaracja zmiennej typu zdefiniowanego przy pomocy słowa class, tworzy
zmienną typu referencyjnego, więc jak już wspominano wcześniej, deklaracja
zmiennej nie tworzy obiektu. Obiekt tworzymy zawsze przy pomocy słowa
kluczowego new:
nazwaZmiennej = new NazwaKlasy();
Po utworzeniu obiektu wszystkie jego pola są zainicjalizowane. Pola liczbowe
mają nadaną wartość zero, logiczne false, pola typów referencyjnych wartość
null. Polu możemy nadać swoją domyślną wartość, podając ją w definicji
pola:
class Osoba
{
public string Nazwisko = "Kowalski";
public string Imie = "Jaś";
public int RokUrodzenia = 1979;
}
Uwaga:
Więcej na temat typu referencyjnego można znaleźć w rozdziale drugim tego
kursu.
Struktury stosujemy zazwyczaj do reprezentacji prostych struktur danych typu
punkt, rozmiar, prostokąt, data. W przypadku struktur danych bardziej
złożonych powinniśmy stosować klasy (np. stos, kolejka (:).
Definiując rekurencyjne struktury danych musimy użyć klasy. Zmienne typów
referencyjnych zawierają odwołanie. Odwołanie to niekoniecznie musi
pokazywać na obiekt danej klasy, może być puste, czyli zmienna ma wartość
null. Dzięki temu definicja ma swój koniec, nie jest nieskończona.
Lista jednokierunkowa
Tablice są bardzo przydatnymi strukturami danych, lecz mają również pewne
wady:
1. Rozmiar tablicy musi być podany w trakcie jej tworzenie.
2. Wstawienie nowego elementu, jak również usunięcie istniejącego
elementu tablicy, wymaga przesunięcia wszystkich elementów
znajdujących się za wstawianym (usuwanym) elementem.
Ograniczenia powyższe rozwiązuje struktura zwana listą jednokierunkową.
Lista jednokierunkowa jest kolekcją elementów zwanych węzłami. Każdy
węzeł zawiera dane oraz połączenie (odwołanie) do następnego węzła.
Pierwszy węzeł listy nazywamy głową (head). Przy pomocy zmiennej głowa
(head) możemy odwołać się do pozostałych elementów listy, korzystając z tego,
że węzły są połączone. Ostatni element listy zawiera odwołanie puste.
Nazywamy go ogonem (tail).
Dodawanie elementu do listy (1)
Procedura dodawania pierwszego elementu do listy (pierwszych danych), czyli
utworzenie listy, wygląda następująco:
1. Utwórz nowy obiekt węzeł. Węzeł zawiera dodawane dane.
2. Odwołanie do następnego węzła nowo utworzonego obiektu ustaw na
null.
3. Zmienne ogon i głowa (obie typu Węzeł) ustaw tak, aby odwoływały
się do nowo utworzonego obiektu węzeł.
Dodawanie elementu do listy (2)
Procedura dodawania elementu do głowy listy wygląda następująco:
1. Sprawdź czy lista jest pusta. Jeżeli lista jest pusta wykonaj procedurę
dodawania pierwszego elementu.
2. Utworz nowy obiekt węzeł. Węzeł zawiera dodawane dane.
3. Odwołanie do następnego węzła nowo utworzonego obiektu ustaw na
obiekt wskazywany przez zmienną głowa.
4. Zmienną głowa ustaw tak, aby odwoływała się do nowo utworzonego
obiektu węzeł.
Dodawanie elementu do listy (3)
Procedura dodawania elementu do ogona listy wygląda następująco:
1. Sprawdź czy lista jest pusta. Jeżeli lista jest pusta wykonaj procedurę
dodawania pierwszego elementu.
2. Utwórz nowy obiekt węzeł. Węzeł zawiera dodawane dane.
3. Odwołanie do następnego węzła nowo utworzonego obiektu ustaw na
null.
4. Odwołanie do następnego węzła obiektu wskazywanego przez zmienną
ogon ustaw tak, aby odwoływała się do nowo utworzonego obiektu
węzeł.
5. Zmienną ogon ustaw tak, aby odwoływała się do nowo utworzonego
obiektu węzeł.
Wstawianie elementu do listy
Procedura wstawiania elementu do listy wygląda następująco:
1. Sprawdź czy lista jest pusta. Jeżeli lista jest pusta wykonaj procedurę
dodawania pierwszego elementu.
2. Utwórz nowy obiekt węzeł. Węzeł zawiera dodawane dane.
3. Znajdź węzeł, za którym należy wstawić nowo utworzony węzeł.
Nazwijmy ten węzeł poprzedni. Jeżeli węzeł poprzedni jest
ostatnim węzłem listy wykonaj procedurę dodawania elementu do
ogona. W przypadku, gdy nowy węzeł ma być pierwszym elementem
listy, wykonaj procedurę dodawania elementu do głowy.
4. Odwołanie do następnego węzła nowo utworzonego obiektu ustaw na
węzeł do którego odwołuje się .węzeł poprzedni.
5. Odwołanie do następnego węzła węzła poprzedni ustaw tak, aby
pokazywało na nowo utworzony obiekt węzeł.
Usuwanie elementu z listy (1)
Procedura usuwania elementu z listy, gdy na liście jest jeden element, wygląda
następująco:
1. Usuń węzeł z pamięci.
2. Wartość zmiennych ogon i głowa ustaw na null.
Ponieważ w języku C# obiekty są usuwane z pamięci prze Garbage Collection
(automatyczny odśmiecacz pamięci), wystarczy wykonać tylko krok dwa.
Usuwanie elementu z listy (2)
Procedura usuwania pierwszego elementu (głowy) z listy wygląda następująco:
1. Sprawdź czy lista ma jeden element, Jeżeli tak wykonaj procedurę
usuwania elementu z listy, gdy na liście jest jeden element.
2. Wskaż zmienną pomocniczą na element do usunięcia.
3. Wskaż zmienną głowa na drugi element w liście.
4. Usuń węzeł .wskazywany przez zmienną pomocniczą z pamięci.
Ponieważ w języku C# obiekty są usuwane z pamięci prze Garbage Collection
(automatyczny odśmiecacz pamięci), kroki dwa i cztery mogą być pominięte..
Usuwanie elementu z listy (3)
Procedura usuwania ostatniego węzła (ogona) z listy wygląda następująco:
1. Sprawdź czy lista ma jeden element, Jeżeli tak wykonaj procedurę
usuwania elementu z listy, gdy na liście jest jeden element.
2. Wskaż zmienną pomocniczą na element do usunięcia.
3. Wskaż zmienną ogon na przedostatni element w liście. Krok ten w
listach jednokierunkowych jest operacją nieefektywną. Wymaga
przejścia całej liście. Problem efektywności tego kroku rozwiązują listy
dwukierunkowe, o których będzie mowa w dalszej części tego
rozdziału.
4. Odwołanie do następnego węzła obiektu wskazywanego przez zmienną
ogon (do tej pory przedostatni element listy) ustaw na null.
5. Usuń węzeł .wskazywany przez zmienną pomocniczą z pamięci.
Ponieważ w języku C# obiekty są usuwane z pamięci prze Garbage Collection
(automatyczny odśmiecacz pamięci), kroki dwa i pięć mogą być pominięte..
Usuwanie elementu z listy (4)
Procedura usuwania ostatniego (ogona) węzła z listy wygląda następująco:
1. Sprawdź czy lista ma jeden element, Jeżeli tak, wykonaj procedurę
usuwania elementu z listy, gdy na liście jest jeden element.
2. Wskaż zmienną pomocniczą na element do usunięcia.
3. Jeżeli zmienna pomocnicza odwołuje się do pierwszego elementu listy
(głowy) wykonaj procedurę usuwania pierwszego elementu (głowy) z
listy. Jeżeli zmienna pomocnicza odwołuje się do ostatniego elementu
listy (ogona), wykonaj procedurę usuwania ostatniego węzła (ogona) z
listy.
4. Wskaż zmienną poprzedni na element poprzedzający element do
usunięcia.
5. Ustaw odwołanie do następnego węzła obiektu wskazywanego przez
zmienną poprzedni na węzeł występujący po węźle do skasowania.
6. Usuń węzeł wskazywany przez zmienną pomocniczą z pamięci.
Ponieważ w języku C# obiekty są usuwane z pamięci prze Garbage Collection
(automatyczny odśmiecacz pamięci), krok sześć może być pominięty..
Inne rodzaje list
Usuwanie ostatniego elementu listy (ogona) z listy jednokierunkowej jest
operacją nieefektywną. Problem ten można rozwiązać stosując tak zwane listy
dwukierunkowe. W listach dwukierunkowych każdy węzeł oprócz wskazania
na swojego następnika, zawiera również pole pokazujące poprzednika. Wartość
poprzednika węzła głowa jest ustawiona na null.
Innym rodzajem listy, przydatnym w specyficznych sytuacjach są listy
cykliczne Specyficzną sytuacją jest np. zarządzanie przydziałem pewnego
zasobu dla kilku klientów - procesów, każdy proces ma dostęp do zasobu przez
pewien określony czas, po czym zasób jest przejmowany przez następny
proces.. W listach cyklicznych węzły tworzą pierścień. Każdy węzeł ma swój
następnik.
Pytania sprawdzające
1. Zdefiniuj klasę Samochod, która będzie zawierać następujące pola: marka,
model, rok produkcji, przebieg
Odp.
class Samochod
{
public string Marka;
public string Model;
public int RokProdukcji;
public ulong Przebieg;
}
2. Jaki popełniono błąd w poniższym programie?
class Klasa{
public int Pole;
}
...
static void Main(){
Klasa a;
a.Pole = 10;
}
Odp.
W powyższym przykładzie używamy zmienną, która nie zawiera odwołania
do żadnego obiektu.
Laboratorium
Ćwiczenie 1:
Napisz program, który będzie zawierał implementacje listy jednokierunkowej.
Do listy będą dodawane obiekty klasy Osoba. Klasa Osoba jest
zaimplementowana w projekcie Biblioteka. Projekt Biblioteka jest częścią
rozwiązania Kurs\Modul12\Start\Modul12\Modul12.sln, gdzie
Kurs jest katalogiem, gdzie skopiowano pliki kursu. Program będzie składał
się z dwóch podzespołów:
Biblioteki dll, o nazwie Listy, która będzie zawierała implementację listy
jednokierunkowej. W klasie lista będą zaimplementowane następujące
metody:
o IsEmpty - sprawdzenie czy lista jest pusta
o AddToHead - dodanie elementu na początek listy
o AddToTail - dodanie elementu na koniec listy
o DeleteFromHead - usunięcie elemntu z początku listy
o DeleteFromTail - usunięcie elementu z końca listy
o PrintAll - wypisanie na ekranie danych wszystkich elementów listy
o GetCount - zwraca ilość elementów w liście
Programu głównego, w którym przetestujemy listę.
1. Skopiuj rozwiązanie
Kurs\Modul12\Start\Modul12\Modul12.sln, gdzie Kurs jest
katalogiem, gdzie skopiowano pliki kursu.
2. Otwórz skopiowane rozwiązanie Modul12.sln
3. 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:
c. typu projektu: Visual C#/Windows
i. szablon: Class Library
ii. lokalizacja: Moje Dokumenty\Visual Studio 2005\Projects\
iii. nazwa projektu: Listy.
4. Podłącz do programu Listy, podzespół Biblioteka.
a. W okienku Solution Explorer, z menu kontekstowego związanego z
elementem reprezentującym projekt Listy wybierz Add Reference...
b. W okienku Add Reference przejdź do zakładki Projects, zaznacz
projekt Biblioteka i naciśnij OK.
5. Zaznacz, że będziemy korzystać z przestrzeni nazw Biblioteka.
using Biblioteka;
6. Zmień nazwę pliku Class1.cs na List.cs.
7. Zmień nazwę klasy z Class1 na List Wewnątrz klasy List zdefiniuj
klasę Node (Węzeł). .Do klasy Node dodaj następujące pola: pole Data
(Dane) typu Osoba, pole Next (Nastepny) typu Node. Do klasy List
dodaj pole Head (Glowa) i Tail (Ogon) typu Node.
public class List
{
public class Node
{
public Osoba Data;
public Node Next;
}
public Node Head, Tail;
}
8. Do klasy List dodaj metodę IsEmpty::
public static bool IsEmpty (List lista)
{
return lista.Head == null;
}
9. Do klasy List dodaj metodę AddToHead::
public static void AddToHead(List lista,Osoba os)
{
Node tmp = new Node();
tmp.Data = os;
tmp.Next = lista.Head;
lista.Head = tmp;
if (lista.Tail == null)
lista.Tail = tmp;
}
10. Do klasy List dodaj metodę AddToTail::
public static void AddToTail (List lista,Osoba os)
{
Node tmp = new Node();
tmp.Data = os;
if (lista.Tail == null)
lista.Tail = lista.Head = tmp;
else
{
lista.Tail.Next = tmp;
lista.Tail = tmp;
}
}
11. Do klasy List dodaj metodę DeleteFromHead::
public static Osoba DeleteFromHead (List lista)
{
if (lista.Head == null) //lista pusta
throw new InvalidOperationException(
"Lista jest pusta");
Osoba x = lista.Head.Data;
if (lista.Head == lista.Tail
lista.Head = lista.Tail = null;
else
lista.Head = lista.Head.Next;
return x;
}
12. Do klasy List dodaj metodę DeleteFromTail::
public static Osoba DeleteFromTail (List lista)
{
if (lista.Tail == null) //lista pusta
throw new InvalidOperationException(
"Lista jest pusta");
Osoba x = lista.Tail.Data;
if (lista.Head == lista.Tail)
lista.Head = lista.Tail = null;
else
{
Node tmp;
for (tmp = lista.Head;
tmp.Next != lista.Tail; tmp = tmp.Next);
lista.Tail = tmp;
lista.Tail.Next = null;
}
return x;
}
13. Do klasy List dodaj metodę PrintAll::
public static void PrintAll(List lista)
{
for (Node tmp = lista.Head; tmp != null;
tmp = tmp.Next)
{
Osoba.WypiszOsobe(tmp.Data);
Console.WriteLine();
}
}
14. Do klasy List dodaj metodę GetCount::
public static int GetCount(List lista)
{
int i;
Node tmp;
for (i = 0, tmp = lista.Head; tmp != null;
i++, tmp = tmp.Next) ;
return i;
}
15. Do rozwiązania dodaj nowy projekt, w którym będziemy testowali listę.
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: TestListy.
c. Uczyń nowo utworzony projekt projektem startowym
d.
Podłącz do programu TestListy, podzespóły Biblioteka oraz Listy.
e.
Zaznacz, że będziemy korzystać z przestrzeni nazw Biblioteka
oraz Listy.
using Biblioteka;
using Listy;
16. Napisz kod testujący listę
static char Menu()
{
Console.Clear();
Console.WriteLine("\n\t\tA - Dodaj osobę do
¬początku listy");
Console.WriteLine("\n\t\tB - Usuń pierwszą
¬osobę z listy");
Console.WriteLine("\n\t\tC - Dodaj osobę na
¬koniec listy");
Console.WriteLine("\n\t\tD - Usuń ostatnią
¬osobę z listy");
Console.WriteLine("\n\t\tE - Podaj liczbę osób
¬na liście");
Console.WriteLine("\n\t\tF - Wypisz osoby z
¬listy");
Console.WriteLine("\n\t\tK - Koniec");
return Console.ReadKey(true).KeyChar;
}
static void Main(string[] args)
{
List mojaLista = new List();
Osoba tmp;
char c;
do
{
c = Menu();
switch (c)
{
case 'a':
case 'A':
Osoba.WprowadzOsobe(out tmp);
List.AddToHead(mojaLista, tmp);
break;
case 'b':
case 'B':
Console.WriteLine("Usunięta osoba to:");
Osoba.WypiszOsobe(
List.DeleteFromHead(mojaLista));
Console.ReadKey();
break;
case 'c':
case 'C':
Osoba.WprowadzOsobe(out tmp);
List.AddToTail(mojaLista, tmp);
break;
case 'd':
case 'D':
Console.WriteLine("Usunięta osoba to:");
Osoba.WypiszOsobe(
List.DeleteFromHead(mojaLista));
Console.ReadKey();
break;
case 'e':
case 'E':
Console.WriteLine("Liczba osób na liście
¬wynosi: {0}",
List.GetCount(mojaLista));
Console.ReadKey();
break;
case 'f':
case 'F':
List.PrintAll(mojaLista);
Console.ReadKey();
break;
}
}
while (!(c == 'k' || c == 'K'));
}
17. Skompiluj i uruchom program.
Ćwiczenie 2:
Wymagania:
Wymagane jest ukończenie poprzedniego ćwiczenia.
Napisz program, który będzie zawierał implementacje kolejki FIFO przy
pomocy listy. Do kolejki będziemy dodawać zmienne typu Osoba. Klasa
Lista była zaimplementowana w poprzednim ćwiczeniu w programie Listy.
Program będzie składał się z dwóch podzespołów:
Biblioteki dll, o nazwie Kolejka, która będzie zawierała implementację
kolejki FIFO.
Programu głównego, w którym przetestujemy kolejkę.
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: Class Library
iii. nazwa projektu: KolejkaFIFO.
2. Podłącz do programu KolejkaFIFO, podzespóły Biblioteka oraz Listy.
c. W okienku Solution Explorer, z menu kontekstowego związanego z
elementem reprezentującym projekt KolejkaFIFO wybierz Add
Reference...
d. W okienku Add Reference przejdź do zakładki Projects, zaznacz
projekty Biblioteka oraz Listy i naciśnij OK.
3. Zaznacz, że będziemy korzystać z przestrzeni nazw Biblioteka i
Listy.
using Biblioteka;
using Listy;
4. Zmień nazwę pliku Class1.cs na Queue.cs.
5. Zmień nazwę klasy z Class1 na Queue. Do klasy Queue dodaj pole:
Kolejka typu List i :od razu je zainicjalizuj
public class Queue
{
public List Kolejka = new List();;
...
}
6. Do klasy Queue dodaj metodę Enqueue:
public static void Enqueue(Queue q,Osoba os)
{
List.AddToTail(q.Kolejka, os);
}
7. Do klasy Queue dodaj metodę IsEmpty:
public static bool IsEmpty(Queue q)
{
return List.IsEmpty(q.Kolejka);
}
8. Do klasy Queue dodaj metodę Dequeue:
public static Osoba Dequeue(Queue q)
{
return List.DeleteFromHead(q.Kolejka);
}
9. Do klasy Queue dodaj metodę GetLength:
public static int GetLength(Queue q)
{
return List.GetCount(q.Kolejka);
}
10. Do rozwiązania dodaj nowy projekt, w którym będziemy testowali kolejkę.
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: KomitetKolejkowy.
c.
Uczyń nowo utworzony projekt projektem startowym
d.
Podłącz do programu KomitetKolejkowy, podzespół Biblioteka oraz
KolejkaFIFO.
e.
Zaznacz, że będziemy korzystać z przestrzeni nazw Biblioteka
oraz KolejkaFIFO.
using Biblioteka;
using KolejkaFIFO;
f. Napisz kod testujący kolejkę
static char Menu()
{
Console.Clear();
Console.WriteLine("\n\t\tA - Dodaj osobę do
¬kolejki");
Console.WriteLine("\n\t\tB - Usuń osobę z
¬kolejki");
Console.WriteLine("\n\t\tC - Podaj liczbę
¬osób w kolejce");
Console.WriteLine("\n\t\tK - Koniec");
return Console.ReadKey(true).KeyChar;
}
static void Main(string[] args)
{
Queue mojaKolejka = new Queue();
Osoba tmp;
char c;
do
{
c = Menu();
switch (c)
{
case 'a':
case 'A':
Osoba.WprowadzOsobe(out tmp);
Queue.Enqueue(mojaKolejka, tmp);
break;
case 'b':
case 'B':
Osoba.WypiszOsobe(
Queue.Dequeue(mojaKolejka));
Console.ReadKey();
break;
case 'c':
case 'C':
Console.WriteLine("Liczba osób w
¬kolejce wynosi: {0}",
Queue.GetLength(mojaKolejka));
Console.ReadKey();
break;
}
}
while (!(c == 'k' || c == 'K'));
}
11. Skompiluj i uruchom program.
Ćwiczenie 3:
Wymagania:
Wymagane jest ukończenie ćwiczenia pierwszego.
Napisz program, który będzie zawierał implementacje kolejki LIFO. Na stos
będziemy wkładać zmienne typu Osoba. Struktura Osoba była
zaimplementowana w ćwiczeniu pierwszym w programie Biblioteka. Koleka
LIFO będzie zaimplementowana przy pomocy listy jednokierunkowej, która
była utworzona w programie pierwszym. Program będzie składał się z dwóch
podzespołów:
Biblioteki dll, o nazwie Stos, która będzie zawierała implementację kolejki
LIFO.
Programu głównego, w którym przetestujemy stos.
1. Dodaj do bieżącego rozwiązania nowy projekt
e. Z menu File wybierz Add/New Project...
f. W oknie dialogowym Add New Project określ następujące
właściwości:
g. typu projektu: Visual C#/Windows
i. szablon: Class Library
ii. nazwa projektu: Stos.
2. Podłącz do programu Stos, podzespoły Biblioteka i Listy.
h. W okienku Solution Explorer, z menu kontekstowego związanego z
elementem reprezentującym projekt Stos wybierz Add Reference...
i.
W okienku Add Reference przejdź do zakładki Projects, zaznacz
projekt Biblioteka oraz Listy i naciśnij OK.
3. Zaznacz, że będziemy korzystać z przestrzeni nazw Biblioteka.i
Listy
using Biblioteka;
using Listy;
4. Zmień nazwę pliku Class1.cs na
Stack
.cs.
5. Zmień nazwę klasy z Class1 na Stack. Do klasy Stack dodaj pole
Czarownice typu List:i od razu je zainicjalizuj:
public struct Stack
{
List Czarownice = new List();
}
6. Do klasy Stack dodaj metodę Push:
public static void Push(Stack s,Osoba os)
{
List.AddToHead(s, os);
}
7. Do klasy Stack dodaj metodę IsEmpty:
public static bool IsEmpty(Stack s)
{
return List.IsEmpty(s.Czarownice);
}
8. Do klasy Stack dodaj metodę Pop:
public static Osoba Pop(Stack s)
{
return List.DeleteFromHead(s.Czarownice);
}
9. Do klasy Stack dodaj metodę GetLength:
public static uint GetLength(Stack s)
{
return (uint)List.GetCount(s.Czarownice);
}
10. Do rozwiązania dodaj nowy projekt, w którym będziemy testowali stos.
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: Inkwizytor.
c.
Uczyń nowo utworzony projekt projektem startowym.
d.
Podłącz do programu Inkwizytor, podzespoły Biblioteka oraz Stos.
e. Zaznacz, że będziemy korzystać z przestrzeni nazw Biblioteka
oraz Stos.
using Biblioteka;
using Stos;
f. Napisz kod testujący kolejkę
static char Menu()
{
Console.Clear();
Console.WriteLine("\n\t\tA - Dodaj
¬czarownicę do stosu");
Console.WriteLine("\n\t\tB - Usuń czarownicę
¬ze stosu");
Console.WriteLine("\n\t\tC - Podaj liczbę
¬czarownic na stosie");
Console.WriteLine("\n\t\tK - Koniec");
return Console.ReadKey(true).KeyChar;
}
static void Main(string[] args)
{
Stack mojaStos = new Stack();
Osoba tmp;
char c;
do
{
c = Menu();
switch (c)
{
case 'a':
case 'A':
Osoba.WprowadzOsobe(out tmp);
Stack.Push(mojaStos, tmp);
break;
case 'b':
case 'B':
Osoba.WypiszOsobe(
Stack.Pop(mojaStos));
Console.ReadKey();
break;
case 'c':
case 'C':
Console.WriteLine("Liczba czarownic
¬na stosie wynosi: {0}",
Stack.GetLength(mojaStos));
Console.ReadKey();
break;
case 'd':
case 'D':
Stack.Clear(ref mojaStos);
Console.WriteLine(
"Stos oprózniony!!!");
Console.ReadKey();
break;
}
}
while (!(c == 'k' || c == 'K'));
}
11. Skompiluj i uruchom program.