cpppro

Archive for the ‘Data Structures in C/C++’ Category

Swapping nodes in a single linked list

In C Tidbits, Data Structures in C/C++ on January 12, 2008 at 4:29 pm

Here is algorithm for swapping two nodes in linked list..

//A complete swap algorithm which cares of
//several scenarios while swapping two nodes in
//a linked list which doesn't have any special nodes
//scenarios considered while swapping
//1)two nodes which are far away
//2)two nodes which are far away, one is node is at
//  beginning of the list
//3)two node which are neighbors
//4)two nodes which are neibhors,
//  one node is at beginning of the list
Node *SwapNodes(Node *list, Node *node1, Node *node2)
{
  Node *node1prev, *node2prev, *tmp;

  node1prev = FindPrev(list, node1);
  node2prev = FindPrev(list, node2);

  tmp = node2->next;

  //check whether node to swapped is in
  //beggining (i.e. header node)
  if (node1 != list)
  {
    node1prev->next = node2;
  }
  else
  {
    //as we do not have special header node,
    //if the first node and some
    //other node, need to be swapped,
    //then update the list (makes new min node as
    //logical header)
    list = node2;
  }

  //are nodes to be swapped neibgoring nodes?
  if (node1->next == node2)
  {
    //nodes to be swapped are neibhoring nodes,
    //then swap them simply
    node2->next = node1;
    node1->next = tmp;
  }
  else
  {
    //nodes to be swapped are not neibhor nodes,
    //they are apart
    //so, consider all scenarios
    node2->next = node1->next;

    node1->next = tmp;
    node2prev->next = node1;
  }

  return list;
}

Please refer reference code for collection of posts in data structures

[note:I’d used old complier(msvc 6.0), if you are using a new compiler you may get some compiler warnings, please solve it yourself or post it here with the problems)

if you find any bugs in the above program post them as comments..

Advertisements

Balanced (AVL) Binary Search Trees

In C Tidbits, Data Structures in C/C++ on December 28, 2007 at 6:55 pm

An AVL (adelson-velskii-landis) tree also known as balanced tree is a binary search tree with a balance condition.
The balance condition is that for every node in the tree, the height of left and right subtrees can differ by at most 1. The condition ensures that the depth of the tree is O(log N).

      9                           9
     / \                         / \
    /   \                       /   \
   /     \                     /     \
  5      15                   5      15
 / \     /                   / \     / \
2   6   /                   2   6   /   \
       13                          13   20
      /                           /
     /                           /
    12                          12

fig1:BST but               fig2:BST and is balanced(AVL) tree
not balanced tree

as the node 15 in fig1 is out of balance because height of left sub tree is 2 and height of right sub tree is 0.
You might be wondering how to compute height, here it is

height(Tree) = MAX(height(left-sub-tree), height(right-sub-tree)) + 1;

for example, height(9) = MAX(height(5), height(15)) + 1;
height(5) = MAX(height(2), height(6)) + 1 = 1;
height(15) = MAX(height(13), -1) + 1 = 2
so, height(5) = MAX(1, 2) + 1 = 3;

Maintaining height information of each node is necessary to check the balancing condition in AVL (balanced) tree.
So, here is the AVL (balanced) tree node representation

struct Tree
{
  Tree * left,
  Tree * right;
  int element;
  int height;
};

Here are the operations which are possible on Balanced (AVL) tree ADT,

1)Make Empty
2)Height
3)Find
4)FindMin
5)FindMax
6)Insert
7)Delete

 

Please refer http://www.refcode.net/2013/02/balanced-avl-binary-search-trees.html

 

 

Printing Binary Trees in Ascii

In C Tidbits, Data Structures in C/C++ on December 21, 2007 at 8:14 pm

Here we are not going to discuss what binary trees are (please refer this, if you are looking for binary search trees), or their operations but printing them in ascii.

The below routine prints tree in ascii for a given Tree representation which contains list of nodes, and node structure is this

struct Tree
{
  Tree * left, * right;
  int element;
};

