Board index » cppbuilder » Insert Linked List function

Insert Linked List function


2004-05-11 10:40:12 AM
cppbuilder6
Hey. For our final project, my teacher wants us to implement our own
class for creating polynomials. The user enters two numbers and the
menu calls the insert function, and I'm having some problems getting it
to work.
I need it to check every node in the series, inserting the new one
before one with a higher exponent, adding the coefficients if they're
the same, and deleting any nodes with a zero coefficient.
I'm only including the private members and the insert function to cut
down on size. I'd really appreciate any help I could get.
class Polynomial
{
private:
struct Chain
{
int co;
int exp;
Chain *next;
};
Chain *head;
};
void Polynomial::Insert(int co, int exp)
{
Chain *newNode, *nodePtr;
newNode = new Chain;
newNode->co = co;
newNode->exp = exp;
newNode->next = NULL;
if(newNode->co == 0)
{
delete newNode;
return;
}
if(head == NULL)
{
head = newNode;
}
else
{
nodePtr = head;
while (nodePtr != NULL)
{
if(newNode->exp>nodePtr->exp)
{
// Really need some help here.
}
else if(nodePtr->exp == newNode->exp)
{
nodePtr->co = newNode->co + nodePtr->co;
delete newNode;
break;
}
if(nodePtr->co == 0)
{
delete nodePtr;
break;
}
nodePtr = nodePtr->next;
}
}
}
 
 

Re:Insert Linked List function

Greg Davidson < XXXX@XXXXX.COM >writes:
Quote
class Polynomial
{
private:
struct Chain
{
int co;
int exp;
Chain *next;
};
Chain *head;
};
I'd suggest adding a constructor to Chain that takes 2 int parameters,
used to initialize co and exp;
Quote
void Polynomial::Insert(int co, int exp)
{
Chain *newNode, *nodePtr;

newNode = new Chain;
newNode->co = co;
newNode->exp = exp;
newNode->next = NULL;
If Chain had a constructor, then this would be replaced by
newNode = new Chain(co, exp);
But it's not a good idea to create this here. Looking ahead, you have
3 code paths that simply delete this object, undoing the work done
here. A better approach would be to create the object closer to where
it's actually needed, so in the paths where you currently delete the
object, you don't have to. The less mess you make, the less cleanup
there is, and removing waste reduces runtime overhead.
Quote
if(newNode->co == 0)
{
delete newNode;
return;
}
Then this would just be a return, no delete.
Quote
if(head == NULL)
{
head = newNode;
}
Then this would be an assignment
head = new Chain(co, ex0:
Quote
else
{
nodePtr = head;
while (nodePtr != NULL)
{
if(newNode->exp>nodePtr->exp)
{
// Really need some help here.
}
else if(nodePtr->exp == newNode->exp)
{
nodePtr->co = newNode->co + nodePtr->co;
delete newNode;
break;
}
if(nodePtr->co == 0)
{
delete nodePtr;
break;
}
nodePtr = nodePtr->next;
}
}
}
Again, this would all benefit from creating new nodes only in the
cases where they're needed.
I don't think your logic above covers all the cases either, to do what
you're wanting. You handle the case where the co is 0 and where the
exp is the same. Before the loop, if the exp < head, then you have a
new head and don't need to enter the loop at all.
But for the case where newNode->exp>nodePtr->exp, all you know by
that test is that the newnode somes *SOMEPLACE* after the "current
node". Otherwise, you're going to keep advancing (remembering the
current node as the node previously viewed) until you find where
newnode is NO LONGER greater than the next. Once found, you stick the
new node after prev and before next. Further, if you reach the end,
then just insert this after prev without modifying next.
There is no reason to check nodePtr->co == 0 inside the loop. Check
that before the loop. (Though you'd just check co and not
nodePtr->co, since you're going to follow my advice and only create
nodePtr when you have found a place to insert it. Riiight? :)
Hope this gives you some ideas.
--
Chris (TeamB);
 

Re:Insert Linked List function

"Chris Uzdavinis (TeamB)" wrote:
Quote
Hope this gives you some ideas.
That it did; thanks for your help. Now I just need to get the
overloaded assignment operators to return what I want.
 

{smallsort}