#include <stdio.h>
#include <stdlib.h>
typedef int DataType ;
typedef struct LNODE
{
DataType data;/*data数据项用于存放结点的数据值*/
struct LNODE *next; /*next数据项存放下一个结点的指针*/
} LNODE;
LNODE* initl()
{
LNODE *head;
head=(LNODE*)malloc(sizeof(LNODE)); /*为头结点申请空间*/
if(head!=NULL) /*将头结点的指针域初始化为NULL*/
head->next=NULL;
return (head);
}
LNODE* creatL1()/*建立一个头为head的带头结点的单链表*/
{
LNODE *head,*p,*s;
DataType x;
head=initl(); /*链表初始化*/
p=head;
scanf("%d",&x);
while(x!=-1)
{
s=(LNODE*)malloc(sizeof(LNODE)); /*申请新结点空间*/
s->data=x; /*给新结点的数据域赋值*/
s->next=NULL; /*将新结点的指针域初始化为空*/
p->next=s; /*将新结点链接到表尾*/
p=s; /*新结点成为新链表的尾结点*/
scanf("%d",&x);
}
return head;
}
void output(LNODE *head) /*输出节点数据*/
{
LNODE *p;
p=head->next;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
}
/*以下函数完成升序合并两上单链表*/
void Ascendingmerge(LNODE *head1,LNODE *head2)
{
LNODE *p,*q,*s;
p=head1->next;
q=head2->next;
s=(LNODE*)malloc(sizeof(LNODE));
while(p->next!=NULL&&q->next!=NULL)
{
if((p->data)>(q->data))
{
int temp;
s->data=q->data;
s->next=p->next;
p->next=s;
temp=p->data;
p->data=s->data;
s->data=temp;
q=q->next;
}
if((p->data)<=(q->data))
p=p->next;
}
if((p->data)>(q->data))
{
int temp;
s->data=q->data;
s->next=p->next;
p->next=s;
temp=p->data;
p->data=s->data;
s->data=temp;
q=q->next;
}
if((p->data)<=(q->data))
p=p->next;
if(p->next==NULL)
{
p->next=q;
}
head1=p;
}
int main()
{
LNODE *head1,*head2;
head1=creatL1();
head2=creatL1();
Ascendingmerge(head1,head2);
printf("合并后的数据为:\n");
output(head1);
return 0;
}
输入样例:
10 20 50 -1
15 25 45 60 -1
输出样例:
合并后的数据为:
10 15 20 25 45 50 60