习题:实现一个大小固定的有序数组,支持动态增删改操作
数组插入操作需要保证有序,插入接口将要插入的元素与数组中原有元素比较,得到所要插入的位置,然后进行插入操作。
删除操作则先查询所要删除元素在数组中的位置,然后针对指定数组位置进行删除操作。
无论是插入操作,还是删除操作,都涉及将原有数据进行相应的拷贝移位操作。
在学习专栏过程中,有以前没有想到过的操作思路,这里顺便记录下。
数组插入操作,如果是有序的,则中间插入一个元素,需要将后面的元素都往后移一位,如果不是有序的,则可以将原有位置的数据存放到最后,将新数据插入到已挪位的位置即可。
不过既然不讲究有序,为什么要在中间插入元素呢,这个实际应用场景我还没碰到过。后面快排算法会运用这一思想,到时再好好体会下。
删除操作,则删除中间一个元素,为保证数组内存的连续性,需要将后面的元素都往前移一位。不过在特殊场景下,如果不需要考虑删除后内存的连续性,可以先对删除元素进行标记,等后面插入新元素空间不足时,再对之前已标记删除的元素统一删除,减少数据拷贝操作。
数组初始化相关代码复用数据结构与算法-数组动态扩容中的接口,新增相关接口代码如下:
/**@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、删除操作拷贝个数要减一,还有需要手动将最后一个元素清空下。