单链表函数中的引用传递

hlt原创，转载请注明出处：c++语言中，函数参数传递一般分为两种类型：值传递和地址传递。值传递比较简单，形参定义同一般变量的形式；而实现地址传递，需要利用指针变量*或通过引用&。需要注意的是，指针传递和引用传递在实现机理上不完全相同，因此不是所有的引用传递都可以用指针传递代替。下面重点阐述和测试单链表相关操作函数：这里以严蔚敏、李冬梅教材上的相关操作的实现为例，链表为带有表头结点的情况。结点结构如下：单链表的基本操作函数有许多，这里仅仅讨论具有代表性的4个函数：===================================================StatusInitList_L(LinkList&L){//算法2.5单链表的初始化//构造一个空的单链表LL=newLNode;//生成新结点作为头结点，用头指针L指向头结点L-next=NULL;//头结点的指针域置空returnOK;}分析：该函数中，采用了引用符号&实现地址传递，&代表给传入的实参ml一个别名L，实际上两者都同一个变量；此时对L的操作相当于对ml的操作。如图1，ml开始为null，然后通过引用方式传递，给L分一个结点，相当于给ml分一个结点。图1若不加引用，采用如下形式：StatusInitList_L(LinkListL){//算法2.5单链表的初始化//构造一个空的单链表LL=newLNode;//生成新结点作为头结点，用头指针L指向头结点L-next=NULL;//头结点的指针域置空returnOK;}分析，此时L为Lnode指针类型，则通过形参，ml将null传递给了L；而后L分了新结点，但ml没有发生任何变化，仍然是null；此时对L的操作对ml没有其作用。因此，将达不到为ml分配头结点的过程，不能如此写。ml-nullL=nullml-null^Lml-null^ml（L）图2为了实现采用指针传递地址，不用引用&方式传递地址，可以采用指向指针的指针即LinkList*L作为形参（相当于Lnode**L）。此时的函数写法如下：=========================================对于创建链表函数，也存在上述情况。若函数CreateList_L(LinkList&L,intn)中的形参L不加引用符号实现地址传递，则ml将地址传给L后，在CreateList_L函数执行时，因为给L分配了新的结点，从而使得L和ml没有任何关系了，此时对L后面所加入的所有数据结点都不会反映在ml上。因此，如下函数形式中，必须采用引用传递。voidCreateList_L(LinkList&L,intn){//算法2.11后插法创建单链表//正位序输入n个元素的值，建立到头结点的单链表LLNode*r,*p;L=newLNode;L-next=NULL;//先建立一个带头结点的空链表r=L;//尾指针r指向头结点cout请输入n个数:\n;for(inti=0;in;i++){p=newLNode;//生成新结点cinp-data;//输入元素值p-next=NULL;r-next=p;//插入到表尾r=p;//r指向新的尾结点};}//CreateList_L对于上述函数，一种例外的情况时（图3），若分配头结点是在CreateList_L函数之外，这个函数仅仅负责增加数据结点，则是可以不加引用，而是通过简单的指针方式传递地址。此时，在输入数据之前，ml先通过initList函数分配了头结点。这种情况与链表的插入删除函数的参数传递同理。此时CreateList_L函数将不需要要L=newLNode;L-next=NULL;这两句。在形参中可以不加&符号，而是采用指针传递地址即可。mlLmlLab1、ml将头结点地址传给L2、利用L在头结点后面插入数据节点，此时修改L就是修改ml图3===============================================链表查找函数，由于该函数不改变L的结点情况，因此采用指针实现地址传递即可（这里不采用值传递，因为链表访问都是采用指针形式实现的）。这个也可以采用&，但是没有必要。StatusGetElem_L(LinkListL,inti,ElemType&e){//算法2.6按序号查找//在带头结点的单链表L中查找第i个元素intj;LNode*p;p=L-next;j=1;//初始化，p指向第一个结点，j为计数器while(ji&&p){//顺链域向后扫描，直到p指向第i个元素或p为空p=p-next;++j;}if(!p||ji)returnERROR;//第i个元素不存在e=p-data;//取第i个元素returnOK;}//GetElem_L==========================================================对于插入函数，形参L的结构发生变化，要将这个变化反应给实参ml，可以加&；也可以不加&。加上&相当于给ml一个别名L，对L的参数如同对ml操作一样。不加&，就是指针传递地址，将ml所指的结点地址给了L，对L的修改实际上是对ml修改。此时L和ml实际上是两个指针变量，L不在是ml的别名。StatusListInsert_L(LinkList&L,inti,ElemType&e){//算法2.8单链表的插入StatusListInsert_L(LinkListL,inti,ElemType&e){//算法2.8单链表的插入//在带头结点的单链表L中第i个位置之前插入元素eintj;LNode*p,*s;p=L;j=0;while(p&&ji-1){p=p-next;++j;}//寻找第i-1个结点if(!p||ji-1)returnERROR;//i大于表长+1或者小于1s=newLNode;//生成新结点ss-data=e;//将结点s的数据域置为es-next=p-next;//将结点s插入L中p-next=s;returnOK;}//ListInsert_L总结：1、在调用函数前ml=null，在函数中对L进行了分配新结点，而不是ml传递给L的结点；此时只有采用&或者是指向指针的指针形式。LinkList&L或LinkList*L。对应的函数有：链表初始化、创建链表。2、在函数调用前ml!=null，在函数中对链表结点进行插入和删除操作，则可以采用引用传递LinkList&L；也可以采用指针传递LinkListL，即LNode*L。mlLmlLax1、ml将头结点地址传给L2、在插入函数中操作L，相对于对ml操作abb