[25일차] 탐색 알고리즘(순차, 이분, 이진트리, 레드-블랙, 해쉬)

여러 탐색 알고리즘에 대해 배웠다.

• 순차 검색
• 이분 검색
• 이진트리 검색
• 해쉬 검색

---

• 순차 검색 가장 단순한 탐색방법. 주어진 자료 파일에서 처음부터 검색키에 해당하는 레코드를 순차적으로 비교.
  - 장점 : 조직화 및 정렬 필요 없다. 매우 단순하다. 작은 데이터를 검색할 때 효율적
  - 단점 : 평균적으로 약 N/2번의 비교를 해야 하기 때문에 속도가 느리다.

C 표준함수에 포함되어있음

delete니 insert에서는 num을 증가, 감소시켜줘야 해서 포인터로 받는다.

void Is_search(int key, int a[], int *num)
{
	int i=0;
    while(a[i] != key && I < *num)	i++;	// 키값을 찾음
    return (i< *num ? i : -1); //찾았으면 인덱스를 아니면 -1을 리턴
}

 

• 이분 검색

아주 유명하고 쉽게 구현할 수 있다. 

 key값에 따라 left, right, mid를 변경해가며 값을 찾아가는 알고리즘.

이분 검색의 개선으로 보간법을 이용할 수 있다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int BinarySearch(int key, int *data, int n)
{
    int left, right, mid;

    left = 0; // 배열 처음
    right = n - 1; // 배열 끝
    
    mid = -1; // 첫 반복 조건 충족을 위한 무의미한 값
    while( mid != left )
    {
/*
	TODO: find mid index
*/
        mid = (left + right) / 2;

/*
	TODO: if data @ mid is equal to key ,  return mid index.
*/
        if(data[mid] == key)
            return mid;

/*
	TODO: if data @ mid is less than key ,  return next to mid index 
*/
        if(data[mid] < key)
            left = mid + 1;

        else // data[mid] > key
            right = mid - 1;
    }

    return -1;
}

int main(void)
{
    int i, N;

    srand((unsigned int)time(NULL));
    N = rand() % 100;
	
    // 가변 길이 배열(VLA; Variable Length Array)
    int data[N];

    for(i=0; i<N; i++)
        data[i] = i;

    int key, idx;
    for(i=0; i<N; i++)
    {
        key = rand() % N;
        idx = BinarySearch(key, data, N);

        if(idx == -1)
        {
            printf("[Error] BinarySearch : "
                   "incorrect logic \n");
            
            return 1;
        }

        printf("found : %4d  by binary searching algorithm\n", idx);
    }

    return 0;
}

 

• 이진트리 검색

트리는 개념을 다시 봐야겠다.

특히 레드-블랙 이진트리에 대해.

 

이진탐색트리

//이진탐색트리
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

// 이진 탐색 트리를 구성하는 노드
typedef struct _tree_node
{
    struct _tree_node *left;    // 왼쪽 자식노드
    struct _tree_node *right;   // 오른쪽 자식노드
    int data;
} Node;

// 이진 탐색 트리
typedef struct __binary_search_tree
{
    Node *treeEntry;    // 이진탐색트리의 루트노드
    int elemCnt;        // 트리의 노드 갯수
    Node *gotLatest;    // 마지막으로 검색된 노드 주소
} BST_Tree;

// 노드 생성
Node *BST_Create_Node(int data);

// 이진탐색트리 초기화
int BST_Init_Tree(BST_Tree *tree);

// 노드 탐색
Node *BST_Search(BST_Tree *tree, int key);

// 부모 노드를 리턴
Node *BST_Get_Parent(BST_Tree *tree, Node *target);

// 노드 삽입
void BST_Insert(BST_Tree *tree, Node *target);
// 기준점으로부터의 최대값노드 리턴
Node *BST_Get_Max(Node *root);

// 노드 삭제
void BST_Delete(BST_Tree *tree, Node *target);

// 트리의 전체 노드 삭제
void BST_DestroyTree(BST_Tree *tree);

// 전위순회 출력
void __print_preorder(Node *p);

