Question: Adding nodes to sorted linked list

C

CR

I've been to figure out how to get AddSortLast function to add nodes in
acsending order (a b c d)
I figured it out how to get it to sort in decending order but I can't get it
to sort in acsending order by flipping
the < sign to a > sign like I thought I could. Any suggestions or
improvements would be greatly appreciated.
typedef struct /* file data structure */
{
string_f firstName;
string_l lastName;
char gender;
char rate;
int tenure;
float salary;
char raise;
int rec;
} data;

typedef struct node *pointer_t; /* pointer to node */

typedef struct node /* node data structure */
{
data e;
pointer_t pNodeNext;
} NODE;

typedef struct list /* list data structure */
{
pointer_t head;
int rec;
} LinkedList;

int AddSortFirst(LinkedList *pList, data e)
{
NODE * pNodeCurrent;
NODE * pNodeNew;
NODE * pNodePrevious;

pNodeNew = (NODE *)malloc(sizeof(NODE));

if (pNodeNew == NULL)
return(0);

pNodeNew->pNodeNext = NULL;
pNodeNew->e = e;

pNodePrevious = NULL;
pNodeCurrent = pList->head;

/* CHECK LIST FOR DUPLICATES */
while(pNodeCurrent != NULL)
{
if((strcmp(pNodeNew->e.firstName,
pNodeCurrent->e.firstName))==0)
goto skipname; /* SKIP THIS NAME IT ALREADY EXISTS IN LIST
*/
pNodeCurrent = pNodeCurrent->pNodeNext;
}
/* REINITIALIZE pNodeCurrent TO START OF LINKED LIST */
pNodeCurrent = pList->head;

while ((pNodeCurrent != NULL) && (strcmp(pNodeNew->e.firstName,
pNodeCurrent->e.firstName))>0)
{
pNodePrevious = pNodeCurrent;
pNodeCurrent = pNodeCurrent->pNodeNext;
}

if (pNodePrevious != NULL)
{
pNodeNew->pNodeNext = pNodePrevious->pNodeNext;
pNodePrevious->pNodeNext = pNodeNew;
}
else
{
pNodeNew->pNodeNext = pList->head;
pList->head = pNodeNew;
}
return(1);

skipname: /* SKIP THE FILE IF DUPLICATES ARE FOUND */
return(0);

}
int AddSortLast(LinkedList *pList, data e)
{
NODE * pNodeCurrent;
NODE * pNodeNew;
NODE * pNodePrevious;

pNodeNew = (NODE *)malloc(sizeof(NODE));

if (pNodeNew == NULL)
return(0);

pNodeNew->pNodeNext = NULL;
pNodeNew->e = e;

pNodePrevious = NULL;
pNodeCurrent = pList->head;

while(pNodeCurrent != NULL)
{
if((strcmp(pNodeNew->e.firstName,
pNodeCurrent->e.firstName))==0)
goto skipname; /* SKIP THIS NAME IT ALREADY EXISTS */
pNodeCurrent = pNodeCurrent->pNodeNext;
}
pNodeCurrent = pList->head;

/* WHAT AM I MISSING IN ORDER TO SORT IN ASCENDING ORDER LIKE IN
AddSortFirst() ? */
while ((pNodeCurrent != NULL) && (strcmp(pNodeNew->e.lastName,
pNodeCurrent->e.lastName))<0)
{
pNodePrevious = pNodeCurrent;
pNodeCurrent = pNodeCurrent->pNodeNext;
}

if (pNodePrevious != NULL)
{
pNodeNew->pNodeNext = pNodePrevious->pNodeNext;
pNodePrevious->pNodeNext = pNodeNew;
}
else
{
pNodeNew->pNodeNext = pList->head;
pList->head = pNodeNew;
}

return(1);
skipname:
return(0);

}
 
T

The Real OS/2 Guy

int AddSortFirst(LinkedList *pList, data e)

