hash1.cpp

The Hashtable program

//
// Code by Jellydn
// Env : Dev-C++
// Chuong trinh dung bang bam voi cac so nguyen to
//

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
const int N=6; 
const int MAX=100;
typedef int infor;

struct element
{
       infor data;
       element *next;
};

typedef element *List;
List A[N];

// Cac nguyen mau ham
int Hash(int x);
int sngto(int i);
void Create(List A[]);
int Search (int x,List A[]);
void Insert(int x,List A[]);
void Delete(int x,List A[]);
void Delete_c(int i,List A[]);
void Delete_a(List A[]);
void Display(List A[]);

int main()
 {
          int cv,t,i;
          char c;
          Create(A);
          printf("\n  --------------------------------------- ");
          printf("\n |                                       |");
          printf("\n |     Chuong trinh dung bang bam        |");
          printf("\n |   cac so nguyen to nho hon 100        |");
          printf("\n |     vao cac lop co tan cung la :      |");
          printf("\n |           1,2,3,5,7,9                 |");
          printf("\n |                                       |");
          printf("\n  --------------------------------------- ");
          while(1)
          {
                  
                  printf("\n\n");
                  printf("\n  ======================================= ");
                  printf("\n |                                       |");
                  printf("\n |     Main MENU                         |");
                  printf("\n |   [1].Hien bang bam hien tai          |");
                  printf("\n |   [2].Tim mot phan tu                 |");
                  printf("\n |   [3].Them mot phan tu                |");
                  printf("\n |   [4].Xoa mot phan tu                 |");
                  printf("\n |   [5].Xoa mot lop                     |");
                  printf("\n |   [6].Xoa bang bam                    |");
                  printf("\n |   [7].Thoat chuong trinh              |");
                  printf("\n  --------------------------------------- ");
                  printf("\n Ban chon :");
                  scanf("%d",&cv);
                  switch(cv)
                  {
                            case 1 : Display(A); 
                                     printf("\n Press A key to continue...");
                                     getch(); 
                                     break;
                            case 2 : printf("\n Ban muon tim phan tu :");
                                     scanf("%d",&t);
                                     i=Search(t,A);
                                     if(i>=0)
                                       printf("\n Tim thay phan tu trong lop thu %d cua bang bam ",i);
                                     else
                                       printf("\n Khong tim thay phan tu trong bang bam");
                                     printf("\n Press A key to continue...");
                                     getch(); 
                                     break;
                            case 3 : printf("\n Ban muon them phan tu :");
                                     scanf("%d",&t);
                                     Insert(t,A);
                                     printf("\n Press A key to continue...");
                                     getch(); 
                                     break;
                           case 4  : printf("\n Ban muon xoa phan tu :");
                                     scanf("%d",&t);          
                                     Delete(t,A);
                                     printf("\n Press A key to continue...");
                                     getch(); 
                                     break;
                           case 5  : printf("\n Ban muon xoa lop thu :");
                                     scanf("%d",&t);
                                     Delete_c(t,A);
                                     printf("\n Press A key to continue...");
                                     getch(); 
                                     break;
                           case 6  : // Xoa cac ky tu dang con luu trong bo nho dem
                                     char ss[80];
                                     gets(ss);
                                     printf("\n Ban muon xoa bang bam (c/k) ... ?");
                                     c=getchar();      
                                     if(c=='c'||c=='C') Delete_a(A);
                                     printf("\n Press A key to continue...");
                                     getch(); 
                                     break;
                           case 7  : exit(0); break;
                                                             
                                     
                  }
          }
 }

// Cac chuong trinh con
int Hash(int x)
{
    int vt;
    vt=x%10;
    if(vt==1) return 0;
    else if(vt==2) return 1;
    else if(vt==3) return 2;
    else if(vt==5) return 3;
    else if(vt==7) return 4;
    else if(vt==9) return 5;
    else return -1;
 
}
int sngto(int i)
{
    int j=2;
    while( i%j && j<sqrt(i)) j++;
    if (j > sqrt(i)) return 1 ;
    else return 0;
 
}
void Create(List A[])
{
     int i,vt;
     List p;
     // Khoi tao bang bam
     for(i=0;i<N;i++) 
     A[i]=NULL;         
     // Them cac so nguyen to vao cac lop tuong ung trong bang bam
     for(i=2;i<=MAX;i++)
       {
        if(sngto(i))
         {
          // Tao bo nho de them phan tu moi vao bang bam
          p=new element;
          p->data=i;
          // Tim lop de them vao
          vt=Hash(i);
          // Them vao dau lop
          p->next=A[vt];
          A[vt]=p;
                
         }                
         
       }
}
int Search (int x,List A[])
{
    int vt=Hash(x);
    List p;
    if(vt>=0)
    {
    p=A[vt];
    while(p!=NULL && p->data!=x) 
         p=p->next;
    if(p!=NULL) return vt ;
    else return -1;              
    }
    else return -1;
}
void Insert(int x,List A[])
{
    int vt=Hash(x);
    List p;
    if(vt>=0 && sngto(x))
    {
    // Kiem tra da co trong lop
    p=A[vt];
    while(p!=NULL && p->data!=x) 
    p=p->next;
    // Neu co
    if(p!=NULL) printf("\n Da co phan tu %d trong bang bam ",x);
    else // hoac chua
     {
         // tao moi phan tu
         p=new element;
         p->data=x;
         // them vao dau
         p->next=A[vt];
         A[vt]=p;
         printf("\n Da chen phan tu %d vao lop %d",x,vt);
     }
    }
    else
    printf("\n Khong chen vao bang bam vi khong thuoc lop nao ca ");
      
}
void Delete(int x,List A[])
{
    int vt=Hash(x);
    List p,before;
    if(vt>=0)
    {
    // Kiem tra da co trong lop
    p=A[vt];
    while(p!=NULL && p->data!=x) 
    {
    // before chua dia chi cua phan tu truoc phan tu can xoa
    before=p;
    p=p->next;
    } 
    // Neu co
    if(p!=NULL) 
     {
     // Neu phan tu can xoa o dau
     if (p==A[vt]) A[vt]=p->next;
     else          before->next=p->next;
     delete p;
     printf("\n Da xoa phan tu %d ra khoi bang bam ",x);
     }
    else
    printf("\n Khong co phan tu can xoa trong bang bam"); 
    }
    else
    printf("\n Khong co phan tu can xoa trong bang bam");  
 }
void Delete_c(int i,List A[])
{
     List p;
     while(p=A[i])
      {
       A[i]=p->next;
       delete p;           
      }
     
 }
void Delete_a(List A[])
{
     int i;
     for(i=0;i<N;i++)
      Delete_c(i,A);
}
void Display(List A[])
{
     int i;
     List p;
     printf("\n Cac phan tu trong bang bam .");
     for(i=0;i<N;i++)
      {
                     p=A[i];
                     printf("\n Phan tu trong lop thu %d:",i);
                     while(p!=NULL)
                      {
                      printf(" %d ",p->data);
                      p=p->next;             
                      }
      }
}