关于静态链表实现 (A-B)U(B-A)

所谓(A-B)U(B-A)，实际上就是A独有的那一部分和B独有的那一部分的并集

也就是简简单单的如图所示

其实这个问题本身用动态链表（就是常规链表）是很好解决的，但是由于我们要用静态链表来实现，所以就会显得略微有一些麻烦，到底哪里麻烦？

1. 相对于动态链表，静态链表的内存分配函数需要自己来实现
2. 相对于动态链表，静态链表的内存回收函数需要自己来实现.
3. 静态链表的连接方式，和动态链表也有所不同
4. 静态链表在实际操作中比动态链表更容易断（人为因素）

首先大概说一下答题思想吧，如果想先把两个链表建立起来在互相查找删减，实现会很麻烦，因此我采用的方法是：首先我完全建立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++;
    }