// 무작위 데이터, 무작위 위치 삽입/삭제 테스트 함수
void __tree_test(BST_Tree *tree, int range, int rep);


int main(void)
{
    BST_Tree *numList = (BST_Tree *)malloc(sizeof(BST_Tree));

    BST_Init_Tree(numList);

    __tree_test(numList, 100, 20);
   
    printf("모든 노드 삭제 완료 !! \n");

    return 0;
}


Node *BST_Create_Node(int data)
{
    Node *pTemp = (Node *)malloc(sizeof(Node));
    if(!pTemp)
        return NULL;        

    pTemp->data = data;
    pTemp->left = NULL;
    pTemp->right = NULL;

    return pTemp;
}

int BST_Init_Tree(BST_Tree *tree)
{
    tree->treeEntry = NULL;
    tree->elemCnt = 0;
    tree->gotLatest = NULL;

    return 0;
}

Node *BST_Search(BST_Tree *tree, int key)
{
    Node *p = tree->treeEntry;

    while(p != NULL)
    {
        if(p->data == key)
        {
            tree->gotLatest = p;
            return p;
        }

        if(p->data > key)
            p = p->left;

        else
            p = p->right;
    }

    return NULL;
}

Node *BST_Get_Parent(BST_Tree *tree, Node *target)
{
    Node *p, *parent;

    if(tree->elemCnt < 2)
        return NULL;

    if(tree->treeEntry == target)
        return NULL;


    parent = tree->treeEntry;

    if(target->data > parent->data)
        p = parent->right;
    else
        p = parent->left;

    // 위 조건문에서 이미 p는 parent보다 1레벨 증가한 상태
    // (p를 parent밑으로 놓아야하는데, 왼쪽에 놓을지 
    // 오른쪽에 놓을지 결정한 것)
    while(p != NULL)
    {
        if(target->data == p->data)
            return parent;

        // p위치를 parent에 유지시켜놓고
        parent = p;


        // p만 이동, 그러면 parent는 부모 자리에 남게됨
        if(target->data > p->data)
            p = p->right;

        else
            p = p->left;
    }

    return NULL;
}

void BST_Insert(BST_Tree *tree, Node *target)
{
    if(target == NULL)
        return;
    if(BST_Search(tree, target->data))
        return;

    if((tree->elemCnt != 0) && (tree->treeEntry != NULL))
    {
        Node **pp = & tree->treeEntry;

        while(*pp != NULL)
        {
            if((*pp)->data > target->data)
                pp = & (*pp)->left;

            else
                pp = & (*pp)->right;
        }

        *pp = target;
    }

    else
    {
        tree->treeEntry = target;
    }

    tree->elemCnt++;
}
Node *BST_Get_Max(Node *root)
{
    Node *p = root;

    while(p->right != NULL)
        p = p->right;

    return p;
}

