|
3.完成下面算法，它将两个有序单链表看做集合，求其并集。 Node* set_union(Node* a,Node* b); 函数返回表示并集合的单链表第一个节点指针。注意，并集中不存在相同元素。函数返回后，链表啊，a，b消失。 /*****************************************************************************/ /*==================================================================*/ /*****************************************************************************/ #include<iostream> 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_<currentPtr->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<SIZE1;i++){ //赋值链表heada； a[i].value_=x[i]; a[i-1].next_=&(a[i]); } a[i-1].next_=NULL; heada=a[0]; for(int j=1;j<SIZE2;j++){ //赋值链表headb； b[j].value_=y[j]; b[j-1].next_=&(b[j]); } b[j-1].next_=NULL; headb=b[0]; //创建链表完毕； cout<<"默认链表a为："<<endl; //开始输出链表heada； currentPtr=&heada; while(currentPtr->next_!=NULL){ cout<<currentPtr->value_<<"->"; currentPtr=currentPtr->next_; } cout<<currentPtr->value_<<endl<<endl; cout<<"默认链表b为："<<endl; //开始输出链表headb； currentPtr=&headb; while(currentPtr->next_!=NULL){ cout<<currentPtr->value_<<"->"; currentPtr=currentPtr->next_; } cout<<currentPtr->value_<<endl<<endl; cout<<"合并后链表c为："<<endl; //开始输出合并后链表； currentPtr=set_union(&heada,&headb); //题目中函数的运用； while(currentPtr->next_!=NULL){ cout<<currentPtr->value_<<"->"; currentPtr=currentPtr->next_; } cout<<currentPtr->value_<<endl<<endl; return 0; }
 /****************************************************************************/ /*==================================================================*/ /****************************************************************************/ |
|
|
