关于静态链表的问题！
这是一个集合运算的算法（A-B)U(B-A)
运行出错了 请大家帮我分析一下；
#define TRUE1
#define FALSE0
#defineOK1
#define ERROR0
#define INFEAIBLE-1
#define OVERFLOW-2
#define MAXSIZE 100
typedef int ElemType;
typedef int status;
typedef struct component{
ElemType data;
int cur;
}SLinkList[MAXSIZE];
void InitSpace_SL(SLinkList *space)
{
for(int i=0;i <MAXSIZE-1;i++)
{
space[i]-> cur=i+1;
}
space[MAXSIZE-1]-> cur=0;
}//InitSpace_SL
status Malloc_SL(SLinkList *space)
{
int i;
i=space[0]-> cur;
space[0]-> cur=space[i]-> cur;
return i;
}//Malloc_SL 从备用链表返回一个空闲的节点下标，
status FreeSpace_SL(SLinkList *space,int i)
{
space[i]-> cur=space[0]-> cur;
space[0]-> cur=i;
return OK;
}//FreeSpace_SL 回收一个节点到备用链表
void Difference(SLinkList *space,int *s)
{
int m,n,j,r,k,p,i;
ElemType e;
InitSpace_SL(space);
*s=Malloc_SL(space);
r=*s; //r指向s的当前最后一个元素；
printf( "请输入集合A和B的个数，用空格隔开:\n ");
scanf( "%d %d ",&m,&n);
for(i=0;i <m;i++)
{
printf( "请输入集合A的第%d个元素:\n ",i+1);
j=Malloc_SL(space);
scanf( "%d ",&space[j]-> data);
space[r]-> cur=j;
r=j;
}
space[r]-> cur=0;
for(i=0;i <n;i++)
{
printf( "请输入集合B的第%d个元素\n ",i+1);
scanf( "%d ",&e);
k=*s;
p=space[k]-> cur;
while(space[p]-> data!=e&&p!=space[r]-> cur)
{
k=p;
p=space[k]-> cur;
}
if(k==space[r]-> cur)
{
j=Malloc_SL(space);
space[j]-> data=e;
space[j]-> cur=space[r]-> cur;
space[r]-> cur=j;
}
else
{
space[k]-> cur=space[p]-> cur;
FreeSpace_SL(space,p);
if(p==r)
r=k;
}
}
}//Difference
void main()
{
int s;
SLinkList space;
InitSpace_SL(&space);
Difference(&space,&s);
}
[解决办法]
SLinkList已经是一个指针了, 指向一个数组.
而InitSpace_SL函数应改为:
void InitSpace_SL(SLinkList space)
{
for(int i=0; i <MAXSIZE-1; i++)
{
space[i].cur=i+1;
}
space[MAXSIZE-1].cur=0;
}//InitSpace_SL
改后是可以运行, 但有没有正确, 我想其它函数可能也有这个问题
[解决办法]
LZ这个算法是有问题的。在A组或B组有重叠元素存在的情况下，算法是完全错误的。Anyway, 我把LZ的code改了一下，在组内没有重叠元素的情况下，应该是没有问题了。
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEAIBLE -1
#define OVERFLOW -2
#define MAXSIZE 100
typedef int ElemType;
typedef int status;
typedef struct component{
ElemType data;
int next;
}SLinkList[MAXSIZE];
void InitSpace_SL(SLinkList &space)
{
for(int i=0;i <MAXSIZE-1;i++)
{
space[i].next=i+1;
}
space[MAXSIZE-1].next=0;
}//InitSpace_SL
// put the first free node into the chain
status Malloc_SL(SLinkList &space)
{
int i; // i is the first available node
i=space[0].next;
space[0].next=space[i].next;
return i;
}//Malloc_SL
// recycle the deleted node
// and set it as the head of the free node chain
status FreeSpace_SL(SLinkList &space,int i)
{
space[i].next=space[0].next;
space[0].next=i;
return OK;
}//FreeSpace_SL
void Difference(SLinkList &space,int &head)
{
int m,n,j,end,index,prev, i;
ElemType e;
InitSpace_SL(space);
head=1;
index=head;
printf( "please input number of set A and B, seperated by space:\n ");
scanf( "%d %d ",&m,&n);
for(i=0;i <m;i++)
{
//printf( "Please input the %dth number of set A:\n ",i+1);
j=Malloc_SL(space);
scanf( "%d ",&space[j].data);
space[index].next=j;
index=j;
}
end = index;
space[end].next=0;
for(i=0;i <n;i++)
{
//printf( "Please input the %dth number of set B\n ",i+1);
scanf( "%d ",&e);
if(head==0) { // empty chain
j = Malloc_SL(space);
head = j;
space[j].next = 0;
end = j;
continue;
}
index=head;
while(space[index].data!=e && space[index].next!=0)
{
prev = index;
index=space[index].next;
}
if(space[index].data != e) // not found
{
end = index;
j=Malloc_SL(space);
space[j].data=e;
space[j].next=space[end].next;
space[end].next=j;
end=j;
}
else // found it
{
// is it the only node?
if(head == end) {
head = 0;
FreeSpace_SL(space, index);
continue;
}
// is it the head
else if(index == head) {
head = space[head].next;
FreeSpace_SL(space, index);
continue;
}
space[prev].next=space[index].next;
FreeSpace_SL(space,index);
if(index==end)
end=prev;
}
}
}//Difference
void main()
{
int head;
SLinkList space;
InitSpace_SL(space);
Difference(space, head);
printf( "\nlet 's print out the result:\n ");
if(head == 0) {
printf( "Oops, empety set! ");
return;
}
int index = head;
while(space[index].next != 0) {
printf( "%d ", space[index].data);
index = space[index].next;
}
printf( "%d\n ", space[index].data);
}
