Homework SourseDemonstrating Structures Pointers Linked Lists Dynamic Alloc
Demonstrating
Structures Pointers Linked Lists Dynamic Allocation
Overview
Applications from scientific computation to distributed databases to physicalsimulations to image rendering all have a need to deal with incredibly large
and precise
information; however, hardware (like a processor) is intrinsically bounded
in its
capabilities – it cannot magically process an arbitrarily precise piece of data. Softwaremust help. In this lab, you will explore a means to allow mathematical operations on
very large numbers.
Outline
• You will implement a program capable of “truly arbitrary precision integer arithmetic”.
• This means the user can use integers of any
size
o A typical short
integer (16 bits) can represent a maximum value of 65,535
o A typical long
integer (32 bits) can represent a maximum value of 4,294,967,295
o A typical long long
integer (64 bits) can represent a maximum value of
18,446,744,073,709,551,615
o We want to allow the user to use much, much, much
bigger numbers
• The user will enter two (base 10) integers, of an arbitrary size
• The user will then select an operation:
o Add (‘+’)
o Subtract (‘-‘)
• The program will print the result, and quit
• Negative numbers are not allowed
Design
Integers will be represented as a linked list of single digits
o To grow an integer, you allocate and link new digits
integer.c
o Will contain, at a minimum, the following functions:
‘add’, which accepts two ‘immense_int_t’s, and returns a new ‘immense_int_t’
representing their sum
‘subtract’, which accepts two ‘immense_int_t’s, and returns a new‘immense_int_t’ representing their difference
A function to create a new ‘immense_int_t’
A function to destroy an ‘immense_int_t’
Constraints
Input
o All input lines are terminated with a newline character (‘\ ’). There is no otherwhitespace on an input line.
o An input integer will have at least one digit.
o There is no upper bound on the size of the input integers, other than it will not be solarge that your process runs out of memory.
o There will be no commas in the input integer; the only valid input characters for an
integer are 0-9.
o The first two input lines will always be integers, the last (third) input line will alwaysbe either the character ‘+’, or ‘-‘, indicating the desired operation
o When subtraction is specified, the larger number will always be first, so that the
result remains positive.
o Input integers will have no leading 0’s.
Output
o Your output should consist of only the result, followed by a newline character (‘\ ’).
Do not include any other whitespace or output.
o Your output integer should have no leading 0’so Valid characters for the result are 0-9
Implementation Hints
Simulate longhand addition and subtraction, working with a single digit at a time, as you
might while working with pencil and paper.
Sample input and output
Example input 1:
o 10984729
o 93940001
o +
Example output 1:
o 104924730
Example input 2:
o 1092337
o 342888
o -
Example output 2:
o 749449
Example view from the command line, with manual input/output
o ./integer
o 10984729
o 93940001
o +
o 104924730
o ./integer
o 1092337
o 342888
o -
o 749449
Compiling and Naming
Your source code must be named “integer.c” Your source must compile with:
gcc –Wall integer.c –o integer
You can run your program in GDB by first compiling with symbols (-g) then invokingGDB:
gcc -g –Wall integer.c –o integergdb -ex run ./integer
I highly suggest running your program in the above fashion even if you have beenstubbornly resisting gdb. Diagnosing a \"Segmentation Fault\" when using pointers isvirtually impossible without the use of gdb. GDB will be your friend in this lab. Trust me,just do it. You can run your program through an industry standard tool called valgrind to searchfor memory leaks. At the end of execution, valgrind will let you know if your programleaks memory. To run your program through valgrind use the following command:
valgrind ./integer
Solution
#include <stdio.h>
#include <stdlib.h>
struct integerNode{
char value;
struct integerNode *next;
};
typedef struct integerNode ELE;
typedef struct integerNode *integer;
integer READ();
void Print(integer a);
int compare(integer a1, integer a2);
integer ADD(integer a1, integer a2);
integer SUB(integer a1, integer a2);
int main()
{
ELE *a1;
ELE *a2;
ELE *a;
int i=0;
while(i!=3)
{
printf(\"1)Add\ 2)Subtract\ 3)Quit\ \");
printf(\"Please enter the number to perform operation\ \");
scanf(\"%d\", &i);
getchar();
switch(i)
{
case 1:
printf(\"Enter first large integer\ \");
a1=READ();
printf(\"Enter second large integer\ \");
a2=READ();
ADD(a1, a2);
Print(a);
case 2:
SUB(a1, a2);
case 3:
exit(0);
}
}
}
integer READ( )
{
char ch;
ELE *head = NULL;
ELE *new;
while((ch=getchar())!=\'\ \')
{
if( (ch>=\'0\' ) && (ch<=\'9\') ){
new=malloc(sizeof(ELE));
new->value=ch;
new->next=head;
head=new;
}
}
return head;
printf(\"\ \");
}
integer ADD(integer a1, integer a2)
{
int value1, value2, total;
ELE *new;
ELE *head;
while((a1!=NULL) && (a2!=NULL))
{
new=malloc(sizeof(ELE));
value1=a1->value-48;
value2=a2->value-48;
total=value1+value2;
new->value=total;
new->next=head;
head=new;
a1=a1->next;
a2=a2->next;
}
printf(\"+\ \");
printf(\"%d\", total);
}
integer SUB(integer a1, integer a2)
{
int value1, value2, difference;
ELE *new;
ELE *head;
while((a1!=NULL) && (a2!=NULL))
{
new=malloc(sizeof(ELE));
value1=a1->value-48;
value2=a2->value-48;
difference=value1-value2;
new->value=difference;
new->next=head;
head=new;
a1=a1->next;
a2=a2->next;
}
printf(\"-\ \");
printf(\"%d\", difference);
}
void Print(integer a)
{
if(a->next!=NULL)
{
Print(a->next);
printf(\"%c\", a->value);
}
else
printf(\"%c\", a->value);
}
