题目描述
(线性表)顺序结构线性表LA与LB的结点关键字为整数。LA与LB的元素按非递减有序,线性表空间足够大。试用给出一种高效算法,将LB中元素合到LA中,使新的LA的元素仍保持非递减有序。高效指最大限度的避免移动元素。
输入
输入LA长度m:7
输入数据:3 7 11 15 57 68 99
输入LB长度n:7
输入数据:6 7 8 9 10 23 67
输出
3 6 7 8 9 10 11 15 23 57 67 68 99
样例输入
7
4 6 7 9 10 16 23
8
1 2 4 7 8 13 15 44
样例输出
1 2 4 6 7 8 9 10 13 15 16 23 44
参考代码
#include"stdio.h"
#include"stdlib.h"
typedef struct node
{
int data;
struct node *next;
}
node;
node *create(node *head)
{
int i,len;
node *p1=0,*p2=0;
scanf("%d",&len);
for (i=0;i<len;i++)
{
p1=(node*)malloc(sizeof(node));
scanf("%d",&p1->data);
if(i==0)
head=p1; else
p2->next=p1;
p2=p1;
}
p1->next=0;
return head;
}
node *Union(node *head1,node *head2)
{
node *head=0,*p;
if(head1->data<head2->data)
{
head=head1;
head1=head1->next;
} else
{
head=head2;
head2=head->next;
}
p=head;
while(head1!=0&&head2!=0)
{
if(head1->data==head2->data)
{
head->next=head1;
head1=head1->next;
head2=head2->next;
head=head->next;
continue;
}
if(head1->data<head2->data)
{
head->next=head1;
head1=head1->next;
head=head->next;
} else
{
head->next=head2;
head2=head2->next;
head=head->next;
}
}
if(head1==0)
head->next=head2; else
head->next=head1;
return p;
}
int main()
{
node *head1,*head2,*head;
head1=create(head1);
head2=create(head2);
head=Union(head1,head2);
printf("%d",head->data);
head=head->next;
while(head!=0)
{
printf(" %d",head->data);
head=head->next;
}
return 0;
}
解析
暂无