void BST_Delete(BST_Tree *tree, Node *target)
{
    if(target == NULL)
        return;

    Node *parent = BST_Get_Parent(tree, target);

    if(parent == NULL)
    {
        // 무작위 위치에서 삭제할 때
        // 노드가 1개뿐일 때(마지막으로) Root노드를 삭제
        // 하는 경우가 더 적으므로, 그렇지 않을 때를        
		// 조건식으로 잡아 먼저 위치시킴
        if(tree->elemCnt != 1)
        {
            // 현재 Root 노드 위에 매달아놓을 가상의 Root
            Node *vRoot = BST_Create_Node(tree->treeEntry->data + 1);


/*
	TODO:
*/
            // 가상 Root의 left에 실제 Root를 연결하고
            vRoot->right = NULL;
            vRoot->left = tree->treeEntry;
            tree->treeEntry = vRoot;

/*
	TODO:
*/
            // 실제 Root(가상Root의 left)를 삭제하면 
            // Root노드삭제 로직이 아닌 
            // 자식이 1개인 노드삭제 로직이 돌아감
            BST_Delete(tree, vRoot->left);

/*
	TODO:
*/
            // 삭제로직이 수행되면 vRoot->left에는 
            // 왼쪽서브트리의 최대값으로 대체돼 있음, 
            // 이것이 실제 트리상의 새로운 Root
            tree->treeEntry = vRoot->left;

            // Root 삭제용으로 만들었던 가상의 Root 삭제
            free(vRoot);
        }

        // 트리에 루트노드 1개만 남아있을 때 
        // 이것을 삭제하는 경우
        else
        {
            free(target);
            tree->treeEntry = NULL;
            tree->elemCnt = 0;
        }

        return;
    }
    // 양쪽 자식이 모두 없는 경우 (단말 노드인 경우)
    if(target->left == NULL  &&  target->right == NULL)
    {
        if(parent->left == target)
            parent->left = NULL;

        else
            parent->right = NULL;

        free(target);
    }

    // 자식노드가 오른쪽에만 있는 경우
    else if(target->left == NULL  &&  target->right)
    {
        if(parent->left == target)
            parent->left = target->right;

        else
            parent->right = target->right;

        free(target);
    }

    // 자식노드가 왼쪽에만 있는 경우
    else if(target->left  &&  target->right == NULL)
    {
        if(parent->left == target)
            parent->left = target->left;
        else
            parent->right = target->left;

        free(target);
    }

    // 삭제할 노드의 자식노드가 양쪽 모두 있는 경우, 
    // 왼쪽트리에서의 최대값 또는 오른쪽트리에서의
    // 최소값으로 삭제할 노드를 대체한다
    else
    {
        Node *leftMax = BST_Get_Max(target->left);
        Node *leftMaxParent = BST_Get_Parent(tree, leftMax);

        // 왼쪽 서브트리의 최대값 노드 데이터를 삭제하려는
        // 타겟 자리로 복사한 후, 링크/해제 작업만 한다
        target->data = leftMax->data;

        // 왼쪽 서브트리의 최대값노드(오른쪽으로만 이동시켜 
        // 찾은 노드)는 왼쪽 자식이 있을 수도 있다
        if(leftMax->left)
        {
            // 타겟과 왼쪽 최대값 노드(leftMax)는 
            // 인접해있을 수도 있다
            if(leftMaxParent == target)
                leftMaxParent->left = leftMax->left;
            else
                leftMaxParent->right = leftMax->left;
        }
        else
        {
            if(leftMaxParent == target)
                leftMaxParent->left = NULL;

            else
                leftMaxParent->right = NULL;
        }

        free(leftMax);
    }

    tree->elemCnt--;
}

void BST_DestroyTree(BST_Tree *tree)
{
    while(tree->elemCnt)
        BST_Delete(tree, tree->treeEntry);

    if( tree->treeEntry != NULL
       || tree->elemCnt != 0 )
    {
        printf("error \n");
        return;
    }
}

void __print_preorder(Node *p)
{
    if(p == NULL)
        return;

    printf("%3d  ", p->data);
    __print_preorder(p->left);
    __print_preorder(p->right);
}

void __tree_test(BST_Tree *tree, int range, int rep)
{
    srand((unsigned int)time(NULL));

    int i, ranNum = 0, ranIdx = 0;
    int *arr = (int *)malloc(sizeof(int) * range);
    memset(arr, 0, sizeof(int) * range);

    printf("----- [ 1~%d의 난수 삽입 %d회 테스트... ]\n", range, rep);
    for(i=0; i<rep; i++)
    {
        ranNum = 1 + rand() % range;
        ranIdx = rand() % range;
        if(arr[ranIdx] != 0)
            continue;

        arr[ranIdx] = ranNum;
        BST_Insert(tree, BST_Create_Node(ranNum));
        __print_preorder(tree->treeEntry);
        printf("\n");
    }
    printf("\n----- [ 노드 1개씩 삭제... ]\n");

    while(tree->elemCnt != 0)
    {
        ranIdx = rand() % range;
        if(arr[ranIdx] == 0)
            continue;

        Node *del = BST_Search(tree, arr[ranIdx]);
        if(del == NULL)
            continue;

        BST_Delete(tree, del);
        __print_preorder(tree->treeEntry);
        printf("\n");
    }

    free(arr);
}

 

