双向链表及模板

C++中链表例子侑详细的注释)学C++的时候大家一定会对链表很难弄明白所以就给大家一个例子重点的说明了链表的用法还加了很详细的注释例子：#include<iostream>usingnamespacestd;structNode〃很多同学对这个名字很模糊，节点的英文就是Node{〃不一定非要用Node的。intdata;〃节点中的数据结构体Node的成员变量Node*next;〃指向下一节点的指针，习惯用next命名结构体Node的成员变量Node(constint&d=int())〃结构体也可以有构造函数，d=T()来指定默认值:data(d),next(NULL)〃用构造函数来初始化成员变量data和指针{}//所有数据类型，默认初始化都为0，这里data默认初始化为0};〃老师是把Node作为封装类的内包结构体，这里我给分开写一下classChain〃封装链表{private:〃数据成员通常都是private的Node*head;〃首先，我们要一个Node型的指针来保存链表的第一个节点；intlength;〃再用一个整型变量来记录当前链表内的节点数public:Chain()〃在构造函数里建立一个空链表，即head指向NULL:head(NULL),length(0){}〃节点数为0;〃这里小小插句嘴：当我们在类中定义函数时(不是声明)，相当于在前面加上一个inline修饰voiddelall()〃见名知意，这个函数用来删除链表中的所有节点{Node*pdel;〃定义一个Node型指针用来保存要删除的节点while(head!=NULL)//当head的指向不为NULL时，就是链表中还存在节点{pdel=head;〃这里备份head的当前指向节点head=head->next;〃把head的指向改变为下一节点deletepdel;//把head的原指向给删除掉}〃如此一直下去，尾节点的next肯定是指向NULL的，那删除最后一个的时候//head就被赋值为NULL，不满足循环条件，退出循环length=0;〃把节点数归零}~Chain(){delall();}〃在析构函数中调用delall函数，来完成对象销毁时清理工作〃这样一个链表必须具备的功能就实现了。下面我们来实现他的增、删、查、改功能Node*&getpoint(intposition)〃相信大家已经发现，对链表的操作，其实全部(〃通过指针来实现的，那就需要定义一个函数来返回当前节点的指针(引用)if(position<0||position>length)〃对节点编号进行合法检查position=length;//如果是非法节点编号，那么就把他修改为最后一个节点编号if(position==0)//如果编号为0，那就是第一个节点了，returnhead;〃直接返回head就是指向第一个节点的，注意返回的是head本身Node*head_bak=head;//如果编号合法并且不是第一个节点，就开始遍历链表for(int『1;i<position;i++)〃有人从QQ上问我，为什么不直接用head{〃非要定义一个head_bak，注意这里修改的是成员变量。你把head改了，以后到哪找链表〃我们都是通过head一个一个的往下找节点的。head被修改了。后果显而易见head_bak=head_bak->next;〃同过备份的指针来遍历到指定编号前一个节点}〃关于为什么i不从0开始，老师已经说过了，减少运算，提高效率returnhead_bak->next;//这里如果返回head_bak的话。那就是需要的前一个节点了}voidinsert(constint&data,intposition)//如果不修改参数的话。使用引用做{〃参数的时候，最好加上constNode*pin=newNode(data);//这个相信都能看明白吧，需要调用Node的构造函数pin->next=getpoint(position);//把指定位置的指针返回给新节点的指针〃也就是说，把新的节点的next指向原来这个位置的节点。getpoint(position)=pin;//getpoint()返回的是引用，我们可以直接修改它〃前面的一个节点的next指向我们新的节点。length++;〃链表的节点数+1}intdel(constint&data){intposition=find(data);if(position!=-1)//-1代表没找到{Node*&pnext=getpoint(position);〃用getponit()来获得指定节点的指向信息Node*pbak=pnext;〃用来备份节点的指向信息pnext=pnext->next;〃把next指向改为下下个节点。deletepbak;length--;}returnposition;}intfind(constint&data){Node*head_bak=head;

