btree实现中的分段错误

任何人都可以帮助删除此分段错误。 我正在研究这段代码一周仍无法调试。 此代码是Btree实现。 插入部分工作正常但删除时存在分段错误。 我无法调试它,有人可以帮忙吗?

我根据此链接给出了输入(已将字母值转换为ASCII值) http://cis.stvincent.edu/html/tutorials/swd/btree/btree.html

当我删除第一个H (等效的ASCII值)时它可以正常工作,但是当我删除T (等效的ASCII值)时,我会得到一个分段错误。

  #include #include #define M 5 struct node{ int n; /* n < M No. of keys in node will always less than order of B tree */ int keys[M-1]; /*array of keys*/ struct node *p[M]; /* (n+1 pointers will be in use) */ }*root=NULL; enum KeyStatus { Duplicate,SearchFailure,Success,InsertIt,LessKeys }; void insert(int key); void display(struct node *root,int); void DelNode(int x); void search(int x); enum KeyStatus ins(struct node *r, int x, int* y, struct node** u); int searchPos(int x,int *key_arr, int n); enum KeyStatus del(struct node *r, int x); int input_array[20]= {65,67,71,78,72,69,75,81,77,70,87,76,84,90,68,80,82,88,89,83}; int main() { int choice, i,key = 11; printf("Creation of B tree for node %d\n",M); while(1) { printf("1.Insert\n"); printf("2.Delete\n"); printf("3.Search\n"); printf("4.Display\n"); printf("5.Quit\n"); printf("Enter your choice : "); scanf("%d",&choice); switch(choice) { case 1: //printf("Enter the key : "); //scanf("%d",&key); //for(i=0;i<20;i++) for(i=0;in = 1; root->keys[0] = upKey; root->p[0] = uproot; root->p[1] = newnode; }/*End of if */ }/*End of insert()*/ enum KeyStatus ins(struct node *ptr, int key, int *upKey,struct node **newnode) { struct node *newPtr, *lastPtr; int pos, i, n,splitPos; int newKey, lastKey; enum KeyStatus value; if (ptr == NULL) { *newnode = NULL; *upKey = key; return InsertIt; } n = ptr->n; pos = searchPos(key, ptr->keys, n); if (pos keys[pos]) return Duplicate; value = ins(ptr->p[pos], key, &newKey, &newPtr); if (value != InsertIt) return value; /*If keys in node is less than M-1 where M is order of B tree*/ if (n keys, n); /*Shifting the key and pointer right for inserting the new key*/ for (i=n; i>pos; i--) { ptr->keys[i] = ptr->keys[i-1]; ptr->p[i+1] = ptr->p[i]; } /*Key is inserted at exact location*/ ptr->keys[pos] = newKey; ptr->p[pos+1] = newPtr; ++ptr->n; /*incrementing the number of keys in node*/ return Success; }/*End of if */ /*If keys in nodes are maximum and position of node to be inserted is last*/ if (pos == M - 1) { lastKey = newKey; lastPtr = newPtr; } else /*If keys in node are maximum and position of node to be inserted is not last*/ { lastKey = ptr->keys[M-2]; lastPtr = ptr->p[M-1]; for (i=M-2; i>pos; i--) { ptr->keys[i] = ptr->keys[i-1]; ptr->p[i+1] = ptr->p[i]; } ptr->keys[pos] = newKey; ptr->p[pos+1] = newPtr; } splitPos = (M - 1)/2; (*upKey) = ptr->keys[splitPos]; (*newnode)=malloc(sizeof(struct node));/*Right node after split*/ ptr->n = splitPos; /*No. of keys for left splitted node*/ (*newnode)->n = M-1-splitPos;/*No. of keys for right splitted node*/ for (i=0; i n; i++) { (*newnode)->p[i] = ptr->p[i + splitPos + 1]; if(i n - 1) (*newnode)->keys[i] = ptr->keys[i + splitPos + 1]; else (*newnode)->keys[i] = lastKey; } (*newnode)->p[(*newnode)->n] = lastPtr; return InsertIt; }/*End of ins()*/ void display(struct node *ptr, int blanks) { if (ptr) { int i; for(i=1;i<=blanks;i++) printf(" "); for (i=0; i n; i++) printf("%d ",ptr->keys[i]); printf("\n"); for (i=0; i n; i++) display(ptr->p[i], blanks+10); }/*End of if*/ }/*End of display()*/ void search(int key) { int pos, i, n; struct node *ptr = root; printf("Search path:\n"); while (ptr) { n = ptr->n; for (i=0; i n; i++) printf(" %d",ptr->keys[i]); printf("\n"); pos = searchPos(key, ptr->keys, n); if (pos keys[pos]) { printf("Key %d found in position %d of last dispalyednode\n",key,i); return; } ptr = ptr->p[pos]; } printf("Key %d is not available\n",key); }/*End of search()*/ int searchPos(int key, int *key_arr, int n) { int pos=0; while (pos  key_arr[pos]) pos++; return pos; }/*End of searchPos()*/ void DelNode(int key) { struct node *uproot; enum KeyStatus value; value = del(root,key); switch (value) { case SearchFailure: printf("Key %d is not available\n",key); break; case LessKeys: uproot = root; root = root->p[0]; free(uproot); break; }/*End of switch*/ }/*End of delnode()*/ enum KeyStatus del(struct node *ptr, int key) { int pos, i, pivot, n ,min; int *key_arr; enum KeyStatus value; struct node **p,*lptr,*rptr; if (ptr == NULL) return SearchFailure; /*Assigns values of node*/ n=ptr->n; key_arr = ptr->keys; p = ptr->p; min = (M - 1)/2;/*Minimum number of keys*/ pos = searchPos(key, key_arr, n); if (p[0] == NULL) { if (pos == n || key < key_arr[pos]) return SearchFailure; /*Shift keys and pointers left*/ for (i=pos+1; i n >= (ptr==root ? 1 : min) ? Success : LessKeys; }/*End of if */ if (pos n; qp1 = qp->p[nkey]; if (qp1 == NULL) break; qp = qp1; }/*End of while*/ key_arr[pos] = qp->keys[nkey-1]; qp->keys[nkey - 1] = key; }/*End of if */ value = del(p[pos], key); if (value != LessKeys) return value; if (pos > 0 && p[pos-1]->n > min) { pivot = pos - 1; /*pivot for left and right node*/ lptr = p[pivot]; rptr = p[pos]; /*Assigns values for right node*/ rptr->p[rptr->n + 1] = rptr->p[rptr->n]; for (i=rptr->n; i>0; i--) { rptr->keys[i] = rptr->keys[i-1]; rptr->p[i] = rptr->p[i-1]; } rptr->n++; rptr->keys[0] = key_arr[pivot]; rptr->p[0] = lptr->p[lptr->n]; key_arr[pivot] = lptr->keys[--lptr->n]; return Success; }/*End of if */ if (pos > min) { pivot = pos; /*pivot for left and right node*/ lptr = p[pivot]; rptr = p[pivot+1]; /*Assigns values for left node*/ lptr->keys[lptr->n] = key_arr[pivot]; lptr->p[lptr->n + 1] = rptr->p[0]; key_arr[pivot] = rptr->keys[0]; lptr->n++; rptr->n--; for (i=0; i n; i++) { rptr->keys[i] = rptr->keys[i+1]; rptr->p[i] = rptr->p[i+1]; }/*End of for*/ rptr->p[rptr->n] = rptr->p[rptr->n + 1]; return Success; }/*End of if */ if(pos == n) pivot = pos-1; else pivot = pos; lptr = p[pivot]; rptr = p[pivot+1]; /*merge right node with left node*/ lptr->keys[lptr->n] = key_arr[pivot]; lptr->p[lptr->n + 1] = rptr->p[0]; for (i=0; i n; i++) { lptr->keys[lptr->n + 1 + i] = rptr->keys[i]; lptr->p[lptr->n + 2 + i] = rptr->p[i+1]; } lptr->n = lptr->n + rptr->n +1; free(rptr); /*Remove right node*/ for (i=pos+1; i n >= (ptr == root ? 1 : min) ? Success : LessKeys; }/*End of del()*/ 

可能是什么问题呢?

如果不知道这应该如何工作,我可以说你在p向量之外写

  for (i=0; i < rptr->n; i++) { lptr->keys[lptr->n + 1 + i] = rptr->keys[i]; // When you delete key 84, rptr->n is 4 at one point which takes you outside // p[M] lptr->p[lptr->n + 2 + i] = rptr->p[i+1]; } 

Valgrind是一个很好用的工具,我发现这个问题是由valgrind -v --leak-check=full

Interesting Posts