任何人都可以指定我關於不相交集作爲鏈表的一些信息?我無法找到任何代碼。 語言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. 設置活動鏈接(無ul列表)
- 3. 三路設置不相交
- 4. 將表的第一列設置爲鏈接
- 5. NavigateUri爲空時不設置超鏈接
- 6. 交換鏈接列表中的相鄰元素
- 7. OHAttributedLabel:爲URL設置鏈接
- 8. XForms:爲列表設置相關性
- 9. 超級鏈接將下拉列表設置爲可見
- 10. 交換鏈接列表中的節點
- 11. 交換鏈接列表中的節點
- 12. 鏈接列表中的交換元素
- 13. 兩個鏈接列表的交集
- 14. 將提交的表單結果顯示爲URL鏈接列表
- 15. 鏈接設置爲絕對鏈接不起作用
- 16. 相交,並設置
- 17. 鏈接列表的鏈接列表
- 18. 將鏈接列表分解爲更小的鏈接列表
- 19. 鏈接表交易
- 20. 設置相對鏈接來自文件的源,而不是域
- 21. 交換兩個鏈接列表條目
- 22. 在鏈接列表中提交C++
- 23. 將單個鏈接列表轉換爲雙鏈接列表
- 24. 嘗試將鏈接列表轉換爲循環鏈接列表
- 25. C++鏈接列表行爲
- 26. 設置爲鏈接的屬性在NIAttributedLabel
- 27. 將列表轉換爲鏈接列表
- 28. 提交表單的鏈接
- 29. 設置gridview的排序屬性爲true,但列不會變爲鏈接
- 30. 設置MySQL的交叉列表查詢
你試過std :: sets嗎? – 2009-08-07 07:31:04
什麼類型的信息?什麼是不相交集?如何用鏈表實現它們?有沒有實現它們的庫? – iain 2009-08-07 09:52:37