最優陣列推

Question

我想創造某些功能以兩個參數：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是否有可能做這樣的事情。

Answer 1

正如評論所說，你可能只想追加到數組，然後用一個小結構和功能，讓你訪問你想要的，如果陣列正在前置到元素。你似乎已經調整了大小，所以我只會提出一些示例代碼來反轉。這是未經測試的，因爲我目前沒有一個unix box坐在我旁邊進行簡單測試 - 請注意我的C有點生鏽。

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

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

這樣，您還可以分配比您需要的數組大一些的數組。在「prependArray」中保留一個int，列出您上次重新分配的大小。當有人試圖添加項目時，請檢查您是否已達到該限制;如果有，請在添加新值之前調整列表大小。如果您添加大量數字，這可以節省分配時間。

你可能想看看了「矢量」數據結構多一點的這種想法。

Answer 2

而不是使用原始陣列，它很可能是更好的包裝你的數組中的一個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; 
} 

這如果您可以將項目附加到數組的末尾而不是將其附加到開頭，那將會明顯更簡單。請注意，上述代碼完全未經測試，可能包含逐個錯誤，但核心思想是：

• 內存分配很昂貴。分配比您需要的更多內存，然後寫入分配但未使用的空間。這樣可以減少您需要重新分配緩衝區的次數，並可以複製數據以將其轉移。
• 最小化您必須通過它在更大的步驟日益成長的緩衝次數。