作业帮用单链表求两个集合的交集
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/06 07:37:09
用单链表求两个集合的交集
用单链表求两个集合的交集
用单链表求两个集合的交集
struct Link
{
int data;
struct Link *next;
};
struct Link *CreateLink()
{
struct Link *head=NULL,*p=NULL,*q=NULL;
head = (struct Link *)malloc(sizeof(struct Link));
head->next = NULL;
p = head;
int n=1;
printf("Please input a number(0 exit):\n");
scanf("%d",&n);
while( n != 0)
{
q = (struct Link *)malloc(sizeof(struct Link));
q->data = n;
p = Insert(p,q);
scanf("%d",&n);
}
return head;
}
struct Link *Insert(struct Link *head,struct Link *p)
{
struct Link *h=head,*q=NULL,*pTemp=p;
q = h;
while(q->next != NULL)
{
if ( (q->next->data) >= (pTemp->data) )
{
break;
}
q = q->next;
}
if (q->next != NULL)
{
pTemp->next = q->next;
q->next = pTemp;
}
else
{
q->next = pTemp;
pTemp->next = NULL;
}
return h;
}
//核心功能函数,找出交集
struct Link *Intersect(struct Link *head1,struct Link *head2)
{
struct Link *p1=head1->next,*p2=head2->next;
struct Link *head,*p,*q;
head = (struct Link *)malloc(sizeof(struct Link));
head->next = NULL;
p = head;
while( (p1!=NULL)&&(p2!=NULL) )
{
if (p1->data == p2->data)
{
q = (struct Link *)malloc(sizeof(struct Link));
q->data = p1->data;
q->next = NULL;
p->next = q;
p = q;
p1 = p1->next;
p2 = p2->next;
}
else if (p1->data < p2->data)
{
p1 = p1->next;
}
else
{
p2 = p2->next;
}
}
return head;
}
//输出链表内容
void PrintLink(struct Link *head)
{
struct Link *p = head->next;
printf("\nThe data in link:");
while (p != NULL)
{
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}
int main(int argc,char* argv[])
{
struct Link *h1=NULL,*h2=NULL,*head=NULL;
h1 = CreateLink();
PrintLink(h1);
h2 = CreateLink();
PrintLink(h2);
head = Intersect(h1,h2);
PrintLink(head);
return 0;
}