Everything in a single blog

Thursday, September 11, 2014

C Program->Hashing->Collision->OpenHashing->Chaining

Example Program To Implement Chain Hashing(in C):

#include
#include
#include

struct hash *hashTable = NULL;
int eleCount = 0;

struct node {
int key, age;
char name[100];
struct node *next;
};

struct hash {
struct node *head;
int count;
};

struct node * createNode(int key, char *name, int age) {
struct node *newnode;
newnode = (struct node *)malloc(sizeof(struct node));
newnode->key = key;
newnode->age = age;
strcpy(newnode->name, name);
newnode->next = NULL;
return newnode;
}

void insertToHash(int key, char *name, int age) {
int hashIndex = key % eleCount;
struct node *newnode = createNode(key, name, age);
/* head of list for the bucket with index "hashIndex" */
if (!hashTable[hashIndex].head) {
hashTable[hashIndex].head = newnode;
hashTable[hashIndex].count = 1;
return;
}
/* adding new node to the list */
newnode->next = (hashTable[hashIndex].head);
/*
* update the head of the list and no of
* nodes in the current bucket
*/
hashTable[hashIndex].head = newnode;
hashTable[hashIndex].count++;
return;
}

void deleteFromHash(int key) {
/* find the bucket using hash index */
int hashIndex = key % eleCount, flag = 0;
struct node *temp, *myNode;
/* get the list head from current bucket */
myNode = hashTable[hashIndex].head;
if (!myNode) {
printf("Given data is not present in hash Table!!\n");
return;
}
temp = myNode;
while (myNode != NULL) {
/* delete the node with given key */
if (myNode->key == key) {
flag = 1;
if (myNode == hashTable[hashIndex].head)
hashTable[hashIndex].head = myNode->next;
else
temp->next = myNode->next;

hashTable[hashIndex].count--;
free(myNode);
break;
}
temp = myNode;
myNode = myNode->next;
}
if (flag)
printf("Data deleted successfully from Hash Table\n");
else
printf("Given data is not present in hash Table!!!!\n");
return;
}

void searchInHash(int key) {

int hashIndex = key % eleCount, flag = 0;

struct node *myNode;

myNode = hashTable[hashIndex].head;

if (!myNode) {

printf("Search element unavailable in hash table\n");

return;

}

while (myNode != NULL) {

if (myNode->key == key) {

printf("VoterID : %d\n", myNode->key);

printf("Name : %s\n", myNode->name);

printf("Age : %d\n", myNode->age);

flag = 1;

break;

}

myNode = myNode->next;

}

if (!flag)

printf("Search element unavailable in hash table\n");

return;

}

