删除两个双向循环链表的相同节点

分类： Data Structure 面试题集 2011-09-23 12:37 1242人阅读评论(1) 收藏举报

 
 null
 delete
 struct
 system
 c

有两个双向循环链表A，B，知道其头指针为：pHeadA，pHeadB，请写一个函数将两链表中数值相同的节点删除。

分析：

（1）首先把A中含有与B中相同的数据节点找出来组成一个新的链表，例如：

链表A：1 2 3 4 2 6 4

链表B：10 20 3 4 2 10

新链表C：2 3 4

（2）遍历链表C，删除A和B的所有和C中节点值相同的节点。

[cpp] 
    view plain
    copy 
     
    
 #include "stdafx.h"  
 #include <iostream>  
 //双向循环链表的操作  
 using namespace std;  
 typedef struct Dbnode{  
     int data;      //节点数据  
     Dbnode *left;  //前驱结点指针  
     Dbnode *right; //后继节点指针  
 }Dbnode;  
 void Print(Dbnode *head);  
   
 //根据数据创建节点  
 Dbnode *CreateNode(int data){  
     Dbnode *pnode=new Dbnode;//  
     if (pnode==NULL){ //如果内存申请失败，返回NULL  
         return NULL;  
     }  
     pnode->data=data;  
     pnode->left=pnode;//新节点的前驱和后继指针都指向自身  
     pnode->right=pnode;  
     return pnode;  
 }  
   
 //在表尾插入新节点，返回表头节点  
 Dbnode *AppendNode(Dbnode *head,int data){  
     if (head==NULL){  
         return NULL;  
     }  
     Dbnode *phead=head;  
     Dbnode *pnode=CreateNode(data);//创建一个新节点  
     while (head!=phead->right){ //找到表尾  
            phead=phead->right;  
     }  
     pnode->right=phead->right;//右连接  
     head->left=pnode;  
     phead->right=pnode;//左连接  
     pnode->left=phead;  
     return head;  
 }  
   
 //双向循环链表测长  
 int GetLength(Dbnode *head){  
     if (head==NULL)//如果指针为空则返回0  
     {  
         return 0;  
     }  
     Dbnode *phead=head->right;  
     int i=1;  
     while (head!=phead){  
           phead=phead->right;  
            i++;  
     }  
     return i;  
 }  
   
   
 //双向循环链表的节点查找  
 Dbnode *FindNode(Dbnode *head,int data){  
     if (head==NULL){  
         return NULL;  
     }  
     if (head->data==data){ //如果表头节点和值相等  
         return head;  
     }  
     Dbnode *phead=head->right;  
     while (head != phead && phead->data != data){  
            phead=phead->right;  
       }  
     if (phead->data==data){//如果是值相等退出，则返回节点  
         return phead;  
     }  
     else  //如果没有找到，则返回NULL  
         return NULL;  
 }  
   
   
   
 //获得pA链表和pB链的交集，返回一个新链表  
 Dbnode *GetLink(Dbnode *pA,Dbnode *pB){  
     if (pA==NULL || pB==NULL){//如果为空，则返回NULL  
         return NULL;  
     }  
     Dbnode *pC=NULL;  
     Dbnode *node=NULL;  
     Dbnode *phead=NULL;  
     //Dbnode *pheadA=pA;  
     int len_a=GetLength(pA);  
     int len_b=GetLength(pB);  
     int data;  
     for (int i=0;i<len_a;i++){  
                phead=pB;  
                data=pA->data;  
                if (FindNode(pC,data)!=NULL){//如果data已在pC中，则进行下次循环  
                     pA=pA->right;  
                    continue;  
                }  
             if (data==pB->data){//如果pB的头节点和data相等  
                  node=new Dbnode;  
                  node->data=data;  
                  node->left=node->right=node;  
                     if (pC==NULL){//如果pC为空，则作为头节点  
                              pC=node;  
                            pC->left=pC;  
                           pC->right=pC;  
                     }else{  
                           pC->right->left=node;  
                           node->right=pC->right;  
                           pC->right=node;  
                           node->left=pC;  
                         }  
         }else{//如果pB的头节点和data不相等  
                phead=pB->right;  
             while (pB!=phead && phead->data != data){  
                 phead=phead->right;  
             }  
             if (phead->data == data){  
                 node=new Dbnode;  
                 node->data=data;  
                 node->right=node;  
                 node->left=node;  
                 if (pC==NULL){ //如果pC为NULL  
                     pC=node;  
                     pC->left=pC;  
                     pC->right=pC;  
                 }else{  
                     pC->right->left=node;  
                     node->right=pC->right;  
                     pC->right=node;  
                     node->left=pC;  
                 }  
             }  
         }  
            pA=pA->right;  
     }  
     return pC;  
 }  
   
 //删除节点中所有数值等于data的节点  
 Dbnode *DeleteNode(Dbnode *head,int data){  
     if (head==NULL){//链表不存在返回NULL  
         return NULL;  
     }  
     Dbnode *node=NULL;  
     Dbnode *pdelnode=NULL;  
     while(head->data==data){ //如果头节点相等，则删除  
         if (head->right==head){ //如果只有一个头节点，则返回NULL  
             delete head;  
             return NULL;  
         }  
         pdelnode=head;   //保存即将删除的节点  
         node=head->right;//保存head的下一个节点  
         head->right->left=head->left;  
         head->left->right=head->right;  
         head=node;//head的下一个节点作为头节点  
         delete pdelnode;//释放删除的节点  
         pdelnode =NULL;  
     }  
     Dbnode *phead=head->right;  
     while (head!=phead){  
         if (phead->data==data){  
             while(phead->data==data){  
                 pdelnode=phead;  
                 node=phead->right; //保存phead的下一个节点  
                 phead->right->left=phead->left;  
                 phead->left->right=phead->right;  
                 phead=node;  
                 delete pdelnode;  
                 pdelnode=NULL;  
             }  
         }else  
         phead=phead->right;  
     }  
     return head;  
 }  
   
 //删除链表A和链表B中所有含相同数据的节点  
 void DeleteEqual(Dbnode **pA,Dbnode **pB){  
     Dbnode *pheadA=*pA;  
     Dbnode *pheadB=*pB;  
     Dbnode *pheadC=NULL;  
     if (pA==NULL || pB==NULL){ //如果指针为NULL ，返回  
         return ;  
     }  
     if (pheadA==NULL || pheadB==NULL){//如果链表为空，返回  
         return;  
     }  
     Dbnode *pC=GetLink(pheadA,pheadB);//获得公共集合  
     if (pC==NULL){  
         return;  
     }  
     pheadA=DeleteNode(pheadA,pC->data);//删除pheadA和pheadB中和pC的头节点值相等的所有节点  
     pheadB=DeleteNode(pheadB,pC->data);  
      pheadC=pC->right;  
     while (pheadC!=pC){ //循环删除pheadA和pheadB中和pC的头节点值相等的所有节点  
         pheadA=DeleteNode(pheadA,pheadC->data);  
         pheadB=DeleteNode(pheadB,pheadC->data);  
         pheadC=pheadC->right;  
     }  
   
     *pA=pheadA;//把处理后的链表再分别赋给pA和pB  
     *pB=pheadB;  
 }  
   
   
 //打印双向循环链表  
 void Print(Dbnode *head){  
     if (NULL==head){ //head为NULL表示为空链表  
         getchar();  
         return;  
     }  
     cout<<head->data<<" "; //先打印出表头  
     Dbnode *p=head->right;  
     while (head!=p){ //依次遍历，直到到达表尾  
         cout<<p->data<<" ";  
         p=p->right;  
     }  
     cout<<endl;  
 }  
 int _tmain(int argc, _TCHAR* argv[])  
 {  
     Dbnode *pA=NULL;  
     Dbnode *pB=NULL;  
     Dbnode *pC=NULL;  
     Dbnode *pheadC=pC;  
     Dbnode *pfind=NULL;  
     Dbnode *pNhead=NULL;  
     Dbnode *pList=NULL;  
     pA=CreateNode(0);//创建表头节点，表头节点不作为存放有意义数据的节点  
     for (int i=1;i<10;i++){  
         AppendNode(pA,i);  
     }  
     AppendNode(pA,9);  
     AppendNode(pA,20);  
     cout<<"pA:";  
     Print(pA);  
     pB=CreateNode(0);  
     AppendNode(pB,3);  
     AppendNode(pB,2);  
     AppendNode(pB,6);  
     AppendNode(pB,9);  
     AppendNode(pB,9);  
     AppendNode(pB,15);  
     AppendNode(pB,20);  
     AppendNode(pB,20);  
     cout<<"pB:";  
     Print(pB);  
     pC=GetLink(pA,pB);  
     cout<<"Subset pA and pB:";  
     Print(pC);  
   
     DeleteEqual(&pA,&pB);  
     cout<<"After DeleteEqual pA:";  
     Print(pA);  
     cout<<" After DeleteEqual pB:";  
     Print(pB);  
    system("pause");  
     delete [] pA;  
     delete [] pB;  
     delete [] pC;  
     return 0;  
 }  