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

一时失言乱红尘 2022-05-14 15:51 278阅读 0赞

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

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

**静态链表的存储结构**

#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;
    }

静态链表的练习：[静态链表——UVA11988(破损键盘)][UVA11988]

[UVA11988]: https://blog.csdn.net/sinat_38816924/article/details/83475233