大链表查找，求解决方法

lewy7

求解决方案

结点结构
struct some_s {
int a;
int b;
void *data;
。。。(等等)
};

现在有个单向链表，有100W个结点，如何快速查找 a=18954545941 和 b=0 的结点 。
变量a在所有结点中是唯一的。


如果还有其他更合适的数据结构也可以，不一定要用链表。

cobras

a=18954545941不会被截断吗？编译器没有报警吗？

folklore

1. std::map<int,int>(a,b）;
   
2. 
   
3. 或者
   
4. struct b{
   
5. int a;
   
6. int b;
   
7. xxx;
   
8. }
   
9. 
   
10. std::map<int,shared_ptr<struct b>>(a,new b());

复制代码

cobras

如果以a排序存储，采用二分法查找会很快。不过数据结构要改改。如果用数组更快。用链表也行，不过要增加额外存储的信息。

super皮波

回复 1# lewy7
hash表


   

csumck

这必须用map+list实现啊, 网上很多哈希表都是带list功能的

Dannysd

快速排序后，二分查找
链表也可以快速排序，二级指针就够用

yulihua49

lewy7 发表于 2014-08-05 17:44
求解决方案

结点结构

二叉树，
STL的map。。。。。

long long a;

每个节点地址组成数组，排序，二分法。
hash，都可以。

二叉树省事一些。

hanxin83

Boost.MultiIndex....绝对适合你.

starwing83

回复 7# Dannysd


    亲，链表可以二分查找么？