如何實現一套？

我想在C中實現Set。創建SET時可以使用鏈表嗎？還是應該使用其他方法？如何實現一套？

你通常如何實現自己的設置（如果需要）。

注：如果我使用鏈表的辦法，我可能會Set有如下的複雜性我的操作：

O（n * m）似乎可能有點大，特別是對於大數據...有沒有一種方法來實現我的設置更有效率？

不知道你想要達到什麼，很難提供幫助。如果你只想擁有一個像結構一樣的數組，Vector就可能是你的出路。我假設你實際上正在使用C++。 STL有大量的東西可以幫助你。 – thecoshman 2010-03-29 12:11:44

C++將其集合類作爲平衡二叉樹實現 - 這可能是一個不錯的選擇。 – 2010-03-29 12:12:25

@thecoshman由於他的問題被標記爲C，我想我們可以假設他沒有使用C++。 – 2010-03-29 12:13:30

我已經在過去使用紅黑樹來建立集合。

以下是維基百科文章的時間複雜性。

空間爲O（n）
搜索O（log n）的
插入O（log n）的
刪除O（log n）的

2010-03-29 12:18:31

你能給我一些關於O（n）複雜性的提示嗎？ – 2010-03-29 12:22:12

發佈在編輯 – 2010-03-29 12:23:03

std::set經常被實現爲一個紅黑樹：http://en.wikipedia.org/wiki/Red-black_tree

這種方法會給你列出的所有操作好得多的複雜性。

2010-03-29 12:11:27

設置執行有很多方法。 Here是其中的一些。除了MSDN還有很好的文章。

2010-03-29 12:17:22 malay

感謝您提到MSDN文章，文章非常相似。 – 2010-03-29 12:55:01

既然你已經有一個鏈表實現的，最簡單的就是一個skip list。如果你想使用平衡的樹木，我認爲最簡單的是treap。這些是隨機數據結構，但通常它們與確定性對應物一樣有效，如果不是更多（並且可以使跳過列表具有確定性）。

2010-03-29 12:25:19 IVlad

感謝您提及跳過列表（不知道它）。我可能會在另一個環境中使用它。（Multumesc！） – 2010-03-29 12:53:55

集通常被實現爲紅 - 黑樹（其需要的元素有一個總的順序），或作爲自動調整大小散列表（這需要一個散列函數）。

後者典型地由具有大小哈希表雙重並重新插入所有元素超過某一容量閾值（75％工作良好）時實現。這意味着單個插入操作可以是O（n），但是當分攤到許多操作時，它實際上是O（1）。

2010-03-29 12:25:49

回答