arithmetic.c

嵌入式的小程序

            a1->bf = 0;
        else {
            balance = 0;
            if (d == 1) {
                if (b->bf == 1) {
                    b = a1->left_pointer;
                    a1->left_pointer = b->right_pointer;
                    a1->bf = 0;
                    b->right_pointer = a1;
                    b->bf = 0;
                } else if (b->bf == -1) {
                    b = a1->left_pointer;
                    c = b->right_pointer;
                    a1->left_pointer = c->right_pointer;
                    b->right_pointer = c->left_pointer;
                    c->right_pointer = a1;
                    c->left_pointer = b;
                    if (c->bf == 1) {
                        a1->bf = -1;
                        b->bf = 0;
                    } else if (c->bf == -1) {
                        a1->bf = 0;
                        b->bf = 1;
                    } else if (c->bf == 0) {
                        a1->bf = 0;
                        b->bf = 0;
                    }
                    c->bf = 0;
                    b = c;
                }
            } else {
                if (b->bf == -1) {
                    b = a1->right_pointer;
                    a1->right_pointer = b->left_pointer;
                    a1->bf = 0;
                    b->left_pointer = a1;
                    b->bf = 0;
                }
                if (b->bf == 1) {
                    b = a1->right_pointer;
                    c = b->left_pointer;
                    a1->right_pointer = c->left_pointer;
                    b->left_pointer = c->right_pointer;
                    c->left_pointer = a1;
                    c->right_pointer = b;
                    if (c->bf == 1) {
                        a1->bf = 0;
                        b->bf = -1;
                    } else if (c->bf == -1) {
                        a1->bf = 1;
                        b->bf = 0;
                    } else if (c->bf == 0) {
                        a1->bf = 0;
                        b->bf = 0;
                    }
                    c->bf = 0;
                    b = c;
                }
            }
        }
        if (balance == 0) {
            if (f1 == NULL)
                prTree->Root = b;
            else {
                if (f1->left_pointer == a1)
                    f1->left_pointer = b;
                if (f1->right_pointer == a1)
                    f1->right_pointer = b;
            }
        }
    }
    return;
}

/*
 * 参数   : prTree:AVL树指针,ptr:指向AVL树根结点的指针,Key:所要查找的关键字
 * 返回值 : 
 * 描述   : 从一棵AVL树中查询数据
 */
void AvlSelect(AVL * prTree, TREE * ptr, unsigned char *Key)
{
    if (prTree->Root == NULL) {
        prTree->ErrorCode = 1403;
        strcpy(prTree->ErrorInfo, "Tree is Empty!");
        return;
    }
    prTree->ErrorCode = 1403;
    strcpy(prTree->ErrorInfo, "Data Not Found!");
    Select(prTree, ptr, Key);
}

void Select(AVL * prTree, TREE * ptr, unsigned char *Key)
{
    if (ptr == NULL)
        return;
    if (strcmp(ptr->Key, Key) > 0) {
        if (ptr->left_pointer != NULL)
            Select(prTree, ptr->left_pointer, Key);
        else
            return;
    } else if (strcmp(ptr->Key, Key) == 0) {
        prTree->Result = ptr;
        prTree->ErrorCode = 0;
        return;
    } else {
        if (ptr->right_pointer != NULL)
            Select(prTree, ptr->right_pointer, Key);
        else
            return;
    }
}

/*
 * 参数   : prTree:AVL树指针,OldKey:要变更的域关键字段，
 *	    NewKey:新的关键字段，NewFd:新域
 * 返回值 : 
 * 描述   : 变更AVL树中一个结点的关键域
 */
void AvlUpdate(AVL * prTree, unsigned char *OldKey, unsigned char *NewKey,
               void *NewFd)
{
    prTree->ErrorCode = 0;
    not_old(prTree, NewKey, prTree->Root);
    if (prTree->ErrorCode != 0)
        return;
    if (AvlDelete(prTree, OldKey) != 1)
        return;
    AvlInsert(prTree, NewFd, NewKey);
    return;
}

