用链表判断B是否为A的子集
/*两个整数序列A=a1,a2,a3,...,am和B=b1,b2,b3,...,bn已经存入两个单链表中,设计一个算法,判断序列B是否是序列A的连续子序列
*/
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode
{
int data;
struct LNode *next;
} LNode,*LinkList;
//先建立一个链表,运用后插法吧(带头结点)
LinkList BuildList(LinkList &L)
{
//先创立一个结点,让L指向它
L=(LNode *)malloc(sizeof(LNode));
L->next=NULL;
LNode *p=L;
LNode *s=L;
int e;
printf("请输入链表的数值:\n");
scanf("%d",&e);
while(e!=-1)
{
s=(LNode *)malloc(sizeof(LNode));
s->data=e;
p->next=s;
p=s;
scanf("%d",&e);
}
s->next=NULL;
return L;
}
//输出链表
void OutputList(LinkList L)
{
LNode *p=L->next;
if(p==NULL)
{
printf("链表为空！");
return;
}
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
}
//根据题目所写的骚操作
bool Judge(LinkList A,LinkList B)
{
LNode *p=A;
LNode *q=B;
//先判断两个链表的大小
int a=0;
while(p->next!=NULL)
{
p=p->next;
a++;
}
int b=0;
while(q->next!=NULL)
{
q=q->next;
b++;
}
if(a<=b)
{
return false;
}
//判断B是否为A的子集
p=A;
q=B->next;
int n=0;
loop1:
while(1)
{
p=p->next;
q=B->next;
if(p==NULL)
{
goto loop;
}
while(q!=NULL)
{
if(p->data==q->data)
{
n++;
goto loop1;
}
else
{
q=q->next;
}
}
}
loop:
if(n>=b)
{
return true;
}
else
{
return false;
}
}
int main()
{
LinkList A,B;
LNode *a=BuildList(A);
LNode *b=BuildList(B);
if(Judge(a,b))
{
printf("B是A的子集");
}
else
{
printf("B不是A的子集");
}
}
页:
[1]