说透一级指针和二级指以及(void**)&在双链表中的应用

http://blog.csdn.net/unix21/article/details/8923752

2013

因为函数参数是按值传递的，所以要想改变变量，必须传递地址。

二级指针实际上就是指针变量的地址，如果传递二级指针，函数声明必须写**。

(void**)&必须是本质上就是指针变量的地址才可以做这样的转换，并不是说把一个一级指针也可以转换，void**的本质是标识一个二级指针。

&data就是(默认数据类型 **)&data，(void **)&data和&data还是同一块内存，只不过数据类型发生变化了。

如果默认数据类型是int，&data就是(int **)&data

一级指针：

[cpp] view plain copy

1. void  
2. swap ( int *a, int *b ){  
3.     int temp = 0;  
4.     temp = *a;  
5.     *a = *b;  
6.     *b = temp;   
7. }  
8.   
9. int  
10. main ( int argc, char **argv ){  
11.     int a,b;  
12.     a = 16;  
13.     b = 32;  
14.     swap(&a, &b);  
15.     return ( a - b );  
16. }  

二级指针：

[cpp] view plain copy

1. void swap(int **a, int **b)  
2. {  
3.     int t;  
4.     t =**a;  
5.     **a =**b;  
6.     **b=t;  
7. }  
8. int main()  
9. {  
10.     int i = 3;  
11.     int j = 5;  
12.     int *p = &i;  
13.     int *q = &j;  
14.     swap(&p, &q);  
15. }  

高级一点使用void**只是为了通用，可以交换各种类型。

[cpp] view plain copy

1. void swap(void **a, void **b)  
2. {  
3.     void *t;  
4.     t =*a;  
5.     *a =*b;  
6.     *b=t;  
7. }  
8. int main()  
9. {  
10.     int i = 3;  
11.     int j = 5;  
12.     int *p = &i;  
13.     int *q = &j;  
14.     char *s1="abc";  
15.     char *s2="def";  
16.     swap((void**)&p, (void**)&q);  
17.     swap((void**)&s1, (void**)&s2);  
18. }  

注意char*是字符串指针，需要改变其对应的变量必须用地址，s1就是"abc"的起始地址，是不能被改变，要想改变s1必须用他的地址也就是&s1，所以需要void**：

[cpp] view plain copy

1. void swap(void *a, void *b)  
2. {  
3.     void *t;  
4.     t =a;  
5.     a =b;  
6.     b=t;  
7. }  
8. int main()  
9. {  
10.     char *s1="abc";  
11.     char *s2="def";  
12.     swap((void*)s1, (void*)s2);  
13. }  

(void**)& 本质

在看《算法精解  C语言描述》的双链表dlist.c的代码看到这样一段

算法精解：C语言描述\examples_unix\examples\chtbl\ex-1.c

[cpp] view plain copy

1. int                *data;  
2. *data = 11;  
3. if (dlist_remove(&list, element, (void **)&data) != 0)  
4.    return 1;  

算法精解：C语言描述\examples_unix\source\dlist.c

[cpp] view plain copy

1. int dlist_remove(DList *list, DListElmt *element, void **data) {  
2.   
3. /***************************************************************************** 
4. *                                                                            * 
5. *  Do not allow a NULL element or removal from an empty list.                * 
6. *                                                                            * 
7. *****************************************************************************/  
8.   
9. if (element == NULL || dlist_size(list) == 0)  
10.    return -1;  
11.   
12. /***************************************************************************** 
13. *                                                                            * 
14. *  Remove the element from the list.                                         * 
15. *                                                                            * 
16. *****************************************************************************/  
17.   
18. *data = element->data;  
19.   
20. if (element == list->head) {  
21.   
22.    /************************************************************************** 
23.    *                                                                         * 
24.    *  Handle removal from the head of the list.                              * 
25.    *                                                                         * 
26.    **************************************************************************/  
27.   
28.    list->head = element->next;  
29.   
30.    if (list->head == NULL)  
31.       list->tail = NULL;  
32.    else  
33.       element->next->prev = NULL;  
34.   
35.    }  
36.   
37. else {  
38.   
39.    /************************************************************************** 
40.    *                                                                         * 
41.    *  Handle removal from other than the head of the list.                   * 
42.    *                                                                         * 
43.    **************************************************************************/  
44.   
45.    element->prev->next = element->next;  
46.   
47.    if (element->next == NULL)  
48.       list->tail = element->prev;  
49.    else  
50.       element->next->prev = element->prev;  
51.   
52. }  
53.   
54. /***************************************************************************** 
55. *                                                                            * 
56. *  Free the storage allocated by the abstract data type.                     * 
57. *                                                                            * 
58. *****************************************************************************/  
59.   
60. free(element);  
61.   
62. /***************************************************************************** 
63. *                                                                            * 
64. *  Adjust the size of the list to account for the removed element.           * 
65. *                                                                            * 
66. *****************************************************************************/  
67.   
68. list->size--;  
69.   
70. return 0;  
71.   
72. }  

