Code:
//John Torres
//COP 3223-0002
//Assignment #3
//Febuary, 20, 2009
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct integer* read_integer(char* stringInt);
struct integer* read_integerRec(char* stringInt, int len);
void print(struct integer *p);
void printRec(struct integer *p, int list_len);
struct integer* add(struct integer *p, struct integer *q);
struct integer* addRec(struct integer *p, struct integer *q, int carry);
struct integer* subtract(struct integer *p, struct integer *q);
struct integer* subtractRec(struct integer *p, struct integer *q, int barrow);
int compare(struct integer *p, struct integer *q);
int compareRec(struct integer* p, struct integer* q, int len);
void FreeList(struct integer *p);
struct integer* ResizeList(struct integer *p);
struct integer* ResizeListRec(struct integer *p, int len);
int ListSize(struct integer *p);
struct integer{
int digit;
struct integer *next;
};
int main(void)
{
struct integer* head[3];
char number[201];
int file_len;
int test1;
int test2;
int i,j;
FILE *fin;
//open file and get number of file lines
fin = fopen("bigint.txt", "r");
fscanf(fin, "%d", &file_len);
//loop breaks after file is done
for(i = 0; i < file_len; i++)
{
//read operation type, 1=add, 2=sub
fscanf(fin,"%d", &test1);
//reads the 2 strings and converts them to numbers
for(j = 0; j < 2; j++)
{
fscanf(fin, "%s", number);
head[j] = read_integer(number);
}
//if add
if(test1 == 1)
{
//add function
head[2] = add(head[0], head[1]);
//resize
head[2] = ResizeList(head[2]);
//print operation
print(head[0]);
printf("\n+\n");
print(head[1]);
printf("\n=\n");
print(head[2]);
printf("\n\n");
system("pause");
}
//if subtract
else if(test1 == 2)
{
//subtract function
head[2] = subtract(head[0], head[1]);
//resize answer
head[2] = ResizeList(head[2]);
//check order
test2 = compare(head[0], head[1]);
//print operation
if(test2 == -1)
{//if second is larger
print(head[1]);
printf("\n-\n");
print(head[0]);
printf("\n=\n");
print(head[2]);
printf("\n");
system("pause");
}
else
{//if same or first is larger
print(head[0]);
printf("\n-\n");
print(head[1]);
printf("\n=\n");
print(head[2]);
printf("\n");
system("pause");
}
}
//if first number was not a 1 (add) or a 2 (sub)
else
{
printf("BAD DATA");
}
//free lists
FreeList(head[0]);
FreeList(head[1]);
///////////////////////////////////////////////second problem
///////////////////////////////////////////////dies here for just one line
FreeList(head[2]);
}
return 0;
}
////////////////////////////////////////////////////////////////////////////////
//Preconditions: the first parameter is string that stores
// only contains digits, doesn't start with
// 0, and is 50 or fewer characters long.
//
//Postconditions: The function will read the digits of the
// large integer character by character,
// convert them into integers and place them in
// nodes of a linked list. The pointer to the
// head of the list is returned.
//
//Discription:
////////////////////////////////////////////////////////////////////////////////
struct integer* read_integer(char* stringInt)
{
struct integer* temp;
int len;
//find number of digits
len = strlen(stringInt) - 1;
//build struct
return read_integerRec(stringInt, len);
}
struct integer* read_integerRec(char* stringInt, int len)
{
struct integer* temp;
//allocate memory
temp = (struct integer*) malloc(sizeof(struct integer));
//end case
if(len == 0)
{
temp->digit = (int) stringInt[0] - '0';
temp->next = NULL;
return temp;
}
//base case
else
{
temp->digit = (int) stringInt[len] - '0';
temp->next = read_integerRec(stringInt, len-1);
return temp;
}
}
////////////////////////////////////////////////////////////////////////////////
//Preconditions: p is a pointer to a big integer, stored in
// reverse order, least to most significant
// digit, with no leading zeros.
//
//Postconditions: The big integer pointed to by p is
// printed out.
//
//Discription:
////////////////////////////////////////////////////////////////////////////////
void print(struct integer *p)
{
int list_len;
//find list lenth
list_len = ListSize(p);
//print function
printRec(p, list_len);
}
void printRec(struct integer *p, int list_len)
{
struct integer* temp;
int i;
//end case
if(list_len == 0)
{
printf("%d", p->digit);
}
//base case
else
{
temp = p;
//move pointer to end of list
for(i = 0; i < list_len; i++)
{
temp = temp->next;
}
//print last number in list (first digit in number)
printf("%d", temp->digit);
//do it again
printRec(p, list_len-1);
}
}
////////////////////////////////////////////////////////////////////////////////
//Preconditions: p and q are pointers to big integers,
// stored in reverse order, least to most
// significant digit, with no leading zeros.
//
//Postconditions: A new big integer is created that stores
// the sum of the integers pointed to by p
// and q and a pointer to it is returned.
//
//Discription:
////////////////////////////////////////////////////////////////////////////////
struct integer* add(struct integer *p, struct integer *q)
{
return addRec(p, q, 0);
}
struct integer* addRec(struct integer *p, struct integer *q, int carry)
{
struct integer* big_number;
//allocate memory
big_number = (struct integer*) malloc(sizeof(struct integer));
//if nothing left to add
if(q->next == NULL && p->next == NULL)
{
big_number->digit = p->digit + q->digit + carry;
big_number->next = NULL;
return big_number;
}
//if q is has no more numbers
else if(q->next == NULL)
{
big_number->digit = q->digit+ p->digit + carry;
big_number->next = p->next;
return big_number;
}
//if p has no more numbers
else if(p->next == NULL)
{
big_number->digit = p->digit + q->digit + carry;
big_number->next = q->next;
return big_number;
}
//base case
else
{
//add
big_number->digit = p->digit + q->digit + carry;
//...carry the one...
if(big_number->digit > 9)
{
big_number->digit -= 10;
carry =1;
}
//reset carry
else
{
carry = 0;
}
//do it again
big_number->next = addRec(p->next, q->next, carry);
return big_number;
}
}
////////////////////////////////////////////////////////////////////////////////
//Preconditions: p and q are pointers to big integers,
// stored in reverse order, least to most
// significant digit, with no leading zeros.
//
//Postconditions: A new big integer is created that stores
// the absolute value of the difference
// between the two and a pointer to this is
// returned.
//
//Discription:
////////////////////////////////////////////////////////////////////////////////
struct integer* subtract(struct integer *p, struct integer *q)
{
struct integer* big_number;
int test;
//compare list to find grater number
test = compare(p, q);
//if first is grater
if(test == 1)
{
big_number = subtractRec(p, q, 0);
}
//if same or second is grater
else
{
big_number = subtractRec(q, p, 0);
}
return big_number;
}
struct integer* subtractRec(struct integer *p, struct integer *q, int barrow)
{
struct integer* big_number;
//allocate memory
big_number = (struct integer*) malloc(sizeof(struct integer));
//if q has no more numbers after this one
//and p is more then q + barrow
//end case
if(q->next == NULL && p->digit >= (q->digit + barrow))
{
big_number->digit = p->digit - q->digit - barrow;
big_number->next = p->next;
barrow = 0;
return big_number;
}
//if q and p have no more numbers after this one
//end case
else if(q->next == NULL && p->next == NULL)
{
big_number->digit = p->digit - q->digit - barrow;
big_number->next = NULL;
barrow = 0;
return big_number;
}
//if q has no more numbers after this one
//and q + barrow is more then p
//end case
else if(q->next == NULL)
{
big_number->digit = p->digit - q->digit - barrow + 10;
big_number->next->digit = p->next->digit - 1;
big_number->next->next = p->next->next;
barrow = 0;
return big_number;
}
//base case, p > q + barrow (dont need to barrow from next number
else if(p->digit >= (q->digit + barrow))
{
big_number->digit = p->digit - q->digit - barrow;
big_number->next = subtractRec(p->next, q->next, 0);
return big_number;
}
//base case, p < q + barrow (need to barrow from next number
else
{
big_number->digit = p->digit - q->digit - barrow + 10;
big_number->next = subtractRec(p->next, q->next, 1);
return big_number;
}
}
////////////////////////////////////////////////////////////////////////////////
//Preconditions: Both parameters of the function are
// pointers to struct integer.
//
//Postconditions: The function compares the digits of two
// numbers recursively and returns:
// -1 if the first number is smaller than the second,
// 0 if the first number is equal to the second number,
// 1 if the first number is greater than the second.
//
//Discription:
////////////////////////////////////////////////////////////////////////////////
int compare(struct integer *p, struct integer *q)
{
int p_len;
int q_len;
//finds number of digits in numbers
p_len = ListSize(p);
q_len = ListSize(q);
//compares lenths
if(p_len > q_len)
{//p is longer
return 1;
}
else if(p_len < q_len)
{//q is longer
return -1;
}
else
{//need more info
return compareRec(p, q, p_len);
}
}
int compareRec(struct integer* p, struct integer* q, int len)
{
struct integer* temp_p;
struct integer* temp_q;
int i;
//assing temp pointers
temp_p = p;
temp_q = q;
//end case
if(len == 1)
{
//if p<q
if(p->digit < q->digit)
{
return -1;
}
//if p>q
else if(p->digit > q->digit)
{
return 1;
}
//if p=q
else
{
return 0;
}
}
//base case
//move pointer to end of list (first number)
for(i = 1; i < len; i++)
{
temp_p = temp_p->next;
temp_q = temp_q->next;
}
//check
//if p>q
if(temp_p->digit > temp_q->digit)
{
return 1;
}
//if p<q
else if(temp_p->digit < temp_q->digit)
{
return -1;
}
//need more info, do it again
else
{
return compareRec(temp_p, temp_q, len-1);
}
}
////////////////////////////////////////////////////////////////////////////////
//Preconditions: A valid list header
//
//Postconditions: All nodes in list are freed
//
//Discription:
////////////////////////////////////////////////////////////////////////////////
void FreeList(struct integer *p)
{
struct integer* temp;
//base case
if(p != NULL)
{
//temp point to 2nd node
temp = p->next;
//do it again
FreeList(temp);
//free first node
free(p);
}
//end case (nothing...this is a void function)
}
////////////////////////////////////////////////////////////////////////////////
//Preconditions: Valid list of numbers
//
//Postconditions: returns a head pointer to a resied list. The new list has
// no ending zeros.
//
//Discription:
////////////////////////////////////////////////////////////////////////////////
struct integer* ResizeList(struct integer *p)
{
struct integer* temp;
int len;
//get list size (number of digits)
len = ListSize(p);
return ResizeListRec(p, len);
}
struct integer* ResizeListRec(struct integer *p, int len)
{
struct integer* temp;
int i;
//keeps the last number, no matter what (even 0)
//end case
if(len == 1)
{
temp = p->next;
p->next = NULL;
free(temp);
return p;
}
if(len == 0)
{
return p;
}
//assign temp
temp = p;
//put temp to last node (first digit)
for(i = 0; i < len - 1 ; i++)
{
temp = temp->next;
}
//check to see if digit is 0
if(temp->next->digit == 0)
{
//////////////////////////////////////first problem
//////////////////////////////////////Problem here after 5 calls on 3rd function
//////////////////////////////////////I think it is a memory issue
//free usless node
free(temp->next);
//changes pointer to null (end of list)
temp->next = NULL;
//do it again
return ResizeListRec(p, len - 1);
}
//if digit is not 0
//end case
else
{
return p;
}
}
////////////////////////////////////////////////////////////////////////////////
//Preconditions: Valid list of numbers
//
//Postconditions: Returns an int the size of the number of nodes in the list
//
//Discription:
////////////////////////////////////////////////////////////////////////////////
int ListSize(struct integer *p)
{
struct integer* temp;
int i;
//assign temp
temp = p;
//count number of digits in list
for(i = 0; temp->next != NULL; i++)
{
temp = temp->next;
}
return i;
}
Link List math
Originally Posted by t014y
