描述

在实现单链表的时候，有时可以使用一维数组来表示，静态单链表节点的查找操作是静态单链表数据结构对象操作的重要内容，现在要求用链表实现集合运算：（A-B）∪（B-A）。

假设由终端输入集合元素，先建立表示集合A的静态链表S，而后再输入集合B的元素的同时查找S，若存在和B相同的元素，则从S中删除它，否则将此元素插入到S中。

为了使算法清晰，可以分3个过程完成：a.将整个数组空间初始化成一个链表；b.从备份空间取一个节点；c.将空闲节点链接到备用链表中。(强烈建议使用下面的定义和函数结构)

Void InitSpace_SL(SLinkList &space)

int Malloc_SL(SLinkList &space)

Void Free_SL(SLinkList &space,int k)

Void Difference(SLinkList &space,int &S)

输入

输入有多组测试数据，每组测试数据包括2行，第一行是集合A的内容，第二行是集合B的内容，

输出

用一行输出集合运算后的集合。

样例输入

A = ( W N F P S U )
B = ( F Q H N W X L )
A = ( U C I Z G )
B = ( X N K D Z Y )

样例输出

(A-B)U(B-A) = ( P S U L X H Q )
(A-B)U(B-A) = ( U C I G Y D K N X )

提示

#include <iostream>

#include <stdio.h>

#include <cstring>

#include <algorithm>

using namespace std;

 

typedef struct Node

{

    char c;

    struct Node *next;

}LNode, *List;

 

List init(void)             //初始化单链表

{

    List pH = new LNode;

    pH->next = NULL;

    return pH;

}

 

void Insert(List pH, char s[1000], int n)   //单链表赋值算法

{

    List p = pH;

    int t = 0;

    for(int i = 0; i < n;i++)

    {

                List pNew = new LNode;

                pNew->c = s[i];

                pNew->next = NULL;

                p->next = pNew;

                p = pNew;

    }

}

 

void Show(List pH)    //单链表输出算法

{

    List p = pH->next;

    printf("(A-B)U(B-A) = ( ");

    while(p->next != NULL)

    {

        printf("%c ",p->c);

        p = p->next;

    }

    printf("%c )\n",p->c);

 

}

 

void shaichu(char s[1000], char c[1000])

{

    int i, j;

    int l = strlen(s)-1;

    for(i=6,j=0; i<l; i+=2,j++)

        c[j] = s[i];

    c[j] = '\0';

}

 

void charu(char s[1000], char a[1000], int la, char b[1000], int lb, int &k)

{

    int t;

    for(int i=0; i<la; i++)

    {

        t = 0;

        for(int j=0; j<lb; j++)

        {

            if(a[i] == b[j])

            {

                t = 1;

                break;

            }

        }

        if(t == 0) s[k++] = a[i];

    }

    s[k] = '\0';

}

 

void hebing(char a[1000], char b[1000])

{

    List L = init();

    char s[1000];

    int i = 0;

    int la = strlen(a);

    int lb = strlen(b);

    charu(s,a,la,b,lb,i);

    charu(s,b,lb,a,la,i);

    Insert(L,s,i);

    Show(L);

}

 

int main()

{

    int n, i, t;

    char s[1000], a[1000], b[1000], c;

    while(gets(s))

    {

        shaichu(s,a);

        gets(s);

        shaichu(s,b);

        strrev(b);

        hebing(a,b);

    }

    return 0;

}