btree实现中的分段错误

Question

任何人都可以请帮助删除此分段错误。我在这个代码上工作了一个星期，仍然无法调试。这段代码是一个Btree实现。插入部分正常工作，但删除时出现分段错误。我无法调试它，任何人都可以请帮忙吗？

我已经给出了基于此链接输入（转换了字母值ASCII值） http://cis.stvincent.edu/html/tutorials/swd/btree/btree.html

当我删除第一H（相当于ASCII值），它工作正常，但是当我删除T（相当于ASCII值）我会得到一个分段错误。

#include<stdio.h> 
    #include<stdlib.h> 
    #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;i<20;i++) 
        { 
         key = input_array[i]; 
         insert(key); 
        } 
        //insert(key++); 
        //insert(key); 
        break; 
       case 2: 
        printf("Enter the key : "); 
        scanf("%d",&key); 
        DelNode(key); 
        break; 
       case 3: 
        printf("Enter the key : "); 
        scanf("%d",&key); 
        search(key); 
        break; 
       case 4: 
        printf("Btree is :\n"); 
        display(root,0); 
        break; 
       case 5: 
        exit(1); 
       default: 
        printf("Wrong choice\n"); 
        break; 
      }/*End of switch*/ 
     }/*End of while*/ 
     return 0; 
    }/*End of main()*/ 

    void insert(int key) 
    { 
     struct node *newnode; 
     int upKey; 
     enum KeyStatus value; 
     value = ins(root, key, &upKey, &newnode); 
     if (value == Duplicate) 
      printf("Key already available\n"); 
     if (value == InsertIt) 
     { 
      struct node *uproot = root; 
      root=malloc(sizeof(struct node)); 
      root->n = 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 < n && key == ptr->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 < M - 1) 
     { 
      pos = searchPos(newKey, ptr->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 < (*newnode)->n; i++) 
     { 
      (*newnode)->p[i] = ptr->p[i + splitPos + 1]; 
      if(i < (*newnode)->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 < ptr->n; i++) 
       printf("%d ",ptr->keys[i]); 
      printf("\n"); 
      for (i=0; i <= ptr->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 < ptr->n; i++) 
       printf(" %d",ptr->keys[i]); 
      printf("\n"); 
      pos = searchPos(key, ptr->keys, n); 
      if (pos < n && key == ptr->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 < n && key > 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; i++) 
      { 
       key_arr[i-1] = key_arr[i]; 
       p[i] = p[i+1]; 
      } 
      return --ptr->n >= (ptr==root ? 1 : min) ? Success : LessKeys; 
     }/*End of if */ 

     if (pos < n && key == key_arr[pos]) 
     { 
      struct node *qp = p[pos], *qp1; 
      int nkey; 
      while(1) 
      { 
       nkey = qp->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 < rptr->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 < rptr->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; i++) 
     { 
      key_arr[i-1] = key_arr[i]; 
      p[i] = p[i+1]; 
     } 
     return --ptr->n >= (ptr == root ? 1 : min) ? Success : LessKeys; 
    }/*End of del()*/ 

可能是什么问题？

Answer 1

不知道到底该如何工作，我可以说，你写的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 <your executable>