最佳的数组推送方法

Question

最佳的数组推送方法

carrays

3

我希望创建一个函数，它有两个参数：int element 和输入数组。我希望这个函数能够将元素参数放在数组的第一个位置，同时扩大数组一个单元，最后将输入数组放在插入元素后面。

举个例子，假设我的输入数组是{1, 2, 3}，传递给函数的元素是5。输出应该为{5, 1, 2, 3}。

如何以最优的方式实现这个功能？

我提出了以下函数：

void push(int el, int **arr)
{
    int *arr_temp = *arr;

    *arr = NULL;
    *arr = (int*) malloc(sizeof(int)*(n - 1));

    (*arr)[0] = el;
    for(int i = 0; i < (int)n - 1; i++)
    {
        (*arr)[i + 1] = arr_temp[i];
    }
}

这个功能能用，但是它不是我写过的最快的函数，而且它会拖慢整个程序。有没有更好的方法来实现呢？

我的猜测是做一些类似于(*arr)[1] = arr_temp的操作，但是它没有起作用，我也不确定在C语言中是否有实现这样的可能性。

- user2252786

2

一个数组并不是这种操作的理想数据结构。 - Carl Norum

1

尝试使用realloc来扩大数组而无需复制每个元素（如果可能的话）。 - Tushar

4

从技术上讲，这不是一次“推送”操作，而是一次“插入到数组开头”的操作。如果你发现自己比进行真正的“推送”操作（将某些内容添加到数组末尾）更频繁地这样做，那么你可能需要翻转数组，这样你就可以实际上将内容添加到末尾了。如果你经常使用推送/弹出/插入/移动操作，但很少访问数组中间的元素，则双向链表可能更适合。 - cdhowie

@Tushar，在这种情况下，这该怎么做？ - Carl Norum

2

你也没有释放旧数组。在C程序中，你不需要对malloc的返回值进行强制类型转换。 - Carl Norum

显示剩余4条评论

2个回答

0

根据评论所建议的，您可能只想将元素附加到数组末尾，然后使用一个小结构体和函数来让您像将数组前置一样访问所需的元素。您似乎已经掌握了重新调整大小，因此我只会建议一些反转示例代码。由于我现在身边没有Unix盒子可以轻松测试，因此这些代码未经过测试 - 请注意，我的C语言有点生疏。

typedef struct{
    int* array;
    int size;
} prependArray;

void accessElement(int element, prependArray myArray) {
    return myArray.array[size-element-1];
}

这样，您还可以分配比所需稍大的数组。在“prependArray”中保留一个int，列出您上次重新分配的大小。当有人尝试添加项目时，请检查是否达到了该限制；如果是，则在添加新值之前调整列表大小。如果您要添加许多数字，则可以节省分配时间。

您可能想查找“向量”数据结构，以获取更多关于此类思想的信息。

- Marshall Conover

问题是我正在操作的数组已经是列表的属性。将int *array list的属性更改为列表内部的“this”列表是否可以？ - user2252786

@user2252786 - 我已经更改了参数的名称，以防名称"List"令人困惑。现在，当您说您正在操作的数组已经是列表的属性时，您是否意味着您正在将链接列表中的所有元素添加到一个数组中？ - Marshall Conover

我正在遍历列表，并对每个元素的数组执行unshift操作。 - user2252786

啊 - 那么是的，你应该能够更改列表节点，使用“prependArray”结构而不是int*。 - Marshall Conover

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jamesdlin · Accepted Answer

不要使用原始数组，最好将数组包装在一个结构体中：

typedef struct
{
    size_t elementsAllocated;
    size_t elementsUsed;
    int* buffer;
} vector;

然后您的推送函数可能看起来像这样：

vector* push_front(vector* v, int item)
{
    if (elementsUsed == elementsAllocated)
    {
        // Time to grow the buffer.
        int elementsAllocated = v->elementsAllocated * 2;
        if (elementsAllocated <= v->elementsAllocated)
        {
            abort(); // Overflow occurred.
        }

        int* buffer = realloc(v->buffer, elementsAllocated * sizeof *buffer);
        if (buffer == NULL)
        {
            abort();
        }

        // Shift the existing data over.
        memmove(buffer + elementsAllocated - v->elementsUsed,
                buffer + v->elementsAllocated - v->elementsUsed,
                v->elementsUsed * sizeof *buffer);
        v->buffer = buffer;
        v->elementsAllocated = elementsAllocated;
    }

    // Prepend the new item.
    int* p = v->buffer + v->elementsAllocated - v->elementsUsed - 1;
    *p = item;
    v->elementsUsed++;
    return p;
}

这将会更加简单，如果你可以将项附加到数组的末尾而不是在开头前置。请注意，上述代码完全未经测试，可能包含离谱的错误，但核心思想如下：

内存分配是昂贵的。分配比所需更多的内存，然后写入已分配但未使用的空间。这减少了需要重新分配缓冲区和复制数据以进行移位的次数。
通过较大的步骤增长缓冲区来最大程度地减少增长缓冲区的次数。