合并单链表
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
currentPtr=&heada;
while(currentPtr->next_!=NULL){
coutvalue_";
currentPtr=currentPtr->next_;
}
coutvalue_
cout
currentPtr=&headb;
while(currentPtr->next_!=NULL){
coutvalue_";
currentPtr=currentPtr->next_;
}
coutvalue_
cout
currentPtr=set_union(&heada,&headb); //题目中函数的运用；
while(currentPtr->next_!=NULL){
coutvalue_";
currentPtr=currentPtr->next_;
}
coutvalue_
return 0;
}
/****************************************************************************/
/*==================================================================*/
/****************************************************************************/