在鏈表中刪除相同節(jié)點(diǎn)

1、在鏈表中刪除相同節(jié)點(diǎn)1需求分析： 依次比較兩個(gè)鏈表元素，取出兩個(gè)鏈表相同元素，組成一個(gè)新的鏈表并賦順序指針struct Node  int number;  Node *next; Node *p，*q； ;2源代碼#include "stdafx.h"   #include <iostream>   /雙向循環(huán)鏈表的操作   using namespace std;   typedef struct&#

2、160;Dbnode    int data;      /節(jié)點(diǎn)數(shù)據(jù)     Dbnode *left;  /前驅(qū)結(jié)點(diǎn)指針     Dbnode *right; /后繼節(jié)點(diǎn)指針   Dbnode;   void Print(Dbnode *head);      /根據(jù)

3、數(shù)據(jù)創(chuàng)建節(jié)點(diǎn)   Dbnode *CreateNode(int data)   Dbnode *pnode=new Dbnode;/       if (pnode=NULL) /如果內(nèi)存申請(qǐng)失敗，返回NULL           return NULL;       

4、       pnode->data=data;       pnode->left=pnode;/新節(jié)點(diǎn)的前驅(qū)和后繼指針都指向自身       pnode->right=pnode;       return pnode;         /在表尾插入新節(jié)點(diǎn)，返回表頭節(jié)

5、點(diǎn)   Dbnode *AppendNode(Dbnode *head,int data)       if (head=NULL)           return NULL;              Dbnode *phead=hea

6、d;       Dbnode *pnode=CreateNode(data);/創(chuàng)建一個(gè)新節(jié)點(diǎn)       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;         /雙向循環(huán)鏈表測(cè)長(zhǎng)   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;           /雙向循環(huán)鏈表的節(jié)點(diǎn)查找   Dbnode *FindNode(Dbnode *head,int data)&

11、#160;      if (head=NULL)           return NULL;              if (head->data=data) /如果表頭節(jié)點(diǎn)和值相等         

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

13、0;       phead=phead->right;                if (phead->data=data)/如果是值相等退出，則返回節(jié)點(diǎn)           return phead;     

14、         else  /如果沒(méi)有找到，則返回NULL           return NULL;               /獲得pA鏈表和pB鏈的交集，返回一個(gè)新鏈表   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中，則進(jìn)行下次循環(huán)                  

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

20、#160;           if (data=pB->data)/如果pB的頭節(jié)點(diǎn)和data相等                    node=new Dbnode;         &#

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

22、#160;          if (pC=NULL)/如果pC為空，則作為頭節(jié)點(diǎn)                                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的頭節(jié)點(diǎn)

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;         /刪除節(jié)點(diǎn)中所有數(shù)值等于data的節(jié)點(diǎn)   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) /如果頭節(jié)點(diǎn)相等，則刪除           if (head->right=head) /如果只有一個(gè)頭節(jié)點(diǎn)，則返回NULL            

40、60;  delete head;               return NULL;                      pdelnode=head;   /保存即將刪除的節(jié)點(diǎn)&#

41、160;          node=head->right;/保存head的下一個(gè)節(jié)點(diǎn)           head->right->left=head->left;           head->left->right=head->right; 

42、60;         head=node;/head的下一個(gè)節(jié)點(diǎn)作為頭節(jié)點(diǎn)           delete pdelnode;/釋放刪除的節(jié)點(diǎn)           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的下一個(gè)節(jié)點(diǎn) &

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中所有含相同數(shù)據(jù)的節(jié)點(diǎn)   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的頭節(jié)點(diǎn)值相等的所有節(jié)點(diǎn)       pheadB=D

52、eleteNode(pheadB,pC->data);        pheadC=pC->right;       while (pheadC!=pC) /循環(huán)刪除pheadA和pheadB中和pC的頭節(jié)點(diǎn)值相等的所有節(jié)點(diǎn)           pheadA=DeleteNode(pheadA,pheadC->data);

53、0;          pheadB=DeleteNode(pheadB,pheadC->data);           pheadC=pheadC->right;                 *pA=pheadA;/把處理后的鏈表再分別賦給pA和pB

54、       *pB=pheadB;            /打印雙向循環(huán)鏈表   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) /依次遍歷，直到到達(dá)表尾           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);/