asked on

Sorting Link List

sorting a link list:

Hi I have made a class called Pipes and I want to sort the pipes based on their id.

the pipe with the lowest material id comes on top.

I am unable to figure out a way.

can somebody tell me how to sort a link list.

2.How to check for uniqueness of ID, i.e ID which has been added once cannot be added again

3.Do I have regular-expressions in C++ . So That I can format my material ID as

SS304 or SS316 i,e a string with first two characters as letters and last 3 characters as numbers

---------------------- Imp -----------------

This is not a homework problem, but a problem for my research. I am using C++ in my thermo hydraulics code. The problem is that I have used visual basic and Java Script but never C++ to change fortran codes.

My current job involves code conversion of fortran 77 and making it more maintainable

_________________________________________________________

ASKER CERTIFIED SOLUTION

VGR

membership

This solution is only available to members.

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

Start Free Trial

ksokolowski

The thing with linked lists, is that they lend themselves to inserting elements in sorted order O(n) vs O(nlogn)

For example..

void sortedInsert(struct pipe *newPipe, struct pipe **startlist, struct pipe **endlist)

{
struct pipe *oldPipe, *pPipe;
ppipe=*startlist;
if (!*endlist)
{
newPipe->next = NULL;
*endlist = newPipe;
*startlist = newPipe;
return;
}
oldPipe=NULL;
while(pPipe)
{
if (pPipe->ID < newPipe->ID)
{
oldPipe = pPipe;
pPipe = pPipe->next;
}
else
{
if (oldPipe) /* we want to add a new node
after old pipe and before pPipe*/
{
oldPipe->next=newPipe;
newPipe->next=pPipe;
return;
}
/* Otherwise we want to insert it right at the
start of the list */
newPipe->next=pPipe;
*startlist = newPipe;
return;
}
}
(*endlist)->next=newPipe; /* stick it on the end */
newPipe->next=NULL;
*endlist=newPipe;
}

ksokolowski

To assign a unique ID, you can just traverse the list, and look at each existing ID to see if it is in use already... OR, just use an incremental ID, so the new ID will be +1 over the last.. Like a SQL identity, or Access Autonumber..