visitor (0 QPoints)
  • FR
  • EN
  • NL
  • DE
  • ES
316 experts, 1194 registered users, 1659 questions already answered
European Experts Exchange, the very best site for high-quality IT solutions

New Improved Search!

 


05/10/2011 1h30 : Steve Jobs is dead, the father of Apple ][ is gone, we are all orphaned.

Algorithms :: Sorting :: Sorting Link List
By: FiatLink Belgium  Date: 28/02/2003 00:00:00  English  Points: 50 Status: Answered
Quality : Excellent
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


_________________________________________________________
By: VGR Date: 28/02/2003 09:51:00 English  Type : Answer
yes, it's cryptic because you don't use Pascal/TurboPascal/Delphi/Kylix ;-)

OK, pointers :
-think of them (I hear the wolves coming :D ) as addresses in memory, that is basically a pointer on a variable of type, let's say, integer, is the address of the memory block containing the integer value. This isn't completely true, but serves the purpose of explaining the basics of pointers.
In Pascal/C this would be written :
Var i : Integer;
pti : ^Integer;
or in C :
int i, *pti;

-you should think of pointers as TYPED pointers, that is a ^Integer is not the same entity as a ^Record (struct in C), even if on the same platform, both occupy X bytes (4 on 32bits systems) and are sometimes (C) assignation-compatible. They should not be. At least not without a typecast, for your mental sake. Think of them as "accessors" to types variables.

-Taking a int* or ^Integer variable named pti, you asisgn it an integer value by writing :
pti^:=2;
or in C :
pti* = 2;

This is called "dereferencing" a pointer variable

-pointers are especially useful for dealing with memory structures repeated an unknown number of times (that is, an array/vector won't fit) or sparsely (arrays would waste memory, arrays are a "dense" memory block)

-they are thus used to build the wonderful constructs called "lists", "single-chained lists" and "double-chained lists"

-the only modification they induce compared to an array/vector is :
a) you don't directly access the memory structure, you dereference first the relevant pointer
b) you don't increment/decrement a loop counter to skip forwards and backwards, but you just skip to the next structure by following the adequate pointer, present in the structure.

An example (incomplete but "speaking enough" IMHO)
(sorry in case of typos, I type this on-the-fly)
(in Pascal, I find this clearer)

Type TreeNode = Record // a simple struct
element : String;
previous, next : PTreeNode;
End; // Record
PTreeNode = ^TreeNode; // pointer

Var TreeRoot, current : PTreeNode;

Begin // Main
// create the root
TreeRoot:=New(PTreeNode); // allocate new structure
With TreeRoot^ Do Begin
element:='some text';
next:=Nil;
previous := Nil;
End; // With
// now create a child
current:=New(PTreeNode);
current^.element:='I''m a child';
// prune this as a child of TreeRoot
current^.previous:=TreeRoot;
// here you can create the other children and build your tree, not forgetting to set pointers next and previous to Nil or to the PTreeNode you want ; sometimes it's necessary to memorize one, two, three pointers (for sorting for example)
// now navigate back to father (backwards)
current:=current^.previous;
// you may print out current^ fields, they'll be the ones of TreeRoot ;-)
// deallocate and terminate program
Dispose(current);
Dispose(TreeRoot);
End. // Program
By: TheFalklands Date: 28/02/2003 13:18:00 English  Type : Comment
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;
}
By: TheFalklands Date: 28/02/2003 13:22:00 English  Type : Comment
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..

Do register to be able to answer

©2012 These pages are served without commercial sponsorship. (No popup ads, etc...). Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE.
Please DO link to this page! Post to Twitter Post to Plurk Post to Yahoo Buzz Post to Delicious Post to Digg Post to Facebook Post to MySpace Post to Ping.fm Post to Reddit Post to StumbleUpon

EContact
browser fav
page generated in 383.900170 milliseconds

Why Google AdSense ads ?
compteur
 Ranking-Hits PageRank for this page