C语言哈希表实现中插入操作触发Segmentation Fault问题排查

尝试用C语言实现链地址法哈希表，插入数组最后一个元素41时触发Segmentation Fault，GDB调试显示错误发生在insertVal函数的第27行while循环处。

节点结构体定义 #

//define a Nodes
typedef struct node{
    int data;
    struct node* nextPtr;
} node;
typedef node* nodePtr;

哈希表相关函数 #

//Insert values into the hash table
void insertVal(nodePtr* aNode, int val){
    nodePtr temp = (nodePtr) malloc(sizeof(node));
    temp->data = val;
    temp->nextPtr = NULL;
    //Insert the value at the hashtable
    if(!(*aNode)){
        (*aNode) = temp;
    }
    else{
        //Check if the first element is greater than temp's value
        //Append to the front of the value
        if(val < (*aNode)->data){       
            temp->nextPtr = (*aNode);   //set temp's next to point to head node
            *aNode = temp;              //reset the position of the head node
        }
        else if(val >= (*aNode)->data) {
            //Set up the walking nodes
            nodePtr prev = NULL;
            nodePtr curr = *aNode;
            //Walk through list until either is false:
            //  - val <= curr 
            //  - curr  == NULL
            while((val >= curr->data) && (curr)){
              //Check if the values are equal
              if(val == curr->data){
                //Insert them
                temp->nextPtr = curr->nextPtr;
                curr->nextPtr = temp;
                return;
              }
              prev = curr;
              curr = curr->nextPtr;
            }
            //at either condition,
            prev->nextPtr = temp;       //Insert inbetween the prev and curr
            temp->nextPtr = curr;
        }
    }
}

//Delete a value from the node Array
int delete(nodePtr* aNode) {
    nodePtr temp = *aNode;      //Get the leading node value
    (*aNode) = (*aNode)->nextPtr;//Move head pointer to next node
    int ret = temp->data;        //Get the value of deleted node
    free(temp);                 //Free Space allocated to deleted node
    return ret;                 //Return the deleted value
}

//Function to search a Node for a value
int* search(nodePtr* aNode, int val){
    int* valPos = calloc(2, sizeof(int));   //(0,1) = (arrayInd, nodeInd)
    memset(valPos, -1, 2);      //fill the memory with -1 and return
    if(!(*aNode)){
        return valPos;
    }
    int nodePos = 0;
    nodePtr curr = *aNode;
    //Walk node until:
    //  - value found
    //  - node's NULL
    while((val == curr->data) && (curr)){
        nodePos++;              //Increment the node position
        curr = curr->nextPtr;   //Walking the node
    }
    valPos[0] = val%10;         //get the val's array position
    valPos[1] = nodePos;        //Get the val's node level
    return valPos;    
}

main函数代码 #

int main(){
    int A[5] = {21,23,11,23,41};
    //Create a chaining hash table
    nodePtr* aTable = calloc(10, sizeof(nodePtr));      //Array of nodePtrs
    //Insert the values into the aTable
    for(int i = 0; i<5; i++){
        //Declare hash function
        int hasFunc = A[i]%10; 
        insertVal(&aTable[hasFunc], A[i]);
    }
    //Search for inserted values
    for(int i = 0; i<5; i++){
        int hasFunc = A[i]%10; 
        int *res = search(&aTable[A[i]%10], A[i]);
        if(res[0] != -1){
            printf("Value: %d found at array index: %d, and node level: %d\n", A[i], res[0], res[1]);
        }
        else{
            printf("value not found\n");
        }
    }
    return 0;
}

GDB调试信息 #

Program received signal SIGSEGV, Segmentation fault.
0x00005555555554b4 in insertVal (aNode=0x5555555592a8, val=41) at Chaining.c:27
27                  while((val >= curr->data) && (curr)){
(gdb) Quit

问题原因与修复方案 #

1. 核心段错误原因

insertVal函数中while循环的条件顺序错误：先判断val >= curr->data再检查curr是否为NULL。当curr遍历到链表末尾变为NULL时，curr->data会访问空指针，直接触发段错误。

修复后的while循环条件：

while(curr && (val >= curr->data)){

先检查curr是否有效，再访问其成员，避免空指针解引用。

2. 其他潜在问题修复

• search函数逻辑错误：原while循环条件val == curr->data会导致找到目标值后立刻退出，无法统计正确的节点位置，且未找到时也会提前终止。应改为：

  while(curr && (val != curr->data)){
      nodePos++;
      curr = curr->nextPtr;
  }
  // 找到目标值才更新位置，否则保持-1
  if(curr){
      valPos[0] = val%10;
      valPos[1] = nodePos;
  }
  

• memset参数错误：原memset(valPos, -1, 2)仅填充2字节，而valPos是2个int类型（通常8字节），正确写法：

  memset(valPos, -1, 2 * sizeof(int));
  

• delete函数空指针检查：当链表为空时，*aNode为NULL，直接访问(*aNode)->nextPtr会触发错误，需添加判断：

  int delete(nodePtr* aNode) {
      if(!(*aNode)){
          return -1; // 或其他错误标识
      }
      nodePtr temp = *aNode;
      (*aNode) = (*aNode)->nextPtr;
      int ret = temp->data;
      free(temp);
      return ret;
  }
  

内容的提问来源于stack exchange，提问作者Grimmace_23