1

代码如下：

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

typedef struct node
{
    unsigned long int val;
    bool black;
    struct node* parent;
    struct node* lchild;
    struct node* rchild;
}mynode;

mynode* createNode(unsigned long int ival, mynode* father);
mynode* createLeaf(unsigned long int ival, mynode* father);
mynode* search (unsigned long int ival, mynode *root);
void insert ( unsigned long int ival, mynode *root);
mynode * getFather (mynode* child);
mynode * getUncle (mynode* child);
void doubleRotate (mynode* myptr);
void rotate(mynode* myptr);
void myRotate(mynode* myptr);
void changeRed(mynode* myptr);
void changeBlack(mynode* myptr);
void colorFlip( mynode* myptr);
void subtreeRepair (mynode* myptr);
bool isRoot(mynode* myptr);
void rootRepair (mynode* myptr);
void repair (mynode* myptr);
bool isRed (mynode* myptr);
void smallRotate(mynode* myptr);


int main()
{
    mynode myroot;
    mynode *myrootptr;
    mynode *myleafptr;
    FILE *fp;
    int ch;
    unsigned long long lines=0, i=0;
    unsigned long *myArr;
    unsigned long int ival;

   fp = fopen("integers.txt","r");
   if(fp == NULL)
   {
      printf("Error in opening file.");
      return(-1);
   }

    while(!feof(fp))
    {
    ch = fgetc(fp);
    if(ch == '\n')
    {
        lines++;
    }
    }
    lines++;
    printf("lines = %lu", lines);
    myArr = (unsigned long*)calloc(lines, sizeof(unsigned long));

    fseek(fp, 0, SEEK_SET);
    while(!feof(fp))
    {
          fscanf(fp, "%lu,", &myArr[i] ); // des ta pos k giati tou input.
          i++;
    }
    fclose(fp);

    myroot.val = myArr[0];
    myroot.parent = NULL;
    myroot.lchild = NULL;
    myroot.rchild = NULL;
    myroot.black = true;
    myrootptr = &myroot;
    myleafptr = createLeaf(myrootptr->val, myrootptr);
    myrootptr->lchild = myleafptr;
    myleafptr = createLeaf(myrootptr->val, myrootptr);
    myrootptr->rchild = myleafptr;
    for(i=1; i<lines; i++)
    {
        ival = myArr[i];
        insert(ival, myrootptr);
    }

    return 0;
}

mynode* createNode(unsigned long int ival, mynode* father)
{
  mynode* nodeptr = (mynode* )malloc(sizeof(mynode));
  nodeptr->val = ival;
  nodeptr->lchild = NULL;
  nodeptr->rchild = NULL;
  nodeptr->parent = father;
  nodeptr->black = false;
  return nodeptr;
}

mynode* createLeaf(unsigned long int ival, mynode* father)
{
  mynode* leafptr = (mynode* )malloc(sizeof(mynode));
  leafptr->val = ival;
  leafptr->lchild = NULL;
  leafptr->rchild = NULL;
  leafptr->parent = father;
  leafptr->black = true;
  return leafptr;
}

mynode* search (unsigned long int ival, mynode *rootptr)
{
    mynode* myptr = (mynode* )malloc(sizeof(mynode));

    myptr = rootptr;

    while ( ( (myptr->lchild) != NULL) && ( (myptr->rchild) != NULL))
    {
        if ( ival < myptr->val)
        {
            myptr = myptr->lchild;
        }
        else
        {
            myptr = myptr->rchild;
        }
    }
    return myptr;
    }

void insert (unsigned long int ival, mynode *root)
{
    mynode * current = (mynode* )malloc(sizeof(mynode));
    mynode * insertleafptr = (mynode* )malloc(sizeof(mynode));
    mynode * father = (mynode* )malloc(sizeof(mynode));
    unsigned long int max, min;
    unsigned long int num;

    current = search(ival, root);
    num = current->val;
    if((current->val) == ival)
    {
        return ;
    }
    else
    {
        if(ival>(current->val))
        {
            max = ival;
            min = current->val;
        }
        else
        {
            max = current->val;
            min = ival;
        }
        father = current->parent;
        current = createNode(min, father);
        if(num == (father->lchild)->val)
        {
            father->lchild = current;
        }
        else
        {
            father->rchild = current;
        }
        insertleafptr = createLeaf(min, current);
        current->lchild = insertleafptr;
        insertleafptr = createLeaf(max, current);
        current->rchild = insertleafptr;
        repair(current);
       return ;
    }
}

mynode * getFather (mynode* child)
{
    return child->parent;
}

mynode * getUncle (mynode* child)
{
    mynode * randNode1 = (mynode* )malloc(sizeof(mynode));
    mynode * randNode2 = (mynode* )malloc(sizeof(mynode));
    randNode1 = getFather(child);
    randNode2 = getFather(randNode1);
    if((randNode1->val) == ((randNode2->lchild)->val))
    {
        return randNode2->rchild;
    }
    else
    {
        return randNode2->lchild;
    }
    free(randNode1);
}

bool isRed (mynode* myptr)
{
    if ((myptr->black) != true)
    {
        return true;
    }
    else
    {
        return false;
    }
}

void changeColor (mynode* myptr)
{
        if ((myptr->black) == true)
        {
            myptr->black = false;
        }
        else
        {
            myptr->black = true;
        }
}

bool sameType(mynode* myptr)
{
    int counter = 0;
    unsigned long int val;
    mynode* father;
    father = myptr->parent;
    val = myptr->val;
    if ( val == (father->lchild)->val)
    {
        counter++;
    }
    else
    {
        counter--;
    }
    val = father->val;
    father = father->parent;
        if ( val == (father->lchild)->val)
    {
        counter++;
    }
    else
    {
        counter--;
    }
    if( (counter == 2) || (counter == -2))
    {
        return true;
    }
    else
    {
        return false;
    }
}



