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.