//RB-tree
#include <stdio.h>
#include <stdlib.h>

typedef struct _node
{
	struct _node *left;
	struct _node *right;
	int red;          /* 노드의 색깔, 빨강이면 1, 검정이면 0 */
	int key;
}node;

void init_tree (node **p)
{	/* 나무의 시작점을 생성 */
	*p = (node*)malloc(sizeof(node));
	(*p)->left = NULL;
	(*p)->right = NULL;
	(*p)->red = 0;
}

node *rbti_search(int key, node *base, size_t *num)
{
    node *s;
    s = base->left;

    while (key != s->key && s != NULL)
    {
        if (key < s->key)
            s = s->left;
        else
            s = s->right;
    }
    return s;
}

node *rotate(int key, node *pivot, node *base)
{   
    /* 회전을 수행 */
    node *child, *gchild; /* 축의 아들과 손자 */
    
	if (key < pivot->key || pivot == base) /* 아들의 방향 결정 */
		child = pivot->left;
    else
		child = pivot->right;
	
    if (key < child->key) /* 손자의 방향 결정 */
    {
		gchild = child->left; /* L회전 */
		child->left = gchild->right;
		gchild->right = child;
    }
    else
    {
		gchild = child->right; /* R회전 */
		child->right = gchild->left;
		gchild->left = child;
    }

    if (key < pivot->key || pivot == base) /* 축에 손자를 연결시킴 */
		pivot->left = gchild;
    else
		pivot->right = gchild;
    return gchild;
}

node *rbti_insert(int key, node *base, size_t *num)
{
    node *t, *parent, *gparent, *ggparent; /* 자신, 부, 조부, 증조부를 저장 */
    ggparent = gparent = parent = base;
    t = base->left;
    while (t != NULL) 
    {
		if (key == t->key) 
			return NULL ; /* 이미 같은 키가 존재함 */

		if (t->left && t->right && t->left->red && t->right->red)
		{   /* 경로의 중간에 4-노드가 있으면 분할, 즉 색상 변환 */
			t->red = 1;        /* 색상 변환 */
			t->left->red = t->right->red = 0;
			if (parent->red)  /* 부모가 빨강이면 회전이 필요 */
    	    {
				gparent->red = 1;
				if (key < gparent->key != key < parent->key)
					parent = rotate(key, gparent, base);  /* LR이나 RL인 경우 R회전과 L회전을 먼저 함 */
				t = rotate(key, ggparent, base); /* LL과 RR회전 */
				t->red = 0;
			}

	    base->left->red = 0; /* 뿌리 노드는 검정 노드이다. */
	}

  	ggparent = gparent;
	gparent = parent;
	parent = t;

	if (key < t->key)		/* 삽입될 곳을 찾아 들어감 */
	    t = t->left;
	else
	    t = t->right;
    }

    if ((t = (node*)malloc(sizeof(node))) == NULL) /* 노드 생성 */
		return NULL;

    t->key = key;
    t->left = NULL;
    t->right = NULL;

    if (key < parent->key || parent == base) /* 삽입 */
		parent->left = t;
    else
		parent->right = t;

    (*num)++;		 /* 자료수 증가 */
    t->red = 1;        /* 새로 삽입되는 노드는 빨간 노드이다 */

    if (parent->red)  /* 부모도 빨강이면 회전이 필요 */
    {
		gparent->red = 1;
		if (key < gparent->key != key < parent->key) /* LR 회전이나 RL 회전 */
			parent = rotate(key, gparent, base);  

		t = rotate(key, ggparent, base); /* LL회전이나 RR회전 */
		t->red = 0;
    }

    base->left->red = 0;
    return t;
}

node *find_seed(int key, node *base)
{
    node *del, *seed_parent, *parent;

    seed_parent = NULL;
    parent = base;
    del = base->left;

    while (del != NULL)
    {
		if (key < del->key)
		{
			if (del->red || (del->right && del->right->red))
				seed_parent = parent; /* 빨강 노드나 오른쪽 자식이 빨간 노드 찾기 */
			parent = del;	    del = del->left;
		}
		else
        {
			if (del->red || (del->left && del->left->red))
				seed_parent = parent; /* 빨강 노드나 왼쪽 자식이 빨간 노드 찾기 */
			
			parent = del;	    del = del->right;
        }
    }
	
    return seed_parent;
}

