大链表查找，求解决方法

Dannysd

回复 10# starwing83



   当然，如果是用 struct test *next这样的链表应该是不行的，用二级指针不是可以当作二维数组那样访问嘛~  

starwing83

回复 11# Dannysd


    亲，二级指针也得链表node本身在内存里是连续的，即使链表本身的存储是连续的，在排序之后连续的元素也不一定是排序的连续元素了（因为只更改了next指针的值，并没有拷贝移动元素本身——这也是链表排序的优势），因此这时候你用二级指针直接就是作死。

一般的链表，通过malloc/free分配，你用二级指针操作除非是想crash想着急了

fender0107401

如果只有链表，那就没有好讲的了。

如果想提高查询性能，那就一定要有一个辅助的数据结构，或者干脆转化为其他的存储方式，比如hash table。

Dannysd

回复 12# starwing83


    我表达不太清楚，请大神参考一下scandir的实现（其中一个版本），如下

1. /*
   
2. * scandir, alphasort - scan a directory
   
3. *
   
4. * implementation for systems that do not have it in libc
   
5. */
   
6. 
   
7. #include "../config.h"
   
8. 
   
9. #ifndef        HAVE_SCANDIR
   
10. 
    
11. #include <sys/types.h>
    
12. #include <dirent.h>
    
13. #include <stdlib.h>
    
14. #include <stddef.h>
    
15. #include <string.h>
    
16. 
    
17. /*
    
18. * convenience helper function for scandir's |compar()| function:
    
19. * sort directory entries using strcoll(3)
    
20. */
    
21. int
    
22. alphasort(const void *_a, const void *_b)
    
23. {
    
24.     struct dirent **a = (struct dirent **)_a;
    
25.     struct dirent **b = (struct dirent **)_b;
    
26.     return strcoll((*a)->d_name, (*b)->d_name);
    
27. }
    
28. 
    
29. 
    
30. #define strverscmp(a,b) strcoll(a,b) /* for now */
    
31. 
    
32. /*
    
33. * convenience helper function for scandir's |compar()| function:
    
34. * sort directory entries using GNU |strverscmp()|
    
35. */
    
36. int
    
37. versionsort(const void *_a, const void *_b)
    
38. {
    
39.     struct dirent **a = (struct dirent **)_a;
    
40.     struct dirent **b = (struct dirent **)_b;
    
41.     return strverscmp((*a)->d_name, (*b)->d_name);
    
42. }
    
43. 
    
44. /*
    
45. * The scandir() function reads the directory dirname and builds an
    
46. * array of pointers to directory entries using malloc(3).  It returns
    
47. * the number of entries in the array.  A pointer to the array of
    
48. * directory entries is stored in the location referenced by namelist.
    
49. *
    
50. * The select parameter is a pointer to a user supplied subroutine
    
51. * which is called by scandir() to select which entries are to be
    
52. * included in the array.  The select routine is passed a pointer to
    
53. * a directory entry and should return a non-zero value if the
    
54. * directory entry is to be included in the array.  If select is null,
    
55. * then all the directory entries will be included.
    
56. *
    
57. * The compar parameter is a pointer to a user supplied subroutine
    
58. * which is passed to qsort(3) to sort the completed array.  If this
    
59. * pointer is null, the array is not sorted.
    
60. */
    
61. int
    
62. scandir(const char *dirname,
    
63.         struct dirent ***ret_namelist,
    
64.         int (*select)(const struct dirent *),
    
65.         int (*compar)(const struct dirent **, const struct dirent **))
    
66. {
    
67.     int i, len;
    
68.     int used, allocated;
    
69.     DIR *dir;
    
70.     struct dirent *ent, *ent2;
    
71.     struct dirent **namelist = NULL;
    
72. 
    
73.     if ((dir = opendir(dirname)) == NULL)
    
74.         return -1;
    
75. 
    
76.     used = 0;
    
77.     allocated = 2;
    
78.     namelist = malloc(allocated * sizeof(struct dirent *));
    
79.     if (!namelist)
    
80.         goto error;
    
81. 
    
82.     while ((ent = readdir(dir)) != NULL) {
    
83. 
    
84.         if (select != NULL && !select(ent))
    
85.             continue;
    
86. 
    
87.         /* duplicate struct direct for this entry */
    
88.         len = offsetof(struct dirent, d_name) + strlen(ent->d_name) + 1;
    
89.         if ((ent2 = malloc(len)) == NULL)
    
90.             return -1;
    
91.        
    
92.         if (used >= allocated) {
    
93.             allocated *= 2;
    
94.             namelist = realloc(namelist, allocated * sizeof(struct dirent *));
    
95.             if (!namelist)
    
96.                 goto error;
    
97.         }
    
98.         memcpy(ent2, ent, len);
    
99.         namelist[used++] = ent2;
    
100.     }
     
101.     closedir(dir);
     
102. 
     
103.     if (compar)
     
104.         qsort(namelist, used, sizeof(struct dirent *),
     
105.               (int (*)(const void *, const void *)) compar);
     
106. 
     
107.     *ret_namelist = namelist;
     
108.     return used;
     
109. 
     
110. 
     
111. error:
     
112.     if (namelist) {
     
113.         for (i = 0; i < used; i++)
     
114.             free(namelist[i]);
     
115.         free(namelist);
     
116.     }
     
117.     return -1;
     
118. }
     
119. #endif
     
120. 
     
121. 
     
122. #if        STANDALONE_MAIN
     
123. int
     
124. main(int argc, char **argv)
     
125. {
     
126.         struct dirent **namelist;
     
127.         int i, n;
     
128. 
     
129.         n = scandir("/etc", &namelist, NULL, alphasort);
     
130. 
     
131.         for (i = 0; i < n; i++)
     
132.                 printf("%s\n", namelist[i]->d_name);
     
133. }
     
134. #endif

复制代码

action08

回复 3# folklore


    map是红黑树，比left+right二叉树性能要稳定多了

sxcong

linux下经常用的list_entry是最快的。
根据地址直接查到，不管你是千万还是亿万。
libuv里有简单的例子：

#define container_of(ptr, type, member) \
  ((type *) ((char *) (ptr) - offsetof(type, member)))

struct timer_ctx* ctx = container_of(handle, struct timer_ctx, handle);

原理就是记住某个结构体里的某个变量的内存地址。自行搜索一下，http://blog.csdn.net/jiatingqiang/article/details/6437496 这里也有。
这也是为什么指针对c/c++如此重要的原因。