2207: 实现链表(线性表)

题目描述

（线性表）顺序结构线性表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;
}

解析

暂无