/*
 * 参数   : prTree:AVL树指针,OldKey:所要删除的结点的关键字
 * 返回值 : 
 * 描述   : 删除一棵AVL树中一个结点
 */
int AvlDelete(AVL * prTree, unsigned char *OldKey)
{
    TREE *father_ptr, *ptr, *ffptr;

    prTree->ErrorCode = 0;
    if (prTree->Root == NULL) {
        prTree->ErrorCode = 2;
        strcpy(prTree->ErrorInfo, "tree is empty");
        return 0;
    }
    if (strcmp(OldKey, prTree->Root->Key) == 0) {
        delroot(prTree);
        return (1);
    } else if (strcmp(OldKey, prTree->Root->Key) < 0)
        ptr = prTree->Root->left_pointer;
    else
        ptr = prTree->Root->right_pointer;
    father_ptr = prTree->Root;
    ffptr = NULL;
    while (ptr != NULL) {
        if (strcmp(OldKey, ptr->Key) == 0) {
            delnode(prTree, ptr, father_ptr, ffptr);
            return (1);
        } else if (strcmp(OldKey, ptr->Key) < 0) {
            ffptr = father_ptr;
            father_ptr = ptr;
            ptr = ptr->left_pointer;
        } else {
            ffptr = father_ptr;
            father_ptr = ptr;
            ptr = ptr->right_pointer;
        }
    }

    prTree->ErrorCode = 3;
    sprintf(prTree->ErrorInfo, "OldKey:%s can't find", OldKey);
    return (0);
}

/*
 * 参数   : prTree:AVL树指针,ptr:指向AVL树根结点的指针
 *	    Func:遍历至每一结点时要调用的回调函数名,ptr1:指向遍历结点的指针
 * 返回值 : 
 * 描述   : 以升序遍历一棵AVL树
 */
void AvlExport(AVL * prTree, TREE * ptr, void (*Func) (TREE * ptr1))
{
    prTree->ErrorCode = 0;
    strcpy(prTree->ErrorInfo, "");
    Export(prTree, ptr, Func);
}

void Export(AVL * prTree, TREE * ptr, void (*Func) (TREE * ptr1))
{
    if (prTree->Root == NULL)
        return;
    if (ptr->left_pointer != NULL)
        AvlExport(prTree, ptr->left_pointer, Func);
    Func(ptr);
    if (ptr->right_pointer != NULL)
        AvlExport(prTree, ptr->right_pointer, Func);
    return;
}

void delroot(AVL * prTree)
{
    TREE *fptr, *ptr, *ffptr;

    fptr = prTree->Root;
    ffptr = NULL;
    ptr = prTree->Root->left_pointer;

    free(prTree->Root->Field);
    if (prTree->Root->left_pointer == NULL) {
        if (prTree->Root->right_pointer != NULL) {
            prTree->Root = prTree->Root->right_pointer;
            prTree->Root->bf = 0;
            return;
        }
        free(prTree->Root);
        prTree->Root = NULL;
        return;
    } else {
        while (ptr->right_pointer != NULL) {
            ffptr = fptr;
            fptr = ptr;
            ptr = ptr->right_pointer;

        }
        if (fptr == prTree->Root) {
            fptr->left_pointer = ptr->left_pointer;
            fptr->bf = fptr->bf - 1;
        } else {
            fptr->right_pointer = ptr->left_pointer;
            fptr->bf = fptr->bf + 1;
        }
        prTree->Root->Field = ptr->Field;
        (prTree->Root->Key) = (ptr->Key);
        free(ptr);
        modi(prTree, fptr, ffptr);
        return;
    }
}

