By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
428,586 Members | 623 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 428,586 IT Pros & Developers. It's quick & easy.

Subtracting large numbers usng linked list

P: n/a
Hi,
I have an assignment that requires me to subtract two very large
unsigned integers
using linked list.AFAIK I have to manipulate data as character. But I
dont know how to get input into the linked list since the input will
all be in one line. eg.
1234567890. Also I have to use one integer per node.
Any help/suggestion will be greatly appreciated.
Thanks in advance
Jul 22 '05 #1
Share this Question
Share on Google+
8 Replies


P: n/a
simpleman wrote:
Hi,
I have an assignment that requires me to subtract two very large
unsigned integers
using linked list.AFAIK I have to manipulate data as character. But I
dont know how to get input into the linked list since the input will
all be in one line. eg.
1234567890. Also I have to use one integer per node.
Any help/suggestion will be greatly appreciated.
Thanks in advance


Get the input as string.

And then tokenize the string into parts such that
you can fit each part into a node in the linked list.

--
Karthik. http://akktech.blogspot.com .
' Remove _nospamplz from my email to mail me. '
Jul 22 '05 #2

P: n/a

"simpleman" <kh*********@gmail.com> wrote in message
news:32**************************@posting.google.c om...
Hi,
I have an assignment that requires me to subtract two very large
unsigned integers
using linked list.AFAIK I have to manipulate data as character. But I
dont know how to get input into the linked list since the input will
all be in one line. eg.
1234567890. Also I have to use one integer per node.
Any help/suggestion will be greatly appreciated.
Thanks in advance


Well that seems the easier part of your assignment.

You could read the input one character at a time. E.g.

char ch;
while (cin.get(ch))
{
if (ch == '\n') // stop at end of line
break;
// add char to list here
}

You could read a line at a time and then split the line up into individual
characters.

string line;
getline(cin, line);
for (size_t i = 0; i < line.size(); ++i)
{
char ch = line[i];
// add char to list here
}

john
Jul 22 '05 #3

P: n/a
"simpleman" writes:
I have an assignment that requires me to subtract two very large
unsigned integers
using linked list.AFAIK I have to manipulate data as character. But I
dont know how to get input into the linked list since the input will
all be in one line. eg.
1234567890. Also I have to use one integer per node.
Any help/suggestion will be greatly appreciated.


A simple linked list gives you easy access to only one end of the list. So
you want to put the data in backwards, so the '0' will be put in last. Then
you can conveniently work in a right to left fashion, as you learned in
elementary school. Convert the digits to positive BCD digits, 0000 to 1001
as you insert them. Do any necessary sign finagling as a separate step.
You might want to use nine or tens complement arithmetic. But my guess is
that the instructor will let you get by if you only handle positive
integers. Note that you can do anything that needs to be done, +, -, *, /,
with a proper subtractor [sp?].

Even though the data are one line, it doesn't mean that you can't read and
process a single character. That is:

char ch;
cin >> ch;

works OK.
Jul 22 '05 #4

P: n/a
I got the input into the string with one integer per node. Now the
problem
is subtracting two linked lists from one another as it involves carry
over in case the bottom number is larger than corresponding integer.
Also since they are in the linked list, I have to subtract one integer
from another.
Any help will be greatly appreciated
Thans in Advance
Jul 22 '05 #5

P: n/a

"simpleman" <kh*********@gmail.com> schrieb im Newsbeitrag
news:32**************************@posting.google.c om...
I got the input into the string with one integer per node. Now the
problem
is subtracting two linked lists from one another as it involves carry
over in case the bottom number is larger than corresponding integer.
Also since they are in the linked list, I have to subtract one integer
from another.
Any help will be greatly appreciated
Thans in Advance

Do you know how to do a difference manually (on paper)?
You can do the same with the computer. As you are using your own
representation
you can use an additional flag for the sign.
2 3 4 5 6 7 8 9 (A)
-1 2 3 4 5 6 7 8 (B)
---------------
1 1 1 1 1 1 1 1 (C)

Remark:
if A<B:
C= - (B-A)
else:
C= A-B

Regards
Michael
Jul 22 '05 #6

P: n/a

"simpleman" <kh*********@gmail.com> wrote in message
news:32**************************@posting.google.c om...
I got the input into the string with one integer per node. Now the
problem
is subtracting two linked lists from one another as it involves carry
over in case the bottom number is larger than corresponding integer.
Also since they are in the linked list, I have to subtract one integer
from another.
Any help will be greatly appreciated
Thans in Advance


You only get help with homework when you show that you have made some effort
yourself. Post your attempt to subtract one number from another. Then people
will help you with the code.

Also try to explain exactly what you are stuck on, it sounds like you are
stuck on what algorithm to use. So post your ideas on the algorithm, even if
it only half baked ideas like 'I'm going to use a loop'. The way you do this
problem, is very similar to the way you subtract two numbers one a piece of
paper, so have a think about that.

The bottom line is no-one is going to give you the answer. You have to show
that you are making an effort.

John
Jul 22 '05 #7

