1. Omów pojęcie: złożoność obliczeniowa algorytmów.

złożoność obliczeniowa - nakład czasu lub zasobów maszyny realizującej algorytm, niezbędny dla jego prawidłowego wykonania
Analiza algorytmów - złożoność obliczeniowa jest podstawową własnością określaną dla algorytmów. Zadaniem analizy algorytmu jest określenie tej złożoności, a co za tym idzie realizowalności algorytmu.
Czynniki wpływające na złożoność algorytmów:
a) Rozmiar zadania - rozmiar danych niezbędnych dla realizacji algorytmu. Bierze się pod uwagę:
rozmiar danych wejściowych
rozmiar danych roboczych
rozmiar danych wyjściowych
b) Czas działania algorytmu - liczba kroków przekładająca się na czas faktycznej pracy maszyny realizującej algorytm. Istotne znaczenie mają w tym przypadku:
złożoność rozwiązywanego zadania
sposób konstrukcji algorytmu
wydajność maszyny realizującej obliczenia

Złożoność zasobowa (pamięciowa) - wyrażana w skali zajętości zasobów (PAO, pamięci zewnętrznych itp.) niezbędnych dla realizacji algorytmu
Złożoność czasowa - wyrażana w skali czasy wykonania algorytmu (liczba kroków, aproksymowany czas rzeczywisty

2. Jaka jest istota zasady dekompozycji i abstrakcji w programowaniu?

Bardzo często w naszym codziennym działaniu rozwiązując różne problemy posługujemy się następującymi metodami:
Dekompozycji - dzielimy większy problem na mniejsze - łatwiejsze do ogarnięcia umysłem podproblemy. Wydzielone fragmenty możemy dzielić w miarę potrzeb na jeszcze mniejsze kawałki.
Abstrakcji - każdy z podproblemów rozwiązujemy oddzielnie abstrahując w tym czasie od pozostałych podproblemów.
Po złożeniu wszystkich rozwiązanych podproblemów uzyskujemy rozwiązanie całości.

3. Przedstaw przykład ilustrujący wykorzystanie zjawiska iteracji i zjawiska rekurencji.

a)iteracyjne wykonanie funkcji Fibbonaciego

long int petlaFib(int a)

{

register int i=2, ostatni=0, zm1;

long int zm2 =1;

if (a<2) return a;

else

{

for ( ; i<=a; ++i) {

zm1 = zm2;

zm2 += ostatni;

ostatni = zm1;

}

return zm2;

}

b) rekurencyjne wykonanie funkcji Fibbonaciego

long int Fib (int a)

{

if (a<2)

return a;

else

return Fib(a-2) + Fib (a-1);

}

4. Wymień i omów podstawowe proste predefiniowane typy danych w języku C.

Całkowite:

char (opcjonalnie unsigned char) - ma rozmiar pojedynczej jednostki pamięci potrzebnej do przechowania znaku w systemie czyli zazwyczaj 1 Bajt. W C nie ma rozróżnienia między typem znakowym a całkowitym, zatem zmienną char można inicjować zarówno znakiem (w pojedyncych cudzysłowach!!!), lub liczbą całkowitą

short (opcjoalnie unsigned short) - zazwyczaj ma rozmiar pomiędzy char a int, czyli najczęściej 2 Bajty

int (opcjonalnie unsigned int) - ma rozmiar naturalnego rejestru w procesorze (w przypadku x86 są to 32 bity, Ultra sparc 64 bity). Zmienna lub stała tego typu może być dodatnia, ujemna lub równa zero. Zakres wartości zależy od komputera

long (opcjonalnie unsigned long) - W teorii zmienna większa niż int, w praktyce często identyczna z int.

Zmiennoprzecinkowe:

float - Zmienna rzeczywista pojedynczej precyzji (odpowiednik real z pacala)

double - Zmienna rzeczywista podwójnej precyzji (odpowiednik extended z pascala)

5. Omów metodę deklarowania i sposób realizacji zmiennych wskaźnikowych.

Wskaźnik jest specjalnym typem danych. Zmienna typu wskaźnikowego przechowuje adres (wskazanie do) innego obiektu (zmiennej) w pamięci operacyjnej. Wskazania poprzez typy wskaźnikowe można traktować tak jak nazwane adresy w pamięci operacyjnej. Dzięki wskaźnikom można w stosunkowo prosty sposób operować na adresach w pamięci operacyjnej.

Dwa podstawowe operatory dla typów wskaźnikowych to:

operator zwracający wartość przechowywaną pod konkretnym wskazaniem - oznaczany gwiazdką - *

operator zwracający adres zmiennej wskazywanej - oznaczany „ampersandem” - &

Deklaracja zmiennej wskaźnikowej w języku C:

typ *zmienna_wskaźnikowa

(znak gwiazdki oznacza wskaźnik - jest on bardzo ważny!!!)

(zmienna_wskaźnikowa = = wskazanie na zmienną)

Deklaracja wskaźnika na zmienną całkowitoliczbową

int *p;

(p = = wskazanie na zmienną)

Deklaracja wskaźnika na zmienną całkowitoliczbową

int p, q; (*p- wskaźnik na zmienną całkowitoliczbową; q - zmienna całkowitoliczbowa)

Ustawienie wskazania z p na q:

p = & q; (znak & (ampersand) oznacza ustawienie wskazania adresowego dla wskaźnika)

Ustawienie wskazania na zmienną całkowitoliczbową:

int *p, q;

p = &q;

Podstawienie wartości liczby:

q = 150; (ustawienie wartości przez zmienną wskazywaną)

lub

*p = 150; (ustawienie wartości przez zmienną wskaźnikową - odwołanie niejawne do zmiennej q)

Inkrementacja wartości wskaźnika „p” oznacza przejście do adresu:

„p + liczba bajtów dla wskazywanego przez p”

dekrementacja wartości wskaźnika „p” oznacza przejście do adresu:

„p - liczba bajtów dla wskazywanego przez p”

Dla wskaźnika do typu char będzie to przechodzenie co 1 bajt,

Dla wskaźnika do typu int będzie to przechodzenie co 2 bajty,

Dla wskaźnika do typu float - przechodzenie co 4 bajty

Dla wypisania wartości wskaźników w funkcji printf stosuje się operator konwersji: %p.

Język C w sposób wyjątkowy utożsamia wskaźniki i tablice. Tak faktycznie, to w wyniku deklaracji zmiennej tablicowej, środowisko języka C tworzy wskaźnik na początek tej tablicy. Miejsca na pozostałe elementy tablicy są zajmowane w zależności od rozmiaru tablicy. Tablica zajmuje spójny obszar pamięci operacyjnej. Tak więc do tablic możemy odnosić się w sposób tradycyjny, tzn. przy pomocy nazwy zmiennej z indeksem tablicy: tab[i] lub stosując arytmetykę wskaźników. Takie traktowanie tablic jest szczególnie przydatne dla tzw. tablic otwartych i łańcuchów znaków - bez wstępnego określenia ich długości. Środowisko języka C jest w stanie na bieżąco reagować na aktualne potrzeby programisty w tym zakresie. Takich cech nie ma większość innych języków programowania.

Kiedy do wskaźnika p podstawiamy wskazanie na tablicę tab nie używamy znaku & (ampersand). Wynika to z tego, że zmienna tablicowa jest niejawnie realizowana przez środowisko języka C jako wskaźnik do początku tablicy. Wtedy stosujemy podstawienie:

p=tab;

Stosowanie arytmetyki wskaźników przy tablicach jest możliwe, ale niezbyt wygodne. Lepiej jest wykorzystywać zwykłe indeksowanie tablic - efekt jest ten sam w obu przypadkach. Należy zwrócić uwagę na różnicę pomiędzy poniższymi wyrażeniami:

*p++; /*zwiększa wskazanie p do następnego elementu*/

*(p+1) /*daje wskazanie do następnego bez zwiększania p*/

6. Przedstaw definicję liniowej struktury danych.

Liniową strukturą danych nazywamy strukturę danych S=(D, R, e), w której relacja porządkująca N opisuje powiązania pomiędzy elementami odpowiednio dla poszczególnych rodzajów list.

gdzie:

D - oznacza zbiór danych elementarnych di, i = 1,..,|D| (i - jest indeksem poszczególnych danych),

R={rwe, N} - jest zbiorem dwóch relacji określonych na strukturze danych:

• relacja wejścia do struktury danych S,

• relacja następstwa (porządkująca) strukturę S,

e - jest elementem wejściowym do struktury danych S (nie jest to dana wchodząca w skład struktury danych S).

Wyróżniamy cztery rodzaje list (jednopoziomowych):

• jednokierunkowe listy niecykliczne

• dwukierunkowe listy niecykliczne

• jednokierunkowe listy cykliczne (pierścienie jednokierunkowe)

• dwukierunkowe listy cykliczne (pierścienie dwukierunkowe)

7. Omów podstawowe metody realizacji liniowych struktur danych.

Realizacje sekwencyjne - wtedy, gdy z góry znamy maksymalny rozmiar przetwarzanej struktury liniowej i z góry chcemy zarezerwować dla niej określony zasób (pamięć operacyjne, pamięć zewnętrzna). W czasie wytwarzania programów komputerowych bazujemy wtedy na zmiennych statycznych,

