Quick Question in Linked List

[AmmmG 01]

Could someone see why my check bigger doesn't work?
In a sense that if I say 2000 - 4000 it works,
but if the first number is bigger (4000 - 2000) it doesn't work.
my project presentation is in 6 hours, I hope you guys do this one
for me....I have worked hard on this one!!!!

Appreciated.

#include <iostream>
#include <string>
using namespace std;
class Node
{
public:
        int val;
        Node * next;
        Node(){val=0;next=NULL;}
        Node(int v){val=v;next=NULL;}
};
void AddHead(Node*& h, int v)
{
        Node *a = new Node(v);
        a->next = h;
        h=a;
}
void Print(Node *h)
{
        while(h)
        {
                cout<<h->val;
                h=h->next;
        }
}
int Length(Node *h)
{
        int i=0;
        while(h)
        {
                i++;
                h=h->next;
        }
        return i;
}
void DeleteHead(Node*&h)
{
        if(!h) return;
        Node *t = h;
        h=h->next;
        delete t;
}
  void Plus(Node* a, Node* b, Node* c)
{
        Node*head=NULL;
        int ans=0;
        while(a && b)
        {
                ans = a->val+b->val;
                if(!a->next)
               {
                  AddHead(head, ans);
                a=a->next;
                b=b->next;
                  break;
               }
               if(ans>=10)
                {
                        ans=ans-10;
                      if(a->next) a->next->val++;
                }
                AddHead(head, ans);
                a=a->next;
                b=b->next;
        }
        while(a)
        {
                AddHead(head, a->val);
                a=a->next;
        }
        while(b)
        {
                AddHead(head, b->val);
                b=b->next;
        }
        Print(head);
 delete a,b,c;
}
void Minus(Node* a, Node* b, Node* c)
{
   
Node*head=NULL;
        int ans=0;
        while(a && b)
        {
  if(a->val-b->val<0)
    {
       a->val=a->val+10;
       a->next->val--;
       ans = a->val-b->val;
    }
   else
    {
    ans = a->val-b->val;
    }
    AddHead(head, ans);
    a=a->next;
    b=b->next;
  }
        while(a)
        {
                AddHead(head, a->val);
                a=a->next;
        }
        while(b)
        {
                AddHead(head, b->val);
                b=b->next;
        }
        Print(head);
		delete a,b,c;
}
bool CheckBigger(Node*a, Node* b)
{
    if (a->val > b->val)
    return true;
    else if( a->val < b->val)
    return false;
    a=a->next;
	b=b->next;

}

int main()
{
        Node* answer = NULL;
        string num1="", num2="";
        char ansdo, ansop;
        do{
        cout<<"Enter the first number:";
        cin>>num1;
         const char *in = num1.c_str();
        int i=0;
        Node * head1 = NULL;
        while(in[i]!='\0')
        {
                int value = in[i]-'0';
                AddHead(head1, value);
                i++;
        }
         cout<<"Enter the second number:";
        cin>>num2;
         const char *in2 = num2.c_str();
        int j=0;
        Node * head2 = NULL;
        while(in2[j]!='\0')
        {
                int value = in2[j]-'0';
                AddHead(head2, value);
                j++;
        }
 
         cout<<"Enter + to add or - to subtract: ";
        cin>>ansop;
       
        if ( ansop == '+')
        {
        Plus(head1,head2,answer);
        Print(answer);
cout<<endl;
        }
    else if (ansop == '-')
        {
            if (Length(head1)>Length(head2))
                {
                Minus(head1,head2,answer);
                Print(answer);
                }
            else if (Length(head1)<Length(head2))
                {
                  Minus(head2,head1, answer);
                  Print(answer);
               }
           else
             if (CheckBigger(head1, head2))
             {
                Minus(head1,head2,answer);
               Print(answer);
             }
          else
             {
              Minus(head2,head1, answer);
                  Print(answer);
             }
          
           cout<<endl;
       }
        else cout<<"Wrong Input!"<<endl;
       
        cout<<"Would you like to repeat the calculation? <Y to repeat>:";
        cin>>ansdo;
} while(ansdo == 'y' || ansdo == 'Y');
         return 0;
 
}

[kkhalaf]

in your Minus() function

this is the correct logic for your while(a && b) loop

while (a && b)
	{
		if (a->val - b->val<0)
		{
			ans = b->val - a->val;
		}
		else
		{
			ans = a->val - b->val;
		}
		AddHead(head, ans);
		a = a->next;
		b = b->next;
	}

[AmmmG 01]