for(intposition=0;head_bak!=NULL;position++){〃对整个链表进行遍历，当next为NULL的时候证明是尾节点。遍历结束if(head_bak->data==data)returnposition;head_bak=head_bak->next;}return-1;//如果没有找到。那返回-1，做为其他函数里的判断条件}inteditor(constint&o1dd,constint&newd){intposition=find(o1dd);//调用查找函数来找到和oldd匹配的节点编号if(position!=-1)〃如果找到匹配数据，返回值就不为-1{Node*pedit=getpoint(position);pedit->data=newd;〃把原来的oldd修改为新的值}returnposition;〃修改位置返回}〃好了，大功告成，下面为了方便，我们来把<<重载，直接输出链表friendostream&operator<<(ostream&os,constChain&oc){Node*phead=oc.head;os<<"[";while(phead!=NULL)〃判断是否到尾节点{os<<phead->data<<'';phead=phead->next;}os<<”]";〃这个函数，应该没什么好说的了returnos;〃如果还是不理解，当成固定模式去背吧}};voidshow()〃菜单，这个。。。。。。不用说了{cout<<!!******************************!!<<endl;cout<<"1-查看链表内所有数据成员”<<endl;cout<<!!******************************!!<<endl;cout<<"1-查看链表内所有数据成员”<<endl;cout<<"2-向链表内添加节点(数据节点号)"<<endl;cout<<"3-删除链表内某一个数据(数据)"<<endl;cout<<"4-在链表内查找数据(数据)"<<endl;cout<<”5-修改链表内数据(旧数据，新数据)"<<endl;cout<<"0-退出”<<endl;cout<<!!******************************!!<<endl;Chainlink;intposition,data,choice,data_new;while(choice!=0){show();cout<<”请选择：”；cin>>choice;switch(choice){case1:cout<<link<<endl;break;case2:cout<<"请输入要插入的数据和插入位置："；cin>>data>>position;link.insert(data,position);cout<<link<<endl;break;case3:cout<<”请输入要删除的数据为：";cin>>data;link.del(data);cout<<link<<endl;break;case4:cout<<”请输入要查找的数据:”；cin>>data;position=link.find(data);if(position!=-1)cout<<”在:"<<position<<”找到数据"<<data<<endl;elsecout<<”没有找到数据!”<<endl;break;case5:cout<<"请输入原数据修改后数据:"；cin>>data>>data_new;link.editor(data,data_new);cout<<link<<endl;break;default:break;}}}双向链表的查找节点。考点：双向链表的操作出现频率：★★★★解析：使用right指针遍历，直至找到数据为data的节点，如果找到节点，返回节点，否则返回NULL。〃查找节点，成功则返回满足条件的节点指针，否则返回NULLDbNode*FindNode(DbNode*head,intdata)〃参数1是链表的表头节点{〃参数2是要查找的节点，其数据为dataDbNode*pnode=head;5if(head==NULL)〃链表为空时返回NULLTOC\o"1-5"\h\z{returnNULL;}10/*找到数据或者到达链表末尾退出while循环*/while(pnode->right!=NULL&&pnode->data!=data){pnode=pnode->right;//使用right指针遍历}16〃没有找到数据为data的节点，返回NULLif(pnode->right==NULL){returnNULL;}22returnpnode;}解释什么是模板的特化(templatespecialization)考点：模板的特化的理解出现频率：★★★解析：模板的特化(templatespecialization)分为两类：函数模板的特化和类模板的特化。函数模板的特化：当函数模板需要对某些类型进行特别处理，称为函数模板的特化。例如：boolIsEqual(Tt1,Tt2)TOC\o"1-5"\h\z{returnt1==t2;}5intmain(){charstr1[]="Hello";charstr2[]="Hello";cout<<IsEqual(1,1)<<endl;cout<<IsEqual(str1,str2)<<endl;〃输出0return0;}代码11行比较字符串是否相等。由于对于传入的参数是char*类型的，max函数模板只是简单的比较了传入参数的值，即两个指针是否相等，因此这里打印0。显然，这与我们的初衷不符。因此，max函数模板需要对char*类型进行特别处理，即特化：template<>boolIsEqual(char*t1,char*t2)〃函数模板特化3{4returnstrcmp(t1,t2)==0;5}这样，当IsEqual函数的参数类型为char*时，就会调用IsEqual特化的版本，而不会再由函数模板实例化。类模板的特化：与函数模板类似，当类模板内需要对某些类型进行特别处理时，使用类模板的特化。例如：template<classT>classcompare3{public:boolIsEqual(Tt1,Tt2)6{7returnt1==t2;8}9};10intmain(){charstr1[]="Hello";charstr2[]="Hello";compare<int>c1;compare<char*>c2;cout<<c1.IsEqual(1,1)<<endl;〃比较两个int类型的参数cout<<c2.IsEqual(str1,str2)<<endl;〃比较两个char*类型的参数return0;}这里代码18行也是调用模板类compare<char*>的IsEqual进行两个字符串比较，显然这里存在的问题和上面函数模板中的一样，我们需要比较两个字符串的内容，而不是仅仅比较两个字符指针。因此，需要使用类模板的特化：template<>classcompare<char*>〃特化(char*)TOC\o"1-5"\h\z{public:boolIsEqual(char*t1,char*t2){returnstrcmp(t1,t2)==0;〃使用strcmp比较字符串8}9};注意：进行类模板的特化时，需要特化所有的成员变量及成员函数双向链表的打印。更多内容请到“融智技术学苑飞HYPERLINK