Laboratorium programowania zad 8

Zadanie z laboratorium programowania na Informatyce UW.

Zadanie 8 (termin wysylania rozwiazan: 7 III 2008, godz. 23:59)

(Grupowanie plikow)

Napisz program, ktory wczyta z wejscia informacje o plikach i podzieli
te pliki na grupy tak, by laczny rozmiar plikow w jednej grupie nie
przekroczyl 700 (megabajtow).

Postac danych:

Na wejsciu programu jest ciag wierszy, z ktorych kazdy opisuje jeden
plik. W wierszu jest kolejno:

- liczba calkowita wyrazajaca rozmiar pliku (w megabajtach)
- jedna spacja
- nazwa pliku (wolno zalozyc, ze moze byc wartoscia typu string)

Postac wyniku:

Program powinien wypisac tyle wierszy, ile grup plikow utworzy.
W kazdym maja sie znalezc nazwy plikow, ktore trafily do danej
grupy, z zachowaniem kolejnosci, w jakiej pliki pojawily sie
na wejsciu. Po kazdej nazwie pliku wypisujemy jedna spacje.

Algorytm:

Program wczytuje z wejscia informacje o kolejnych plikach i dla
kazdego szuka pierwszej grupy, do ktorej plik ten sie zmiesci. Robi
to, przechodzac po utworzonych do tej pory grupach w kolejnosci, w
jakiej te grupy powstawaly. Jesli plik nie miesci sie w zadnej z
dotychczas powstalych grup, tworzymy nowa.

Pliki o rozmiarze przekraczajacym 700 program powinien zignorowac.

Np. dla danych:

400 jeden
10 dwa
300 trzy
500 cztery
111 piec
2222 szesc
222 siedem
1 osiem
10 dziewiec
200 dziesiec

program powinien wypisac:

jeden dwa piec osiem dziewiec 
trzy siedem 
cztery dziesiec 

Wskazowka:

W rozwiazaniu nalezy zbudowac liste grup, a z kazda grupa zwiazac
liste plikow, ktore przydzielilismy do tej grupy.

A oto rozwiązanie:

program zad8;
type

	//Struktura danych to lista dwuwymiarowa. 

	//Tutaj beda przechowywane pliki
	plik_t=^plik_r_t;
	plik_r_t=record
		nastepny:plik_t;
		nazwa:string;
		rozmiar:integer;
	end;
	
	//A tu cale wiersze
	grupa_t=^grupa_r_t;
    grupa_r_t=record 
		wolne:integer; //Wolne miejsce w grupie
		nastepny:grupa_t;
		plik:plik_t; //Pierwszy plik
		ostatni:plik_t;
	end;


var rozmiar:integer;
nazwa:string;
plik,tmp_plik: plik_t;
grupa,pierwszy,tmp_grupa:grupa_t;
znaleziono:boolean;
spacja:char;
begin



	//Tworzymy pierwsza grupe

	new(pierwszy);
	pierwszy^.nastepny:=nil;
	grupa:=pierwszy;
	grupa^.wolne:=700;

	new(grupa^.plik);
	plik:=grupa^.plik;
	plik^.nastepny:=nil;
	plik^.nazwa:='';
	grupa^.ostatni:=plik;
	
	
	//Wczytujemy pliki
	while not EOF do
	begin
		read(rozmiar);
		read(spacja);
		read(nazwa);
		znaleziono:=false;
		grupa:=pierwszy;
		
		//write('Umieszczamy plik "');
		//write(nazwa);
		//write('" o rozmiarze ');
		//write(rozmiar);
		
		if rozmiar<701 then
		begin
			while ((grupa^.nastepny  nil) AND (znaleziono=false))  do
			begin
				//Dla kazdej grupy przechowujemy ilosc wolnego miejsca. dzieki temu nie musimy biegac po tej liscie.
				if ((grupa^.wolne >= rozmiar) AND (znaleziono=false)) then
				begin
					//writeln('    OK. jest grupa z ');
					//write(grupa^.wolne);
					//write(' miejsca');
					//Znalezlismy grupe w ktorej jest wystarczajaco miejsca
						grupa^.ostatni^.nazwa:=nazwa;
						grupa^.ostatni^.rozmiar:=rozmiar;
						new(grupa^.ostatni^.nastepny);
						grupa^.ostatni:=grupa^.ostatni^.nastepny;
						grupa^.ostatni^.nastepny:=nil;
						grupa^.wolne:=grupa^.wolne-rozmiar;
					//Zeby nie wstawiac pliku kilka razy:
					znaleziono:=true;
				end
				else
				begin
					//writeln('    w tej grupie jest za malo. tylko ');
					//write(grupa^.wolne);
					//write(' miejsca');
					grupa:=grupa^.nastepny;
				end
			end;
			
			if (znaleziono=false) then
			begin
				grupa^.wolne:=700-rozmiar;

				//wstawiamy plik:
				
				new(grupa^.plik);
				grupa^.plik^.nazwa:=nazwa;
				grupa^.plik^.rozmiar:=rozmiar;
				
				//Wstawiamy strażnika
				
				new(grupa^.plik^.nastepny);
				grupa^.plik^.nastepny^.nastepny:=nil;
				grupa^.plik^.nastepny^.rozmiar:=0;
				grupa^.plik^.nastepny^.nazwa:='';
				grupa^.ostatni:=grupa^.plik^.nastepny;

				//I straznika dla grupy
				new(grupa^.nastepny);
				grupa:=grupa^.nastepny;
				grupa^.nastepny:=nil;

			end
		end
	end;
	//I pliki wczytane. Wystarczy wypisac.

	
	grupa:=pierwszy;
	while grupa^.nastepnynil do
	begin
		plik:=grupa^.plik;
		while plik^.nastepnynil do
		begin
			write(plik^.nazwa);
			
			if (plik^.nazwa'') then
				write(' ');
			
			//sprzatamy:
			tmp_plik:=plik;
			plik:=plik^.nastepny;
			dispose(tmp_plik);
		end;
		//usuwamy straznika:
		dispose(plik);
		
		writeln();
		
		//Sprzatamy:
		tmp_grupa:=grupa;
		grupa:=grupa^.nastepny;
		dispose(tmp_grupa);
	end;
	dispose(grupa);
	//usuwamy straznika
end.