Ласло Краус	ПЈМП Први парцијални испит 14. 3. 2004.

Поставка задатка 1 (70 поена) (⇒ решење | почетак)

Пројектовати на језику C++ систем класа са следећим описом:

• Сваком апстрактном атому може да се направи копија (клон) и да се израчуна целобројна величина која представља број бајтова које би атом заузео у некој датотеци. Ова величина не може да се одреди оператором sizeof, већ се одређује на основу неопходног садржаја атома у датотеци. Атом може да се испише на стандардном излазу (оператор <<).
• Знак је атом који је описан са два податка: кодом знака (карактер, један бајт), и кратким целим бројем (два бајта) којим се описује стил знака. Исписује се на стандардном излазу по формату "Z(код, стил)".
• Пиксел је атом описан са четири бајта, од којих прва три представљају компоненте боје (црвену, зелену и плаву), а четврти представља фактор прозирности. Исписује се на стандардном излазу по формату "P(црвена, зелена, плава, прозирност)".
• Елемент је атом који садржи низ атома ограниченог капацитета. Ствара се празан задатог капацитета, а онда му се додају атоми, редом (оператор +=). Прекорачење капацитета низа атома изазива изузетак. Исписује се на стандардном излазу у угластим заградама као низ атома, међусобно раздвојених зарезима.
• Текст je елемент који садржи низ знакова ограниченог капацитета и информацију о дужини садржаја (кратак цео број, два бајта). Исписује се на стандардном излазу по формату "Tekst: (дужина) ", иза чега следи низ знакова.
• Слика је елемент који садржи низ пиксела ограниченог капацитета, као и информације о ширини и висини слике, изражене у броју пиксела (кратки цели бројеви по два бајта). Ствара се празна задатог капацитета низа пиксела и задате ширине. Исписује се на стандардном излазу по формату "Slika: (ширина, висина) ", иза чега следи низ пиксела.
• Документ је елемент који има своје име (конвенционални низ карактера завршен знаком '\0'). Документ може да садржи текстове, слике и друге документе. Документ се исписује на стандардном излазу по формату "Dokument: <име>", иза чега следи низ елемената.

Саставити на језику C++ главни програм који демонстрира формирање једног документа са неколико текстова, слика и других докумената, затим испише документ и на крају израчуна и испише величину документа.

Поставка задатка 2 (15 поена) (⇒ почетак)

Одговорити концизно на следећа питања

а) Навести редослед активности приликом конструкције и деструкције објекта изведене класе.

б) Којим редоследом треба навести рутине за обраду изузетка основне и изведене класе и зашто?

в) Који проблем решава и на којој идеји се заснива статички Хафманов алгоритам?

Поставка задатка 3 (15 поена) (⇒ решење | почетак)

Симболи A, B, C ..., H кодирају се са по три бита 000, 001, 010 ..., 111. Извршити компресију низа симбола CEEHHACDD применом динамичког Хафмановог поступка.

Решење задатка 1 (⇒ поставка | почетак)

#include <iostream.h>
#include <string.h>

class Atom {
  virtual void pisi (ostream& d) const =0;
public:
  virtual ~Atom() {}
  virtual Atom* kopija() const =0;
  virtual int velicina() const =0;
  friend ostream& operator<<(ostream& d, const Atom& a) { a.pisi(d); return d; }
};

class Znak: public Atom{ char kod; short stil;
  void pisi(ostream &d) const { d<<"Z("<<kod<<","<<stil<<")"; }
public:
  Znak(char k, short s): kod(k), stil(s){}
  Atom* kopija() const { return new Znak(*this); }
  int velicina() const { return sizeof(kod)+sizeof(stil); }
};

class Piksel: public Atom {
  char boja[3]; char prozirnost;
  void pisi(ostream &d) const {
    d<<"P("<<(int)boja[0]<<","<<(int)boja[1]<<","<<
             (int)boja[2]<<","<<(int)prozirnost<<")";
  }
public:
  Piksel(char c, char z, char p, char t): prozirnost(t)
    { boja[0]=c; boja[1]=z; boja[2]=p; }
  Atom* kopija() const { return new Piksel(*this); }
  int velicina() const { return 3*sizeof(boja[0])+sizeof(prozirnost); }
};

class PreviseAtoma{};

