静态链表实现(A-B)+(B-A)【代码】

-----------------------------------------------第一次发代码，写在前面------------------------------------------------------

思路不完全等同于严师太的课本，所以代码并不是参照课本。

代码参照《大话数据结构》相应章节，并经过了相应修改

注意：链表下标为i的节点和链表中第i个节点在链表初始化后是一样的，但是在经过删除操作后不一样了。

为此本人在这里浪费了很多时间调试。注意细节。

代码可有某些地方有瑕疵，但是通过了C::B跑了几组数据，应该没大问题。

共同学习，共同进步！

 

-----------------------------------------------以下摘自《大话数据结构》----------------------------------------------------

在静态链表中，每一个结点包含两部分内容，一部分是data（即有意义的数据），另一部分是cur（存储该元素下一个元素所在数组对应的下标）。

有几个特殊的结点：

首先是下标为0的结点中不包含有意义的数据，它的cur存储的是备用链表（即没有存储的数据的那些结点）第一个结点的下标。如上图2所示，数组第一个元素的cur存放的是7。

其次是数组最后一个元素，数组最后一个元素的cur存放的是静态链表的第一个结点的下标（此处的第一个结点，是指有实质意义的数据的结点）。

最后就是链表的最后一个元素（并不一定是数组的最后一个元素），链表最后一个元素的cur一般存放0，表示它后面的结点为空了。

 

---------------------------------------------代码如下---------------------------------------------------------

 

#include 

using namespace std;

#define MAXSIZE 100

typedef struct
{
int data;
int cur;
}component,SLinkList[MAXSIZE];


int InitSpace_SL(SLinkList& space)
{
for(int i=0;i1;i++) space[i].cur=i+1;
space[MAXSIZE-1].cur=0;
return 0;
}


int LocateElem_SL(SLinkList &S,int e)//在静态链表中查找第一个值为e的元素，若找到，则返回它在线性表中的位序，否则返回0;
{
int i=S[MAXSIZE-1].cur;
while(i&&S[i].data!=e)
i=S[i].cur;
if(!i) return 0;
else return i;
}


int ListLength_SL(SLinkList& L)
{
int j=0;
int i=L[MAXSIZE-1].cur;
while(i)
{
i=L[i].cur;
j++;
}
return j;
}


int Malloc_SL(SLinkList &space)
{
int i=space[0].cur;
if(space[0].cur) space[0].cur=space[i].cur;
return i;
}


int Free_SL(SLinkList &space,int k)//把下标为k的空闲节点回收到备用链表，该节点成为备用链表中的首节点
{
space[k].cur=space[0].cur;
space[0].cur=k;
return 0;
}

int ListInsert_SL(SLinkList &L,int i,int e)//在L中第i个元素之前插入新的元素e
{
int j,k,l;
k=MAXSIZE-1;//k为数组最后一个元素的下标
if(i<1||i>ListLength_SL(L)+1) return 0;
j=Malloc_SL(L);
if(j)//L不为空表
{
L[j].data=e;
for(l=1;l<=i-1;i++)
k=L[k].cur;
L[j].cur=L[k].cur;
L[k].cur=j;
}
return 0;
}


int ListInsert2_SL(SLinkList &L,int e)//在备用链表表头插入一个元素
{
int i,j=L[MAXSIZE-1].cur,k=Malloc_SL(L);
for(i=1;i< ListLength_SL(L);i++)
j=L[j].cur;
L[j].cur=k;
L[k].data=e;
L[0].cur=L[k].cur;
L[k].cur=0;
return 0;
}

 

int ListDelete_SL(SLinkList &L,int i)//删除在L中的第i个元素e
{
int j,k;
if(i<1||i>ListLength_SL(L)) return 0;
k=MAXSIZE-1;
for(j=1;j<=i-1;j++)
k=L[k].cur;
j=L[k].cur;
L[k].cur=L[j].cur;
Free_SL(L,j);
return 0;
}


int ListDelete2_SL(SLinkList &L,int i)//删除在L中下标为i的元素L[i]
{
int k=L[MAXSIZE-1].cur,m=L[k].cur;
int j=L[0].cur;
while(m!=i)
{
k=L[k].cur;
m=L[k].cur;
}
L[k].cur=L[m].cur;
L[0].cur=i;
L[i].cur=j;
return 0;
}
int MergeList_SL(SLinkList &L1,SLinkList &L2)//(A-B)+(B-A)
{
int i=L2[MAXSIZE-1].cur;
int m;
while(i)
{
m=0;
int j=L1[MAXSIZE-1].cur;
while(j)
{
m=LocateElem_SL(L1,L2[i].data);
if(m) {ListDelete2_SL(L1,m);break;}
j=L1[j].cur;
}
if(!m) ListInsert2_SL(L1,L2[i].data);
i=L2[i].cur;
}
return 0;
}


int main()
{
int m,n,j;
SLinkList L1,L2;
InitSpace_SL(L1);
InitSpace_SL(L2);
cout<<"输入集合A中的元素个数："<<endl;
cin>>m;
cout<<"输入集合A中各元素的值："<<endl;
for(int i=1;i<=m;i++)
{
cin>>L1[i].data;
L1[0].cur=L1[i].cur;
}
L1[m].cur=0;
L1[MAXSIZE-1].cur=1;
cout<<"输入集合B中的元素个数："<<endl;
cin>>n;
cout<<"输入集合B中各元素的值："<<endl;
for(int i=1;i<=n;i++)
{
cin>>L2[i].data;
L2[0].cur=L2[i].cur;L2[MAXSIZE-1].cur=1;
}
L2[n].cur=0;
L2[MAXSIZE-1].cur=1;
MergeList_SL(L1,L2);
j=L1[MAXSIZE-1].cur;
while(j)
{
cout<" ";
j=L1[j].cur;
}
return 0;
}

 

 

-----XJX