所谓(A-B)U(B-A),实际上就是A独有的那一部分和B独有的那一部分的并集
也就是简简单单的如图所示
其实这个问题本身用动态链表(就是常规链表)是很好解决的,但是由于我们要用静态链表来实现,所以就会显得略微有一些麻烦,到底哪里麻烦?
- 相对于动态链表,静态链表的内存分配函数需要自己来实现
- 相对于动态链表,静态链表的内存回收函数需要自己来实现.
- 静态链表的连接方式,和动态链表也有所不同
- 静态链表在实际操作中比动态链表更容易断(人为因素)
首先大概说一下答题思想吧,如果想先把两个链表建立起来在互相查找删减,实现会很麻烦,因此我采用的方法是:首先我完全建立A集合,然后再B集合输入的过程中对A中已经存在的元素进行删除操作
由于我采用的是传统写法因此对于时间复杂度可能不会考虑太多
首先我们要解决的一个问题就是静态链表的初始化函数,这个其实还是挺简单的
伪代码:
木有
C语言代码:
void initMainLinklist(slinklist *temp){ for(int i=0;i<MAXLINKLISTSIZE;i++){ temp[i].pointerMember=i+1; } temp[MAXLINKLISTSIZE-1].pointerMember=0; }
总得思想就是和静态链表建立一样,不多啰嗦
然后第二个需要考虑的问题就是静态链表的内存分配(包括分配新的空间和删除不需要的空间),因此在这里需要两个函数来完成这个内存分配mallocSpace和freeSpace
int mallocSpace(slinklist *temp){ int linklistHead = temp[0].pointerMember; if(temp[0].pointerMember){ temp[0].pointerMember=temp[linklistHead].pointerMember; return linklistHead; }else{ return -1; } }
void freeSpace(slinklist *temp,int deleteSpace){ temp[deleteSpace].pointerMember=temp[0].pointerMember; temp[0].pointerMember=deleteSpace; }
在这里一定不要忘记静态链表的载体数组的首元素的作用:第一个未使用(可分配)节点的位置
最后呢就是一个主体部分的了
void kernel(slinklist *temp){ int endPointer,tmp,s,setA,setB,Apre,Anow; initMainLinklist(temp); s=mallocSpace(temp); endPointer=s; scanf("%d%d",&setA,&setB); for(int i=0;i<setA;i++){ tmp=mallocSpace(temp); temp[endPointer].pointerMember=tmp; scanf("%d",&temp[tmp].dataMember); endPointer=tmp; } temp[endPointer].pointerMember=0; for(int i=0;i<setB;i++){ int b; scanf("%d",&b); Apre = s; Anow = temp[s].pointerMember; while(temp[Anow].dataMember!=b && && temp[Anow].pointerMember!=temp[endPointer].pointerMember){ Apre = Anow; Anow = temp[Anow].pointerMember; } if(temp[Anow].dataMember ==b){ temp[Apre].pointerMember=temp[Anow].pointerMember; freeSpace(temp,Anow); if(Anow==endPointer) endPointer=Apre; }else{ int tmp=mallocSpace(temp); temp[Anow].pointerMember=tmp; temp[tmp].dataMember=b; temp[tmp].pointerMember=0; endPointer=tmp; } } }
这个kernel函数有一些比较有意思的地方
s=mallocSpace(temp);
这个步骤的存在是为了声明一个头节点,因为在静态链表的实际操作中0位置是存储第一个未使用(可分配)节点的位置,所以就需要一个表头来记录正式链表的头,因此需要申请一个空的空间作为表头
while(temp[Anow].dataMember!=b && temp[Anow].pointerMember!=temp[endPointer].pointerMember){ Apre = Anow; Anow = temp[Anow].pointerMember; }
这条while语句的第二个条件是防止Anow跳到0(实在惭愧这个bug看了这么久才看出来)
千万不要忘记了在后续添加B集合的时候要把原有集合A的最后一个成员的指针域的0改成新申请的静态地址(就是数组位置)
这大致就是我犯的错误了,最后附上我自己写的显示全部数组成员的代码
while(i!=MAXLINKLISTSIZE){ printf("%d:%d ",mainLinklist[i].dataMember,mainLinklist[i].pointerMember); i++; }