数组的常见操作
本帖最后由 行客 于 2019-2-24 20:36 编辑动态数组
动态数组：在声明时未确定其大小，有需要时再重新定义其大小。
思路：
1、在动态数组初始化时给其一个默认大小，当默认数组大小无法满足操作需要时，扩充数组大小。
2、在扩充数组大小时，每次将数组扩充为原有的 2 倍大小，直到满足要求。
注：realloc 重新定义数组大小时，若新分配内存大于原有内存，则数组数据不会丢失，若内存比原有内存小则丢失数据。
int* dynamicArry(int *nums,int *numSize,int newSize)
{
if (newSize < *numSize) return nums;
int size = *numSize;
while (size < newSize)
size *= 2;
nums = (int *)realloc(nums,size*sizeof(int));//重新分配内存大小
*numSize = size;
return nums;
}
定长数组数据的删除
思考：
1、考虑是否保持数组数据的有序性，若需要则需要将删除数据索引后的数依序前移。
2、若不需要保持数据有序性，则将删除数据索引标记为已删除即可（用另一数组标记当前数组每一个索引的状态）；
int *arryDelete(int* nums,int numsSize,int deleteIndex )
{
if (deleteIndex >= numsSize || deleteIndex < 0)
{
printf("超出数组索引范围\n");
return nums;
}
for (int i = deleteIndex; i < numsSize - 1; i++)
nums = nums;//删除索引后的数据前移
return nums;
}
定长数组数据的插入
思考：
1、插入数据后是否会超过数组长度
2、保持数据有序性，将插入索引以及之后数据依序后移
3、不保持数据有序性，且插入点已有数据，将已有数据放入数组末尾，新插入点数据复制给插入索引值。
int *insertArry(int* nums,int numSize,int existDataSize,int insertIndex,int insertData)
{
if (existDataSize + 1 >= numSize)
printf("超出数组长度");
if (insertIndex >= existDataSize)
nums = insertData;
else
{
for (int i = existDataSize; i > insertIndex; i++)
nums = nums;
nums = insertData;
}
return nums;
}
有序数组的合并
两个升序数组的合并：假设 nums1 已有足够的空间容纳 nums1 、nums2 两个数组中已有元素。
思路：
1、将两个数组中已有元素的最大值放到末尾。
2、若 nums2 的元素已排序完，则结束排序。
3、若 nums1 的元素已排序完，则剩余都为 nums2 元素
void merge(int* nums1, int m, int* nums2, int n) {
int i = 0,
index_nums1 = m - 1,
index_nums2 = n - 1,
sum = m + n;
while (i < sum)
{
i++;
if (index_nums1 < 0)
nums1 = nums2;
else if (index_nums2 < 0)
break;
else if (nums1 > nums2)
nums1 = nums1;
else
nums1 = nums2;
}
}
感谢hack_hu的分享 谢谢分享
这些实现，其实和STL的部分原理是一致的。
页:
[1]