Advertisement
Guest User

Untitled

a guest
Nov 26th, 2015
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.84 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define inf 1 << 29
  4.  
  5. typedef int elementtype;
  6.  
  7. typedef struct celltag {
  8. elementtype element;
  9. struct celltag* next;
  10. } celltype;
  11.  
  12. typedef celltype* List;
  13. typedef celltype* position;
  14.  
  15.  
  16. position LiEnd( List L ) { // vraca pokazivac na zadnju element liste
  17. position p=L;
  18. while ( p->next != NULL )
  19. p = p->next;
  20. return p;
  21. }
  22.  
  23. position LiMakeNull( List *Lp ) { //pretvara listu u praznu listu i vraca pokazivac na zadnji element
  24. *Lp = ( celltype* )malloc( sizeof(celltype) );
  25. (*Lp)->next = NULL;
  26. return( *Lp );
  27. }
  28.  
  29. void LiInsert( elementtype x, position p, List *L ) { //ubacuje element iza pozicije p
  30. position temp = p->next;
  31. p->next = ( celltype* ) malloc( sizeof(celltype) );
  32. p->next->element = x;
  33. p->next->next = temp;
  34. }
  35.  
  36. void LiDelete( position p, List *L ) { //briše element iza p
  37. position temp = p->next;
  38. p->next = p->next->next;
  39. free( temp );
  40. }
  41.  
  42. position LiFirst( List L ){
  43. return L;
  44. }
  45.  
  46. position LiNext( position p, List L ) {
  47. return p->next;
  48. }
  49.  
  50. position LiPrevious( position p, List L ) {
  51. position temp = L;
  52. while ( temp->next != p )
  53. temp->next = temp->next->next;
  54. return temp;
  55. }
  56.  
  57. elementtype LiRetrive( position p, List L ) {
  58. return p->next->element;
  59. }
  60.  
  61. void ispisi(List l) {
  62. position temp = LiFirst(l);
  63. while (LiNext(temp, l) != NULL) {
  64. printf("%d ", LiRetrive(temp, l));
  65. temp = LiNext(temp, l);
  66. }
  67. }
  68.  
  69. int odrediVelicinu(List l) {
  70. int ret = 0;
  71. position temp = LiFirst(l);
  72. while (LiNext(temp, l) != NULL) {
  73. ret++;
  74. temp = LiNext(temp, l);
  75. }
  76. return ret;
  77. }
  78.  
  79.  
  80. List Listcopy(List l1, int vel1, List l2, int vel2, List *nova) {
  81.  
  82. position prvi = LiFirst(l1);
  83. position drugi = LiFirst(l2);
  84. List ret;
  85. LiMakeNull(&ret);
  86.  
  87. while (prvi != LiEnd(l1) || drugi != LiEnd(l2)) {
  88. if (prvi == LiEnd(l1)) {
  89. LiInsert(LiRetrive(drugi, l2), LiEnd(ret), &ret);
  90. drugi = LiNext(drugi, l2);
  91. }
  92. else if (drugi == LiEnd(l2)) {
  93. LiInsert(LiRetrive(prvi, l1), LiEnd(ret), &ret);
  94. prvi = LiNext(prvi, l1);
  95. }
  96. else {
  97. int broj1 = LiRetrive(prvi, l1);
  98. int broj2 = LiRetrive(drugi, l2);
  99. if (broj1 < broj2) {
  100. LiInsert(broj1, LiEnd(ret), &ret);
  101. prvi = LiNext(prvi, l1);
  102. }
  103. else {
  104. LiInsert(broj2, LiEnd(ret), &ret);
  105. drugi = LiNext(drugi, l2);
  106. }
  107. }
  108. }
  109.  
  110. LiMakeNull(nova);
  111.  
  112. position temp = LiFirst(ret);
  113. while (LiNext(temp, ret) != NULL) {
  114. LiInsert(LiRetrive(temp, ret), LiEnd(*nova), nova);
  115. temp = LiNext(temp, ret);
  116. }
  117. }
  118.  
  119.  
  120.  
  121. int main (void) {
  122.  
  123. int n, i, a, oznaka1, oznaka2;
  124. int jesamUzeo[20];
  125. int velicina[20];
  126. int broj[20];
  127.  
  128. List l[20];
  129.  
  130. scanf("%d", &n);
  131.  
  132. for (i=0; i<2*n; ++i) {
  133. LiMakeNull(&l[i]);
  134. jesamUzeo[i] = -1;
  135. velicina[i] = 0;
  136. }
  137.  
  138. for (i=0; i<n; ++i) {
  139. jesamUzeo[i] = 0;
  140. scanf ("%d", &a);
  141. while (a != -1) {
  142. velicina[i]++;
  143. LiInsert(a, LiEnd(l[i]), &l[i]);
  144. scanf("%d", &a);
  145. }
  146. }
  147.  
  148. int qq, j;
  149. for (qq=0; qq<n-1; ++qq) {
  150.  
  151. int zadnji = 1;
  152. for (i = 0; i < n; ++i) {
  153. if (jesamUzeo[i] == 0) {
  154. printf("L%d: ", zadnji, velicina[i]);
  155. ispisi(l[i]);
  156. printf("\n");
  157. broj[i] = zadnji;
  158. zadnji++;
  159. }
  160. }
  161.  
  162. int mini1 = inf, mini2=inf;
  163. int broj1=-1, broj2=-1;
  164.  
  165. for (i = 0; i < n; ++i) {
  166. if (jesamUzeo[i] == 0) {
  167. if (mini1 > velicina[i]) {
  168. mini1 = velicina[i];
  169. broj1 = i;
  170. oznaka1 = broj[i];
  171. }
  172. }
  173. }
  174.  
  175. for (i = 0; i < n; ++i) {
  176. if (jesamUzeo[i] == 0) {
  177. if (mini2 > velicina[i] && i != broj1) {
  178. mini2 = velicina[i];
  179. broj2 = i;
  180. oznaka2 = broj[i];
  181. }
  182. }
  183. }
  184.  
  185. printf("Spajam L%d i L%d\n", oznaka1 < oznaka2 ? oznaka1 : oznaka2, oznaka1 < oznaka2 ? oznaka2 : oznaka1);
  186. Listcopy(l[broj1 < broj2 ? broj1 : broj2], velicina[broj1 < broj2 ? broj1 : broj2], l[broj1 >= broj2 ? broj1 : broj2], velicina[broj1 >= broj2 ? broj1 : broj2], &l[broj1 < broj2 ? broj1 : broj2]);
  187. velicina[broj1 < broj2 ? broj1 : broj2] = odrediVelicinu(l[broj1 < broj2 ? broj1 : broj2]);
  188. jesamUzeo[broj1 < broj2 ? broj2 : broj1] = 1;
  189. }
  190.  
  191. printf("L1: "); ispisi(l[0]); printf("\n");
  192.  
  193. return 0;
  194. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement