558 Programming and Data Structures
calculated and their mid digits are evaluated. Based on the mid digits the keys are paced in the
appropriate index. Here the mid digit obtained can be from 0 to 9. Hence, we may need up to ten
indices starting from index 0 through index 9.
For example, if the key is k=10,
H(10)=(10*10)=100.
Its middle digit is 0. Hence, number 10 would be placed in index 0. Similarly, the same procedure is
adopted for all other numbers and they are placed in different indices based on the mid digit value.
Consider the following numbers for constricting the hashing table.
12,14,18,20,36,31,27,35,23,59.
Table 15.2 Table of key, square and mid
Key
Square Mid
12
144 4
14 196 9
18
324 2
20 400 0
26
676 7
31
961 6
27 729 2
15 225 2
23
529 2
23
841 4
Table 15.3 Hashing table using the mid-square method
Index Keys
0
20
1
-
2 18,27,15,23
3
-
4 12,29
5
-
6 31
7 26
8
-
9
14
A program is prepared for hashing table using the mid-square method.
15.5 Write a program to display the hash table, which is to be prepared by using the mid-square
method.
iincludfrcstdio. h>
fincludecconio. h>
main()
{
Int msarr[6]-{l8,21,29,27,12,ll},sel[€),B«2[6] ,ma3 [6],me4[6] ;
int a,l,ml,m2,ia3,2B4,amid;
Non-Linear Data Structure 559
int squmid(int) ;
void disp (int farr [] , int count);
c lrs c r();
ml=m2^m3=an4=0;
printf ("The numbers are as follow s:n");
fo r(i»l;i< «7 ; i++)
p rin tf("t%d",msarr[i]);
for (a*l;a<7;a++)
{
smidesqu mid (xnsarr [a ]);
switch (smid)
{
case 1:
{ ml++; msl [ml] *msarr [a] ; break; }
case 2:
{ m2++; ms2 [m2] smsarr [a] ; break; }
case 3:
{ m3++; ms3 [m3] «xasarr [a ] ; break; }
case 4:
{ m4-f ; ms4 [m4] amsarr [a] ; break; }
}
}
printf ("nnThe Hash Table with Mid-Square method is as follow s:" );
printf ("n
....
........
—
.........
-
................
") ;
printf (" Indexl: ");
disp(msl.ml) ;
printf ("
lndex2: ");
disp(ms2,m2) ;
printf ("
lndex3: ■);
disp(ms3,m3) ;
printf ("
lndex4: ■);
disp (ms4,m4);
printf ("n-------------------------------------------n");
int squ mid (int ele)
{
int squ=0,mid,n;
squ=ele*ele;
for(n*0;n<2;n++)
560 Programming and Data Structures
{
midassqu%10;
squ=squ/10;
}
return mid ;
void disp(int fa rr [] , int count)
{
int al;
for (a l= l; al<=count; al++)
printf ("%5d" , farr [ail]);
QLOTUI:
The numbers are as follows:
21 29 27 12 11 64 0
The Hash Table with Mid-Square method is as follows:
Index 1:
Index 2: 27 11
Index 3:
Index 4: 21 29 12
Explanation In the above program the main array 'msarr[]' having six elements is declared. In
addition to the above, /ml[]'/m 2[]'/m3[]' and 'm4[] are initialized . These arrays are initialized for
storing the index. Two functions are declared, squ mid () ; and d is (); . These two functions are
initialized for finding the middle digit of the square and display the keys. By using the mod operator,
the middle digit of the square number is calculated. After finding, the middle digit they are displayed
in the hash table.
The folding method: In the folding method, the key is divided into a number of parts. The parts, of
course, are dependent on the length of the key All the parts are added together. If the carry results from
this operation it is to be ignored and the number that remains behind after ignoring the carry is the
address of the key. By using this method, we fold the key. Hence, this method is called folding method.
For example, consider the following cases.
1) k = 879987: By using this method, we divide it in two parts like 879 and 987. They are added,
carry is ignored and the number after ignoring the carry becomes the address of the key. 879 +987
= 1866. Its most significant digit is 1. Hence, after ignoring l,the number that is left is 687 which
is the address of the key.
2) k=678897678 In this key is divided into the three parts. They are 678,897 and 678. By adding,
678+897+678= 2253. After ignoring last carry 2, the number that is left is 253. Therefore, 253 is the
address of the key Thus, the folding method is useful in converting a multiword key in to a single
word. By applying the hashing function, the key can be identified. The program can be developed
by the reader.
Non-Linear Data Structure 561
The length dependent method: One more hashing technique used is length dependent method. In
this method, the length of the key is measured and the number is placed in the Index table appropriately.
Here a simple program is made to search an element from the array. The program is self-explanatory.
Length of an array and length of each element can be anything, but some finite value can be taken.
15.6 Write a program for searching an element by using the length dependent hash function.
Display the hash table and search the element from the table.
#include<stdio.h>
#include<canio. h>
main ()
{
int arr [5] , ini [5] , in2 [5] , in3 [5], in4 [5] , in5 [5];
int a, i , len, 11,12,13,14,15, snum;
int length (in t);
void disp (int fa rr[] ,int count) ;
void search(int sa rr[] , int n,int co) ;
clrs c r();
Il=i2=i3*i4=i5=0;
p rin tf("
Enter the number of the elements; " );
for(ial;i<=5;i++)
scanf ("%d", &arr [ i ] );
for (a=l;a<6;a++)
{
len*length(arr[a]);
prin tf C
The length of %d is:%d",a rr[a] ,len) ;
switch (len)
{
case 1:
{ il+ +; i n i [ i l ] = a r r [ a ]; break; }
case 2:
{ i2++; in 2 [i2 ]= a r r[a ]; break; }
case 3:
{ i3++; in 3 [i3 ]= a r r [a ]; break; }
case 4:
{ i4++; in 4[14]= a r r [a ]; break; }
case 5:
{ i5++; in 5 [i5 ]* a r r [a ]; break; }
}
}
printf ( ”nThe Hash Table is as follows: ”);
printf (" n-------------------------------------------
") ;
printf ( "Index 1: ") ;
disp (ini, i l ) ;
p rin t f("
lndex 2: ") ;
562 Programming and Data Structures
di*p(in2,12);
printf ("
lndex 3 :");
disp(in3,13);
printf (■
lndex 4 :");
d is p(in4 ,i4 );
printf ("
lndex 5 :”);
<lisp(in5,i5);
printf ("n
----------------------
.....................n");
printf ( "Eater the number to search:") ;
scanf ("%d”,&8Dum);
len*length (snum);
switch (len)
{
case 1:
H
-H
I
i
1
*
m
; prin tf ("in Index 1") ; break; }
case 2:
{ search(in2,snum, 12); prin tf ( "in Index 2") ;
break; }
case 3:
{ search(in3, snum, 13); prin tf ("in Index 3"); break; }
case 4:
{ search (in4, snum, 14); printf ("in Index 4") ; break; }
case 5:
{ search(in5,snum, 15); printf ("in Index 5" ); break; }
}
}
int length (int ele)
{
int c»0,num;
while (ele>0)
{
if(el«> -10 )
{
ela-ala/10;
C++;
}
else
{
c+-f;
break;
}
}
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.