静态链表——集合运算（A-B）U（B-A）-蒲公英云

静态链表——集合运算（A-B）U（B-A）

来源：严蔚敏《数据结构》（书上讲的很清楚）

先介绍静态链表，再以例题的形式展示。

静态链表的存储结构

#define maxn 15
struct space
{
    int cur;
    int key; 
}s[maxn];

这种描述方便在于，不设“指针”类型的高级程序设计语言中使用链表结构。

在上面的结构中，一个分量表示一个节点，同时用游标cur代替指针指示节点在数组中的位置。

数组的零分量可以看成头结点，其指针域指示链表的第一个节点。

做线性表的插入和删除的时候，不需要移动元素，只需要修改指针。具有链式存储的优点。

思考：下面遍历的时候，为什么用i=s[i].cur;

int LocateElem_SL(SLinkList *s,ElemType e)
{
    //在静态链表中查找第一个值为e的元素
    //若找到，则返回它在链表中的位置，否则返回0 
    i=s[0].cur;
    while(i&&s[i].date!=e)
        i=s[i].cur;
    return i;
}
    假设，s\[0\].cur指示第一个节点在数组中的位置。若设i=s\[0\].cur，则s\[i\].date存储线性表的第一个元素，s\[i\].cur指示第二个节点在数组中的位置。
    一般请款下，若第i个分量节点的第k个节点，则s\[i\].cur指示第k+1个节点的位置。
   因此，静态链表中实现线性表的操作和动态链表相似。i=s\[i\].cur的操作实为指针的后移（类似p=p->next）。

下面以集合（A-B）U（B-A）为例，讨论静态链表的算法。

    题目：在终端输入集合元素，先建立表示集合A的静态链表S，然后输入集合B的元素，同时查找S表。若存在和B相同的元素，则从S表中删除，否则将此元素插入S中。
   思路：将整个数组空间初始化成一个链表。从备用空间中取得一个节点。将空闲的节点链接到备用链表中。
#include<stdio.h>
#define maxn 15
struct space
{
    int cur;
    int key; 
}s[maxn];
void InitSpace_SL(struct space *s)//n+1为静态链表的长度 
{
    int i;
    for(i=0;i<maxn-1;i++)
        s[i].cur=i+1;
    s[maxn-1].cur=0;
}
int Malloc_SL(struct space *s)
{
    int    i=s[0].cur;
    if(i)
        s[0].cur=s[i].cur;
    return i;
} 
void free_SL(struct space *s,int k)//将下标为k的节点回收 
{
    s[k].cur=s[0].cur;
    s[0].cur=k;
}
void PrintSpace_SL(struct space *s)
{
    int i;
    for(i=s[1].cur;i!=0;i=s[i].cur)//第一个里面不存东西 
        printf("%d ",s[i].key);
    printf("\n");
}
void different(struct space *s)
{
    InitSpace_SL(s);
    int head=Malloc_SL(s);
    int last=head;
    int i,j,k;
    int m,n;
    scanf("%d%d",&m,&n);//输入集合A和集合B的元素的个数
    for(j=1;j<=m;j++)//建立集合A的链表 
    {
        i=Malloc_SL(s);//分配节点 
        scanf("%d",&s[i].key);
        s[last].cur=i;//插入表尾 
        last=i; 
    } 
    s[last].cur=0;
    //PrintSpace_SL(s);
    int b;
    for(j=1;j<=n;j++)
    {
        scanf("%d",&b);
        int p=head;
        k=s[head].cur;
        while(k&&s[k].key!=b)
        {
            p=k;
            k=s[k].cur;
        }
        if(k==0)
        {
            i=Malloc_SL(s);
            s[i].key=b;
            s[i].cur=0;
            s[last].cur=i;
            last=i;
        }
        else
        {
            s[p].cur=s[k].cur;
            free_SL(s,k);
        }
    } 
}
int main()
{
    different(s);
    PrintSpace_SL(s);
    return 0;
}