SHARE
TWEET

Untitled

a guest Feb 11th, 2019 55 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
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
 
Top