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