void make_leaf_red(int key, node *base)
{
    node *seed_parent, *seed, *seed_child;

    seed_parent = find_seed(key, base); /* 빨강 씨앗을 찾음 */

    if (seed_parent == NULL) /* 빨강 씨앗이 없으면 */
    {
		seed_parent = base;
		seed = seed_parent->left;
		seed->red = 1; /* 뿌리노드를 빨강으로 하고 씨앗으로 삼는다 */
    }
    else
    {
		if (key < seed_parent->key || seed_parent == base)
			seed = seed_parent->left;
		else 
			seed = seed_parent->right;
    }
    
	if (!seed->red) /* 씨앗이 빨강이 아니면 그 자식이 빨강이다 */
    {/* 그래서 회전을 하여 빨강을 끌어 올린다 */
		if (key < seed->key)
			seed_child = seed->right;
		else
			seed_child = seed->left;

		seed->red = 1;
		seed_child->red = 0;
		seed_parent = rotate(seed_child->key, seed_parent, base); /* 회전 */
    }

    while (seed->left && seed->right)
    {/* 외부 노드가 아닐 동안 */
		seed->red = 0; /* 역색상 변환 */
		seed->right->red = seed->left->red = 1;
		if (key < seed->key)
		{
			if ((seed->right->left || seed->right->right) && (seed->right->left->red || seed->right->right->red))
			{   /* 회전이 필요하면 회전을 한다 */
				if (seed->right->left && seed->right->left->red)
				{/* RL회전이 필요 */
					seed->right->red = 0;
					rotate(seed->right->left->key, seed, base);
				}
				else
					seed->right->right->red = 0;

				rotate(seed->right->key, seed_parent, base);
			}
			seed_parent = seed;
			seed = seed->left;
		}
		else
		{
			if ((seed->left->left || seed->left->right) && (seed->left->left->red || seed->left->right->red))
			{/* 회전이 필요하면 회전을 한다 */
				if (seed->left->right && seed->left->right->red)
				{/* LR회전이 필요 */
					seed->left->red = 0;
					rotate(seed->left->right->key, seed, base);
				}
				else
					seed->left->left->red = 0;

				rotate(seed->left->key, seed_parent, base);
			}
			seed_parent = seed;	    seed = seed->right;
		}
	}
}

node *rbti_delete(int key, node *base, size_t *num)
{
    node *parent, *del, *center, *pcenter, *son;
    int temp;
    parent = base;
    del = base->left;

    while (key != del->key && del != NULL)
    {
		/* 삭제할 키를 찾음 */
        parent = del;
        if (key < del->key)
            del = del->left;
        else
            del = del->right;
    }
    if (del == NULL) 
		return NULL; /* 삭제할 키를 찾지 못함 */

    if (del->right && del->left)
    { 

		/* 자식이 두 개이면, 즉 내부 노드이면 */
		pcenter = del; /* 삭제할 노드를 대체할 노드를 찾음 */
		center = del->right;

		while (center->left != NULL)
		{
			pcenter = center;
			center = center->left; /* center는 대체할 키임 */
		}
		
		del->key = center->key; /* 삭제할 키를 대체할 키로 바꿈 */
		del = center; /* 이제 center를 삭제하도록 조정 */
		parent = pcenter;
		key = del->key;
    }

    if (del->left || del->right)
    { 

		/* 자식이 하나인 경우, 자식이 하나면 반드시 빨강 자식이다 */
		if (del->left)
			son = del->left;
		else
			son = del->right;
		
		son->red = 0;
    }
    else if (del->left == NULL && del->right == NULL)
    {  

		/* 자식이 없는 경우, 빨강이면 그냥 삭제, 검정이면 2-노드이므로 3-노드나 4-노드로 변환 후에 삭제*/
		if (!del->red) 
			make_leaf_red(del->key, base);



		son = NULL;
    }
    
	base->left->red = 0;
    
	if (key < parent->key || parent == base)
		parent->left = son;
    else
		parent->right = son;

	free(del);

	(*num)--;

    return parent;
}

