数据结构与算法-数组动态扩容

根据昨天的计划，今天实现了下数组的第一个习题，动态扩容。

这个具体要实现成什么样，没有明确说明，所以我按照自己的想法，只是实现了支持任何类型的元素数组进行动态扩容，新增加的元素插入到上一个元素的后面，不考虑删除操作。

实现代码具体如下(忽略我的出错打印～)：

typedef struct dyn_array{
  void *array;    // 数组地址
  int array_len;    // 数组长度
  int curr_len;    // 当前存储位置
  int element_len;  // 数组元素大小
}DYN_ARRAY;

/**@brief    数组初始化
 * @param[in]  p_array 数组指针
 * @param[in]   initial_len 初始化数组长度
 * @param[in]   element_len 数组元素类型长度
 * @return     OK / ERROR
 */
int array_init(DYN_ARRAY *p_array, int initial_len, int element_len)
{
  if (NULL == p_array)
  {
    printf("%s %s %d    \n", __FILE__, __func__, __LINE__ );
    return ERROR;
  }

  p_array->array = malloc(initial_len * element_len);
  if (NULL == p_array->array)
  {
    printf("%s %s %d    \n", __FILE__, __func__, __LINE__ );
    return ERROR;
  }

  memset(p_array->array, 0, (initial_len * element_len));
  p_array->array_len = initial_len;
  p_array->element_len = element_len;
  p_array->curr_len = 0;

  return OK;
}

/**@brief      插入新元素到前一个元素后面
 * @param[in]  p_array 数组指针
 * @param[in]   data 要插入的元素地址
 * @param[in]   element_len 元素类型长度
 * @return     OK / ERROR
 */
int array_insert_data(DYN_ARRAY *p_array, void *data, int element_len)
{
  void *p_tmp_array = NULL;

  if (NULL == p_array || NULL == data)
  {
    printf("%s %s %d    \n", __FILE__, __func__, __LINE__ );
    return ERROR;
  }

  if (NULL == p_array->array || p_array->element_len != element_len)
  {
    printf("%s %s %d    \n", __FILE__, __func__, __LINE__ );
    return ERROR;
  }

  if (p_array->curr_len == p_array->array_len)
  {
    printf("%s %s %d    \n", __FILE__, __func__, __LINE__ );

    // 数组自动扩容1.5倍
    p_tmp_array = malloc(p_array->array_len * 1.5 * element_len);
    if (NULL == p_tmp_array)
    {
      printf("%s %s %d    \n", __FILE__, __func__, __LINE__ );
      return ERROR;
    }

    memset(p_tmp_array, 0, (p_array->array_len * 1.5 * element_len));
    memcpy(p_tmp_array, p_array->array, p_array->array_len * element_len);
    SAFE_FREE(p_array->array);
    p_array->array = p_tmp_array;
    p_array->array_len = p_array->array_len * 1.5;  // 遗漏，忘记重新赋值数组长度
  }

  //memcpy(&p_array->array[p_array->curr_len * element_len], data, element_len);  // waring:
  memcpy(&((char *)p_array->array)[p_array->curr_len * element_len], data, element_len);
  p_array->curr_len += 1;

  return OK;
}

中间遇到的问题：

1、编译出现如下告警

waring: dereferencing 'void *' pointer [enabled by default]
waring: taking address of expression of type 'void' [enabled by default]

问题原始代码：

memcpy(&p_array->array[p_array->curr_len * element_len], data, element_len);

问题在于第一个入参，取数组的下标，本身是需要知道元素的类型，才知道应该如何计算某个数组元素的地址，公式如下：

a[k]_address = base_address + k * type_size

而我这里为了可以适配任何类型元素，所以是void类型，这样就不知道type_size大小了，这里我都按字节来计算偏移，所以都强制转换成(char *)处理，如下：

memcpy(&((char *)p_array->array)[p_array->curr_len * element_len], data, element_len);

2、计算数组个数，没有除以每个元素的个数。

for (i = 0; i < sizeof(buf)/sizeof(buf[0]); i++)

FEATURED TAGS