单链表中的二级指针.doc

先来看C语言创建链表、插入节点和遍历链表的一段代码：C代码1. #include2. #include3. 4. typedefintElemType;5. 6. typedefstructNode7. ElemTypeelem;8. structNode*next;9. Node,*LinkedList;10. 11. /voidinit_linkedlist(LinkedList*list)12. voidinit_linkedlist(LinkedList*list)13. *list=(LinkedList)malloc(sizeof(Node);14. (*list)-next=NULL;15. 16. 17. voidinsert(LinkedListlist,ElemTypeelem)18. Node*p,*q;19. q=list;20. p=(Node*)malloc(sizeof(Node);21. p-elem=elem;22. p-next=NULL;23. while(q-next!=NULL)q=q-next;24. q-next=p;25. 26. 27. voidmain()28. LinkedListlist,p;29. init_linkedlist(&list);30. insert(list,3);31. insert(list,4);32. insert(list,5);33. p=list-next;34. while(p!=NULL)35. printf(%4d,p-elem);36. p=p-next;37. 38. printf(n);39. 这个小程序完成的功能很简单，创建一个链表，然后插入3,4,5这三个整数，最后遍历链表输出每个节点中的整数。但是大家注意到没有，在main函数中，初始化链表的函数参数的是一个二级指针，为什么要使用一个二级指针作为参数呢？在任何一本C语言的教材上，都会写C语言的函数参数传递是值传递方式，所有的参数都是通过值传递的，使用指针作为参数可以在函数中改变参数的值(此处感觉表达有误，但是想不到更好的表达方式)。可能有人会有疑问了，在上面代码的main函数中初始化链表的调用函数代码Java代码1. init_linkedlist(&list);list已经是一个指针了，为什么要传递一个指针的地址，直接使用指针不行吗？确实不行。为什么？那么我们来看看不使用二级指针会发生什么情况，先来看看不使用二级指针的代码：C代码1. #include2. #include3. 4. typedefintElemType;5. 6. typedefstructNode7. ElemTypeelem;8. structNode*next;9. Node,*LinkedList;10. 11. 12. voidinit_linkedlist(Node*list)13. list=(LinkedList)malloc(sizeof(Node);14. list-next=NULL;15. 16. 17. voidinsert(LinkedListlist,ElemTypeelem)18. Node*p,*q;19. q=list;20. p=(Node*)malloc(sizeof(Node);21. p-elem=elem;22. p-next=NULL;23. while(q-next!=NULL)q=q-next;24. q-next=p;25. 26. 27. voidmain()28. LinkedListlist,p;29. printf(%dn,list);30. init_linkedlist(list);31. printf(%dn,list);32. 这段代码的main函数中有两处输出，分别是在初始化链表函数之前和之后，如果运行这段代码，会发现两处输出都是一样的值：但是如果在使用二级指针的代码(本文的第一段代码)中插入相同的两处输出代码，会发现输出的两个值是不同的：为什么会这样，原因就在于本文的第一段代码使用的是二级指针作为参数传递，而第二段代码使用的是一级指针作为参数传递。这个问题最终还是回归到了C语言参数传递是值传递了。如果是使用一级参数传递，首先是main函数中定义一个Node类型的指针，这个指针用list表示，C语言在定义指针的时候也会分配一块内存，一般会占用2个字节或4个字节，现在在大部分的编译器中占用4个字节，这里用4个字节算。在这4个字节的内存中，没有任何值，所以这个指针不指向任何值。然后传递到函数init_linkedlist中，在init_linkedlist函数中，编译器首先为形参list分配一个临时指针内存块，而语句C代码1. list=(LinkedList)malloc(sizeof(Node);中函数malloc分配一块内存，并向该程序返回一个指向这块内存的指针，这样形参list就有值了，在list所表示的临时内存区域中填入刚刚分配的内存的这块内存的地址，假设为0x10086，这样使用(*list)就可以访问这块内存（0x10086）中的内容了。此时在函数init_linkedlist中list所代表的这块内存中的内容是有值的，为0x10086，用图可表示为：但是现在的list只是占据了一个零时的内存空间，这种改变并不能反映到main函数中，init_linkedlist函数执行完了，临时的list内存块就被回收了，这样刚刚分配的内存块的地址0x10086没有被记录下来。而我们如果要初始化main函数中的链表list的话，就必须记录记录下这块内存空间(0x10086)。 下面我们来考虑使用二级指针的代码，在使用二级指针的代码(本文第一段代码)中，首先定义了一个指针C代码1. LinkedListlist然后调用init_linkedlist，调用代码是C代码1. init_linkedlist(&list);这样传递的参数就是一个指针的地址，在函数的参数列表中就表现为指针的指针，函数的定义为C代码1. voidinit_linkedlist(LinkedList*L)函数的参数是一个二级指针，同样，在执行调用这个函数的时候，临时分配一个指针，这个指针占据一个占用4个字节的内存块（函数执行完要回收的），同时这个临时指针L指向主函数main中定义的list指针，这里假设主函数main中的list指针在内存中的地址为0x12306，用图表示为其中L是一块临时内存，list是主函数main的中定义的一个指针，此时list代表的内存块中还没有内容（貌似这样说法有误，或者说这块内存还没有初始化）。下面执行内存分配的代码C代码1. *L=(LinkedList)malloc(sizeof(Node);malloc函数分配了一块内存空间，假设地址为0x10010，由于L指向list所代表的内存块，所以*L等价于list，这样将malloc函数分配的内存块赋值给*L就相当于执行语句C代码1. list=0x10010那么在list代表的内存块中所存储的值就为0x10010，用图表示为这样在函数init_linkedlist中分配的一段内存也就能在main函数中反映出来了，main函数中list代表的内存块的就指向了新分配的内存，链表初始化完成。 查看图片附件分享到：归并排序及改进|listview中设置textView使用方法etonitemcl . 2013-04-03 21:09 浏览 1420 评论(3) 分类:编程语言 相关推荐评论3 楼一袋大米2014-07-08感谢！这是我看了几个回答里最清楚的一个！2 楼andy05662013-11-20看错了，请楼主删回帖1 楼andy05662