unionopr_list.cpp

集合操作 尾插法制表；2

// ② 对两集合A,B进行以下操作:A∪B,A—B,A∩B
// 用到以下功能：1，尾插法制表；2，链表求纯；3，逆置链表

typedef int ElemType;
typedef struct LNode
{
	ElemType data;
	struct LNode *next;
}LNode, *LinkList;


#include <stdio.h>
#include<stdlib.h>

void CreatList_L(LinkList *L);              //尾插法制表
void union_add(LinkList *Lc,LinkList La,LinkList Lb);   //A∪B
void union_sub(LinkList *Ld,LinkList La,LinkList Lb);   //A—B
void union_jun(LinkList *Le,LinkList La,LinkList Lb);   //A∩B
void pur_LinkList(LinkList *L);             //链表求纯,即删除其中相同元素的结点
void reverse_L(LinkList *);                 //将链表逆置
void Print_L(LinkList *L);                  //输出链表

void main()
{
	LinkList La= (LinkList)malloc(sizeof(LNode));
    LinkList Lb= (LinkList)malloc(sizeof(LNode));

    LinkList Lc= (LinkList)malloc(sizeof(LNode));  //创建 A∪B 头结点
    LinkList Ld= (LinkList)malloc(sizeof(LNode));  //创建 A—B 头结点
    LinkList Le= (LinkList)malloc(sizeof(LNode));  //创建 A∩B 头结点

	La->next=Lb->next=Lc->next=Ld->next=Le->next=NULL;
	
	printf("(以下集合元素输入完后以回车结束)\n");

	printf("请输入集合A中的元素：\n");
    CreatList_L(&La);

	printf("请输入集合B中的元素：\n");
	CreatList_L(&Lb);
	
	printf("\n");

    union_add(&Lc,La,Lb);
    pur_LinkList(&Lc);  
	printf("A∪B 结果如下:\n");
    Print_L(&Lc);
	
	union_sub(&Ld,La,Lb);
	printf("A-B 结果如下:\n");
    Print_L(&Ld);

    union_jun(&Le,La,Lb);
    printf("A∩B 结果如下:\n");
    Print_L(&Le);

	printf("\n");
 
	printf("将A∪B的结果逆置可得如下结果：\n");
    reverse_L(&Lc);
    Print_L(&Lc);

	printf("\n");

}

void CreatList_L(LinkList *L)  
{
	LinkList p,q;
	int temp;
	char c;               //以回车结束
	(*L)->next=NULL;
	p=(*L);
    

	while(c!='\n')
	{
		scanf("%d",&temp);
		q=(LinkList)malloc(sizeof(LNode));
		q->data=temp;
		q->next=NULL;
		p->next=q;
		p=q;
	    c=getchar();

	}
}

//  输出链表
void Print_L(LinkList *L)
{
	LinkList p=(*L)->next;

	if(!p)	
		printf("     ⊙");	        //空集

	while(p)
	{
		printf("%5d",p->data );
		p=p->next;
	}
	printf("\n");
}


//  求纯链表
void pur_LinkList(LinkList *L)
{
	LinkList p,q,r;
	p=(*L)->next;
	if(!p)  return;
	while(p)
	{
		q=p;
		while(q->next)
		{
			if(q->next->data==p->data)
			{
				r=q->next;
				q->next=r->next;
				free(r);
			}
			else
				q=q->next;
		}

		p=p->next;
	}
}


//	A∪B
	
void union_add(LinkList *Lc,LinkList La,LinkList Lb)
{
	LinkList p=La->next,q=*Lc,r;	
	
		while(p)
		{
			r=(LinkList)malloc(sizeof(LNode));
			q->next=r;
			r->next=NULL;
			r->data=p->data;
			p=p->next;
			q=r;
		}

		p=Lb->next;
		while(p)
		{
			r=(LinkList)malloc(sizeof(LNode));
			q->next=r;
			r->next=NULL;
			r->data=p->data;
			p=p->next;
			q=r;
		}
}

		
//   A—B

void union_sub(LinkList *Ld,LinkList La,LinkList Lb)
{
	LinkList p=La->next,q,s,r=*Ld;

	while(p)
	{
        q=Lb->next;
		while(q)
		{
			if(p->data==q->data)
			    break; 
			else
				q=q->next;
		}

		if(!q)
		{
			s=(LinkList)malloc(sizeof(LNode));
			s->data=p->data;
			s->next=NULL;
			r->next=s;
			r=s;
		
		}
        
			p=p->next;

		
	}

}


//A∩B

void union_jun(LinkList *Le,LinkList La,LinkList Lb)
{
	LinkList p=La->next,s=*Le,q,r;

	while(p)
	{
        q=Lb->next;
		while(q)
		{
			if(p->data==q->data)
			{
				r=(LinkList)malloc(sizeof(LNode));
				r->data=p->data;
				r->next=NULL;
				s->next=r;
				s=r;
				p=p->next;
				break;
			}
			else
				q=q->next;
		}
		if(!q)
			p=p->next;
	}
}


//逆置链表

void reverse_L(LinkList *L)
{
	LinkList p,q;
	p=(*L)->next;
	(*L)->next=NULL;

	while(p)
	{
		q=p;
		p=p->next;
		q->next=(*L)->next;
		(*L)->next=q;
	} 
	
}