linked list, overloading, operator +

namehere's Avatar, Join Date: Jul 2008
Newbie Member
Im trying to put together a a polynomial calculator to perform simple arithmatic operations on short polynomials.

I decided to represent each polynomial as a linked list of terms.My problem is that the program crashes on the statment r=p+q where each is a polynomial object. The crash seems to take place within the function operator=, however it works fine on statments such as p=q or r=p. Before the return statment within operator+ the values of the return object show to be correct so it seems as if the problem is in passing the return object to operator=.Here it is..
Code:
struct term
{
	double a;
	int b;
	int sign;
	term* next;
	term(const double c, const int e, const int s);
};

class polynomial
{
public:
	polynomial();
	polynomial(const polynomial&);
	
	~polynomial();
	void read();
	void print();
	const polynomial& operator=(const polynomial& p);
	polynomial operator+(const polynomial& p)const;
	//polynomial operator-(const polynomial&)const;
	//polynomial operator*(const polynomial&)const;
	//polynomial operator/(const polynomial&)const;

private:
	//void sort();
	void clear();
	void copy(const polynomial&);
	term* first;
	
};
 

term::term(const double c, const int e, const int s)
{
	a=c;
	b=e;
	sign=s;
	next=NULL;
}
polynomial::polynomial()
{
	first=NULL;
}
void polynomial::copy(const polynomial& original)
{
	if(first!=NULL)
		clear();

	term* temp1= original.first;
	first=new term(original.first->a,original.first->b,original.first->sign);
	term* temp2=first;
	for(temp1=temp1->next;temp1!=NULL;temp1=temp1->next){
		temp2->next=new term(temp1->a,temp1->b,temp1->sign);
		temp2=temp2->next;}
	
}
polynomial::polynomial(const polynomial& original)
{
	copy(original);
}
void polynomial::clear()
{
	term* temp=first;
	while(temp!=NULL)
	{
		first=first->next;
		delete temp;
		temp=first;
	}
}
polynomial::~polynomial()
{
	clear();
}
void polynomial::read()
{
	double x;
	int y,s;
	
	term* temp;
	char punc,op;
	cout<<"Enter terms, include the degree of each term:";
	
	cin>>x;
	cin>>punc>>punc;
	cin>>y;
	s=1;
	
	first=new term(x,y,s);
	
	temp=first;
	
	cin>>op;
	cin>>x;
	cin>>punc>>punc;
	cin>>y;
		if(op=='-')
		s=-1;
	else
		s=1;
	while(x>0)
	{
	temp->next=new term(x,y,s);
	temp=temp->next;
	cin>>op;
	cin>>x;
	cin>>punc>>punc;
	cin>>y;
		if(op=='-')
		s=-1;
	else
		s=1;
	}
}

//void polynomial::sort()
//{
	
//}
void polynomial::print()
{
	term* temp1=first->next;
	if(first->sign==-1)
		cout<<'-';
	cout<<first->a<<"x^"<<first->b;
	while(temp1!=NULL)
	{
		if(temp1->sign==-1)
			cout<<'-';
		else
			cout<<'+';
		cout<<temp1->a<<"x^"<<temp1->b;
		temp1=temp1->next;
	}
}
const polynomial& polynomial::operator=(const polynomial& p)
{
	cout<<'2'<<endl;
	term* temp1;
	term* temp2;
	
	if(first!=NULL)
		clear();
//crash here
cout<<'3'<<endl;
first=new term(p.first->a,p.first->b,p.first->sign);
cout<<'4'<<endl;
temp1=first;
	
temp2=p.first->next;
	
while(temp2!=NULL)
	{
		temp1->next=new term(temp2->a,temp2->b,temp2->sign);
		temp1=temp1->next;
		temp2=temp2->next;
	}
return *this;
}
polynomial polynomial::operator+(const polynomial& p)const
{
	polynomial sum;
	int tempSign;
	term* temp1;
	term* temp2;
	//term* tempNew=sum.first;

	if(first->b==p.first->b)
	{
		if((first->a*first->sign+p.first->b*p.first->sign)<0)
			tempSign=-1;
		else
			tempSign=1;

		sum.first=new term(abs(first->a*first->sign+p.first->a*p.first->sign),first->b,tempSign);
		temp1=first->next;
		temp2=p.first->next;
	}
	else if(first->b>p.first->b)
	{
		sum.first=new term(first->a,first->b,first->sign);
		temp1=first->next;
	}
	else if(first->b<p.first->b)
	{
		sum.first=new term(p.first->a,p.first->b,p.first->sign);
		temp2=p.first->next;
	}
//values of sum are correct. 
	cout<<sum.first->a<<' '<<sum.first->b<<' '<<sum.first->sign<<endl;
	cout<<'1'<<endl;
	return sum;
//omit further terms



	//while(temp1!=NULL)
	//{
		//if(temp1->b==temp2->b){
		//if((temp->a*temp->sign+temp2->b*temp2->sign)<0)
			//temp3->next->sign=-1;
		//else
			//temp3->next->sign=1;

		//temp3->next->a=abs(temp1->a*temp1->sign+temp2->b*temp2->sign);
		//temp1=temp1->next;
		//temp2=temp2->next;
	//}
	//else if(temp1->b>temp2->b)
	//{

	//}
}
void main()
{
	polynomial p,q,r;
	p.read();
	p.print();
	cout<<endl;

	q.read();
	q.print();
	cout<<endl;
	r=p+q;
	r.print();
	
	cout<<endl;
	
}