It's a bad idea to copy the whole struct to a local parameter. Use a
pointer instead.
{
NODE * pNodeCurrent;
NODE * pNodeNew;
NODE * pNodePrevious;

pNodeNew = (NODE *)malloc(sizeof(NODE));

Creats undefined behavior as you've forgotten to #include <stdlib.h>
and you tells the compiler that it has to comvert int (as it things
now malloc returns) to a pointer type.

Never cast the return type of a function that returns a pointer to
void! The only you reashes by the cast is undefined behavior because
int is not a pointer.
if (pNodeNew == NULL)
return(0);

pNodeNew->pNodeNext = NULL;
pNodeNew->e = e;

This copies the data another time.
pNodePrevious = NULL;
pNodeCurrent = pList->head;

/* CHECK LIST FOR DUPLICATES */
while(pNodeCurrent != NULL)
{
if((strcmp(pNodeNew->e.firstName,
pNodeCurrent->e.firstName))==0)
goto skipname; /* SKIP THIS NAME IT ALREADY EXISTS IN LIST
*/

I can't find the destination of the goto. Using goto is BAD!

Another thing is that you has created now a memory leak. You've
allocated a block of memory but forgets its address.

I stop here because too important design errors found yet.
 
C

Christopher Benson-Manica

The Real OS/2 Guy said:
I can't find the destination of the goto. Using goto is BAD!

Well, it's there - just totally unnecessary, since this is all it
is...
 
T

The Real OS/2 Guy

Well, it's there - just totally unnecessary, since this is all it
is...
As said already. Code faild in design by using goto and producing
memory leaks. Code needs redesigned and written from scratch based on
new design.
 
B

Brian MacBride

CR said:
Any suggestions or
improvements would be greatly appreciated.

int AddSortFirst(LinkedList *pList, data e)
{
NODE * pNodeCurrent;
NODE * pNodeNew;
NODE * pNodePrevious;

pNodeNew = (NODE *)malloc(sizeof(NODE));

if (pNodeNew == NULL)
return(0);

pNodeNew->pNodeNext = NULL;
pNodeNew->e = e;

pNodePrevious = NULL;
pNodeCurrent = pList->head;

/* CHECK LIST FOR DUPLICATES */
while(pNodeCurrent != NULL)
{
if((strcmp(pNodeNew->e.firstName,
pNodeCurrent->e.firstName))==0)
goto skipname; /* SKIP THIS NAME IT ALREADY EXISTS IN LIST
*/
pNodeCurrent = pNodeCurrent->pNodeNext;
}
/* REINITIALIZE pNodeCurrent TO START OF LINKED LIST */
pNodeCurrent = pList->head;

while ((pNodeCurrent != NULL) && (strcmp(pNodeNew->e.firstName,
pNodeCurrent->e.firstName))>0)
{
pNodePrevious = pNodeCurrent;
pNodeCurrent = pNodeCurrent->pNodeNext;
}

if (pNodePrevious != NULL)
{
pNodeNew->pNodeNext = pNodePrevious->pNodeNext;
pNodePrevious->pNodeNext = pNodeNew;
}
else
{
pNodeNew->pNodeNext = pList->head;
pList->head = pNodeNew;
}
return(1);

skipname: /* SKIP THE FILE IF DUPLICATES ARE FOUND */
return(0);

}

Mercy...

Consider...

int AddSortFirst (LinkedList *pList, data e) {
NODE **npp = &pList->head, *np = 0;

while (*npp) {
int i = strcmp ((*npp)->e.firstName, e.firstName);
if (!i) /* Duplicate? */
return 0; /* Bail! */

if (i > 0) {
np = *npp;
break;
}
npp = &(*npp)->pNodeNext;
}

*npp = malloc (sizeof **npp);
if (!*npp)
return 0;
(*npp)->e = e;
(*npp)->pNodeNext = np;

return 1;
}

Others have wondered why you don't use a pointer rather than pass a copy of
the whole struct to the function? I wonder whether you need a deep(er) copy
than that provided by the simple assignment....

pNodeNew->e = e; (yours)

.. . . or . . .

(*npp)->e = e; (mine)

Regards

Brian
 
B

Brian MacBride

Brian MacBride said:
Mercy...

Consider...

int AddSortFirst (LinkedList *pList, data e) {
NODE **npp = &pList->head, *np = 0;

while (*npp) {
int i = strcmp ((*npp)->e.firstName, e.firstName);
if (!i) /* Duplicate? */
return 0; /* Bail! */

if (i > 0) {
np = *npp;
break;
}
npp = &(*npp)->pNodeNext;
}

*npp = malloc (sizeof **npp);
if (!*npp)
return 0;
(*npp)->e = e;
(*npp)->pNodeNext = np;

return 1;
}

Others have wondered why you don't use a pointer rather than pass a copy of
the whole struct to the function? I wonder whether you need a deep(er) copy
than that provided by the simple assignment....

pNodeNew->e = e; (yours)

. . . or . . .

(*npp)->e = e; (mine)

Oops... a mental lapse (or too much EggNog?)

Consider...

int AddSortFirst (LinkedList *pList, data e) {
NODE **npp = &pList->head, *np;

while (*npp) {
int i = strcmp ((*npp)->e.firstName, e.firstName);
if (!i) /* Duplicate? */
return 0; /* Bail! */

if (i > 0)
break;

npp = &(*npp)->pNodeNext;
}

np = malloc (sizeof *np);
if (!np)
return 0;
np->pNodeNext = *npp;
np->e = e;
*npp = np;

return 1;
}
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,899
Latest member
RodneyMcAu

Latest Threads

Top