差集运算(线性表)

差集运算(线性表)

时间: 1ms        内存:128M

描述:

线性表)已知递增有序的单链表A,B分别存储了一个集合,请编程以求出两个集合A和B 的差集(即由在A中出现且在B中不出现的元素所构成的集合),并以同样的形式存储,同时返回该集合的元素个数。
#include<iostream>
using namespace std;
#define NULL 0      
int i,len,j,n,m;
struct linklist     //定义结构体
{
    int num;
    linklist *next;
};
linklist *creat()    //尾插法建立链表
{   int x;
   cin>>m;
   linklist *p1,*head,*p2;//p1用于指向新建立的结点,p2指向尾结点
   p1=new linklist;
   for(x=1;x<=m;x++)
    {
        cin>>p1->num;
        if(x==1) head=p1;
        p2=p1;      
        p1=new linklist;
        p2->next=p1;
        if(x==m) p2->next=NULL;
    }
      return head;
}
void build_print_linklist(linklist *a,linklist *b)  //两条链表取差集的函数
{
    linklist *p1,*p2,*head,*p,*c,*p3;
    p1=a;p2=b;
    int m=0,n=0;
    while(p1!=NULL)        //遍历p1
    {
        n=0;p2=b;            
        while(p2!=NULL)     //移动p2,寻找在p1中出现却不在p2中出现的值
        {
            if(p2->num==p1->num) n=1;  //有相等的值,记录n=1
            p2=p2->next;
        }
          if(n==0)
            {
               /******************/
                添加代码
              /******************/
                if(m==1) c=p,p3=p;    //差集存放才c中
                else
               {
                p3->next=p;
                p3=p;
                }
            }
        p1=p1->next;
    }
    p3->next=NULL;
    n=0;
    while(c!=NULL)         //输出差集
    {
        n++;
        cout<<c->num<<" ";
        c=c->next;
    }
    cout<<endl;
    cout<<n<<endl;
}
void destroy(struct linklist *head)
{
 struct linklist *p;
 while(head!=NULL)
 {
  p=head->next;
  delete(head);
  head=p;
 }
}
int main()
{
    linklist *heada,*headb;//建立两条链表,由build_print_linklist函数执行A-B并输出
    heada=creat();
    headb=creat();
    build_print_linklist(heada,headb);
 destroy(heada);
    destroy(headb);
    return 0;
}

输入:

一个整数m,表示A链表的长度m。

m个数表示A链表中的m个数据元素。

一个整数n,表示B链表的长度n。

n个数表示B链表中的n个数据元素。

输出:

A-B链表

元素个数

示例输入:

7
13 42 35 56 7 11 14
6
21 17 90 23 13 42

示例输出:

35 56 7 11 14 
5

提示:

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

#include <stdio.h>
int main()
{
	int n,m,i,j,r=0;
	int a[1000],b[1000];
	scanf("%d",&n);
	for (i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	scanf("%d",&m);
	for (i=0;i<m;i++)
	{
		scanf("%d",&b[i]);
	}
	for (i=0;i<n;i++)
	{
		for (j=0;j<m;j++)
		{
			if (a[i]==b[j])
				a[i]=0;
		}
	}
	for (i=0;i<n;i++)
	{
		if (a[i]!=0)
		{
			printf("%d ",a[i]);
			r=r+1;
		}
	}
	printf("\n%d\n",r);
	return 0;
}

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

#include <stdio.h>
int main()
{
	int n,m,i,j,r=0;
	int a[1000],b[1000];
	scanf("%d",&n);
	for (i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	scanf("%d",&m);
	for (i=0;i<m;i++)
	{
		scanf("%d",&b[i]);
	}
	for (i=0;i<n;i++)
	{
		for (j=0;j<m;j++)
		{
			if (a[i]==b[j])
				a[i]=0;
		}
	}
	for (i=0;i<n;i++)
	{
		if (a[i]!=0)
		{
			printf("%d ",a[i]);
			r=r+1;
		}
	}
	printf("\n%d\n",r);
	return 0;
}

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

点赞

发表评论

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