Tuesday, March 5, 2013

Data Structure Notes

Data Structure Notes




STACK APPLICATION
 A simple application of stack is reversal of a given line. We can accomplish this task by pushing each character on to a stack as it read. When the line is finished , characters are then popped off the stack , and they will come off in the reverse order.
  Consider the word STACK
C
A
T
S
K
C
A
T
S

T
S

S

A
T
S
   1)PUSH  S     2)PUSH T       
                                                  3)PUSH A              4)PUSH C           5)PUSH K
                                                                                                                                   

             6)POP K    7)POP C  8)POP A    9)POP T   10) POP S

Infix to Postfix conversion using stack
1)      Push (on to the stack and add) to the end of X
2)      Scan X from left to right and repeat steps 3 to 6 for each element of X until the stack is empty :
3)      If an operand is encountered add it to Y
4)      If a left parenthesis is encountered, push it on to stack.
5)      If an operator is encountered then
a)      Repeatedly pop from the stack and add to Y each operator (on top of stack) which has the same precedence as or higher precedence than operator.
b)      Add operator to stack
6)      If a right parenthesis is encountered then:
a)       Repeatedly pop from the stack and add to Y each operator (on top of stack) until a left parenthesis is encountered
b)      Remove the left parenthesis

                 /*End of If structure
                /* End of step 2 loop
7)      End

A PRIORITY QUEUE is an abstract data type that captures the idea of a container whose elements have "priorities" attached to them.  An element of highest priority always appears at the front of the queue.   If that element  is removed, the next  highest priority  element  advances to the front. 

The C++ standard library defines a class template priority_queue, with the following operations:
·         push:  Insert an element into the prioity queue.
·         top: Return (without removing it) a highest priority element from the priority queue.
·         pop: Remove a highest priority element from the priority queue.
·         size: Return the number of elements in the priority queue.
·         empty: Return true or false according to whether the priority queue is empty or not.
The following code snippet shows how to construct two priority queues, one that can contain integers and another one that can contain character strings:

#include <queue>

priority_queue<int> q1;
priority_queue<string> q2;

The following is an example of priority queue usage:

#include <string>
#include <queue>
#include <iostream>

using namespace std;  // This is to make available the names of things defined in the standard library.

int main()
{
    piority_queue<string> pq; // Creates a priority queue pq to store strings, and initializes the queue to be empty.

    pq.push("the quick");
    pq.push("fox");
    pq.push("jumped over");
    pq.push("the lazy dog");

    // The strings are ordered inside the priority queue in lexicographic (dictionary) order:
    // "fox", "jumped over", "the lazy dog", "the quick"
    //  The lowest priority string is "fox", and the highest priority string is "the quick"

    while (!pq.empty()) {
       cout << pq.front() << endl;  // Print highest priority string
       pq.pop();                    // Remmove highest priority string
    }

    return 0;
}
The output of this program is:



the quick
the lazy dog
jumped over
fox

Another example priority queue
#include <iostream>
#include <string>
#include <queue>
using namespace std;

class Prioritize {
public:
     int operator() ( const pair<string, unsigned int>& p1,
                      const pair<string, unsigned int>& p2 ) {
         return p1.second < p2.second;
     }
};

int main()
{
     priority_queue< pair< string, unsigned int >,
        vector <pair< string, unsigned int > >, Prioritize >   pq;

     pq.push( pair<string, int>( "Event 1", 2) );
     pq.push( pair<string, int>( "Event 2", 10 ) );
     pq.push( pair<string, int>( "Event 3", 1 ) );

     while ( !pq. empty() ) { 
         cout << pq.top().first << endl;
         pq.pop();
     }

     return 0;
}

REPRESENTING A POLYNOMIAL USING A LINKED
LIST

A polynomial can be represented in an array or in a linked
list by simply storing the coefficient and exponent of each
term.
However, for any polynomial operation , such as addition
or multiplication of polynomials , you will find that the
linked list representation is more easier to deal with.
First of all note that in a polynomial all the terms may not
be present, especially if it is going to be a very high order
polynomial. Consider

5 x12 + 2 x9 + 4x7 + 6x5 + x2 + 12 x

Now this 12th order polynomial does not have all the 13
terms (including the constant term).
It would be very easy to represent the polynomial using a
linked list structure, where each node can hold information
pertaining to a single term of the polynomial.

Each node will need to store
the variable x,
the exponent and
the coefficient for each term.

It often does not matter whether the polynomial is in x or y.
This information may not be very crucial for the intended
operations on the polynomial.

Thus we need to define a node structure to hold two
integers , viz. exp and coff

Compare this representation with storing the same
polynomial using an array structure.
In the array we have to have keep a slot for each exponent
of x,
thus if we have a polynomial of order 50 but containing
just 6 terms, then a large number of entries will be zero in
the array.

You will also see that it would be also easy to manipulate a
pair of polynomials if they are represented using linked
lists.

Addition of two polynomials

Consider addition of the following polynomials

5 x12 + 2 x9 + 4x7 + 6x6 + x3

7 x8 + 2 x7 + 8x6 + 6x4 + 2x2 + 3 x + 40

The resulting polynomial is going to be

5 x12 + 2 x9 + 7 x8 + 6 x7 + 14x6 + 6x4 +x3

2x2 + 3 x + 40

Now notice how the addition was carried out. Let us say the
result of addition is going to be stored in a third list.
We started with the highest power in any polynomial.

If there was no item having same exponent , we simply
appended the term to the new list, and continued with the
process.

Wherever we found that the exponents were matching, we
simply added the coefficients and then stored the term in
the new list.

If one list gets exhausted earlier and the other list still
contains some lower order terms, then simply append the
remaining terms to the new list.

Now we are in a position to write our algorithm for adding
two polynomials.

Let phead1 , phead2 and phead3 represent the pointers of
the three lists under consideration.

Let each node contain two integers exp and coff .

Let us assume that the two linked lists already contain
relevant data about the two polynomials.

Also assume that we have got a function append to insert a
new node at the end of the given list.

p1 = phead1;
p2 = phead2;

Let us call malloc to create a new node p3 to build the
third list
p3 = phead3;

/* now traverse the lists till one list gets exhausted */

