基于开放寻址与懒删除的Set ADT扩容时出现未初始化值错误

问题现象 #

使用开放寻址+懒删除实现Set ADT时，插入元素至集合总容量75%时正常，但扩容后访问所有元素（插入元素均唯一）触发Valgrind错误，错误信息如下：

==294546== Conditional jump or move depends on uninitialised value(s)
==294546==    at 0x48D6AD6: __vfprintf_internal (vfprintf-internal.c:1516)
==294546==    by 0x48C079E: printf (printf.c:33)
==294546==    by 0x10FD3D: showDisciplineStatistics (simple.c:149)
==294546==    by 0x109454: main (main.c:37)
==294546==  Uninitialised value was created by a stack allocation
==294546==    at 0x10FC00: showDisciplineStatistics (simple.c:127)

错误精准出现在索引128及之后，确认问题与扩容时元素重新添加的逻辑相关。

相关代码 #

测试用main函数 #

#include <stdlib.h>
#include <stdio.h>

#include "set.h"

int main() {
  PtSet set = setCreate();

  int v[200];
  for(int i = 0; i < 200; i++) {
    setAdd(set, i);
  }

  int elementsSize;
  setSize(set, &elementsSize);
  SetElem *elements = setValues(set);

  for(int i = 0; i < elementsSize; i++) {
    v[elements[i]] = 1;
  }

  for(int i = 0; i < 200; i++) {
    printf("%d - %d\n", i, v[i]);
  }

  return EXIT_SUCCESS;
}

set.c核心实现（关键错误点标注） #

#define LOAD_FACTOR_THRESHOLD 0.75

typedef struct setNode {
  SetElem element; // Element present at this node.
  int occupied; // Whether this node is occupied or not.
  int deleted; // Whether this node has been deleted or not.
} SetNode;

typedef struct setImpl {
  SetNode* nodes; // Nodes of the set.
  int size; // Size of the set.
  int deletedCount; // Number of nodes that have been deleted.
  int index; // Determines the capacity (getPrime(index)) and multiplier (getPrime(index - 1)). 
} SetImpl;

static int hashFunction(SetElem elem, int multiplier, int tableSize);

static bool ensureCapacity(PtSet set);

static int findPosition(); // 错误：声明与定义参数不匹配

static int getPrime(int index);

// ... 其他函数实现 ...

static int findPosition(PtSet set, SetElem elem) {
  if(set == NULL) return -1;

  int position = hashFunction(elem, getPrime(set->index - 1), getPrime(set->index));

  return position;
}

元素操作函数 #

void setElemPrint(SetElem elem) {
  printf("%d\n", elem);
}

int setElemCompare(SetElem elem1, SetElem elem2) {
  if(elem1 == elem2) return true;
  else return false;
}

Valgrind运行命令 #

valgrind --leak-check=full --show-reachable=yes --track-origins=yes ./prog

问题根源 #

1. 函数声明与定义不匹配：findPosition函数声明为无参，但实际定义接收两个参数，导致编译器错误解析参数传递，计算出错误的哈希位置，最终部分元素无法被正确插入到扩容后的哈希表中。
2. 栈数组未初始化：main函数中int v[200];是栈上分配的数组，未初始化。当部分元素未被正确插入时，v[elements[i]] = 1无法覆盖所有索引，printf时访问未初始化的v[i]值，触发Valgrind错误。

修复方案 #

1. 修正函数声明：将set.c中的static int findPosition();改为static int findPosition(PtSet set, SetElem elem);，确保声明与定义的参数一致，让编译器正确传递参数。
2. 初始化栈数组：将main函数中的int v[200];改为int v[200] = {0};，初始化所有元素为0，避免访问未初始化内存。

修正后的关键代码片段：

• set.c中的函数声明：

static int findPosition(PtSet set, SetElem elem);

• main中的数组初始化：

int v[200] = {0};

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