Hi khalaf,
I just tried your code and added it to my code yet it doesn't work,
maybe I implemented your code in the wrong line.
Could you implement it yourself and then show the full code to me,

Thanks!

[kkhalaf]

It's working for me. look at your minus function, there is that while (a && b) loop. Then check mine.

Don't add my code to yours, change yours to look like mine.

void Minus(Node* a, Node* b, Node* c)
{

	Node*head = NULL;
	int ans = 0;
	while (a && b)
	{
		if (a->val - b->val<0)
		{
			ans = b->val - a->val;
		}
		else
		{
			ans = a->val - b->val;
		}
		AddHead(head, ans);
		a = a->next;
		b = b->next;
	}
	while (a)
	{
		AddHead(head, a->val);
		a = a->next;
	}
	while (b)
	{
		AddHead(head, b->val);
		b = b->next;
	}
	Print(head);
	delete a, b, c;
}

Enter the first number:4
Enter the second number:2
Enter + to add or - to subtract: -
2
Would you like to repeat the calculation? <Y to repeat>:y
Enter the first number:2
Enter the second number:4
Enter + to add or - to subtract: -
2
Would you like to repeat the calculation? <Y to repeat>:

Good luck

[dhayden]

Main() seems to think that Plus() and Minus() modify their 3rd argument but they don't. In fact they delete it. This is why it's a good idea to put a comment at the top of your functions to describe exactly what they are supposed to do. I suggest you change Plus() to:

// Add the numbers in a and b, returning the result
Node * Plus(Node* a, Node* b)

and then in main() you can do this:

answer = Plus(head1, head2);
Print(answer);

Plus() is a mess:
Line 52: what if ans >= 10? You'll be putting a digit value of 10-19 in the answer.
Line 68: Same problem.
Line 60: You're changing one of the numbers that was passed in! That's a very bad idea. Imagine how hard it would be to write code if x = a+b changed a or b.

Basically you have to deal with the carry on each digit.

// Add the numbers in a and b, returning the result
Node * Plus(Node* a, Node* b)
{
    Node*head=NULL;
    int ans=0;
    int carry = 0;
    while(a && b)
        {
            ans = a->val+b->val+carry;
            if(ans>=10) {
                ans=ans-10;
                carry = 1;
            } else {
                carry = 0;
            }
            AddHead(head, ans);
            a=a->next;
            b=b->next;
        }

    // There may be more digits in one of the numbers. Point 'a'
    // to the one with (possibly) more digits
    if (a == NULL) a = b;
    while(a)
        {
            ans = a->val + carry;
            if(ans>=10) {
                ans=ans-10;
                carry = 1;
            } else {
                carry = 0;
            }
            AddHead(head, a->val);
            a=a->next;
        }
    if (carry) {
        AddHead(head, carry);
    }
    return head;
}

Minus() has the same problems.

Something important to note: Plus() and Minus() take their arguments with the least significant digit at the head of the list, but they create their result with the least significant digit at the tail of the list! This means that Print() is real easy, but in any sort of Production system this wouldn't be acceptable.

CheckBigger() only compares one digit. What if that digit is the same but the next one is different? Remember, the numbers you're comparing are stored with the least significant digit first. Also, since main() is really just interested in which digit is larger, you can combine Length() and CheckBigger() into one function, but it requires recursion. Are you familiar with that? Here is pseudo-code for what I have in mind:

// Compare the numbers a and b. Return a negative number, 0, or a positive number
// depending on whether a is less than, equal to, or greater than b.
int compare(Node*a, Node* b)
{
    // The idea here is to compare the more significant digits first. If they
    // are all equal then use the current digit in an attempt to break the tie
    if (a and b are null) {
        return 0. you reachec the end of two numbers with the same number of digits
    else if (b == NULL) {
        return 1. A has more digits than b
    else if (a == NULL) {
        return -1. B has more digits.
    }

    // if you get here then a and b are not null. Compare the more significant digits
    int result = compare(a->next, b->next);
    if (result == 0) {  // More significant digits are all the same.
        result = a->val - b->val;    // break the tie
    }
    return result;
}

If you do this then the code for subtracting in main() becomes:

                if compare(head1, head2) < 0) {
                    answer = Minus(head2, head1);
                } else {
                    answer = Minus(head1, head2);
                }
                Print(answer);

I Hope this helps.

[cire]

kkhalaf wrote:

Don't add my code to yours, change yours to look like mine.

delete a, b, c;

That doesn't do what you think it does. It is equivalent to:

    delete a;
    b;
    c;

where the last two statements are essentially no-ops.