一般链表实现集合运算（C语言）

落日映苍穹つ 2023-05-29 03:45 6阅读 0赞

# 一般链表实现集合运算（C语言） #

## 最近在学习数据结构，遇到以下问题： ##

假设集合A = （c, b, e, g, f, d），B = （a, b, n, f），利用一般线性链表实现集合运算（A-B）∪（B-A）。

## 分析： ##

上面的问题只要是考察怎样应用链表，熟悉链表的操作，对链表有更加理性的认识。题目理解：题目的意思是将A和B中相同的元素删除，不同的元素插入的到A中，或者另外创建一个链表来存储。知道题目要求之后下面来提供实现思路：

## 思路： ##

1、根据链表的特点，实现它的基本功能（增、删、改、查）。  
2、在主函数中创建两个链表来存储集合A和B。  
3、题目实现函数：通过使用指针来遍历A和B如果发现相同元素则进行删除，如果没有相同元素则添加。

## 下面给出示例代码： ##

/** * @Author 明志 * @Detail 实现集合运算（A-B）∪（B-A） * @DateTime 2019-11-02 * @Tools sublime text3 + gcc */
    #include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    
    typedef char ElemType;   //声明元素类型
    
    //声明单链表的存储结构
    typedef struct LNode
    { 
    	ElemType data;
    	struct LNode* next;
    
    }LNode, *LinkList;
    
    //初始化单链表
    
    void InitList(LinkList* L)  //注意：这里的L是二级指针
    { 
    	*L = (LinkList)malloc(sizeof(LNode)); //分配空间
    	if (!(*L))
    	{ 
    		printf("the allocation space error!");
    		exit(0);
    	}
    	(*L)->next = NULL;
    }
    
    //销毁单链表
    void DestroyList(LinkList *L)
    { 
    	LinkList q;
    	while (*L)
    	{ 
    		q = (*L)->next;
    		free(*L);  //释放头结点
    		*L = q;   //L指向原首元节点，实现头结点
    	}
    }
    
    //将单链表重置为空表
    void ClearList(LinkList L)
    { 
    	LinkList p = L->next; //p指向第一个结点
    	L->next = NULL;   //头结点指针域为空
    	DestroyList(&p);  //销毁p所指向的单链表
    
    }
    
    //判断单链表是否为空表
    int ListEmpty(LinkList L)
    { 
    	if (L->next) //非空
    	{ 
    		return 0;
    	}
    	else
    	{ 
    		return 1;
    	}
    
    }
    
    //返回L中的数据元素个数
    int ListLength(LinkList L)
    { 
    	int i = 0;
    	LinkList p = L->next; //p指向第一个结点
    	while (p)
    	{ 
    		i++;
    		p = p->next;  //p指向下一个结点
    	}
    	return i;
    
    }
    
    
    //获取单链表中的第i个元素
    int GetElem(LinkList L, int i, ElemType *e)
    { 
    	int j = 1;
    	LinkList p = L->next; //p指向第一个结点
    	while (p && j < i)
    	{ 
    		j++; //计数器加一
    		p = p->next;  //p指向下一个结点
    	}
    
    	if ((!p) || (j > i)) //结点不存在
    	{ 
    		return 0;
    	}
    	*e = p->data;  //获取第i个元素
    	return 1;
    }
    
    //返回L中第一个与e存在关系的元素的位置
    int LocateElem(LinkList L, ElemType e, int(*compare)(ElemType, ElemType))
    { 
    	int i = 0;
    	LinkList p = L->next; //p指向第一个结点
    	while (p)  //未到表尾
    	{ 
    		i++;
    		if (compare(p->data, e))  //找出数据元素
    		{ 
    			return i;
    		}
    		p = p->next;  //p指向下一个结点
    	}
    	return 0;  //满足关系的数据元素不存在
    }
    
    //比较两个元素是否相等
    int ListCompare(ElemType e1, ElemType e2)
    { 
    	if (e1 == e2)
    	{ 
    		return 1;
    	}
    	else
    	{ 
    		return 0;
    	}
    
    }
    //在带头结点的单链表L中第i个位置之前插入元素e
    int ListInsert(LinkList L, int i, ElemType e)
    { 
    	int j = 0;
    	LinkList s, p = L;   //p指向头结点
    	while (p && j < i - 1)  //寻找第i - 1个结点
    	{ 
    		j++;
    		p = p->next;  //p指向下一个结点
    	}
    	if (!p || j > i - 1)
    	{ 
    		return -1;   //插入失败
    	}
    	s = (LinkList)malloc(sizeof(LNode));  //生成新节点，以下将其插入L中
    	s->data = e;      //将e赋值给新节点
    	s->next = p->next; //新节点指向原第i个结点
    	p->next = s;      //原第i-1个结点指向新节点
    	return 1;     //成功插入
    }
    
    //在单链表中删除第i个元素并且用e返回
    int ListDelete(LinkList L, int i, ElemType *e)
    { 
    	int j = 0;
    	LinkList q, p = L;
    	while (p->next && j < i - 1)
    	{ 
    		j++;
    		p = p->next;   //p指向下一个结点
    	}
    
    	if (!p->next || j > i - 1)  //删除位置不合理
    	{ 
    		return -1;
    	}
    
    	q = p->next;  //指向待删除的结点
    	p->next = q->next;   //
    	*e = q->data;
    	free(q);
    	return 1;
    
    }
    
    //打印函数
    void Display(ElemType e)
    { 
    	printf("%c, ", e);
    
    }
    //将元素输出
    void ListTraverse(LinkList L, void(*visit)(ElemType))
    { 
    	LinkList p = L->next;
    	while (p)
    	{ 
    		visit(p->data);
    		p = p->next;
    	}
    	printf("\n");
    }
    
    //求和函数
    void ListAdd(LinkList &list1, LinkList &list2)
    { 
    	ElemType e;   //用来暂时存放元素
    	LinkList p1 = list1->next;    //首先将指针赋值给变量p1和p2，使用指针来遍历链表
    	LinkList p2 = list2->next;
    
    	while (p1)
    	{ 
    		while (p2)
    		{ 
    			int pos = LocateElem(list1, p2->data, ListCompare);   //寻找元素的位置
    			if (pos)   //如果元素存在，则将元素删除
    			{ 
    				ListDelete(list1, pos, &e);  //删除元素
    			}
    			else
    			{ 
    				ListInsert(list1, 1, p2->data);   //插入元素
    			}
    			p2 = p2->next;   //移动指针，遍历链表
    		}
    
    		p1 = p1->next; //移动指针，遍历链表
    	}
    
    
    }
    
    int main(void)
    { 
    	char A[] = { 'c', 'b', 'e', 'g', 'f', 'd'};  //初始化插入元素
    	char B[] = { 'a', 'b', 'n', 'f'};
    	LinkList list1;    //用链表来保存数据
    	LinkList list2;
    
    	InitList(&list1);   //初始化链表
    	InitList(&list2);
    	//初始化链表
    	for (int i = 0; i < 6; i++)
    	{ 
    		ListInsert(list1, i + 1, A[i]);    //将链表初始化
    	}
    
    	for (int i = 0; i < 4; i++)
    	{ 
    		ListInsert(list2, i + 1, B[i]);    //将链表初始化
    	}
    
    	ListTraverse(list1, Display);     //显示链表当前状态
    	ListTraverse(list2, Display);
    
    	ListAdd(list1, list2);
    	//输出链表的结果
    	ListTraverse(list1, Display);    //显示结果
    	ClearList(list1);
    	ClearList(list2);
    	system("pause");    //让程序等待
    
    	return 0;
    }

## 运算结果： ##

![在这里插入图片描述][20191103203833571.png]  
链表遍历查找相同元素的算法效率还不是很高，如果你有更加好的方法欢迎给我留言。

[20191103203833571.png]: https://img-blog.csdnimg.cn/20191103203833571.png