Solved

Posted on 2006-04-06
Medium Priority
401 Views
Hello, I am adding 2 linked lists. These can be of different lenghts. Below is the sum function. But for some reason the program keeps crashing, and I guess i am missing smth or doing smth wrong in my fucntion. Would you please give me some comment on the function.

void Calculate::sum (Calculate &Number2)
{
int carry = 0;

while (p1 !=NULL && p2 !=NULL )

{

p1->item = p1->item + p2->item + carry;

if (p1->item>=10 )
{
carry=1;
p1->item =(p1->item)-10;
}

else
{
carry=0;
}
p1=p1->next;
p2=p2->next;

}

if ( p1->next == NULL && p2->next !=NULL )
{
while ( p2->next !=NULL )

{
digit *newdigit = new digit();
newdigit->item=p2->item;
p1->next= newdigit;
newdigit->next = NULL;
p1=p1->next;
p2=p2->next;
}
}

if ( carry==1 )

{
digit *newdigit = new digit();
newdigit->item=1;
p1->next = newdigit;
newdigit->next = NULL;
}

}
0
Question by:Gipsy
• 5
• 2

LVL 17

Expert Comment

ID: 16399639
>     if ( p1->next == NULL && p2->next !=NULL )

!= NULL perhaps?

If not, you'll go kaboom, when you dereference the pointer in...

p1->next= newdigit;

Can't comment about the logic otherwise, because I've only scan read it and it has been many years since I messed around with home-grown linked lists.
0

Author Comment

ID: 16399901
you mean if ( p1->next != NULL && p2->next !=NULL ) ?

I wrote it that way because if If p2 is not empty, then i want to copy the rest of p2 to the end of p1.

I forgot to mention that when i add the numbers, they are added with the least significant digit first. When i enter  200, the linked list stores it as 002. So if i want to ad 456 to 32

23
654
----
884, so 4 is just being added to the p1.

0

LVL 17

Expert Comment

ID: 16400049
Look 23 lines down from that if.

You'll see: if ( p1->next == NULL && p2->next !=NULL )

If you look in the scrope that follows you'll see a while loop. In the scope of the while loop, you'll see:

p1->next= newdigit;

That will be deferencing p1, when it is null.
0

LVL 17

Expert Comment

ID: 16400061
No it won't. My apologies. I haven't got my eyes screwed in right today! 8-)
0

LVL 17

Expert Comment

ID: 16400157
OK, here's the problem.

When this loop exits...

while (p1 !=NULL && p2 !=NULL )
{
}

...wither p1 or p1, will be NULL.

You, however, deference them in the next line...

if ( p1->next == NULL && p2->next !=NULL )

... to look at their next values and that will be causing the crash.

My eyes are screwed in properly now I hope. :-)
0

Author Comment

ID: 16401593
rstaveley do you have any suggestion, taking into account what i am trying to do with the code. Thanks,
0

LVL 17

Accepted Solution

rstaveley earned 90 total points
ID: 16411044
If this is an academic exercise in working with linked lists, I can understand why you are uring a home-grown linked list. If this is a real world application, I'd start with looking at existing libraries.

Are you doing this to deal with arbitrarily big integer numbers (i.e. integers with more digits than can be stored in an integer)? If so, and if this isn't an academic exercise, check out http://cvs.sourceforge.net/viewcvs.py/boost-sandbox/boost-sandbox/libs/bigint/ for the Boost sandbox implementation for big integers. You'll also find an implementation at http://groups.yahoo.com/group/boost/files/big_int/ which is also been put forward for Boost. Both of these provide a full suite of integer operations (i.e. addition, subtraction, multiplication and division).

If you are setting out to do something else, consider using the standard library for the linked list. Look at std::list<> for a robust linked list implementation, but consider std::vector<>, because that gives you random access to digits.

If this is an academic exercise, mastering linked lists etc, consider the loop exit condition for....

while (p1 !=NULL && p2 !=NULL )

....when Number2 is longer than `this`. You will have fallen off the end of the linked list for `this`. Either you want to keep a previous digit link or you want to exist the while loop, when next is NULL.

But, here's a quick and dirty std::vector<> illustration to illustrate how much easier it is to work with the standard library, prettied up with a bit of operator overloading:
--------8<--------
#include <iostream>
#include <string>
#include <vector>
#include <iterator>

class BigNum;
std::ostream& operator<<(std::ostream&,const BigNum&);

class BigNum {
std::vector<char> arr;
friend std::ostream& operator<<(std::ostream&,const BigNum&);
friend BigNum operator+(const BigNum& a,const BigNum& b);
public:
BigNum(const std::string& str) : arr(str.rbegin(),str.rend()) {}
BigNum() {}
};

// Display the big number on an output stream
std::ostream& operator<<(std::ostream& os,const BigNum& dn)
{
copy(dn.arr.rbegin(),dn.arr.rend(),std::ostream_iterator<char>(os));
return os;
}

BigNum operator+(const BigNum& a,const BigNum& b) {
BigNum c;
bool carry = false;
int count = a.arr.size() > b.arr.size() ? a.arr.size() : b.arr.size();
for (int i = 0;i < count;++i) {
char digit_a = i < a.arr.size() ? a.arr[i]-'0' : 0;
char digit_b = i < b.arr.size() ? b.arr[i]-'0' : 0;
char digit_c = digit_a+digit_b+(carry?1:0);
carry = digit_c > 9;
c.arr.push_back('0'+digit_c%10);
}
if (carry)
c.arr.push_back('1');
return c;
}

int main()
{
BigNum a("123456789012345678901234567890");
BigNum b("11");
BigNum c("900000000000000000000000000000");
std::cout << a << " + " << b << " = " << a+b << '\n';
std::cout << b << " + " << a << " = " << b+a << '\n';
std::cout << c << " + " << a << " = " << c+a << '\n';
}
--------8<--------

The only thing funky about this, is the use of reverse iterators rbegin/rend to get the least signiificant digit stored first; notice that the vector constructor uses it from std::string, and the ostream& operator<<() also uses it.

[NB: Any other C++ expects reading this will flame me for not implemementing operator+() in terms of operator+=() with a temporary. In your own implementation, your sum function is operator+=() rather than operator+().]
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.htā¦
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilationā¦
The viewer will learn how to synchronize PHP projects with a remote server in NetBeans IDE 8.0 for Windows.
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
###### Suggested Courses
Course of the Month14 days, 15 hours left to enroll