Realizacje łącznikowe - wtedy, gdy rozmiar struktury nie jest z góry znany i w czasie jej przetwarzania może istnieć konieczność dodawania do niej nowych elementów lub ich usuwania. W czasie wytwarzania programów komputerowych bazujemy wtedy na zmiennych dynamicznych (wskaźnikowych),

Realizacje łącznikowo-sekwencyjne - połączenie obu powyższych metod - wtedy gdy konieczny jest odpowiedni balans pomiędzy zmiennymi statycznymi i dynamicznymi

8. Omów logikę kolejki FIFO.

Kolejka (ang. FIFO - First In, First Out; pierwszy na wejściu, pierwszy na wyjściu) - liniowa struktura danych, znaczeniowo odpowiadająca nazwie: nowe dane dopisywane są na końcu kolejki, a jako pierwsze obsługiwane są dane z początku.

Specjalną modyfikacją jest kolejka priorytetowa - każda ze znajdujących się w niej danych dodatkowo ma przypisany priorytet, który modyfikuje kolejność późniejszego wykonania. Oznacza to, że pierwsze na wyjściu niekoniecznie są te dane, które w kolejce oczekują najdłużej, ale te o największym priorytecie.

Kolejkę spotyka się przede wszystkim w sytuacjach związanych z różnego rodzaju obsługą zdarzeń. W szczególności w systemach operacyjnych ma zastosowanie kolejka priorytetowa, przydzielająca zasoby sprzętowe uruchomionym procesom.

Przeciwieństwem kolejki jest stos, bufor (ang. LIFO - Last In, First Out; ostatni na wejściu, pierwszy na wyjściu), w którym jako pierwsze obsługiwane są dane wprowadzone jako ostatnie.

9. Omów logikę stosu.

Stos (ang. LIFO - Last In, First Out; ostatni na wejściu, pierwszy na wyjściu), jest liniową strukturą danych, na której można wykonać dwie operacje: odłożenia elementu na stos i zdjęcia elementu ze stosu, i w której jako pierwsze obsługiwane są dane wprowadzone jako ostatnie. Odłożenie elementu na stos powoduje, że znajduje się on na tzw. wierzchołku stosu i może być jako pierwszy zdjęty ze stosu. Odłożenie kolejnego elementu na stos uniemożliwia dostęp do poprzednio odłożonych elementów - mogą być zdejmowane tylko w porządku odwrotnym do odkładania.

10. Omów ideę tablic rzadkich.

Tablice rzadkie są jednym z przypadków liniowych struktur danych. Ich cechą charakterystyczną jest to, że przechowują one jedynie wartości niezerowe.
Pozycja tablicy z wartością zerową nie występuje.
W tablicy są więc przechowywane wyłącznie wartości znaczące(różne od wartości domyślnej).
Tablice rzadkie realizujemy wyłącznie w postaci łącznikowej

11. Przedstaw przykłady realizacji tablic rzadkich.

Tablice rzadkie są jednym z przypadków liniowych struktur danych. Ich cechą charakterystyczną jest to, że przechowują one jedynie tzw. wartości niezerowe,

Po prostu pozycja tablicy z wartością zerową nie występuje (brak pozycji w macierzy oznacza wartość zerową),

W tablicy są więc przechowywane wyłącznie wartości znaczące (tzn. różne od ustalonej z góry wartości domyślnej)

Tablice rzadkie realizujemy wyłącznie w postaci łącznikowej (dynamiczne struktury danych)

Macierze rzadkie mogą być wykorzystywane do implementacji macierzy incydencji grafów

Częstym zastosowaniem jest przechowywanie obrazów rastrowych (szczególnie wtedy, gdy na obrazie jest mało „zapalonych” punktów)

Program pobierający wartości i tworzący z nich tablice rzadką; zero jako wartość nie znacząca

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

struct list{

int nrkol;

struct list *nextkol;

struct elem *start;

};

struct elem{

int nrwier;

int wart;

struct elem *nextelem;

};

int main (void)

{

struct list *lista;

struct elem *element;

struct list *prvlista;

struct list *aktlista;

struct elem *aktelem;

int tmp,dalej=1,ok=1;

int kolumna,dana,wiersz;

lista=NULL;

element=NULL;

clrscr ();

do

{ //pobieranie danych

printf("dana: ");

scanf("%d",&dana);

printf("kolumna: ");

scanf("%d",&kolumna);

printf("wiersz: ");

scanf("%d",&wiersz);

if(dana!=0)

{

aktlista=lista;

//jezeli pusta lista

if(aktlista==NULL)

{

lista=malloc(sizeof(struct list));

lista->nrkol=kolumna;

element=malloc(sizeof(struct elem));

element->wart=dana;

element->nextelem=NULL;

element->nrwier=wiersz;

lista->nextkol=NULL;

lista->start=element;

}

else //lista niepusta

{

if(kolumna<aktlista->nrkol) //wstawiamy kol przed pierwsza

{

lista=malloc(sizeof(struct list));

lista->nrkol=kolumna;

element=malloc(sizeof(struct elem));

element->wart=dana;

element->nextelem=NULL;

element->nrwier=wiersz;

lista->nextkol=aktlista;

lista->start=element;

}

if(kolumna==aktlista->nrkol) //wstaiwamy do pierwszej kolumny

{

aktelem=aktlista->start;

while(aktelem->nrwier!=wiersz && aktelem->nextelem!=NULL)

{

aktelem=aktelem->nextelem;

}

if(aktelem->nrwier==wiersz) //jezeli juz istnieje

{ //to zmieniamy

aktelem->wart=dana;

}

else //jezeli nie istnieje to tworzymy nowy

{ //na koncu listy

aktelem->nextelem=malloc(sizeof(struct elem));

aktelem->nextelem->nextelem=NULL;

aktelem->nextelem->wart=dana;

aktelem->nextelem->nrwier=wiersz;

}

}

if(kolumna>aktlista->nrkol) //wstawiamy kolumne po pierwszej

{

{

while(kolumna>aktlista->nrkol && aktlista->nextkol!=NULL)

{

prvlista=aktlista;

aktlista=aktlista->nextkol;

}

if(aktlista->nextkol==NULL) //wstawiamy na koniec listy{

if(kolumna==aktlista->nrkol) //do istniejacej kolumny

{

aktelem=aktlista->start;

while(aktelem->nrwier!=wiersz && aktelem->nextelem!=NULL)

{

aktelem=aktelem->nextelem;

}

if(aktelem->nrwier==wiersz)

{

aktelem->wart=dana;

}

else

{

aktelem->nextelem=malloc(sizeof(struct elem));

aktelem->nextelem->nextelem=NULL;

aktelem->nextelem->wart=dana;

aktelem->nextelem->nrwier=wiersz;

}

}

else

{

if(aktlista->nrkol<kolumna)

// wstawiamy na koniec listy do nowej kolumny

{

aktlista->nextkol=malloc(sizeof(struct list));

aktlista->nextkol->nextkol=NULL;

aktlista->nextkol->nrkol=kolumna;

element=malloc(sizeof(struct elem));

element->nextelem=NULL;

element->wart=dana;

element->nrwier=wiersz;

aktlista->nextkol->start=element;

}

else

{

prvlista->nextkol=malloc(sizeof(struct list));

prvlista->nextkol->nextkol=aktlista;

prvlista->nextkol->nrkol=kolumna;

element=malloc(sizeof(struct elem));

element->nrwier=wiersz;

element->wart=dana;

element->nextelem=NULL;

prvlista->nextkol->start=element;

}

}

}

else//wstawiamy kolumne pomiedzy 2 istniejace

{

prvlista->nextkol=malloc(sizeof(struct list));

prvlista->nextkol->nextkol=aktlista;

prvlista->nextkol->nrkol=kolumna;

element=malloc(sizeof(struct elem));

element->nextelem=NULL;

element->nrwier=wiersz;

element->wart=dana;

prvlista->nextkol->start=element;

}

}

}

}

}

printf("czy dalej? 0-nie");

scanf("%d",&dalej);

}while(dalej);

//wypisywanie listy

aktlista=lista;

do

{

if(aktlista->nextkol==NULL) ok=0;

aktelem=aktlista->start;

while(aktelem->nextelem!=NULL)

{

printf("dana: %d kolumna: %d wiersz: %d\n",aktelem->wart,\

aktlista->nrkol,aktelem->nrwier);

aktelem=aktelem->nextelem;

}

printf("dana: %d kolumna: %d wiersz: %d\n",aktelem->wart,\

aktlista->nrkol,aktelem->nrwier);

aktlista=aktlista->nextkol;

}while(ok);

getche ();

return 0;

}

12. Omów definicję tablicy rozproszonej.

Definicja tablicy rozproszonej (z haszowaniem)

Tablicą rozproszoną nazywamy trójkę uporządkowaną T=( K,D,h ) , gdzie

K={k1, k2, k3,….,kn} — zbiór kluczy,

D={d1, d2, d3, ….,dn} — zbiór adresów,

h — funkcja mieszająca (haszująca) zdefiniowana następująco:

h: K→ D

Tradycyjnym obszarem zastosowań tablic rozproszonych są zagadnienia związane z przetwarzaniem danych.

Tablice rozproszone, funkcja haszująca

Zadaniem funkcji haszującej h jest w miarę równomierne obciążenie tablicy rozproszonej (jej komórek). Zagadnienie definiowania funkcji mieszającej jest istotne dla efektywności obliczeń realizowanych na bazie tablic rozproszonych.