void repair (mynode* myptr)
{
    rootRepair(myptr);
    subtreeRepair(myptr);
    return ;
}

void rootRepair (mynode* myptr)
{
    if(isRoot(myptr))
    {
        myptr->black = true;
    }
    return ;
}

bool isRoot(mynode* myptr)
{
    if ((myptr->parent) == NULL)
    {
        return true;
    }
    return false;
}

void subtreeRepair (mynode* myptr)
{
    mynode* father = (mynode* )malloc(sizeof(mynode));
    mynode* uncle = (mynode* )malloc(sizeof(mynode));
    father = getFather(myptr);
    uncle = getUncle(myptr);

    if( (isRed(father)) || (isRoot(myptr) == false))
    {
        if( isRed(uncle))
        {
            colorFlip(myptr);
        }
        else
        {
            myRotate(myptr);
        }

    }
    return ;
}


void colorFlip( mynode* myptr)
{
    mynode* cfather = (mynode* )malloc(sizeof(mynode));
    mynode* cuncle = (mynode* )malloc(sizeof(mynode));
    mynode* cgrandpa = (mynode* )malloc(sizeof(mynode));
    cfather = getFather(myptr);
    cuncle = getUncle(myptr);
    cgrandpa = getFather(cfather);
    changeBlack(cfather);
    changeBlack(cuncle);
    changeRed(cgrandpa);
    repair(cgrandpa);
    return ;
}

void changeBlack(mynode* myptr)
{
    myptr->black = true;
    return ;
}

void changeRed(mynode* myptr)
{
    myptr->black = false;
    return ;
}

void myRotate(mynode* myptr)
{
    if( sameType(myptr))
    {
        rotate(myptr);
    }
    else
    {
        doubleRotate(myptr);
    }
    return ;
}

void rotate(mynode* myptr)
{
    mynode* rfather = (mynode* )malloc(sizeof(mynode));
    mynode* runcle = (mynode* )malloc(sizeof(mynode));
    mynode* rgrandpa = (mynode* )malloc(sizeof(mynode));
    mynode* current = (mynode* )malloc(sizeof(mynode));
    rfather = getFather(myptr);
    runcle = getUncle(myptr);
    rgrandpa = getFather(rfather);

    changeColor(rfather);
    changeColor(rgrandpa);

    if((rfather->lchild)->val == ((myptr)->val) )
    {
        current = rfather->rchild;
    }
    else
    {
        current = rfather->lchild;
    }

    if((rgrandpa->lchild)->val == (runcle->val))
    {
        rgrandpa->rchild = current;
    }
    else
    {
        rgrandpa->lchild = current;
    }

    rfather->parent = rgrandpa->parent;
    current = rgrandpa->parent;
    if((current->lchild)->val == (rgrandpa)->val)
    {
        current->lchild = rfather;
    }
    else
    {
        current->rchild = rfather;
    }

    if((rfather->rchild)->val == (myptr)->val)
    {
        rfather->lchild = rgrandpa;
    }
    else
    {
        rfather->rchild = rgrandpa;
    }

    free(current);
    return ;
}

void doubleRotate (mynode* myptr)
{
    mynode* current = (mynode* )malloc(sizeof(mynode));
    current = myptr->parent;
    smallRotate(myptr);
    rotate(current);
    return ;
}


void smallRotate(mynode* myptr)
{
    mynode* srfather = (mynode* )malloc(sizeof(mynode));
    mynode* srgrandpa = (mynode* )malloc(sizeof(mynode));
    mynode* srcurrent = (mynode* )malloc(sizeof(mynode));
    int flag = 0;
    srfather = getFather(myptr);
    srgrandpa = getFather(srfather);

    if( (srgrandpa->lchild)->val == (srfather->val))
    {
        srgrandpa->lchild = myptr;
    }
    else
    {
        srgrandpa->rchild = myptr;
        flag = 1;
    }

    if(flag = 0)
    {
        srcurrent = myptr->lchild;
        myptr->lchild = srfather;
        srfather->rchild = srcurrent;
    }
    else
    {
        srcurrent = myptr->rchild;
        myptr->rchild = srfather;
        srfather->lchild = srcurrent;
    }

    return ;
}

编程直到“插入”功能运行没有问题。当我将修复功能（在插入功能中）和所有实现红黑树属性的功能添加到我的数据结构时，发生了分段错误。

R&B 校正（或平衡，如果你喜欢）算法主要来自这里

重要编辑：

使用调试器让我得到了 getUncle 函数，我认为那里发生了分段错误。我的预测是它不能返回“叔叔”，因为它靠近根。因此，当数组开头的信息存储在树中或平衡达到树的如此高时，我有一个问题......有什么想法吗？

4

1 回答 1

3

您有以下行：

if(flag = 0)

这很可能是：

if(flag == 0)

注意=是赋值，==是比较。

另请注意，如果您启用了编译器警告（例如gcc -Wall ...），这将在编译时被标记，以及其他有关可疑代码的有用警告：

rbtree.c:64:31: warning: format specifies type 'unsigned long' but the argument has type 'unsigned long long' [-Wformat]
        printf("lines = %lu", lines);
                        ~~~   ^~~~~
                        %llu
rbtree.c:436:17: warning: using the result of an assignment as a condition without parentheses [-Wparentheses]
        if(flag = 0)
           ~~~~~^~~
rbtree.c:436:17: note: place parentheses around the assignment to silence this warning
        if(flag = 0)
                ^
           (       )
rbtree.c:436:17: note: use '==' to turn this assignment into an equality comparison
        if(flag = 0)
                ^
                ==
2 warnings generated.
于 2018-05-22T15:27:05.113 回答