Bigint 2 Program (Linked List Version)

////////////////////////////////////////////////////////////////////////////////
///
///  \file bigint2.c
///  \brief Adds or subtracts very large numbers from a formatted file using
///         linked lists, and outputs the result to a file.
///
///  <br>Author(s): Nicholas Guthrie
///  <br>Created: 06 February 2011
///  <br>Email: nickguthrie@knights.ucf.edu
///  <br>Web: http://nickguthrie.com
///  <br>Title: Big Integers (Linked List Version)
///  <br>Course: COP3502C  Computer Science I
///  <br> Class #: 16173
///  <br>Section #: 0001
///
///  THIS SOFTWARE IS PROVIDED BY THE NICHOLAS GUTHRIE''AS IS'' AND ANY EXPRESS
///  OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
///  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
///  NO EVENT SHALL UCF BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
///  EXEMPLARY,OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 
///  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
///  OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
///  WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
///  OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 
///  ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
///  
////////////////////////////////////////////////////////////////////////////////

# define _CRT_SECURE_NO_WARNINGS 1

////////////////////
//    Includes    //
////////////////////
#include<stdio.h>
#include<stdlib.h> //necessary for malloc
#include<string.h>


////////////////////
//   Structures   //
////////////////////
struct integer 
{
  int digits;		/**< value of digit */
  struct integer *next;	/**< pointer to next digit */

};


/////////////////////////
// Function Prototypes //
/////////////////////////
struct integer* convert_integer(char* stringInt);
void print(FILE *ntw, struct integer *p);
struct integer* add(struct integer *p, struct integer *q);
struct integer* subtract(struct integer *p, struct integer *q);
int compare(struct integer *p, struct integer *q);

struct integer* addToFront(struct integer *list, int value);
struct integer* addToEnd(struct integer *list, int value);
struct integer* delZero(struct integer *list);

void freeInteger(struct integer *ptr);


