Data Structures in the real world

Does any one How and when does one apply Data Structures techbiques when one
is programming in a Real World situation.

They are generally used in advanced systems programs such as OS's, Database Management Systems and ERP systems. An example is SQL Server which uses BTrees to manage database records and relationships or some ERP systems which use queues to process sales orders. The CLR which runs .NET applications uses stacks
to keep track of method calls and operands. Generally, in any application where perfomance is crucial, a lot of thought goes into choosing data structures and algorithms that ensure optimal perfomance.

Just to throw something in (a whole five months after the thread was made):

I was reading some text on dynamic memory allocation, the most widespread and implemented heap-manager is Doug Lea malloc (dlmalloc) and most distros in linux either use a beefed up version or one based on the original. Dlmalloc (and variants) have the following functions: malloc(), realloc() and free() amongst others.

this is just another example of data structures being used irl. some implementations (variants) of dlmalloc use a balanced-tree structure (which we'll be doing in our last assignment), to keep track of all the free "chunks" assigned to a bin. And in windows, a linked list is used in the process environment block of every process to keep track of allocations.

Another neat implementation is how windows implements it's "Structured exception handler", which is how WinXp (and probably Vista) are able to handle exceptions (that pesky "Report Error" pop-up). It's a single-linked list, where each node has a pointer to the next exception-handler and a pointer to the function which handles the exception.

TREES ARE ONE OF THE MORE INTERESTING SECTIONS IN THE TEXT BOOK, IMHO!!!

Thanks for the info Synnopsys,
In general (not only C++) data structures are used quite often. Lists and sorted list are included in the .net System.Collections libraries. And then there are Hashtables Etc that we do not even cover, that are used quite often in real life programming.

I used this a linked list data structure to solve the missionary and cannibals problems. The Linked list contains two linked items (the next item in the list - and also the "parent" from which the node was generated...). The linked list is then designed to be interacted with as a FIFO (First in first out) queue. In this way I solved the problem using breadth-first search. This is fine for the missionary and cannibals problem as the state space is small.

Is this a real world example?

Code follows, it will compile with any C compiler.

#include <stdio.h>
#define L 1
#define R 0

char* boatpos(int boat);
void * malloc (size_t n);

struct 
{
  int c;
  int m;
  int boat;
} typedef worldstate;

struct
{
  worldstate state;
  void * parent;
  void * next;
} typedef node;



worldstate  suc1(worldstate);
worldstate  suc2(worldstate);
worldstate  suc3(worldstate);
worldstate  suc4(worldstate);
worldstate  suc5(worldstate);


void push(worldstate state, node * current);
node * solve(worldstate init, node * parent);
node * front; 
node * back;
node * begin;
void showsolution(node * solution);

int main()
{ 

  worldstate init;		/* set initial state */
  init.c = 0;
  init.m = 0;
  init.boat = R;
 
  node * solution;
 
  if (solution = solve(init,NULL))
    {
    
      printf("Solution to Missionary and Cannibals Problems\n";
      printf("CM[LR] - C is #Cannibals M is #Missionaries [LR] is bank with boat..\n";
      printf("For initial state 00R and Goal State 33L\n\n"; 
      
showsolution(solution);
    }
  else
    printf("no solution.\n";

  node * cleanup = begin;
  while (cleanup != NULL)
    {
      node * tmp;
      tmp = cleanup;
      cleanup = cleanup->next;
      free(tmp);
    }
}

void showsolution(node * solution) /* Recursive diplay of solution as
				      it has the unwound from the
				      solution */
{
  if (solution->parent != NULL)
    showsolution(solution->parent);
  printf("%d%d%s\n",(solution->state).c,(solution->state).m,boatpos((solution->state).boat));
}

char* boatpos(int boat)
{
  char * retval = (char *) malloc(2); 
  retval[0] = boat ? 'L' : 'R';
  retval[1] = '\0';
  return retval;
}

int forbidden(worldstate current) {
  if 
     ((current.c > current.m && current.m != 0)
     ||
   (current.m > current.c && current.m !=3)) {

    return 1;
  }
  return 0;
}

int goal(worldstate * current)
{
   if ((current->c == 3)   
      &&
      (current->m == 3)
      &&
      (current->boat == L))
    {
      return 1;
    }
  else
    return 0;
}




worldstate suc1(worldstate state)
{
   
  if (state.boat == L) {
    if (state.c > 0) {
      (state.c)--;
      state.boat = R;
     }
  }

  else if (state.boat == R) {
  if ((state.c) < 3) {
       (state.c)++;
      state.boat = L;
    }
  }

  return state;
}

worldstate suc2(worldstate state)
{

  if (state.boat == L) {
    if (state.c > 1) {
      (state.c)-=2;
      state.boat = R;
    }
  }

  else if (state.boat == R) {
    if ((state.c) < 2) {
     (state.c)+=2;
      state.boat = L;
    }
  }

  return state;

}

worldstate suc3(worldstate state)
{

  if (state.boat == L) {
    if (state.m > 0) {
      (state.m)--;
      state.boat = R;
    }
  }

  else if (state.boat == R) {
    if ((state.m) < 3) {
      (state.m)++;
      state.boat = L;
    }
  }
  return state;
}

worldstate suc4(worldstate state)
{
  if (state.boat == L) {
    if (state.m > 1) {
      (state.m)-=2;
      state.boat = R;
    }
  }

  else if (state.boat == R) {
    if ((state.m) < 2) {
      (state.m)+=2;
      state.boat = L;
    }
  }

  return state;
}


worldstate suc5(worldstate state)
{

  if (state.boat == L) {
    if ((state.m > 0) && (state.c > 0)) {
      (state.m)--;
      (state.c)--;
      state.boat = R;
    }
  }

  else if (state.boat == R) {
    if ( (state.m) < 3  && (state.c)< 3 ) {
      (state.m)++;
      (state.c)++;
      state.boat = L;
    }
  }

  return state;
}

int empty();
node * dequeue();
node * solve(worldstate state, node * parent)
{

   push(state , parent);	
   if (goal(&(front->state)))
      return front;
      else
	{

	  while (!empty()){

	    if (goal(&(front->state)))
	      return front;
	    else { 
	    
	      if (!forbidden(suc1(front->state))) push(suc1(front->state), front);
	      if (!forbidden(suc2(front->state))) push(suc2(front->state), front);
	      if (!forbidden(suc3(front->state))) push(suc3(front->state), front);
	      if (!forbidden(suc4(front->state))) push(suc4(front->state), front);
	      if (!forbidden(suc5(front->state))) push(suc5(front->state), front);
	      
	    }
	    dequeue();	 
	  }
	}
   
}


node * dequeue()
{
  front=front->next;
  return front;
}

int empty() {
  return (front==NULL)?1:0;
}


int equals(worldstate lhs, worldstate rhs);
void push(worldstate state, node * parent)
{
 
  /* Check if state has already been added.... if so do not add. */
  node * t;
   for(t=begin;t!=NULL;t=t->next)
    if (equals(state,t->state)) return;

  node * new = (node *) malloc(sizeof(node));
  (new->state).c=state.c;
  (new->state).m=state.m;
  (new->state).boat=state.boat;
  new->parent = parent;
  
  if (front == NULL && back == NULL) { 		/* Init */

    new->next = NULL;
    front = back = begin = new;
  }
  else
    {
      new->next = NULL;
      back->next = new;
      back = new;
    }
	
}

int equals(worldstate lhs, worldstate rhs)
{
  if ((lhs.c == rhs.c)   
      &&
      (lhs.m == rhs.m)
      &&
      (lhs.boat == rhs.boat))
    { 
      return 1;
    }
  else
    return 0;

}

Thanks Ilan,
Will take a good look at this.