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)

C Questions

C Questions
C Questions

Note : All the programs are tested under Turbo C/C++ compilers.
It is assumed that,
Programs run under DOS environment, The underlying machine is an x86 system, Program is compiled using Turbo C/C++ compiler.
The program output may depend on the information based on this assumptions (for example sizeof(int) == 2 may be assumed).
Predict the output or error(s) for the following:

void main()
{
int const * p=5; printf("%d",++(*p));
}
Answer:
Compiler error: Cannot modify a constant value.
Explanation:
p is a pointer to a "constant integer". But we tried to change the value of the "constant integer".
main()
{
char s[ ]="man"; int i;
for(i=0;s[ i ];i++)
printf("\n%c%c%c%c",s[ i ],*(s+i),*(i+s),i[s]);
}
Answer: mmmm
aaaa nnnn
Explanation

Zoho Interview | Set 1 (Advanced Programming Round)

Third Round: (Advanced Programming Round) Here they asked us to create a “Railway reservation system” and gave us 4 modules. The modules were:
    1. Booking
    2. Availability checking
    3. Cancellation
    4. Prepare chart
We were asked to create the modules for representing each data first and to continue with the implementation phase.

 My Solution :

#include<stdio.h>#include<conio.h>#include<stdlib.h>#include<string.h>#include<iostream.h>#include<time.h>#include<iomanip.h>#include<fstream.h>char f[10]="f";char s[10]="s";int addr,ad,flag,f1,d,m,i,amt;float tamt; class login {public:char id[100];char pass[100];char*password;void getid(){ cout<<"Enter your id:";gets(id); password=getpass("Enter the password:");strcpy(pass,password);}void displayid(){ cout<<"Id:";puts(id); cout<<"Password:";puts(pass);}}; class detail {public:in…