Posted By

markoaleric on 11/12/12


Tagged

array polje implementacija msort


Versions (?)

Zadatak 1 lista_polje.h


 / Published in: C++
 

Header lista_polje.h, implementacija liste pomoću polja

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. struct tzivotinja{
  5. int sifra, god, mj, dan;
  6. float cijena;
  7. char vrsta[40], ime[40];
  8. };
  9. typedef int element;
  10. struct zapis{
  11. tzivotinja zivotinja[100];
  12. int kursor;
  13. };
  14. typedef struct zapis lista;
  15. bool brisiime=0;
  16. element LastL(lista *L){
  17. return (L->kursor);
  18. }
  19.  
  20. element EndL(lista *L){
  21. return (L->kursor);
  22. }
  23. element FirstL(lista *L){
  24. if(L->kursor==0)
  25. return EndL(L);
  26. else
  27. return 0;
  28. }
  29. tzivotinja RetreiveL(element p, lista *L){
  30. return L->zivotinja[p];
  31. }
  32. element InsertL(tzivotinja x,element p,lista *L){
  33. if(p>L->kursor || p<0) return 0;
  34. else{
  35. for( int q=L->kursor;q>=p;q--)
  36. L->zivotinja[q+1]=L->zivotinja[q];
  37. L->kursor++;
  38. L->zivotinja[p]=x;
  39. return 1; }
  40. }
  41. element NextL(element p, lista *L){
  42. if(p==EndL(L)-1) return EndL(L);
  43. if(p==EndL(L)) return 0;
  44. else
  45. return p+1;
  46. }
  47. element PreviousL(element p, lista *L){
  48. if(p==FirstL(L)) return -1;
  49. if(p==EndL(L)) return p-1;
  50. return p-1;
  51. }
  52. element LocateL(tzivotinja trazi, lista *L){
  53. element pozicija=EndL(L);
  54. pozicija=PreviousL(pozicija,L);
  55.  
  56. if(brisiime==1){
  57. if(FirstL(L)!=EndL(L)){
  58. while(true){
  59. tzivotinja tmp=RetreiveL(pozicija,L);
  60. if(strcmp(trazi.ime,tmp.ime)==0)
  61. return pozicija;
  62. if(pozicija==FirstL(L))break;
  63. pozicija=PreviousL(pozicija,L);
  64. }
  65.  
  66. }
  67. }
  68. if(brisiime==0){
  69. if(FirstL(L)!=EndL(L)){
  70. while(true){
  71. tzivotinja tmp=RetreiveL(pozicija,L);
  72. if(strcmp(trazi.vrsta,tmp.vrsta)==0)
  73. return pozicija;
  74. if(pozicija==FirstL(L))break;
  75. pozicija=PreviousL(pozicija,L);
  76. }
  77. }
  78. }
  79. return EndL(L);
  80. }
  81. element DeleteL(element p, lista *L){
  82. if((L->kursor==0))
  83. return 0;
  84. if((p>=L->kursor)||(p<0))
  85. return 0;
  86. if(p==EndL(L))
  87. return 0;
  88. if(p==FirstL(L)){
  89. L->kursor--;
  90. for( int i=p; i<L->kursor; i++)
  91. L->zivotinja[i]=L->zivotinja[i+1];
  92. return 1;
  93. }
  94. else{
  95. L->kursor--;
  96. for( int i=p; i<L->kursor; i++)
  97. L->zivotinja[i]=L->zivotinja[i+1];
  98. }
  99. return 1;
  100. }
  101. lista *InitL(lista *L){
  102. L=new lista;
  103. L->kursor=0;
  104. return L;
  105. }
  106. void VratiL(tzivotinja x,int p,lista *L) {
  107. L->zivotinja[p]=x;
  108. }
  109. void Spoji(lista *L,int i, int k, int j) {
  110. int I=i, J=k+1, K=0;
  111. tzivotinja A,B,*POM = new tzivotinja [j-i+1];
  112.  
  113.  
  114.  
  115. while(I<=k && J<=j){
  116. A=RetreiveL(I,L);
  117. B=RetreiveL(J,L);
  118.  
  119. if(A.cijena < B.cijena) {
  120. POM[K++]=A;
  121. I++;
  122. }
  123.  
  124. else if(A.cijena > B.cijena){
  125. POM[K++]=B;
  126. J++;
  127. }
  128. else if(strcmp(A.ime,B.ime)==1) {
  129. POM[K++]=B;
  130. J++;
  131. }
  132. else {
  133. POM[K++]=A;
  134. I++;
  135. }
  136. }
  137.  
  138. if(I>k) while(J<=j) {
  139. B=RetreiveL(J++,L);
  140. POM[K++] = B;
  141. }
  142.  
  143. else while(I<=k) {
  144. A=RetreiveL(I++,L);
  145. POM[K++] = A;
  146. }
  147.  
  148. for(int I=0;I<=j-i;I++) VratiL(POM[I],i+I,L);
  149. delete [] POM;
  150. }
  151. void Sortiraj(lista *L, int i, int j) {
  152. if(i<j) {
  153. int k=(i+j)/2;
  154. Sortiraj(L,i,k);
  155. Sortiraj(L,k+1,j);
  156. Spoji(L,i,k,j);
  157. }
  158. }
  159. int MSort(lista *L) {
  160. Sortiraj(L,0,EndL(L)-1);
  161. return 1;
  162. }

Report this snippet  

Comments

RSS Icon Subscribe to comments
Posted By: dmacan23 on November 12, 2012

Vidim da si u struct-u datum zapisivao kao 3 zasebna elementa (god,mj,dan), a ja sam radio datum kao polje s 3 elementa i u njih upisivao [0-god, 1-mj, 2-dan] Radio si Merge Sort isto kao i ja u header-u, ali sam ja i ispis napravio u header-u, dok si ti u main-u

You need to login to post a comment.