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

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

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

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

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

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

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

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

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

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

/**@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、删除操作拷贝个数要减一，还有需要手动将最后一个元素清空下。

FEATURED TAGS