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.