[数据结构与算法]单链表求差集

/*时间：2021年10月6日
  版本：Dve-C++ 5.11
  问题描述：以单链表表示集合，假设集合A用单链表LA表示，
  集合B用单链表LB表示，设计算法求两个集合的差，即A-B。*/ 
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>     
#include<math.h>
#include<time.h> 

#define OK 1;
#define ERROR 0;

#define MAXSIZE 100;

typedef int Status;
typedef int ElemType;

Status visit(ElemType c){
	printf("%d",c);
	return OK;
}

//声明链表 、定义链表  
typedef struct Node{
	ElemType data;			/*数据域*/ 
	struct Node *next;		/*指针域*/ 
}Node,*LinkList;

//初始化链表 
Status InitList(LinkList*L) { 
    *L=(LinkList)malloc(sizeof(Node)); 			/*产生头结点,并使L指向此头结点*/
    if(!(*L)) 									/*存储分配失败*/
        return ERROR;
    (*L)->next=NULL;							/*指针指向空*/

    return OK;
}

//操作结果：返回L中数据元素个数 
int ListLength(LinkList L){
    int i=0;
    LinkList p=L->next; 						/*p指向第一个结点*/
    while(p){
        p=p->next;								/*p 指向下一个结点*/
        i++;
    }
    return i;
}
//获取元素，用e返回L中第i个数据元素的值 
Status GetElem(LinkList L,int i,ElemType *e){
	int j;
	LinkList p;								/*声明一个结点p指向链表L的第一个结点*/ 
	p=L->next;				
	j=0;									/*用来存放单链表的长度*/ 
	while(p&&j<i){ 					    	/*p遍历到i-1*/   
		p=p->next;  
		j++;
	}
	if(!p||j>i ) 
		return ERROR; 
	*e=p->data;  							 /*取第i个元素的数据*/
	return OK;
}
//返回L中第1个与e满足关系的数据元素的位序
int LocateElem(LinkList L,ElemType e){
    int i=0;
    LinkList p=L->next;
    while(p){
        i++;
        if(p->data==e)
			return i;
        p=p->next;
    }
    return 0;								/*若这个数据元素不存在，返回值为0*/
}
//删除链表L中的数据元素，删除第i个数据元素，链表L的元素个数减一 
Status ListDelete(LinkList *L,int i,ElemType *e){ 
	int j;
	LinkList p,q;
	p=*L;
	j=0;
	while(p->next&&j<i){				/*遍历链表，寻找第i个元素*/
        p = p->next;
        j++;
	}
	if(!(p->next)||j>i) 
	    return ERROR;          
	q=p->next;
	p->next=q->next;					/*将p的后继结点赋值给q的后继结点*/
	*e=q->data;               		    /*将q的数据域赋值给e*/ 
	free(q);                   			/*释放q*/
	return OK;
}
//输出链表L的数据元素 
Status ListTraverse(LinkList L){
    LinkList p=L->next;
    while(p){
        visit(p->data);
        p=p->next;
    }
    printf("\n");
    return OK;
}
//尾插法创建单链表 
void CreateListTail(LinkList*L,int n) {
	LinkList p,r;
	int i,e;
	*L=(LinkList)malloc(sizeof(Node)); 
	r=*L;                               
	for(i=0;i<n;i++){
		p=(Node*)malloc(sizeof(Node)); 
		printf("请输入创建链表的一个数据元素：");
		scanf("%d",&e);
		p->data=e;        
		r->next=p;                       		 /*将尾结点的指针指向新结点 */
		r=p;                           		     /*将当前的新结点定义为新的尾结点*/
	}
	r->next = NULL;
}
//求两个集合的差集 
void Difference(LinkList LA,LinkList LB){
	LinkList pre,p,q,r;
	pre=LA;
	p=LA->next;				/*p指向LA表中的某一结点，而pre始终指向p的前驱结点*/
	while(p!=NULL){
		q=LB->next;
		while(q!=NULL&&q->data!=p->data)
			q=q->next;
		if(q!=NULL){
			r=p;
			pre->next=p->next;
			p=p->next;
			free(r);
		}
		else{
			pre=p;
			p=p->next;
		}
	} 
}

int main(){
	LinkList LA;
	LinkList LB;
	
	InitList(&LA);
	InitList(&LB);
	
	printf("对于LA：\n");
	CreateListTail(&LA,5);
    printf("A：");
    ListTraverse(LA); 
    
   	printf("对于LB：\n");
    CreateListTail(&LB,6);
    printf("B：");
    ListTraverse(LB); 
    Difference(LA,LB);
	printf("A-B:");
	ListTraverse(LA);
    return 0;
}

集合的差A-B中包含所有属于A而不属于集合B的元素。

对于集合A中的每一个元素e，在集合B的链表LB中进行查找，若存在与e相同的元素，则总LA中将其删除。

1. 算法设计

1. Init()用来初始化链表；
2. CreatFromTail()用尾插法来创建链表；
3. Difference()函数用来求两个集合的差；