题目描述
(线性表)已知递增有序的单链表A,B分别存储了一个集合,请编程以求出两个集合A和B 的交集(即由在A中出现且在B中出现的元素所构成的集合),并以同样的形式存储,同时返回该集合的元素个数。
#include <stdio.h>
#include <stdlib.h> //standard library标准库头文件
typedef struct node
{
int data;
struct node *next;
}List;
List *Create(int n) //尾插法建立链表
{
int i;
List *tmp, *p;
List *head=(List *)malloc(sizeof(List)); //(分配类型 *)malloc(分配元素个数 *sizeof(分配类型))
head->next =NULL;
tmp=head;
for(i=0;i<n;i++)
{
p=(List *)malloc(sizeof(List));
scanf("%d", &p->data);
p->next=tmp->next;
tmp->next=p;
tmp=p;
}
return head;
}
List *intersection(List *p1,List *p2)//两条链表取交集的函数
{
List *p,*tmp; //p用于指向新建立的结点, tmp指向链表尾部
p=(List *)malloc(sizeof(List));//另开辟存储空间存放交集
p->next=NULL;
tmp=p;
p1=p1->next;
p2=p2->next;
while(p1!=NULL) //遍历p1链表
{
if(p2==NULL) //p2与p1比较
{
break;
}
while(p2->data<p1->data&&p2->next!=NULL)
{
p2=p2->next; //相当于p2++
}
if(p1->data==p2->data) //当两条链表中的值相等时
{
/*************/
添加代码
/*************/
}
p1=p1->next; //相当于/p1++
}
tmp->next=NULL;
//delete ;
return p;
}
List *output(List *p) //输出
{
while(p->next)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
return p;
}
void destroy( List *p1)
{
List *p;
while(p1!=NULL)
{
p=p1->next;
delete(p1);
p1=p;
}
}
int main()
{
int m,n;
List *p1,*p2,*p;
scanf("%d", &n);
p1=Create(n); //第一条链表的建立
scanf("%d", &m);
p2=Create(m);//第二条链表的建立
p=intersection( p1, p2);
output(p);
destroy(p);
return 0;
}
输入
一个整数m,表示A的长度m。
m个数表示A中的m个数据元素。
一个整数n,表示B的长度n。
n个数表示B中的n个数据元素。
输出
A与B的交集C
样例输入
6
11 22 33 44 55 66
4
22 22 33 56
样例输出
22 33
参考代码
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int data;
struct node *next;
}
List;
List *Create(int n)
{
int i;
List *tmp, *p;
List *head = (List *)malloc(sizeof(List));
head->next =NULL;
tmp = head;
for (i = 0; i < n; i++)
{
p = (List *)malloc(sizeof(List));
scanf("%d", &p->data);
p->next = tmp->next;
tmp->next = p;
tmp = p;
}
return head;
}
int main()
{
int m, n;
List *p1, *p2, *p, *tmp;
scanf("%d", &n);
p1 = Create(n);
scanf("%d", &m);
p2 = Create(m);
p = (List *)malloc(sizeof(List));
p->next = NULL;
tmp = p;
p1 = p1->next;
p2 = p2->next;
while(p1)
{
if(!p2)
{
break;
}
while(p2->data < p1->data && p2->next)
{
p2 = p2->next;
}
if(p1->data == p2->data)
{
tmp->next = p1;
tmp = p1;
p2 = p2->next;
}
p1 = p1->next;
}
tmp->next = NULL;
while(p->next)
{
p = p->next;
printf("%d ", p->data);
}
printf("n");
return 0;
}
解析
暂无