void not_old(AVL * prTree, unsigned char *Key, TREE * ptr)
{
    if (ptr->left_pointer != NULL)
        not_old(prTree, Key, ptr->left_pointer);
    if (strcmp(ptr->Key, Key) == 0) {
        prTree->ErrorCode = 1;
        strcpy(prTree->ErrorInfo, "new data is Already in the tree");
        return;
    }
    if (ptr->right_pointer != NULL)
        not_old(prTree, Key, ptr->right_pointer);
    return;
}

void delnode(AVL * prTree, TREE * ptr, TREE * father, TREE * ffptr)
{
    TREE *fpr, *pr, *ffpr;

    fpr = father;
    pr = ptr;
    ffpr = ffptr;
    free(ptr->Field);

    if (pr->left_pointer == NULL) {
        if (fpr->left_pointer == pr) {
            fpr->left_pointer = pr->right_pointer;
            fpr->bf = fpr->bf - 1;
        } else {
            fpr->right_pointer = pr->right_pointer;
            fpr->bf = fpr->bf + 1;
        }
        free(ptr);
        modi(prTree, fpr, ffpr);
        return;
    } else {
        ffpr = fpr;
        fpr = ptr;
        pr = ptr->left_pointer;
        while (pr->right_pointer != NULL) {
            ffpr = fpr;
            fpr = pr;
            pr = pr->right_pointer;
        }
        if (fpr->right_pointer == pr) {
            fpr->right_pointer = pr->left_pointer;
            fpr->bf = fpr->bf + 1;
        } else {
            fpr->left_pointer = pr->left_pointer;
            fpr->bf = fpr->bf - 1;
        }
        (ptr->Key) = (pr->Key);
        ptr->Field = pr->Field;
        modi(prTree, fpr, ffpr);
        free(pr);
        return;
    }
}

void InitNode(TREE * ptr, unsigned char *Key, void *Fd)
{
    (ptr->Key) = Key;
    ptr->Field = Fd;
    ptr->bf = 0;
    ptr->left_pointer = NULL;
    ptr->right_pointer = NULL;
}


void modi(AVL * prTree, TREE * fpr, TREE * ffpr)
{
    switch (fpr->bf) {
    case 0:
        avl(prTree, fpr, ffpr);
        break;
    case +2:
        if (fpr->left_pointer->bf == 1) {
            avl(prTree, ll(prTree, fpr, ffpr), ffpr);
            break;
        } else if (fpr->left_pointer->bf == -1) {
            avl(prTree, lr(prTree, fpr, ffpr), ffpr);
            break;
        } else if (fpr->left_pointer->bf == 0) {
            l0(prTree, fpr, ffpr);
            break;
        } else {
            prTree->ErrorCode = 9;
            strcpy(prTree->ErrorInfo, "error9");
            break;
        }
    case -2:
        if (fpr->right_pointer->bf == -1) {
            avl(prTree, rr(prTree, fpr, ffpr), ffpr);
            break;
        } else if (fpr->right_pointer->bf == 1) {
            avl(prTree, rl(prTree, fpr, ffpr), ffpr);
            break;
        } else if (fpr->right_pointer->bf == 0) {
            r0(prTree, fpr, ffpr);
            break;
        } else {
            prTree->ErrorCode = 10;
            strcpy(prTree->ErrorInfo, "error10");
            break;
        }
    default:
        break;
    }
    return;
}


void avl(AVL * prTree, TREE * ptr, TREE * fptr)
{
    TREE *pointer, *fpointer;
    pointer = prTree->Root;
    fpointer = NULL;
    if (fptr == NULL)
        return;
    while (pointer != fptr) {
        if (strcmp(fptr->Key, pointer->Key) < 0) {
            fpointer = pointer;
            pointer = pointer->left_pointer;
        } else {
            fpointer = pointer;
            pointer = pointer->right_pointer;
        }
    }
    if (ptr == fptr->left_pointer)
        fptr->bf = fptr->bf - 1;
    else if (ptr == fptr->right_pointer)
        fptr->bf = fptr->bf + 1;
    else {
        prTree->ErrorCode = 11;
        strcpy(prTree->ErrorInfo, "error11");
    }
    modi(prTree, pointer, fpointer);
    return;
}

