实现链表(线性表)

实现链表(线性表)

时间: 1ms        内存:128M

描述:

(线性表)顺序结构线性表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 

提示:

参考答案(内存最优[0]):

#include<iostream>
using namespace std;
struct line
{
    int shu;
    line *next;
};
void printfLine(line *head)
{
    while(head)
    {
        cout<<head->shu<<" ";
        head=head->next;
    }
    cout<<endl;
}
int main()
{
    line *head1,*head2,*head3;
    line *p1,*p2;
    line *q1,*q2;
    line *p;
    int i,j;
    int m,n;
    cin>>m;
    p1=p2=head1=new line;
    for(i=0;i<m;i++)
    {
        cin>>p1->shu;
        if(i!=m-1)
            p1=p1->next=new line;
        else
            p1->next=NULL;
    }
    cin>>n;
    q1=q2=head2=new line;
    for(j=0;j<n;j++)
    {
        cin>>q1->shu;
        if(j!=n-1)
            q1=q1->next=new line;
        else
            q1->next=NULL;
    }
    p1=head1;
    q1=head2;
    p1=p1->next;
    q1=q1->next;
    if(head1->shu<=head2->shu)
    {
        head3=head1;
        p2=p1;
        p1=p1->next;
        p=head3;
        p->next=NULL;
    }

    else
    {
        head3=head2;
        q2=q1;
        q1=q1->next;
        p=head3;
        p->next=NULL;
    }
    while(1)
    {
        if(p2!=NULL&&q2!=NULL)
        {
            if(p2->shu<=q2->shu)
            {
                p=p->next=p2;
                p2=p1;
                if(p1!=NULL)
                    p1=p1->next;
            }
            else
            {
                p=p->next=q2;
                q2=q1;
                if(q1!=NULL)
                    q1=q1->next;
            }
        }
        else if(p2==NULL&&q2!=NULL)
        {
            p->next=q2;
            break;
        }
        else if(p2!=NULL&&q2==NULL)
        {
            p->next=p2;
            break;
        }
    }
    p=head3;
    printfLine(p);
    return 0;
}

参考答案(时间最优[0]):

#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;
	}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注