int main()
{

	node *myRBnode; 
	node *t;
	
	size_t node_count = 0; 

	int i; 
	
	init_tree(&myRBnode);


#define  TEST_NODE_MAX 9
	
	for( i=1; i<= TEST_NODE_MAX;i++)
	{

/*
	TODO:	insert each node with key = i
*/

		t = rbti_insert( i, myRBnode, &node_count);

		if ( t == NULL )
		{
			puts("fail to insert");
			break;
		}

	}



	printf("\nnode count after insert is : %d \n",  node_count );
	
	t = rbti_delete(3, myRBnode, &node_count);
	if (t== NULL)
		puts("fail to delelte node");

	printf("\nnode count after delete is : %d \n",  node_count );

	return 0;
	
}

 

• 해쉬 검색

그림으로 개념을 이해하는 알고리즘 책에서 읽었기 때문에 개념적으로는 이해가 되었다.

하지만 C로 구현한 코드는 좀 더 들여다봐야겠다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define Uart_Printf  printf

// 해쉬를 구성하는 키 값
typedef int KeyType;
typedef int ValueType;

typedef struct _hashNode
{
    KeyType key;
    ValueType value;
} Node;

typedef struct _hashTable
{
    Node *table;
    int tableSize;
} HashTable;

// < 나눗셈법에 의한 해시 함수 >
// 테이블의 크기로 간단히 나누기 때문에
// 테이블의 크기는 소수, 그리고
// 2의 제곱수인 4, 8, 16, 32, 64, 128, ...과
// 먼 크기로 하는 것이 효율적

// Ex) tableSize = 193
// 2의 7제곱 = 128과 2의 8제곱 256 사이의 소수 --> 193
int __hash_modulus(KeyType key, int tableSize)
{


/*
	TODO:
*/
    // input 인덱스로부터 간단히 나눗셈을 통해
    // Output 인덱스를 구한다
    return (int)key % tableSize;
	
}

// 기준점으로부터의 최대값노드 리턴
// < 자리수 접기(Digits folding)에 의한 해시 함수 >
int __hash_digitFolding(char *key, int tableSize)
{
    int i, len = strlen(key);
    int value = 0;

    // 이 역시도 충돌(Collision)을 피할 순 없다
    for(i=0; i<len; i++)
        value += key[i];

    return value % tableSize;
}


HashTable *Create_HashTable(int tableSize)
{
    HashTable *pNew = (HashTable *)malloc(sizeof(HashTable));
    pNew->table = (Node *)malloc(sizeof(Node) * tableSize);
    pNew->tableSize = tableSize;

    return pNew;
}

void Set_HashTable(HashTable *pTable, KeyType key, ValueType value)
{
    int idx ;
	
	idx = __hash_modulus(key, pTable->tableSize);


    pTable->table[idx].key = key;
    pTable->table[idx].value = value;
}

ValueType Get_HashTable(HashTable *pTable, KeyType key)
{

	int idx ;

/*
	TODO: get index by hash function call.
*/	
    idx = __hash_modulus(key, pTable->tableSize);

    return pTable->table[idx].value;
}

