Java集合并交差运算.doc

一、题目要求：
用Java语言实现单链表的基本操作，并实现集合的交、并和差运算。

二、程序功能定义：
1、输出两个集合的交集，即找出两个集合的相同元素。
2、输出两个集合的并集，即把两个集合的全部元素不重复的加起来。
3、输出两个集合的差集，即从一个集合中找出另一个集合里没有的元素。

三、设计思路：
程序1：单链表结点
public class Node<T> //单链表结点类，T指定结点的元素类型
{
public T data; //数据域，保存数据元素
public Node<T> next; //地址域，引用后继结点
public Node(T data, Node<T> next) //构造结点，data指定数据元素，next指定后继结点
{
this.data = data;
this.next = next;
}
public Node()
{
this(null, null);
}
}

程序2：
import java.util.ArrayList;
public class SinglyList<T>
{
public Node<T> head;
public int length;
//以上为默认构造方法，构造空单链表
public static ArrayList<String> union=new ArrayList<String>();
public SinglyList()
{
this.head = new Node<T>();
}
//以上为构造单链表
public SinglyList(T[] element)
{
this(); //创建空单链表，只有头结点
this.length = element.length;
Node<T> rear = this.head; //rear指向单链表最后一个结点
for (int i = 0; i < element.length; i++)
//若element==null，跑出空对象异常；element.length==0时，构造空链表
{
rear.next = new Node<T>(element[i], null); //创建结点链入rear结点之后
rear = rear.next; //rear指向性的链尾结点
}
}

public String toString()
{
String str = "(";
Node<T> p = this.head.next;
while (p != null)
{
str += p.data.toString();
if (p.next != null)
{
str += ",";
} //不是最后一个结点时，后加分隔符
p = p.next;
}
return str + ")"; //空表返回()
}

public String addAll(SinglyList list)
{
Node<T> p = this.head.next;
String str = "(";
while (p != null)
{
Node<T> q = list.head.next;
while (q != null)
{
if ( p.data.toString().equals(q.data.toString())) //集合的元素值相等
{
if (!str.equals("("))
{
str += ",";
} //用逗号间隔
str += p.data.toString();
this.union.add(p.data.toString()) ;
}
q = q.next;
}
p = p.next;
}
return str + ")";
}
//以上为求交集过程。
public String union(SinglyList list)
{
Node<T> p = this.head.next;
String str = "(";
while (p != null)
{
Node<T> q = list.head.next;
int i = 0;
while (q != null)
{
if (!p.data.toString().equals(q.data.toString()))
{
i++;
if (i == list.length)
{
for(int a=0;a<union.size();a++)
{
if( !p.data.toString().equals(union.get(a))&a==union.size()-1)
{
if (!str.equals("(")) str += ",";
str += p.data.toString();
}
}
}
}
q = q.next;
}
p = p.next;
i = 0;
}
Node<T> w = list.head.next;
while (w != null)
{
str += ",";
str += w.data.toString();
w = w.next;
}
return str + ")";
}
//以上为求并集过程。
public String difference(SinglyList list)
{
Node<T> p = this.head.next;
String str = "(";
while (p != null)
{
Node<T> q = list.head.next;
int i = 0;
while (q != null)
{
if ( !p.data.toString().equals(q.data.toString()))
{
i++;
if (i == list.length)
{
if (!str.equals("(")) str += ",";
str += p.data.toString();
}
}
q = q.next;
}
p = p.next;
i = 0;
}
return str + ")";
}
}
//以上为求差集过程。

程序3：
import java.util.Scanner;
public class MainClass
{
public static void main(String[] args)
{
int a, b;
Scanner cin = new Scanner(System.in);
System.out.print("请输入集合A的元素（用英文逗号间隔）：");
String a_string=cin.nextLine();
String[] suma=a_string.split(",");
System.out.print("请输入集合B的元素（用英文逗号间隔）：");
String b_string=cin.nextLine();
String[] sumb=b_string.split(",");
SinglyList<String> list1 = new SinglyList<String>(suma);
SinglyList<String> list2 = new SinglyList<String>(sumb);
System.out.println("集合A和集合B的交集为："+list1.addAll(list2));
System.out.println("集合A和集合B的并集为："+list1.union(list2));
System.out.println("A与B的差集为："+list1.difference(list2));
System.out.println("B与A的差集为："+list2.difference(list1));
}
}

四、程序运行输出图：