C++链表基本操作

C++链表基本操作 #includeiostream,h#includestring.hstructNode{intnum;Node*next;};Node*Create()//链表创建{intn=0;Node*p1,*p2,*head;p1=p2=newNode;cinp1-num;head=NULL;while(p1-num!=0){if(n==1){head=p1;}elsep2-next=p1;p2=p1;p1=newNode;cinp1-num;n++;}p2-next=NULL;returnhead;}intListLength(NodeL)//链表的计数{Nodep=L;intcount=0;while(p-next){count++;p=p-next;}returncount;}intSearch(Node&L,intvalue)//链表的查找{Nodep=L;intindex=0;while(p){if(p-num==value)returnindex;p=p-next;index++;}return0;}voidPrint(Node*head)//输出链表{Node*p=head;while(p){coutp-num;p=p-next;}coutendl;}voidDestruct(Node*head)//清空链表{Node*current=head,*temp=NULL;while(current){temp=current;current=current-next;deletetemp;}}Node*ReverseList(Node*head)//链表逆序（循环方法）{Node*p,*q,*r;p=head;//一开始p指向第一个节点q=p-next;//q指向第二个节点while(q!=NULL)//如果没到链尾{//以第一次循环为例r=q-next;//r暂时存储第三个节点q-next=p;//没执行此句前，q-next指向第三个节点//执行之后，q-next指向第一个节点pp=q;//之后p指向第二个节点q=r;//q指向第三个节点//即...p=q=r...变为...p=q=r...}head-next=NULL;//昀后原来的链头变为链尾，把它指向NULL。head=p;//原来的链尾变成链头returnhead;}Node*ReverseList2(Node*head)//链表逆序（递归方法）{if(!head){returnNULL;}Node*temp=ReverseList2(head-next);if(!temp){returnhead;}head-next-next=head;head-next=NULL;returntemp;}递归时,head可以分别用head，head1,head2...headn-1,headn来表示总共n+1个节点temp=ReverseList2(head-next);此句的递归一直将参数传进来的。Node*head递归到headn然后判断下列语句：elseif(!headn-next){returnheadn;}将返回值传给temp,此时temp指向链尾,由于在此次返回,故此次没有执行昀后的else的那部分的语句,返回上一级即是headn-1那一级,继续执行下面的headn-1-next-next=headn-1;headn-1-next=NULL;//此两句将昀后两个逆序连接,returntemp;//之后返回temp比上一层的temp即是执行temp=ReverseList2(head-next)赋值,因为递归的口都是在这里的,如果说好理解点也可以将temp来编号同理在返回temp后,继续执行headn-2-next-next=headn-2;headn-2-next=NULL;returntemp;.....一直到head时即是原链表的第一个节点,在对其head-next=NULL后,此时以temp所指向的节点为链头的逆序链表就形成了.//已知两个链表head1和head2各自有序，请把它们合并成一个链表依然有序。（循环方法）//(保留所有结点，即便大小相同）Node*Merge(Node*head1,Node*head2){if(head1==NULL)returnhead2;if(head2==NULL)returnhead1;if(head1-num=head2-num){head=head1;head1=head1-next;}else{head=head2;head2=head2-next;}Node*temp=head;while(head1!=NULL&&head2!=NULL){if(head1-num=head2-num){temp-next=head1;head1=head1-next;temp=temp-next;}else{temp-next=head2;head2=head2-next;temp=temp-next;}}if(head1==NULL)temp-next=head2;if(head2==NULL)temp-next=head1;returnhead;}//已知两个链表head1和head2各自有序，请把它们合并成一个链表依然有序。（递归方法）Node*MergeRecursive(Node*head1,Node*head2){if(head1==NULL)returnhead2;if(head2==NULL)returnhead1;Node*head=NULL;if(head1-numhead2-num){head=head1;head-next=MergeRecursive(head1-next,head2);}else{head=head2;head-next=MergeRecursive(head1,head2-next);}returnhead;}从递归函数的定义不难看出，这个函数定义中递归调用时形参发生改变，即是当前节点的下一个节点，每一次递归都按照这个规律逐次遍历两个有序链表的每一个节点，判断大小后使head指向数据域较小的节点，由堆栈空间的思想可知递归到昀后指向NULL时才返回两个链表的某一个头节点，而此时head-next=head2，head=head1链表的昀后一个节点，该语句就使得这样一个指向关系确立起来。以上均通过理想的有序链表，即链表1的任何一个数据值都小于链表2来做分析，其他的情况讨论方式类似。Node*Delete(Node*head,intnum)//删除节点{if(head==NULL){coutListisNullendl;returnhead;}Node*p1,*p2;p1=head;while(p1-num!=num&&p1-next){p2=p1;p1=p1-next;}if(p1-num==num){if(p1==head){head=p1-next;}elsep2-next=p1-next;}elsecoutDonotFindTheNumnumendl;returnhead;}Node*Insert(Node*head,intnum)//插入节点{Node*p0,*p1,*p2;p1=head;p0=newNode;p0-num=num;if(head==NULL){head=p0;p0-next=NULL;returnhead;}while(p1-nump0-num&&p1-next){p2=p1;p1=p1-next;}if(p1-num=p0-num){if(p1==head)head=p0;elsep2-next=p0;p0-next=p1;}else{p1-next=p0;p0-next=NULL;}returnhead;}voidmain(){省略不写}双向链表原书这部分内容很多，至少相对于循环链表是很多。相信当你把单链表的指针域搞清楚后，这部分应该难不倒你。现在我的问题是，能不能从单链表派生出双向链表？你可以有几种做法：一种就是先定义一个双链节点--但是，它的名字必须叫Node，这是没办法的事；不然你就只好拷贝一份单链表的实现文件，把其中的Node全都替换成你的双链节点名字，但是这就不叫继承了。另一种做法就是先定义一种结构例如这样的：template＜classType＞classnewtype{public:Typedata;Node＜newtype＞*link;}当你派生双向链表时，这样写template＜calssType＞classDblList:publicList＜newtype＜Type＞＞，注意连续的两个＞之间要有空格。或者根本不定义这样的结构，直接拿Node类型来做，例如我下面给出的。但是，请注意要完成==的重载，否则，你又要重写Find函数，并且其他的某些操作也不方便。在开始完成你的从单链表派生出来的双向链表之前，要在单链表这个基类中添加修改当前指针和当前前驱指针的接口，如下所示：protected:voidPut(Node＜Type＞*p)//尽量不用，双向链表将使用这个完成向前移动{current=p;}voidPutPrior(Node＜Type＞*p)//尽量不用，原因同上{prior=p;}因为这个接口很危险，而且几乎用不到，所以我在前面并没有给出，但要完成双向链表昀杰出的优点--向前移动当前指针，必须要使用。另外说的是，我从前也从来没计划从单链表派生双链表，下面你将看到，这个过程很让人烦人，甚至不如重写一个来的省事，执行效率也不是很好，这种费力不讨好的事做它有什么意思呢？的确，我也觉得我在钻牛角尖。定义和实现#ifndefDblList_H#defineDblList_H#includeList.htemplate＜classType＞classDblList:publicList＜Node＜Type＞＞{public:Type*Get(){if(pGet()!=NULL)return&pGet()-＞data.data;elsereturnNULL;}Type*Next(){pNext();returnGet();}Type*Prior(){if(pGetPrior!=NULL){Put(pGetPrior());PutPrior((Node＜Node＜Type＞＞*)pGet()-＞data.link);returnGet();}returnNULL;}voidInsert(constType&value){Node＜Type＞newdata(value,(Node＜Type＞*)pGet());List＜Node＜Type＞＞::Insert(newdata);if(pGetNext()-＞link!=NULL)pGetNext()-＞link-＞data.link=(Node＜Type＞*)pGetNext();}BOOLRemove(){if(List＜Node＜Type＞＞::Remove()){pGet()-＞data.link=(Node＜Type＞*)pGetPrior();returnTURE;}returnFALSE;}};#endif【说明】只完成了昀重要的Insert和Remove函数和昀具特点的Prior()函数，其他的没有重新实现。所以，你在这里使用单链表的其他方法，我不保证一定正确。并且，这里的指针类型转换依赖于编译器实现，我也不能肯定其他的编译器编译出来也能正确。对于让不让Prior返回头节点的data，我考虑再三，反正用First();Get();这样的组合也能返回，所以就不在乎他了，所以要是用Prior遍历直到返回NULL，就会将头节点的data输出来了。