void main(void)
{
    HashTable *p = Create_HashTable(193);

    Set_HashTable(p, 418, 32114);
    Set_HashTable(p, 9, 514);
    Set_HashTable(p, 27, 8917);
    Set_HashTable(p, 1031, 286);

    Uart_Printf("%d \n", Get_HashTable(p, 418));
    Uart_Printf("%d \n", Get_HashTable(p, 9));
    Uart_Printf("%d \n", Get_HashTable(p, 27));
    Uart_Printf("%d \n\n", Get_HashTable(p, 1031));

    #if 1
    // 단순히 테이블의 크기로 Modulus연산하는 해시함수는
    // 다음과 같이 충돌(Collision)문제가 생긴다
    Set_HashTable(p, 193, 777);
    Set_HashTable(p, 193 * 2, 888);
    Set_HashTable(p, 193 * 3, 999);

    Uart_Printf("%d \n", Get_HashTable(p, 193));
    Uart_Printf("%d \n", Get_HashTable(p, 193 * 2));
    Uart_Printf("%d \n", Get_HashTable(p, 193 * 3));
    #endif
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define Uart_Printf  printf

// 해쉬를 구성하는 키 값
typedef int  KeyType; typedef int  ValueType;
typedef struct _hashNode
{
    KeyType key;
    ValueType value;
} Node;

typedef struct _hashTable
{
    Node *table;
    int tableSize;
} HashTable;

HashTable *CreateHashTable(int size)
{
    HashTable *p = (HashTable *)malloc(sizeof(HashTable));

    p->table = (Node *)malloc(sizeof(Node) * size);
    p->tableSize = size;

    memset(p->table, 0, sizeof(Node) * size);

    return p;
}
int __hash_modulus(KeyType key, int tableSize)
{
    return (int)key % tableSize;
}


#if 1
// 선형 탐사 (Linear probing)
void Set_HashTable_LinProbe(HashTable *p, KeyType key, ValueType value)
{
    int idx = __hash_modulus(key, p->tableSize);

    Node *pIter = NULL;    pIter = p->table + idx;

    while(pIter != (p->table + p->tableSize))
    {
        if(pIter->key == 0)
        {
            pIter->key = key;
            pIter->value = value;
            return;
        }
        pIter++;
    }

    pIter = p->table + 0; //  & p->table[0]

    while(pIter != (p->table + idx))
    {
        if(pIter->key == 0)
        {
            pIter->key = key;
            pIter->value = value;
            return;
        }
        pIter++;
    }

    Uart_Printf("데이터 들어갈 공간 없음 \n");
}

ValueType Get_HashTable_LinProb(HashTable *p, KeyType key)
{
    int idx = __hash_modulus(key, p->tableSize);

    Node *pFwd = p->table + idx;		// forward  pointer
    Node *pBwd = p->table + idx - 1;	// backward pointer

    while(1)
    {
        if(pFwd == (p->table + p->tableSize))	// forward pointer leached at last ?  no room for it !  Fail!
            break;

        if(pFwd->key == key)	// found at forward ?
            return pFwd->value;

        if(pBwd == (p->table - 1))			// backward pointer leached at first ?  no room for it !  Fail!
            break;

        if(pBwd->key == key)	// found at backward ?
            return pBwd->value;

/*
	TODO:
*/

// move forward pointer forward!
        pFwd++;	

/*
	TODO:
*/

// move backward pointer backward 
        pBwd--;	

    }

    return -1;
}
#endif
#if 0
// 제곱 탐사 (Quadratic probing)
void Set_HashTable_QuadProb(HashTable *p, KeyType key, ValueType value);

ValueType Get_HashTable_QuadProb(HashTable *p, KeyType key);
#endif


int IsOverlapped(int data, int *p, int size)
{
    int i;

    for(i=0; i<size; i++)
    {
        if(data == p[i])
            return 1;
    }

    return 0;
}


void main(void)
{
    int NUM = 193;int i;int ranData = 0;
    int testData = 1;int keyList[NUM];
    HashTable *p = CreateHashTable(NUM);
    srand( (unsigned)time(NULL) );
    for(i=0; i<NUM; i++)
    {
        while(1)
        {
            ranData = 1 + rand() % 10000;
            if( IsOverlapped(ranData, keyList, NUM) )
                continue;
            keyList[i] = ranData;
            break;
        }
    }
    for(i=0; i<NUM; i++)
    {
        Set_HashTable_LinProbe(p, keyList[i], testData);
        testData++;
    }

    for(i=0; i<NUM; i++)
    {
        Uart_Printf("%3d ", (int)Get_HashTable_LinProb(p, keyList[i]));
    }
}

 

 

---

* 개인적인 학습 목적으로 작성한 글이기에 내용에 잘못된 정보가 있을 수 있습니다.