This pic illustrates what the below routine does on canvas..
ascii tree

Here is the printing routine..

//prints ascii tree for given Tree structure
void print_ascii_tree(Tree * t)
{
  asciinode *proot;
  int xmin, i;
  if (t == NULL) return;
  proot = build_ascii_tree(t);
  compute_edge_lengths(proot);
  for (i=0; iheight && i < MAX_HEIGHT; i++)
  {
    lprofile[i] = INFINITY;
  }
  compute_lprofile(proot, 0, 0);
  xmin = 0;
  for (i = 0; i height && i < MAX_HEIGHT; i++)
  {
    xmin = MIN(xmin, lprofile[i]);
  }
  for (i = 0; i height; i++)
  {
    print_next = 0;
    print_level(proot, -xmin, i);
    printf("\n");
  }
  if (proot->height >= MAX_HEIGHT)
  {
    printf("(This tree is taller than %d, and may be drawn incorrectly.)\n",
           MAX_HEIGHT);
  }
  free_ascii_tree(proot);
}

Auxiliary routines..

//This function prints the given level of the given tree, assuming
//that the node has the given x cordinate.
void print_level(asciinode *node, int x, int level)
{
  int i, isleft;
  if (node == NULL) return;
  isleft = (node->parent_dir == -1);
  if (level == 0)
  {
    for (i=0; ilablen-isleft)/2)); i++)
    {
      printf(" ");
    }
    print_next += i;
    printf("%s", node->label);
    print_next += node->lablen;
  }
  else if (node->edge_length >= level)
  {
    if (node->left != NULL)
    {
      for (i=0; iright != NULL)
    {
      for (i=0; ileft,
                x-node->edge_length-1,
                level-node->edge_length-1);
    print_level(node->right,
                x+node->edge_length+1,
                level-node->edge_length-1);
  }
}

//This function fills in the edge_length and
//height fields of the specified tree
void compute_edge_lengths(asciinode *node)
{
  int h, hmin, i, delta;
  if (node == NULL) return;
  compute_edge_lengths(node->left);
  compute_edge_lengths(node->right);

  /* first fill in the edge_length of node */
  if (node->right == NULL && node->left == NULL)
  {
    node->edge_length = 0;
  }
  else
  {
    if (node->left != NULL)
    {
      for (i=0; ileft->height && i left, 0, 0);
      hmin = node->left->height;
    }
    else
    {
      hmin = 0;
    }
    if (node->right != NULL)
    {
      for (i=0; iright->height && i right, 0, 0);
      hmin = MIN(node->right->height, hmin);
    }
    else
    {
      hmin = 0;
    }
    delta = 4;
    for (i=0; ileft != NULL && node->left->height == 1) ||
	      (node->right != NULL && node->right->height == 1))&&delta>4)
    {
      delta--;
    }

    node->edge_length = ((delta+1)/2) - 1;
  }

  //now fill in the height of node
  h = 1;
  if (node->left != NULL)
  {
    h = MAX(node->left->height + node->edge_length + 1, h);
  }
  if (node->right != NULL)
  {
    h = MAX(node->right->height + node->edge_length + 1, h);
  }
  node->height = h;
}
asciinode * build_ascii_tree_recursive(Tree * t)
{
  asciinode * node;

  if (t == NULL) return NULL;

  node = malloc(sizeof(asciinode));
  node->left = build_ascii_tree_recursive(t->left);
  node->right = build_ascii_tree_recursive(t->right);

  if (node->left != NULL)
  {
    node->left->parent_dir = -1;
  }

  if (node->right != NULL)
  {
    node->right->parent_dir = 1;
  }

  sprintf(node->label, "%d", t->element);
  node->lablen = strlen(node->label);

  return node;
}

//Copy the tree into the ascii node structre
asciinode * build_ascii_tree(Tree * t)
{
  asciinode *node;
  if (t == NULL) return NULL;
  node = build_ascii_tree_recursive(t);
  node->parent_dir = 0;
  return node;
}

