Zadanie z laboratorium programowania na Informatyce UW.
Zadanie 16 (termin wysylania rozwiazan: 2 czerwca 2008, godz. 23:59) (Graf) Tekstowym zapisem grafu skierowanego, majacego n wierzcholkow etykietowanych liczbami calkowitymi od 1 do n, bedzie ciag n wierszy wskazujacych sasiadow kazdego z wierzcholkow. W i-tym wierszu znajda sie, rozdzielone spacjami i uporzadkowane rosnco, numery wierzcholkow, do ktorych prowadza krawedzie z wierzcholka i. k-tym poziomem w grafie g wzgledem wierzcholka w nazwiemy zbior wierzcholkow grafu g, ktorych odleglosc od w, mierzona liczba wierzcholkow na najkrotszej sciezce, wynosi k. Napisz program, ktory wczyta z wejscia tekstowy zapis grafu skierowanego o niepustym zbiorze wierzcholkow i wypisze na wyjscie kolejno, od pierwszego, wszystkie niepuste poziomy liczone wzgledem wierzcholka 1. Dla kazdego poziomu program powinien wypisac, uporzadkowane rosnaco i rozdzielone pojedynczymi odstepami, numery wierzcholkow znajdujacych sie na tym poziomie. Np. dla danych: 3 4 1 4 5 2 2 4 5 program powinien wypisac: 1 3 4 2 5
A oto rozwiązanie:
#include
#include
#include
//Ten kod jest bardzo, bardzo brzydki. Opieram się na algorytmie przeszukiwania wszerz.
//Struktura dla kolejki przeszukiwania.
typedef struct kolejka_el{
int wezel;
struct kolejka_el * nastepny;
int poziom;
};
//Struktura dla wezłów grafu
struct wezel_el{
int liczba;
struct wezel_el * nastepny;
struct krawedz_el* krawedzie;
int odwiedzony;
struct krawedz_el* wypisanie;
};
//Struktura dla krawędzi grafu
struct krawedz_el {
int cel;
struct krawedz_el* nastepny;
};
int main (int argc, char *argv[])
{
//Inicjujemy
int numer_wezla,liczba,wynik,i;
char znak;
struct wezel_el *teraz_wezel=NULL;
struct wezel_el *tmp_wezel=NULL;
struct wezel_el *start_wezel=NULL;
struct krawedz_el *teraz_krawedz=NULL;
struct krawedz_el *tmp_krawedz=NULL;
struct kolejka_el *start_kolejka=NULL;
struct kolejka_el *teraz_kolejka=NULL;
struct kolejka_el *koniec_kolejka=NULL;
struct kolejka_el *tmp_kolejka=NULL;
numer_wezla=1;
wynik=scanf("%d",&liczba);
//Wczytujemy
if(wynik!=EOF)//jesli nie bylo znakow w pierwszym wierszu.
{
//pierwszy element ciagu znakow
start_wezel=malloc(sizeof(struct wezel_el));
start_wezel->nastepny=NULL;
start_wezel->krawedzie=malloc(sizeof(struct krawedz_el));
start_wezel->wypisanie=NULL;
start_wezel->krawedzie->nastepny=NULL;
start_wezel->krawedzie->cel=liczba;
start_wezel->liczba=numer_wezla;
start_wezel->odwiedzony=0;
wynik=scanf("%c",&znak);
teraz_wezel=start_wezel;
teraz_krawedz=teraz_wezel->krawedzie;
while(wynik!=EOF)
{
if(znak==' ')
{
//Wczytalismy spacje. Zaraz bedzie nowa krawedz.
teraz_krawedz->nastepny=malloc(sizeof(struct krawedz_el));
teraz_krawedz=teraz_krawedz->nastepny;
teraz_krawedz->nastepny=NULL;
teraz_krawedz->cel=0;
}
else if((znak>='0')&&(znakcel=teraz_krawedz->cel*10 + (znak-'0');
}
else if(znak=='n')
{
//Wczytalismy nowy wiersz. Budujemy nowy wezel.
numer_wezla++;
teraz_wezel->nastepny=malloc(sizeof(struct wezel_el));
teraz_wezel->wypisanie=NULL;
teraz_wezel=teraz_wezel->nastepny;
start_wezel->odwiedzony=0;
teraz_wezel->nastepny=NULL;
teraz_wezel->liczba=numer_wezla;
teraz_wezel->krawedzie=malloc(sizeof(struct krawedz_el));
teraz_krawedz=teraz_wezel->krawedzie;
teraz_krawedz->cel=0;
teraz_krawedz->nastepny=NULL;
}
wynik=scanf("%c",&znak);
}
//powinno byc wczytane.
// Teraz przetworzymy dane.
koniec_kolejka=malloc(sizeof(struct kolejka_el));
koniec_kolejka->nastepny=NULL;
koniec_kolejka->poziom=1;
koniec_kolejka->wezel=1;
start_kolejka=koniec_kolejka;
teraz_kolejka=start_kolejka;
while(teraz_kolejka!=NULL)
{
//Odszukujemy wskaznik do wezla.
teraz_wezel=start_wezel;
i=1;
while((iwezel)&&(teraz_wezel!=NULL))
{
teraz_wezel=teraz_wezel->nastepny;
i++;
}
//Jesli jeszcze nie byl odweidzony
if(teraz_wezel->odwiedzony==0)
{
//Odwiedzilismy wezel.
teraz_wezel->odwiedzony=1;
//Wypiszmy go.
i=1;
tmp_wezel=start_wezel;
while((ipoziom)&&(tmp_wezel!=NULL))
{
tmp_wezel=tmp_wezel->nastepny;
i++;
}
//jestesmy na odpowiednim poziomie.
if(tmp_wezel->wypisanie==NULL)
{
tmp_wezel->wypisanie=malloc(sizeof(struct krawedz_el));
tmp_wezel->wypisanie->nastepny=NULL;
tmp_wezel->wypisanie->cel=teraz_wezel->liczba;
}
else
{
//jest tu cos, trzeba znalezc odpowiednie miejsce. - insertion sort.
if(tmp_wezel->wypisanie->cel>teraz_wezel->liczba)
{
//Pierwszy element zamieniamy.
tmp_krawedz=tmp_wezel->wypisanie;
tmp_wezel->wypisanie=malloc(sizeof(struct krawedz_el));
teraz_krawedz=tmp_wezel->wypisanie;
teraz_krawedz->nastepny=tmp_krawedz;
teraz_krawedz->cel=teraz_wezel->liczba;
}
else
{
teraz_krawedz=tmp_wezel->wypisanie;
while((teraz_krawedz->nastepny!=NULL)&&(teraz_krawedz->nastepny->celliczba))
{
teraz_krawedz=teraz_krawedz->nastepny;
}
//znalezlismy miejsce do wstawienia.
tmp_krawedz=teraz_krawedz->nastepny;
teraz_krawedz->nastepny=malloc(sizeof(struct krawedz_el));
teraz_krawedz=teraz_krawedz->nastepny;
teraz_krawedz->nastepny=tmp_krawedz;
teraz_krawedz->cel=teraz_wezel->liczba;
}
}
//Wstawiony do listy do wypisania.
//Dodajmy jego krawedzie do kolejki.
teraz_krawedz=teraz_wezel->krawedzie;
while(teraz_krawedz!=NULL)
{
if(teraz_krawedz->cel!=0)
{
koniec_kolejka->nastepny=malloc(sizeof(struct kolejka_el));
koniec_kolejka=koniec_kolejka->nastepny;
koniec_kolejka->nastepny=NULL;
koniec_kolejka->poziom=teraz_kolejka->poziom+1;
koniec_kolejka->wezel=teraz_krawedz->cel;
}
teraz_krawedz=teraz_krawedz->nastepny;
}
}
tmp_kolejka=teraz_kolejka;
teraz_kolejka=teraz_kolejka->nastepny;
free(tmp_kolejka);
}
//Wezly przetworzone i gotowe do wypisania.
teraz_wezel=start_wezel;
while(teraz_wezel->nastepny!=NULL)
{
teraz_krawedz=teraz_wezel->wypisanie;
if(teraz_krawedz!=NULL)
{
while(teraz_krawedz!=NULL)
{
printf("%d ",teraz_krawedz->cel);
tmp_krawedz=teraz_krawedz;
teraz_krawedz=teraz_krawedz->nastepny;
free(tmp_krawedz);
}
printf("n");
}
teraz_krawedz=teraz_wezel->krawedzie;
while(teraz_krawedz!=NULL)
{
tmp_krawedz=teraz_krawedz;
teraz_krawedz=teraz_krawedz->nastepny;
free(tmp_krawedz);
}
tmp_wezel=teraz_wezel;
teraz_wezel=teraz_wezel->nastepny;
free(tmp_wezel);
}
free(teraz_wezel);
}
else
{
//Szwindel. Nie bylo znakow.
return 1;
}
return 0;
}