Skip to main content

Quick Way to Implement Dictionary in C


Example program To Implement Dictionary using Hashing(in C):

struct  Dictionary { /* table entry: */
    struct  Dictionary *next; /* next entry in chain */
    char *word; /* defined word */
    char *meaning; /* replacement text */
};

#define HASHSIZE 101
static struct  Dictionary *HashTable[HASHSIZE]; /* pointer table */

/* getHashCode: form getHashCode value for string s */
unsigned getgetHashCodeCode(char *s)
{
    unsigned hashValue;
    for (hashValue = 0; *s != '\0'; s++)
      hashValue = *s + 31 * hashValue;
    return hashValue % HASHSIZE;
}

/* lookup: look for s in HashTable */
struct  Dictionary *lookup(char *s)
{
    struct  Dictionary *node;
    for (node = HashTable[getHashCode(s)]; node != NULL; node = node->next)
        if (strcmp(s, node->word) == 0)
          return node; /* found */
    return NULL; /* not found */
}

char *strdup(char *);

/* install: put (word, meaning) in HashTable */
struct  Dictionary *install(char *word, char *meaning)
{
    struct  Dictionary *node;
    unsigned hashValue;
    if ((node = lookup(word)) == NULL) { /* not found */
        node = (struct  Dictionary *) malloc(sizeof(*node));
        if (node == NULL || (node->word = strdup(word)) == NULL)
          return NULL;
        hashValue = getHashCode(word);
        node->next = HashTable[hashValue];
        HashTable[hashValue] = node;
    } else /* already there */
        free((void *) node->meaning); /*free previous meaning */
    if ((node->meaning = strdup(meaning)) == NULL)
       return NULL;
    return node;
}

char *strdup(char *s) /* make a duplicate of s */
{
    char *p;
    p = (char *) malloc(strlen(s)+1); /* +1 for ’\0’ */
    if (p != NULL)
       strcpy(p, s);
    return p;
}




