博客

题目描述：

已知两个由正整数组成的无序序列A、B，每个序列的元素个数未知，但至少有一个元素。你的任务是判断序列B是否是序列A的连续子序列。假设B是“1 9 2 4 18”，A是“33 64 1 9 2 4 18 7”，B是A的连续子序列；假设B是“1 9 2 4 18”，A是“33 1 9 64 2 4 18 7”，B不是A的连续子序列。

要求：

建立两个单链表A、B用于存储两个正整数序列，然后按照题目的要求，判断链表B是否是链表A的连续子序列。正整数的输入用-1作为结束标志，注意-1不算这个正整数序列中的元素（不要统计-1）。在程序结束前要释放链表A、B中的所有节点

输入：

依次输入两个乱序的正整数序列A、B，序列中元素个数未知，但每个序列至少有一个元素，并以输入“-1”结束，每个序列占一行。

输出：

如果序列B是序列A的连续子序列，则输出“ListB is the sub sequence of ListA.”，否则输出“ListB is not the sub sequence of ListA.”。

数据最多的测试用例节点数在100这个数量级，所有整数可以用int型存储。


请注意输入输出格式。

样例输入：

Sample 1:
5 4 3 2 1 -1
3 2 1 -1

Sample 2:
1 2 3 4 5 6 7 8 9 -1
1 2 3 4 5 6 7 8 0 -1

样例输出：

Sample 1:
ListB is the sub sequence of ListA.

Sample 2:
ListB is not the sub sequence of ListA.

代码块：

#include<stdio.h>
#include<stdlib.h>
typedef struct node{
	int data;
	struct node* next;
}Node,*Link;
void insertend(Link head,int arr[],int n);
int ifsub(Link head1,Link head2);//判断 
int main()
{
	Link head1=malloc(sizeof(Node));
	head1->next=NULL;
	Link head2=malloc(sizeof(Node));
	head2->next=NULL;
	int a[1000],b[1000];
	int i=0,j=0,p;
	scanf("%d",&a[i]);
	while(a[i]!=-1){
		i++;
		scanf("%d",&a[i]);
	}
	scanf("%d",&b[j]);
	while(b[j]!=-1){
		j++;
		scanf("%d",&b[j]);
	}
	insertend(head1,a,i);
	insertend(head2,b,j);
	p=ifsub(head1,head2);
	if(p)
	printf("ListB is the sub sequence of ListA");
	else
	printf("ListB is not the sub sequence of ListA");
	return 0;
}
void insertend(Link head,int arr[],int n)
{
	int i=0;
	Link p=head->next;
	Link q=head;
	for(i=0;i<n;i++){
		p=malloc(sizeof(Node));
		p->data=arr[i];
		p->next=NULL;
		q->next=p;
		q=p;
	}
}
int ifsub(Link head1,Link head2)
{
	Link p1=head1->next;
	Link p2=head2->next;
	Link pre=p1;
	while(p1!=NULL&&p2!=NULL){
		if(p1->data==p2->data)
		{
			p1=p1->next;
			p2=p2->next;
		}
		else
		{
			pre=pre->next;
			p1=pre;
			p2=head2->next;
		}
	}
	if(p2==NULL)
	return 1;
	else
	return 0;
}