Dr Aleksander Klosov

Algorytmy i Struktury Danych

Wykład

DYNAMICZNE STRUKTURY DANYCH

DYNAMICZNE STRUKTURY DANYCH - Idea

Cechy charakterystyczne:

1. Powtarzające się złożone statyczne jednostki danych (rekordy)

2. Liczba wszystkich danych nie jest z góry określona

3. Dane są łatwo dostępne

4. Dane mogą być umieszczane w dowolnym obszarze pamięci w zależności od wolnego miejsca

5. Rekurencyjność

Dodatkowe wymagania od środowiska programowania:

1. Dynamiczny przydział pamięci

2. Typ danych przechowujący adresy w zamian wartości

RODZAJE DYNAMICZNYCH STRUKTUR DANYCH

Lista jednokierunkowa

Lista dwukierunkowa

Lista cykliczna

Stos

Kolejka FIFO

Sterta

Kolejka priorytetowa

Drzewa binarne

Drzewa zrównoważone

Drzewa wielokierunkowe

B-Drzewa

Grafy

Kopce dwumianowe

Kopce Fibonacciego

ZASTOSOWANIE

1. Listy wysyłkowe, poczta elektroniczna

2. Zarządzanie pamięcią w systemie operacyjnym

3. Przetwarzanie symboliczne w składni języka LISP

4. Sekwencyjny zapis plików w blokach HDD

5. Semafory w językach programowania współbieżnego

6. Obsługa zdarzeń w systemie wielowątkowym, kolejkowanie

7. Wywołanie funkcji w języku C

8. Abstrakcyjne maszyny stosów w kompilatorach czy kalkulatorach

9. Kodowanie Huffmana

10.Modelowanie interfejsów użytkownika

11. Systemy bazodanowe, indeksy typu B⁺-drzewa

12. Przetwarzanie wyrażeń w kompilatorach

13. Sztuczna inteligencja - drzewa decyzyjne

14. Sortowanie topologiczne

15. Planowanie zadań, harmonogramowanie

16. Równoważenie obciążenia, optymalizacja

LISTA JEDNOKIERUNKOWA

Struktura

type T = record {dane;...} nast.: ^T; end

struct T { /* dane; ... */ T* nast.; }

Głowa element1 element2 element3

LISTA JEDNOKIERUNKOWA

Wymiana elementów

B ⇔ C

A.adres = C B.adres = D C.adres = B

Tmp = A.adres A.adres = A.adres.adres Tmp.adres = A.adres.adres A.adres.adres = Tmp

A B C D

STOS

FILO - First In Last Out

Struktura o ograniczonym dostępie!

Operacje:

1. Odkładanie danych na wierzchołek stosu (operacja push())

2. Zdejmowanie danych z wierzchołka stosu (operacja pop())

STOS

Ćwiczenie

Ile elementów będzie zawierał stos oraz jaki element będzie na wierzchu w wyniku wykonania następujących operacji?

Push(A);

Push(B);

Pop();

Push(C);

Push(D);

Pop();

STOS

Odpowiedź

KOLEJKA

FIFO - First In First Out

element1 element2 element3

Operacje:

1. Dodawanie elementu na koniec kolejki (ogon)

2. Usuwanie elementu z początku kolejki (głowa)

// STOS - zastosowanie w uproszczonej postaci

// przedstawienie liczby (>0) w systemie 2-m

#include "stdafx.h"

#include "iostream.h"

struct stos

{

int n;

stos *nast;

} *s;

void init()

{

s = new stos;

s->n = -1; // 'dno' stosu

s->nast = 0;

}

void push(int e)

{ stos *nowy = new stos; // tworzenie w pamięci miejsca na nowy element stosu

nowy->n = e;

nowy->nast = s;

s = nowy;

}

int pop()

{ int wynik = s->n;

stos* stary = s;

s=s->nast;

delete stary; // zwolnienie pamięci

return wynik;

}

// STOS: c.d.

void bin(long liczba)

{int bit;

while(liczba>0)

{

push(liczba%2); // na stos resztę od podziału: 0 lub 1

liczba/=2;

}

// wydruk w odwrotnej kolejności

while((bit=pop()) != -1) cout << bit;

}

void main()

{

long liczba; // w systemie 10-m

cout << "\nPodaj liczbe [10]: "; cin >> liczba;

init(); // inicjacja stosu

cout << "\n[2] = "; bin(liczba);

cout << "\n";

}

STOS - DEFINICJA PEŁNA

typedef int DATA; // można dowolnie zdefiniować typ DATA

struct element

{

DATA dane;

element* nast;

};

struct stos

{

element* szczyt;

long ile_elementow;

// interfejs stosu ----------------------------------------

void init(); // inicjacja stosu

void push(DATA); // zapis na stos

DATA pop(); // odczyt ze stosu

void peek(); // wyświetla dane ze szczytu

long size(); // zwraca rozmiar stosu

};

INICJACJA ORAZ OPERACJA PUSH

void stos::init()

{

element* szczyt = new element;

szczyt->nast = 0;

ile_elementow = 0;

};

void stos::push(DATA d)

{

element *nowy = new element;

nowy->dane = d;

nowy->nast = szczyt;

szczyt = nowy;

ile_elementow++;

}

OPERACJE POP, PEEK, SIZE

DATA stos::pop()

