在链表中删除相同节点

1、在链表中删除相同节点1需求分析： 依次比较两个链表元素，取出两个链表相同元素，组成一个新的链表并赋顺序指针struct Node  int number;  Node *next; Node *p，*q； ;2源代码#include "stdafx.h"   #include <iostream>   /双向循环链表的操作   using namespace std;   typedef struct&#

2、160;Dbnode    int data;      /节点数据     Dbnode *left;  /前驱结点指针     Dbnode *right; /后继节点指针   Dbnode;   void Print(Dbnode *head);      /根据

3、数据创建节点   Dbnode *CreateNode(int data)   Dbnode *pnode=new Dbnode;/       if (pnode=NULL) /如果内存申请失败，返回NULL           return NULL;       

4、       pnode->data=data;       pnode->left=pnode;/新节点的前驱和后继指针都指向自身       pnode->right=pnode;       return pnode;         /在表尾插入新节点，返回表头节

5、点   Dbnode *AppendNode(Dbnode *head,int data)       if (head=NULL)           return NULL;              Dbnode *phead=hea

6、d;       Dbnode *pnode=CreateNode(data);/创建一个新节点       while (head!=phead->right) /找到表尾              phead=phead->right;      

7、60;       pnode->right=phead->right;/右连接       head->left=pnode;       phead->right=pnode;/左连接       pnode->left=phead;       return

8、60;head;         /双向循环链表测长   int GetLength(Dbnode *head)       if (head=NULL)/如果指针为空则返回0                  return 0;   &#

9、160;          Dbnode *phead=head->right;       int i=1;       while (head!=phead)             phead=phead->right;&

10、#160;             i+;              return i;           /双向循环链表的节点查找   Dbnode *FindNode(Dbnode *head,int data)&

11、#160;      if (head=NULL)           return NULL;              if (head->data=data) /如果表头节点和值相等         

12、;  return head;              Dbnode *phead=head->right;       while (head != phead && phead->data != data)      

13、0;       phead=phead->right;                if (phead->data=data)/如果是值相等退出，则返回节点           return phead;     

14、         else  /如果没有找到，则返回NULL           return NULL;               /获得pA链表和pB链的交集，返回一个新链表   Dbnode *GetLink(Dbnode *pA,Dbnod

15、e *pB)       if (pA=NULL | pB=NULL)/如果为空，则返回NULL           return NULL;              Dbnode *pC=NULL;     

16、0; Dbnode *node=NULL;       Dbnode *phead=NULL;       /Dbnode *pheadA=pA;       int len_a=GetLength(pA);       int len_b=GetLength(pB);   &#

17、160;   int data;       for (int i=0;i<len_a;i+)                  phead=pB;              

18、;    data=pA->data;                  if (FindNode(pC,data)!=NULL)/如果data已在pC中，则进行下次循环                  

19、;     pA=pA->right;                      continue;                     &

20、#160;           if (data=pB->data)/如果pB的头节点和data相等                    node=new Dbnode;         &#

21、160;          node->data=data;                    node->left=node->right=node;            &

22、#160;          if (pC=NULL)/如果pC为空，则作为头节点                                pC=node; 

23、60;                            pC->left=pC;                    

24、0;        pC->right=pC;                       else                 

25、            pC->right->left=node;                             node->right=pC->right;

26、0;                            pC->right=node;                    &#

27、160;        node->left=pC;                                      else/如果pB的头节点

28、和data不相等                  phead=pB->right;               while (pB!=phead && phead->data != data) 

29、60;                 phead=phead->right;                              if 

30、(phead->data = data)                   node=new Dbnode;                   node->data=data; 

31、60;                 node->right=node;                   node->left=node;         

32、60;         if (pC=NULL) /如果pC为NULL                       pC=node;            &#

33、160;          pC->left=pC;                       pC->right=pC;             

34、;      else                       pC->right->left=node;                 &#

35、160;     node->right=pC->right;                       pC->right=node;               &#

36、160;       node->left=pC;                                          

37、                 pA=pA->right;              return pC;         /删除节点中所有数值等于data的节点   Dbnode *DeleteNode(Dbn

38、ode *head,int data)       if (head=NULL)/链表不存在返回NULL           return NULL;              Dbnode *node=NULL;     

39、60; Dbnode *pdelnode=NULL;       while(head->data=data) /如果头节点相等，则删除           if (head->right=head) /如果只有一个头节点，则返回NULL            

40、60;  delete head;               return NULL;                      pdelnode=head;   /保存即将删除的节点&#

41、160;          node=head->right;/保存head的下一个节点           head->right->left=head->left;           head->left->right=head->right; 

42、60;         head=node;/head的下一个节点作为头节点           delete pdelnode;/释放删除的节点           pdelnode =NULL;          &

43、#160;   Dbnode *phead=head->right;       while (head!=phead)           if (phead->data=data)               while(p

44、head->data=data)                   pdelnode=phead;                   node=phead->right; /保存phead的下一个节点 &

45、#160;                 phead->right->left=phead->left;                   phead->left->right=phead->right; &#

46、160;                 phead=node;                   delete pdelnode;          

47、60;        pdelnode=NULL;                          else           phead=phead->right;&#

48、160;             return head;         /删除链表A和链表B中所有含相同数据的节点   void DeleteEqual(Dbnode *pA,Dbnode *pB)       Dbnode *pheadA=*pA;    

49、0;  Dbnode *pheadB=*pB;       Dbnode *pheadC=NULL;       if (pA=NULL | pB=NULL) /如果指针为NULL ，返回           return      

50、60;        if (pheadA=NULL | pheadB=NULL)/如果链表为空，返回           return;              Dbnode *pC=GetLink(pheadA,pheadB);/获得公共集合  

51、;     if (pC=NULL)           return;              pheadA=DeleteNode(pheadA,pC->data);/删除pheadA和pheadB中和pC的头节点值相等的所有节点       pheadB=D

52、eleteNode(pheadB,pC->data);        pheadC=pC->right;       while (pheadC!=pC) /循环删除pheadA和pheadB中和pC的头节点值相等的所有节点           pheadA=DeleteNode(pheadA,pheadC->data);

53、0;          pheadB=DeleteNode(pheadB,pheadC->data);           pheadC=pheadC->right;                 *pA=pheadA;/把处理后的链表再分别赋给pA和pB

54、       *pB=pheadB;            /打印双向循环链表   void Print(Dbnode *head)       if (NULL=head) /head为NULL表示为空链表           getch

55、ar();           return;              cout<<head->data<<" " /先打印出表头       Dbnode *p=head->right;    

56、60;  while (head!=p) /依次遍历，直到到达表尾           cout<<p->data<<" "           p=p->right;            &

57、#160; 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);/