C中廣泛使用哪種數據結構？

幾天前我問自己哪個數據結構應該在C的函數中。我通常寫在C++和選擇將下降到std :: vector。C中廣泛使用哪種數據結構？

有沒有一些可能的選擇：

靜態（足夠大的）陣列
動態數組在需要時（如增加了一倍大小）
一個自己的列表實現與一個結構它生長指針下一個

最後一個選項似乎不尋常。有沒有更大的項目在哪裏有人使用自己的結構如列表？數組結構或自己的數據結構之間是否有一個通用規則？

當我需要一個樹結構時，我不會三思而後行寫一棵樹。是否有任何與這種結構廣泛使用的庫（如boost for C++）？或者這被認爲是不好的風格，因爲你將不得不存儲一個void *而不是的實際類型？

感謝您的經驗！

來源

2011-04-08 tgmath

各有各的優點和缺點。

靜態數組：非常適合查找表和在整個程序執行過程中不改變其大小的數據。它們在程序啓動時分配，因此您不必以任何方式管理該內存。缺點是你不能調整大小或釋放一個靜態數組 - 它會一直呆在那裏，直到程序終止。
動態增長數組：一種易於管理的數據結構，幾乎可以替代C++中的矢量數組。一個缺點是在運行時分配內存的開銷，但如果一次分配更大的塊，則可以緩解這一問題。
鏈接列表：小心如果你要有很多元素，因爲分別分配每個元素而不使用內存池會導致內存浪費和碎片。

來源

2011-04-08 11:54:46

動態鏈接列表被廣泛用於C中要存儲的項目數量未知的情況。

來源

2011-04-08 11:42:12

但std :: vector也是如此。 – helpermethod 2011-04-08 11:43:59

'std :: vector' in not C – pajton 2011-04-08 11:44:47

Vector是一個動態數組，並在內部實現爲動態數組。我建議你使用向量，因爲機器已經過優化以檢索連續的內存位置，而鏈接列表不會被存儲在連續的位置。

話雖如此，如果你不需要通過索引在你的用例中快速檢索元素，那麼你也可以去鏈接列表。鏈接列表還有一個好處，就是不會像動態數組那樣浪費空間（當它快要變滿時，通過加倍），並且與陣列相比，開始時或元素之間的插入更便宜。

來源

2011-04-08 11:52:05

不同的數據結構爲插入，查找和其他操作提供不同的計算複雜度。

要採取特定示例中，有一個數字的陣列，並且一個鏈接列表之間的差異：

查找由指數是在列表中的一個陣列和O(n)O(1);
插入到列表中的是O(1)或O(n)（取決於它們是否需要遍歷），並且如果做得好，則將數組分成O(1);
刪除數組是O(n)而某些類型的列表刪除可以在O(1)時間內完成;
陣列提供了更好的參考位置並因此提供了更好的緩存性能。

您可能會發現下面的頁面有用：http://essays.hexapodia.net/datastructures/

一般情況下，選擇一個數據結構時，我首先考慮自己是否有足夠的理由相信有問題的代碼，業績將是重要：

如果我不，我選擇了最簡單的數據結構，將做的工作，或者說適合於最清晰的代碼的一個;
如果我做，我會仔細考慮我要在結構上執行哪些操作，並據此進行選擇，然後進行分析。

至於良好的C數據結構庫的建議，看看Are there any open source C libraries with common data structures?

來源

2011-04-08 12:01:13 NPE

非常感謝。我發現最適合我的答案是：GLib。通常我很容易選擇正確的結構（但我並不知道GLib，而在沒有任何lib的純C中，我經常會選擇一個數組，因爲可以正確地工作，而且當前的地方不是瓶頸。 – tgmath 2011-04-08 15:09:36

你能解釋一下，如何插入數組可以是O（1）？我可以想象只有展開鏈表或類似的東西，但不是「純」數組。 – 2011-04-08 15:34:09

@SJ：關鍵詞有* amortized *。這意味着''n'插入到一個數組中可以用'O（n）'的總時間來完成，這並不意味着每個插入都是'O（1）'，例如http：// stackoverflow.com/questions/200384/constant-amortized-time – NPE 2011-04-08 15:45:02

在純C我主要使用靜態數組。它與嵌入式設備的編程相關，這些嵌入式設備在分配和釋放內存方面存在問題 - 堆碎片。

但是，如果有需要使用列表我自己實現一個 - 有時它的實現基於靜態數組（再次）。

我認爲有C庫可以提供體面實現更復雜的數據結構。 AFAIK glib廣泛使用並提供至少鏈接列表。

來源

2011-04-08 12:06:50 smbear

它完全取決於您要在數據結構上執行哪些操作。如果您將通過索引檢索數據（例如，數據[3]），那麼列表是一個可怕的想法，因爲每次閱讀都需要您閱讀清單。如果您將插入第一個位置（例如data [0] = x），那麼數組將變得很糟糕，因爲您將移動每個插入的所有數據。

如果你打算使用std :: vector，那麼動態數組可能是最好的替代品。但也許std :: vector不會是正確的選擇。

來源

2011-04-08 12:07:58

我記得我從蘋果讀取文檔前一段時間說這樣的事情可以用類似結構天真地實現：

struct { 
    void *data; //other type rather than void is easier 
    int length; 
} MyArray; 

MyArray *MyArrayCreate(){ 
    //mallocate memory 
    return ... 
} 
void MyArrayRelease(){ 
    free(...); 
}

和實施檢查數組和長度的函數沒有足夠長的時間，那麼將分配另一個足夠大的數組，之前的數據將被複制到它並添加新的數據。

MyArrayInsertAt(MyArray *array, index, void *object){ 
    if (length < index){ 
     //mallocate again, copy data 
     //update length 
    } 
    data[index] = object; 
}

因此，它可以使用像這樣：

MyArray *array = MyArrayCreate(); 
MyArrayInsertAt(array, 5, something); 
MyArrayRelease(array);

MyArrayInsertAt（）函數不會贏得一個價格它的性能，但它可能是因爲沒有高要求苛刻的程序/應用

的解決方案

我只是找不到鏈接...也許有人也讀過它？

添加：我發現GNU NSMutableArray（Objective-C）方法的實現是在C中完成的，它們與上面的一樣。每次需要添加對象時，它們都會將數組大小加倍，並且不適合數組。見行131到145

來源

2011-04-08 12:25:20 nacho4d

C中廣泛使用哪種數據結構？

回答

相關問題