3

我想创建一些带有两个参数的函数：int 元素和输入数组。我希望这个函数将元素参数放在数组的第一位，将数组放大单个索引，最后将输入数组放在推入的元素之后。

为了说明这一点，假设我的输入数组是 {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 中是否有可能做这样的事情。

4

2 回答 2

2

而不是使用原始数组，最好将数组包装在 a 中struct：

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;
}

如果您可以将项目附加到数组的末尾而不是添加到开头，这将变得更加简单。请注意，上面的代码完全未经测试，可能包含一个错误，但核心思想是：

  • 内存分配很昂贵。分配比您需要的更多的内存，然后写入已分配但未使用的空间。这减少了您需要重新分配缓冲区和复制数据以将其转移的次数。
  • 通过以更大的步长增加缓冲区，最大限度地减少增加缓冲区的次数。
于 2013-04-08T22:25:27.403 回答
0

正如评论中所建议的，您可能只想追加到数组，然后使用一些结构和函数来让您访问所需的元素，就像数组被追加到一样。您似乎已经缩小了尺寸，所以我只建议一些用于反转的示例代码。这是未经测试的，因为我现在没有一个 unix 盒子来方便测试 - 请注意我的 C 有点生锈。

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

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

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

您可能想查找“向量”数据结构以了解更多关于这种想法的信息。

于 2013-04-08T22:06:49.250 回答