Total Pageviews

Tuesday, September 18, 2012

Chapter 10: Elementary Data Structure


I am not posting solution of all the questions. But if you've any doubt kindly post it as 
a comment I'll post the solution as soon as possible.

10.2.4. Let's first define our node structure.
            struct node{
              int value;
              struct node* next;
            }
         When we've a sentinal node we'll make our last node in the linked list to point to the sentinal node.                And whenever we need to search for a value we'll update the value of our sentinal node to that search value. This way we'll be sure of finding that value in the linked list. The code goes here:
         
         boolean ListSearch(node* head,int value,node* sentinal_node){
            if(!head){
                return false;
            }
            sentinal_node->value = value;
            while(head != null){
                if(head->value == value){
                      break;
                }
                head = head->next;
            }
            if(head == sentinal_node){
                return false;
            }
            return true;
       }
       
10.2.5. Impleting a dictionary using a linked list is very similar to storing a list of numbers 
        in a linked list. Here, we just need to replace integer values with string literals.
        Let's first define our node structure.
            struct node{
                      char* word;
                      struct node* next;
            }
        Here are the cost of some operations:
        INSERT: O(1), simply insert at the head of the list.
        DELETE: O(n), you'll have to first search for the element in the list. For searching in the worst case
       you've to compare with every node in the linked list.
        SEARCH: O(n), reason is same as of above.
         
10.2.6. Let's first define our node structure.
            struct node{
                      char* word;
                      struct node* next;
            }
            struct Set{
                    struct node* head;
                    struct node* tail;
            }
        For every list beside with the head pointer we'll also keep a tail pointer.
        Supporting union operation in O(1) time: Suppose we've two Sets S1 and S2.
        
       PSEUDO-CODE:
                node* Union(Set S1,Set S2){
                      S1.tail->next = S2.head;
                      S1.tail = S2.tail;
                      Remove S2 from the list of sets;
                      return S1;
                }


10.4.4. void PrintNodes(node* root){
if(!root){
return;
}
PrintNodes(root->left);
printf("%d ",root->value);
PrintNodes(root->sibling);
            }


10.4.5. One very basic approach would be to do a level-order traversal. This can be implemented using a queue.
PSEUDO-CODE:

void DoLevelTraversal(node* root){
Queue<node*> Q;
Q.push(root);
while(!Q.empty()){
node* top = Q.front();
Q.pop();
printf("%d ",top->value);
while(top->sibling != NULL){
Q.push(top->sibling);
top = top->sibling;
}
}
}

But it uses extra space. Will think of some other approach soon.