P: n/a
Here is the rough code I have done so far;
It works untill it prits out two linked list but after that don't have any
idea whats happening...
#include<iostream.h>
struct link{
char ch;
link *next;};
int main(){
link *top1=0,*top2=0,*top3=0;
link *lptr;
char ch;
int one,two,temp;
cout<<"Input first number:";
while(cin.get(ch)){
if(ch == '\n')
break;
lptr =new link;
lptr->ch=ch;
lptr->next=top1;
top1=lptr;}
lptr=top1;
while(top1){
cout<<top1->ch;
top1=top1->next;}
cout<<"Input second number:";
while(cin.get(ch)){
if(ch=='\n')
break;
lptr =new link;
lptr->ch=ch;
lptr->next=top2;
top2=lptr;}
lptr=top2;
while(top2){
cout<<top2->ch;
top2=top2->next;}
while(top1!=NULL && top2!=NULL){
one=top1->ch - '0';
two=top2->ch - '0';
if(one<two){
temp=-(two - one);
lptr=new link;
lptr->ch=temp;
lptr->next=top3;
top3=lptr;
top1=top1->next;
top2=top2->next;
cout<<top3->ch;}
else
one=top1->ch - '0';
two=top2->ch - '0';
temp=(one - two);
lptr=new link;
lptr->ch=temp;
lptr->next=top3;
top3=lptr;
top1=top1->next;
top2=top2->next;
cout<<top3->ch;}
return 0;
}
Jul 22 '05 #8

P: n/a

"simpleman" <kh*********@gmail.com> wrote in message
news:32**************************@posting.google.c om...
Here is the rough code I have done so far;
It works untill it prits out two linked list but after that don't have any
idea whats happening...
#include<iostream.h>
struct link{
char ch;
link *next;};
int main(){
link *top1=0,*top2=0,*top3=0;
link *lptr;
char ch;
int one,two,temp;
cout<<"Input first number:";
while(cin.get(ch)){
if(ch == '\n')
break;
lptr =new link;
lptr->ch=ch;
lptr->next=top1;
top1=lptr;}
lptr=top1;
while(top1){
cout<<top1->ch;
top1=top1->next;}
cout<<"Input second number:";
while(cin.get(ch)){
if(ch=='\n')
break;
lptr =new link;
lptr->ch=ch;
lptr->next=top2;
top2=lptr;}
lptr=top2;
while(top2){
cout<<top2->ch;
top2=top2->next;}
while(top1!=NULL && top2!=NULL){
one=top1->ch - '0';
two=top2->ch - '0';
if(one<two){
temp=-(two - one);
lptr=new link;
lptr->ch=temp;
lptr->next=top3;
top3=lptr;
top1=top1->next;
top2=top2->next;
cout<<top3->ch;}
else
one=top1->ch - '0';
two=top2->ch - '0';
temp=(one - two);
lptr=new link;
lptr->ch=temp;
lptr->next=top3;
top3=lptr;
top1=top1->next;
top2=top2->next;
cout<<top3->ch;}
return 0;
}


Did you know that C++ has a built in linked list? Using it would certainly
tidy up your code.

Anyway there are at least four different things you aren't dealing with

1) Lists which are different length. This is actually quite easy, when you
subtract 123 from 34567 say, you just have to think of the smaller number as
having extra zeros, i.e. subtract 00123 from 34567. So when one list is
smaller than the other don't quit your loop early, carry on until both lists
are NULL but take zeros from the smaller list. Something like this

while(top1!=NULL || top2!=NULL){
{
if (top1)
one=top1->ch - '0';
else
one = 0; // end of top1 list, pad out with zeros
if (top2)
two=top2->ch - '0';
else
two = 0; // end of top2 list, pad out with zeros
...
}
2) Borrowing when the top number is less than the bottom number. This is
also quite easy when you know how. Remember how you do subtract one paper
(you do know how to do that right? In this age of computers and calculators
its hard to be sure). If the top number is smaller than the bottom number
you have to borrow from the next column. This means that you have to
remember when you subtract two numbers whether you borrowed last time
around. So you need an extra variable to remember this. Something like this

bool borrow = false; // no borrow to start with
while (more digits)
{
int top_digit = digit off top list;
int bottom_digit = digit off bottom list;
if (borrow) // did we borrow last time?
--top_digit; // if we did then subtract one from top digit
int result_digit = top_digit - bottom_digit;
if (result_digit < 0) // is result less than zero?
{
result_digit += 10; // we need to borrow
borrow = true; // remember we borrowed for next time
}
else
{
borrow = false; // remember we didn't borrow for next time
}
...
}

Now a question, what do you need it means if at the end of the whole loop
borrow is true. What does that mean in terms of the two numbers?

3) Your final number ends up in the opposite direction from your first two
numbers. The first two lists are smallest number first. The final list is
largest number first. You are go to have to write some code to reverse a
list.

When you finish you will need to write some code to reverse the final list.

4) The code is a god-awful mess. Try to write a few functions. Things like

link* input_number();

void print_number(link* num);

link* subtract_numbers(link* top, link* bottom);

link* reverse_list(list* l);

Doing this will help you complete the assignment because it will force you
to organise your thoughts a little better. Also choosing better variable
names will help you for exactly the same reason.

john
Jul 22 '05 #9

This discussion thread is closed

Replies have been disabled for this discussion.