main.cpp

用游标的方法实现对称差的计算

#include <iostream>  //用游标实现对称差的计算
using namespace std;
#define MAX 30

struct spacestr
{
    char x;
    int next;
};
void initialize(spacestr Space[]);  //用于对空间进行初始化
void func(spacestr Space[],int Lhead,int n1,int n2);  //用于实现对称差计算及输出

int main()
{
    spacestr Space[MAX];
    int i=0,j=0;
    int n1,n2;  //n1，n2分别为A,B的元素个数
    initialize(Space);  //调用函数初始化空间

    cout<<"请输入集合A的元素个数"<<endl;
    cin>>n1;

    cout<<"请输入集合B的元素个数"<<endl;
    cin>>n2;
    cout<<"请输入集合A"<<endl;

    for (;i<n1;i++)
    {

        cin>>Space[i].x;  //给A分配空间0到n1-1
    }

    cout<<"请输入集合B"<<endl;
    for (j=n1;j<n1+n2;j++)
    {
        cin>>Space[j].x;  //给B分配空间n1到n1+n2-1
    }
    cout<<endl;
    cout<<"(A-B)+(B-A)的结果为"<<endl;
    func(Space,0,n1,n2);  //计算A-B
    func(Space,n1,n1,n2);  //计算B-A
    return 0;
}

void initialize(spacestr Space[])  //将next按1至30顺序存储，最后一个存-1
{
    int i=0;
    for (;i<MAX;i++)
    {
        Space[i].next=i+1;
    }
    Space[i].next=-1;
}



void func(spacestr Space[],int Lhead,int n1,int n2)
{
    int AddHead=n1+n2;
    int k=AddHead,p=0;
    int m=Lhead,h=n1+n2-1;

    if (Lhead==0)  //计算A-B的情况

    {
        for (;m<n1;m++,k++)  //将A中元素全部存入空闲空间n1+n2到2*n1+n2
        {

            Space[k].x=Space[m].x;
        }
        Space[k-1].next=-1;  //最后一个元素对应的next存-1

        for (k=AddHead;k<AddHead+n1;k++)
        {
            for (m=n1;m<AddHead;m++)
            {
                if (Space[k].x!=Space[m].x)continue; //如果A中执行到的该元素与B集合交集为空，则跳过本次循环
                else          //否则需去掉该点
                {
                    p=k-1;
                    while (Space[p].next==0)  //如果需去掉的点的上一个元素也被去掉了，则下一元素地址传给最邻近的一个未被去掉的点对应next
                    {
                        p-=1;
                    }

                    Space[p].next=Space[k].next;
                    Space[k].next=0;  //为需去掉的点对应next置零
                    break;  //跳出该循环

                }
            }

        }
    }

    if (Lhead==n1)

    {
        for (;m<Lhead+n2;m++,k++)  //将B中元素全部存入空闲空间n1+n2到2*n2+n1
        {

            Space[k].x=Space[m].x;
            Space[k-1].next=k;
        }
        Space[k-1].next=-1;  //最后一个元素对应的next存-1
        for (k=AddHead;k<AddHead+n2;k++)
        {
            for (m=0;m<n1;m++)
            {
                if (Space[k].x!=Space[m].x)continue;  //如果B中执行到的该元素与A集合交集为空，则跳过本次循环
                else  //否则需去掉该点
                {
                    p=k-1;
                    while (Space[p].next==0) //如果需去掉的点的上一个元素也被去掉了，则下一元素地址传给最邻近的一个未被去掉的点对应next
                    {
                        p-=1;
                    }

                    Space[p].next=Space[k].next;
                    Space[k].next=0; //为需去掉的点对应next置零

                    break; //跳出该循环
                }

            }
        }
    }

    while (Space[h].next!=-1)  //输出最后结果
    {
        if (Space[h].next!=0)
        {

            h=Space[h].next;

            cout<<Space[h].x<<"   ";

        }

    }

}