TREE *ll(AVL * prTree, TREE * a, TREE * f)
{
    TREE *b;
    b = a->left_pointer;
    a->left_pointer = b->right_pointer;
    a->bf = 0;
    b->right_pointer = a;
    b->bf = 0;
    if (f == NULL)
        prTree->Root = b;
    else if (f->left_pointer == a)
        f->left_pointer = b;
    else if (f->right_pointer == a)
        f->right_pointer = b;
    else
        printf("\n error 4");
    return (b);
}

TREE *lr(AVL * prTree, TREE * a, TREE * f)
{
    TREE *b, *c;
    b = a->left_pointer;
    c = b->right_pointer;
    a->left_pointer = c->right_pointer;
    b->right_pointer = c->left_pointer;
    c->right_pointer = a;
    c->left_pointer = b;
    if (c->bf == 1) {
        a->bf = -1;
        b->bf = 0;
    } else if (c->bf == -1) {
        a->bf = 0;
        b->bf = 1;
    } else if (c->bf == 0) {
        a->bf = 0;
        b->bf = 0;
    }
    c->bf = 0;
    b = c;
    if (f == NULL)
        prTree->Root = b;
    else if (f->left_pointer == a)
        f->left_pointer = b;
    else if (f->right_pointer == a)
        f->right_pointer = b;
    else
        printf("\n error 5");
    return (b);
}

TREE *rr(AVL * prTree, TREE * a, TREE * f)
{
    TREE *b;
    b = a->right_pointer;
    a->right_pointer = b->left_pointer;
    a->bf = 0;
    b->left_pointer = a;
    b->bf = 0;
    if (f == NULL)
        prTree->Root = b;
    else if (f->left_pointer == a)
        f->left_pointer = b;
    else if (f->right_pointer == a)
        f->right_pointer = b;
    else
        printf("\n error 6");
    return (b);
}

TREE *rl(AVL * prTree, TREE * a, TREE * f)
{
    TREE *b, *c;
    b = a->right_pointer;
    c = b->left_pointer;
    a->right_pointer = c->left_pointer;
    b->left_pointer = c->right_pointer;
    c->left_pointer = a;
    c->right_pointer = b;
    if (c->bf == 1) {
        a->bf = 0;
        b->bf = -1;
    } else if (c->bf == -1) {
        a->bf = 1;
        b->bf = 0;
    } else if (c->bf == 0) {
        a->bf = 0;
        b->bf = 0;
    }
    c->bf = 0;
    b = c;
    if (f == NULL)
        prTree->Root = b;
    else if (f->left_pointer == a)
        f->left_pointer = b;
    else if (f->right_pointer == a)
        f->right_pointer = b;
    else
        printf("\n error 7");
    return (b);
}

TREE *l0(AVL * prTree, TREE * a, TREE * f)
{
    TREE *b;
    b = a->left_pointer;
    a->left_pointer = b->right_pointer;
    a->bf = 1;
    b->right_pointer = a;
    b->bf = -1;
    if (f == NULL)
        prTree->Root = b;
    else if (f->left_pointer == a)
        f->left_pointer = b;
    else if (f->right_pointer == a)
        f->right_pointer = b;
    else
        printf("\n error 8");
    return (b);
}

TREE *r0(AVL * prTree, TREE * a, TREE * f)
{
    TREE *b;
    b = a->right_pointer;
    a->right_pointer = b->left_pointer;
    a->bf = -1;
    b->left_pointer = a;
    b->bf = 1;
    if (f == NULL)
        prTree->Root = b;
    else if (f->left_pointer == a)
        f->left_pointer = b;
    else if (f->right_pointer == a)
        f->right_pointer = b;
    else
        printf("\n error 9");
    return (b);
}