由做UVa133引发的一系列问题及讨论

1.引用类型    C++ Primer P51

引用就是对象的另一个名字，使用多个变量名指向同一地址。实际程序中，引用主要用作函数形参。

复合类型。不能定义引用类型的引用，但可以定义任何其他类型的引用。

格式： 类型名&  标示符=已声明的常变量;

2.引用形参    C++ Primer P201-205

非引用形参有普通的、指针形参、const形参（可传const对象或非const对象）

引用形参，3种情形：@修改实参，或返回多个值  @避免复制大型对象  @没办法实现对象的复制 （唯一目的是避免复制时应使用更灵活的const型引用形参，因为非const型引用形参不太灵活）

3.指针形参与指向指针的引用形参

在UVa133中，定义 Node* CreateList(Node* &head, int n) ，如果不用引用形参则是 Node* CreateList(Node* head, int n) 。在main函数里是这样调用的，Node *head=NULL;
  Node *mnode=CreateList(head,n); Node *knode=head->next;

如果是按第二种定义，则在定义knode时会产生段异常，head->next是不可访问的。而是用第一种定义即引用形参时，则可以正常是用head指针、达到程序本来的目的。

这两种定义的差别就在于多了一个引用符号&，函数的实现以及实参的形式都是一样的。而第二种定义实际并没有修改实参指向的值；如果不用引用类型而非要用指针类型来实现，就得用Node** head作形参，函数实现中应该是*head=...; 

这里就产生这样结果的原因进行讨论。

我个人的理解，形参的传递就是一直值复制的过程。包括指针做形参时，只不过指针做形参时，你传递的是指针的值（即该指针所在地址的内容，即所指向的值的地址，或者说要指向的地方/地址），所以在函数中用*运算符即可达到目的。比如，在void swap(int *a,int *b)函数实现中，你通过对a进行取值*运算，就可以得到swap(c,d)的实参c所指向的值，所以可以达到交换值的目的，和void swap(int x,int y)不同。但事实上，指针a本身的地址和实参c本身的地址还是不同的。  如果使用引用形参，void swap(int* &m,int* &n)实现如下{ int *tmp=n; n=m; m=temp; } 这里直接操作的是指针，而不是像指针形参的实现中使用的取值操作符*。这里形参m和实参c本身的地址是相同的，它们是指向同一地址的多个变量名而已。所以在指针引用形参中，可以直接交换地址，这样实参那个标示符指向的位置交换了，则取值后所指向的内容自然是交换的；而在指针形参中，只能通过取值，来对两个指针所指向的值进行交换。当然，还有void swap(int &z,int &w)很好理解。  可以看到，void swap(int , int ) 和 void swap(int& , int& ) 所对应的实参是相同的，实现也是相同的，不同的是最终的实现结果。void swap(int* , int* ) 和 void swap(int* &, int* &)所对应的实参也是相同的，实现的也是相同，不同的也是最终实现的结果。然后void swap(int& , int& ) 和 void swap(int* , int* )实现的结果常常是类似的，但具体实现又有所差别（即一个取值和一个用地址的差别）

所以就可以理解了为什么不用引用形参，上面的main函数里的head看起来是没有改变的，因为head实参传递给head形参的是它指向的地址，而在CreateList函数里对head形参进行了malloc返回值的赋值，即将head指向的位置又改变了，但这影响不了实参head的。所以很多实现里把头指针直接用CreateList的返回值进行赋值来实现。而如果使用引用形参，则head形参只是head实参这个变量的地址的另一标示符，那么把形参head指向的位置改变了，由于实参head和形参head本身在同一地址上，所以实参head所指向的位置即改变。当然，也可以使用Node** 来作形参。

另外，我又加强了对指针的认识。指针就是存的一个地址，然后类型的话是说明这个地址所存的数据是怎样的类型。但你比如说声明Node *p指针时，它并没有创建Node结构体数据，它只是创建了一个指针，该指针只能用来指向Node类型数据。所以，链表中所提到的头指针其实只是声明一个这样的指针，然后指向头结点，而不是创建一个头指针结点。（也就是说UVa133实现的时候是我自己理解错了，创建了一个头指针结点。。。感觉这些东西当初学数据结构时就应该懂的，还是应该在学习后进行总结，特别是对没搞太懂的或有疑问的。注重量的学习还是不是最重要的，还是应该进行总结，注重质。我一直坚持的是对的，不能一知半解得过且过。）

4.内存泄露及free相关

@free同一块内存多次会发生不可知的错误。  参考

@一般我们常说的内存泄漏是指堆内存的泄漏。堆内存是指程序从堆中分配的，大小任意的（内存块的大小可以在程序运行期决定），使用完后必须显示释放的内存。应用程序一般使用malloc，realloc，new等函数从堆中分配到一块内存，使用完后，程序必须负责相应的调用free或delete释放该内存块，否则，这块内存就不能被再次使用，我们就说这块内存泄漏了。 

概念：简单的说就是你申请了一块内存空间，使用完毕后没有释放掉。它的一般表现方式是程序运行时间越长，占用内存越多，最终用尽全部内存，整个系统崩溃。由程序申请的一块内存，且没有任何一个指针指向它，那么这块内存就泄露了。

如 void fun(){ char *p=new char[100]; } 执行完上面的函数就发生了泄露，指针p是局部变量，函数执行完后，指针p被销毁，造成new char[100]的内存没有指针指向它，也就无法再使用，造成内存泄漏。

参考：http://bbs.csdn.net/topics/310089353