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.