while ((p1 != NULL) || (p2 != NULL))
{

/ * if the exponent of p1 is higher than that of p2 then
the next term in final list is going to be the node of p1* /

while (p1 ->exp
> p2 -> exp )
{
p3 -> exp = p1 -> exp;
p3 -> coff = p1 -> coff ;
append (p3, phead3);

/* now move to the next term in list 1*/

p1 = p1 -> next;

}

/ * if p2 exponent turns out to be higher then make p3
same as p2 and append to final list * /

while (p1 ->exp
< p2 -> exp )
{
p3 -> exp = p2 -> exp;
p3 -> coff = p2 -> coff ;
append (p3, phead3);
p2 = p2 -> next;
}

/* now consider the possibility that both exponents are
same , then we must add the coefficients to get the term for
the final list */

while (p1 ->exp
= p2 -> exp )
{
p3-> exp = p1-> exp;
p3->coff = p1->coff + p2-> coff ;
append (p3, phead3) ;
p1 = p1->next ;
p2 = p2->next ;
}
}

/* now consider the possibility that list2 gets exhausted ,
and there are terms remaining only in list1. So all those
terms have to be appended to end of list3. However, you do
not have to do it term by term, as p1 is already pointing to
remaining terms, so simply append the pointer p1 to phead3
*/

if ( p1 != NULL)

append (p1, phead3) ;

else

append (p2, phead3);

Now, you can implement the algorithm in C, and maybe
make it more efficient.



