04071402228.cpp

数据结构链表的C++源程序,实现简单易懂,绝对正确,直接就可以运行,不需做任何修改.

//求链表A和链表B的交集，链表A和链表B中可能含有相同的元素
#include<iostream.h>
typedef int elemtype;
#include"04071402llist.h"

void list_intersect(llist &A,llist B)                 //算法实现子函数          
{
    llist pa,pb,pre,p;
	int k=0;
	pa=A->next;pb=B->next;pre=A;
    while(pa&&pb)
	{
		if(pa->data<pb->data) 
		{
			p=pa;pa=pa->next;delete p;
		}
        else if(pa->data>pb->data)
			pb=pb->next;
        else
		{
			if(!k)
			{
				pre->next=pa;pre=pa;pa=pa->next;pb=pb->next;
			}
			else
			{
				if(pre->data==pa->data)
				{
					p=pa;pa=pa->next;pb=pb->next;delete p;
				}
			    else
				{
					pre->next=pa;pre=pa;pa=pa->next;pb=pb->next;
				}
			}
		}
		k++;
	}
	pre->next=NULL;
	if(pa)
	{
		p=pa;pa=pa->next;delete p;
	}
	delete B;
}

void main()                                 //主函数
{
	llist A,B;
	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);
    if(A->next)
	{
		cout<<"两链表的交集为:"<<endl;
	    listtraverse(A);
	}
	else
		cout<<"两链表的交集为空集!";
	cout<<endl;
}