#include "stdafx.h"#include "malloc.h"typedef struct Node{	char data;	Node *next;}List;

// 创建单链表void CreateList(List *&L, char a[], int n){	List *s,*r;	L = (List *)malloc(sizeof(List));	L->next = NULL;	r = L;	for (int i = 0; i < n; i++)	{		s = (List *)malloc(sizeof(List));		s->data = a[i];		r->next = s;		r = s;	}	r->next = NULL;}

// 使用了排序算法中的插入排序void Sort(List *&head){	List *p = head->next, *q, *r; // p指向第一个节点	if(p!=NULL)	{		r = p->next; // r指向第二个节点		p->next = NULL; // p的后继节点为NULL		p = r; // p指向第一个节点		while (p!=NULL)		{			r = p->next; 			q = head;			while (q->next!=NULL &&q->next->data
     
      data)			{				q = q->next;			}			p->next = q->next;			q->next = p;			p = r;		}	}}// 求两个集合并集void Union(List *La, List *Lb, List *&Lc){	List *la = La->next, *lb = Lb->next,*tc,*s;	Lc = (List *)malloc(sizeof(List));	tc = Lc;	// 在进行比较	if (la != NULL && lb != NULL)	{		while (la != NULL && lb != NULL)		{			s = (List *)malloc(sizeof(List));			if (la->data > lb->data)			{				// la节点大于lb节点				s->data = lb->data;				tc->next = s;				tc = s;				lb = lb->next;			}			else if(la->data
      
       data)			{				 // la节点小于lb节点				s->data = la->data;				tc->next = s;				tc = s;				la = la->next;			}			else			{				s->data = la->data;				tc->next = s;				tc = s;				la = la->next;				lb = lb->next;			}		}	}	//  剩余节点(la与lb必定有一个是NULL)	if (lb != NULL)	{		la = lb;	}	while (la!=NULL)	{		s = (List *)malloc(sizeof(List));		s->data = la->data;		tc->next = s;		tc = s;		la = la->next;	}	tc->next = NULL;}// 求两个集合的并集void  InterSect(List *La, List *Lb, List *&Lc){	List *la = La->next, *lb,*tc, *s;	Lc = (List *)malloc(sizeof(List));	tc = Lc;	while (la!=NULL)	{		lb = Lb->next;		// 根据链表为有序链表过滤一部分比较节点		while (lb!=NULL && lb->data
       
        data)		{			lb = lb->next;		}		if (lb != NULL && lb->data == la->data)		{			s = (List *)malloc(sizeof(List));			s->data = la->data;			tc->next = s;			tc = s;		}		la = la->next;	}	tc->next = NULL;}// 求差集，即a-b，去掉a链表中与b链表的交集void Subs(List *La, List *Lb, List *&Lc){	List *la = La->next, *lb, *tc, *s;	Lc = (List *)malloc(sizeof(List));	tc = Lc;	while (la!=NULL)	{		lb = Lb->next;		// 根据链表为有序链表过滤一部分比较节点		while (lb!=NULL && lb->data
        
         data)		{			lb = lb->next;		}		// 去掉Lb链表与La链表的交集部分		if (!(lb != NULL &&la->data == lb->data))		{			s = (List *)malloc(sizeof(List));			s->data = la->data;			tc->next = s;			tc = s;		}		la = la->next;	}	tc->next = NULL;}
        
       
      
     

　　1、使用单链表对集合进行交、并、差的运算，重点在于对单链表进行排序，排序后的单链表在进行运算，可以减少节点的比较优化时间复杂度。