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; }