BẢNG BĂM ĐÓNG
Chiến lược băm một chuỗi:
- Chuyển chuỗi sang số
Code:
long int StringToNumber(Node Key) {
int temp = 0;
for(int i = 0; i<strlen(Key); i++)
temp+=(int)Key[i];
return temp;
}
- Hàm băm
Code:
int H(long int k) {
return k%B;
}
- Khi đụng khóa ta có chiến lược băm lại như sau: i = H(k+j), j=1..B-1
Code:
int k = StringToNumber(Key);
int i = H(k), j = 1;
while(strcmp((*T).Key[i],"")) {
i = H(k+j); //bam lai
j++;
}
strcpy((*T).Key[i],Key);
(*T).n++;
Chương chình mẫu:
Code:
#include <stdio.h>
#include <conio.h>
#include <ctype.h>
#include <string.h>
#define B 10
//cau tru du lieu cua node
typedef char Node[30];
typedef struct Tab {
Node Key[B];
int n;
};
//chuyen chuoi sang so
long int StringToNumber(Node Key) {
int temp = 0;
for(int i = 0; i<strlen(Key); i++)
temp+=(int)Key[i];
return temp;
}
//ham bam
int H(long int k) {
return k%B;
}
//khoi tao bang bam
void MakeNull(Tab *T) {
for(int i = 0; i<B; i++)
strcpy((*T).Key[i],"");
(*T).n = 0;
}
//kiem tra node co trong bang bam
char Member(Node Key, Tab T) {
int i = H(StringToNumber(Key));
int n = 0;
while(strcmp(T.Key[i],Key) && strcmp(T.Key[i],"") && n<B){
i++;
n++;
if(i>=B)
i-= B;
}
return (strcmp(T.Key[i],Key) == 0);
}
//chen phan tu vao bang bam
void Insert(Node Key, Tab *T) {
if((*T).n == B){
printf("\nBang bam bi day khong them khoa \"%s\" vao duoc.",Key);
}
else
if(Member(Key,*T))
printf("\nKhoa da ton tai!");
else {
int k = StringToNumber(Key);
int i = H(k), j = 1;
while(strcmp((*T).Key[i],"")) {
i = H(k+j); //bam lai
j++;
}
strcpy((*T).Key[i],Key);
(*T).n++;
}
}
//Xoa phan tu khoi bang bam
void Delete(Node Key, Tab *T) {
int i = H(StringToNumber(Key));
int n = 0;
while(strcmp((*T).Key[i],Key) && strcmp((*T).Key[i],"") && n<B){
i++;
n++;
if(i>=B)
i-= B;
}
if(strcmp((*T).Key[i],Key) == 0) {
strcpy((*T).Key[i],"");
(*T).n--;
}
else
printf("\nKhoa khong co trong bang bam!");
}
//Xuat bang bam
void Write(Tab T) {
printf("\n----- BANG BAM -----");
for(int i =0; i<B; i++)
printf("\nT[%d]:\t%s ",i,T.Key[i]);
}
//giao dien chuong trinh
int Menu() {
int ch;
clrscr();
printf("BANG BAM DONG\n");
printf(" 1. Them mot khoa vao bang bam\n");
printf(" 2. Xoa khoa trong bang bam\n");
printf(" 3. Xoa toan bo bang bam\n");
printf(" 4. Duyet bang bam\n");
printf(" 5. Tim kiem tren bang bam\n");
printf(" 6. Ket thuc chuong trinh.\n");
printf(" Chon tu 1 den 6: ");
scanf("%d",&ch);
return ch;
}
//chuong trinh chinh
void main() {
Tab T;
char ch, flag = 1;
Node Key;
MakeNull(&T);
while(flag){
ch = Menu();
switch(ch){
case 1:
{
clrscr();
printf("THEM KHOA MOI VAO BANG BAM\n");
printf("Nhap khoa: ");
flushall();
gets(Key);
Insert(Key,&T);
getch();
break;
}
case 2:
{
clrscr();
printf("XOA KHOA KHOI BANG BAM\n");
printf("Nhap khoa: ");
flushall();
gets(Key);
Delete(Key,&T);
getch();
break;
}
case 3:
{
clrscr();
printf("XOA TOAN BO BANG BAM\n");
printf("Ban co chac khong?(C/K)");
flushall();
ch = getch();
ch =_toupper(ch);
if(ch=='C')
MakeNull(&T);
break;
}
case 4:
{
clrscr();
printf("DUYET BANG BAM");
Write(T);
getch();
break;
}
case 5:
{
clrscr();
printf("TIM KHOA TREN BANG BAM\n");
printf("Nhap khoa: ");
flushall();
gets(Key);
if(!Member(Key,T))
printf("Khong tim thay \"%s\" tren bang bam",Key);
else
printf(" Khoa \"%s\" co trong T[%d]",Key,H(StringToNumber(Key)));
getch();
break;
}
case 6: flag = 0;
default: break;
}
}
}