//Free all the nodes of the given tree
void free_ascii_tree(asciinode *node)
{
  if (node == NULL) return;
  free_ascii_tree(node->left);
  free_ascii_tree(node->right);
  free(node);
}

//The following function fills in the lprofile array for the given tree.
//It assumes that the center of the label of the root of this tree
//is located at a position (x,y).  It assumes that the edge_length
//fields have been computed for this tree.
void compute_lprofile(asciinode *node, int x, int y)
{
  int i, isleft;
  if (node == NULL) return;
  isleft = (node->parent_dir == -1);
  lprofile[y] = MIN(lprofile[y], x-((node->lablen-isleft)/2));
  if (node->left != NULL)
  {
    for (i=1; i edge_length && y+i left, x-node->edge_length-1, y+node->edge_length+1);
  compute_lprofile(node->right, x+node->edge_length+1, y+node->edge_length+1);
}

void compute_rprofile(asciinode *node, int x, int y)
{
  int i, notleft;
  if (node == NULL) return;
  notleft = (node->parent_dir != -1);
  rprofile[y] = MAX(rprofile[y], x+((node->lablen-notleft)/2));
  if (node->right != NULL)
  {
    for (i=1; i edge_length && y+i left, x-node->edge_length-1, y+node->edge_length+1);
  compute_rprofile(node->right, x+node->edge_length+1, y+node->edge_length+1);
}

Here is the asciii tree structure…

struct asciinode_struct
{
  asciinode * left, * right;

  //length of the edge from this node to its children
  int edge_length;

  int height;

  int lablen;

  //-1=I am left, 0=I am root, 1=right
  int parent_dir;

  //max supported unit32 in dec, 10 digits max
  char label[11];
};

Please refer reference code for collection of posts in data structures

[note: I’d used msvc6 (which is a bit old one), so when you use new compilers you may get few compilations errors, fix them yourself or drop a msg over here..]

Binary Search Trees

In C Tidbits, Data Structures in C/C++ on December 21, 2007 at 7:28 pm

A binary tree is a tree in which no node can have more than two children. The property that makes a binary tree into a binary search tree is that for every node, X, in the tree, the values of all the keys in its left subtree are smaller than the key value in X, and the values of all the keys in its right subtree are larger than the key value in X.

An important application of binary trees is their use in searching.

Here are the operations which are possible on binary search tree ADT (abstract data type),

1)Make Empty
2)Find
3)FindMin
4)FindMax
5)Insert
6)Delete

Please refer http://www.refcode.net/2013/02/binary-search-trees.html

Circular Linked Lists

In C Tidbits, Data Structures in C/C++ on May 17, 2007 at 5:54 pm

Please visit my earlier post linked lists for basics of linked lists. Visit this post for circular double linked lists

What is circular linked list?

Circular Linked lists are chain of records/nodes, one record/node points to the next, and last node/record pointing to the first node instead of pointing to a sentinel. Record/node holds the data.

Why circular linked lists?

Circular linked lists can be traversed from anywhere (given any node) in the list, which gives flexibility and it also enahnces efficiencies of some operations however it complicates operations by inducing special cases to deal with circularity of list

How circular linked lists look like?

Circular linked list

Operations On Circular Linked Lists:

 

Please refer http://www.refcode.net/2013/02/circular-linked-lists.html

 

Printing linked List in Reverse without Reversing The List Actually

In C Tidbits, Data Structures in C/C++ on May 6, 2007 at 2:48 pm

Printing a linked list in reverse order without actually reversing the linked list can be done by a recursive routine or using a stack.

Lets us see a recursive routine first…

In recursive routine go to the end then print the nodes, i.e. recursive call comes before printing the node… Here is the function…

void printreverse(Node *node)
{
  if (node)
  {
    printreverse(node->next);
    printf("%d -> ",node->info);
  }
}

Reversing the list using stack:
Push all the nodes, pop one by one and print them… Here is the program for this..