class Element: public Atom {
  Atom** atomi; short kapacitet;
  void kopirajSpec(const Element& element);
  void brisiSpec();
protected:
  short brAtoma;
  Element& operator+=(const Atom& atom) {
    if (brAtoma==kapacitet) throw PreviseAtoma();
    atomi[brAtoma++]=atom.kopija();
    return *this;
  }
  void pisi(ostream &d) const;
public:
  Element(int k):kapacitet(k) { atomi=new Atom*[kapacitet]; brAtoma=0; }
  Element(const Element& element): Atom(element) { kopirajSpec(element); }
  ~Element() { brisiSpec(); }
  Element& operator=(const Element& element) {
    if (&element!=this) {
      brisiSpec(); Atom::operator=(element); kopirajSpec(element);
    }
    return *this;
  }
  int velicina() const;
};

void Element::kopirajSpec(const Element& element) {
  brAtoma=element.brAtoma;
  kapacitet=element.kapacitet;
  atomi=new Atom*[kapacitet];
  for (int i=0; i<brAtoma; i++) atomi[i]=element.atomi[i]->kopija();
}

void Element::brisiSpec() {
  for (brAtoma--; brAtoma>=0; brAtoma--) delete atomi[brAtoma];
  delete atomi; atomi=NULL;
}

void Element::pisi(ostream &d) const {
  for (int i=0; i<brAtoma; i++)
    d<<"["<<*atomi[i]<<"]"<<((i<brAtoma-1)?", ":"");
}

int Element::velicina() const {
  int d=0;
  for (int i=0; i<brAtoma; i++) d+=atomi[i]->velicina();
  return d;
};

class Tekst: public Element {
  void pisi(ostream &d) const
    { d<<"Tekst: ("<<brAtoma<<") "; Element::pisi(d); }
public:
  Tekst(int k): Element(k) {}
  Element& operator+=(const Znak& znak) { return Element::operator+=(znak); }
  Atom* kopija() const { return new Tekst(*this); }
  int velicina() const { return Element::velicina()+sizeof(brAtoma); }
};


class Slika: public Element{
  short sirina, visina;
  virtual void pisi(ostream &d) const {
    d<<"Slika: ("<<sirina<<", "<<visina<<") ";
    Element::pisi(d);
  }
public:
  Slika(int k, short s): Element(k), sirina(s), visina(0) {}
  Element& operator+=(const Piksel& piksel){
    Element::operator+=(piksel);
    if (brAtoma%sirina==1) visina++;
    return *this;
  }
  Atom* kopija() const { return new Slika(*this); }
  int velicina() const { return Element::velicina()+sizeof(sirina)+sizeof(visina); }
};

class Dokument: public Element{
  char *ime;
  void kopirajSpec(const Dokument& dokument) {
     ime=new char[strlen(dokument.ime)+1];
     strcpy(ime,dokument.ime);
  }
  void brisiSpec() { delete ime; }
  void pisi(ostream &d) const
    { d<<"Dokument: <"<<ime<<">"; Element::pisi(d); }
public:
  Dokument(char* naziv, int k):Element(k)
    { ime=new char[strlen(naziv)+1];  strcpy(ime,naziv); }
  Dokument(const Dokument& dok): Element(dok) {kopirajSpec(dok);}
  ~Dokument() { brisiSpec(); }
  Dokument& operator=(const Dokument& dok) {
    if (&dok!=this) {
      brisiSpec(); Element::operator=(dok); kopirajSpec(dok);
    }
    return *this;
  }
  Element& operator+=(const Element& element){
    return Element::operator+=(element);
  }
  Atom* kopija() const { return new Dokument(*this); }
  int velicina() const { return Element::velicina()+strlen(ime)+1; }
};

void main(){
  try{ Dokument du("Unutra",2), d("Spolja",2);
    Tekst t1(5);
    for (int i=0; i<5; i++) t1+=Znak(65+i,3);
//  t1+=Znak(70,2); //test izuzetka PreviseAtoma
    du+=t1;
    Slika s(8,2);
    for (i=0; i<6; i++) s+=Piksel(127-i,i,127,100);
    du+=s;
    d+=du;
    Tekst t2(10);
    for (i=0; i<3; i++) t2+=Znak(97+i,5);
    d+=t2;
    cout<<d<<endl;
    cout<<"Velicina
    dokumenta="<<d.velicina()<<endl;
  } catch (PreviseAtoma) { cout<<"Previse atoma!"<<endl; }
}

Решење задатка 3 (⇒ поставка | почетак)

0100 1000 1001 1100 1000 0000 0110 0011 1001 (36b > 9·3=27b))

Copyright © 2004, Laslo Kraus
Последња ревизија: 08.7.2004.