Posted By

mnovosel2 on 11/11/12


Tagged

sort merge lista pokazivac Strukture podataka ATP


Versions (?)

Strukture podataka-Pokazivaci


 / Published in: C++
 

Header koji sadrži sve funkcije koje se mogu izvesti nad listom implementirane pomocu pokazivaca. U headeru se jos nalazi i Merge sort algoritam.

  1. #include<iostream>
  2. using namespace std;
  3. struct zivotinja{
  4. int sifra;
  5. char vrsta[35];
  6. char naziv[35];
  7. float cijena;
  8. int datum[3];
  9. };
  10. struct Lista_zapis{
  11. zivotinja vrijednost;
  12. Lista_zapis *sljedeci;
  13. };
  14. typedef Lista_zapis *element;
  15. typedef Lista_zapis lista;
  16. element EndL(lista *L){
  17. return 0;
  18. }
  19. element FirstL(lista *L){
  20. if(L->sljedeci==NULL) return EndL(L);
  21. else
  22. return L->sljedeci;
  23. }
  24. lista *InitL(lista *L){
  25. L=new lista;
  26. L->sljedeci=NULL;
  27. return L;
  28. }
  29. element PreviousL(element p, lista *L){
  30. if(p==FirstL(L)) return 0;
  31. if(p==EndL(L)){
  32. while(L->sljedeci)
  33. L=L->sljedeci;
  34. }
  35. else{
  36. while(p!=L->sljedeci)
  37. L=L->sljedeci;
  38. }
  39. return L;
  40. }
  41. zivotinja RetreiveL(element p, lista *L){
  42. return p->vrijednost;
  43. }
  44. int InsertL(zivotinja x, lista *p, lista *L){
  45. lista *novi;
  46. if(p>L->sljedeci || p<0) return 0;
  47. if(p==EndL(L)){
  48. while(L->sljedeci)
  49. L=L->sljedeci;
  50. novi=new lista;
  51. L->sljedeci=novi;
  52. novi->sljedeci=NULL;
  53. novi->vrijednost=x;
  54. return 1;
  55. }
  56. else{
  57. p=PreviousL(p,L);
  58. novi=new lista;
  59. novi->sljedeci=L->sljedeci;
  60. p->sljedeci=novi;
  61. novi->vrijednost=x;
  62. return 1;
  63. }
  64. }
  65. element NextL(element p, lista *L){
  66. if(p->sljedeci==NULL) return EndL(L);
  67. if(p==EndL(L)) return 0;
  68. else{
  69. return p->sljedeci;
  70. }
  71. }
  72. int DeleteL(element p, lista *L){
  73. element prethodni, tekuci;
  74. tekuci=p;
  75. if(tekuci==EndL(L))return 0;
  76. if(p==FirstL(L)){
  77. L->sljedeci=tekuci->sljedeci;
  78. delete tekuci;
  79. return 1;
  80. }
  81. else{
  82. prethodni=PreviousL(tekuci,L);
  83. prethodni->sljedeci=tekuci->sljedeci;
  84. delete tekuci;
  85. return 1;
  86. }
  87. return 0;
  88. }
  89.  
  90.  
  91. element LocateL(zivotinja x, lista *L){
  92. element pozicija=EndL(L);
  93. pozicija=PreviousL(pozicija,L);
  94. if(strlen(x.naziv)>0){
  95. if(EndL(L)!=FirstL(L)){
  96. while(5){
  97. zivotinja trenutni=RetreiveL(pozicija,L);
  98. if(strcmp(x.naziv,trenutni.naziv)==0)
  99. return pozicija;
  100. if(pozicija==FirstL(L))break;
  101. pozicija=PreviousL(pozicija,L);
  102. }
  103. }}
  104. if(strlen(x.vrsta)>0){
  105. if(EndL(L)!=FirstL(L)){
  106. while(5){
  107. zivotinja trenutni=RetreiveL(pozicija,L);
  108. if(strcmp(x.vrsta,trenutni.vrsta)==0)
  109. return pozicija;
  110. if(pozicija==FirstL(L))break;
  111. pozicija=PreviousL(pozicija,L);
  112. }
  113. }}
  114. return EndL(L);
  115. }
  116. element DeleteAll(lista *L){
  117. element trenutni,prijasnji;
  118. prijasnji=L;
  119. trenutni=L->sljedeci;
  120. while(trenutni){
  121. delete prijasnji;
  122. prijasnji=trenutni;
  123. trenutni=trenutni->sljedeci;
  124. }
  125. delete prijasnji;
  126. L=NULL;
  127. return NULL;
  128. }
  129. void Merge(zivotinja polje[],int i, int k, int j){
  130. int beg=i, sec=k+1, br=0, vel=j-i+1;
  131. zivotinja *pomocno=new zivotinja[j-i+1];
  132. while(beg<=k && sec<=j){
  133. if(polje[beg].cijena>polje[sec].cijena)
  134. pomocno[br++]=polje[beg++];
  135. else if(polje[beg].cijena<polje[sec].cijena)
  136. pomocno[br++]=polje[sec++];
  137. if(polje[beg].cijena==polje[sec].cijena){
  138. if(strcmp(polje[beg].naziv,polje[sec].naziv)==1)
  139. pomocno[br++]=polje[beg++];
  140. else
  141. pomocno[br++]=polje[sec++];
  142.  
  143. }
  144. }
  145. while(beg<=k)
  146. pomocno[br++]=polje[beg++];
  147. while(sec<=j)
  148. pomocno[br++]=polje[sec++];
  149. for(int I=0;I<vel;I++)
  150. polje[i+I]=pomocno[I];
  151. delete []pomocno;
  152.  
  153. }
  154. void Rec(zivotinja polje[],int i, int j){
  155. int middle;
  156. if(i<j){
  157. middle=(i+j)/2;
  158. Rec(polje,i,middle);
  159. Rec(polje,middle+1,j);
  160. Merge(polje,i,middle,j);
  161. }
  162.  
  163. }
  164. void copy(zivotinja polje[],int velicina){
  165. element sortirana=InitL(sortirana);
  166. element novi,zadnji;
  167. zadnji=sortirana;
  168. for(int i=0; i<velicina;i++){
  169. while(zadnji->sljedeci)
  170. zadnji=zadnji->sljedeci;
  171. novi=new lista;
  172. zadnji->sljedeci=novi;
  173. novi->sljedeci=NULL;
  174. novi->vrijednost.sifra=polje[i].sifra;
  175. strcpy(novi->vrijednost.naziv,polje[i].naziv);
  176. novi->vrijednost.datum[0]=polje[i].datum[0];
  177. novi->vrijednost.datum[1]=polje[i].datum[1];
  178. novi->vrijednost.datum[2]=polje[i].datum[2];
  179. strcpy(novi->vrijednost.vrsta,polje[i].vrsta);
  180. novi->vrijednost.cijena=polje[i].cijena;
  181. cout<<"Sifra "<<novi->vrijednost.sifra<<endl;
  182. cout<<"Naziv "<<novi->vrijednost.naziv<<endl;
  183. cout<<"Cijena "<<novi->vrijednost.cijena<<endl;
  184. cout<<"Vrsta "<<novi->vrijednost.vrsta<<endl;
  185. cout<<"Datum "<<novi->vrijednost.datum[0]<<"."<<novi->vrijednost.datum[1]<<"."<<novi->vrijednost.datum[2]<<"."<<endl;
  186. cout<<endl;
  187.  
  188. }
  189. }
  190. void MSort(lista *L,element i, element j){
  191. if(FirstL(L)!=EndL(L)){
  192. int velicina=0,br=0;
  193. element zadnji;
  194. zadnji=L;
  195. while(zadnji->sljedeci){
  196. zadnji=zadnji->sljedeci;
  197. velicina++;
  198. }
  199. zivotinja *pomocno=new zivotinja[velicina];
  200. element lokacija=L->sljedeci;
  201. while(lokacija){
  202. pomocno[br++]=RetreiveL(lokacija,L);
  203. lokacija=lokacija->sljedeci;
  204.  
  205. }
  206. Rec(pomocno,0,velicina-1);
  207. copy(pomocno,velicina);
  208. }
  209. else
  210. cout<<"Lista ne postoji ili je prazna "<<endl;
  211. }

Report this snippet  

You need to login to post a comment.