void printreverse(Node* node)
{
  Node *tmpnode;

  Stack *stack = CreateStack();

  while(node)
  {
    Push(stack, node);
    node = node->next;
  }

  tmpnode = Pop(stack);

  while(tmpnode)
  {
    tmpnode = Pop(stack);
    printf("%d -> ", tmpnode->info);
  }

  DestroyStack(stack);
}

Josephus Problem in C

In Data Structures in C/C++ on May 6, 2007 at 1:43 pm

Q:Josephus Flavius was a famous Jewish historian of the first century at the time of the Second Temple destruction. During the Jewish-Roman war he got trapped in a cave with a group of 40 soldiers surrounded by romans. The legend has it that preferring suicide to capture, the Jews decided to form a circle and, proceeding around it, to kill every third remaining person until no one was left. Josephus, not keen to die, quickly found the safe spot in the circle and thus stayed alive.

Requirements:

  1. Circular linked list must be used.
  2. The sequence starts from 1, therefore you won’t see a 0 appear in the sequence.The number of people and number of skips must be larger than 0
    (>0).

Please refer http://www.refcode.net/2013/03/josephus-problem-in-c.html

Sorting a Linked List with QuickSort – Simple Algorithm

In C Tidbits, Data Structures in C/C++ on May 1, 2007 at 7:42 pm

Quicksort is the fastest known sorting algorithm in practice. Its average running time is O(nlogn). It is based on devide and conquer idea:
partition into two lists and put them back together again. It does more work on the divide side, less on the combine side.

The basic algorithm is
1)pick any element (called as Pivot) in list
2)Partition the list as two parts, first part contains all the elements which are less than pivot, the other contain all the elements which are greater than pivot
3)do quicksort recursively on sub lists

Regarding step1:
Any element can be selected as pivot, but some choices may cause bad performance. Example. first element everytime: this pivot cause bad performance on presorted or lists in reverse sorted order, because all elements go into one sublist. One safe strategy is choosing pivot randomly.

regarding Step2:
As already pointed out quicksort does most of the work while partitioning the lists, so this is the step which is a bit complex..

both step1 and 2 are represented graphically below…

Please refer http://www.refcode.net/2013/02/sorting-linked-list-with-quicksort.html

 

Sorting a Linked List with Selection Sort

In C Tidbits, Data Structures in C/C++ on April 29, 2007 at 7:26 pm

The basic idea of selection sorting algorithm is

1)find minimum element in the list
2)swap it with the beginning element
3)repeat the above steps after moving pointer to next element

Here is the graphical representation of operation of this algorithm…

selection sort array pic

Before we go to linked list sorting understand how do we sort for an array…
Here is the C code for selection sort for an array

 

Please refer http://www.refcode.net/2013/02/sorting-linked-list-with-selection-sort.html

 

Detecting a loop in single linked list

In C Tidbits, Data Structures in C/C++ on April 22, 2007 at 7:07 pm

Please refer this post for linked list basics and all other operations on linked lists.

 

Loops in linked list can be detected by inserting dummy nodes after every node, so if we find dummy node after a node already, that says that list has a loop. The diagram below explains this. This method takes O(n) time and O(n) additional space.
detecting loops

Loops in linked list can also be detected by running two loops paralally, one loop traverse list by one node, another loop traverse list by skipping a node while going to next node. this way they meet at some point of time, if the list has a loop. The diagram below explains this. This method takes O(n) time in best case.
detecting loops another method

program for finding loop by traversing with two pointers… this program takes input as linked list, returns a node(where a loop starts), or returns NULL if we could not find a loop…

Node *detectloop(Node *list)
{
  Node *n1, *n2;

  //prev indicates loop started at this point
  Node *prev=NULL;

  for(n1=list, n2=list; (n1!=NULL) && (n2!=NULL); )
  {
    if (prev && (n1 == n2))
    {
      return prev;
    }
    prev = n1;
    n1=n1->next;
    n2=n2->next;
    if (n2)
    {
      n2=n2->next;
    }
  }
}

comments?