求链表交集(线性表)

求链表交集(线性表)

时间: 1ms        内存:128M

描述:

(线性表)已知递增有序的单链表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个数据元素。

输出:

AB的交集C

示例输入:

6
11 22 33 44 55 66
4
22 22 33 56 

示例输出:

22 33 

提示:

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

#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;
}

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

#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;
}

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

点赞

发表评论

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