An integer can be represented by a linked list with one digit in each node. The

Question

An integer can be represented by a linked list with one digit in each node. The least significant digit in this representation is in the first node of the list. This allows for integers of virtually any size. The nodes are of the following type:

struct digit

{ int    Value;          // a digit value, 0-9

         digit* Next;

};

typedef digit* ptrType;

The following diagram shows the representation for 2149:

Develop an ADT named number with the following operations for unlimited-digit numbers. In the following descriptions, number refers to an object of your ADT. M, N and O are all of type number. The sample usage for each operation shows how it might be used, although you can make your operations work differently.

Increment: A method that increases the value of a number by 1. Sample usage: N.Increment();

Note that you cannot necessarily just change the last digit of the number; adding 1 to 1999, for example, requires changing all four digits to get 2000, and adding 1 to 9 requires making a new digit to get 10.

Hint: You should allow for three possibilities in your function regarding the initial value for N.

a.   N is NULL

b.   N is not NULL, and the value in the first node is 0..8

c.   N is not NULL, and the value in the first node is 9

Copy: A method that copies one number to another. Note that you cannot just copy one pointer to another — you must create copies of each node in the original as illustrated in a copy constructor for linked lists. Sample usage: N.Copy(M);

Sum: A method that takes two numbers and sums them. Sample usage: N.Sum(M); (adds M to N). Don't forget about a carry when the sum of two digits is greater than 10.

DisplayNumber: A method that displays the number in standard (most-significant digit first) form. Sample usage: N.DisplayNumber();

Your ADT should be a C++ class, with all functions and data declared in the appropriate sections. You may use recursion as you wish. Include a short program that adequately tests all the procedures in your ADT.

Explanation / Answer

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 10001

struct integer {
int* digits;
int size;
};

struct integer* add(struct integer* one, struct integer *two);
void print(struct integer* number);
void print_op(struct integer* op1, struct integer* op2,struct integer* tempwer,char op);
struct integer* convert_integer(char* word);
void free_struct(struct integer* thisint);
struct integer* multiply(struct integer *p, struct integer *q);


int main() {

FILE* ifp = fopen("bigint.txt", "r");

int loop, numcases;
fscanf(ifp, "%d", &numcases);

// Go through each case.
for (loop=1; loop<=numcases; loop++) {

// Read in both operands.
char op1[MAX];
char op2[MAX];
fscanf(ifp, "%s%s", op1, op2);

// Convert and compute.
struct integer* first = convert_integer(op1);
struct integer* second = convert_integer(op2);
struct integer* ans = multiply(first, second);


printf("Problem #%d: ", loop);
print_op(first, second, ans, '*');
printf(" ");

// After we output, we don't need these any more.
free_struct(first);
free_struct(second);
free_struct(ans);


}

return 0;
}

// Pre-conditions: Both one and two are not NULL pointers that point to
// linked lists structures that store non-negative digits
// at each node.
// Post-conditions: A pointer to a linked list will be returned. The
// linked list will store the value of the sum of the
// two integers represented by the linked lists passed
// into the function.
struct integer* add(struct integer* one, struct integer *two) {

struct integer *ans;
int digit1 = 0, digit2 = 0, carry = 0, result, i;


ans = (struct integer *)malloc(sizeof(struct integer));

//allocate space for the larger of the 2 arrays
if(one->size>two->size)
ans->size=one->size;
else
ans->size=two->size;

ans->digits=(int*)(malloc(sizeof(int)*ans->size));

for(i=0;i<ans->size;i++){
// Determine digit to add from first operand.
if (i<one -> size)
digit1 = one -> digits[i];
else
digit1 = 0;

// Determine digit to add from second operand.
if (i<two -> size)
digit2 = two -> digits[i];
else
digit2 = 0;

// Compute correct addition digit and carry.
result = (digit1 + digit2 + carry)%10;
carry = (digit1 + digit2 + carry)/10;

// Store result in the appropriate linked list.
ans -> digits[i] = result;

}//for

// Take care of the most significant digit if there is a carry.
if (carry != 0) {

//copy off the whole array into a new one
//of size+1 and free the old one in case of carry
ans->size+=1;
ans->digits = (int *)realloc(ans->digits, sizeof(int)*ans->size);
ans->digits[ans->size-1] = carry;
}

// Return the ptr. to the added result.
return ans;
}

// Precondition: number points to a not NULL linked list that contains
// only single digits stored at each node.
// Postcondition: The integer represented by the linked list pointed to by
// number will be printed out.
void print(struct integer* number) {

int i;
if (number != NULL) {

// Loop through in backwards order, since number is stored reversed.
for(i=number->size-1;i>=0;i--){
printf("%d",number->digits[i]);
}
}

}

