任何人都可以指定我關於不相交集作爲鏈表的一些信息?我無法找到任何代碼。 語言C++不相交的設置爲鏈接列表
2
A
回答
1
嗯,我想你可以在這個頁面找到信息Wikipedia。當然,這些信息是用僞代碼編寫的,但並不難翻譯它。
2
Boost有一個實現:http://www.boost.org/doc/libs/1_39_0/libs/disjoint_sets/disjoint_sets.html。 猜猜這是你在找什麼。
5
我剛寫了這個,如果有人還有興趣的話。我正在實施CLRS Chap 21.1
/******************************************************************
* PROGRAM: Implementation of Linked-list representation of disjoi-*
* nted sets in C++ without weighted union optimization. *
* makeset, find takes O(1), Union takes O(n). Testing *
* code is in the main method. *
* AUTHOR: Bo Tian (bt288 at cam.ac.uk) drop me an email if you *
* have any questions. *
* LICENSE: Creative Commons Attribution 3.0 Unported *
* http://creativecommons.org/licenses/by/3.0/ *
*******************************************************************/
#include <iostream>
using namespace std;
long NodeAddress[10] = {0};
int n=0;
template<class T> class ListSet {
private:
struct Item;
struct node {
T val;
node *next;
Item *itemPtr;
};
struct Item {
node *hd, *tl;
};
public:
ListSet() { }
long makeset(T a);
long find (long a);
void Union (long s1, long s2);
};
template<class T> long ListSet<T>::makeset (T a) {
Item *newSet = new Item;
newSet->hd = new node;
newSet->tl = newSet->hd;
node *shd = newSet->hd;
NodeAddress[n++] = (long) shd;
shd->val = a;
shd->itemPtr = newSet;
shd->next = 0;
return (long) newSet;
}
template<class T> long ListSet<T>::find (long a) {
node *ptr = (node*)a;
return (long)(ptr->itemPtr);
}
template<class T> void ListSet<T>::Union (long s1, long s2) {
//change head pointers in Set s2
Item *set2 = (Item*) s2;
node *cur = set2->hd;
Item *set1 = (Item*) s1;
while (cur != 0) {
cur->itemPtr = set1;
cur = cur->next;
}
//join the tail of the set to head of the input set
(set1->tl)->next = set2->hd;
set1->tl = set2->tl;
delete set2;
}
int main() {
ListSet<char> a;
long s1, s2, s3, s4;
s1 = a.makeset('a');
s2 = a.makeset('b');
s3 = a.makeset('c');
s4 = a.makeset('d');
cout<<s1<<' '<<s2<<' '<<s3<<' '<<s4<<endl;
cout<<a.find(NodeAddress[2])<<endl;
a.Union(s1, s3);
cout<<a.find(NodeAddress[2])<<endl;
}
相關問題
- 1. 三路設置不相交
- 2. 將表的第一列設置爲鏈接
- 3. NavigateUri爲空時不設置超鏈接
- 4. XForms:爲列表設置相關性
- 5. 超級鏈接將下拉列表設置爲可見
- 6. 鏈接列表中的交換元素
- 7. 交換鏈接列表中的節點
- 8. 兩個鏈接列表的交集
- 9. 將提交的表單結果顯示爲URL鏈接列表
- 10. 鏈接設置爲絕對鏈接不起作用
- 11. 將鏈接列表分解爲更小的鏈接列表
- 12. 將單個鏈接列表轉換爲雙鏈接列表
- 13. 嘗試將鏈接列表轉換爲循環鏈接列表
- 14. C++鏈接列表行爲
- 15. yql鏈接列表爲html
- 16. 將列表轉換爲鏈接列表
- 17. 設置gridview的排序屬性爲true,但列不會變爲鏈接
- 18. 設置MySQL的交叉列表查詢
- 19. Pascal鏈接列表鏈接列表不起作用
- 20. 爲什麼使用相同的IDXGIFactory爲設備和交換鏈
- 21. 鏈接樣式沒有爲CSS中的所有鏈接設置
- 22. 爲相同鏈接的不同部分設計
- 23. 鏈接列表...不更改
- 24. 鏈接器設置
- 25. 使用樹中的元素初始化鏈接列表設置
- 26. 設置用戶和鏈接表
- 27. 鏈接列表
- 28. 鏈接列表
- 29. 爲Mod設置mod_rewrite下載鏈接
- 30. 將鏈接設置爲固定活動
你試過std :: sets嗎? – 2009-08-07 07:31:04
什麼類型的信息?什麼是不相交集?如何用鏈表實現它們?有沒有實現它們的庫? – iain 2009-08-07 09:52:37