Guest User

Untitled

a guest
Jan 16th, 2019
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 16.56 KB | None | 0 0
  1.  
  2. #include <iostream>
  3.  
  4. using namespace std;
  5.  
  6. template <typename Tip>
  7. class Iterator;
  8. template<typename tip>
  9. class Niz
  10. {
  11. int tren, broj_el, kapacitet, prati;
  12. tip *niz;
  13. public:
  14. Niz(): tren(0), broj_el(0), kapacitet(1), prati(0), niz(new tip[kapacitet]) {}
  15. virtual int brojElemenata() const
  16. {
  17. return broj_el;
  18. }
  19. virtual ~Niz()
  20. {
  21. if(broj_el>0)
  22. {
  23. delete[] niz;
  24. }
  25. }
  26. Niz (const Niz &n);
  27. Niz &operator=(const Niz &n);
  28. virtual tip trenutni();
  29. virtual bool prethodni();
  30. virtual bool sljedeci();
  31. virtual void pocetak();
  32. virtual void kraj();
  33. virtual void dodajIspred(const tip &element);
  34. virtual void dodajIza(const tip &element);
  35. virtual void obrisi();
  36. virtual tip operator[](int n) const;
  37. friend class Iterator<tip>;
  38. };
  39.  
  40. template<typename tip>
  41. class Lista : public Niz<tip>
  42. {
  43. struct Cvor
  44. {
  45. tip element;
  46. Cvor *sljedeci;
  47. };
  48. Cvor *poc, *kr, *tren;
  49. int broj_el;
  50. public:
  51. Lista():
  52. poc(0), kr(0), tren(0), broj_el(0) {}
  53. ~Lista();
  54. Lista (const Lista &l);
  55. Lista &operator=(const Lista &l);
  56. int brojElemenata() const;
  57. tip trenutni() const;
  58. bool prethodni();
  59. bool sljedeci();
  60. void pocetak();
  61. void kraj();
  62. void dodajIspred(const tip &element);
  63. void dodajIza(const tip &element);
  64. void obrisi();
  65. tip operator[](int n) const;
  66. friend class Iterator<tip>;
  67. };
  68.  
  69. //Klasa DvostrukaLista - zadaca.
  70.  
  71. template<typename tip>
  72. class DvostrukaLista : public Niz<tip>
  73. {
  74. struct DupliCvor
  75. {
  76. tip element;
  77. DupliCvor *sljedeci;
  78. DupliCvor *prethodni;
  79. };
  80. DupliCvor *poc, *kr, *tren;
  81. int broj_el;
  82. public:
  83. DvostrukaLista(): poc(0), kr(0), tren(0), broj_el(0) {}
  84. ~DvostrukaLista();
  85. DvostrukaLista (const DvostrukaLista &dl);
  86. DvostrukaLista &operator=(const DvostrukaLista &dl);
  87. int brojElemenata() const;
  88. tip trenutni() const;
  89. bool prethodni();
  90. bool sljedeci();
  91. void pocetak();
  92. void kraj();
  93. void dodajIspred(const tip &element);
  94. void dodajIza(const tip &element);
  95. void obrisi();
  96. tip operator[](int n) const;
  97. friend class Iterator<tip>;
  98. };
  99.  
  100.  
  101. //Klasa iterator, nisam je ni poceo na tutorijalu zbog ispravljanja greski sa pripreme za tutorijal.
  102.  
  103. template<typename tip>
  104. class Iterator
  105. {
  106. const Niz<tip> *niz;
  107. const Lista<tip> *lista;
  108. const DvostrukaLista<tip> *dvostruka;
  109. int trenutniNiz;
  110. typename Lista<tip>::Cvor *trenutniLista;
  111. typename DvostrukaLista<tip>::DupliCvor *trenutniDvostrukaLista;
  112. public:
  113. Iterator(const Niz<tip> &n) : niz(&n), lista(0), dvostruka(0), trenutniNiz(0), trenutniLista(0), trenutniDvostrukaLista(0) {}
  114. Iterator (const Lista<tip> &l) : lista(&l), niz(0), dvostruka(0), trenutniNiz(0), trenutniLista(l.poc), trenutniDvostrukaLista(0) {}
  115. Iterator (const DvostrukaLista<tip> &dl) : dvostruka(&dl), niz(0), lista(0), trenutniNiz(0), trenutniLista(0), trenutniDvostrukaLista(dl.poc) {}
  116. tip trenutni() const;
  117. bool prethodni();
  118. bool sljedeci ();
  119. void pocetak();
  120. void kraj();
  121. };
  122.  
  123.  
  124. template<typename tip>
  125. Niz<tip>::Niz (const Niz<tip> &n)
  126. {
  127. niz=new tip[n.broj_el];
  128. broj_el=n.broj_el;
  129. kapacitet=n.kapacitet;
  130. tren=n.tren;
  131. prati=n.prati;
  132. for(int i=0; i<broj_el; i++)
  133. {
  134. niz[i]=n.niz[i];
  135. }
  136. }
  137.  
  138. template<typename tip>
  139. Niz<tip> &Niz<tip>::operator=(const Niz<tip> &n)
  140. {
  141. if(broj_el>0)
  142. {
  143. delete[] niz;
  144. }
  145. niz=new tip[n.broj_el];
  146. broj_el=n.broj_el;
  147. kapacitet=n.kapacitet;
  148. tren=n.tren;
  149. prati=n.prati;
  150. for(int i=0; i<broj_el; i++)
  151. {
  152. niz[i]=n.niz[i];
  153. }
  154. return *this;
  155. }
  156.  
  157.  
  158. template<typename tip>
  159. tip Niz<tip>::trenutni()
  160. {
  161. if (broj_el==0) throw "Nema elemenata u nizu";
  162. return niz[tren];
  163. }
  164.  
  165. template<typename tip>
  166. bool Niz<tip>::prethodni()
  167. {
  168. if (tren==0) return false;
  169. tren--;
  170. return true;
  171. }
  172.  
  173. template<typename tip>
  174. bool Niz<tip>::sljedeci()
  175. {
  176. if (tren==broj_el-1) return false;
  177. tren++;
  178. return true;
  179. }
  180.  
  181. template<typename tip>
  182. void Niz<tip>::pocetak()
  183. {
  184. tren=0;
  185. }
  186.  
  187. template<typename tip>
  188. void Niz<tip>::kraj()
  189. {
  190. tren=broj_el-1;
  191. }
  192.  
  193. template<typename tip>
  194. void Niz<tip>::dodajIspred(const tip &element)
  195. {
  196. if (broj_el==0)
  197. {
  198. if(prati!=0)
  199. {
  200. niz=new tip[kapacitet];
  201. }
  202. niz[broj_el]=element;
  203. broj_el++;
  204. }
  205. else
  206. {
  207. niz[broj_el]=element;
  208. broj_el++;
  209. for (int i=broj_el-1; i>tren; i--)
  210. {
  211. tip pom=niz[i];
  212. niz[i]=niz[i-1];
  213. niz[i-1]=pom;
  214. }
  215. tren++;
  216. }
  217. if(broj_el==kapacitet)
  218. {
  219. kapacitet*=2;
  220. tip *pom=new tip[kapacitet];
  221. for(int i=0; i<broj_el; i++)
  222. {
  223. pom[i]=niz[i];
  224. }
  225. delete[] niz;
  226. niz=pom;
  227. }
  228. }
  229.  
  230. template<typename tip>
  231. void Niz<tip>::dodajIza(const tip &element)
  232. {
  233. if (broj_el==0)
  234. {
  235. if(prati!=0)
  236. {
  237. niz=new tip[kapacitet];
  238. }
  239. niz[broj_el]=element;
  240. broj_el++;
  241. }
  242. else
  243. {
  244. niz[broj_el]=element;
  245. broj_el++;
  246. for (int i=broj_el-1; i>tren; i--)
  247. {
  248. tip pom=niz[i];
  249. niz[i]=niz[i-1];
  250. niz[i-1]=pom;
  251. }
  252. }
  253. if(broj_el==kapacitet)
  254. {
  255. kapacitet*=2;
  256. tip *pom=new tip[kapacitet];
  257. for(int i=0; i<broj_el; i++)
  258. {
  259. pom[i]=niz[i];
  260. }
  261. delete[] niz;
  262. niz=pom;
  263. }
  264. }
  265.  
  266. template<typename tip>
  267. void Niz<tip>::obrisi()
  268. {
  269. if (broj_el==0) throw "Niz je prazan.\n";
  270. if(broj_el==1)
  271. {
  272. broj_el=0;
  273. delete[] niz;
  274. niz=0;
  275. if(prati==0) prati=1;
  276. }
  277. else
  278. {
  279. broj_el--;
  280. if(broj_el>0 && broj_el==kapacitet/4)
  281. {
  282. kapacitet/=2;
  283. tip *pom=new tip[kapacitet];
  284. for(int i=0; i<broj_el; i++)
  285. {
  286. if(i<tren) pom[i]=niz[i];
  287. else pom[i]=niz[i+1];
  288. }
  289. delete[] niz;
  290. niz=pom;
  291. }
  292. else
  293. {
  294. tip *pom=new tip[broj_el];
  295. for(int i=0; i<broj_el; i++)
  296. {
  297. if(i<tren) pom[i]=niz[i];
  298. else pom[i]=niz[i+1];
  299. }
  300. delete[] niz;
  301. niz=pom;
  302. }
  303. }
  304. }
  305.  
  306. template<typename tip>
  307. tip Niz<tip>::operator[](int n) const
  308. {
  309. if (n<0 || n>broj_el-1) throw "Pogresan indeks";
  310. //tren=n-1;
  311. return niz[n];
  312. }
  313.  
  314. template<typename tip>
  315. Lista<tip>::~Lista() {
  316. Cvor *pom=poc;
  317. while(pom!=0){
  318. pom=pom->sljedeci;
  319. delete poc;
  320. poc=pom;
  321. }
  322. broj_el=0;
  323. poc=kr=tren=0;
  324. }
  325.  
  326. //URADI KOPIJU I OPERATOR DODJELE!!!
  327.  
  328. template<typename tip>
  329. int Lista<tip>::brojElemenata() const
  330. {
  331. return broj_el;
  332. }
  333.  
  334. template<typename tip>
  335. tip Lista<tip>::trenutni() const
  336. {
  337. if (poc==0) throw "Nema elemenata u nizu";
  338. return tren->element;
  339. }
  340.  
  341. template<typename tip>
  342. bool Lista<tip>::prethodni()
  343. {
  344. if (tren==poc) return false;
  345. else
  346. {
  347. Cvor *p=poc;
  348. while (p->sljedeci!=tren)
  349. {
  350. p=p->sljedeci;
  351. }
  352. tren=p;
  353. return true;
  354. }
  355. }
  356.  
  357. template<typename tip>
  358. bool Lista<tip>::sljedeci()
  359. {
  360. if (tren==kr) return false;
  361. else
  362. {
  363. tren=tren->sljedeci;
  364. return true;
  365. }
  366. }
  367.  
  368. template<typename tip>
  369. void Lista<tip>::pocetak()
  370. {
  371. tren=poc;
  372. }
  373.  
  374. template<typename tip>
  375. void Lista<tip>::kraj()
  376. {
  377. tren=kr;
  378. }
  379.  
  380. template<typename tip>
  381. void Lista<tip>::dodajIspred(const tip &element)
  382. {
  383. Cvor *novi=new Cvor;
  384. novi->element=element;
  385. novi->sljedeci=0;
  386. if (poc==0)
  387. {
  388. poc=kr=tren=novi;
  389. }
  390. else if (tren==poc)
  391. {
  392. novi->sljedeci=poc;
  393. poc=novi;
  394. }
  395.  
  396. else
  397. {
  398. Cvor *prethodni=poc;
  399. novi->sljedeci=tren;
  400. while (prethodni->sljedeci != tren)
  401. prethodni=prethodni->sljedeci;
  402. prethodni->sljedeci=novi;
  403. }
  404. broj_el++;
  405. }
  406.  
  407. template<typename tip>
  408. void Lista<tip>::dodajIza(const tip &element)
  409. {
  410. Cvor *novi=new Cvor;
  411. novi->element=element;
  412. novi->sljedeci=0;
  413. if (brojElemenata()==0)
  414. {
  415. poc=tren=kr=novi;
  416. }
  417. else
  418. {
  419. if(tren->sljedeci!=0)
  420. {
  421. novi->sljedeci=tren->sljedeci;
  422. }
  423. tren->sljedeci=novi;
  424. }
  425. broj_el++;
  426. }
  427.  
  428. template<typename tip>
  429. void Lista<tip>::obrisi()
  430. {
  431. if (broj_el==0) throw "Lista je prazna";
  432. if(tren==poc)
  433. {
  434. poc=poc->sljedeci;
  435. delete tren;
  436. tren=poc;
  437. }
  438. else
  439. {
  440. Cvor *prethodni;
  441. prethodni=poc;
  442. while (prethodni->sljedeci != tren)
  443. {
  444. prethodni=prethodni->sljedeci;
  445. }
  446. if(tren->sljedeci!=0)
  447. {
  448. prethodni->sljedeci=tren->sljedeci;
  449. delete tren;
  450. tren=prethodni->sljedeci;
  451. }
  452. else
  453. {
  454. prethodni->sljedeci=0;
  455. delete tren;
  456. tren=prethodni;
  457. }
  458. }
  459. broj_el--;
  460. }
  461.  
  462. template<typename tip>
  463. tip Lista<tip>::operator[](int n) const
  464. {
  465. if (n<0 || n>=brojElemenata()) throw "Pogresan indeks";
  466. Cvor *p=poc;
  467. int br(0);
  468. while (br<n)
  469. {
  470. p=p->sljedeci;
  471. br++;
  472. }
  473. return p->element;
  474. }
  475.  
  476. template<typename tip>
  477. DvostrukaLista<tip>::~DvostrukaLista() {
  478. DupliCvor *pom=poc;
  479. while(pom!=0){
  480. pom=pom->sljedeci;
  481. delete poc;
  482. poc=pom;
  483. }
  484. broj_el=0;
  485. poc=kraj=tren=0;
  486. }
  487.  
  488. //URADI KOPIJU I OPERATOR DODJELE!!!
  489.  
  490. template<typename tip>
  491. int DvostrukaLista<tip>::brojElemenata() const
  492. {
  493. return broj_el;
  494. }
  495.  
  496. template<typename tip>
  497. tip DvostrukaLista<tip>::trenutni() const
  498. {
  499. if (poc==0) throw "Nema elemenata u nizu";
  500. return tren->element;
  501. }
  502.  
  503. template<typename tip>
  504. bool DvostrukaLista<tip>::prethodni()
  505. {
  506. if (tren==poc) return false;
  507. else
  508. {
  509. tren=tren->prethodni;
  510. return true;
  511. }
  512. }
  513.  
  514. template<typename tip>
  515. bool DvostrukaLista<tip>::sljedeci()
  516. {
  517. if (tren==kr) return false;
  518. else
  519. {
  520. tren=tren->sljedeci;
  521. return true;
  522. }
  523. }
  524.  
  525. template<typename tip>
  526. void DvostrukaLista<tip>::pocetak()
  527. {
  528. tren=poc;
  529. }
  530.  
  531. template<typename tip>
  532. void DvostrukaLista<tip>::kraj()
  533. {
  534. tren=kr;
  535. }
  536.  
  537. template<typename tip>
  538. void DvostrukaLista<tip>::dodajIspred(const tip &element)
  539. {
  540.  
  541. DupliCvor *novi=new DupliCvor;
  542. novi->element=element;
  543. novi->sljedeci=0;
  544. novi->prethodni=0;
  545. if (brojElemenata()==0)
  546. {
  547. poc=kr=tren=novi;
  548. }
  549. else if (tren==poc)
  550. {
  551. tren->prethodni=novi;
  552. novi->sljedeci=tren;
  553. poc=novi;
  554. }
  555.  
  556. else
  557. {
  558. tren->prethodni->sljedeci=novi;
  559. novi->prethodni=tren->prethodni;
  560. tren->prethodni=novi;
  561. novi->sljedeci=tren;
  562. }
  563. broj_el++;
  564. }
  565.  
  566.  
  567. template<typename tip>
  568. void DvostrukaLista<tip>::dodajIza(const tip &element)
  569. {
  570. DupliCvor *novi=new DupliCvor;
  571. novi->element=element;
  572. novi->sljedeci=0;
  573. novi->prethodni=0;
  574. if (brojElemenata()==0)
  575. {
  576. poc=tren=kr=novi;
  577. }
  578. else
  579. {
  580. if(tren->sljedeci!=0)
  581. {
  582. novi->sljedeci=tren->sljedeci;
  583. }
  584. tren->sljedeci->prethodni=novi;
  585. tren->sljedeci=novi;
  586. novi->prethodni=tren;
  587. }
  588. broj_el++;
  589. }
  590.  
  591.  
  592. template<typename tip>
  593. void DvostrukaLista<tip>::obrisi()
  594. {
  595. if (broj_el==0) throw "Lista je prazna";
  596. else if(broj_el==1)
  597. {
  598. delete tren;
  599. broj_el--;
  600. sljedeci=0;
  601. prethodni=0;
  602. }
  603. else if(tren==poc)
  604. {
  605. poc=poc->sljedeci;
  606. delete tren;
  607. tren=poc;
  608. tren->prethodni=0;
  609. broj_el--;
  610. }
  611. else
  612. {
  613. if(tren->sljedeci==0)
  614. {
  615. DupliCvor *pom=tren->prethodni;
  616. pom->sljedeci=0;
  617. delete tren;
  618. tren=pom->sljedeci;
  619. }
  620. else
  621. {
  622. DupliCvor *pom=tren->prethodni;
  623. pom->sljedeci=tren->sljedeci;
  624. delete tren;
  625. tren=pom->sljedeci;
  626. tren->prethodni=pom;
  627. }
  628. broj_el--;
  629. }
  630. }
  631.  
  632.  
  633.  
  634. template<typename tip>
  635. tip DvostrukaLista<tip>::operator[](int n) const
  636. {
  637. if (n<0 || n>=brojElemenata()) throw "Pogresan indeks";
  638. DupliCvor *p=poc;
  639. int br(0);
  640. while (br<n)
  641. {
  642. p=p->sljedeci;
  643. br++;
  644. }
  645. return p->element;
  646. }
  647.  
  648.  
  649. template<typename tip>
  650. tip Iterator<tip>::trenutni() const
  651. {
  652. if(niz!=0)
  653. {
  654. if(niz->brojElemenata()==0) throw "Niz je prazan.\n";
  655. return niz->niz[trenutniNiz];
  656. }
  657. if(lista!=0)
  658. {
  659. if(lista->brojElemenata()==0) throw "Lista je prazna.\n";
  660. return trenutniLista->element;
  661. }
  662. if(dvostruka!=0)
  663. {
  664. if(dvostruka->brojElemenata()==0) throw "Lista je prazna.\n";
  665. return trenutniDvostrukaLista->element;
  666. }
  667. }
  668.  
  669. template<typename tip>
  670. bool Iterator<tip>::prethodni()
  671. {
  672. if(niz!=0)
  673. {
  674. if(trenutniNiz==0)
  675. {
  676. return false;
  677. }
  678. else
  679. {
  680. trenutniNiz--;
  681. return true;
  682. }
  683. }
  684. if(lista!=0)
  685. {
  686. if(trenutniLista==lista) return false;
  687. else
  688. {
  689. typename Lista<tip>::Cvor *p=lista;
  690. while (p->sljedeci!=trenutniLista)
  691. {
  692. p=p->sljedeci;
  693. }
  694. trenutniLista=p;
  695. return true;
  696. }
  697. }
  698. if(dvostruka!=0)
  699. {
  700. if(trenutniDvostrukaLista->prethodni==0)
  701. {
  702. return false;
  703. }
  704. else
  705. {
  706. trenutniDvostrukaLista=trenutniDvostrukaLista->prethodni;
  707. return true;
  708. }
  709. }
  710. }
  711.  
  712. template<typename tip>
  713. bool Iterator<tip>::sljedeci()
  714. {
  715. if(niz!=0)
  716. {
  717. if (trenutniNiz==niz->brojElemenata()-1) return false;
  718. trenutniNiz++;
  719. return true;
  720. }
  721. if(lista!=0)
  722. {
  723. if (trenutniLista->sljedeci==0) return false;
  724. else
  725. {
  726. trenutniLista=trenutniLista->sljedeci;
  727. return true;
  728. }
  729. }
  730. if(dvostruka!=0)
  731. {
  732. if(trenutniDvostrukaLista->sljedeci==0)
  733. {
  734. return false;
  735. }
  736. else
  737. {
  738. trenutniDvostrukaLista=trenutniDvostrukaLista->sljedeci;
  739. return true;
  740. }
  741. }
  742. }
  743.  
  744. template<typename tip>
  745. void Iterator<tip>::pocetak()
  746. {
  747. while(prethodni());
  748. }
  749.  
  750. template<typename tip>
  751. void Iterator<tip>::kraj()
  752. {
  753. while(sljedeci());
  754.  
  755. }
  756.  
  757. template<typename tip>
  758. tip dajMaksimum(const Niz<tip>& n)
  759. {
  760. if(n.brojElemenata()==0) throw "Niz je prazan.\n";
  761. else
  762. {
  763. tip max=n.niz[0];
  764. for(int i=0; i<int(n.brojElemenata()); i++)
  765. {
  766. if(n[i]>max)
  767. {
  768. max=n[i];
  769. }
  770. }
  771. }
  772. return max;
  773. }
  774.  
  775. template<typename tip>
  776. tip dajMaksimum(const Lista<tip>& l)
  777. {
  778. if(l.poc==0) throw "Lista je prazna.\n";
  779. Iterator<tip> pom(l);
  780. tip max=pom.pocetak();
  781. while(pom.sljedeci())
  782. {
  783. if(pom.trenutni()>max)
  784. {
  785. max=pom.trenutni();
  786. }
  787. }
  788. return max;
  789. }
  790.  
  791. template<typename tip>
  792. tip dajMaksimum(const DvostrukaLista<tip>& dl)
  793. {
  794. if(dl.poc==0) throw "Lista je prazna.\n";
  795. Iterator<tip> pom(dl);
  796. tip max=pom.pocetak();
  797. while(pom.sljedeci())
  798. {
  799. if(pom.trenutni()>max)
  800. {
  801. max=pom.trenutni();
  802. }
  803. }
  804. return max;
  805. }
  806.  
  807.  
  808. int main()
  809. {
  810. Niz<int> niz;
  811. int a(5), c(10), d(1);
  812. niz.dodajIspred(a);
  813. niz.dodajIspred(c);
  814. cout<<niz.trenutni()<<endl;
  815. niz.obrisi();
  816. cout<<niz.trenutni()<<endl;
  817. niz.dodajIza(c);
  818. cout<<"Trenutno ima: "<<niz.brojElemenata()<<" clanova.\n";
  819. niz.dodajIza(d);
  820. cout<<endl;
  821. for (int i=0; i<int(niz.brojElemenata()); i++)
  822. cout<<niz[i]<<endl;
  823.  
  824. Lista <int> l;
  825. l.dodajIspred(1);
  826. l.dodajIspred(5);
  827. l.dodajIspred(10);
  828. l.dodajIza(10);
  829. l.dodajIza(5);
  830. l.dodajIza(1);
  831. cout<<l.trenutni()<<endl;
  832. for (int i=0; i<6; i++)
  833. {
  834. cout<<l[i]<<",";
  835. }
  836. cout<<endl;
  837. l.obrisi();
  838. cout<<l.trenutni()<<endl;
  839.  
  840. return 0;
  841.  
  842. }
Add Comment
Please, Sign In to add comment