Ma to szczególne znaczenie dla tablic rozproszonych przetwarzanych bezpośrednio w nośnikach zewnętrznych (taśmach, dyskach)

13. Na czym polega zjawisko konfliktu w tablicach rozproszonych.

Kolizją (konfliktem) w tablicy rozproszonej nazywamy sytuację powstałą wtedy, gdy:

a zadaniem funkcji haszującej h jest równomierne obciążanie tablicy rozproszonej. W przypadku konfliktu takie równomierne obciążanie nie zachodzi.

Elementy k_i, k_j biorące udział w kolizji nazywamy synonimami.

14. Co to jest i kiedy występuje synonim w tablicach rozproszonych?

Synonimy są to elementy biorące udział w kolizji (konflikcie) w tablicy rozproszonej.

Występuja one gdy:

∃ ki,kj ∋ K , ki ≠ kj •( h(ki) = h(kj) )

czyli gdy funkcja haszująca dla dwóch różnych elementów zwraca tę samą wartość

15. Przedstaw i omów przykłady trzech różnych funkcji haszujących.

Zadaniem funkcji haszującej h jest w miarę równomierne obciążanie tablicy rozproszonej (jej komórek). Zagadnienie definiowania funkcji mieszającej jest istotne dla efektywności obliczeń realizowanych na bazie tablic rozproszonych. Ma to szczególnie duże znaczenie dla tablic rozproszonych przetwarzanych bezpośrednio w nośnikach zewnętrznych

.

Metody haszowania w tablicach rozproszonych

Randomizacja: - funkcja niezależna od rozkładu klucza, jest prosta, lecz rzadko używana

di = randomize(ki)

Metoda kwadratu środka:

K O W A L S K I - klucz

21 25 33 11 22 29 21 19 - kody znaków

3 11 22 2 - wycięty środek

6 8 5 9 1 3 3 2 8 4 - kwadrat wyciętej liczby

9 1 3 - wyliczony adres d

Metoda składania

K O W A L S K I - klucz

21 25 33 11 22 29 21 19 29 21 19 - kody znaków

21 25 33 11 22 29 21 19 21 25 00 - sposób składania

d = 212500 + 331122 + 292119 = 834741 - wyliczony adres

Metoda dzielenia (bardzo efektywna)

adres wyliczany według formuły:

d = wart(k) mod p, gdzie:

d - adres w tablicy rozproszonej (czasami: indeks)

wart(k) - wartość wyliczona na podstawie klucza - inną metodą, np. metodą składania lub kwadratu środka

p - liczba pozycji w tablicy

Przykład:

tablica ma 1000 pozycji

zakończenie przykładu przedstawionego dla metody kwadratu środka:

d1 = 913 mod 1000 = 913

zakończenie przykładu przedstawionego dla metody składania:

d2 = 834741 mod 1000 = 741

16. Omów przykład usuwania konfliktów w tablicach rozproszonych bez

obszarów nadmiarowych.

Tablice rozproszone bez obszaru nadmiarowego - tutaj dane

znajdują się wyłącznie w obszarze bazowym

szukanie kwadratowe

di = (d0 + a * i + b * i2) mod p,

lub wzór uproszczony:

di = (d0 + i2), gdzie

d0 = h(k) - wynik początkowego haszowania klucza

di - nowy adres, wyliczany wtedy, gdy w (i-1)-szym kroku

wystąpił konflikt

a, b - stałe współczynniki empiryczny

i - numer kolejnego kroku szukania (0 <= i <= p)

p - liczba pozycji w tablicy

szukanie liniowe

di = (d0 + a * i) mod p, gdzie

d0 = h(k) - wynik początkowego haszowania klucza

di - nowy adres, wyliczany wtedy, gdy w (i-1)-szym kroku

wystąpił konflikt

a - stały współczynnik empiryczny

i - numer kolejnego kroku szukania (0 <= i <= p)

p - liczba pozycji w tablicy

szukanie sześcienne

di = (d0 + i3), gdzie

d0 = h(k) - wynik początkowego haszowania klucza

di - nowy adres, wyliczany wtedy, gdy w (i-1)-szym kroku

wystąpił konflikt

i - numer kolejnego kroku szukania (0 <= i <= p)

p - liczba pozycji w tablicy

17. Omów przykład usuwania konfliktów w tablicach rozproszonych z obszarem nadmiarowym.

Z wykorzystaniem obszarów nadmiarowych:

- listy synonimów::: pierwsze wstawienie do wolnego miejsca w obszarze bazowym... Kiedy wyliczona w haszowaniu pozycja z obszaru bazowego jest zajęta, to wstawiamy nowy element do listy synonimów podwieszonej pod ta pozycję w obszarze bazowym. Listy synonimów tworzą obszary nadmiarowe.

- rozproszona lista indeksowa: wszystkie dane są wstawiane do obszaru nadmiarowego

Obszary nadmiarowe są organizowane w postaci zestawu posortowanych wykazów liniowych lub posortowanych i zrównoważonych wykazów leksykograficznych.

18. Przedstaw w języku C definicję typów danych dla listy jednokierunkowej i dla listy dwukierunkowej.

struct lista_jedno_kier{

int dane;

struct lista_jedno_kier * nastepny;

};

struct lista_dwu_kier{

int dane;

struct lista_dwu_kier * nastepny, * poprzedni;

};

typedef int Telem;
typedef struct Telem_listy {
  Telem_listy* nast_elem;
  Telem elem;
};
typedef Telem_listy* Tlista;

typedef int Telem;
typedef struct Telem_listy {
  Telem_listy* nast_elem;
  Telem_listy* poprz_elem;
  Telem elem;
};
typedef Telem_listy* Tlista;

19. Przedstaw w języku C implementację operacji wstawienia elementu do listy jednokierunkowej niecyklicznej.

struct list{

int dane;

struct list *nextPtr;

};

int main()

{

struct list *lista;

struct list *prvLista;

struct list *pom;

int dalej=1,tmp=0;

lista=NULL;

do{

printf("Podaj zawartosc: ");

scanf("%d",&tmp);

prvLista=lista;

if(prvLista==NULL)

{

lista=malloc(sizeof(struct list));

lista->dane=tmp;

lista->nextPtr=NULL;

}

else

{

if(prvLista->nextPtr==NULL)

{

if(prvLista->dane<tmp)

{

prvLista->nextPtr=malloc(sizeof(struct list));

prvLista->nextPtr->dane=tmp;

prvLista->nextPtr->nextPtr=NULL;

}

else

{

pom=lista;

lista=malloc(sizeof(struct list));

lista->dane=tmp;

lista->nextPtr=pom;

}

}

else

{

pom=prvLista->nextPtr;

if(prvLista->dane>tmp)

{

pom=lista;

lista=malloc(sizeof(struct list));

lista->dane=tmp;

lista->nextPtr=pom;

}

else

{

while(pom->nextPtr!=NULL && pom->dane<tmp)

{

pom=pom->nextPtr;

prvLista=prvLista->nextPtr;

printf("a");

}

if(pom->nextPtr==NULL)

{

pom->nextPtr=malloc(sizeof(struct list));

pom->nextPtr->dane=tmp;

pom->nextPtr->nextPtr=NULL;

}

else

{

pom2=prvLista->nextPtr;

prvLista->nextPtr=malloc(sizeof(struct list));

prvLista->nextPtr->dane=tmp;

prvLista->nextPtr->nextPtr=pom2;

}

}

}

printf(”czy dalej?0-nie”)

scanf(”%d”,&dalej)

}

}while(dalej);

return 0;

}

20. Przedstaw w języku C implementację operacji usunięcia elementu z listy jednokierunkowej niecyklicznej.

Algorytm usuwania elementu z listy jednokierunkowej:

Dane wejściowe:

- dowiązanie głowy listy `startPtr'

- opis elementu, np. wartość danej elementarnej

1. Jeżeli dane są zgodne z danymi pierwszego elementu listy to: usuń pierwszy element listy

2. W p.p. znajdź element do usunięcia w liście

3. Jeżeli nie znaleziono elementu, generuj komunikat

4. W p.p. usuń znaleziony element

Algorytm:

int delete (NodePtr *startPtr, char nazwa)

{

NodePtr prevPtr, curr Ptr,tempPtr;

int retcode;

if(*startPtr = = NULL) /* lista pusta */

retcode = 0;

else

{

if ( nazwa = = ( *startPtr ) → data) /* usuń pierwszy element listy */

{

tempPtr = *startPtr;

*startPtr = ( *startPtr ) → next;

free ( tempPtr );

retcode = 1;

}

else

{ /* znajdź w liście element do usunięcia */

prevPtr = *startPtr; /* początek listy */

currPtr = ( *startPtr ) → next; /* drugi element */

while ( currPtr != NULL && currPtr → data != nazwa )

{

prevPtr = currPtr;

currPtr = currPtr → next;

}

if ( currPtr = = NULL )

retcode = 0; /* node not found */

else

{ /* usuń znaleziony element */

tempPtr = currPtr;

prevPtr → next = currPtr → next;

free ( tempPtr );

retcode = 1;

}}

}

return retcode;

}

21. Przedstaw w języku C implementację operacji wstawienia elementu do listy dwukierunkowej niecyklicznej.

Tworzenie listy dwukierunkowej przypomina tworzenie listy jednokierunkowej z tą różnicą, że należy zatroszczyć się o dwa wskaźniki.

Utwórzmy strukturę:

struct adres{

char imie [40];

char ulica [20];

char miasto [20];

struct adres *nastepny; /* łącze do następnego adresu */

struct adres *poprzedni; /* łącze do poprzedniego adresu */

};

void d_lista (struct adres *i, struct adres **ostatni)

{

if (!*ostatni) *ostatni = i; /* czy to pierwszy element listy */

else (*ostatni) -> nastepny = i;

i -> nastepny = NULL;

i -> poprzedni = *ostatni;

*ostatni = i;}

Funkcja d_lista() umieszcza każdy nowy element na końcu listy.

22. Przedstaw w języku C implementację operacji usunięcia elementu z listy dwukierunkowej niecyklicznej.

struct list{

int data;

struct list *prvPtr;

struct list *nextPtr;

};

...

struct list *lista; //to jest poczatek listy

struct list *pom; //pomocnicza

...

int tmp=0;

pom=lista; //ustawia na poczatek listy

printf("Co chcesz usunac?\n");

scanf("%d",&tmp);

if(pom==NULL) //gdy lista jest pusta

{

printf("Lista jest pusta");

}

else

{

while(pom->nextPtr!=NULL && pom->dane!=tmp)

{

pom=pom->nextPtr;

}

if(pom->data==tmp)

{

if(pom->prvPtr!=NULL)

{

pom->prvPtr->nextPtr=pom->nextPtr;

}

else if(pom->nextPtr!=NULL)

{

pom->nextPtr->prvPtr=NULL;

f(pom->nextPtr!=NULL)

{

pom->nextPtr->prvPtr=pom->prvPtr;

else if(pom->prvPtr!=NULL)

{

pom->prvPtr->nextPtr=NULL;

}

if(pom->prvPtr==NULL && pom->nextPtr==NULL) //tylko 1 el. w liscie

{

lista=NULL; //lista jest wtedy pusta

}

free(pom);

}

else

{

printf("Nie ma takiego elementu!");

}

}

23. Przedstaw w języku C implementację operacji wstawienia elementu do listy jednokierunkowej cyklicznej.

Algorytm dołączania elementu do listy jednokierunkowej (w porządku rosnącym):

struct adres {

char nazwisko[40];

char ulica[40];

char miasto[20];

struct adres *następny; //łącze do anstępnego adresu

};

void lista (struct adres *i, // nowy element do dopisania

struct adres **początkowy, // początek listy

struct adres **końcowy) //koniec listy

{

struct adres *stary, *p;

p= *początkowy;

if (!*końcowy) {

/pierwszy element listy

i→ następny = NULL;

*końcowy = i;

*początkowy = i;

return;

}

stary = NULL;

while (p) {

if (strcmp (p→ nazwisko, i→ nazwisko) <0) {

stary = p;

p = p→ następny;

}

else {

if (stary) { // umieść w środku

stary → następny =i;

i→ następny = p;

return;

}

i → następny =p; // nowy, pierwszy element

*początkowy = i;

return;

}

}

(*końcowy) → następny = i; //dopisać na końcu

i → następny = NULL;

*końcowy = i;

}

24. Przedstaw w języku C implementację operacji usunięcia elementu z listy jednokierunkowej cyklicznej.

Void sldelete(

Struct adress p /* poprzedni element*/

Struct adress i /*element do usiniecia*/

Struct adress **start /*początek listy*/

Struct adress **last) /*koniec listy*/

{

if(p)

p->next = i->next;

else *start = i-> next;

if (i==*last && p) *last =p;

25. Przedstaw w języku C implementację operacji wstawienia elementu do listy dwukierunkowej cyklicznej.

struct Node

{

char data;

struct Node *prev;

struct Node *next;

};

typedef struct Node *NodePtr;

int insert(NodePtr *startPtr, char nazwa)

{

NodePtr newPtr, currPtr, prevPtr;

int retcode = 1;

/* utworz element Node: */

newPtr = (NodePtr) malloc(sizeof(struct Node));

if(newPtr == NULL) retcode = 0;

else

{ /* ustal dane elementarne */

newPtr -> data = nazwa;

newPtr -> next = NULL;

newPtr -> prev = NULL;

if(*startPtr == NULL) /* Lista pusta */

{

*startPtr = (NodePtr)malloc(sizeof(struct Node));

if(startPtr == NULL) retcode = 0;

else

{

(*startPtr) -> next = *startPtr;

(*startPtr) -> prev = *startPtr;

}

}

prevPtr = *startPtr;

currPtr = (*startPtr) -> next;

/* znajdz miejsce wstawienia */

while ( (currPtr != *startPtr) && (nazwa > currPtr->data) )

{

prevPtr = currPtr;

currPtr = currPtr -> next;

}

/* wstaw element */

newPtr -> next = currPtr;

newPtr -> prev = prevPtr;

prevPtr -> next = newPtr;

currPtr -> prev = newPtr;

retcode = 1;

}

return retcode;

} /* insert */

26. Przedstaw w języku C implementację operacji usunięcia elementu z listy dwukierunkowej cyklicznej.

struct Node

{

char data;

struct Node *prev;

struct Node *next;

};

int delete(NodePtr *startPtr, char nazwa)

{

NodePtr prevPtr, currPtr, tmpPtr;

int retcode;

if( (*startPtr == NULL)

|| ( (*startPtr) -> next == *startPtr)

|| ( (*startPtr) -> prev == *startPtr) ) retcode = 0;

else /* znajdz element do usuniecia */

{

prevPtr = *startPtr;

currPtr = (*startPtr) -> next;

while( (currPtr != *startPtr) && (currPtr -> data != nazwa) )

{

prevPtr = currPtr;

currPtr = currPtr -> next;

}

if(currPtr == *startPtr) retcode = 0; /* nie znaleziono */

else

{

tmpPtr = currPtr;

prevPtr -> next = currPtr -> next;

free(tmpPtr); /* usun */

retcode = 1;

}

}

return retcode;

} /* delete */

27. Przedstaw ideę drzewiastej struktury danych stopnia drugiego i wykazu leksykograficznego.

Drzewiastą strukturą danych nazywamy strukturę danych S=(D, R, e), w której relacja porządkująca N opisuje kolejne, rekurencyjne powiązania pomiędzy danymi elementarnymi drzewa, tworzącymi kolejne „poddrzewa”.

Strukturą drzewiastą stopnia drugiego (drzewem binarnym) nazywamy drzewo, w którym każdy węzeł ma co najwyżej dwóch następników - lewego i prawego. Ostatnimi potomkami są liście - elementy, które nie mają potomków.

Rodzaje struktur drzewiastych:

- zupełne drzewo binarne - każdy węzeł, z wyjątkiem liści, ma dokładnie dwóch potomków;

- drzewo poszukiwań binarnych (BST) - dla każdego węzła (nie liścia) wszystkie wartości przechowywane w lewym poddrzewie są mniejsze od jego wartości oraz przeciwnie dla drzewa prawego;

- drzewo AVL - drzewo BST, w którym dla każdego wierzchołka, wysokości dwóch jego poddrzew różnią się o co najwyżej jeden poziom

- kopiec - drzewo, w którym wartości przechowywane w potomkach każdego węzła są mniejsze od wartości w węźle; drzewo jest wypełniane od lewego poddrzewa; liście leżą co najwyżej na dwóch sąsiednich poziomach;

28. Przedstaw w języku C definicję typu danych dla drzewa binarnego i czwórkowego.

Deklaracja elementu drzewa binarnego:

struct Node{

int data; /* dane elementarne */

struct Node *llink; /* dowiązanie do lewego potomka */

struct Node *rlink; /* dowiązanie do prawego potomka */

}; typedef struci Node *NodePtr;

/* pomocniczy typ wskaźnikowy do struktury `Node' */

/* zmienna `start' tego typu wskazywać będzie korzeń */

Deklaracja elementu drzewa czwórkowego:

struct Node{

int data; /* dane elementarne */

struct Node *1-link; /* dowiązanie do pierwszego potomka */

struct Node *2-link; /* dowiązanie do drugiego potomka */

struct Node *3-link; /* dowiązanie do trzeciego potomka */

struct Node *4-link; /* dowiązanie do czwartego potomka */

}; typedef struci Node *NodePtr;

/* pomocniczy typ wskaźnikowy do struktury `Node' */

/* zmienna `start' tego typu wskazywać będzie korzeń */

29. Przedstaw w języku C implementację operacji wstawienia elementu do drzewa dwójkowego w porządku leksykograficznym.

/* funkcja dodaje element do drzewa wedlug relacji drzewa BST, pierwszym argumentem powinien być wskaźnik na korzeń drzewa natomiast drugi to wskaźnik na dodawany element; funkcja zwraca:

0 - jeżeli element zostanie pomyślnie dodany

1 - element o danym id już istnieje*/

int add_item (item *curr, item *tmp)

{

int code = 0;

if (head = NULL){

head = tmp;

code = 0;

return code;}

if ((tmp -> id > curr -> id) && (curr -> right != NULL))

code = add_item (curr -> right, tmp);

if ((tpm -> id < curr -> id) && (curr -> left != NULL))

code = add_item (curr -> left, tmp);

if (tmp -> id == curr -> id)

{ code = 1;

return code;}

if ((tmp -> id > curr -> id) && (curr -> right == NULL))

{ curr -> right = tmp;

update_avl_code(head);

return code;}

if ((tmp -> id < curr -> id) && (curr -> left == NULL))

{ curr -> left = tmp;

update_avl_code(head);

return code;}

return code;

}

