Cormen:Introduction to Algorithms Solutions: Chapter 10: Elementary Data Structure
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.
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.
Read full article from Cormen:Introduction to Algorithms Solutions: Chapter 10: Elementary Data Structure
No comments:
Post a Comment