Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
?
Solved

Sorting Link List

Posted on 2003-02-28
3
Medium Priority
?
307 Views
Last Modified: 2013-12-14
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
 

_________________________________________________________

0
Comment
Question by:amitpcjain
  • 2
3 Comments
 
LVL 15

Accepted Solution

by:
VGR earned 200 total points
ID: 8045218
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
0
 
LVL 1

Expert Comment

by:ksokolowski
ID: 8045962
 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;
}
0
 
LVL 1

Expert Comment

by:ksokolowski
ID: 8045971
 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..
0

Featured Post

Get expert help—faster!

Need expert help—fast? Use the Help Bell for personalized assistance getting answers to your important questions.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article will inform Clients about common and important expectations from the freelancers (Experts) who are looking at your Gig.
This article will show how Aten was able to supply easy management and control for Artear's video walls and wide range display configurations of their newsroom.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
Progress
Suggested Courses

572 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question