simpleman said:
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
