数据结构与算法-数组支持动态增删

Posted by 周思进 on July 22, 2019

习题:实现一个大小固定的有序数组,支持动态增删改操作

数组插入操作需要保证有序,插入接口将要插入的元素与数组中原有元素比较,得到所要插入的位置,然后进行插入操作。

删除操作则先查询所要删除元素在数组中的位置,然后针对指定数组位置进行删除操作。

无论是插入操作,还是删除操作,都涉及将原有数据进行相应的拷贝移位操作。

在学习专栏过程中,有以前没有想到过的操作思路,这里顺便记录下。

数组插入操作,如果是有序的,则中间插入一个元素,需要将后面的元素都往后移一位,如果不是有序的,则可以将原有位置的数据存放到最后,将新数据插入到已挪位的位置即可。

不过既然不讲究有序,为什么要在中间插入元素呢,这个实际应用场景我还没碰到过。后面快排算法会运用这一思想,到时再好好体会下。

删除操作,则删除中间一个元素,为保证数组内存的连续性,需要将后面的元素都往前移一位。不过在特殊场景下,如果不需要考虑删除后内存的连续性,可以先对删除元素进行标记,等后面插入新元素空间不足时,再对之前已标记删除的元素统一删除,减少数据拷贝操作。

数组初始化相关代码复用数据结构与算法-数组动态扩容中的接口,新增相关接口代码如下:

/**@brief    有序插入数组
 * @param[in]  p_array 数组指针
 * @param[in]   data 要插入的元素地址
 * @param[in]   element_len 元素类型长度
 * @return     OK / ERROR
 */
int array_insert_data_by_sort(DYN_ARRAY *p_array, void *data, int element_len)
{
  void *p_tmp_array = NULL;
  int i = 0;

  // 省去入参判断

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

  for (i = 0; i < p_array->curr_len; i++)    // 注意别判断使用 i < p_array->array_len
  {
    if (((int *)p_array->array)[i] > *((int*)data))  // 判断大于就进行拷贝操作
    {
      memmove(&((int *)p_array->array)[i+1], &((int *)p_array->array)[i], 
        (p_array->curr_len - i) * p_array->element_len);
      break;
    }
  }

  ((int *)p_array->array)[i] = *(int*)data;
  p_array->curr_len += 1;

  return OK;
}


/**@brief    获取指定元素下标地址
 * @param[in]  p_array 数组指针
 * @param[in]   data 要查找的元素
 * @return     OK / ERROR
 */
int search_data_index(DYN_ARRAY *p_array, void *data)
{
  int i = 0;

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

  for (i = 0; i < p_array->curr_len; i++)
  {
    if (((int *)p_array->array)[i] == *(int *)data)
    {
      return i;
    }
  }

  return -1;
}

/**@brief    删除元素
 * @param[in]  p_array 数组指针
 * @param[in]   index 要删除的数组下标
 * @return     OK / ERROR
 */
int array_delete_data(DYN_ARRAY *p_array, unsigned int index)
{
  if (NULL == p_array || index > p_array->curr_len)
  {
    printf("%s %s %d    \n", __FILE__, __func__, __LINE__ );
    return ERROR;
  }

  memmove( &((int *)p_array->array)[index], &((int *)p_array->array)[index+1],  
    (p_array->curr_len - index -1 ) * p_array->element_len);  //  这里需要减少一个

  memset(&((int *)p_array->array)[p_array->curr_len-1], 0, p_array->element_len);  // 需要手动将最后一个清0
  p_array->curr_len -= 1;

  return OK;
}

中间遇到的问题:

1、memmove函数接口使用错误,第三个入参是拷贝的字节数,对于整型数组一定要注意是数组个数乘以整型变量占用字节数。类似问题经常犯,长个记性啊!!

2、删除操作拷贝个数要减一,还有需要手动将最后一个元素清空下。