04071402226.cpp

来自「数据结构链表的C++源程序,实现简单易懂,绝对正确,直接就可以运行,不需做任何修」· C++ 代码 · 共 59 行

//另辟空间求链表A和链表B的交集，且同一链表中不含有相同的元素
#include<iostream.h>
typedef int elemtype;
#include"04071402llist.h"

void list_intersect(llist A,llist B,llist &C)        //算法的具体实现      
{
    llist pa,pb,pc,s;
	C=new Lnode;
	pa=A->next;pb=B->next;pc=C;
	while(pa&&pb)
	{
		if(pa->data<pb->data) 
			pa=pa->next;
        else if(pa->data>pb->data) 
			pb=pb->next;
        else
		{
			s=new Lnode;
            s->data=pa->data;
			pc->next=s;
            pc=s;
            pa=pa->next;
			pb=pb->next;
		}
	}
	pc->next=NULL;
	delete A,B;
}

void main()                           //主函数
{
	llist A,B,C;
	elemtype *a,*b;
	int m,n;
	cout<<"请输入链表存储数据的个数:"<<endl;
	cin>>m;
	a=new elemtype[m];
    cout<<"请依次输入链表所存储的元素:"<<endl;
	for(int i=0;i<m;i++)
		cin>>a[i];
	listcreat(A,m,a);                            //调用构造链表子函数
	cout<<"请输入链表存储数据的个数:"<<endl;
	cin>>n;
	b=new elemtype[n];
    cout<<"请依次输入链表所存储的元素:"<<endl;
	for(i=0;i<n;i++)
		cin>>b[i];
	listcreat(B,n,b);                                //调用构造链表子函数
	list_intersect(A,B,C);                        //调用实现子函数
    if(C->next)
	{
		cout<<"两链表的交集为:"<<endl;
        listtraverse(C);
	}
	else
		cout<<"两链表的交集为空集!";
	cout<<endl;
}