자료구조 마지막 실습..

오늘로서 자료구조 수업 및 시험이 모두 끝났다.

C 언어 야매로 배웠더니 2학년 과목이었음에도 불구하고 힘들었던듯 ㅡㅡ;

마지막 실습은 해싱. 오버플로 처리도 없는 해싱이다.ㅋㅋ

/*
***********************************************************************/
/* 작성자 : 박상현                                                                     */
/* 작성일 : 2008. 06. 12
/* Hashing
/************************************************************************/
// 헤더파일 선언
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#define FULL    1                       // FULL 플래그 정의
// slot 구조체 선언
typedef struct
{
        char key[11];
} slot;
// 해시 테이블 구조체 선언
typedef struct
{
        int fullFlag;                           // 버킷이 꽊 찼는지 표시하는 플래그
        int slotCnt;                            // 슬롯이 찬 개수를 표시
        slot s[2]; // 배열 선언할때는 그러네. 그럼 기본 데이터가 하나 있어야되냐
} element;

int collCnt = 0;                        // 콜리전 횟수
int overCnt = 0;                        // 오버플로 횟수
element hash_table[50];         // 50 크기의 해시 테이블 선언

void initTable();                                       // 해시테이블 초기화
int hash(char *key);                                                    // 해시함수
void linearInsert(slot item);           // 데이터 삽입


void main()
{
        FILE *fp;                                                                               // 파일 포인터
        fp = fopen("data.txt", "r");                                    // 읽기 전용으로 open
        int i = 0, cnt = 0;
        char temp[11];                                                                  // 임시 문자열
        slot item;                                                                              // 임시 슬롯
        int dataCnt = 0;                                                                // 총 데이터 갯수
        while(1)                                                                                // fin 이 나올 때까지 loop
        {
                fscanf(fp, "%s\n", temp);                                       // 파일로부터 문자를 읽어옴
                strcpy(item.key, temp);                                         // 임시 item 에 삽입
                if(strcmp(temp, "fin") == 0)                            // fin 을 만나면 종료    
                        break;
                linearInsert(item);                                                     // 해시테이블에 삽입
                dataCnt++;                                                                      // 데이터 갯수 증가
        }

        printf("\t\tslot1    |    slot2    \n");
        // 해시테이블 출력
        for(i = 0 ; i < 50 ; i++)
        {
                printf("hash value : %d ", i);
                printf("%s  %s\n", hash_table[i].s[0].key, hash_table[i].s[1].key);
        }
        // 각 카운트 변수들 출력
        printf("dataCnt : %d\noverflow : %d\ncollision : %d\n", dataCnt, overCnt, collCnt);

}

/************************************************************************/
/* 함수명 :linearInsert                                                                     */
/* item 을 인자로 받아 해시테이블에 삽입한다.                                           */
/************************************************************************/
void linearInsert(slot item)
{
        int hash_value;
        hash_value = hash(item.key);                    // 해시펑션을 이용하여 해시 값을 구한다.

        // 버킷에 공간이 있다면
        if(hash_table[hash_value].fullFlag != FULL)
        {
                // 슬롯이 하나도 안찼다면
                if(hash_table[hash_value].slotCnt == 0)
                {
                        hash_table[hash_value].slotCnt++;       // 슬롯 count 증가
                        strcpy(hash_table[hash_value].s[0].key, item.key);              // 데이터를 슬롯에 insert

                }
                // 두 개의 슬롯 중 하나만 찼다면
                else
                {
                        collCnt++;                      // Collision 변수 증가
                        hash_table[hash_value].fullFlag = FULL;                 // 슬롯이 꽉찼으므로 플래그를 FULL 로..
                        strcpy(hash_table[hash_value].s[1].key, item.key);              // 데이터를 슬롯에 insert

                }
        }
        // 버킷이 꽉 찼다면
        else
        {
                overCnt++;      // Overflow 변수 증가
                collCnt++; // Collision 변수 증가
        }
}

/************************************************************************/
/* 함수명 : hash                                                                  */
/* key 값을 인자로 받아 재산 잔여법을 사용하여 해싱한뒤 그 값을 리턴한다. */
/************************************************************************/
int hash(char *key)
{
        unsigned hash_value;
        for(hash_value = 0 ;  *key != '\0' ; key++)
            hash_value = *key + 51 * hash_value;

    return hash_value % 50;
}

/************************************************************************/
/* 함수명 : initTable                                                                     */
/* 해시테이블을 초기화 한다.
/************************************************************************/
void initTable()
{
        int i;
        for(i = 0 ; i < 50 ; i++)
        {
                hash_table[i].s[0].key[0] = NULL;
                hash_table[i].s[1].key[0] = NULL;

        }
}

Posted by 행복한 프로그래머 궁금쟁이박

댓글을 달아 주세요