C 数组 Insertion/Deletion

Question

对于一个array，说明插入和删除是0(n):

与此相关的两个问题：

什么是“插入”或“删除”操作？例如，下面是插入吗？
```
int numbers[10];
numbers[4] = 12; // this would be 0(1) though (?)
```
这是指一个动态数组，其中 insert/delete 暗示列表中涉及一些调整大小？也就是说，如果我们有一个 10 数数组并且我们想要删除元素 4，而不是 numbers[3] = 0，这意味着我们想要获得一个大小为 9 的数组，其中前一个条目是第五个位置的项目？例如：
```
int numbers2[9];
memcpy(numbers2, numbers, sizeof(int) * 3);
memcpy(numbers2+3, numbers+4, sizeof(int) * 6);
```

Answer 1

在数组中添加或删除元素意味着您需要将现有元素向上或向下移动以说明添加或删除的元素。

例如：

// assumes the array has capacity to add a member
void add_array(int *arr, int len, int index, int value)
{
    int i;
    for (i=len-1; i>index; i--) {
        arr[i+1] =  arr[i];
    }
    arry[index] = value;
}

void remove_array(int *arr, int len, int index)
{
    int i;
    for (i=index; i<len-1; i++) {
        arr[i] =  arr[i+1];
    }
}

这是 O(n)，因为执行必要的移位平均需要 n 次迭代。

C 数组 Insertion/Deletion

C Array Insertion/Deletion

c

algorithm

big-o

data-structures