API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Feb 11th, 2019
64
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 12.41 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include <malloc.h>
  3. #include <assert.h>
  4. #include <memory.h>
  5.  
  6. typedef struct TNode {
  7. char m_Digit;
  8. struct TNode * m_Next;
  9. }TNODE;
  10.  
  11. TNODE * createNode ( char digit, TNODE * next )
  12. {
  13. TNODE * n = (TNODE *) malloc (sizeof ( *n ));
  14. n -> m_Digit = digit;
  15. n -> m_Next = next;
  16. return n;
  17. }
  18.  
  19. void deleteList (TNODE * l)
  20. {
  21. while (l)
  22. {
  23. TNODE * tmp = l -> m_Next;
  24. free (l);
  25. l = tmp;
  26. }
  27. }
  28.  
  29. void initString(char * string, int len) {
  30. for (int i = 0; i < len; ++i) {
  31. string[i] = '\0';
  32. }
  33. }
  34.  
  35. void stringReverse(char * string) {
  36. int size = (int)strlen(string);
  37. char * rev = (char*)malloc(size * sizeof(char));
  38. for (int i = 0; i < size; ++i) {
  39. rev[i] = string[size-i-1];
  40. }
  41. for (int i = 0; i < size; ++i) {
  42. string[i] = rev[i];
  43. }
  44. free(rev);
  45. }
  46.  
  47. char * doubleArraySize(char * string, int * len) {
  48. int prevLen = (*len);
  49. (*len) = (*len) * 2;
  50. char * biggerString = (char*)malloc((*len) * sizeof(char));
  51. for (int i = 0; i < prevLen; ++i) {
  52. biggerString[i] = string[i];
  53. }
  54. for (int j = prevLen; j < (*len); ++j) {
  55. biggerString[j] = '\0';
  56. }
  57. free(string);
  58. return biggerString;
  59. }
  60.  
  61. char * linkToString(TNODE * link, int * length) {
  62. int len = 100;
  63. char * string = (char*)malloc(len * sizeof(char));
  64. initString(string, len);
  65. int counter = 1;
  66. while (link) {
  67. string[counter-1] = link->m_Digit;
  68. if (counter == len) {
  69. string = doubleArraySize(string, &len);
  70. }
  71. counter++;
  72. link = link->m_Next;
  73. }
  74. (*length) = counter;
  75. // char * newString =
  76. stringReverse(string);
  77. // free(string);
  78. return string;
  79. }
  80.  
  81. void maxOfThreeChars(char a, char b, char c, char * maxCandidates) {
  82. if (a == b && b == c) {
  83. return;
  84. }
  85. else if (a == b && c < a) {
  86. maxCandidates[0] = 'a';
  87. maxCandidates[1] = 'b';
  88. maxCandidates[2] = '\0';
  89. }
  90. else if (b == c && a < c) {
  91. maxCandidates[0] = 'b';
  92. maxCandidates[1] = 'c';
  93. maxCandidates[2] = '\0';
  94. }
  95. else if (a == c && b < c) {
  96. maxCandidates[0] = 'a';
  97. maxCandidates[1] = 'c';
  98. maxCandidates[2] = '\0';
  99. }
  100.  
  101. else if (a > b && a > c) {
  102. maxCandidates[0] = 'a';
  103. maxCandidates[1] = '\0';
  104. maxCandidates[2] = '\0';
  105. }
  106. else if (b > a && b > c) {
  107. maxCandidates[0] = 'b';
  108. maxCandidates[1] = '\0';
  109. maxCandidates[2] = '\0';
  110. }
  111. else if (c > a && c > b) {
  112. maxCandidates[0] = 'c';
  113. maxCandidates[1] = '\0';
  114. maxCandidates[2] = '\0';
  115. }
  116. }
  117.  
  118. void maxOfTwoChars(char a, char b, char * maxCandidates) {
  119. if (a == b) {
  120. return;
  121. }
  122. else if (a > b) {
  123. maxCandidates[1] = '\0';
  124. }
  125. else if (b > a) {
  126. maxCandidates[0] = maxCandidates[1];
  127. maxCandidates[1] = '\0';
  128. }
  129. }
  130.  
  131. void minOfThreeChars(char a, char b, char c, char * maxCandidates) {
  132. if (a == b && b == c) {
  133. return;
  134. }
  135. else if (a == b && c > a) {
  136. maxCandidates[0] = 'a';
  137. maxCandidates[1] = 'b';
  138. maxCandidates[2] = '\0';
  139. }
  140. else if (b == c && a > c) {
  141. maxCandidates[0] = 'b';
  142. maxCandidates[1] = 'c';
  143. maxCandidates[2] = '\0';
  144. }
  145. else if (a == c && b > c) {
  146. maxCandidates[0] = 'a';
  147. maxCandidates[1] = 'c';
  148. maxCandidates[2] = '\0';
  149. }
  150.  
  151. else if (a < b && a < c) {
  152. maxCandidates[0] = 'a';
  153. maxCandidates[1] = '\0';
  154. maxCandidates[2] = '\0';
  155. }
  156. else if (b < a && b < c) {
  157. maxCandidates[0] = 'b';
  158. maxCandidates[1] = '\0';
  159. maxCandidates[2] = '\0';
  160. }
  161. else if (c < a && c < b) {
  162. maxCandidates[0] = 'c';
  163. maxCandidates[1] = '\0';
  164. maxCandidates[2] = '\0';
  165. }
  166. }
  167.  
  168. void minOfTwoChars(char a, char b, char * maxCandidates) {
  169. if (a == b) {
  170. return;
  171. }
  172. else if (a < b) {
  173. maxCandidates[1] = '\0';
  174. }
  175. else if (b < a) {
  176. maxCandidates[0] = maxCandidates[1];
  177. maxCandidates[1] = '\0';
  178. }
  179. }
  180.  
  181. int max3(const char * aString, const char * bString, const char * cString, int len) {
  182. // get chars
  183. // compare every digit from most significant to least significant
  184. char a,b,c;
  185. char maxCandidates[4] = "abc";
  186.  
  187. for (int i = 0; i < len; ++i) {
  188. a = aString[i], b = bString[i], c = cString[i];
  189. if (strlen(maxCandidates) == 3) {
  190. maxOfThreeChars(a,b,c,maxCandidates);
  191. }
  192. else if (strcmp(maxCandidates,"ab") == 0) {
  193. maxOfTwoChars(a,b,maxCandidates);
  194. }
  195. else if (strcmp(maxCandidates,"ac") == 0) {
  196. maxOfTwoChars(a,c,maxCandidates);
  197. }
  198. else if (strcmp(maxCandidates,"bc") == 0) {
  199. maxOfTwoChars(b,c,maxCandidates);
  200. }
  201. if (strlen(maxCandidates) == 1) {
  202. break;
  203. }
  204. }
  205. return (maxCandidates[0] - 'a' + 1);
  206. }
  207.  
  208. int min3(const char * aString, const char * bString, const char * cString, int len) {
  209. char a,b,c;
  210. char minCandidates[4] = "abc";
  211.  
  212. for (int i = 0; i < len; ++i) {
  213. a = aString[i], b = bString[i], c = cString[i];
  214. if (strlen(minCandidates) == 3) {
  215. minOfThreeChars(a,b,c,minCandidates);
  216. }
  217. else if (strcmp(minCandidates,"ab") == 0) {
  218. minOfTwoChars(a,b,minCandidates);
  219. }
  220. else if (strcmp(minCandidates,"ac") == 0) {
  221. minOfTwoChars(a,c,minCandidates);
  222. }
  223. else if (strcmp(minCandidates,"bc") == 0) {
  224. minOfTwoChars(b,c,minCandidates);
  225. }
  226. if (strlen(minCandidates) == 1) {
  227. break;
  228. }
  229. }
  230. return (minCandidates[0] - 'a' + 1); // 'a' - 'a' = 0, 0 + 1 = 1
  231. }
  232.  
  233. int max2(char * aString, char * bString) {
  234. char a,b;
  235. char maxCandidates[3] = "ab";
  236. for (int i = 0; i < strlen(aString); ++i) {
  237. a = aString[i], b = bString[i];
  238. maxOfTwoChars(a,b,maxCandidates);
  239. if (strlen(maxCandidates) == 1) {
  240. break;
  241. }
  242. }
  243. return (maxCandidates[0] - 'a' + 1);
  244. }
  245.  
  246.  
  247. TNODE * median3( TNODE * a, TNODE * b, TNODE * c) {
  248. char * aString, * bString, *cString;
  249. int aLength = -1;
  250. int bLength = -2;
  251. int cLength = -3;
  252. aString = linkToString(a, &aLength);
  253. bString = linkToString(b, &bLength);
  254. cString = linkToString(c, &cLength);
  255.  
  256. if (strcmp(aString,bString) == 0 ||
  257. strcmp(bString,cString) == 0 ||
  258. strcmp(aString,cString) == 0) {
  259. free(aString);free(bString);free(cString);return NULL;
  260. }
  261.  
  262. if (aLength == bLength && bLength == cLength) {
  263.  
  264. int min = min3(aString,bString,cString,aLength);
  265. int max = max3(aString,bString,cString,aLength);
  266. if (max != 1 && min != 1) {
  267. free(aString);free(bString);free(cString);return a;
  268. }
  269. if (max != 2 && min != 2) {
  270. free(aString);free(bString);free(cString);return b;
  271. }
  272. if (max != 3 && min != 3) {
  273. free(aString);free(bString);free(cString);return c;
  274. }
  275. }
  276.  
  277. else if (cLength < aLength && aLength < bLength) {
  278. free(aString);free(bString);free(cString);return a;
  279. }
  280. else if (aLength < bLength && bLength < cLength) {
  281. free(aString);free(bString);free(cString);return b;
  282. }
  283. else if (bLength < cLength && cLength < aLength) {
  284. free(aString);free(bString);free(cString);return c;
  285. }
  286.  
  287. else if (aLength == bLength && cLength > bLength) {
  288. int max = max2(aString, bString);
  289. if (max == 1) { free(aString);free(bString);free(cString);return a;}
  290. if (max == 2) { free(aString);free(bString);free(cString);return b;}
  291. }
  292. else if (cLength == bLength && aLength > bLength) {
  293. int max = max2(bString, cString);
  294. if (max == 1) { free(aString);free(bString);free(cString);return b;}
  295. if (max == 2) { free(aString);free(bString);free(cString);return c;}
  296. }
  297. else if (aLength == cLength && bLength > cLength) {
  298. int max = max2(aString, cString);
  299. if (max == 1) { free(aString);free(bString);free(cString);return a;}
  300. if (max == 2) { free(aString);free(bString);free(cString);return c;}
  301. }
  302.  
  303. return a;
  304. }
  305.  
  306. int main() {
  307. TNODE * a, * b,* c;
  308. TNODE * res;
  309. a = createNode('0',
  310. createNode('9',
  311. createNode('1', NULL)));
  312.  
  313. b = createNode('8',
  314. createNode('5',
  315. createNode('2', NULL)));
  316.  
  317. c = createNode('8',
  318. createNode('5',
  319. createNode('1', NULL)));
  320.  
  321. res = median3(a,b,c);
  322. assert( res == a);
  323.  
  324. deleteList(a);
  325. deleteList(b);
  326. deleteList(c);
  327.  
  328. a = createNode('8',
  329. createNode('5',
  330. createNode('5',
  331. createNode('5',
  332. createNode('5',
  333. createNode('5',
  334. createNode('5',
  335. createNode('5',
  336. createNode('5',
  337. createNode('5',
  338. createNode('5',
  339. createNode('5',
  340. createNode('5',
  341. createNode('5',
  342. createNode('5',
  343. createNode('5',
  344. createNode('5',
  345. createNode('5',
  346. createNode('5',
  347. createNode('5',
  348. createNode('2', NULL)))))))))))))))))))));
  349.  
  350. b = createNode('8',
  351. createNode('5',
  352. createNode('5',
  353. createNode('5',
  354. createNode('5',
  355. createNode('5',
  356. createNode('5',
  357. createNode('5',
  358. createNode('5',
  359. createNode('5',
  360. createNode('5',
  361. createNode('5',
  362. createNode('5',
  363. createNode('5',
  364. createNode('5',
  365. createNode('5',
  366. createNode('5',
  367. createNode('5',
  368. createNode('4',
  369. createNode('5',
  370. createNode('2', NULL)))))))))))))))))))));
  371.  
  372. c = createNode('8',
  373. createNode('5',
  374. createNode('5',
  375. createNode('5',
  376. createNode('5',
  377. createNode('5',
  378. createNode('5',
  379. createNode('5',
  380. createNode('5',
  381. createNode('5',
  382. createNode('5',
  383. createNode('5',
  384. createNode('5',
  385. createNode('5',
  386. createNode('5',
  387. createNode('5',
  388. createNode('5',
  389. createNode('5',
  390. createNode('3',
  391. createNode('5',
  392. createNode('2', NULL)))))))))))))))))))));
  393. res = median3(a,b,c);
  394. assert(res == b);
  395. deleteList(a);
  396. deleteList(b);
  397. deleteList(c);
  398.  
  399. a = createNode('1',NULL);
  400. b = createNode('2', createNode('1',NULL));
  401. c = createNode('3',createNode('1',createNode('2',NULL)));
  402. res = median3(a,b,c);
  403. assert(res == b);
  404. deleteList(a);
  405. deleteList(b);
  406. deleteList(c);
  407.  
  408. a = createNode('1',createNode('1',NULL));
  409. b = createNode('1', createNode('1',NULL));
  410. c = createNode('3',createNode('1',createNode('2',NULL)));
  411. res = median3(a,b,c);
  412. assert(res == NULL);
  413. deleteList(a);
  414. deleteList(b);
  415. deleteList(c);
  416.  
  417. a = createNode('1',createNode('1',NULL));
  418. b = createNode('2', createNode('1',NULL));
  419. c = createNode('3',createNode('1',createNode('2',NULL)));
  420. res = median3(a,b,c);
  421. assert(res == b);
  422. deleteList(a);
  423. deleteList(b);
  424. deleteList(c);
  425.  
  426. a = createNode('6',createNode('5',createNode('3',createNode('4',createNode('1',NULL)))));
  427. b = createNode('6',createNode('5',createNode('5',createNode('5',createNode('1',NULL)))));
  428. c = createNode('7',createNode('6',createNode('4',createNode('5',createNode('1',NULL)))));
  429. res = median3(a,b,c);
  430. assert(res == c);
  431. deleteList(a);
  432. deleteList(b);
  433. deleteList(c);
  434.  
  435. a = createNode('6',createNode('5',createNode('3',createNode('4',createNode('1',NULL)))));
  436. b = createNode('5',createNode('5',createNode('5',createNode('5',createNode('1',NULL)))));
  437. c = createNode('7',createNode('6',createNode('4',createNode('5',createNode('1',NULL)))));
  438. res = median3(a,b,c);
  439. assert(res == c);
  440. deleteList(a);
  441. deleteList(b);
  442. deleteList(c);
  443.  
  444. return 0;
  445. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!