30. Przedstaw w języku C implementację operacji usunięcia wskazanego elementu z drzewa binarnego.

int usun_z_drzewa (Tdrzewo* d, Telem e) {

if (*d != NULL) {

if ((**d).elem > e)

usun_z_drzewa(&(**d).lewy,e);

else {

if ((**d).elem < e)

usun_z_drzewa(&(**d).prawy,e);

else {

q = *d;

if ((*q).lewy == NULL)

*d = (*q).prawy;

else {

if ((*q).prawy == NULL)

*d = (*q).lewy;

else

usun(&(*q).lewy);

}

free(q);

return(1);

}

}

} else

return(0);

}

void usun(Tdrzewo* r) {
  if ((**r).prawy != NULL)
usun(&(**r).prawy);
  else {
(*q).elem = (**r).elem;
q = *r;
*r = (**r).lewy;
  }
}

31. Co to jest drzewo BST, AVL, czerwono-czarne, kopiec binarny?

Drzewo poszukiwań binarnych (BST):

Dla każdego węzła (nie liścia) wszystkie wartości przechowywane w lewym poddrzewie są mniejsze od jego wartości oraz przeciwnie dla drzewa prawego;

Drzewo AVL (1962 - Adelson-Velskii, Landis)

Drzewo BST jest drzewem AVL wtedy, kiedy dla każdego wierzchołka wysokości dwóch jego poddrzew różnią się o co najwyżej 1 poziom;

Drzewem czerwono-czarnym (DCC) nazywamy takie drzewo poszukiwań binarnych (przeznaczone do szybkiego wyszukiwania obszaru pamięci zawierającego podany adres), w którym:

- każdy węzeł jest czerwony lub czarny

- każdy liść (NULL) jest czarny

- każdy czerwony węzeł ma czarne dzieci

- każda prosta ścieżka z ustalonego węzła do liścia (w dół drzewa) ma tyle samo czarnych węzłów.

W DCC:

Wszystkie wskazania NULL traktujemy jako wskazania na zewnętrzne węzły drzewa - liście;

Zwyczajne węzły DCC (zawierające klucze) nazywamy wewnętrznymi węzłami drzewa

.

DCC musi w każdym węźle przechowywać informacje o kolorze (wystarczy 1 bit). W DCC definiujemy czarną głębokość liczbą czarnych węzłów na prostej ścieżce z danego węzła x do liścia (bez tego węzła).

Kopiec

Wartości przechowywane w potomkach każdego węzła są mniejsze od wartości węźle;

Drzewo jest szczelnie wypełniane od lewego poddrzewa;

Liście leżą na co najwyżej dwóch sąsiednich poziomach;

Zupełne drzewo binarne (dwójkowe):

Każdy węzeł, z wyjątkiem liści, ma dokładnie dwóch potomków;

32. Omów metodę lewostronnej pojedynczej rotacji drzew binarnych.

Lewa rotacja (lub „w lewo”):

Polega na obrocie wokół wyróżnionego węzła (x) przeciwnie do

ruchu wskazówek zegara;

W wyniku rotacji węzeł y staje się nowym korzeniem

poddrzewa, węzeł x zostaje jego lewym synem a lewy syn

węzła y zostaje prawym synem węzła x;

Można ją wykonać, jeżeli prawy syn węzła y nie jest NULL

33. Omów metodę lewostronnej podwójnej rotacji drzew binarnych.

podwójna lewa rotacja

procedure LR(var p: ptr);

var x, y: ptr;

begin

   x:=p^.left;   y:=x^.right;

   x^.right:=y^.left;   y^.left:=x;

   p^.left:=y^.right;   y^.right:=p;

   if y^.bl=1 then p^.bl:=-1 else p^.bl:=0;

   if y^.bl=-1 then x^.bl:=1 else x^.bl:=0;

   y^.bl:=0;   p:=y;

end;

rotacje LR wykonuje się wtedy, kiedy x należy do prawego poddrzewa lewego poddrzewa A. Niech left będzie lewym dzieckiem A, a grandchild -prawym dzieckiem left. W celu wykonania rotacji LR prawe dziecko left ustawiamy na lewe dziecko grandchild, lewe dziecko grandchild ustawiamy na left, lewe dziecko A na prawe dziecko grandchild, zas prawe dziecko grandchild na A i w koncu wskzanik wskazujacy A ustawiamy na grandchild.

34. Omów metodę prawostronnej pojedynczej rotacji drzew binarnych.

Procedura pojedynczej prawej rotacji może być zapisana następująco:

 

procedure RR(var p: ptr);

var x: ptr;

begin

   x:=p^.right;

   p^.right:=x^.left;

   x^.left:=p;

 if x^.bl=-1 then p^.bl:=0 else p^.bl:=-1;

 if x^.bl=0 then x^.bl:=1 else x^.bl:=0;

  p:=x;

end;

Rotacje RR realizuje sie wowczas, gdy x znajduje sie w prawym poddrzewie prawego poddrzewa A. Rotacja RR jest odbiciem symetrycznym rotacji LL. niech right będzie prawym dzieckiem A. Aby wykonac rotacje RR, ustawiamy prawy wskaznik A na lewe dziecko right, lewy wskaznik right na A, a wskaznik wskazujacy A na right. Po rotacji wspolczynniki zrownowazenia A i right ustawiamy na 0, pozostale wspolczynniki nie ulegaja zmianie.

35. Omów metodę prawostronnej podwójnej rotacji drzew binarnych.

Metoda podwójnej rotacji - dwukrotna rotacja…

36. Omów, przedstaw i porównaj metody sortowania przez wstawianie i przez wybieranie.

Sortowanie przez wstawianie ( insertion sort )

Sortowanie przez wstawianie odbywa się w następujący sposób: dla każdego i=2,3,…,n trzeba powtarzać wstawianie a[i] w już uporządkowaną część listy a[i]<=….<=a[i-1]

Liczba porównań wykonywanych w poniższym algorytmie insertionsort jest proporcjonalna do liczby inwersji na liście q, tzn. takich par, że a[i] > a[j] dla i<j.

procedure insertionsort;

{ a[0] = - ∞, aby uniknąć testu „j>1”}

var i, j, v :integer;

begin

for i:= 2 to n do

begin { a[0] <= a[1] <= …<= a[i-1]}

j : = i; v : = a[i];

while a[j-1] > v do

begin {a[0] <=…<= a[j-1] <= a[j+1] <= a[i],

j<i → v < a[j+1], a[j] — wolne miejsce}

a[j] : = a[j-1]; j : = j-1

end;

a[j] : = v

end

end insertionsort;

Sortowanie przez wybieranie ( selection sort)

Sortowanie przez selekcję odbywa się w następujący sposób: trzeba wyznaczyć najmniejszy element w ciągu; zamienić go miejscami z pierwszym elementem w ciągu, wyznaczyć najmniejszy element w a[2…n] i zamienić go z drugim elementem w ciągu itd., aż cała tablica zostanie posortowana.

Do głównych zalet przedstawionego poniżej algorytmu nakeżą:

a) optymalność, jeśli chodzi o liczbę przestawień {tylko n-1};

b) prostota implementacji;

c) zadowalająca szybkość dla małych wartości n;

Algorytm selectionsort nie jest stabilny.

procedure selectionsort;

var i,j,min : integer;

begin

for i : =1 to n-1 do

begin {a[1] <= …<= a[i-1] <= a[i….n]}

min : = i;

for j : = i+1 to n do

if a[j] < a[min] then min : = j;

a[min] < a[i]; {zamiana miejscami a[min] z a[i]}

end

end selectionsort;

37. Omów, przedstaw i porównaj metody sortowania przez zamianę i mieszanego.

Najlepiej znane sortowanie to sortowanie bąbelkowe. Jego popularność wynika z prostoty, ale jako metoda sortowania jest to jedna z najgorszych metod. Należy ono do kategorii sortowania przez zamianę. Wiąże się z wielokrotnym porównywaniem, a w razie konieczności przestawianiem sąsiednich elementów.

Załóżmy, że tablica, którą należy posortować to: DCAB. Kolejne przebiegi to:

Początek: DCAB

Przebieg1: ADCB

Przebieg2: ABDC

Przebieg3: ABCD

W sortowaniu bąbelkowym liczba porównań jest zawsze identyczna, ponieważ dwie pętle for wykonywane są określoną ilość razy niezależnie od tego, czy wejściowa lista jest już posortowana, czy nie. Oznacz to, że ma miejsce ½(n²-n) zamian, gdzie n oznacza liczbę elementów do posortowania. Dlatego algorytm sortowania bąbelkowego to algorytm kwadratowy.

W sortowaniu bąbelkowym w najlepszym wypadku, gdy lista jest już posortowana, liczba zamian wynosi zero. Jednak w najgorszym rośnie w postępie geometrycznym.

