数组的常见操作

行客

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

思路：

1、在动态数组初始化时给其一个默认大小，当默认数组大小无法满足操作需要时，扩充数组大小。

2、在扩充数组大小时，每次将数组扩充为原有的 2 倍大小，直到满足要求。

注：realloc 重新定义数组大小时，若新分配内存大于原有内存，则数组数据不会丢失，若内存比原有内存小则丢失数据。

1. int* dynamicArry(int *nums,int *numSize,int newSize)
   
2. {
   
3.     if (newSize < *numSize) return nums;
   
4.     int size = *numSize;
   
5.     while (size < newSize)
   
6.         size *= 2;
   
7.     nums = (int *)realloc(nums,size*sizeof(int));//重新分配内存大小
   
8.     *numSize = size;
   
9.     return nums;
   
10. }

复制代码

定长数组数据的删除
思考：

1、考虑是否保持数组数据的有序性，若需要则需要将删除数据索引后的数依序前移。

2、若不需要保持数据有序性，则将删除数据索引标记为已删除即可（用另一数组标记当前数组每一个索引的状态）；

1. int *arryDelete(int* nums,int numsSize,int deleteIndex )
   
2. {
   
3.     if (deleteIndex >= numsSize || deleteIndex < 0)
   
4.     {
   
5.         printf("超出数组索引范围\n");
   
6.         return nums;
   
7.     }
   
8.     for (int i = deleteIndex; i < numsSize - 1; i++)
   
9.         nums[i] = nums[i + 1];//删除索引后的数据前移
   
10.     return nums;
    
11. }

复制代码

定长数组数据的插入
思考：

1、插入数据后是否会超过数组长度

2、保持数据有序性，将插入索引以及之后数据依序后移

3、不保持数据有序性，且插入点已有数据，将已有数据放入数组末尾，新插入点数据复制给插入索引值。

1. int *insertArry(int* nums,int numSize,int existDataSize,int insertIndex,int insertData)
   
2. {
   
3.     if (existDataSize + 1 >= numSize)
   
4.         printf("超出数组长度");
   
5.     if (insertIndex >= existDataSize)
   
6.         nums[insertIndex] = insertData;
   
7.     else
   
8.     {
   
9.         for (int i = existDataSize; i > insertIndex; i++)
   
10.             nums[i] = nums[i - 1];
    
11.         nums[insertIndex] = insertData;
    
12.     }
    
13.     return nums;
    
14. }

复制代码

有序数组的合并
两个升序数组的合并：假设 nums1 已有足够的空间容纳 nums1 、nums2 两个数组中已有元素。

思路：

1、将两个数组中已有元素的最大值放到末尾。

2、若 nums2 的元素已排序完，则结束排序。

3、若 nums1 的元素已排序完，则剩余都为 nums2 元素

1. void merge(int* nums1, int m, int* nums2, int n) {
   
2.     int i = 0,
   
3.         index_nums1 = m - 1,
   
4.         index_nums2 = n - 1,
   
5.         sum = m + n;
   
6.     while (i < sum)
   
7.     {
   
8.         i++;
   
9.         if (index_nums1 < 0)
   
10.             nums1[sum - i] = nums2[index_nums2--];
    
11.         else if (index_nums2 < 0)
    
12.             break;
    
13.         else if (nums1[index_nums1] > nums2[index_nums2])
    
14.             nums1[sum - i] = nums1[index_nums1--];
    
15.         else
    
16.             nums1[sum - i] = nums2[index_nums2--];
    
17.     }
    
18. 
    
19. }

复制代码

感谢hack_hu的分享

My_A

谢谢分享

行客

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