⼀般链表实现集合运算（C语⾔）
⼀般链表实现集合运算（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)//⾮空
{
return0;
}
else
{
return1;
}
}
//返回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))//结点不存在
{
return0;
}
*e = p->data;//获取第i个元素
return1;
}
//返回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指向下⼀个结点
}
return0;//满⾜关系的数据元素不存在
}
//⽐较两个元素是否相等
int ListCompare(ElemType e1, ElemType e2)
{
if(e1 == e2)
{
return1;
}
else
{
return0;
}
}
//在带头结点的单链表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个结点指向新节点
return1;//成功插⼊
}
/
/在单链表中删除第i个元素并且⽤e返回
c语言listinsert函数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);
return1;
}
//打印函数
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");//让程序等待
return0;
}
运算结果：
链表遍历查相同元素的算法效率还不是很⾼，如果你有更加好的⽅法欢迎给我留⾔。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。