asked on

Problem With Linked List Node

I am having a problem with a section of code. This function accepts a NODE *, and int(number to add) and is supposed to either create a new node if the llist is empty, or if the number is a repeat just increase the counter of the node that is the same, or just add the number to the correct spot in the list. When I go and print out the list everything works fine, except that when a duplicate number is added, its not supposed to create a new node, just increase the counter(which it does do). I am not sure where in the logic it is wrong??? Here is the code Below:

/*==============================================================================
Function: insert_Integer()
Parameters: A pointer to a PNODE, and an int element
Returns: PNODE pointer
Function Calls: create_Node()

Purpose: Creates and inserts and element node in the correct position
Increase count of integer x or insert new node in sorted list.
================================================================================
*/
PNODE insert_integer(PNODE pList, int x)
{

PNODE pPrev, pCur, pNew;
/* Check if we are starting new list. */
if (pList == NULL)
{
pNew = create_node(x);
return pNew;
}
/* Otherwise, find its position and put it there. */
else
{
pPrev = NULL;
pCur = pList;

while ((pCur != NULL) && (pCur->x < x))
{
pPrev = pCur;
pCur = pCur->next;
}

if ((pCur != NULL) && (pCur->x == x))
{
/* Integer has occurred before, increase count. */
pCur->count = pCur->count + 1; <-- should not create a new node just increase counter
}

else if (pPrev == NULL)
{
/* New integer that is smaller up to this point. */
pNew = create_node(x);
pNew->next = pList;
pList = pNew;
}
else
{
/* larger integer goes between pPrev and pCur. */
pNew = create_node(x);
pNew->next = pCur;
pPrev->next = pNew;
}
}//end of first else
return pList;
}

vadim_ti

i think there is no problem in your code, may be you have a problem with your print routine or in test case?

Sabre3487

ASKER

The print routine is as follows:

for{pTemp = pList; pTemp != NULL; pTemp = pTemp->next)
{
for ( x=0; x < pTemp->count; x++)
printf("Num: %d repeats %d\n",pTemp->x,pTemp->count);
}

efn

If you have a node that says there are 3 occurrences of 5, the print routine will output

Num: 5 repeats 3
Num: 5 repeats 3
Num: 5 repeats 3

Is that what you want, or is that the problem?

Sabre3487

ASKER

That is correct, the print out will print all nodes and their counter. Problem is I do not want repeated numbers to even become nodes.

ASKER CERTIFIED SOLUTION

efn

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

efn

That's the inner for statement I was suggesting you delete.

PaulCaswell

Two suggestions:

1. At the point where you create your new list:

...
pNew = create_node(x);
return pNew;
...

you do not change pList but when you add a new node to the start of the list you do:

...
/* New integer that is smaller up to this point. */
pNew = create_node(x);
pNew->next = pList;
pList = pNew;
...

This is slightly inconsistend. I would suggest:

...
pNew = create_node(x);
pList = pNew;
return pNew;
...

2. I think your problem is indeed in the print routine:

for{pTemp = pList; pTemp != NULL; pTemp = pTemp->next)
{
for ( x=0; x < pTemp->count; x++)
printf("Num: %d repeats %d\n",pTemp->x,pTemp->count);
}

should probably be:

for{pTemp = pList; pTemp != NULL; pTemp = pTemp->next)
{
//for ( x=0; x < pTemp->count; x++)
printf("Num: %d repeats %d\n",pTemp->x,pTemp->count);
}

I suspect this is waht efn was suggesting.

Paul

Emms

my approach to your question, if the below is what you want:

node 1, count = 1
node 2, count = 2
node 3, count = 3

during --- if ((pCur != NULL) && (pCur->x == x)) --- let's say at node 2

coding shall logically be;

if ((pCur != NULL) && (pCur->x == x))
count = count + 1; // no need to increment node

========
node 1, count = 1
node 2, count = 2
node 2, count = 3 // increment a count for duplicate integer
node 3, count = 4 // your new node will now start at count = 4
========

let me know if i am in the right track.

cheers - emms

Sabre3487

ASKER

The problem was in the print statement! And I fixed up the logic a bit as well. Thanks.