Januar 2007

1.

L=91 bit

ASCII 7-bitni = 7*24=168

8-bitni 8*24=192

2.

Pretpostavimo da je stablo građeno tako da je informaciono polje (ključ) desnog sina veće ili jednako od informacionog polja (ključa) oca.

Sledbenik zadatog čvora je čvor sa najmanjim ključem koji je veći od ključa datog čvora.

Koji čvor nema sledbenika? Samo najdešnji čvor u stablu (koji nema desnog sina i koji je desni sin svog oca), jer je on čvor sa maksimalnom vrednošću ključa. (1. situacija)

Karakteristični slučajevi za čvor v čije informaciono polje (ključ) ima vrednost elementa a iz skupa S su:

2. v ima desno podstablo => Sledbenik se traži kao ključ desnog sina, odnosno kao ključ najlevljeg čvora u desnom podstablu

3. v nema desnog sina => Sledbenik se traži tako što se traži ključ najnižeg pretka w takvog da levi sin od w je predak čvora v.

Ova operacija se najefikasnije izvodi ako se za svaki čvor čuva i polje otac sa pokazivačem na oca čvora. Tako se ide od čvora v prema korenu sve dok se ne nađe čvor w koji je levi sin svog oca. U slučaju da nema takvog pretka w, onda je a najveći element skupa i nema svog sledbenika.

U svakoj situaciji, sledbenik se nalazi bez poređenja ključeva zahvaljujući principu uređenosti stabla.

Sledi algoritam za nalaženje sledbenika za zadatu vrednost ključa čvora ukazanog sa v koji vraća adresu sledbenika ili NULL. Koristi se i poziv algoritma BST_MIN koji u BST (stablu binarnog pretraživanja) traži ključ sa minimalnom vrednošću.

Algoritam BST_MIN za BST čiji je koren ukazan argumentom node ide po lancu levih pokazivača sve dok ne dođe do čvora koji nema levog sina. .

int BST_MIN (Stablo koren) /* Najmanji u uredjenom stablu. */
 { return koren->levo ? BST_MIN (koren->levo ) : koren->broj; }

Algoritam BST_MIN pokriva 1. situaciju kada je potrebno pronači ključ sa minimalnom vrednošću u desnom podstablu čvora v.

Algoritam BST_SLEDBENIK (v)
ulaz: v
izlaz: q /* bilo da je NULL ili nije */
{
 pom=v
 if (right(pom) != NULL) return BST_MIN(right(pom)) /*2. situacija*/
 else /* 1. i 3. situacija*/
 {
 q=otac(pom)
 while (q != NULL ) and (pom == right(q)) do
 {
 pom=q
 q=otac(pom)
 }
 return q
 }
}

Napomena: x=right(y) <= > x=y- > right . . .

Operacije nalaženja minimalnog ključa, sledbenika imaju vreme izvršavanja srazmerno visini stabla h, tj. O(h), jer u svakoj od situacija prate putanju kroz stablo samo u jednom smeru.

3.

#include <stdio.h>

#define MAX 10 /*maksimalan broj cvorova*/

void topSortPoseti(int x, int a[][MAX], int n, int m[], int lista[], int *k);

/*obilazak grafa sa n cvorova zadatog matricom a pocev od neposecenog cvora x;

pri obilasku u nizu markiranih cvorova m vrednost clana m[x] ce postati 1,

kad se poseti cvor x.

Kada se za cvor x zavrsi poseta svih nemarkiranih susednih cvorova,

cvor x se dodaje na pocetak liste l na poziciji *k */

void topsort(int a[][MAX], int n, int lista[]);

/*DFS obilazak grafa G sa n cvorova zadatog matricom povezanosti a

i formiranje topoloskog

redosleda cvorova u nizu lista*/

void ucitaj_matricu(int a[][MAX], int n); //ucitavanje grana grafa sa stdin

void trampa(int a[], int i, int j); //trampa clana a[i], a[j]

void test(int a[][MAX], int l[], int n);

main()

{int a[MAX][MAX];

int n; //broj cvorova grafa

int lista[MAX];

scanf("%d", &n);

ucitaj_matricu(a,n);

topsort(a, n, lista);

test(a,lista,n);

}

void topSortPoseti(int x, int a[][MAX], int n, int m[], int lista[], int *k)

{

int y; //cvor koji je u grafu potencijalni sused cvora x

m[x]=1; //markira se cvor x kao posecen

//ako postoji susedni cvor y koji nije markiran(m[y]=0),

//rekurzivno se poziva topSortPoseti za y

for (y=0; y<n; y++)

if( m[y]==0 && a[x][y]==1) topSortPoseti(y, a, n, m, lista, k);

lista[*k]=x; //ubacuje se cvor u topoloski uredjenu listu na kraj

*k++; //priprema za prihvat sledeceg clana liste

}

void topsort(int a[][MAX], int n, int lista[])

{

int x, m[MAX],k; //cvor grafa x, niz markiranih (posecenih) cvorova m,

//k je index clanova topoloski uredjene liste cvorova

k=0;

for (x=0; x<n; x++) m[x]=0; //na pocetku su svi cvorovi neposeceni

for (x=0; x<n; x++)

if (m[x]==0) topSortPoseti(x, a, n, m, lista, &k);

//ako x nije posecen, pokrenuti topSortPoseti iz x

//kako smo cvorove dodavali u f-ji topSortPoseti na kraj lista,

//a ne na pocetak niza lista, mora se niz lista obrnuti

for(x=0; x<n/2; x++) trampa(lista, x, n-x-1); //trampe se prvi i poslednji, drugi i pretposlednji,...

}

void ucitaj_matricu(int a[][MAX], int n)

{

int i, j;

for (i=0; i< n; i++)

for(j=0; j<n; j++) a[i][j]=0;

while (scanf("(%d,%d)", &i, &j) != EOF) a[i][j]=1;

}

void trampa(int a[], int i, int j)

{

int pom=a[i]; a[i]=a[j]; a[j]=pom;

}

void test(int a[][MAX], int l[], int n)

{

int i;

for(i=0;i<n;i++)

if (a[l[i]], a[l[i+1]] ==0)

{

printf("\nNe postoji prost put koji sadrzi sve cvorove \n");

return;

}

printf("\nPostoji prost put koji sadrzi sve cvorove i to:\n");

for(i=0;i<n-1;i++)

printf("%d->",l[i]);

printf("%d\n",l[n-1]);

}

SLOZENOST:

1. Slozenost topoloskog sortiranja je O(|V| + |E|)

2. Slozenost potprograma test je O(|V|)

   Zato je ukupna slozenost suma navedenih slozenosti, tj. O(|V| + |E| )

4. Videti poglavlje 11.4. u knjizi