TREES
A node is a structure which may contain a value, a condition, or represent a separate data structure (which could be a tree of its own). Each node in a tree has zero or more child nodes, which are below it in the tree (by convention, trees are drawn growing downwards). A node that has a child is called the child's parent node (or ancestor node, or superior). A node has at most one parent.
The simplest form of tree is a binary tree. A binary tree consists of
  1. a node (called the root node) and
  2. left and right sub-trees.
    Both the sub-trees are themselves binary trees.
In an ordered binary tree,
1.      the keys of all the nodes in the left sub-tree are less than that of the root,
2.      the keys of all the nodes in the right sub-tree are greater than that of the root,
3.      the left and right sub-trees are themselves ordered binary trees.

struct TreeNode {
              int item;         // The data in this node.
              TreeNode *left;   // Pointer to the left subtree.
              TreeNode *right;  // Pointer to the right subtree.
   }
Consider the problem of counting the nodes in a binary tree. f the tree is empty, the number of nodes is zero. Otherwise, use recursion to count the nodes in each subtree. Add the results from the subtrees together, and add one to count the root. This gives the total number of nodes in the tree. 
int countNodes( TreeNode *root ) {
           // Count the nodes in the binary tree to which
           // root points, and return the answer.
        if ( root == NULL )
           return 0;  // The tree is empty.  It contains no nodes.
        else {
           int count = 1;   // Start by counting the root.
           count += countNodes(root->left);  // Add the number of nodes
                                            //     in the left subtree.
           count += countNodes(root->right); // Add the number of nodes
                                            //    in the right subtree.
           return count;  // Return the total.
        }
     } // end countNodes()

tree-traversal refers to the process of visiting (examining and/or updating) each node in a tree data structure , exactly once, in a systematic way. Such traversals are classified by the order in which the nodes are visited. 
Depth-first Traversal
To traverse a non-empty binary tree in preorder, perform the following operations recursively at each node, starting with the root node:
1.     Visit the root.
2.     Traverse the left subtree.
3.     Traverse the right subtree.
To traverse a non-empty binary tree in inorder (symmetric), perform the following operations recursively at each node:
1.     Traverse the left subtree.
2.     Visit the root.
3.     Traverse the right subtree.
To traverse a non-empty binary tree in postorder, perform the following operations recursively at each node:

Traversing (visiting all the nodes) a tree starting at node is often done in one of three orders
  • Preorder - node, left subtree, right subtree.
  • Inorder - left subtree, node, right subtree. This could be used to print a binary search tree in sorted order.
  • Postorder - left subtree, right subtree, node. This could be used to print an expression tree in reverse polish notation (postfix).
INORDER TRAVERSAL
  1. inorder(TreeNode* currentNode)
  2. {
  3. if (currentNode) {
  4. inorder(currentNode->LeftChild);
  5. cout << currentNode->data;
  6. inorder(currentNode->RightChild);
  7. }
  8. }
