链表中的并集和交集（c/c++实现）

淡淡的烟草味﹌ 2023-07-24 14:45 0阅读 0赞

使用单链表表示集合。编写两个算法（求交算法和求并算法），并输出最终的结果。  
测试用例：集合A为\{3，4，1，6\}，集合A为\{2，3，6，7\}，  
交集为\{3，6\}  
并集为\{1，2，3，4，6，7\}

#include<stdio.h>
    #include<iostream>
    using namespace std;
    #define N 4
    typedef struct Lnode
    {
        
    	int data;
    	struct Lnode *next;
    }Lnode, *Linklist;//类型定义
     //函数声明
    //尾插法创建一个单链表（顺序输入一个数组）
    Linklist Createndlist(int a[N])
    {
        
    	Linklist L;
    	L = (Lnode*)malloc(sizeof(Lnode));
    	if (L == NULL)
    	{
        
    		cout << "error";
    		exit(0);
    	}
    	else L->next = NULL;
    	Linklist tail, p;
    	tail = L;
    	int j;
    	for (j = 0; j < N; j++)
    	{
        
    		p = (Lnode*)malloc(sizeof(Lnode));
    		if (p == NULL)
    		{
        
    			cout << "error";
    			exit(0);
    		}
    		else p->next = NULL;
    		p->data = a[j];
    		tail->next = p;
    		tail = p;
    	}
    	tail->next = NULL;
    	return L;
    }
    //输出单链
    void putlist(Linklist L)
    {
        
    	Linklist p;
    	p = L->next;
    	cout << "当前链表为：";
    	while (p != NULL)
    	{
        
    		cout << p->data << " ";
    		p = p->next;
    	}
    	cout << endl;
    }
    //求交集
    Linklist Getjiaolist(Linklist LA, Linklist LB,Linklist LC)  
    {
        
    	Linklist p, q, p1;
    	p = LA->next;
    	//LA->next = NULL;
    	p1 = LC;
    	q = LB->next;
    	while (p)
    	{
        
    		if (p->data == q->data)
    		{
        
    			Linklist a;
    			a = (Lnode*)malloc(sizeof(Lnode));   //申请一个新结点
    			if (a == NULL)
    			{
        
    				cout << "error";
    				exit(0);
    			}
    			else a->next = NULL;
    			a->data = p->data;
    			a->next = NULL;
    			p1->next = a;
    			p1 = a;
    			p = p->next;
    			q = LB->next;
    		}
    		else
    		{
        
    			if (q->next != NULL)q = q->next;
    			else
    			{
        
    				p = p->next;
    				q = LB->next;
    			}
    		}
    	}
    	return LC;
    }
    //求并集
    Linklist Getbinglist(Linklist LA, Linklist LB)
    {
        
    	Linklist m;
    	m = LA->next;
    	while (m&&m->next != NULL)
    	{
        
    		m = m->next;
    	}
    	m->next = LB->next;
    	Linklist p, q;
    	p = LA->next;
    	q = p;
    	while (p->next)
    	{
        
    		if (p->data == q->next->data)
    		{
        
    			
    			if (q->next->next == NULL)
    			{
        
    				q->next = NULL;
    				p = p->next;
    				q = p;
    			}
    			else
    			{
        
    				q->next = q->next->next;
    			}
    		}
    		else
    		{
        
    			if (q->next->next == NULL)
    			{
        
    				p = p->next;
    				q = p;
    			}
    			else q = q->next;
    		}
    	}
    	return LA;
    
    }
    int main()
    {
        
    	Linklist LC;
    	LC = (Lnode*)malloc(sizeof(Lnode));
    	LD = (Lnode*)malloc(sizeof(Lnode));
    	int a[N], b[N];
    	cout << "正在创建链表LA:..." << endl;
    	printf("请输入%d个链表元素的值:", N);
    	for (int i = 0; i < N; i++)
    	{
        
    		cin >> a[i];
    	}
    	Linklist LA;
    	LA = Createndlist(a);
    	cout << "正在创建链表LB:..." << endl;
    	printf("请输入%d个链表元素的值:", N);
    	for (int i = 0; i < N; i++)
    	{
        
    		cin >> b[i];
    	}
    	Linklist LB;
    	LB = Createndlist(b);
    	Getjiaolist(LA,LB,LC);
    	cout << "所得交集为：";
    	putlist(LC);
    	Getbinglist(LA, LB);
    	cout << "所得并集为：";
    	putlist(LA);
    	return 0;
    }