sahar_karimi
کاربر تازه وارد
- تاریخ عضویت
- 9 جولای 2006
- نوشتهها
- 10
- لایکها
- 0
error این برنامه چیه؟ فوری
کد:
/********************************************************
3 - B+ tree programming
********************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
#define TRUE 1
#define FALSE 0
#define MAX 30001
typedef struct Bplus {
int Snum;
char Sname[20];
} Bplus;
typedef struct Bplus_tree *Bplus_tree_ptr;
struct Bplus_tree{
Bplus data_l, data_r;
Bplus_tree_ptr left_child, middle_child, right_child;
int SET;
};
Bplus_tree_ptr tree_root, seq_root, que;
typedef struct linked_list{
Bplus_tree_ptr d;
struct linked_list *next;
} linked_list;
typedef linked_list *link;
typedef struct stack{
int cnt;
link top;
} stack;
stack stk; // global stack ¼±¾ð
/********************************************************
********************************************************/
void initialize(stack *stk);
void push(Bplus_tree_ptr d, stack *stk);
Bplus_tree_ptr pop(stack *stk);
void check_mem(char *p);
int tree_op(char *opt); // operation
void viewhelp(void); // help message
void print_error(void);
void pop_all(void);
Bplus_tree_ptr new_node(void); // node
Bplus_tree_ptr searchBplus(Bplus_tree_ptr t, Bplus x); // node
void insertBplus(Bplus_tree_ptr *t, Bplus y);
void new_root(Bplus_tree_ptr *t, Bplus y, Bplus_tree_ptr q, int set);
// root
int Scompare(Bplus x,Bplus_tree_ptr t);
Bplus_tree_ptr find_node(Bplus_tree_ptr t, Bplus x);
void put_in(Bplus_tree_ptr *p, Bplus y, Bplus_tree_ptr q);
void split(Bplus_tree_ptr p, Bplus *y, Bplus_tree_ptr *q, int set);
// node
void find_seq(Bplus_tree_ptr t);
/* Print Bpluss of 23tree by inorder */
void print(Bplus_tree_ptr t, int level, char child, FILE *outfp);
/********************************************************/
void main()
{
char *op;
int i;
tree_root = NULL;
op = (char *)calloc(80,sizeof(char));
check_mem(op);
initialize(&stk);
clrscr();
viewhelp();
do {
printf("\n>");
gets(op);
i = tree_op(op);
} while(i != -1 ) ; // operation
free(op);
}
void deleteBplus(Bplus_tree_ptr *t, Bplus y)
{
Bplus_tree_ptr p, r;
p = searchBplus(*t,y);
if(p) {
if(p->data_r.Snum !=MAX) {
if(y.Snum == p->data_r.Snum)
p->data_r.Snum = MAX;
else {
p->data_l = p->data_r;
p->data_r.Snum = MAX;}
} // end if
else {
if(p == tree_root){
tree_root = NULL;
free(p); } // end if
else{
r = pop(&stk); // parent node
if(p == r->right_child) {
r->data_r.Snum = MAX;
r->right_child = NULL;
free(p);
} // end if
else if(p == r->middle_child) {
if(r->data_r.Snum != MAX){
r->data_r.Snum = MAX;
r->middle_child = r->right_child;
r->right_child = NULL;
free(r->right_child);
} // end if
else {
if(r->left_child->data_r.Snum != MAX) {
r->data_l = r->left_child->data_l;
p->data_l = r->left_child->data_r;
r->left_child->data_r.Snum = MAX;
} // end if
else {
free(p);
Bplus x;
x = r->left_child->data_l;
free(r->left_child);
Bplus_tree_ptr s;
s = pop(&stk);
if(r == s->right_child) {
s->data_r.Snum = MAX;
s->right_child = NULL;
free(r);
insertBplus(&s, x);
} // end if
else if(r == s->middle_child) {
if(s->data_r.Snum != MAX) {
s->data_r.Snum = MAX;
s->middle_child = s->right_child;
s->right_child = NULL;
free(s->right_child); .
insertBplus(&s, x);
} // end if
else {
if(s != tree_root) {
Bplus_tree_ptr t;
t = pop(&stk);
insertBplus(&t, x);
} // end if
else {
tree_root = s->left_child;
free(s);
insertBplus(&tree_root, x);
} // end else
} // end else
} // end else if
else {
if(s->data_r.Snum != MAX) {
s->data_l = s->data_r;
s->left_child = s->middle_child;
s->middle_child = s->right_child;
s->right_child = NULL;
s->data_r.Snum = MAX;
free(s->right_child);
insertBplus(&s, x);
} // end if
else {
if(s != tree_root) {
Bplus_tree_ptr t;
t = pop(&stk);
insertBplus(&t, x);
} // end if
else {
tree_root = s->middle_child;
free(s);
insertBplus(&tree_root, x); } // end else
} // end else
} // end else
} // end else
} // end else
} // end else if
else{
if(r->data_r.Snum != MAX){
r->data_l = r->data_r;
r->data_r.Snum = MAX;
r->left_child = r->middle_child;
r->middle_child = r->right_child;
r->right_child = NULL;
free(r->right_child);
} // end if
else {
if(r->middle_child->data_r.Snum != MAX) {
p->data_l = r->data_l = r->middle_child->data_l;
r->middle_child->data_l = r->middle_child->data_r;
r->middle_child->data_r.Snum = MAX;
} // end if
else {
free(p);
Bplus x;
x = r->middle_child->data_l;
free(r->middle_child);
Bplus_tree_ptr s;
s = pop(&stk);
if(r == s->right_child) {
s->data_r.Snum = MAX;
insertBplus(&s, x);
} // end if
else if(r == s->middle_child) {
if(s->data_r.Snum != MAX) {
s->data_r.Snum = MAX;
s->middle_child = s->right_child;
s->right_child = NULL;
free(s->right_child);
insertBplus(&s, x);
} // end if
else {
if(s != tree_root) {
Bplus_tree_ptr t;
t = pop(&stk);
insertBplus(&t, x);
} // end if
else {
tree_root = s->left_child;
free(s);
insertBplus(&tree_root, x);
} // end else
} // end if
} // end else if
else {
if(s->data_r.Snum != MAX) {
s->data_l = s->data_r;
s->left_child = s->middle_child;
s->middle_child = s->right_child;
s->right_child = NULL;
s->data_r.Snum = MAX;
free(s->right_child);
insertBplus(&s, x);
} // end if
else {
if(s != tree_root) {
Bplus_tree_ptr t;
t = pop(&stk);
insertBplus(&t, x);
} // end if
else {
tree_root = s->middle_child;
free(s);
insertBplus(&tree_root, x);
} // end else
} // end else
} // end else
} // end else
} // end else
} // end else
}// end else
} // end else
} // end if
else {
printf("The \"%d\" is not in the tree\n",y);
return;
} // end else
}
void insertBplus(Bplus_tree_ptr *t, Bplus y)
{
Bplus_tree_ptr q, p;
if(!(*t)) .
new_root(t,y,NULL, TRUE);
else {
p = find_node(*t, y);
if(!p){
printf("The \"%d\" is currently in the tree\n",y);
return;
}
q=NULL;
for(;;) {
if(p->data_r.Snum == MAX) {
put_in(&p,y,q);
break;
}
else{
split(p,&y,&q, p->SET); .
if(p == *t){
new_root(t,y,q, FALSE);
break;
}
else
p = pop(&stk);
}
}
pop_all();
}
}
void swap(Bplus *x, Bplus *y) /* swap two Bplus */
{
Bplus temp;
temp = *x;
*x = *y;
*y= temp;
}
void split(Bplus_tree_ptr p, Bplus *y, Bplus_tree_ptr *q, int set)
{
Bplus_tree_ptr extra = *q;
/* sort p->data_l, p->data_r, and y */
(*q) = new_node();
if (y->Snum < p->data_l.Snum) { /* swap p->data_l and y */
swap(&(p->data_l),y);
(*q)->left_child = p->middle_child;
(*q)->middle_child = p->right_child;
p->middle_child = extra;
}
else {
if (y->Snum > p->data_r.Snum) {
swap(&(p->data_r),y); /* swap p->data_r and y */
(*q)->middle_child = extra;
(*q)->left_child = p->right_child;
}
else {
(*q)->middle_child = p->right_child;
(*q)->left_child = extra;
}
}
if(set == TRUE){
(*q)->SET = TRUE;
p->SET = TRUE;
}
else {
(*q)->SET = FALSE;
p->SET = FALSE; }
p->right_child = NULL;
(*q)->data_l = p->data_r; /* move max Snum */
if(set == TRUE)
p->data_r = *y;
else p->data_r.Snum = MAX;
}
void put_in(Bplus_tree_ptr *p, Bplus y, Bplus_tree_ptr q)
{ /* put y into p with right subtree q */
if((*p)->data_l.Snum < y.Snum) {
(*p)->data_r = y; /* put Bplus */
(*p)->right_child = q;
}
else {
(*p)->data_r = (*p)->data_l; /* move data */
(*p)->data_l = y;
(*p)->right_child = (*p)->middle_child; /* move pointer */
(*p)->middle_child = q;
}
}
Bplus_tree_ptr new_node(void)
{ /* make new node */
Bplus_tree_ptr p;
p = (Bplus_tree_ptr) calloc(1, sizeof(struct Bplus_tree));
check_mem((char *)p);
p->data_l.Snum=MAX;
p->data_r.Snum=MAX;
p->left_child=NULL;
p->right_child=NULL;
p->middle_child=NULL;
return p;
}
void new_root(Bplus_tree_ptr *t, Bplus y, Bplus_tree_ptr q, int set)
{ /* make new_root and put q into middle of new root */
Bplus_tree_ptr p;
p = new_node();
p->data_l = y;
p->left_child = *t;
p->middle_child = q;
p->SET = set;
*t = p;
}
Bplus_tree_ptr find_node(Bplus_tree_ptr t, Bplus x)
{ /* find node for insert */
while (t) {
push(t,&stk);
switch(Scompare(x,t)) {
case 1:
t = t->left_child;
break;
case 2:
t = t->middle_child;
break;
case 3:
t = t->right_child;
break;
case 4:
pop_all();
return NULL;
}
}
return pop(&stk);
}
Bplus_tree_ptr searchBplus(Bplus_tree_ptr t, Bplus x)
{ /* search node */
while (t) {
push(t,&stk);
switch(Scompare(x,t)) {
case 1:
t = t->left_child;
break;
case 2:
t = t->middle_child;
break;
case 3:
t = t->right_child;
break;
case 4:
return pop(&stk);
}
}
pop_all();
return NULL;
}
int Scompare(Bplus x,Bplus_tree_ptr t)
{ /* compare Snums */
if ((t->data_l.Snum > x.Snum)||((x.Snum == t->data_l.Snum)&&(t->SET != TRUE)))
return 1;
else
if (((t->data_l.Snum < x.Snum) && (x.Snum < t->data_r.Snum ||
t->data_r.Snum == MAX))||((x.Snum == t->data_r.Snum)&&(t->SET != TRUE)))
return 2;
else
if (x.Snum > t->data_r.Snum && t->data_r.Snum != MAX)
return 3;
else
return 4;
}
/* void find_seq(Bplus_tree_ptr t) /* Print Bpluss of 23tree by inorder */
{
if(t){
find_seq(t->left_child); /* print left child */
if(t->SET == TRUE) {
if(seq_root == NULL) {
seq_root = t;
que = t; }
else {
que->middle_child = t;
que = t; }
}
find_seq(t->middle_child); /* print middle child */
if(t->SET == TRUE){
que->middle_child = t;
que = t; }
find_seq(t->right_child); /* print right child */
if(t->SET == TRUE){
que->middle_child = t;
que = t; }
}
}
*/
void print(Bplus_tree_ptr t, int level, char child, FILE *outfp)
/* Print Bplus tree */
{
int i;
char *top,*bot;
if(t != NULL){
switch(child) {
case 'r': /* when right child */
top = "\xc0\xc4\xc4";
bot = " ";
break;
case 'm': /* when middle child */
top = "\xc3\xc4\xc4";
bot = "\xb3 ";
break;
case 'l': /* when left child */
top = " ";
bot = "\xda\xc4\xc4";
break;
case 'x': /* when root */
top = " ";
bot = " ";
}
print(t->left_child,level+1,'l', outfp); /* print left child */
fputc('\n',outfp);
for(i=0;i < level;i++) /* print space by level */
fprintf(outfp," ");
fprintf(outfp,"%s%4d %s",top,t->data_l.Snum, t->data_l.Sname);
print(t->middle_child,level+1,'m',outfp);
/* print middle child */
fputc('\n',outfp);
for(i=0;i < level;i++)
fprintf(outfp," "); /* print space by level */
if(t->data_r.Snum != MAX) {
fprintf(outfp,"%s%4d %s",bot,t->data_r.Snum, t->data_r.Sname);
print(t->right_child,level+1,'r', outfp);
/* print right child */
}
else
fprintf(outfp,"%s NO",bot);
}
}
void push(Bplus_tree_ptr d, stack *stk)
{
link p;
p = (link)calloc(1,sizeof(linked_list));
check_mem((char *)p);
p->d = d;
p->next = stk->top;
stk->top = p;
stk->cnt++;
}
Bplus_tree_ptr pop(stack *stk)
{
Bplus_tree_ptr d;
link p;
d = stk->top->d;
p = stk->top;
stk->top = stk->top->next;
stk->cnt--;
free((void *)p);
return d;
}
void initialize(stack *stk)
{
stk->cnt = 0;
stk->top = NULL;
}
void pop_all(void) {
while(stk.cnt != 0)
pop(&stk);
}
void check_mem(char *p)
{/* chekc memory */
if(p == NULL ) {
printf("\nOut of memory");
exit(1);
}
}
void print_error(void)
{
printf("Error : Wrong Matrix operation. For more help, use 'h' operation.");
}
int tree_op(char *opt)
{
char *a;
Bplus i;
strtok(opt," ");
switch (*opt) {
case 'h': /* help */
viewhelp();
break;
case 'a': /* insert */
while((a=strtok(NULL," ")) != NULL) {
i.Snum = atoi(a);
a = strtok(NULL," ");
int k =strlen(a);
for(int l = 0;l<=k;l++)
i.Sname[l] = a[l];
insertBplus(&tree_root,i);
}
break;
case 'd': /* delete */
while((a=strtok(NULL," ")) != NULL) {
i.Snum = atoi(a);
deleteBplus(&tree_root,i);
}
break;
case 'f': /* search */
if((a=strtok(NULL," ")) != NULL) {
i.Snum = atoi(a);
Bplus_tree_ptr t;
if((t=searchBplus(tree_root,i)) != NULL){
if((t->data_l.Snum) == i.Snum)
printf("%d %s is in the Bplus tree.",t->data_l.Snum, t->data_l.Sname);
else
printf("%d %s is in the Bplus tree.",t->data_r.Snum, t->data_r.Sname);}
else
printf("%d is NOT in the Bplus tree.",i);
pop_all();
}
else
print_error();
break;
case 'p': /* print by column */
FILE *outfp;
if((outfp = fopen("output.txt", "w")) == NULL) {
fprintf(stderr, "Can't make output file.\n");
exit(1);
}
print(tree_root,0,'x', outfp);
fclose(outfp);
break;
case 'q': /* quit */
return -1;
default :
print_error();
}
return 0;
}
void viewhelp(void) /* print help message */
{
printf("\n Bplus Tree Generater");
printf("\n a : Insert Bpluss ex) a 10 junghyun");
printf("\n d : Delete Bpluss ex) d 10");
printf("\n f : Search Bplus ex) f 10");
printf("\n p : Print Bpluss by column(output.txt) ex) p");
printf("\n h : View this help ex) h");
printf("\n q : Exit ex) q\n");
}