ANOTHER ALGM
1.      Procedure inorder(input: T)
2.      begin
3.      if T = nil then
4.      return;
5.         endif
6.       
7.         inorder(T --> left>; -- traverse the left subtree recursively
8.         visit(T);                  -- visit/process the root
9.         inorder(T --> right>; -- traverse the right subtree recursively
10.  end
 
        
PREORDER TRAVERSAL
  1. preorder(TreeNode* currentNode)
  2. {
  3. if (currentNode) {
  4. cout << currentNode->data;
  5. preorder(currentNode->LeftChild);
  6. preorder(currentNode->RightChild);
  7. }
  8. }
ANOTHER ALGM
·         Procedure preorder(input: T)
·         begin
·            if T = nil then
·               return;
·            endif
·          
·            visit(T);                  -- visit/process the root
·            preorder(T --> left>; -- traverse the left subtree recursively
·            preorder(T --> right>; -- traverse the right subtree recursively
·         end
  •  


POST ORDER TRAVERSAL
  1. postorder(TreeNode* currentNode)
  2. {
  3. if (currentNode) {
  4. postorder(currentNode->LeftChild);
  5. postorder(currentNode->RightChild);
  6. cout << currentNode->data;
  7. }
  8. }

ANOTHER ALGORITHM
·         Procedure postorder(input: T)
·         begin
·            if T = nil then
·               return;
·            endif
·          
·            postorder(T --> left>; -- traverse the left subtree recursively
·            postorder(T --> right>; -- traverse the right subtree recursively
·            visit(T);                  -- visit/process the root
·         end

LEVEL ORDER TRAVERSAL
  1. LevelOrder(TreeNode* root)
  2. {
  3. Queue q<TreeNode*>;
  4. TreeNode* currentNode = root;
  5.  
  6. while (currentNode) {
  7. cout << currentNode->data;
  8. if (currentNode->LeftChild) q.Add(currentNode->LeftChild);
  9. if (currentNode->RightChild) q.Add(currentNode->RightChild);
  10. currentNode = q.Delete(); //q.Delete returns a node pointer
  11. }
  12. }


In the BUBBLE SORT, as elements are sorted they gradually "bubble" (or rise) to their proper location in the array, like bubbles rising in a glass of soda.  The bubble sort repeatedly compares adjacent elements of an array.  The first and second elements are compared and swapped if out of order.  Then the second and third elements are compared and swapped if out of order.  This sorting process continues until the last two elements of the array are compared and swapped if out of order. When this first pass through the array is complete, the bubble sort returns to elements one and two and starts the process all over again.  The bubble sort knows that it is finished when it examines the entire array and no "swaps" are needed (thus the list is in proper order).
void BubbleSort(apvector <int> &num)
{
      int i, j, flag = 1;    // set flag to 1 to start first pass
      int temp;             // holding variable
      int numLength = num.length( ); 
      for(i = 1; (i <= numLength) && flag; i++)
     {
          flag = 0;
          for (j=0; j < (numLength -1); j++)
         {
               if (num[j+1] > num[j])      // ascending order simply changes to <
              { 
                    temp = num[j];             // swap elements
                    num[j] = num[j+1];
                    num[j+1] = temp;
                    flag = 1;               // indicates that a swap occurred.
               }
          }
     }
     return;   //arrays are passed to functions by address; nothing is returned
}
example
INSERTION SORT
The INSERTION SORT, unlike the other sorts, passes through the array only once.  The insertion sort is commonly compared to organizing a handful of playing cards.  You pick up the random cards one at a time.  As you pick up each card, you insert it into its correct position in your hand of organized cards.  

The insertion sort splits an array into two sub-arrays. The first sub-array (such as the cards in your hand) is sorted and increases in size as the sort continues. The second sub-array (such as the cards to be picked up) is unsorted, contains all the elements to yet be inserted into the first sub-array, and decreases in size as the sort continues.
void InsertionSort( apvector <int> &num)
{
     int i, j, key, numLength = num.length( );
     for(j = 1; j < numLength; j++)    // Start with 1 (not 0)
    {
           key = num[j];
           for(i = j - 1; (i >= 0) && (num[i] < key); i--)   // Smaller values move up
          {
                 num[i+1] = num[i];
          }
         num[i+1] = key;    //Put key into its proper location
     }
     return;
}
MERGE SORT
The merge sort combines two sorted arrays into
one larger sorted array.   

Array A and Array B merge to form Array C. 
Arrays to be merged MUST be SORTED FIRST!! 
Be sure to declare Array C  in main( ) and establish its size.
Example: Ascending Order
Array A: {7. 12}
Array B: {5,  7, 8}
Array C: {5, 7, 7, 8, 12} after merge
The first element of array A is compared with the first element of array B.  If the first element of array A is smaller than the first element of array B, the element from array A is moved to the new array C.  The subscript of array A is now increased since the first element is now set and we move on.
If the element from array B should be smaller, it is moved to the new array C.  The subscript of array B is increased.  This process of comparing the elements in the two arrays continues until either array A or array B is empty.  When one array is empty, any elements remaining in the other (non-empty) array are "pushed" into the end of array C and the merge is complete.
void MergeSort(apvector <int> &arrayA, apvector <int> &arrayB, apvector <int> &arrayC)
{
     int indexA = 0;     // initialize variables for the subscripts
     int indexB = 0;
     int indexC = 0;

     while((indexA < arrayA.length( )) && (indexB < arrayB.length( ))
     {
          if (arrayA[indexA] < arrayB[indexB])
          {
                 arrayC[indexC] = arrayA[indexA];
                 indexA++;    //increase the subscript
          }
         else
         {
                 arrayC[indexC] = arrayB[indexB];
                 indexB++;      //increase the subscript
         }
        indexC++;      //move to the next position in the new array
     }
     // Move remaining elements to end of new array when one merging array is empty
     while (indexA < arrayA.length( ))
     {
           arrayC[indexC] = arrayA[indexA];
           indexA++;
           indexC++;
     }
     while (indexB < arrayB.length( ))
     {
           arrayC[indexC] = arrayB[indexB];
           indexB++;
           indexC++;
     }
     return;
}

HEAP SORT
Heapsort (method) is a comparison-based sorting algorithm, and is part of the selection sort family.
Although somewhat slower in practice on most machines than a good implementation of quicksort, it has the advantage of a worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but is not a stable sort.
Heapsort uses two heap operations: insertion and root deletion. Each extraction places an element in the last empty location of the array.
The remaining prefix of the array stores the unsorted elements.
§  The heap sort works as its name suggests.
§  It begins by building a heap out of the data set, and then removing the largest item and placing it at the end of the sorted array.
§  After removing the largest item, it reconstructs the heap, removes the largest remaining item, and places it in the next open position from the end of the sorted array.
§  This is repeated until there are no items left in the heap and the sorted array is full.
§  Elementary implementations require two arrays – one to hold the heap and the other to hold the sorted elements.
§  Heapsort inserts the input list elements into a heap data structure.
§  The largest value (in a max-heap) or the smallest value (in a min-heap) are extracted until none remain, the values having been extracted in sorted order.
  • construct a heap,
  • add each item to it (maintaining the heap property!),
  • when all items have been added, remove them one by one (restoring the heap property as each one is removed).
DEPTH-FIRST SEARCH (DFS) is an algorithm  for traversing or searching a tree, tree structure, or graph. One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking. The depth first search is well geared towards problems where we want to find any solution to the problem (not necessarily the shortest path), or to visit all of the nodes in the graph
The basic concept is to visit a node, then push all of the nodes to be visited onto the stack. To find the next node to visit we simply pop a node of the stack, and then push all the nodes connected to that one onto the stack as well and we continue doing this until all nodes are visited. It is a key property of the Depth First search that we not visit the same node more than once, otherwise it is quite possible that we will recurse infinitely. We do this by marking the node as we visit it, then unmarking it after we have finished our recursions. This action allows us to visit all the paths that exist in a graph; however for large graphs this is mostly infeasible so we sometimes omit the marking the node as not visited step to just find one valid path through the graph 
  • DFS follows the following rules:
    1. Select an unvisited node s, visit it, and treat as the current node
    2. Find an unvisited neighbor of the current node, visit it, and make it the new current node;
    3. If the current node has no unvisited neighbors, backtrack to the its parent, and make that the new current node;
Repeat the above two steps until no more nodes can be visited.
    1. If there are still unvisited nodes, repeat from step 1.
ALGORITHM
·         Procedure DFS(input: graph G)
·         begin
·            Stack S;
·            Integer s,x;
·            while (G has an unvisited node) do
·               s := an unvisited node;
·               visit(v);
·               push(v,S);
·               While (S is not empty) do
·                  x := top(S);
·                  if (x has an unvisited neighbor y) then
·                     visit(y);
·                     push(y,S);
·                  else
·                     pop(S);
·                  endif
·               endwhile
·            endwhile
·         end


Breadth First Search
The Breadth First search is an extremely useful searching technique. It differs from the depth-first search in that it uses a queue to perform the search, so the order in which the nodes are visited is quite different. It has the extremely useful property that if all of the edges in a graph are unweighted (or the same weight) then the first time a node is visited is the shortest path to that node from the source node. You can verify this by thinking about what using a queue means to the search order. When we visit a node and add all the neighbors into the queue, then pop the next thing off of the queue, we will get the neighbors of the first node as the first elements in the queue. This comes about naturally from the FIFO property of the queue and ends up being an extremely useful property. One thing that we have to be careful about in a Breadth First search is that we do not want to visit the same node twice, or we will lose the property that when a node is visited it is the quickest path to that node from the source. 

  • BFS follows the following rules:
1.      Select an unvisited node s, visit it, have it be the root in a BFS tree being formed. Its level is called the current level.
2.      From each node x in the current level, in the order in which the level nodes were visited, visit all the unvisited neighbors of x. The newly visited nodes from this level form a new level that becomes the next current level.
3.      Repeat the previous step until no more nodes can be vsisted.
4.      If there are still unvisited nodes, repeat from Step 1.
ALGORITHM
·           Procedure BFS(input: graph G)
·         begin
·            Queue Q;
·            Integer s,x;
·            while (G has an unvisited node) do
·               s := an unvisited node;
·               visit(s);
·               Enqueue(s,Q);
·               While (Q is not empty) do
·                  x := Dequeue(Q);
·                  For (unvisited neighbor y of x) do
·                     visit(y);
·                     Enqueue(y,Q);
·                  endfor
·               endwhile
·            endwhile
·         end
In a binary tree, each node can have up to two child
nodes. More general tree structures can be created in which different numbers of child
nodes are allowed for each node.
GRAPH
All tree structures are hierarchical. This means that each node can only have one
parent node. Trees can be used to store data which has a definite hierarchy; for
example a family tree or a computer file system.
Some data need to have connections between items which do not fit into a hierarchy
like this. Graph data structures can be useful in these situations. A graph consists of a
number of data items, each of which is called a vertex. Any vertex may be connected to
any other, and these connections are called edges.
Two vertices in a graph are adjacent if the form an edge. Adjacent vertices are called
neighbours.
A path is a sequence of vertices in which each successive pair is an edge.
Circular queues are the queues implemented in circular form. they overcome the problem of unutilized space in linear queues
Deque (double ended queues ) are refined queues in which elements are added or removed at either end but not in the middle.
Two Types
1)      An input restricted deque is a deque which allows insertions at one end but deletion at both ends of the list.
2)      An output restricted deque is a deque which allows deletion at one end but insertions at both ends of the list.
INSERTION IN A CIRCULAR QUEUE
Assume that the circular queue is stored in QU with size N
1.      I f (FRONT=0 AND REAR= N-1) or (FRONT=REAR+1) Then
{
Write “ Over flow” }
Else
{
2.       If  FRONT =NULL Then
{
Set FRONT=0
REAR=0}
3.      ELSE IF REAR =N-1 Then
Set REAR=0
ELSE SET
4.      REAR=REAR+1
}
5.      SET QU(REAR= REAR+1)
6.      END
  • Deletion in circular queue
  • Assume that the circular queue is stored in QU with size N. This algorithm will delete an element from the queue and assign it to D-ITEM.
  •  
1.      If  FRONT =NULL Then {
Write “ Under flow”
Return }
Else
{
2.      Set D_ITEM=QU[FRONT]/* now make the FRONT point to the next element in the queue*/
3.      If FRONT=REAR Then
{
FRONT=NULL
REAR=NULL}
4.      ELSE IF FRONT =N-1 Then
FRONT=0
ELSE
5.      FRONT=FRONT+1
}

6.      END
  •  
Posted by Unknown at 3:11 PM
Labels: , ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)