其实很简单：

data是指针变量；

&data是data指针变量的地址所以传递他就是void**

看下面这幅调试图就明白了，起始&data就是(int **)&data，(void **)&data和&data还是同一块内存，只不过数据类型发生变化了。

注意：原书有问题就是dlist_remove之后没有free()。

相对而言，redis那种风格的删除节点更好，因为是在函数体内释放节点的，而不是外面。关于二者的比较参考：

Redis:adlist.c

[cpp] view plain copy

1. /* Remove the specified node from the specified list. 
2.  * It's up to the caller to free the private value of the node. 
3.  * 
4.  * This function can't fail. */  
5. void listDelNode(list *list, listNode *node)  
6. {  
7.     if (node->prev)  
8.         node->prev->next = node->next;  
9.     else  
10.         list->head = node->next;  
11.     if (node->next)  
12.         node->next->prev = node->prev;  
13.     else  
14.         list->tail = node->prev;  
15.     if (list->free) list->free(node->value);  
16.     zfree(node);  
17.     list->len--;  
18. }  

网上也有人遇到这个问题，人家自己写了个destroy函数，其实就是free

[cpp] view plain copy

1. /*destroy */    
2. void destroy(void *data)    
3. {    
4.     free(data);    
5.     return;    
6. }    
7.   
8. dlist_remove(&dlist_exp, p, (void **)&cb_ptr);    
9.     printf("the data of the third element: length = %d, width = %d, height = %d\n",    
10.             cb_ptr->length,    
11.             cb_ptr->width,    
12.             cb_ptr->height);    
13.     destroy(cb_ptr); //free the memory    

数据结构学习之双向链表结构  数据结构学习之单向链表结构

补充说明：

element是链表结点，这个结点里含有个数据域data,它只是个指针变量，它指向的是应用层分配的空间，
*data指向的不是element内存，而是指向element中的data域，这个域是由应用层来管理的，即当element被删除时，其element内的data域应该保存由应用层开发人员负责释放。

element是DListElmt的一个变量,变量内含有个data指针域, 接口的data域是二级指针,这两个不要混淆了.element被删除后,其data域本身所占用的资源被回收(因为是指针,占4字节),但是并不意味着data所指向的资源也被回收,这是不同的两个概念.
*data = element->data; 这句话将element内data域所指向的物理内存地址记录下来,返回给应用层处理.

《算法精解》这个哈希表的例子作者是给出了删除后要free的代码：

C语言描述\examples_unix\examples\chtbl\ex-1.c

[cpp] view plain copy

1. if ((data = (char *)malloc(sizeof(char))) == NULL)  
2.    return 1;  
3.   
4. *data = 'G';  
5.   
6. if ((retval = chtbl_insert(&htbl, data)) != 0)  
7.    free(data);  
8.   
9. fprintf(stdout, "Trying to insert G again...Value=%d (1=OK)\n", retval);  
10.   
11. fprintf(stdout, "Removing d, G, and S\n");  
12.   
13. c = 'd';  
14. data = &c;  
15.   
16. if (chtbl_remove(&htbl, (void **)&data) == 0)  
17.    free(data);  
18.   
19. c = 'G';  
20. data = &c;  
21.   
22. if (chtbl_remove(&htbl, (void **)&data) == 0)  
23.    free(data);  

其实在作者的代码结尾dlist_destroy函数也说明这一点：

算法精解：C语言描述\examples_unix\examples\chtbl\ex-1.c

[cpp] view plain copy

1. dlist_destroy(&list);  

算法精解：C语言描述\examples_unix\source\dlist.c

[cpp] view plain copy

1. void dlist_destroy(DList *list) {  
2.   
3. void               *data;  
4.   
5. /***************************************************************************** 
6. *                                                                            * 
7. *  Remove each element.                                                      * 
8. *                                                                            * 
9. *****************************************************************************/  
10.   
11. while (dlist_size(list) > 0) {  
12.   
13.    if (dlist_remove(list, dlist_tail(list), (void **)&data) == 0 && list->  
14.       destroy != NULL) {  
15.   
16.       /*********************************************************************** 
17.       *                                                                      * 
18.       *  Call a user-defined function to free dynamically allocated data.    * 
19.       *                                                                      * 
20.       ***********************************************************************/  
21.   
22.       list->destroy(data);  
23.   
24.    }  
25.   
26. }  

这里是调用了list->destroy的。