一道解决不了的难题（哪位仁兄可以帮助小弟啊）
链表中的难题：1,设有以单向非循环递增的线性表x和y，都采用链式存储结构，试编写算法利用原有结点空间合并x和y，且结果链表仍然保持递增有序性；2,设有一单向非循环链表X，其每个结点由一个整型数据域和一个指针域组成，整数在单链表中是无序的，写出该结点的存储结构类型定义，并编写算法，利用原结点空间，将原链表分成由奇数和偶数结点分别构成的两个链表，并要求两个链表的数据都按照递增顺序排列．
typedef struct node{ datatype data; struct node *next; }lnode,*pointer;
//pointer initlist(){ //初始化链表 //pointer l=new lnode(); //l->next=NULL; //return l; //}
pointer create_list(){ //创建链表 pointer head,p,q; datatype x; head=(pointer)malloc(sizeof(lnode)); p=head; cout<<"请从小到大输入链表的元素,输入0则结束:\n"; cin>>x; while(x!=0) { q=(pointer)malloc(sizeof(lnode)); q->data=x; p->next=q; p=q; /* cout<<"请输入下一个数:\n";*/ cin>>x; } p->next=NULL; return head; }
void print_list(pointer head){ //输出链表中的元素 pointer p; p=head->next; while(p!=NULL) { cout<<p->data<<"\t"; p=p->next; } cout<<endl; }
pointer union_list(pointer p,pointer q) { if(p->next==NULL||q->next==NULL||p==NULL||q==NULL)/*如果当中有一个链表为空.直接返回*/ return 0; pointer r1,r2,ptr;/*r1是用于链表Alist,r2是用于Blist链表的*/ ptr = p; /*我先用ptr指向其头节点*/ r1 = p->next; /*r1指向Alist表的第一个数字*/ r2 = q->next; /*r2指向Blist表的第一个数字*/ ptr->next = NULL; /*我先将Alist的表头的next置空.意思也就是断开表头和元素*/ q->next =NULL; /*Blist表也一样断开表头和元素.这个时候我已经用了 r1和r2分别指向它的第一个数字。所以不会脱链*/ while(r1 != NULL && r2 != NULL)/*开始合并链表。当2表不为空就循环*/ { if(r1->data>r2->data) /*r1的元素大过r2的元素*/ { ptr->next = r2;/*将r2接到ptr后面*/ ptr = ptr->next; /*移动ptr.也就是移到刚才r2节点那里*/ r2 = r2->next; /*r2在移后一元素*/ ptr->next = NULL;/*然后置空ptr的next*/ } else if(r1->data<r2->data)/*同理*/ { ptr->next = r1; ptr = ptr->next; r1 = r1->next; ptr->next=NULL; } else /*处理当r1->data==r2->data的时候*/ { ptr->next = r1; ptr = ptr->next; r1 = r1 ->next; r2 = r2 ->next; ptr->next = NULL; } } if(r1 != NULL)/*如果r1表后的元素还没进行合并*/ ptr->next = r1; if(r2 !=NULL)/*同上理*/ ptr->next = r2; return p; }
void main() { pointer Alist,Blist; cout<<"请输入链表A的元素:\n"; Alist=create_list(); //链表A中的元素按非递减排列 print_list(Alist); cout<<"\n请输入链表B的元素:\n"; Blist=create_list(); //链表A中的元素按非递减排列 print_list(Blist); cout<<"合并后的链表:"<<endl; Alist = union_list(Alist,Blist); print_list(Alist); cout<<endl; }
