指针和引用的区别总结

Overload(重载)：在C++程序中，可以将语义、功能相似的几个函数用同一个名字表示，但参数或返回值不同（包括类型、顺序不同），即函数重载。（1）相同的范围（在同一个类中）；（2）函数名字相同；（3）参数不同；（4）virtual关键字可有可无。Override(覆盖)：是指派生类函数覆盖基类函数，特征是：（1）不同的范围（分别位于派生类与基类）；（2）函数名字相同；（3）参数相同；（4）基类函数必须有virtual关键字。Overwrite(重写)：是指派生类的函数屏蔽了与其同名的基类函数，规则如下：（1）如果派生类的函数与基类的函数同名，但是参数不同。此时，不论有无virtual关键字，基类的函数将被隐藏（注意别与重载混淆）。（2）如果派生类的函数与基类的函数同名，并且参数也相同，但是基类函数没有virtual关键字。此时，基类的函数被隐藏（注意别与覆盖混淆）。特别注意如果基类有某个函数的多个重载（overload）版本，而你在子类中重写(overwrite)了其中的一个，或是子类添加新的函数版本，则所有基类的重载版本都被遮蔽。所以，正常情况下，在子类中应重写基类中的所有重载版本。具体地讲，继承类中的重载和重写都包含了重写的涵义，即只要函数名一样，基类的函数版本就会被遮蔽，所以，在派生类中要保持基类的重载版本，就应该重写所有基类的重载版本。重载只在当当前类中有效，继承会失去重载的特性。也就是说，把基类的重载函数放在继承类里，就必须重写。指针和引用的区别总结1.从现象上看：指针在运行时可以改变其所指向的值，而引用一旦和某个对象绑定后就不再改变2.从内存分配上看：程序为指针变量分配内存区域，而引用不分配内存区域3.从编译上看：程序在编译时分别将指针和引用添加到符号表上，符号表上记录的是变量名及变量所对应地址。指针变量在符号表上对应的地址值为指针变量的地址值，而引用在符号表上对应的地址值为引用对象的地址值。符号表生成后就不会再改，因此指针可以改变指向的对象（指针变量中的值可以改），而引用对象不能改。怎样快速检测出一个巨大的单链表中是否具备死链及其位置[e-mail]转载请注明汤姆逊的面试试题：怎么快速检测出一个巨大的单链表中是否具备死链及其位置？先给出各种链表的定义：循环链表(CircularLinkedList)是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一点出发均可找到表中其他结点。单链表是指表中的每个结点只包含一个指针域，除头结点外每个结点只有一个直接前驱，除最后一个结点外每个结点只有一个直接后继。死链：链表的某个节点的next指针指向了曾经出现过的接点或自己，导致链表死循环死链的特点是必然不存在next域为NULL的节点。如果能事先知道链表长度或是所有链表节点可以遍历一遍检查一下就行了。如果你可以知道链表的长度，那么你遍历这个链表，每经过一个节点,长度减一，当长度为0，但链表还没有遍历完时,说明存在死链。时间效率恒定，未申请新空间×××××××××××××××××××××××××××××××××××××××查找表比较如果没有任何其它信息，链表节点中又没有可以自由设置的域可以使用（如果有的话就可以设置访问标志了），可能就需要用一个查找表了。把所有访问过的节点指针放到一个查找表中，遍历链表直到next是NULL（无死链表）或是出现在查找表中（有死链）。效率是查找表的访问效率*N。比如用二分搜索树作为查找表效率就是(N*Log(N))——和排序同级由于死链可能存在于链表的任何位置，这样做就最坏的结果就是将链表遍历一遍（没有死链）有死链的话不用遍历完整个链表就可以找出来了问题在于事先不知道链表的长度，不能申请数组来保存地址啊，申请链表又要浪费大量的动态空间啊实际应用情况通常是知道链表的最大个数的，为了简单起见，tab定义为长度足够的数组，也可以建立一个链表。由于原则上链表接点的地址是没有规律的，所以依据地址表本身的其它快速（如二分等）算法似乎也不可行。void*p[MAX];以p[0]为根，p保存的是各节点next的地址，使用动态查找表中的二叉排序树的办法，建一个新的二叉排序树。如果在建树的过程中出现了相同的节点，就找到了死链书上说查找的平均效率是log(n)，又因为有n个节点，所以算法的时间复杂度应当是n*log(n)空间复杂度是n也可以利用原有的链表作为查找表，但是时间复杂度比较大，是1+2+...+n=n*(n+1)/2时间复杂度O(N^2)简要描述如下：每往下探测一次，就检查-next是否指向已经探测过的节点。每次比较时，从head开始，用head变相保存了各节点的地址，无需额外申请空间，因此空间复杂度为0，相比查表法好，时间复杂度比较高，但是还是比较安全Temp为当前检测的指针，Temp2为已经检测完了的用来与当前指针比较的节点voidcheckdeadlink(LINK*head){LINK*ptmp=head;while(ptmp!=NULL){LINK*ptmp2=head;while(!ptmp==ptmp2){if(ptmp-next=ptmp2-next){SET_DATH_LINK(true);return;}ptmp2=ptmp2-next;}ptmp=ptmp-next;}SET_DATH_LINK(false);return;}×××××××××××××××××××××××××××××××××××××××K步进插入“示踪节点”依次访问每一个节点，每访问n个节点后，插入一个特殊的“示踪”节点，以后如果在访问过程中碰到了曾经插入的示踪节点，则该链表存在死链插入示踪节点时进行计数，工作完成后，利用此计数将插入的节点删除。即使是只读，此法也不会更改其内容，而是更改next，而且工作完成后恢复。n的设置需要计算一下插入一个节点的消耗，通过next查找下一个节点的消耗，以及删除节点的消耗等等，估计了一下，应该在20到100之间比较好。不过如果链表节点比较大的时候会导致空间占用比较大。并且如果链表中有没有使用的域，我们就可以把它作为已访问标志来完成目的，不需要插入标志；如果没有这种域，如何分辨一个节点是否插入的标志节点将是关键？实际使用中还是相对容易找到示踪原子的，如果仅仅判断有没有死链，用示踪法办法应该是最好的当示踪法的N=1时，申请空间上就类似于查找表的方法。对于查找表法，如果采用N步保存地址的方式，虽然时间复杂度没有降低，但是总时间和空间都变为1/N之所以采用插入节点而不用记录节点地址，是因为将来要查找这些地址很麻烦（注意：非常大的链表），如果记录的节点数量太多，显然影响效率。而插入法进行一遍扫描，也不需要和什么值进行比较，所以时间复杂度是O（N）。而如果要记录节点查表，每个新的节点都要和你记录下的这些节点比较，即使你先排序，然后使用折半查找法，时间复杂度也是n*log(n)，当数据量非常大的时候，其时间消耗会迅速的超过插入新节点的方法。总体的比较次数就和链表长度的平方成正比了O（N^2）。因为是单链，没法回溯，因此插入法没法一次检测出死链的具体位置，只能知道“在该接点前面n个接点之内”，若在每个接点后面都插入就可以找到死链位置标志节点法需要遍历至少两遍，第一遍插入标志节点并检测死链，第二遍删除所有的标志节点。不过可以改进：再加一个线性表来保存下所有的标志节点的前继可以加快删除的速度。当确定死链第一次出现后，即可利用前继找到上一个插入节点，此时死节点就位于二者之间，再利用查表比较法，即可确定死链位置。然后利用线性表保存的前继节点就可快速的删除添加的节点恢复原有的链插入节点的步长为Setp，存放这些插入的节点的线形表为p[]如果在插入p[m]之后，碰到了曾经插入的节点p[n]，则可以断定，出问题的节点位于p[n-1]到p[n]之间，这是个常量，最多再进行2*Step*step次比较即可找到这个节点。×××××××××××××××××××××××××××××××××××××××追赶法开两个遍历链表的指针，一个一次往前走一个结点，另一个往前走两个结点，当这两个指针相遇时，则说明有死链。否则快节点已经到了末尾NULL处。关于数学上的证明：如果没有死链，两个指针是不会相遇的，除非在两头。就相当与一个人跑的快，另一个人跑的慢，如果不循环跑，两个人相遇的地点只能在起跑点。追赶法的优势在于：简单，不用进行插入节点、删除节点一类比较麻烦的操作广泛的适应性，与节点的类型无关，而示踪原子法需要依据不同的节点选择不同的示踪节点,这个比较麻烦，如果节点不能找到示踪节点怎么办？这是客观存在的。而且在实际应用中，这样可以通过只读就能解决的问题最好不要对链表写入东西。2是fastpointer的最佳步长用快慢指针，一个一次走一步，一个一次走两步，都进入死链后，快慢指针在第一圈就能相遇（因为每走一步，快指针和慢指针的距离将增加1，假设环长为L，则他们的距离将会是i,i+1,i+2,...,L-1,i取0--L-1;当距离为L-1时，下一步他们将相遇），第一次相遇后，开始记录，当第二次相遇时，记录值就是环的长度L，就是死链的长度假设死链大小是s(2n或者2n+1个)；快慢指针一个每次移动1个大小，可称之为1格，速度为v，另外一个指针每次移动2格，速度为2v。那么假设慢指针在没到s的时候就被赶上了，此时移动次数为t，可以列出等式：vt=2vt-K(s-a)其中a为循环的开始处的前一个位置的格数；那么解出t=k(s-a)/v；那么不管s或者a是2n或者2n+1，t解出来都是整数，符合开始的假设，所以现在只要找到a，一切搞定主要是确定K，还有一个条件需要加进来，就是第一次被追到时，慢指针走的距离vt肯定大于a，得出K(s-a)a，Ka/(s-a)；那么慢指针第一次被追到的时候K为大于a/(s-a)的最小整数。现在来算k，第一次快慢指针相遇的时候可以得出慢指针走了vt=K(s-a)，也就是说K(s-a)可以被算出来。那么再让快慢指针跑，那么下一次它们相遇的时候就可以求出s-a，也就是循环的一圈的长度。两个相除，就可以求出K的大小。(其实如果不关心K的大小，也可以不求K，为了完整起见，求一求也无所谓)，现在主要是求s和a，我们知道，相遇之后，慢指针的位置离开始的位置偏移了K(s-a)。那么如果慢指针再循环K次，它还是在原地，此时该慢指针走过的路程为K(s-a)；而如果在开始处再设一个慢指针，二者速度相等，当原慢指针循环K次回到原地时，此新增指针正好移动K(s-a)，也到了原来的慢指针的位置，这说明这两个指针可以相遇，而且第一次相遇的点是循环的入口(他们速度一样，所以如果在点K(s-a)处相遇，那么也在进入循环开始的时候相遇)，这样一来求到入口地址，顺便也求到了a，由于s-a一开始就被算出来了，这样也求到了s如上图，假设慢指针移动速度为单位距离1，快指针移动速度为单位2，死链入口距离为A，假设在X距离处相遇（X可由程序求出来），则慢指针必定为第一次进入S1S4区间，且快指针为第K次到S3点，S3S1=S3S0–S1S0=X–AS5S4=S5S0–S4S0=2X–S快指针到达S4后遇到死链将返回到S1处继续前移，在S3处与慢指针相遇，此时可能快指针已经在S1S4之间往返多次了，设为M次，则则2X－S－M（S－A）＝X－A》》X＝(M＋1)（S－A）死链部分长度为S－A，慢指针再移动N次后，快慢指针再次相遇必将在S3点（把S3当作环行跑道的起始点，速度相差一倍的人相遇只能是起始点，此时较慢的人正好跑了一圈），故N=S－A此时即可求出M了若M为0，说明快指针为第2次到S3点，二者相遇，则有X＝(M＋1)（S－A）＝S－A＝S1S4S3S4=S0S4–S0S3=S–X＝A＝S0S1，即慢