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.