Sortowanie bąbelkowe ma jedną osobliwość: element znajdujący się na niewłaściwym miejscu na końcu tablicy, zarezerwowanym dla największych elementów (A w przykładzie DCAB) ląduje na odpowiednim miejscu w jednym przebiegu, ale element na niewłaściwej pozycji na początku tablicy (taki jak D), bardzo wolno przesuwa się na odpowiednie miejsce. To sugeruje pewne ulepszenie sortowania bąbelkowego. Zamiast odczytywać tablicę wciąż w tym samym kierunku, w kolejnych przebiegach można na przemian odwracać kierunek. Dlatego elementy leżące daleko od właściwej pozycji szybko wędrują na właściwe miejsce. Ta wersja sortownia nosi nazwę sortowania koktajlowego lub mieszanego, gdyż działa tak jakbyśmy potrząsali tablicą.

Wprawdzie sortowanie mieszane jest ulepszoną wersją bąbelkowego, jednak wciąż jest to algorytm kwadratowy, gdyż liczba porównań nie została zmieniona, a liczba zamian zredukowana tylko w niewielkim stopniu.

Sortowanie przez zamianę (bąbelkowe):

P_o = 0,5 (n² - n)

P_Rmin = 0

P_Rśr = 0,75 (n² - n)

P_Rmax = 1,5 (n² - n)

n - ilość elementów w tablicy,

P_o - liczba porównań klucza,

P_Ri - liczba przesunięć elementów w tablicy

Sortowanie mieszane

P_omin = n - 1 P_Rmin = 0

P_ośr = 0,5 (n² - n (k₂ + ln n)) P_Rśr = n - k₁ sqrt(n)

n - ilość elementów w tablicy,

k₁ - indeks poniżej którego tablica jest posortowana

k₂ - indeks powyżej którego tablica jest posortowana

P_o - liczba porównań klucza,

P_Ri - liczba przesunięć elementów w tablicy

38. Omów i przedstaw metodę sortowania „quick sort”.

Średni czas sortowania jest rzędu 0(nlog(n)) jakkolwiek mogą zdarzyć się sytuacje, że będzie on działał w czasie 0(n2). Istotą metody jest podział zbioru na dwie części. Wybieramy jeden element z tego zbioru i tworzymy dwa podzbiory składające się z elementów mniejszych i nie mniejszych od wybranego elementu. Proces podziału powtarza się dla obydwu podzbiorów. Pierwotny zbiór zostaje posortowany jeżeli wszystkie podzbiory zostaną podzielone. Oparty więc jest na strategii dziel i zwyciężaj. Kluczem właściwego działania algorytmu jest poprawnie zbudowana funkcja podziału (partition), realizująca przekształcanie tablicy X[l..p] wedługt schematu (przy założeniu, że v=X[k]:

• X[l], X[l-1],...X[k-1]v

• vX[k+1], X[[l-1],...X[p]v

• v umieszczony jest na końcu właściwego podzbioru (lewego)

Technika rekurencyjna:

Nie absorbuje w istotny sposób zasobów komputera, gdyż nie jest tworzona kopia tablicy X. W procesie rekurencyjnym przekazywane są jedynie indeksy wyznaczające segmenty tablicy, których elementy mają ulec przestawieniu w danym kroku. Dodatkowe zapotrzebowanie na pamięć dotyczy wyłącznie stosu indeksów granicznych, opisujących nie podzielone jeszcze podzbiory. Głębokość stosu nie przekroczy wartości log2(n). Efektywność algorytmu można dodatkowo zwiększyć trzymając indeksy i, j oraz zmienną v w szybkich rejestrach komputera. Algorytm QUICKSORT nie jest zbyt efektywny dla małych n.

Jeżeli wartość wybierana(podziału) jest największa wówczas przy każdym podziale lewy podzbiór zawiera n-1 elementów zaś prawy tylko jeden. Jest to więc najgorszy przypadek działania algorytmu, gdyż trzeba dokonać n takich podziałów.

Można dowieść, że przy podziale zbioru w proporcjach 9:1 złożoność algorytmu będzie 0(nlog(n)). Jeżeli jako v=X[1] to najgorszym przypadkiem dla algorytmu jest tablica uporządkowana. Efektywność metody uzależniona jest od wyboru elementu osiowego v i początkowej struktury zbioru.

39. Przedstaw i omów definicję liniowej struktury danych.

Liniową strukturą danych nazywamy strukturę danych S=(D, R, e), w której relacja porządkująca N opisuje powiązania pomiędzy elementami odpowiednio dla poszczególnych rodzajów list.

Wyróżniamy cztery rodzaje list (jednopoziomowych):

• jednokierunkowe listy niecykliczne

• dwukierunkowe listy niecykliczne

• jednokierunkowe listy cykliczne (pierścienie jednokierunkowe)

• dwukierunkowe listy cykliczne (pierścienie dwukierunkowe)

Definicja listy stanowi podstawę dla zdefiniowania struktury liniowej. Wszystkie przypadki struktur liniowych można zdefiniować bazując na ich odpowiednich reprezentacjach listowych

Inne liniowe struktury danych:

• kolejki,

• stosy,

• napisy,

• tablice sekwencyjne,

• tablice rzadkie,

• tablice rozproszone (z haszowaniem).

40. Wymień i krótko scharakteryzuj przykłady liniowych struktur danych.

Liniową strukturą danych nazywamy strukturę danych S=(D, R, e), w

której relacja porządkująca N opisuje powiązania pomiędzy parami

elementów odpowiednio dla poszczególnych rodzajów list.

Wyróżniamy cztery rodzaje list (jednopoziomowych):

•jednokierunkowe listy niecykliczne

•dwukierunkowe listy niecykliczne

•jednokierunkowe listy cykliczne (pierścienie jednokierunkowe

•dwukierunkowe listy cykliczne (pierścienie dwukierunkowe

Element listy zawiera:

Dane elementarne,

Odwzorowanie relacji następstwa - informacja o dowiązaniu

do innych elementów;

41. Zaproponuj implementację w języku C deklaracji typów i zmiennych dla niecyklicznej listy jednokierunkowej, a także operacji dołączania, wyszukiwania i usuwania elementu z tej listy.

typedef struct miasta{

int numer;

miasta * nast;

miasta * dokad;

};

miasta * find_city(miasta * wsk, int city)

{

while (wsk != NULL)

{

if (wsk->numer == city)

return wsk;

wsk=wsk->nast;

}

return NULL;

}

void add_city(miasta ** wsk, int numer)

{

miasta ** prev, ** wsk2;

miasta * tmp=(miasta *)malloc(sizeof(miasta));

tmp->numer=numer;

tmp->dokad=NULL;

tmp->nast=NULL;

wsk2=&;(*wsk);

while ((*wsk2 != NULL) && ((*wsk2)->numer < numer))

{

prev=wsk2;

wsk2=&;(*wsk2)->nast;

}

if (*wsk2==NULL)

{

*wsk2=tmp;

tmp->nast=NULL;

}

else

{

(*prev)->nast=tmp;

tmp->nast=*wsk2;

}

}

void del_city(miasta ** wsk, int numer)

{

miasta ** prev, ** wsk2;

wsk2=&;(*wsk);

while ((*wsk2 != NULL) && ((*wsk2)->numer != numer))

{

prev=wsk2;

wsk2=&;(*wsk2)->nast;

}

if (*wsk2==*wsk)

{

&;(*wsk)=NULL

}

else

{

(*prev)->nast=&;(*wsk2)->nast;

free(&;(*wsk2));

}

}

42. Zaproponuj implementację w języku C deklaracji typów i zmiennych dla niecyklicznej listy dwukierunkowej, a także operacji dołączania, wyszukiwania i usuwania elementu z tej listy.

typedef struct miasta{

int numer;

miasta * nast;

miasta * dokad;

miasta * poprzedni;

};

miasta * find_city(miasta * wsk, int city)

{

while (wsk != NULL)

{

if (wsk->numer == city)

return wsk;

wsk=wsk->nast;

}

return NULL;

}

void add_city(miasta ** wsk, int numer)

{

miasta ** prev=NULL, ** wsk2;

miasta * tmp=(miasta *)malloc(sizeof(miasta));

tmp->numer=numer;

tmp->dokad=NULL;

tmp->nast=NULL;

tmp->poprzedni=NULL;

wsk2=&;(*wsk);

while ((*wsk2 != NULL) && ((*wsk2)->numer < numer))

{

prev=wsk2;

wsk2=&;(*wsk2)->nast;

}

if (*wsk2==NULL)

{

*wsk2=tmp;

if (*prev != NULL)

wsk2->poprzedni=*prev;

}

else

{

(*prev)->nast=tmp;

tmp->nast=*wsk2;

tmp->poprzedni=*prev;

(*wsk2)->poprzedni=tmp;

}

}

void del_city(miasta ** wsk, int numer)

{

miasta ** prev, ** wsk2;

wsk2=&;(*wsk);

while ((*wsk2 != NULL) && ((*wsk2)->numer != numer))

{

prev=wsk2;

wsk2=&;(*wsk2)->nast;

}

if (*wsk2==NULL)

{

free(*wsk2);

*wsk2=NULL;

if (*prev != NULL)

{

(*prev)->nast=NULL;

}

}

else

{

(*prev)->nast=&;(*wsk2)->nast;

(*prev)->nast->poprzedni=*prev;

free(*wsk2);

}

}

43. Zaproponuj implementację w języku C deklaracji typów i zmiennych dla cyklicznej listy jednokierunkowej, a także operacji dołączania, wyszukiwania i usuwania elementu z tej listy.

Typedef struct Lista // deklaracja struktury

{

char data; // typ przechowywanych danych

struct Lista *next; // wskaźnik do następnego elementu listy

}W_Lista; // wskaźnik na początek listy

Dodatkowo:

a) operacja wstawiania :

char value // zmienna przechowująca dane które mają być wstawione do elementu

struct lista *nowy // deklaracja nowego elementu dodawanego do listy

b) operacja usunięcia i wyszukania

aktualny *W_lista

//wskaźnik do elementu listy, który w danym momencie jest sprawdzany czy nie jest elementem do usunięcia / wyszukania

char value // zmienna przechowująca dane, które znajdują się w elemencie do usunięcia / wyszukania

44. Zaproponuj implementację w języku C deklaracji typów i zmiennych dla cyklicznej listy dwukierunkowej, a także operacji dołączania, wyszukiwania i usuwania elementu z tej listy.

Typedef struct Lista // deklaracja struktury

{

char data; // typ przechowywanych danych

struct Lista *prev; // wskaźnik do poprzedniego elementu listy

struct Lista *next; // wskaźnik do następnego elementu listy

}W_Lista; // wskaźnik na początek listy

Dodatkowo:

a) operacja wstawiania :

char value // zmienna przechowująca dane które mają być wstawione do elementu

Lista prev, curr, new //deklaracja nowego elementu dodawanego do listy oraz zmiennych w których przechowywane będą poprzedni i bieżący element listy

b) operacja usunięcia i wyszukania

