数组的常见操作

行客

动态数组
动态数组：在声明时未确定其大小，有需要时再重新定义其大小。

思路：

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[i] = nums[i + 1];//删除索引后的数据前移
    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[insertIndex] = insertData;
    else
    {
        for (int i = existDataSize; i > insertIndex; i++)
            nums[i] = nums[i - 1];
        nums[insertIndex] = 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[sum - i] = nums2[index_nums2--];
        else if (index_nums2 < 0)
            break;
        else if (nums1[index_nums1] > nums2[index_nums2])
            nums1[sum - i] = nums1[index_nums1--];
        else
            nums1[sum - i] = nums2[index_nums2--];
    }

}

感谢hack_hu的分享

My_A

谢谢分享

行客

这些实现，其实和STL的部分原理是一致的。