Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * File: struct integer.c
- * Author: Andrew Levenson
- * Course: COP 3502
- * Professor: Jonathan Cazalas
- * Description: Assignment in using Linked Lists
- * in order to perform bigint addition and subtraction.
- *
- * Created on September 1, 2010, 11:38 AM
- */
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- // Constant Definitions
- #define ADD 1
- #define SUB 2
- // Output file
- char *fName = "out.txt";
- FILE *outFile;
- /*
- * Create a prototype of a single
- * node in the Linked List.
- * Each node will represent a single
- * integer comprising one part of a struct integer.
- */
- struct integer
- {
- int digit;
- struct integer *next;
- };
- // Function Prototypes
- struct integer* read_integer( char *stringInt );
- struct integer* add( struct integer *p, struct integer *q );
- struct integer* subtract( struct integer *p, struct integer *q);
- struct integer* stripLeadingZeros( struct integer *p );
- int compare( struct integer *p, struct integer *q );
- void print( struct integer *p );
- void reverse( struct integer **p );
- // Main function
- int main( )
- {
- //Variable initialization
- /*
- * Initialize pointers to the linked lists.
- * One, *head, will always point to the
- * first element, the head, of the list.
- * The other element, *curr, will point to the
- * node currently being accessed, and will be
- * used to traverse the list.
- */
- struct integer* pHead;
- struct integer* qHead;
- struct integer* tHead; // Used to contain the total
- int numOps, oper, i;
- char *fileName = "input.txt";
- char bigintstr[200];
- FILE *inputFile;
- // Open output file
- outFile = fopen(fName, "a+");
- // Open up the input file for reading
- inputFile = fopen(fileName, "r");
- // Read in the number of operations to be performed
- fscanf(inputFile, "%d", &numOps);
- /*
- * For each operation that must be performed,
- * construct a linked list for each of the
- * struct integers in the file. Then, perform the operation
- * indicated by the digit preceding them.
- */
- for( i = 0; i < numOps; i++ )
- {
- // Read in the number that dictates operation
- fscanf(inputFile, "%d", &oper);
- // Read in the first struct integer into a string
- fscanf(inputFile, "%s", bigintstr);
- /*
- * Pass the struct integer string to read_integer()
- * in order to construct a linked list out of it.
- */
- pHead = read_integer( bigintstr );
- // Read in second struct integer into a string
- fscanf(inputFile, "%s", bigintstr);
- /*
- * Pass the struct integer str to read_integer()
- * in order to construct a linked list out of it.
- */
- qHead = read_integer( bigintstr );
- /*
- * Depending on the operation to be performed,
- * call the corresponding function.
- */
- if( oper == ADD )
- {
- tHead = add( pHead, qHead );
- print( pHead );
- fprintf(outFile, " + ");
- print( qHead );
- fprintf(outFile, " = ");
- reverse( &tHead );
- print( tHead );
- fprintf(outFile, "\n");
- }
- else if( oper == SUB )
- {
- /*
- * Before you can subtract, you must
- * compare the two bigints being subtracted.
- * Because we are only dealing with
- * positive integers, we must first
- * determine which is the larger of the
- * two operands. This operand becomes
- * the bigint from which we subtract.
- */
- if( compare( pHead, qHead ) > 0 ) // p > q
- {
- tHead = subtract( pHead, qHead );
- print( pHead );
- fprintf(outFile, " - ");
- print( qHead );
- fprintf(outFile, " = ");
- reverse( &tHead );
- print( tHead );
- fprintf(outFile, "\n");
- }
- else if( compare( pHead, qHead ) == 0 ) // p == q
- {
- tHead->digit = 0;
- tHead->next = NULL;
- print( pHead );
- fprintf(outFile, " - ");
- print( qHead );
- fprintf(outFile, " = ");
- reverse( &tHead );
- print( tHead );
- fprintf(outFile, "\n");
- }
- else // p < q
- {
- tHead = subtract( qHead, pHead );
- print( qHead );
- fprintf(outFile, " - ");
- print( pHead );
- fprintf(outFile, " = ");
- reverse( &tHead );
- print( tHead );
- fprintf(outFile, "\n");
- }
- }
- }
- fclose(inputFile);
- fclose(outFile);
- //system(PAUSE);
- return 0;
- }
- // Function Definitions
- /*
- * Function read_integer
- *
- * @Parameter CHAR* stringInt
- *
- * Parameter contains a string representing a struct integer.
- * Tokenizes the string by each character, converts each char
- * into an integer, and constructs a backwards linked list out
- * of the digits.
- *
- * @Return STRUCT* Integer
- */
- struct integer* read_integer( char* stringInt )
- {
- int i, n;
- struct integer *curr, *head;
- int numDigits = strlen( stringInt ); // Find the length of the struct integer
- head = NULL;
- for( i = 0; i < numDigits; i++ )
- {
- n = stringInt[i] - '0'; // Convert char to an integer
- curr = (struct integer *) malloc (sizeof( struct integer )); // Allocate memory for node
- curr->digit = n; // Digit of current node is assigned to n
- curr->next = head; // Move to the next node in the list.
- head = curr; // Move head up to the front of the list.
- }
- return head; // Return a pointer to the first node in the list.
- }
- /*
- * Function reverse
- *
- * @Parameter STRUCT** Integer
- *
- * Reverses a linked list by creating a new
- * reversed linked list and then returning the
- * head of the newly formed list.
- */
- void reverse (struct integer **p)
- {
- struct integer *oldList = *p;
- struct integer *newList = NULL;
- while( oldList )
- {
- struct integer *oldNext = oldList->next;
- oldList->next = newList;
- newList = oldList;
- oldList = oldNext;
- }
- *p = newList;
- }
- /*
- * Function print
- *
- * @Parameter STRUCT* Integer
- *
- * Given a linked list, will traverse through
- * the nodes and print out, one at a time,
- * the digits comprising the struct integer that the
- * linked list represents.
- *
- * TODO: Print to file
- */
- void print( struct integer *p )
- {
- struct integer *curr = p;
- curr = stripLeadingZeros( curr );
- reverse( &curr );
- while( curr )
- {
- fprintf(outFile, "%d", curr->digit);
- curr = curr->next;
- }
- }
- /*
- * Function add
- *
- * @Paramater STRUCT* Integer
- * @Parameter STRUCT* Integer
- *
- * Takes two linked lists representing
- * big integers stored in reversed order,
- * and returns a linked list containing
- * the sum of the two integers.
- *
- * @Return STRUCT* Integer
- *
- * TODO Comment me
- */
- struct integer* add( struct integer *p, struct integer *q )
- {
- int carry = 0;
- struct integer *sHead, *sCurr;
- struct integer *pHead, *qHead;
- pHead = p;
- qHead = q;
- sHead = NULL;
- while( p )
- {
- sCurr = ( struct integer* ) malloc (sizeof(struct integer));
- sCurr->digit = p->digit + q->digit + carry;
- sCurr->next = sHead;
- sHead = sCurr;
- carry = 0;
- /*
- * If the current digits sum to greater than 9,
- * create a carry value and replace the current
- * value with value mod 10.
- */
- if( sCurr->digit > 9 )
- {
- carry = 1;
- sCurr->digit = sCurr->digit % 10;
- }
- /*
- * If the most significant digits of the numbers
- * sum to 10 or greater, create an extra node
- * at the end of the sum list and assign it the
- * value of 1.
- */
- if( carry == 1 && sCurr->next == NULL )
- {
- struct integer *sCarry = ( struct integer* ) malloc (sizeof(struct integer));
- sCarry->digit = 1;
- sCarry->next = NULL;
- reverse( &sCurr );
- sCurr->next = sCarry;
- reverse( &sCurr );
- }
- p = p->next;
- if( q->next ) q = q->next;
- else q->digit = 0;
- }
- return sHead;
- }
- /*
- * Function subtract
- *
- * @Parameter STRUCT* Integer
- * @Parameter STRUCT* Integer
- *
- * Takes two linked lists representing struct integers.
- * Traverses through the lists, subtracting each
- * digits from the subsequent nodes to form a new
- * struct integer, and then returns the newly formed
- * linked list.
- *
- * @Return STRUCT* Integer
- *
- * TODO Comment me
- */
- struct integer* subtract( struct integer *p, struct integer *q )
- {
- int borrow = 0;
- struct integer *dHead, *dCurr;
- struct integer *pHead, *qHead;
- pHead = p;
- qHead = q;
- dHead = NULL;
- while( p )
- {
- dCurr = (struct integer*) malloc (sizeof(struct integer));
- if( q )
- {
- dCurr->digit = p->digit - q->digit - borrow;
- }
- else
- {
- dCurr->digit = p->digit - borrow;
- }
- dCurr->next = dHead;
- dHead = dCurr;
- if( dCurr->digit < 0 )
- {
- dCurr->digit += 10;
- borrow = 1;
- }
- if( dCurr->next == NULL && borrow == 1 )
- {
- struct integer *dBorrow = (struct integer*) malloc (sizeof(struct integer));
- dBorrow->digit = -1;
- dBorrow->next = NULL;
- dCurr->next = dBorrow;
- }
- p = p->next;
- if( q->next) q = q->next;
- else q->digit = 0;
- }
- return dHead;
- }
- /*
- * Function compare
- *
- * @Parameter STRUCT* Integer
- * @Parameter STRUCT* Integer
- *
- * Takes in two linked lists representing struct integers.
- * Traverses the lists one at a time, comparing the
- * digits.
- *
- * Case: p < q
- * @Return -1
- *
- * Case: p == q
- * @Return 0
- *
- * Case: p > q
- * @Return 1
- *
- * TODO Comment me
- */
- int compare( struct integer *p, struct integer *q )
- {
- struct integer *pHead, *qHead;
- int comp = 0, pCount = 0, qCount = 0;
- pHead = p;
- qHead = q;
- // Get the length of p
- while( p )
- {
- pCount++;
- p = p->next;
- }
- // Get the length of q
- while( q )
- {
- qCount++;
- q = q->next;
- }
- if( pCount > qCount ) // p > q
- {
- return 1;
- }
- if( pCount < qCount ) // p < q
- {
- return -1;
- }
- while( p )
- {
- if( p->digit > q->digit )
- {
- comp = 1;
- }
- if( p->digit < q->digit )
- {
- comp = -1;
- }
- p = p->next;
- if( q->next ) q = q->next;
- else q->digit = 0;
- }
- return comp;
- }
- /*
- * Function stripLeadingZeros
- *
- * @Parameter STRUCT* Integer
- *
- * Step through a linked list, recursively unlinking
- * all leading zeros and making the first
- * non-zero integer the head of the list.
- *
- * @Return STRUCT* Integer
- */
- struct integer* stripLeadingZeros( struct integer *p )
- {
- reverse( &p );
- // Are we at the end of the list?
- if( p == NULL ) return NULL;
- // Are we deleting the current node?
- //Also it should not strip last 0
- if( p->digit == 0 && p->next != NULL)
- {
- struct integer *pNext;
- pNext = p->next;
- // Deallocate the node
- free( p );
- // Try to strip zeros on pointer to the next node and return that pointer
- return stripLeadingZeros(pNext);
- }
- reverse( &p );
- return p;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement