在C數組中排列元素，所以沒有間隙

我在C中有一個常規的數組結構，在每秒運行的程序中更新結構中的所有數據。當條件滿足時，其中一個元素被清除，並被用作新元素（在這種情況下是計時器）的空閒插槽，可以在任何時候進入。在C數組中排列元素，所以沒有間隙

我所做的只是解析數組中所有尋找需要更新的活動元素的元素。但即使元素數量很少（< 2000），我覺得這是浪費時間通過非活動的。有沒有一種方法可以保持數組沒有間隙，所以我只需要迭代當前分配的元素的數量？

2011-10-25 Delirium_4

你掃描你的結構重要嗎？ – AraK

@AraK不是真的，他們只需要存儲自己的索引號，但除此之外，順序並不重要（可以更新爲新索引而沒有問題）。 –

假設元素的具體順序無關緊要，可以非常容易地完成。在指數I

A[N++] = E;

和刪除元素像這樣：

如果你有你的陣列A和有源元件N的數目，可以再增加一個元素E這樣

A[I] = A[--N];

那麼這是如何工作的？那麼，這很簡單。我們希望數組只存儲活動元素，所以我們可以假設當我們開始做這些事情時數組就是這樣的。

添加元素將始終把它在最後，由於目前在陣列中的所有元素，以及新加入的元素，將是積極的，我們可以放心地添加一個到最後。

移除元素是通過移動最後一個元素來接管我們想要移除的元素的數組索引來完成的。因此，A[0..I-1]是活動的，以及A[I+1..N]，並通過移動A[N]到A[I]，整個範圍A[0..N-1]處於活動狀態（A[N]不活躍，因爲它不再存在 - 我們把它移到A[I]，這就是爲什麼我們減少N乘1 ）。

如果要刪除元素，同時遍歷他們對其進行更新，請注意，你只能處理其中不遭到移除元素後增加的循環計數器，否則，你永遠不會處理移動的元素。

來源

2011-10-25 23:32:36

很好的解釋，我明白了。雖然，我從來沒有使用「 - N」符號，它是否像「N--」？ –

@Delirium：不，'N - '返回'N'的值，然後減1; ' - N'遞減'N'，然後返回新的值。（'++'以相同的方式工作，期望它增量而不是遞減。）在這裏你想使用'-N'，因爲你的數組元素被編入索引'[0..N-1]';如果你使用'N - '，你會嘗試訪問不存在的A [N]。 –

哦，我明白了！這解釋了我很久以前遇到的一些錯誤......很高興知道，謝謝！這個操作的名字是什麼？ –

一個比較簡單的方法來做到這一點：

void remove(struct foo *foo_array, int *n) 
{ 
    struct foo *src = foo_array, *dst = foo_array; 
    int num_removed = 0; 

    for (int i=0; i<*n; ++i) 
    { 
     // Do we want to remove this? (should_remove() left as exercise for reader.) 
     if (should_remove(src)) 
     { 
     // yes, remove; advance src without advancing dst 
     ++src; 
     ++num_removed; 
     } 
     else if (src != dst) 
     { 
     // advance src and dst (with copy) 
     *dst++ = *src++; 
     } 
     else 
     { 
     // advance both pointers (no copy) 
     ++src; 
     ++dst; 
     } 
    } 

    // update size of array 
    *n -= num_removed; 
}

的想法是，你跟蹤的數組的元素數量是有效的（*n這裏），並通過其指針爲「IN/OUT參數」。 remove()決定刪除哪些元素並複製不合適的元素。注意這是O（n），無論決定刪除多少個元素。

來源

2011-10-25 23:33:40 asveikau

每秒移動2,000個條目是微不足道的。這實在不值得優化。如果你真的覺得你必須，交換最後活動條目的非活動條目。

來源

2011-10-25 23:34:07

嗯，這主要是好奇心，我不是一個經驗豐富的程序員，並且想提高我的技能。所以你的意思是說，當我刪除一個元素時，我將「最右邊」（考慮左邊的[0]）元素存儲到它中？ –

這當然是一種方式，如果訂單並不特別重要。 –

如何在你的結構中加入一個鏈表的行爲，即一個指針成員指向下一個有源元件？

你將不得不更新元素的激活和失活這些指針。

編輯：這種方法不適合動態調整大小的數組，因爲這可能會改變內存對象的地址，通過無效列表使用的三分球..

來源

2011-10-25 23:34:17 mizo

儘管我知道如何編寫一個鏈表，但我從來沒有理解如何正確地重新排列它們......你有沒有什麼好的參考材料可以使用？ –

@ Delirium_4，要插入到單個鏈接列表中，您需要爲新元素的下一個指針指定前一個元素的下一個指針的值。然後你更新前一個元素的下一個指針指向你的新元素。要刪除一個元素，可以在前一個元素的下一個指針中指定被刪除元素的下一個指針的值。你的意思是什麼樣的重新安排？ – mizo

混合鏈接列表（或任何類型的數組元素指針）與一個可能動態增長（並因此改變地址）的數組是一個非常糟糕的主意...... –

它不喜歡你的聲音有很大的不使用鏈表的原因。如果你執行的很好，你會得到O（1）插入，O（1）刪除，你只需要保持（並迭代）活動結構。儘管中等規模的結構會有一些內存開銷，但即使是雙向鏈表也會非常有效。這種方法的好處在於，您可以將元素保留在插入順序中，而無需額外的計算開銷。

來源

2011-10-25 23:34:57 Patrick87

幾個備選方案浮現在腦海中，根據自己的需要選擇：

1）離開它，因爲它是除非你有一些性能問題或需要擴展。

2）爲每個結構添加一個「下一個」指針，將其用作雙向鏈表中的一個元素。保留兩個列表，一個用於活動列表，一個用於未使用列表。根據你使用struts的方式，還可以考慮使列表雙向鏈接。（如果需要索引結構，也可以使用數組中的元素，如果不需要，也可以停止使用數組）在數組中保持不變，將未使用的條目移動到數組的末尾。然後，當您從頭開始遍歷數組時，只要到達第一個未使用的數組，就可以停止。（您可以存儲最後一個活動結構的索引，以便每當一個結構被禁用時，您可以讓它切換最後一個活動結構的位置，然後遞減最後一個活動結構的索引。）

來源

2011-10-25 23:45:30 Arkku

在C數組中排列元素，所以沒有間隙

回答

相關問題