Example program To Implement Dictionary using Binary Search Tree(in C):

  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>

  struct BSTnode {
        char word[128], meaning[256];
        struct BSTnode *left, *right;
  };

  struct BSTnode *root = NULL;

  struct BSTnode * createNode(char *word, char *meaning) {
        struct BSTnode *newnode;
        newnode = (struct BSTnode *)malloc(sizeof(struct BSTnode));
        strcpy(newnode->word, word);
        strcpy(newnode->meaning, meaning);
        newnode->left = newnode->right = NULL;
        return newnode;
  }

  void insert(char *word, char *meaning) {
        struct BSTnode *parent = NULL, *current = NULL, *newnode = NULL;
        int res = 0;
        if (!root) {
                root = createNode(word, meaning);
                return;
        }
        for (current = root; current !=NULL;
           current = (res > 0) ? current->right : current->left) {
                res = strcasecmp(word, current->word);
                if (res == 0) {
                        printf("Duplicate entry!!\n");
                        return;
                }
                parent = current;
        }
        newnode = createNode(word, meaning);
        res > 0 ? (parent->right = newnode) : (parent->left = newnode);
        return;
  }

  void deleteNode(char *str) {
        struct BSTnode *parent = NULL, *current = NULL, *temp = NULL;
        int flag = 0, res = 0;
        if (!root) {
                printf("BST is not present!!\n");
                return;
        }
        current = root;
        while (1) {
                res = strcasecmp(current->word, str);
                if (res == 0)
                        break;
                flag = res;
                parent = current;
                current = (res > 0) ? current->left : current->right;
                if (current == NULL)
                        return;
        }
        /* deleting leaf node */
        if (current->right == NULL) {
                if (current == root && current->left == NULL) {
                        free(current);
                        root = NULL;
                        return;
                } else if (current == root) {
                        root = current->left;
                        free (current);
                        return;
                }

                flag > 0 ? (parent->left = current->left) :
                                (parent->right = current->left);
        } else {
                /* delete node with single child */
                temp = current->right;
                if (!temp->left) {
                        temp->left = current->left;
                        if (current == root) {
                                root = temp;
                                free(current);
                                return;
                        }
                        flag > 0 ? (parent->left = temp) :
                                        (parent->right = temp);
                } else {
                        /* delete node with two children */
                        struct BSTnode *successor = NULL;
                        while (1) {
                                successor = temp->left;
                                if (!successor->left)
                                        break;
                                temp = successor;
                        }
                        temp->left = successor->right;
                        successor->left = current->left;
                        successor->right = current->right;
                        if (current == root) {
                                root = successor;
                                free(current);
                                return;
                        }
                        (flag > 0) ? (parent->left = successor) :
                                        (parent->right = successor);
                }
        }
        free (current);
        return;
  }

  void findElement(char *str) {
        struct BSTnode *temp = NULL;
        int flag = 0, res = 0;
        if (root == NULL) {
                printf("Binary Search Tree is out of station!!\n");
                return;
        }
        temp = root;
        while (temp) {
                if ((res = strcasecmp(temp->word, str)) == 0) {
                        printf("Word   : %s", str);
                        printf("Meaning: %s", temp->meaning);
                        flag = 1;
                        break;
                }
                temp = (res > 0) ? temp->left : temp->right;
        }
        if (!flag)
                printf("Search Element not found in Binary Search Tree\n");
        return;
  }

  void inorderTraversal(struct BSTnode *myNode) {
        if (myNode) {
                inorderTraversal(myNode->left);
                printf("Word    : %s", myNode->word);
                printf("Meaning : %s", myNode->meaning);
                printf("\n");
                inorderTraversal(myNode->right);
        }
        return;
  }

  int main() {
        int ch;
        char str[128], meaning[256];
        while (1) {
                printf("\n1. Insertion\t2. Deletion\n");
                printf("3. Searching\t4. Traversal\n");
                printf("5. Exit\nEnter ur choice:");
                scanf("%d", &ch);
                getchar();
                switch (ch) {
                        case 1:
                                printf("Word to insert:");
                                fgets(str, 100, stdin);
                                printf("Meaning:");
                                fgets(meaning, 256, stdin);
                                insert(str, meaning);
                                break;
                        case 2:
                                printf("Enter the word to delete:");
                                fgets(str, 100, stdin);
                                deleteNode(str);
                                break;
                        case 3:
                                printf("Enter the search word:");
                                fgets(str, 100, stdin);
                                findElement(str);
                                break;
                        case 4:
                                inorderTraversal(root);
                                break;
                        case 5:
                                exit(0);
                        default:
                                printf("You have entered wrong option\n");
                                break;
                }
        }
        return 0;
  }
  Output(C Program To Implement Dictionary Using Binary Search Tree):
  jp@jp-VirtualBox:~/cpgms/data_structures$ ./a.out   
  1. Insertion 2. Deletion   3. Searching 4. Traversal   5. Exit   Enter ur choice:1   Word to insert:old   Meaning:not new   1. Insertion 2. Deletion   3. Searching 4. Traversal   5. Exit   Enter ur choice:1   Word to insert:fan   Meaning: enthusiastic devotee of sports   1. Insertion 2. Deletion   3. Searching 4. Traversal   5. Exit   Enter ur choice:1   Word to insert:ant   Meaning:insect   1. Insertion 2. Deletion   3. Searching 4. Traversal   5. Exit   Enter ur choice:1   Word to insert:candy   Meaning:chocolate   1. Insertion 2. Deletion   3. Searching 4. Traversal   5. Exit   Enter ur choice:1   Word to insert:ball   Meaning:object used in cricket   1. Insertion 2. Deletion   3. Searching 4. Traversal   5. Exit   Enter ur choice:1   Word to insert:pig   Meaning:animal   1. Insertion 2. Deletion   3. Searching 4. Traversal   5. Exit   Enter ur choice:1      Word to insert:queen   Meaning:women ruler   1. Insertion 2. Deletion   3. Searching 4. Traversal   5. Exit   Enter ur choice:4   Word    : ant   Meaning : insect   Word    : ball   Meaning : object used in cricket   Word    : candy   Meaning : chocolate   Word    : fan   Meaning : enthusiastic devotee of sports   Word    : old   Meaning : not new   Word    : pig   Meaning : animal   Word    : queen   Meaning : women ruler   1. Insertion 2. Deletion   3. Searching 4. Traversal   5. Exit   Enter ur choice:2   Enter the word to delete:queen   1. Insertion 2. Deletion   3. Searching 4. Traversal   5. Exit   Enter ur choice:4   Word    : ant   Meaning : insect   Word    : ball   Meaning : object used in cricket   Word    : candy   Meaning : chocolate   Word    : fan   Meaning : enthusiastic devotee of sports   Word    : old   Meaning : not new   Word    : pig   Meaning : animal   1. Insertion 2. Deletion   3. Searching 4. Traversal   5. Exit   Enter ur choice:2   Enter the word to delete:old   1. Insertion 2. Deletion   3. Searching 4. Traversal   5. Exit   Enter ur choice:4   Word    : ant   Meaning : insect      Word    : ball   Meaning : object used in cricket   Word    : candy   Meaning : chocolate   Word    : fan   Meaning : enthusiastic devotee of sports   Word    : pig   Meaning : animal   1. Insertion 2. Deletion   3. Searching 4. Traversal   5. Exit   Enter ur choice:2   Enter the word to delete:candy   1. Insertion 2. Deletion   3. Searching 4. Traversal   5. Exit   Enter ur choice:4   Word    : ant   Meaning : insect   Word    : ball   Meaning : object used in cricket   Word    : fan   Meaning : enthusiastic devotee of sports   Word    : pig   Meaning : animal   1. Insertion 2. Deletion   3. Searching 4. Traversal   5. Exit   Enter ur choice:3   Enter the search word:ant   Word   : ant   Meaning: insect      1. Insertion 2. Deletion   3. Searching 4. Traversal   5. Exit   Enter ur choice:5


Comments

Popular posts from this blog

ORACLE 9i practice solutions

Created by BCL easyConverter SDK 3 (HTML Version)

Zoho Puzzle Questions With Answers

Measuring Time Logic Puzzle You are given with two ropes with variable width. However if we start burning both the ropes, they will burn at exactly same time i.e. an hour. The ropes are non-homogeneous in nature. You are asked to measure 45 minutes by using these two ropes.

How can you do it?

Please note that you can’t break the rope in half as it is being clearly stated that the ropes are non-homogeneous in nature.
Answer & Explanation Solution: 45 minutes

Explanation :
All you have to do is burn the first rope from both the ends and the second rope from one end only simultaneously. The first rope will burn in 30 minutes (half of an hour since we burned from both sides) while the other rope would have burnt half. At this moment, light the second rope from the other end as well. Where, the second rope would have taken half an hour more to burn completely, it will take just 15 minutes as we have lit it from the other end too.

Thus you have successfully calculated 30+15 = 45 minutes …

Hackerrank > SQL > Basic Select

Select
01-Select All
Given a City table, whose fields are described as +-------------+----------+ | Field       | Type     | +-------------+----------+ | ID          | int(11)  | | Name        | char(35) | | CountryCode | char(3)  | | District    | char(20) | | Population  | int(11)  | +-------------+----------+
write a query that will fetch all columns for every row in the table.

My Solution
SELECT*FROM city;
---------------------------------------------------------------------------------
02-Select by ID
Given a City table, whose fields are described as