剑网三秀姐cos:合并单链表

3.完成下面算法，它将两个有序单链表看做集合，求其并集。

Node* set_union(Node* a,Node* b);

函数返回表示并集合的单链表第一个节点指针。注意，并集中不存在相同元素。函数返回后，链表啊，a，b消失。

/*****************************************************************************/

/*==================================================================*/

/*****************************************************************************/

#include

using namespace std;

#define SIZE1 7

#define SIZE2 8                                    //两个链表的长度；

struct Node{

       double value_;

       Node *next_;

};

//已注释

/*****************************************************************************

Node* set_union(Node* a,Node* b)                  //题目中要设计的函数(无序)；

{

       int same=0;

       Node* currentPtr,*endPtr;

       currentPtr=a;

       endPtr=a;

       while(endPtr->next_!=NULL){

              endPtr=endPtr->next_;

       }

       while(b!=NULL){

              while(currentPtr!=NULL){

                     if(b->value_==currentPtr->value_) { same=1; }

                     currentPtr=currentPtr->next_;

              }

              currentPtr=a;

              if(same==0){

                     endPtr->next_=b;

              }

              same=0;

              b=b->next_;

       }

       return a;

}

*****************************************************************************/

Node* set_union(Node* a,Node* b)                   //题目中要设计的函数，适用升序；

{

       Node *previousPtr,*currentPtr;

       currentPtr=a;

       previousPtr=NULL;

    while(currentPtr!=NULL){

              if(b->value_value_){         //满足该条件，将b中该节点插入a表；             

                     if(previousPtr==NULL){                //插入最前节点的处理；

                            a=b;

                         b=b->next_;

                            previousPtr=a;

                         a->next_=currentPtr;

                     }

                     else{                                 //插入非头结点的处理；

                         previousPtr->next_=b;

                         b=b->next_;   

                            previousPtr=previousPtr->next_;

                         previousPtr->next_=currentPtr;

                     }

              }

              else if(b->value_==currentPtr->value_){   //两者相等时，a表，b表同时推进；

                   b=b->next_;

                  previousPtr=currentPtr;

                   currentPtr=currentPtr->next_;

              }

              else if(b->value_>currentPtr->value_){    //满足该条件时，推进a表；

                  previousPtr=currentPtr;

                   currentPtr=currentPtr->next_;

              }

       }

       if(b!=NULL){                                  //当a表遍历完而b表还没，则将b表接到a表后；

              previousPtr->next_=b;

       }

       return a;

}

int main()

{

    Node heada,headb,a[SIZE1],b[SIZE2],*currentPtr;    //开始创建链表；

       int x[SIZE1]={0,2,3,4,6,8,9};

       int y[SIZE2]={0,3,4,5,7,10,13,15};                 //用来初始化链表的数组；

    a[0].value_=x[0];

       a[0].next_=NULL;

       b[0].value_=y[0];

       b[0].next_=NULL;

       for(int i=1;i

              a[i].value_=x[i];

              a[i-1].next_=&(a[i]);

       }

       a[i-1].next_=NULL;

       heada=a[0];

       for(int j=1;j

              b[j].value_=y[j];

              b[j-1].next_=&(b[j]);

       }

       b[j-1].next_=NULL;

       headb=b[0];                                        //创建链表完毕；

    cout<<"默认链表a为："<

       currentPtr=&heada;                         

       while(currentPtr->next_!=NULL){

              cout<value_<<"->";

              currentPtr=currentPtr->next_;

       }

       cout<value_<

    cout<<"默认链表b为："<

       currentPtr=&headb;                         

       while(currentPtr->next_!=NULL){

              cout<value_<<"->";

              currentPtr=currentPtr->next_;

       }

       cout<value_<

    cout<<"合并后链表c为："<

       currentPtr=set_union(&heada,&headb);               //题目中函数的运用；                        

       while(currentPtr->next_!=NULL){

              cout<value_<<"->";

              currentPtr=currentPtr->next_;

       }

       cout<value_<

       return 0;

/****************************************************************************/

/*==================================================================*/

/****************************************************************************/