// Precondition: op1 and op2 point to valid linked lists storing integers,
// operator is a valid integer operator, and tempwer is the
// value of applying the first operation to the second.
// Postcondition: The arithmetic operation desired (op1 operator op2) will
// be printed to the screen in a reasonable manner.
void print_op(struct integer* op1, struct integer* op2,struct integer* tempwer,char op) {

print(op1);
printf(" %c ", op);
print(op2);
printf(" = ");
print(tempwer);


}

//Preconditions: the first parameter is a pointer to a
// pointer variable that points to
// struct integer. The function skips leading
// blanks and assumes that no leading zeros are
// entered at the input.
//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 as the value of
// the input parameter.
struct integer* convert_integer(char* word) {

int i;

struct integer *ans=(struct integer *)(malloc(sizeof(struct integer)));
ans->size=0;
if(word==NULL) ans->digits=NULL;

else {

// Allocate space for each of the digits.
ans->size = strlen(word);
ans->digits=(int *)(malloc(sizeof(int)*ans->size));

// Store them in reverse order.
for(i=0;i< ans->size;i++)
ans->digits[ans->size-i-1]=word[i] - '0';

}//if word not NULL

return ans;
}

//Preconditions: p and q are pointers to struct integers.
//Postconditions: A new struct integer is created that
// stores the product of the integers
// pointed to by p and q and a pointer to it
// is returned.
struct integer* multiply(struct integer *p, struct integer *q){

struct integer *temp;
struct integer *ans;

int digit1 = 0, digit2 = 0, carry = 0, index=0, front=0, result, i, j, pos, preSize;

temp = (struct integer *)calloc(sizeof(struct integer),1);
ans = (struct integer *)calloc(sizeof(struct integer),1);


//allocate space for the larger of the 2 arrays
//Which ever array is larger will be the starting size of the tempwer array.
if(q->size>p->size)
temp->size = q->size;

else
temp->size = p->size;


temp->digits=(int*)(calloc(sizeof(int)*temp->size,1));


//use a double for loop, one for the top number and one for bottom.
for(i=0; i<q->size; i++){

//Make the starting size the size of the biggest number.
if(q->size>p->size)
temp->size = q->size;

else
temp->size = p->size;


temp->digits=(int*)(calloc(sizeof(int)*temp->size,1));

if (i < q->size)
digit1 = q->digits[i];
else
digit1 = 0;




//Bottom part of the multiplication.
for(j=0; j<p->size; j++){

// Determine digit to add from first operand.
if (j < p->size)
digit2 = p->digits[j];
else
digit2 = 0;

// Compute correct multiplication digit and carry.
//gives last digit
result = (digit1 * digit2 + carry)%10;
//drops last digit
carry = (digit1 * digit2 + carry)/10;

// Store result in the appropriate linked list.
temp -> digits[j] = result;

}

//Add a zero to the end of the next number (like multiplying by hand).
if(i>0){

temp->size += i;
temp->digits = (int *)(realloc(temp->digits, sizeof(int)*temp->size));


for(j=temp->size; j>0; j--){

if((j-1-i)<0)
break;
//Shift everthing over by 1.
else
temp->digits[j-1]=temp->digits[j-1-i];

}
//Make the new number zero.
for(j=1; j<=i; j++)
temp -> digits[j-1] = 0;

}//if


//If there is a carry insert it in front of the number.
if (carry != 0) {

temp->size += 1;
temp->digits = (int *)(realloc(temp->digits, sizeof(int)*temp->size));
temp->digits[temp->size-1]=0;

//Find the front of the number.
for(j=temp->size; j>0; j--){

if(temp->digits[j-1] != 0){

front = j;
break;
}
}

//Insert it.
if(result == 0)
temp->digits[front+1] = carry;
else
temp->digits[front] = carry;

carry = 0;

}//if




//Delete any leading zeros.
if(temp->size != 1){

for(j=temp->size; j>0; j--){

//Finds where the zeros end.
if(temp->digits[j-1] != 0){
pos =j;
break;
}

//Counts the zeros.
if(temp->digits[j-1] == 0)
index++;

}

//If they are all zeros then make the temp number 0 of size 1.
if(index==temp->size) {
pos=1;
temp->size = temp->size-(temp->size-pos);
temp->digits = (int *)realloc(temp->digits, sizeof(int)*temp->size);
}
//If not then reallocate with the extra zeros removed.
else{
temp->size = temp->size-(temp->size-pos);
temp->digits = (int *)realloc(temp->digits, sizeof(int)*temp->size);
}

index=0;

}//if


//If this is the first time saving the answer the allocate memory for it.
if(i==0){
ans->size = temp->size;
ans->digits=(int*)(calloc(sizeof(int)*temp->size,1));
}

//Add the temp number to the total (ans).
ans = add(temp, ans);

//Clear temp.
for(j=0; j<temp->size; j++)
temp->digits[j]=0;


}//for on top


free_struct(temp);

return ans;

}


// Frees the memory for the struct pointed to by thisint.
void free_struct(struct integer* thisint) {
free(thisint->digits);
free(thisint);
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.