Lista prev, curr // deklaracja zmiennych w których przechowywane będą kolejno występujące elementy listy (używane w celu znalezienia elementu wyszukiwanego oraz przy usuwaniu elementu

Lista temp // przy operacji usuwania zostanie do tej zmiennej przypisany element listy, który później zostanie usunięty

char value // zmienna przechowująca dane, które znajdują się w elemencie do usunięcia / wyszukania

45. Przedstaw koncepcję, sposoby realizacji i przykład zastosowania tablic rzadkich w algorytmach wyszukiwania połączeń komunikacyjnych.

Struktury takie jak tablice, listy, drzewa dobrze nadają się do reprezentowania grafów. Dwie reprezentacje można jednak uznać za dominujące: za pomocą tablicy dwuwymiarowej i tzw. slownika węzlów.

Graf może być reprezentowany przy użyciu tablicy dwuwymiarowej, jeśli umówimy się, że wiersze będą oznaczaly węzly początkowe krawędzi grafu, a kolumny ich węzly końcowe.

	A	B	C	D	E	F
A	0	1	0	0	0	0
B	0	0	1	1	0	0
C	0	0	1	0	1	0
D	0	0	0	0	1	1
E	0	0	0	0	0	1
F	0	0	0	0	0	0

Jedynka na pozycji (x,y) oznacza, że pomiędzy węzlami x i y istnieje krawędź skierowana w stronę y. W każdym innym przypadku tablica będzie zawierala zero. Reprezentacja tablicowa jest bardzo prosta w implementacji tablicowej w dowolnym języku programowania. Wada: jedynie grafy o ustalonej z góry liczbie węzlów mogą być reprezentowane w formie tablic.

Przykład zastosowania tablicy: algorytm Roy - Warshalla. Chrakteryzuje się kilkoma cechami: nie używa on żadnych grafów dodatkowych, a ponadto pozwala dość latwo odtworzyć drogę, którą należy pójść, aby przejść po krawędziach od jednego wierzcholka do drugiego.

46. Zapisz i omów definicję tablicy rozproszonej.

Tablice rozproszone, zwane tablicami asocjacyjnymi służą do przechowywania listy skalarów. Tablica rozproszona stanowi zbiór par skalarów klucz=>wartość. Dostęp do elementu takiej tablicy następuje poprzez klucz. Dane nie są tu w żaden sposób uporządkowane, ich kolejność jest przypadkowa i w przeciwieństwie do tablic zwykłych nie ma żadnego znaczenia.

Do oznaczania zmiennych tablic rozproszonych używamy znaku %. Aby utworzyć tablicę wystarczy wypisać wszystkie jej elementy w kolejności klucz1, wartość1, klucz2, wartość2,... i przypisać je do zmiennej:

%wiek = ('Ola', 15, 'Kasia', 13, 'Jaś', 10);

to samo można przedstawić w bardziej czytelnej postaci:

%wiek = ('Ola'=>15, 'Kasia'=>13, 'Jaś'=>10);

gdzie 'Ola', 'Kasia' i 'Jaś' są kluczami, zaś 15, 13, 10 - wartościami (latami poszczególnych osób). Ponieważ klucz musi być łańcuchem, cudzysłowy można pominąć.

Przypisując tablicę rozproszoną do tablicy zwykłej otrzymamy tablicę składającą się z elementów będących kluczami i wartościami. Jeśli zaś do tablicy rozproszonej przypiszemy tablicę zwykłą, jej elementy zostaną rozłożone na pary klucz=>wartość i w takiej postaci trafią do tablicy

47. Czym jest funkcja haszująca i konflikt w tablicach rozproszonych?

Funkcja haszująca h - funkcja, która ma za zadanie w miarę równomierne obciążyć tablicę rozproszoną. Zagadnienie definiowania funkcji mieszającej jest istotne dla efektywności obliczeń realizowanych na bazie tablic rozproszonych. Ma to duże znaczenie dla tablic rozproszonych przetwarzanych bezpośrednio w nośnikach zewnętrznych.

Nie można jednak wykluczyć powstawania tzw. konfliktów w tablicach rozproszonych.

Kolizją (konfliktem) w tablicy rozproszonej nazywamy sytuację powstałą wtedy, gdy:

Elementy ki, kj biorące udział w kolizji nazywamy synonimami.

48. Przedstaw koncepcję i przykład haszowania w tablicach rozproszonych metodą kwadratu środka.

Podczas tworzenia baz danych często pojawia się problemem takiego umieszczania rekordów w pliku, aby dostęp do nich był jak najszybszy. Umożliwiają to tablice rozproszone.

Zagadnienie można przedstawić następująco. Mamy tablicę n-elementową o indeksach od 0 do n-1. Z każdego rekordu, jaki chcemy do niej wstawić, należy wyznaczyć pewien klucz (jakaś liczba), na podstawie którego oblicza się indeks w tablicy (nazywany funkcją mieszającą), gdzie wstawimy rekord. Wystarczy tylko znać klucz danego elementu, by mieć do niego natychmiastowy dostęp. metody kwadratu środka (z klucza wydziela się jego pewną część, traktuje ją jako liczbę binarną i podnosi do kwadratu

Metoda kwadratu środka:

K O W A L S K I - klucz

21 25 33 11 22 29 21 19 - kody znaków

3 11 22 2 - wycięty środek

6 8 5 9 1 3 3 2 8 4 - kwadrat wyciętej liczby

9 1 3 - wyliczony adres d

49. Przedstaw koncepcję i przykład haszowania w tablicach rozproszonych metodą składania.

Metoda składania:

Kod:

K     O    W    A     L      S     K      I          -  klucz 21   25    33   11   22    29    21   19 -  kody znaków               29   21   19 21   25    33   11   22    29   21   19            -  sposób składania               21   25   00

d = 212500 + 331122 + 292119 = 834741 - wyliczony adres

50. Przedstaw koncepcję i przykład haszowania w tablicach rozproszonych metodą dzielenia.

Metoda dzielenia:
adres wyliczany według formuły:
d = wart(k) mod p, gdzie:
d - adres w tablicy rozproszonej (czasami: indeks)
wart(k) - wartość wyliczona na podstawie klucza - inną metodą, np. metodą składania lub kwadratu środka
p - liczba pozycji w tablicy

w zastosowaniach praktycznych metoda ta jest bardzo efektywna.

Przykład zastosowania metody dzielenia:
- tablica ma 1000 pozycji
- zakończenie przykładu przedstawionego dla metody kwadratu środka:
d1 = 913 mod 1000 = 913
- zakończenie przykładu przedstawionego dla metody składania:
d2 = 834741 mod 1000 = 741

51. Omów metody usuwania konfliktów w tablicach rozproszonych bez obszarów nadmiarowych.

Definicja tablicy rozproszonej (z haszowaniem)

Tablicą rozproszoną nazywamy trójkę uporządkowaną

T = K,D, h , gdzie

K = {k1, k2, k3,..., kn} - zbiór kluczy,

D = {d1, d2, d3,..., dn} - zbiór adresów,

h - funkcja mieszająca (haszująca) zdefiniowana następująco :h :K → D

Tradycyjnym obszarem zastosowań tablic rozproszonych są zagadnienia związane z przetwarzaniem danych.

Zadaniem funkcji haszującej h jest w miarę równomierne obciążanie tablicy rozproszonej.Zagadnienie definiowania funkcji mieszającej jest istotne dla efektywności obliczeń realizowanych na bazie tablic rozproszonych. Ma to szczególnie duże znaczenie dla tablic rozproszonych przetwarzanych bezpośrednio w nośnikach zewnętrznych taśmach, dyskach) Nie można jednak wykluczyć powstawania tzw.konfliktów w tablicach rozproszonych. Kolizją (konfliktem) w tablicy rozproszonej nazywamy sytuację powstałą wtedy, gdy istnieją takie dwa elementy Ki oraz Kj, że Ki różne od Kj ale h(Ki)=h(Kj)

