判断链表(线性表)

判断链表(线性表)

时间: 1ms        内存:128M

描述:

(线性表)两个整数序列A=a1,a2,a3,…,amB=b1,b2,b3,…,bn已经存入两个单链表中,设计一个算法,判断序列B是否是序列A的子序列,是则输出1,否则输出0。

输入:

输入A的长度m:6

输入A:1 2 3 4 5 6

输入B的长度n:4

输入B:1 2 3 4

输出:

1

示例输入:

5
7 8 9 12 10
4
7 9 56 10

示例输出:

0

提示:

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

#include<stdio.h>
#include<malloc.h>
#define NULL 0
#define LEN sizeof(struct date)

int t,t1;
struct date
{
	int num;
	struct date *next;
};
struct date * creat(int m)
{
	struct date *head;
	struct date *p1,*p2;
	t=0;
	p1=p2=(struct date *)malloc(LEN);
	head=NULL;
	while(m--)
	{
		scanf("%d",&p1->num);
		t++;
		if(t==1)
			head=p1;
		else
			p2->next=p1;
		p2=p1;
		p1=(struct date *)malloc(LEN);
	}
	p2->next=NULL;
	return (head);
}


void print(struct date *head)
{
	struct date *p;
	p=head;
	if(head!=NULL)
		do
		{
			printf("%d ",p->num);

			p=p->next;
		}while(p!=NULL);
	printf("\n");
}

struct date * createnulllist() 
{ 
    struct date *head; 
    head=(struct date *)malloc(sizeof(LEN)); 
    if(head!=NULL) 
		head->next=NULL;
    else
        printf("out of space!"); 
    return head; 
}

int main()
{
	struct date *p1,*p2,*p3,*p4,*p5,*p6;
	int m,n,t1=0;
	scanf("%d",&m);
	p1=creat(m);
	scanf("%d",&n);
	p2=creat(n);
	p3=createnulllist(); 
	p4=p1;
	p5=p2;
	p6=p3;
	while(p4)
	{
		while(p5)
		{
			if(p4->num==p5->num)
			{
				p6->next=p4;
				p6=p6->next;
				break;
			}
			p5=p5->next;
		}
		p5=p2;
		p4=p4->next;
	}
	p6->next=NULL;
	p3=p3->next;
	while(p3)
	{
		p3=p3->next;
		t1++;
	}
	if(m>n&&n==t1)
		printf("1\n");
	else
		printf("0\n");
	return 0;
}

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

#include<stdio.h>
#include<malloc.h>
#define NULL 0
#define LEN sizeof(struct date)

int t,t1;
struct date
{
	int num;
	struct date *next;
};
struct date * creat(int m)
{
	struct date *head;
	struct date *p1,*p2;
	t=0;
	p1=p2=(struct date *)malloc(LEN);
	head=NULL;
	while(m--)
	{
		scanf("%d",&p1->num);
		t++;
		if(t==1)
			head=p1;
		else
			p2->next=p1;
		p2=p1;
		p1=(struct date *)malloc(LEN);
	}
	p2->next=NULL;
	return (head);
}


void print(struct date *head)
{
	struct date *p;
	p=head;
	if(head!=NULL)
		do
		{
			printf("%d ",p->num);

			p=p->next;
		}while(p!=NULL);
	printf("\n");
}

struct date * createnulllist() 
{ 
    struct date *head; 
    head=(struct date *)malloc(sizeof(LEN)); 
    if(head!=NULL) 
		head->next=NULL;
    else
        printf("out of space!"); 
    return head; 
}

int main()
{
	struct date *p1,*p2,*p3,*p4,*p5,*p6;
	int m,n,t1=0;
	scanf("%d",&m);
	p1=creat(m);
	scanf("%d",&n);
	p2=creat(n);
	p3=createnulllist(); 
	p4=p1;
	p5=p2;
	p6=p3;
	while(p4)
	{
		while(p5)
		{
			if(p4->num==p5->num)
			{
				p6->next=p4;
				p6=p6->next;
				break;
			}
			p5=p5->next;
		}
		p5=p2;
		p4=p4->next;
	}
	p6->next=NULL;
	p3=p3->next;
	while(p3)
	{
		p3=p3->next;
		t1++;
	}
	if(m>n&&n==t1)
		printf("1\n");
	else
		printf("0\n");
	return 0;
}

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

点赞

发表评论

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