선형조사법

/*

 * consolapplicaton.c

 *

 *  Created on: 2014. 11. 18.

 *      Author: SEC

 */

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define KEY_SIZE 10
#define TABLE_SIZE 13
#define empty(e) (strlen(e.key)==0)
#define equal(e1,e2) (!strcmp(e1.key,e2.key))
#define NULL 0

typedef struct {

 char key[KEY_SIZE];

}element;

element hash_table[TABLE_SIZE];

void init_table(element ht[]){

 int i;
 for(i=0; i<TABLE_SIZE; i++){
  ht[i].key[0] = NULL;
 }
}

//문자로 된 탐색키를 숫자로 변환

int transform(char *key){

 int number = 0;
 while(*key)
  number += *key++;
 return number;

}

 

int hash_function(char *key){

 return transform(key) % TABLE_SIZE;

}

//선형 조사법을 이용하여 테이블에 키를 삽입하고,

//테이블이 가득 찬 경우는 종료

void hash_lp_add(element item, element ht[]){

 int i, hash_value;

 hash_value = i = hash_function(item.key);

 while(!empty(ht[i])){

  if(equal(item, ht[i])){
   fprintf(stderr, "탐색키가 중복되었습니다.\n");
  return;
  }

  i = (i+1) % TABLE_SIZE;

  if(i == hash_value){
   fprintf(stderr, "테이블이 가득찼습니다\n");
  return;

  }

 }

 ht[i] = item;

}

//선형 조사법을 이용하여 테이블에 저장된 키를 탐색

void hash_lp_search(element item, element ht[]){

 int i, hash_value;

 hash_value = i = hash_function(item.key);

 while(!empty(ht[i])){

  if(equal(item,ht[i])){
   fprintf(stderr, "탐색 성공 :위치 = %d\n", i);
   return;
  }

  i = (i+1)% TABLE_SIZE;

  if(i == hash_value){
   fprintf(stderr, "찾는 값이 테이블에 없음\n");
   return;
  }
 }

 fprintf(stderr, "찾는 값이 테이블에 없음\n");

}

 

void hash_lp_print(element ht[]){
 int i;
 for(i=0; i<TABLE_SIZE; i++)
  printf("[%d] %s\n",i, ht[i].key);

}

 

int main(void){

 element temp;
 for(int i = 0; i<KEY_SIZE; i++){
  temp.key[i] = NULL;
 }

 
 int op;

 while(1){
  printf("원하는 연산을 입력하시오(0=입력, 1=탐색, 2=종료)=");
  scanf("%d",&op);
  if( op == 2) break;
  switch(op){
  case 0:{
   printf("키를 입력하시오=");
   scanf("%s",temp.key);
   hash_lp_add(temp,hash_table);
   break;
  }

  case 1:{
   printf("키를 입력하시오=");
   scanf("%s",temp.key);
   hash_lp_search(temp,hash_table);
   break;
  }
  case 2:{
   break;
   }

  default:{
   printf("잘못된 입력\n");
   break;
  }

  hash_lp_print(hash_table);

  }

 }

}