Elementy ki, kj biorące udział w kolizji nazywamy synonimami.

Usuwanie konfliktów w tablicach rozproszonych

Bez obszarów nadmiarowych - szukanie liniowe

di = (d0 + a * i) mod p, gdzie

d0 = h(k) - wynik początkowego haszowania klucza

di - nowy adres, wyliczany wtedy, gdy w (i-1)-szym kroku wystąpił konflikt

a - stały współczynnik empiryczny

i - numer kolejnego kroku szukania (0 <= i <= p)

p - liczba pozycji w tablicy

Bez obszarów nadmiarowych - szukanie kwadratowe

di = (d0 + a * i + b * i2) mod p,

lub wzór uproszczony:

di = (d0 + i2), gdzie

d0 = h(k) - wynik początkowego haszowania klucza

di - nowy adres, wyliczany wtedy, gdy w (i-1)-szym kroku wystąpił konflikt

a, b - stałe współczynniki empiryczny

i - numer kolejnego kroku szukania (0 <= i <= p)

p - liczba pozycji w tablicy

Bez obszarów nadmiarowych - szukanie sześcienne

di = (d0 + i3), gdzie

d0 = h(k) - wynik początkowego haszowania klucza

di - nowy adres, wyliczany wtedy, gdy w (i-1)-szym kroku

wystąpił konflikt

i - numer kolejnego kroku szukania (0 <= i <= p)

p - liczba pozycji w tablicy

Funkcje haszujące wprowadza się, aby zmniejszyć wielkość pamięci potrzebnej do zapamiętania określonych danych. Cena, jaką płacimy za często ogromne oszczędności pamięci to możliwość kolizji, tj. sytuacji, w której funkcja haszująca przypisuje dwu różnym kluczom tą samą pozycję w tablicy. Istnieją jednak efektywne metody rozwiązywania konfliktów wywoływanych przez kolizje. Oczywiście najlepiej byłoby w ogóle unikać kolizji - zasadniczy jest tutaj dobór odpowiedniej funkcji haszującej, takiej która wydaje się być losowa. Najprostszą metodą rozwiązywania kolizji w tablicach rozproszonych jest metoda łańcuchowa. W tej metodzie wszystkie elementy, którym odpowiada ta sama pozycja w tablicy, zostają umieszczone na jednej liście. Na j-tej pozycji w tablicy jest pamiętany wskaźnik do początku listy tych wszystkich elementów, dla których funkcja h daje wartość j. Jeśli w zbiorze nie ma takich elementów to pozycja j ma wartość NULL.

52. Omów metody usuwania konfliktów w tablicach rozproszonych z obszarami nadmiarowymi.

Co to są konflikty w tablicach rozproszonych?

Kolizją (konfliktem) w tablicy rozproszonej nazywamy sytuację powstałą wtedy, gdy:

Istnieje (h( ki )) = h(kj))

ki, kj є K , ki != kj

elementy ki,kj biorące udział w kolizji nazywamy synonimami.

Usuwanie konfliktów w tablicach rozproszonych ( z wykorzystaniem obszarów nadmiarowych )

- listy synonimów: pierwsze wstawienie do wolnego miejsca w obszarze bazowym. Kiedy wyliczona w haszowaniu pozycja z obszaru bazowego jest zajęta , to wstawiamy nowy element do listy synonimów podwieszonej pod tą pozycję w obszarze bazowym. Listy synonimów tworzą obszary nadmiarowe

- rozproszona tablica indeksowa: wszystkie dane są wstawiane do obszaru nadmiarowego

Obszary nadmiarowe są organizowane w postaci zestawu posortowanych wykazów liniowych lub posortowanych i zrównoważonych wykazów leksykograficznych

53. Przedstaw przykład sortowania plików metodą łączenia prostego.

Metoda łączenia prostego polega na sukcesywnym dzieleniu danych w pliku na podciągi o ustalonej długości maksymalnej i łączeniu tych podciągów wraz z równoczesnych porządkowaniem zawartych w nich elementów w uporządkowane podciągi danych. Porządek ten może być dowolny, np. rosnący lub malejący.

Łączenie przebiega według następującego schematu:

1. Dzielimy ciąg A na polowy B i C.

2. Łączymy ciągi B i C, składając pojedyncze ich elementy w pary uporządkowane.

3. Nazywamy połączony ciąg A i powtarzamy kroki 1 i 2, łącząc tym razem pary w czwórki.

4. Powtarzamy poprzednie kroki, łącząc czwórki w ósemki, i tak dalej, dopóki cały ciąg nie zostanie uporządkowany.

Np.: mamy ciąg:

44 55 12 42 94 18 06 67

Krok 1:

44 55 12 42

94 18 06 67

Krok2:

44 94 ` 18 55 ` 06 12 ` 42 67

Krok3:

06 12 44 94 ` 18 42 55 67

Krok4:

06 12 18 42 44 55 67 94

54. Przedstaw przykład sortowania plików metodą łączenia naturalnego.

(I) Dopóki nie połączysz elementów z wszystkich serii w jedną serię, wykonuj:

(1) Ustaw plik wejściowy oraz dwa pliki robocze

(2) Podziel plik źródłowy na serie o wartościach niemalejących i rozłóż je równomiernie na dwóch plikach roboczych;

(3) Dopóki nie wyczerpiesz serii ze wszystkich plików roboczych, wykonuj:

(A) Weź po jednej serii o tym samym numerze z każdego niewyczerpanego pliku roboczego;

(B) Połącz te serie w sposób niemalejący i umieść w pliku wyjściowym w postaci jednej serii;

(C)Wyznacz kolejne serie o tych samych numerach, po jednej z każdego niewyczerpanego pliku roboczego

55. Przedstaw przykład sortowania plików metodą polifazową.

//prosta procedura pokazujaca zawartosc pliku

void show_file (void);

char *filename="plik.txt";

int main(void) {

//deklaracje zmiennych

FILE *file;

FILE *tmp1;

FILE *tmp2;

FILE *pointer;

int prev_number,curr_number,byte=0;

int num1, num2, byte1, byte2 ;

bool need_sort;

show_file();

do {

//otwarcie pliku ktory bedzie sortowany

//plik ma postac liczb oddzielonych pojedynczymi spacjami oraz nie moze zawierac licz ujemnych

file=fopen(filename, "rt");

//deklaracja reszty plikow tymczasowych

tmp1=fopen("temp_file.1", "wt");

tmp2=fopen("temp_file.2", "wt");

pointer=tmp1;

//ustawienie zmniennej ktora decyduje o powtornym wykonaniu algorymtu sortowania

need_sort=false;

curr_number=prev_number=0;

//przepisywanie z pliku wejsciowego kolejnych liczb ktore sa juz w relacji

//w tym przypadku jest to relacja niemalenia

do {

byte=fscanf(file, "%d ", &curr_number);

if (byte > 0) {

//jezeli poprzednia cyfra i aktualna nie spelniaja relacji to zmienia sie

//wskaznik do ktorego przepisywany sa pozostale cyfry

if (prev_number > curr_number) {

pointer=tmp2;

need_sort=true;

}

fprintf(pointer, "%d ", curr_number);

prev_number=curr_number;

}

} while (byte>0);

//zamykamy wszystkie pliki i zaczyna sie drugi etap algorytmu

fclose(tmp1);

fclose(tmp2);

fclose(file);

//ponowne otwarcie plikow

tmp1=fopen("temp_file.1", "rt");

tmp2=fopen("temp_file.2", "rt");

file=fopen(filename, "wt");

//przeczytanie pierwszych liczb z plikow tymczasowych

byte1=fscanf(tmp1, "%d ", &num1);

byte2=fscanf(tmp2, "%d ", &num2);

do { if ( (byte1 > 0) && (byte2 > 0) ) {

//jezeli oba pliki zawieraja jeszcze liczby to

if ( num1 < num2) {

//zostaje sprawdzona relacja i odpowiednio przepisana liczba oraz pobrana kolejna

fprintf(file, "%d ", num1);

byte1=fscanf(tmp1, "%d ", &num1);

} else {

fprintf(file, "%d ", num2);

byte2=fscanf(tmp2, "%d ", &num2);

}

//jezeli skoncza sie liczby w ktoryms z plikow to do pliku wyjsciowego sa pozostale

} else if (byte1 <= 0) {

while (byte2 > 0 ) {

fprintf(file, "%d ", num2);

byte2=fscanf(tmp2, "%d ", &num2);

}

} else if (byte2 <= 0) {

while (byte1 > 0 ) {

fprintf(file, "%d ", num1);

byte1=fscanf(tmp1, "%d ", &num1);

}

}

} while ( (byte1>0) || (byte2>0) );

fclose(tmp1);

fclose(tmp2);

fclose(file);

//jezeli trzeba sortowac dalej, tzn gdzies jeszcze nie zostala zachowana relacja to calosc jest powtarzana

} while (need_sort);

show_file();

return 0;

//end

}

void show_file (void) {

FILE *file;

int byte,number;

file=fopen(filename, "r");

do {

byte=fscanf(file, "%d ", &number);

if (byte>0) {

printf("%d ", number);

}

} while (byte>0);

printf("\n");

fclose(file);

return;

}

6

---