Last edited by shabbir; 17Aug2008 at 10:10.. Reason: Code block
0
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
How do you enter data, for example if I'm entering 3x^2+2x-50, what do I type at the keyboard?
0
xpi0t0s's Avatar, Join Date: Aug 2004
Mentor
OK, worked it out, you need to add a "terminating NULL" - very C-like!
3x^2+2x^1-50x^0+0x^0
5x^1+25x^0+0x^0

Meaningful variable names would help a lot. a and b don't mean anything, but if you used something like term and power then that would make the code a lot clearer.

In situations like this I add a shedload of debugging printf statements showing clearly what's going on. In this case the crash is in polynomial::clear() after it's evaluated p+q (which isn't complete, by the way). So the crash probably has something to do with the temporary object the compiler creates. If you add a printf indicating what function you're in and what "this" is then that will shed a lot of light on what's happening. For example printf("polynomial ctor, this=%p\n",this); in the default constructor (polynomial::polynomial()) will show when a new object is created and where it is - the latter is useful in distinguishing different objects.

So with this debug added I get the following output:

polynomial ctor(), this=0012FE80
polynomial ctor(), this=0012FE74
polynomial ctor(), this=0012FE68
polynomial::read(), this=0012FE80
Enter terms, include the degree of each term:3x^2+2x^1-50x^0+0x^0
polynomial::print(), this=0012FE80
3x^2+2x^1-50x^0
polynomial::read(), this=0012FE74
Enter terms, include the degree of each term:5x^1+25x^0+0x^0
polynomial::print(), this=0012FE74
5x^1+25x^0
polynomial op+(const polynomial& p), this=0012FE74
polynomial ctor(), this=0012FD50
3 2 1
1
polynomial ctor(const polynomial& original=0012FD50), this=0012FD9C
polynomial::copy(const polynomial& original=0012FD50), this=0012FD9C
polynomial::clear(), this=0012FD9C

and further, stepping through the Visual Studio 2005 debugger, I find there is a problem on term* temp=first; where first is 0xcccccccc - which is the value VS2005 debugger puts in uninitialised memory, which could explain why you think the crash is in polynomial::operator=(const polynomial& p). ALWAYS ALWAYS ALWAYS initialise stuff you rely on! In this case all it takes is "first=0;" in BOTH polynomial constructors, to save you a lot of debugging time, because then the crash occurs when you dereference the NULL pointer, not some time after.

Oddly though when I add first=0 to the constructor polynomial::polynomial(const polynomial& original) and step through to the same line, first is not NULL as I expected but points to the 3x^2 term from the first polynomial. Not sure therefore what exactly has happened here. However the return sum in polynomial::operator+ returns an object whose first is NULL.

How odd. With first uninitialised, the program crashes out because it ends up pointing at something undefined. With first initialised to NULL it seems to work OK (except as already mentioned that operator+ is incomplete). The complete output from my debug version of the program then is:

polynomial ctor(), this=0012FE80
polynomial ctor(), this=0012FE74
polynomial ctor(), this=0012FE68
polynomial::read(), this=0012FE80
Enter terms, include the degree of each term:3x^2+2x^1-50x^0+0x^0
polynomial::print(), this=0012FE80
3x^2+2x^1-50x^0
polynomial::read(), this=0012FE74
Enter terms, include the degree of each term:5x^1+25x^0+0x^0
polynomial::print(), this=0012FE74
5x^1+25x^0
polynomial op+(const polynomial& p), this=0012FE74
polynomial ctor(), this=0012FD50
3 2 1
1
polynomial ctor(const polynomial& original=0012FD50), this=0012FD9C
polynomial::copy(const polynomial& original=0012FD50), this=0012FD9C
polynomial dtor, this=0012FD50
polynomial::clear(), this=0012FD50
polynomial op=(const polynomial& p), this=0012FD9C
2
3
4
polynomial dtor, this=0012FD9C
polynomial::clear(), this=0012FD9C
polynomial::print(), this=0012FE68
3x^2

If you take the debug printf statement approach, note you have to take the address of anything passed in by reference, for example printf("polynomial::copy(const polynomial& original=%p), this=%p\n",&original,this); Here original is passed by reference rather than by name, and in C++ passing by reference uses the same semantics as passing by value, hence the need to take the address as in &original.

Last edited by xpi0t0s; 17Aug2008 at 17:29.. Reason: convert smilies back to proper text, in code :( really means colon open bracket