{

element* top = szczyt; // zapamiętać element, aby pozniej usunac

DATA wynik = szczyt->dane; // odczyt danych z usuwanego elementu

szczyt = szczyt->nast; // przejscie do nastepnego na stosie elementu

delete top; // kasowanie z pamięci zdejmowanego elementu

ile_elementow--; // pomniejszenie licznika elementów na stosie

return wynik;

}

void stos::peek()

{ cout << szczyt->dane << ", ";}

long stos::size() {return ile_elementow;}

PROGRAM WYKORZYSTUJĄCY STOS

void main(void)

{

struct stos *bufor;

bufor->init();

for(int i=0; i<N; i++) // symulacja postępujących danych

bufor->push(rand()%N), bufor->peek();

cout << "\n";

while(bufor->size()>0) // lub (bufor->szczyt->nast!=0)

cout << bufor->pop() << ", ";

}

DEFINICJA KOLEJKI

typedef int DATA; // można dowolnie zdefiniować typ DATA

struct element

{

DATA dane;

element* nast;

};

struct kolejka

{

element* glowa;

element* ogon;

long ile_elementow;

// interfejs kolejki ----------------------------------------

void init(); // inicjacja kolejki

void zapisz(DATA); // nowy element dołączany ze strony ogonu

DATA usun(); // zdejmowanie elementu ze strony głowy

void peek(); // wyświetla dane z głowy kolejki

long size(); // zwraca rozmiar kolejki

};

PYTANIA KONTROLNE

1. Czym się różni interfejs kolejki od interfejsu stosu?

2. Jaki odpowiednik ma szczyt stosu w definicji kolejki?

3. Jakie odpowiedniki mają funkcję stosu push oraz pop w definicji kolejki?

4. Kolejka to jest struktura typu FIFO czy FILO?

5. W jakich zagadnieniach wykorzystywany jest stos?

6. W jakich zagadnieniach wykorzystywana jest kolejka?

DEFINICJA LISTY 1-KIERUNKOWEJ

typedef int DATA; // można dowolnie zdefiniować typ DATA

struct element

{

DATA dane;

element* nast;

};

struct lista

{

element* glowa;

element* ogon;

long ile_elementow;

// interfejs listy 1-kierunkowej ----------------------------------------

void init(); // inicjacja listy

void wstaw(DATA,n); // nowy element w pozycji n-tej

DATA usun(n); // usuwanie elementu na pozycji n-tej

void peek(); // wyświetla dane z bieżącego elementu

long size(); // zwraca rozmiar listy

void next(); // przejście do następnego elementu listy

};

ZADANIE

Dano listę 1-kierunkową zawierająca n-elementów. Każdy element posiada składową N wskazującą następnika. Mamy dostęp do dwóch specjalnych elementów Głowa oraz Ogon wskazujących na pierwszy oraz na ostatni element listy. Podać algorytm wstawiania nowego elementu w k-tej pozycji listy, przy k = [1...n+1]. W trakcie wstawiania można korzystać tylko z jednej dodatkowej zmiennej wskazującej na element listy.

Rozwiązanie w pseudokodzie:

Algorytm_1(element nowy)

{

ListaInit(głowa, ogon);

PodajDane(k,dane);

If(k<=n+1 and k>=1)

{

if(k = = 1) Algorytm_1_1(dane);

else if(k = = n+1) Algorytm_1_3(dane);

else Algorytm_1_2(dane,k);

}

}

Algorytm_1_1(element nowy) // Wstawianie na początku

{

element bieżący = głowa;

nowy.N = bieżący;

głowa = nowy;

}

Algorytm_1_2(element nowy, int k) // Wstawianie w środku

{

element bieżący = głowa;

int kolejny = 1;

while(kolejny < k-1) // musi zostać przed k-tym obecnie elementem

bieżący = bieżący.N;

nowy.N = bieżący.N;

bieżący.N = nowy;

}

Algorytm_1_3(element nowy) // Wstawianie na końcu

{

element bieżący = ogon;

bieżący.N = nowy;

nowy.N = null;

ogon = nowy;

}

ZADANIA SAMODZIELNE

Dano listę 1-kierunkową zawierająca n-elementów. Każdy element posiada składową N wskazującą następnika. Mamy dostęp do dwóch specjalnych elementów Głowa oraz Ogon wskazujących na pierwszy oraz na ostatni element listy. Podać algorytm usuwania dowolnego elementu z k-tej pozycji listy, przy k = [1...n]. W trakcie operacji można korzystać tylko z jednej dodatkowej zmiennej wskazującej na element listy.

Dano listę 1-kierunkową zawierająca n-elementów. Każdy element posiada składową N wskazującą następnika. Mamy dostęp do dwóch specjalnych elementów Głowa oraz Ogon wskazujących na pierwszy oraz na ostatni element listy. Podać algorytm zamiany pierwszego elementu z elementem w k-tej pozycji listy, przy k = [2...n]. W trakcie operacji można korzystać tylko z jednej dodatkowej zmiennej wskazującej na element listy.

dane

adres

adres

dane

null

dane

adres

adres

null

dane

adres

dane

adres

dane

Ogon

null

dane

adres

dane

adres

dane

Głowa

adres

Dane3

adres

Dane2

adres

Dane1

Góra

Góra

... N

... N

adres

A

adres

C

Głowa

Ogon

Null

1 N

i N

n N

... N

... N

Głowa

Ogon

Null

1 N

i N

n N

n N

i N

1 N

Null

Ogon

Głowa

... N

... N

Null

Ogon

Głowa

n N

... N

i N

... N

1 N

---