Posted By

markoaleric on 11/12/12


Tagged

pointer pokazivac implementacija msort


Versions (?)

Zadatak 1 lista_pokazivac.h


 / Published in: C++
 

Header lista_pokazivac.h, implementacija liste pomoću pokazivača

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

Report this snippet  

You need to login to post a comment.