////////////////////
//      Main      //
////////////////////
int main(){
  /////////////////
  //  Variables  //
  /////////////////
  FILE *input, *output;	/**< input & output streams */
  char itemp&#91;201&#93;;		/**< number collection */
  int i, j;			/**< navigation */
  int repeat;		/**< number of equations in file */
  int operation;		/**< stores +/- as int, +=1, -=2 */
  char op;			/**< stores +/- as char */
  int reverse;		/**< true if #s should reverse for printing */
  int big, small;		/**< used as input parameters */


  ////////////////////
  // Initilizations //
  ////////////////////
  struct integer * data&#91;3&#93;;

  
  ////////////////////
  //    File I/O    //
  ////////////////////
  input = fopen ("bigint.txt", "r");

  //file open error checking
  if(input == NULL)
    {
      printf("File not Found, Press ENTER to exit\n");
      getchar();
      return 0;
    }
  output = fopen("out.txt", "w");
  
  //scan first int in file to determine number of equations to solve
  fscanf(input, "%d", &repeat);
  for(i = 0; i<repeat; i++)
    {
      fscanf(input, "%d", &operation); //collect operation (+/-)

      //store +/- based on input
      if(operation == 2)
	op = '-';
      else
	op = '+';

      //collect big numbers
      for(j = 0; j<2; j++)
	{
	  fscanf(input, "%s", itemp); //collect big numer as string
	  data&#91;j&#93; = convert_integer(itemp); //convert big number string to ints
	}

      //determine which file is bigger & configure flag reverse if necessary
      if(compare(data&#91;0&#93;,data&#91;1&#93;) == -1)
	{
	  big = 1;
	  small = 0;
	  reverse = 1;
	}
      //for adding keep the numbers as they are in the file
      else
	{
	  big = 0;
	  small = 1;
	  reverse = 0;
     }

      //addition
      if(operation == 1)
	{
	  data&#91;2&#93; = add(data&#91;big&#93;,data&#91;small&#93;);
	       
	  //prepare for printing
	  if(reverse == 1)
	    {
	      big = 0;
	      small = 1;
	    }
	}
      
      //subtraction
      else if(operation == 2)
	data&#91;2&#93; = subtract(data&#91;big&#93;,data&#91;small&#93;);
      
      ////////////////////
      // Print to File  //
      ////////////////////
      print(output, data&#91;big&#93;);
      fprintf(output, " %c ", op);
      print(output, data&#91;small&#93;);
      fprintf(output, " = ");
      print(output, data&#91;2&#93;);
      fprintf(output, "\n");

      //free memory
      for(j = 0; j<3; j++)
	{
	  freeInteger(data&#91;j&#93;);
	}
      
    }
     
  //close files and exit program
  fclose(input);
  fclose(output);
  return 0;
}

////////////////////////////////////////////////////////////////////////////////
///
///  \brief frees the memory allocated in an integer structure
///
///  \param&#91;in&#93; pointer to a integer structure
///
///  \return void
///
////////////////////////////////////////////////////////////////////////////////
void freeInteger(struct integer *ptr)
{
  struct integer *temp = ptr;

  if (temp) {
    freeInteger(temp->next);
    free(ptr);
  }
}

////////////////////////////////////////////////////////////////////////////////
///
///  \brief adds a number to the front of a dynamic list
///
///  \param[in] pointer pointer to an integer structure
///  \param[in] value to add to beginning of list
///
///  \return pointer to a struct Integer
///
////////////////////////////////////////////////////////////////////////////////
struct integer* addToFront(struct integer *list, int value)
{
  // Create the new node and store argument date in it
  struct integer * pNew = (struct integer *) malloc(sizeof(struct integer));
  pNew->digits = value;
  pNew->next = NULL;
     



  //IF the list is empty, set the original head ptr to point to the new node
  if(list == NULL)
    {
      list = pNew;
    }
  else
    {
      //point the new node to wherever the head pointer points to
      pNew->next = list;
	  
      //point the head pointer to the new node
      list = pNew;
    }
  return list;
}


////////////////////////////////////////////////////////////////////////////////
///
///  \brief adds a number to the end of a dynamic list
///
///  \param[in] pointer pointer to an integer structure
///  \param[in] value to add to end of list
///
///  \return pointer to a struct Integer
///
////////////////////////////////////////////////////////////////////////////////
struct integer* addToEnd(struct integer *list, int value)
{
  struct integer *help_ptr = list; /**< helper pointer for navigation */
  struct integer *pNew = (struct integer *) malloc(sizeof(struct integer));

  pNew->digits = value;
  pNew->next = NULL;

  //if the list is empty, pNew becomes the first node
  if (list == NULL)
    {
      return pNew;
    }
     
  //otherwise, traverse the list and arrive at the last node
  while (help_ptr->next !=NULL)
    {
      help_ptr = help_ptr->next;
    }

  //make the last node point to the insertion node
  help_ptr->next = pNew;

  return list;
}


////////////////////////////////////////////////////////////////////////////////
///
///  \brief deletes all the leading zeros in a struct Integer
///
///  \param[in] pointer pointer to a struct Integer
///
///  \return pointer to a struct Integer
///
////////////////////////////////////////////////////////////////////////////////
struct integer* delZero(struct integer *list)
{
  struct integer *help_ptr, *node2delZero;
  help_ptr = list;
  while(help_ptr->next != NULL)
    {
      if(help_ptr->next->next == NULL && help_ptr->next->digits == 0)
	{
	  node2delZero = help_ptr->next;
	  help_ptr->next = NULL;
	  free(node2delZero);
	  if(help_ptr->digits == 0)
	    {
	      return delZero(list);
	    }
	}
      else{
	help_ptr = help_ptr->next;
      }
    }
  return list;
}


////////////////////////////////////////////////////////////////////////////////
///
///  \brief reads the digits of the large integer, character by character, and
///         converts them into integers.
///
///  \param[in] string with only digits, does not start with 0, < 200 char long
///
///  \return pointer to a struct Integer
///
////////////////////////////////////////////////////////////////////////////////
struct integer* convert_integer(char* stringInt)
{
  struct integer* data = NULL;

  //navigation variables
  int i;
  int length = strlen(stringInt);

  //convert char to int and store result
  for(i = 0; i<length; i++)
    {
      data = addToFront(data, (int)stringInt&#91;i&#93;-'0');
    }
  return data;
}


////////////////////////////////////////////////////////////////////////////////
///
///  \brief prints out a big integer
///
///  \param&#91;in&#93; pointer to a struct Integer to print
///
////////////////////////////////////////////////////////////////////////////////
void print(FILE *input, struct integer *p)
{
  if(p->next != NULL)
    {
      print(input, p->next);

    }
  fprintf(input, "%d", p->digits);
}


////////////////////////////////////////////////////////////////////////////////
///
///  \brief adds two struct Integers and returns the result as a new Integer
///
///  \param[in] pointer to a struct Integer to add
///  \param[in] pointer to a struct Integer to add
///
///  \return pointer to a struct Integer which is the sum of both params
///
////////////////////////////////////////////////////////////////////////////////
struct integer* add(struct integer *p, struct integer *q)
{
  struct integer* solution = NULL; /**< output data */
  struct integer* big = p; /**< store the head of the big number */
  struct integer* small = q; /**< store the head of the small number */
  
  int result, remainder = 0;
  
  //do for all elements of the larger number
  while(big !=NULL)
    {
      //do for all elements of the smaller number
      if(small != NULL)
	{
	  result = big->digits + small->digits + remainder;
	  solution = addToEnd(solution, result%10);

	  small = small->next;
	}

      //do when no more elements left in the smaller number
      else
	{
	  result = big->digits+remainder;
	  solution = addToEnd(solution, result%10);
	}

      big = big->next;

      //handle remainders
      if(result > 9)
	{
	  remainder = 1;	/**< if the result is > 9 carry the one */
	}
      else
	{
	  remainder = 0;	/**< the result <= 9, do not carry the one */
	}
    }
  //case where there is a remainder and a digit remaining
  if(remainder == 1)
    {
      solution = addToEnd(solution, 1);
    }    
  return solution;
}


////////////////////////////////////////////////////////////////////////////////
///
///  \brief 2nd param is subtracted from the first and the result is returned.
///
///  \param&#91;in&#93; pointer to a struct Integer, >= 2nd param
///  \param[in] pointer to a struct Integer to subtract from first param
///
///  \return pointer to a struct Integer which is the result of subtraction
///
////////////////////////////////////////////////////////////////////////////////
struct integer* subtract(struct integer *p, struct integer *q)
{
  struct integer* solution = NULL;
  struct integer* big = p; /**< store the head of the big number */
  struct integer* small = q; /**< store the head of the small number */

  
  //navigation variables
  int remainder = 0;
  int btemp;

  while(big != NULL)
    {
      btemp = big->digits;


      //handle remainder & big
      //big > 1, use 0
      if(remainder == 1)
	{
	  if(btemp - 1 >=0)
	    {
	      btemp--;
	      remainder = 0;
	    }
	  //big = 0, borrow from next digit
	  else
	    {
	      btemp=9;
	    }
	}
	  
      //if the current position is greater than the size of the smaller number
      if(small != NULL)
	{
	  //calculate values
	  if(btemp - small->digits >= 0)
	    {
	      solution = addToEnd(solution, btemp - small->digits);
	    }
	       
	  else
	    {
	      solution = addToEnd(solution, btemp - small->digits+10);
	      remainder = 1;
	    }
	  small = small->next;
	}
      //no more q digits to subtract
      else
	{
	  if(btemp >= 0)
	    {
	      solution = addToEnd(solution, btemp);
	    }
	  else
	    {
	      solution = addToEnd(solution, btemp +10);
	      remainder = 1;
	    }
	}
      big = big->next;
    }

  //remove leading 0s
  solution = delZero(solution);
  return solution;
}


////////////////////////////////////////////////////////////////////////////////
///
///  \brief Determines which struct Integer has a larger value
///
///  \param[in] pointer to a struct Integer, >= 2nd param
///  \param[in] pointer to a struct Integer to subtract from first param
///
///  \return -1 if first > second
///           0 if first = second
///          +1 if first > second
///
////////////////////////////////////////////////////////////////////////////////
int compare(struct integer *p, struct integer *q)
{
  //base case where the next node on the array is null
  //this means the numbers have the same # of digits
  if(p->next == NULL && q->next == NULL)
    {
      //then p is definitively > q
      if(p->digits > q->digits)
	{
	  return 1;
	}

      //then p is definitively < q
      else if(p->digits < q->digits)
	{
	  return -1;
	}
	  
      //p and q might be equal
      else if(p->digits == q->digits)
	{
	  return 0;
	}
    }
     
  //p has more digits, therefore p > q
  else if(p->next == NULL && q->next != NULL)
    {
      return -1;
    }

  //q has more digits, therefore p < q
  else if(q->next == NULL && p->next !=NULL)
    {
      return 1;
    } 
     
  //current node is not the last node
  else
    {
      //recurse until last node is found
      switch (compare(p->next, q->next))
	{

	  //all higher nodes are equal
	case 0:

	  {
	    //if p>q, p is definitively greater
	    if(p->digits > q->digits)
	      {
		return 1;
	      }
	    //if p<q, q is definitively greater
	    else if(p->digits < q->digits)
	      {
		return -1;
	      }
	    //they are still equal up unto this digit
	    else if(p->digits == q->digits)
	      {
		return 0;
	      }
	  }
	  
	  //if -1 was returned, q is definitively greater
	case -1:
	  {
	    return -1;
	  }

	  //if 1 was returned, p is definitively greater
	case 1:
	  {
	    return 1;
	  }
	}
    }
}

Leave a Reply

You must be logged in to post a comment.