Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

bigintII.c

By: a guest on Sep 12th, 2010  |  syntax: C  |  size: 11.43 KB  |  views: 255  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. /*
  2.  * File:   struct integer.c
  3.  * Author: Andrew Levenson
  4.  * Course: COP 3502
  5.  * Professor: Jonathan Cazalas
  6.  * Description: Assignment in using Linked Lists
  7.  * in order to perform bigint addition and subtraction.
  8.  *
  9.  * Created on September 1, 2010, 11:38 AM
  10.  */
  11.  
  12. #include <stdio.h>
  13. #include <stdlib.h>
  14. #include <string.h>
  15.  
  16.  
  17. // Constant Definitions
  18. #define ADD 1
  19. #define SUB 2
  20.  
  21. // Output file
  22. char *fName = "out.txt";
  23. FILE *outFile;
  24.  
  25.  
  26. /*
  27.  * Create a prototype of a single
  28.  * node in the Linked List.
  29.  * Each node will represent a single
  30.  * integer comprising one part of a struct integer.
  31.  */
  32. struct integer
  33. {
  34.     int digit;
  35.  
  36.     struct integer *next;
  37. };
  38.  
  39.  
  40. // Function Prototypes
  41. struct integer* read_integer( char *stringInt );
  42. struct integer* add( struct integer *p, struct integer *q );
  43. struct integer* subtract( struct integer *p, struct integer *q);
  44. struct integer* stripLeadingZeros( struct integer *p );
  45.  
  46. int compare( struct integer *p, struct integer *q );
  47.  
  48. void print( struct integer *p );
  49. void reverse( struct integer **p );
  50.  
  51.  
  52. // Main function
  53. int main( )
  54. {
  55.     //Variable initialization
  56.  
  57.     /*
  58.      * Initialize pointers to the linked lists.
  59.      * One, *head, will always point to the
  60.      * first element, the head, of the list.
  61.      * The other element, *curr, will point to the
  62.      * node currently being accessed, and will be
  63.      * used to traverse the list.
  64.      */
  65.     struct integer* pHead;
  66.     struct integer* qHead;
  67.     struct integer* tHead; // Used to contain the total
  68.  
  69.     int numOps, oper, i;
  70.     char *fileName = "input.txt";
  71.     char bigintstr[200];
  72.     FILE *inputFile;
  73.  
  74.     // Open output file
  75.     outFile = fopen(fName, "a+");
  76.  
  77.  
  78.     // Open up the input file for reading
  79.     inputFile = fopen(fileName, "r");
  80.  
  81.     // Read in the number of operations to be performed
  82.     fscanf(inputFile, "%d", &numOps);
  83.  
  84.     /*
  85.      * For each operation that must be performed,
  86.      * construct a linked list for each of the
  87.      * struct integers in the file. Then, perform the operation
  88.      * indicated by the digit preceding them.
  89.      */
  90.     for( i = 0; i < numOps; i++ )
  91.     {
  92.         // Read in the number that dictates operation
  93.         fscanf(inputFile, "%d", &oper);
  94.  
  95.         // Read in the first struct integer into a string
  96.         fscanf(inputFile, "%s", bigintstr);
  97.  
  98.         /*
  99.          * Pass the struct integer string to read_integer()
  100.          * in order to construct a linked list out of it.
  101.          */
  102.         pHead = read_integer( bigintstr );
  103.  
  104.         // Read in second struct integer into a string
  105.         fscanf(inputFile, "%s", bigintstr);
  106.  
  107.         /*
  108.          * Pass the struct integer str to read_integer()
  109.          * in order to construct a linked list out of it.
  110.          */
  111.         qHead = read_integer( bigintstr );
  112.  
  113.         /*
  114.          * Depending on the operation to be performed,
  115.          * call the corresponding function.
  116.          */
  117.         if( oper == ADD )
  118.         {
  119.                 tHead = add( pHead, qHead );
  120.                 print( pHead );
  121.                         fprintf(outFile, " + ");
  122.                         print( qHead );
  123.                         fprintf(outFile, " = ");
  124.                         reverse( &tHead );
  125.                         print( tHead );
  126.                         fprintf(outFile, "\n");
  127.         }
  128.         else if( oper == SUB )
  129.         {
  130.                         /*
  131.                          * Before you can subtract, you must
  132.                      * compare the two bigints being subtracted.
  133.                          * Because we are only dealing with
  134.                          * positive integers, we must first
  135.                          * determine which is the larger of the
  136.                          * two operands. This operand becomes
  137.                          * the bigint from which we subtract.
  138.                          */
  139.                         if( compare( pHead, qHead ) > 0 ) // p > q
  140.                         {
  141.                                 tHead = subtract( pHead, qHead );
  142.                                 print( pHead );
  143.                                 fprintf(outFile, " - ");
  144.                                 print( qHead );
  145.                                 fprintf(outFile, " = ");
  146.                                 reverse( &tHead );
  147.                                 print( tHead );
  148.                                 fprintf(outFile, "\n");
  149.                         }
  150.                         else if( compare( pHead, qHead ) == 0 ) // p == q
  151.                         {
  152.                                 tHead->digit = 0;
  153.                                 tHead->next = NULL;
  154.                                
  155.                                 print( pHead );
  156.                                 fprintf(outFile, " - ");
  157.                                 print( qHead );
  158.                                 fprintf(outFile, " = ");
  159.                                 reverse( &tHead );
  160.                                 print( tHead );
  161.                                 fprintf(outFile, "\n");
  162.                         }
  163.                         else // p < q
  164.                         {
  165.                                 tHead = subtract( qHead, pHead );
  166.                                
  167.                                 print( qHead );
  168.                                 fprintf(outFile, " - ");
  169.                                 print( pHead );
  170.                                 fprintf(outFile, " = ");
  171.                                 reverse( &tHead );
  172.                                 print( tHead );
  173.                                 fprintf(outFile, "\n");
  174.                         }
  175.          }
  176.     }
  177.     fclose(inputFile);
  178.     fclose(outFile);
  179.  
  180.     //system(PAUSE);
  181.     return 0;
  182. }
  183.  
  184.  
  185. // Function Definitions
  186.  
  187. /*
  188.  * Function read_integer
  189.  *
  190.  * @Parameter CHAR* stringInt
  191.  *
  192.  * Parameter contains a string representing a struct integer.
  193.  * Tokenizes the string by each character, converts each char
  194.  * into an integer, and constructs a backwards linked list out
  195.  * of the digits.
  196.  *
  197.  * @Return STRUCT* Integer
  198.  */
  199. struct integer* read_integer( char* stringInt )
  200. {
  201.     int i, n;
  202.     struct integer *curr, *head;
  203.    
  204.     int numDigits = strlen( stringInt ); // Find the length of the struct integer
  205.     head = NULL;
  206.  
  207.     for( i = 0; i < numDigits; i++ )
  208.     {
  209.         n = stringInt[i] - '0'; // Convert char to an integer
  210.  
  211.         curr = (struct integer *) malloc (sizeof( struct integer )); // Allocate memory for node
  212.         curr->digit = n; // Digit of current node is assigned to n
  213.         curr->next = head; // Move to the next node in the list.
  214.         head = curr; // Move head up to the front of the list.
  215.     }
  216.        
  217.         return head; // Return a pointer to the first node in the list.
  218. }
  219.  
  220. /*
  221.  * Function reverse
  222.  *
  223.  * @Parameter STRUCT** Integer
  224.  *
  225.  * Reverses a linked list by creating a new
  226.  * reversed linked list and then returning the
  227.  * head of the newly formed list.
  228.  */
  229. void reverse (struct integer **p)
  230. {
  231.         struct integer *oldList = *p;
  232.         struct integer *newList = NULL;
  233.        
  234.         while( oldList )
  235.         {
  236.                 struct integer *oldNext = oldList->next;
  237.                 oldList->next = newList;
  238.                 newList = oldList;
  239.                
  240.                 oldList = oldNext;
  241.         }
  242.        
  243.         *p = newList;
  244. }
  245.  
  246. /*
  247.  * Function print
  248.  *
  249.  * @Parameter STRUCT* Integer
  250.  *
  251.  * Given a linked list, will traverse through
  252.  * the nodes and print out, one at a time,
  253.  * the digits comprising the struct integer that the
  254.  * linked list represents.
  255.  *
  256.  * TODO: Print to file
  257.  */
  258. void print( struct integer *p )
  259. {  
  260.         struct integer *curr = p;
  261.        
  262.         curr = stripLeadingZeros( curr );
  263.  
  264.         reverse( &curr );
  265.        
  266.         while( curr )
  267.     {
  268.         fprintf(outFile, "%d", curr->digit);
  269.         curr = curr->next;
  270.     }
  271.        
  272. }
  273.  
  274. /*
  275.  * Function add
  276.  *
  277.  * @Paramater STRUCT* Integer
  278.  * @Parameter STRUCT* Integer
  279.  *
  280.  * Takes two linked lists representing
  281.  * big integers stored in reversed order,
  282.  * and returns a linked list containing
  283.  * the sum of the two integers.
  284.  *
  285.  * @Return STRUCT* Integer
  286.  *
  287.  * TODO Comment me
  288.  */
  289. struct integer* add( struct integer *p, struct integer *q )
  290. {
  291.     int carry = 0;
  292.  
  293.     struct integer *sHead, *sCurr;
  294.     struct integer *pHead, *qHead;
  295.    
  296.     pHead = p;
  297.     qHead = q;
  298.    
  299.     sHead = NULL;
  300.  
  301.     while( p )
  302.     {
  303.         sCurr = ( struct integer* ) malloc (sizeof(struct integer));
  304.         sCurr->digit = p->digit + q->digit + carry;
  305.         sCurr->next = sHead;
  306.         sHead = sCurr;
  307.  
  308.         carry = 0;
  309.  
  310.         /*
  311.          * If the current digits sum to greater than 9,
  312.          * create a carry value and replace the current
  313.          * value with value mod 10.
  314.          */
  315.         if( sCurr->digit > 9 )
  316.         {
  317.             carry = 1;
  318.             sCurr->digit = sCurr->digit % 10;
  319.         }
  320.  
  321.         /*
  322.          * If the most significant digits of the numbers
  323.          * sum to 10 or greater, create an extra node
  324.          * at the end of the sum list and assign it the
  325.          * value of 1.
  326.          */
  327.         if( carry == 1 && sCurr->next == NULL )
  328.         {
  329.             struct integer *sCarry = ( struct integer* ) malloc (sizeof(struct integer));
  330.             sCarry->digit = 1;
  331.             sCarry->next = NULL;
  332.             reverse( &sCurr );
  333.             sCurr->next = sCarry;
  334.             reverse( &sCurr );
  335.         }
  336.  
  337.         p = p->next;
  338.         if( q->next ) q = q->next;
  339.         else q->digit = 0;
  340.     }
  341.  
  342.     return sHead;
  343. }
  344.  
  345. /*
  346.  * Function subtract
  347.  *
  348.  * @Parameter STRUCT* Integer
  349.  * @Parameter STRUCT* Integer
  350.  *
  351.  * Takes two linked lists representing struct integers.
  352.  * Traverses through the lists, subtracting each
  353.  * digits from the subsequent nodes to form a new
  354.  * struct integer, and then returns the newly formed
  355.  * linked list.
  356.  *
  357.  * @Return STRUCT* Integer
  358.  *
  359.  * TODO Comment me
  360.  */
  361. struct integer* subtract( struct integer *p, struct integer *q )
  362. {
  363.     int borrow = 0;
  364.  
  365.     struct integer *dHead, *dCurr;
  366.     struct integer *pHead, *qHead;
  367.  
  368.     pHead = p;
  369.     qHead = q;
  370.  
  371.     dHead = NULL;
  372.  
  373.     while( p )
  374.     {
  375.         dCurr = (struct integer*) malloc (sizeof(struct integer));
  376.         if( q )
  377.         {
  378.                 dCurr->digit = p->digit - q->digit - borrow;
  379.         }
  380.         else
  381.         {
  382.                 dCurr->digit = p->digit - borrow;
  383.         }
  384.         dCurr->next = dHead;
  385.         dHead = dCurr;
  386.  
  387.         if( dCurr->digit < 0 )
  388.         {
  389.             dCurr->digit += 10;
  390.             borrow = 1;
  391.         }
  392.  
  393.         if( dCurr->next == NULL && borrow == 1 )
  394.         {
  395.             struct integer *dBorrow = (struct integer*) malloc (sizeof(struct integer));
  396.             dBorrow->digit = -1;
  397.             dBorrow->next = NULL;
  398.             dCurr->next = dBorrow;
  399.         }
  400.  
  401.         p = p->next;
  402.         if( q->next) q = q->next;
  403.         else q->digit = 0;
  404.     }
  405.  
  406.     return dHead;
  407. }
  408.  
  409. /*
  410.  * Function compare
  411.  *
  412.  * @Parameter STRUCT* Integer
  413.  * @Parameter STRUCT* Integer
  414.  *
  415.  * Takes in two linked lists representing struct integers.
  416.  * Traverses the lists one at a time, comparing the
  417.  * digits.
  418.  *
  419.  * Case: p < q
  420.  * @Return -1
  421.  *
  422.  * Case: p == q
  423.  * @Return 0
  424.  *
  425.  * Case: p > q
  426.  * @Return 1
  427.  *
  428.  * TODO Comment me
  429.  */
  430. int compare( struct integer *p, struct integer *q )
  431. {
  432.     struct integer *pHead, *qHead;
  433.     int comp = 0, pCount = 0, qCount = 0;
  434.  
  435.     pHead = p;
  436.     qHead = q;
  437.    
  438.     // Get the length of p
  439.     while( p )
  440.     {
  441.         pCount++;
  442.         p = p->next;
  443.     }
  444.    
  445.     // Get the length of q
  446.     while( q )
  447.     {
  448.         qCount++;
  449.         q = q->next;
  450.     }
  451.    
  452.     if( pCount > qCount ) // p > q
  453.     {
  454.         return 1;
  455.     }
  456.     if( pCount < qCount ) // p < q
  457.     {
  458.         return -1;
  459.     }
  460.  
  461.     while( p )
  462.     {
  463.                 if( p->digit > q->digit )
  464.                 {
  465.                         comp = 1;
  466.                 }
  467.  
  468.                 if( p->digit < q->digit )
  469.                 {
  470.                         comp = -1;
  471.                 }
  472.        
  473.         p = p->next;
  474.         if( q->next ) q = q->next;
  475.         else q->digit = 0;
  476.     }
  477.  
  478.     return comp;
  479. }
  480.  
  481. /*
  482.  * Function stripLeadingZeros
  483.  *
  484.  * @Parameter STRUCT* Integer
  485.  *
  486.  * Step through a linked list, recursively unlinking
  487.  * all leading zeros and making the first
  488.  * non-zero integer the head of the list.
  489.  *
  490.  * @Return STRUCT* Integer
  491.  */
  492. struct integer* stripLeadingZeros( struct integer *p )
  493. {
  494.         reverse( &p );
  495.        
  496.     // Are we at the end of the list?
  497.     if( p == NULL ) return NULL;
  498.  
  499.     // Are we deleting the current node?
  500.     //Also it should not strip last 0
  501.     if( p->digit == 0 && p->next != NULL)
  502.     {
  503.         struct integer *pNext;
  504.  
  505.         pNext = p->next;
  506.  
  507.         // Deallocate the node
  508.         free( p );
  509.  
  510.         // Try to strip zeros on pointer to the next node and return that pointer
  511.         return stripLeadingZeros(pNext);
  512.     }
  513.    
  514.     reverse( &p );
  515.    
  516.     return p;
  517. }