Rekurencyjne
struktura danych
- lista
jednokierunkowa
Rekurencyjne
struktura danych
- lista
jednokierunkowa
Przegląd zagadnień
Klasa jako rekord
Lista jednokierunkowa
Dodawanie elementu do listy
Wstawianie elementu do listy
Usuwanie elementu z listy
Inne rodzaje list
Podsumowanie
Pytania sprawdzające
Laboratorium
Klasa jako rekord
Definicja typu referencyjnego
Użycie typu strukturalnego
class Osoba{
public string Imie,Nazwisko;
public int RokUrodzenia;
}
Osoba os =
new Osoba();
os.Imie = "Jan";
os.Nazwisko = "Kowalski";
os.RokUrodzenia = 1988;
...
Console.Write("Pan(i) {0} {1}", os.Imie, os.Nazwisko);
Zarządzana sterta
Kowals
ki
Jan
Stos
.
1988
.
.
o
s
os.RokUrodzenia
os.Imie
os.Nazwisko
Lista jednokierunkowa
Zalety
nie ma zdefiniowanego rozmiaru podczas
tworzenia
łatwość wstawiania elementu
łatwość usuwania elementu
Dane
Następn
y
Dane
Następn
y
...
Dane
Następn
y
Dane
Następn
y
null
głowa (head)
ogon (tail)
węzły listy
Dodawanie elementu do listy (1)
Gdy lista jest pusta
null
głowa
ogon
Nowe
dane
Następn
y
Nowy
Dodawanie elementu do listy (2)
Dodawanie nowego elementu do głowy
Dane
Następny
null
...
gło
w
a
ogon
Nowe
dane
Następn
y
Dane
Następny
Dane
Następny
Nowy
Dodawanie elementu do listy (3)
Dodawanie nowego elementu do ogona
Dane
Następny
null
...
gło
w
a
ogon
Nowe
dane
Następn
y
Dane
Następny
Dane
Następny
Nowy
Wstawianie elementu do listy
Dane
Następny
null
...
gło
w
a
ogon
Nowe
dane
Następn
y
Dane
Następny
Dane
Następny
nowy
poprzedni
Usuwanie elementu z listy (1)
Gdy na liście jest jeden element
null
głowa
ogon
Węzeł
do
usunięci
a
Następn
y
Usuwanie elementu z listy (2)
Usunięcie głowy
Dane
Następny
null
...
gło
w
a
ogon
Następn
y
Dane
Następny
Dane
Następny
Węzeł
do
usunięci
a
Tmp
Usuwanie elementu z listy (3)
Usunięcie ogona
Dane
Następny
null
...
gło
w
a
ogon
Dane
Następny
Dane
Następny
Węzeł
do
usunięci
a
Następn
y
Tmp
Usuwanie elementu z listy (4)
Usunięcie elementu środkowego
Dane
Następny
null
...
gło
w
a
ogon
Dane
Następny
Dane
Następny
Węzeł
do
usunięci
a
Następn
y
Tmp
poprzedni
Inne rodzaje list
Lista dwukierunkowa
Lista cykliczna
Dane
Następn
y
Dane
Następn
y
...
Dane
Następn
y
Dane
Następn
y
null
Dane
Następn
y
Dane
Następn
y
...
Dane
Następn
y
Dane
Następn
y
Poprzed
ni
Poprzed
ni
Poprzed
ni
Poprzed
ni
null
Podsumowanie
Klasa jako rekord
Lista jednokierunkowa
Dodawanie elementu do listy
Wstawianie elementu do listy
Usuwanie elementu z listy
Inne rodzaje list
Podsumowanie
Pytania sprawdzające
Laboratorium
Pytania sprawdzające
Zdefiniuj klasę Samochod, która będzie
zawierać następujące pola: marka,
model, rok produkcji, przebieg.
Jaki popełniono błąd w poniższym
programie?
class Klasa{
public int Pole;
}
...
static void Main(){
Klasa a;
a.Pole = 10;
}
Laboratorium
Ćwiczenie 1:
Implementacja listy
jednokierunkowej, metody:
AddToHead, AddToTail,
DeleteFromHead, DeleteFromTail,
IsEmpty, PrintAll, GetCount
Ćwiczenie 2:
Implementacja listy
jednokierunkowej, metody: Insert,
IsInList, RemoveElement
Ćwiczenie 3:
Implementacja kolejki LIFO i FIFO
przy pomocy listy.