BẢNG BĂM MỞ
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;
}Chương trình minh họa:
Code:
#include "stdio.h"
#include "conio.h"
#include "ctype.h"
#include "stdlib.h"
#include "string.h"
#define B 10
typedef char Data[25];
typedef struct Node {
Data Key;
Node *Next;
};
typedef Node *TNode;
typedef TNode Tab[B];
//Khoi tao 1 nut
TNode GetNode(Data Key) {
TNode p;
p =(TNode)malloc(sizeof(Node));
strcpy(p->Key,Key);
p->Next = NULL;
return p;
}
//chuyen chuoi sang so
long int StringToNumber(Data 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 ban bam rong
void MakeNull(Tab *T) {
for(int i=0; i<B; i++)
(*T)[i] = NULL;
}
//kiem tra nut tren bang bam
char Member(Data Key, Tab T) {
TNode p;
int i = H(StringToNumber(Key));
p = T[i];
while(p && strcmp(Key,p->Key))
p = p->Next;
return (p!= NULL);
}
//them 1 nut
void Insert(Data Key, Tab *T) {
if(Member(Key,*T))
printf("\nKhoa da ton tai.");
else
{
int i = H(StringToNumber(Key));
TNode p;
//chen dau
p = GetNode(Key);
p->Next = (*T)[i];
(*T)[i] = p;
}
}
//xoa 1 node
void DeleteNode(Data Key, Tab *T){
int i = H(StringToNumber(Key));
if(!Member(Key,*T)){
printf("\nKhong ton tai khoa \"%s\".",Key);
getch();
}
else {
TNode p, q;
p = q = (*T)[i];
while(p && strcmp(p->Key,Key)){
q = p;
p = p->Next;
}
if(p==(*T)[i]) { //xoa dau
(*T)[i] = p->Next;
free(p);
}
else
if(p->Next==NULL) //xoa cuoi
{
q->Next = NULL;
free(p);
}
else { //xoa giua
q->Next = p->Next;
free(p);
}
}
}
//Xoa 1 khoa
void DeleteKey(int i, Tab *T){
TNode p, q;
p = (*T)[i];
while(p){
q = p;
p = p->Next;
free(q);
}
(*T)[i] = NULL;
}
//xoa toan bo ban bam
void Delete(Tab *T) {
for(int i=0; i<B; i++)
DeleteKey(i,T);
}
//duyet theo khoa
void WriteKey(int i, Tab T) {
TNode p = T[i];
printf("\nT[%d] : ",i);
while(p){
printf("%s\t-- ",p->Key);
p = p->Next;
}
}
//duyet toan ban bam
void Write(Tab T){
printf("\nBANG BAM MO");
for(int i=0; i<B; i++)
WriteKey(i,T);
}
//giao dien chuong trinh
int Menu() {
int ch;
clrscr();
printf("BANG BAM MO\n");
printf(" 1. Them mot nut vao bang bam\n");
printf(" 2. Xoa 1 nut trong bang bam\n");
printf(" 3. Xoa 1 khoa trong bang bam\n");
printf(" 4. Xoa toan bo bang bam\n");
printf(" 5. Duyet bang bam\n");
printf(" 6. Tim kiem 1 nut tren bang bam\n");
printf(" 7. Ket thuc chuong trinh.\n");
printf(" Chon tu 1 den 7: ");
scanf("%d",&ch);
return ch;
}
//chuong trinh chinh
void main() {
Tab T;
char ch, flag = 1;
Data Key;
MakeNull(&T);
while(flag){
ch = Menu();
switch(ch){
case 1:
{
clrscr();
printf("THEM 1 NUT MOI VAO BANG BAM\n");
printf("Nhap nut: ");
flushall();
gets(Key);
Insert(Key,&T);
getch();
break;
}
case 2:
{
clrscr();
printf("XOA 1 NUT KHOI BANG BAM\n");
printf("Nhap nut: ");
flushall();
gets(Key);
DeleteNode(Key,&T);
getch();
break;
}
case 3:
{
clrscr();
printf("XOA 1 KHOA KHOI BANG BAM\n");
printf("Nhap khoa: ");
int k;
scanf("%d",&k);
if(k>=0 && k<B) {
DeleteKey(k,&T);
printf("Da xoa xong.");
}
else
printf("Khoa khong ton tai.");
getch();
break;
}
case 4:
{
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 5:
{
clrscr();
printf("DUYET BANG BAM");
Write(T);
getch();
break;
}
case 6:
{
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 7: flag = 0;
default: break;
}
}
}