void display() {

struct node *myNode;

int i;

for (i = 0; i < eleCount; i++) {

if (hashTable[i].count == 0)

continue;

myNode = hashTable[i].head;

if (!myNode)

continue;

printf("\nData at index %d in Hash Table:\n", i);

printf("VoterID Name Age \n");

printf("--------------------------------\n");

while (myNode != NULL) {

printf("%-12d", myNode->key);

printf("%-15s", myNode->name);

printf("%d\n", myNode->age);

myNode = myNode->next;

}

return;

}

int main() {

int n, ch, key, age;

char name[100];

printf("Enter the number of elements:");

scanf("%d", &n);

eleCount = n;

/* create hash table with "n" no of buckets */

hashTable = (struct hash *)calloc(n, sizeof (struct hash));

while (1) {

printf("\n1. Insertion\t2. Deletion\n");

printf("3. Searching\t4. Display\n5. Exit\n");

printf("Enter your choice:");

scanf("%d", &ch);

switch (ch) {

case 1:

printf("Enter the key value:");

scanf("%d", &key);

getchar();

printf("Name:");

fgets(name, 100, stdin);

name[strlen(name) - 1] = '\0';

printf("Age:");

scanf("%d", &age);

/*inserting new node to hash table */

insertToHash(key, name, age);

break;

case 2:

printf("Enter the key to perform deletion:");

scanf("%d", &key);

/* delete node with "key" from hash table */

deleteFromHash(key);

break;

case 3:

printf("Enter the key to search:");

scanf("%d", &key);

searchInHash(key);

break;

case 4:

display();

break;

case 5:

exit(0);

default:

printf("U have entered wrong option!!\n");

break;

}

return 0;

}

Output (C Program To Perform Insertion, Deletion In Chain Hash Table):

jp@jp-VirtualBox:$ ./a.out
Enter the number of elements:3

1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter your choice:1
Enter the key value:3
Name:Sally
Age:23

1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter your choice:1
Enter the key value:33
Name:Harry
Age:25

1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter your choice:1
Enter the key value:7
Name:Nick
Age:30

1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter your choice:1
Enter the key value:35
Name:Raj
Age:28

1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter your choice:4

Data at index 0 in Hash Table:
VoterID Name Age
--------------------------------
33 Harry 25
3 Sally 23

Data at index 1 in Hash Table:
VoterID Name Age
--------------------------------
7 Nick 30

Data at index 2 in Hash Table:
VoterID Name Age
--------------------------------
35 Raj 28

1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter your choice:2
Enter the key to perform deletion:33
Data deleted successfully from Hash Table

1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter your choice:4

Data at index 0 in Hash Table:
VoterID Name Age
--------------------------------
3 Sally 23

Data at index 1 in Hash Table:
VoterID Name Age
--------------------------------
7 Nick 30

Data at index 2 in Hash Table:
VoterID Name Age
--------------------------------
35 Raj 28

1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter your choice:3
Enter the key to search:35
VoterID : 35
Name : Raj
Age : 28

1. Insertion 2. Deletion
3. Searching 4. Display
5. Exit
Enter your choice:5

Courtesy :- http://see-programming.blogspot.in

Wednesday, September 10, 2014

C Program->Hashing->Collision->ClosedHashing->LinearProbing

#include
#include
#include

int tableSize = 0, totEle = 0;
struct node *hashTable = NULL;

struct node {
int age, key;
char name[100];
int marker;
};

void insertInHash(int key, char *name, int age) {
int hashIndex = key % tableSize;
if (tableSize == totEle) {
printf("Can't perform Insertion..Hash Table is full!!");
return;
}
while (hashTable[hashIndex].marker == 1) {
hashIndex = (hashIndex + 1)%tableSize;
}
hashTable[hashIndex].key = key;
hashTable[hashIndex].age = age;
strcpy(hashTable[hashIndex].name, name);
hashTable[hashIndex].marker = 1;
totEle++;
return;
}

void deleteFromHash(int key) {

int hashIndex = key % tableSize, count = 0, flag = 0;

if (totEle == 0) {

printf("Hash Table is Empty!!\n");

return;

}

while (hashTable[hashIndex].marker != 0 && count <= tableSize) {

if (hashTable[hashIndex].key == key) {

hashTable[hashIndex].key = 0;

/* set marker to -1 during deletion operation*/

hashTable[hashIndex].marker = -1;

hashTable[hashIndex].age = 0;

strcpy(hashTable[hashIndex].name, "\0");

totEle--;

flag = 1;

break;

}

hashIndex = (hashIndex + 1)%tableSize;

count++;

}

if (flag)

printf("Given data deleted from Hash Table\n");

else

printf("Given data is not available in Hash Table\n");

return;

}

void searchElement(int key) {

int hashIndex = key % tableSize, flag = 0, count = 0;

if (totEle == 0) {

printf("Hash Table is Empty!!");

return;

}

while (hashTable[hashIndex].marker != 0 && count <= tableSize) {

if (hashTable[hashIndex].key == key) {

printf("Voter ID : %d\n", hashTable[hashIndex].key);

printf("Name : %s\n", hashTable[hashIndex].name);

printf("Age : %d\n", hashTable[hashIndex].age);

flag = 1;

break;

}

hashIndex = (hashIndex + 1)%tableSize;

}

if (!flag)

printf("Given data is not present in hash table\n");

return;

}

void display() {

int i;

if (totEle == 0) {

printf("Hash Table is Empty!!\n");

return;

}

printf("Voter ID Name Age Index \n");

printf("-----------------------------------------\n");

for (i = 0; i < tableSize; i++) {

if (hashTable[i].marker == 1) {

printf("%-13d", hashTable[i].key);

printf("%-15s", hashTable[i].name);

printf("%-7d", hashTable[i].age);

printf("%d\n", i);

}

printf("\n");

return;

}

int main() {

int key, age, ch;

char name[100];

printf("Enter the no of elements:");

scanf("%d", &tableSize);

hashTable = (struct node *)calloc(tableSize, sizeof(struct node));

while (1) {

printf("1. Insertion\t2. Deletion\n");

printf("3. Searching\t4. Display\n");

printf("5. Exit\nEnter ur choice:");

scanf("%d", &ch);

switch (ch) {

case 1:

printf("Enter the key value:");

scanf("%d", &key);

getchar();

printf("Name:");

fgets(name, 100, stdin);

name[strlen(name) - 1] = '\0';

printf("Age:");

scanf("%d", &age);

insertInHash(key, name, age);

break;

case 2:

printf("Enter the key value:");

scanf("%d", &key);

deleteFromHash(key);

break;

case 3:

printf("Enter the key value:");

scanf("%d", &key);

searchElement(key);

break;

case 4:

display();

break;

case 5:

exit(0);

default:

printf("U have entered wrong Option!!\n");

break;

}

return 0;

}

Output (Closed Hashing - Linear probing Example):

jp@jp-VirtualBox:~/cpgms/data_structures$ ./a.out

Enter the no of elements:3

1. Insertion 2. Deletion

3. Searching 4. Display

5. Exit

Enter ur choice:1

Enter the key value:1

Name:Harry

Age:23

1. Insertion 2. Deletion

3. Searching 4. Display

5. Exit

Enter ur choice:1

Enter the key value:2

Name:Ram

Age:24

1. Insertion 2. Deletion

3. Searching 4. Display

5. Exit

Enter ur choice:1

Enter the key value:3

Name:Raj

Age:23

1. Insertion 2. Deletion

3. Searching 4. Display

5. Exit

Enter ur choice:4

Voter ID Name Age Index

-----------------------------------------

3 Raj 23 0

1 Harry 23 1

2 Ram 24 2

1. Insertion 2. Deletion

3. Searching 4. Display

5. Exit

Enter ur choice:2

Enter the key value:1

Given data deleted from Hash Table

1. Insertion 2. Deletion

3. Searching 4. Display

5. Exit

Enter ur choice:4

Voter ID Name Age Index

-----------------------------------------

3 Raj 23 0

2 Ram 24 2

1. Insertion 2. Deletion

3. Searching 4. Display

5. Exit

Enter ur choice:1

Enter the key value:10

Name:Ravi

Age:23

1. Insertion 2. Deletion

3. Searching 4. Display

5. Exit

Enter ur choice:4

Voter ID Name Age Index

-----------------------------------------

3 Raj 23 0

10 Ravi 23 1

2 Ram 24 2

1. Insertion 2. Deletion

3. Searching 4. Display

5. Exit

Enter ur choice:3

Enter the key value:10

Voter ID : 10

Name : Ravi

Age : 23

1. Insertion 2. Deletion

3. Searching 4. Display

5. Exit

Enter ur choice:5

Courtesy :- http://see-programming.blogspot.in

Wednesday, May 21, 2014

C++ and Data Encapsulation

All C++ programs are composed of the following two fundamental elements:

Program statements (code): This is the part of a program that performs actions and they are called functions.
Program data: The data is the information of the program which affected by the program functions.

Encapsulation is an Object Oriented Programming concept that binds together the data and functions that manipulate the data, and that keeps both safe from outside interference and misuse. Data encapsulation led to the important OOP concept of data hiding.

Data encapsulation is a mechanism of bundling the data, and the functions that use them and data abstraction is a mechanism of exposing only the interfaces and hiding the implementation details from the user.

C++ supports the properties of encapsulation and data hiding through the creation of user-defined types, called classes. We already have studied that a class can contain private, protected and publicmembers. By default, all items defined in a class are private. For example:

class Box
{
   public:
      double getVolume(void)
      {
         return length * breadth * height;
      }
   private:
      double length;      // Length of a box
      double breadth;     // Breadth of a box
      double height;      // Height of a box
};

The variables length, breadth, and height are private. This means that they can be accessed only by other members of the Box class, and not by any other part of your program. This is one way encapsulation is achieved.

To make parts of a class public (i.e., accessible to other parts of your program), you must declare them after the public keyword. All variables or functions defined after the public specifier are accessible by all other functions in your program.

Making one class a friend of another exposes the implementation details and reduces encapsulation. The ideal is to keep as many of the details of each class hidden from all other classes as possible.

Data Encapsulation Example:

Any C++ program where you implement a class with public and private members is an example of data encapsulation and data abstraction. Consider the following example:

#include 
using namespace std;

class Adder{
   public:
      // constructor
      Adder(int i = 0)
      {
        total = i;
      }
      // interface to outside world
      void addNum(int number)
      {
          total += number;
      }
      // interface to outside world
      int getTotal()
      {
          return total;
      };
   private:
      // hidden data from outside world
      int total;
};
int main( )
{
   Adder a;
   
   a.addNum(10);
   a.addNum(20);
   a.addNum(30);

   cout << "Total " << a.getTotal() <<endl;
   return 0;
}

When the above code is compiled and executed, it produces the following result:

Total 60

Above class adds numbers together, and returns the sum. The public members addNum and getTotalare the interfaces to the outside world and a user needs to know them to use the class. The private member total is something that is hidden from the outside world, but is needed for the class to operate properly.

Designing Strategy:

Most of us have learned through bitter experience to make class members private by default unless we really need to expose them. That's just good encapsulation.

This wisdom is applied most frequently to data members, but it applies equally to all members, including virtual functions.

Courtesy to : http://www.tutorialspoint.com/cplusplus/cpp_data_encapsulation.htm

Everything in a single blog

Thursday, September 11, 2014

C Program->Hashing->Collision->OpenHashing->Chaining

Wednesday, September 10, 2014

C Program->Hashing->Collision->ClosedHashing->LinearProbing

Wednesday, May 21, 2014

C++ and Data Encapsulation

Data Encapsulation Example:

Designing Strategy:

About Me

Blog Archive