搜索
程序员经典1双向链表的查找节点。考点：双向链表的操作出现频率：★★★★解析：使用right指针遍历，直至找到数据为data的节点，如果找到节点，返回节点，否则返回NULL。1//查找节点，成功则返回满足条件的节点指针，否则返回NULL2DbNode*FindNode(DbNode*head,intdata)//参数1是链表的表头节点3{//参数2是要查找的节点,其数据为data4DbNode*pnode=head;56if(head==NULL)//链表为空时返回NULL7{8returnNULL;9}1011/*找到数据或者到达链表末尾退出while循环*/12while(pnode-right!=NULL&&pnode-data!=data)13{14pnode=pnode-right;//使用right指针遍历15}1617//没有找到数据为data的节点，返回NULL18if(pnode-right==NULL)19{20returnNULL;21}2223returnpnode;24}2考点：模板的特化的理解出现频率：★★★解析：模板的特化（templatespecialization）分为两类：函数模板的特化和类模板的特化。（1）函数模板的特化：当函数模板需要对某些类型进行特别处理，称为函数模板的特化。例如：1boolIsEqual(Tt1,Tt2)2{3returnt1==t2;4}56intmain()7{8charstr1[]=Hello;9charstr2[]=Hello;10coutIsEqual(1,1)endl;11coutIsEqual(str1,str2)endl;//输出012return0;13}代码11行比较字符串是否相等。由于对于传入的参数是char*类型的，max函数模板只是简单的比较了传入参数的值，即两个指针是否相等，因此这里打印0。显然，这与我们的初衷不符。因此，max函数模板需要对char*类型进行特别处理，即特化：1template2boolIsEqual(char*t1,char*t2)//函数模板特化3{4returnstrcmp(t1,t2)==0;5}这样，当IsEqual函数的参数类型为char*时，就会调用IsEqual特化的版本，而不会再由函数模板实例化。（2）类模板的特化：与函数模板类似，当类模板内需要对某些类型进行特别处理时，使用类模板的特化。例如：1template2classcompare3{4public:5boolIsEqual(Tt1,Tt2)6{7returnt1==t2;8}9};1011intmain()12{13charstr1[]=Hello;14charstr2[]=Hello;15comparec1;16comparec2;17coutc1.IsEqual(1,1)endl;//比较两个int类型的参数18coutc2.IsEqual(str1,str2)endl;//比较两个char*类型的参数19return0;20}这里代码18行也是调用模板类compare的IsEqual进行两个字符串比较，显然这里存在的问题和上面函数模板中的一样，我们需要比较两个字符串的内容，而不是仅仅比较两个字符指针。因此，需要使用类模板的特化：1template2classcompare//特化(char*)3{4public:5boolIsEqual(char*t1,char*t2)6{7returnstrcmp(t1,t2)==0;//使用strcmp比较字符串8}9};注意：进行类模板的特化时，需要特化所有的成员变量及成员函数。3考点：双向链表的操作出现频率：★★★★解析：与测长的方法一样，使用right指针进行遍历。1//打印整个链表2voidPrintList(DbNode*head)//参数为链表的表头节点3{4DbNode*pnode=NULL;56if(head==NULL)//head为NULL表示链表空7{8return;9}10pnode=head;11while(pnode!=NULL)12{13printf(%d,pnode-data);14pnode=pnode-right;//使用right指针遍历15}16printf();17}4考点：类模板的实例化的理解出现频率：★★★★1template2classArray{3…4};5voidfoo()6{7Arrayarr1;8Arrayarr4,arr5;9Arrayarr2,arr3;10Arrayarr6;11…12}HowmanyinstancesofthetemplateclassArraywillgetinstantiatedinsidethefunctionfoo()A3B6C4D1解析：模板类（templateclass）的实例个数是由类型参数的种类决定的。代码7行和9行实例化的模板类都是Array，代码8行实例化的模板类是Array，代码10行实例化的模板类是Array。一共是三个实例。答案：A5考点：双向链表的操作出现频率：★★★★解析：为了得到双向链表的长度，需要使用right指针进行遍历，直到得到NULL为止。1//获取链表的长度2intGetLength(DbNode*head)//参数为链表的表头节点3{4intcount=1;5DbNode*pnode=NULL;67if(head==NULL)//head为NULL表示链表空8{9return0;10}11pnode=head-right;12while(pnode!=NULL)13{14pnode=pnode-right;//使用right指针遍历15count++;16}1718returncount;19}更多精彩内容，请到“融智技术学苑rzchina”使用模板有什么缺点？如何避免？6考点：理解模板编程的缺陷出现频率：★★★解析：templates（模板）是节省时间和避免代码重复的极好方法，我们可以只输入一个类模板，就能让编译器实例化所需要的很多个特定类及函数。类模板的成员函数只有被使用时才会被实例化，所以只有在每一个函数都在实际中被使用时，我们才会得到这些函数。确实这是一个很重要的技术，但是如果不小心，使用模板可能会导致代码膨胀。什么是代码膨胀？请看下面的例子：1template2classA3{4public:5voidwork()6{7coutwork()endl;8coutnumendl;9}10};1112intmain()13{14Av1;15Av2;16Av3;17Av4;18v1.work();19v2.work();20v3.work();21v4.work();22return0;23}类模板A取得一个类型参数T，并且它还有一个类型为int的参数，一个非类型参数（non-typeparameter），与类型参数相比，虽然非类型参数不是很通用，但他们是完全合法的。在本例中，由于num的不同，代码14到17行的调用将会生成了三个A的实例，然后在18~21行又生成了不同的函数调用。虽然这些函数做了相同的事情（打印一个“work()”和num），但他们却有不同的二进制代码。这就是所说的由于模板导致的代码膨胀。也就是说，虽然源代码看上去紧凑而整洁，但是目标代码却臃肿而松散，会严重影响程序的运行效率。如何避免由于这种代码膨胀呢？有一个原则，就是把C++模板中与参数无关的代码分离出来。也就是让与参数无关的代码只有一份拷贝。对类模板A可以进行如下地修改：1template2classBase3{4public:5voidwork(intnum)6{7coutwork;8coutnumendl;9}10};1112template13classDerived:publicBase14{15public:16voidwork()17{18Base::work(num);19}20};2122intmain()23{24Derivedd1;25Derivedd2;26Derivedd3;2728d1.work();29d2.work();30d3.work();31return0;32}程序中work的参数版本是在一个Base类（基类）中的。与Derived类一样，Base类也是一个类模板，但是与Derived类不一样的是，它参数化的仅仅是类型T，而没有num。因此，所有持有一个给定类型的Derived将共享一个单一的Base类。比如代码24~26行实例化的模板类都共享Base模板类，从而他们的成员函数都共享Base模板类中的work这个单一的拷贝。答案：模板的缺点：不当地使用模板会导致代码膨胀，即二进制代码臃肿而松散，会严重影响程序的运行效率。解决方法：把C++模板中与参数无关的代码分离出来。7如何建立一个双向链表？考点：双向链表的操作出现频率：★★★★解析：双向链表的定义如下：1typedefstructDbNode2{3intdata;//节点数据4DbNode*left;//前驱节点指针5DbNode*right;//后继节点指针6}DbNode;（1）建立双向链表：为方便，这里定义了三个函数：qCreateNode()根据数据来创建一个节点，返回新创建的节点。qCreateList()函数根据一个节点数据创建链表的表头，返回表头节点。qAppendNode()函数总在表尾插入新节点（其内部调用CreateNode()生成节点），返回表头节点。1//根据数据创建创建节点2DbNode*CreateNode(intdata)3{4DbNode*pnode=(DbNode*)malloc(sizeof(DbNode));5pnode-data=data;6pnode-left=pnode-right=pnode;//创建新节点时7//让其前驱和后继指针都指向自身8returnpnode;9}1011//创建链表12DbNode*CreateList(inthead)//参数给出表头节点数据13{//表头节点不作为存放有意义数据的节点14DbNode*pnode=(DbNode*)malloc(sizeof(DbNode));15pnode-data=head;16pnode-left=pnode-right=pnode;1718returnpnode;19}2021//插入新节点,总是在表尾插入;返回表头节点22DbNode*AppendNode(DbNode*head,intdata)//参数1是链表的表头节点，23{//参数2是要插入的节点,其数据为data24DbNode*node=CreateNode(data);//创建数据为data的新节点25DbNode*p=head,*q;2627while(p!=NULL)28{29q=p;30p=p-right;31}32q-right=node;33node-left=q;3435returnhead;36}我们可以使用其中的CreateList()和AppendNode()来生成一个链表，下面是一个数据生成从0到9含有10个节点的循环链表。1DbNode*head=CreateList(0);//生成表头，表头数据为023for(inti=1;i10;i++)4{5head=AppendNode(head,i);//添加9个节点，数据为从1到96}8考点：函数模板与类模板的基本概念和区别出现频率：★★★解析：（1）什么是函数模板和类模板。函数模板是一种抽象函数定义，它代表一类同构函数。通过用户提供的具体参数，C++编译器在编译时刻能够将函数模板实例化，根据同一个模板创建出不同的具体函数，这些函数之间的不同之处主要在于函数内部一些数据类型的不同，而由模板创建的函数的使用方法与一般函数的使用方法相同。函数模板的定义格式如