By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,949 Members | 950 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,949 IT Pros & Developers. It's quick & easy.

Question: Adding nodes to sorted linked list

P: n/a
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);

}
Nov 14 '05 #1
Share this Question
Share on Google+
5 Replies


P: n/a
On Mon, 22 Dec 2003 05:24:50 UTC, "CR" <fa*******@adelphia.net> wrote:
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.
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);

}

--
Tschau/Bye
Herbert

Visit http://www.ecomstation.de the home of german eComStation

Nov 14 '05 #2

P: n/a
The Real OS/2 Guy <os****@pc-rosenau.de> spoke thus:
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...
skipname: /* SKIP THE FILE IF DUPLICATES ARE FOUND */
return(0);
}

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org | don't, I need to know. Flames welcome.
Nov 14 '05 #3

P: n/a
On Mon, 22 Dec 2003 15:02:50 UTC, Christopher Benson-Manica
<at***@nospam.cyberspace.org> wrote:
The Real OS/2 Guy <os****@pc-rosenau.de> spoke thus:
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...
skipname: /* SKIP THE FILE IF DUPLICATES ARE FOUND */
return(0);
}


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.

--
Tschau/Bye
Herbert

Visit http://www.ecomstation.de the home of german eComStation

Nov 14 '05 #4

P: n/a

"CR" <fa*******@adelphia.net> wrote in message
news:Ce********************@news1.news.adelphia.ne t...
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



Nov 14 '05 #5

P: n/a

"Brian MacBride" <ma******@ix.netcom.com> wrote in message
news:bs************@ID-26770.news.uni-berlin.de...

"CR" <fa*******@adelphia.net> wrote in message
news:Ce********************@news1.news.adelphia.ne t...
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)

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;
}
Regards

Brian

Nov 14 '05 #6

This discussion thread is closed

Replies have been disabled for this discussion.