?
Solved

Sorting Link List

Posted on 2003-02-28
3
Medium Priority
?
296 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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 MongoDB database support online, now!

At Percona’s web store you can order your MongoDB database support needs in minutes. No hassles, no fuss, just pick and click. Pay online with a credit card. Handle your MongoDB database support now!

Question has a verified solution.

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

In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
What do responsible coders do? They don't take detrimental shortcuts. They do take reasonable security precautions, create important automation, implement sufficient logging, fix things they break, and care about users.
This video will show you how to get GIT to work in Eclipse.   It will walk you through how to install the EGit plugin in eclipse and how to checkout an existing repository.
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Suggested Courses

770 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