B-트리 #4. 변수 및 함수 선언

처음부터 끝까지 직접 구현해보고 싶었지만
교재의 부록으로 소스가 올려져 있었다.

그래서 열심히 베끼기!!!

물론!
이 소스가 완벽하지 않아서 개인적으로 손을 대긴했다.

그리고, 커다란 문제 발견!!
삭제 과정에서 무한 루프가 발생함.
이 부분은 이번 주말에 느긋하게 확인해보기로 하고
소스를 공개한다.

#define DEGREE            5        // m차 B-트리

#define MAX_ELEMENTS  1000    // 입력되는 key의 최대 수

#define DELETE_COUNT   10       // 삭제시 빼줄 원소 수

 

/* global variables */

FILE* pInputStream;      // input 파일의 핸들

FILE* pOutputStream;    // output 파일의 핸들

 

typedef struct NODE {    // B-트리의 노드 구조

    int bRoot;

    int nElm[DEGREE-1];    // 현재 노드가 가지고 있는 값

    struct NODE* pChild[DEGREE];  // 현재 노드의 자식 노드

} NODE;

typedef struct OVERFLOW_NODE {    // B-트리의 오버플로 노드 구조

    int bRoot;

    int nElm[DEGREE];

    NODE* pChild[DEGREE+1];

} OVERFLOW_NODE;

typedef struct STACK_NODE {    // stack의 노드 구조

    struct NODE* pCurr;

    NODE* pPrev;

} STACK_NODE;

 

/* function initialize */

NODE*                CreatNode();    // 노드 생성

OVERFLOW_NODE* CreatOverflowNode();    // 오버플로 노드 생성

STACK_NODE*       CreatStackNode();        // 스택 노드 생성

STACK_NODE*       PushIntoStack( STACK_NODE* pStackTop,
                                                    NODE* pNode );     // 스택에 푸쉬

STACK_NODE*       PopFromStack( STACK_NODE* pStackTop ); // 스택에서 팝

NODE*                PeepStackTop( STACK_NODE* pStackTop ); // 스택에서 팝을 peep

 

int   CheckElementExist( NODE* pNode, int key );  // 노드에 key가 있는지 검사

int   GetElementCount( NODE* pNode );             // 노드의 원소 수 반환

void PrintNodeElement( NODE* pNode );            // 노드의 key값 출력

 

/*    본문 시작    */

int main()

{

    int i, j;

    int nPos;        // 삽입 위치를 저장하기 위한 임시 변수

    int nKey;        // 삽입 및 삭제를 해줄 key 값

    int bFinished;    // 삽입, 삭제가 일어났는지의 flag

    int bFound;        // B-트리에서 해당 Key가 발견되었는지의 flag

    int bOverflow;    // 해당 node에서 오버플로가 발생했는지의 flag

    int nCount;        // 해당 node의 key수

    int nTemp, nTemp2, nTemp3;    // 임시 변수

 

    int nInput[MAX_ELEMENTS];    // 파일 접근을 줄이기 위해 배열에 저장

    int nElementCnt;

 

    NODE* pRoot;           // 루트 node

    NODE* pCurr;           // 현재 작업 수행중인 node

    NODE* pChild;          // 현재 node의 child node

    NODE* pNewNode;    // 생성할 새 node

    NODE* pInKey;         // In-Key의 pointer

    STACK_NODE*       pStackTop;   // stack의 top pointer

    OVERFLOW_NODE* pOverflow;    // 오버플로의 경우를 처리할 임시 node


                                  *** 중략 ***

변수가 참~~~~ 많죠잉!!
게다가 거 휘황찬란한 함수들 -ㅁ-
이 변수와 함수들을 활용하는 소스는 to be continue~~!!!