Laboratorium programowania zad 16

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

Leave a Reply