数据结构-两个链表的交集、差集、并集

心已赠人 2022-05-19 08:22 236阅读 0赞

***【题目来自灰灰考研】***

**（2018南开大学初试）**两个有序的无头结点的链表La，Lb。编写函数：如何以最优的方式找出二者的交集，并且把结果存在一个新链表中返回。

单链表的类型定义如下：

Typeddf struct LNode\{

Element Type data;

Struct LNode \*next;

\}LNode, \*ListNode;

#include<iostream>
    #include<cstdlib>
    #include<cstring>
    #define MIN 0xc0c0c0c0
    #define MAX 0x3f3f3f3f
    using namespace std; 
    
    typedef int ElementType;
    typedef struct LNode{ 
    	ElementType data;  
    	struct LNode *next; 
    }LNode, *ListNode; 
    
    void CreateLinkList(ListNode A, ListNode B)
    {
    	/*
    		使用指定数组中的数据创建两个链表
    	*/
    	int n = 6, m = 6;
    	ElementType dataA[] = {1, 2, 3, 7, 8, 10};
    	ElementType dataB[] = {1, 3, 5, 7, 9, 11};
    	LNode *p, *q;
    	p = A;
    	p->data = dataA[0];
    	p->next = NULL;
    	for(int i = 1; i < n; i++)
    	{
    		q = (LNode*)malloc(sizeof(LNode));
    		q->data = dataA[i];
    		p->next = q;
    		p = p->next;
    		p->next = NULL;
    	} 
    	p = B;
    	p->data = dataB[0];
    	p->next = NULL;
    	for(int i = 1; i < m; i++)
    	{
    		q = (LNode*)malloc(sizeof(LNode));
    		q->data = dataB[i];
    		p->next = q;
    		p = p->next;
    		p->next = NULL;
    	} 
    }
    
    ListNode intersection(ListNode A, ListNode B)
    {
    	/*
    		找到两个链表的交集
    		思路：
    		依次遍历两个链表，比较两个链表当前元素的大小关系
    		1。如果两个链表当前元素相等，则找到一个相交元素
    		2。如果第一个链表元素小于第二个链表元素，则第一个链表的指针后移一位
    		3。如果第一个链表元素大于第二个链表元素，则第二个链表的指针后移一位
    		 
    	*/ 
    	ListNode C = (ListNode)malloc(sizeof(ListNode));
    	C->next = NULL;
    	LNode *p, *q, *r;
    	p = A;
    	q = B;
    	r = C;
    	while(p!=NULL && q!=NULL)
    	{
    		if(p->data < q->data)
    		{
    			p = p->next;
    		}
    		else if(p->data == q->data)
    		{
    			LNode *s = (LNode*)malloc(sizeof(LNode));
    			s->next = NULL;
    			s->data = p->data;
    			
    			p = p->next;
    			q = q->next;
    			r->next = s;
    			r = s;
    		}
    		else
    		{
    			q = q->next;
    		}
    	}
    	return C->next;
    } 
    ListNode Union(ListNode A, ListNode B)
    {
    	/*
    		找到两个链表的并集（去除相同元素） 
    		思路：
    		首先使用一个指针last记录上次合并进来的新元素 
    		依次遍历两个链表，比较两个链表当前元素的大小关系
    		1。如果两个链表当前元素相等，则比较last和当前元素的关系，如果不相同则将当前元素并入到新的链表中，两指针均后移。如果相同则只是移动两指针 
    		2。如果第一个链表元素小于第二个链表元素，则第一个链表当前元素和last比较，如果不同则加入，并后移第一个链表指针 。如果相同则只是移动第一个指针 
    		3。如果第一个链表元素大于第二个链表元素，则第二个链表当前元素和last比较，如果不同则加入，并后移第二个链表指针 。如果相同则只是移动第二个指针 
    		4。如果两个链表中某个还有剩余，则与last比较... 
    	*/ 
    	ListNode F = (ListNode)malloc(sizeof(ListNode));
    	F->next = NULL;
    	F->data = MAX;
    	LNode *p, *q, *r, *last;
    	p = A;
    	q = B;
    	r = F;
    	last = F;
    	while(p!=NULL && q!=NULL)
    	{
    		if(p->data < q->data)
    		{
    			if(p->data != last->data)
    			{
    				LNode *s = (LNode*)malloc(sizeof(LNode));
    				s->next = NULL;
    				s->data = p->data;
    				
    				r->next = s;
    				last = p;
    				r = s;
    			}
    			p = p->next;
    		}
    		else if(p->data == q->data)
    		{
    			if(p->data != last->data)
    			{
    				LNode *s = (LNode*)malloc(sizeof(LNode));
    				s->next = NULL;
    				s->data = p->data;
    				
    				r->next = s;
    				last = p;
    				r = s;
    			}
    			p = p->next;
    			q = q->next;
    		}
    		else
    		{
    			if(q->data != last->data)
    			{
    				LNode *s = (LNode*)malloc(sizeof(LNode));
    				s->next = NULL;
    				s->data = q->data;
    				
    				r->next = s;
    				last = q;
    				r = s;
    			}
    			q = q->next;
    		}
    	}
    	if(q != NULL)
    		p = q;
    	while(p != NULL)
    	{
    		if(p->data != last->data)
    		{
    			LNode *s = (LNode*)malloc(sizeof(LNode));
    			s->next = NULL;
    			s->data = p->data;
    			
    			r->next = s;
    			last = p;
    			r = s;
    		}
    		p = p->next;	
    	}
    	return F->next;
    } 
    ListNode Difference(ListNode A, ListNode B) 
    {
    	/*
    		找到两个链表的差集
    		思路：
    		依次遍历两个链表，比较两个链表当前元素的大小关系
    		1。如果两个链表当前元素相等，则两个链表的指针均后移一位
    		2。如果第一个链表元素小于第二个链表元素，则第一个链表的元素肯定是独有的，所有加入到结果链表中 
    		3。如果第一个链表元素大于第二个链表元素，则第二个链表的指针后移一位
    		 	
    	*/ 
    	ListNode D = (ListNode)malloc(sizeof(ListNode));
    	D->next = NULL;
    	LNode *p, *q, *r;
    	p = A;
    	q = B;
    	r = D;
    	while(p!=NULL && q!=NULL)
    	{
    		if(p->data < q->data)
    		{
    			LNode *s = (LNode*)malloc(sizeof(LNode));
    			s->next = NULL;
    			s->data = p->data;
    			
    			p = p->next;
    			r->next = s;
    			r = s;
    		}
    		else if(p->data == q->data)
    		{
    			p = p->next;
    			q = q->next;
    		}
    		else
    		{
    			q = q->next;
    		}
    		
    	}
    	while(p != NULL)
    	{
    		LNode *s = (LNode*)malloc(sizeof(LNode));
    		s->next = NULL;
    		s->data = p->data;
    		p = p->next;
    		r->next = s;
    		r = s;
    	}
    	return D->next;
    }
    
    int main()
    {
    	ListNode A, B, C, D, E, F, q;
    	A = (ListNode)malloc(sizeof(ListNode));
    	B = (ListNode)malloc(sizeof(ListNode));
    	
    	//C为两个链表的交集 
    	CreateLinkList(A, B);
    	C = intersection(A, B);
    	q = C;
    	while(q!=NULL)
    	{
    		cout<<q->data<<" ";
    		q = q->next;
    	}
    	cout<<endl;
    	
    	//D为A/B,即A与B的差集 
    	D = Difference(A, B);
    	q = D;
    	while(q!=NULL)
    	{
    		cout<<q->data<<" ";
    		q = q->next;
    	}
    	cout<<endl;
    	
    	//E为B/A,即B与A的差集 
    	E = Difference(B, A);
    	q = E;
    	while(q!=NULL)
    	{
    		cout<<q->data<<" ";
    		q = q->next;
    	}
    	cout<<endl;
    	
    	//F为A和B的去重并集 
    	F = Union(A, B);
    	q = F;
    	while(q!=NULL)
    	{
    		cout<<q->data<<" ";
    		q = q->next;
    	}
    	cout<<endl;
    	
    	return 0;
    }