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;
      }
   }
}