base on 《数据结构实用教程（Java语言描述）》 徐孝凯 编著
集合接口定义：
package com.chujianyun.agorithm.book.interf;
public interface Set
{
public boolean add(Object obj);//向集合中加入一个元素
public boolean add(int index,Object obj);
public boolean remove(Object obj);//在集合中移除一个元素
public boolean contains(Object obj);//判断一个obj是否属于这个集合
public Object get(int index);//返回角标对应的元素
public boolean set(int index,Object obj);
public int indexOf(Object obj);// 从集合中查找obj查找元素的角标
public int size();//求出集合的长度
public boolean isEmpty();//判断是否为空
public Set union(Set set);//求两个集合的并集并返回
public Set intersection(Set set);//求两个集合的交集
public void clear();//清空所有元素
}
顺序结构实现集合：
package com.chujianyun.agorithm.book.impl;
import com.chujianyun.agorithm.book.interf.Set;
//顺序结构实现的集合
public class SequenceSet implements Set
{
public final int minSize = 10;
private Object[] setArray = null;
private int length = 0;
public SequenceSet()
{
setArray = new Object[minSize];
length = 0;
}
public SequenceSet(int minSize)
{
if(minSize< this.minSize)
{
minSize = this.minSize;
}
setArray = new Object[minSize];
length = 0;
}
/**
* 从集合中加入元素
* @param obj 待添加的元素
*/
@Override
public boolean add(Object obj)
{
//因为集合不许有重复元素，如果重复返回false
for(int i=0;i<length;i++)
{
if(obj.equals(setArray[i]))
{
return false;
}
}
//检查数组空间是否用完，如果用完，重新分配一个更大的数组空间
if(length == setArray.length)
{
Object[] newArray = new Object[length*2];//新数组为原来的数组的两倍
//复制原来的集合
for(int i =0;i<setArray.length;i++)
{
newArray[i] = setArray[i];
}
setArray = newArray;
}
setArray[length++] = obj;
return true;
}
/**
* 指定位置 添加元素
* @param index 角标
* @param obj 欲添加的元素
*
*/
@Override
public boolean add(int index, Object obj) {
//因为集合不许有重复元素，如果重复返回false
for(int i=0;i<length;i++)
{
if(obj.equals(setArray[i]))
{
return false;
}
}
//检查数组空间是否用完，如果用完，重新分配一个更大的数组空间
if(length == setArray.length)
{
Object[] newArray = new Object[length*2];//新数组为原来的数组的两倍
//复制原来的集合
for(int i =0;i<setArray.length;i++)
{
newArray[i] = setArray[i];
}
setArray = newArray;
}
//创建临时数组 添加后的数组
Object[] newArray = new Object[setArray.length+1];//新数组为原来的数组的两倍
for(int i =0;i<newArray.length;i++)
{
if(i < index)
{
newArray[i] = setArray[i];
}else if(i > index)
{
newArray[i] = setArray[i-1];
}
}
newArray[index] = obj;
length++;
setArray = newArray;
return true;
}
/**
* 从集合中删除一个元素
* @param obj 待移除的元素
*/
@Override
public boolean remove(Object obj)
{
//顺序查找待删除的元素
for(int i=0;i<setArray.length;i++)
{
if(obj.equals(setArray[i]))
{
//找到以后 最后一个元素覆盖该元素,并将长度减一
setArray[i] = setArray[--length];
return true;
}
}
return false;
}
/**
* 判断一个元素是否属于此集合
* @param obj 待检测的元素
*/
@Override
public boolean contains(Object obj) {
for(int i=0;i<setArray.length;i++)
{
if(obj.equals(setArray[i]))
{
return true;
}
}
return false;
}
/**
* 返回第i个元素的值
* @param index 角标
* @exception IndexOutOfBoundsException 角标异常
*/
@Override
public Object get(int index) {
if(index<0||index>this.size()-1)
{
throw new IndexOutOfBoundsException();
}
return setArray[index];
}
/**
* 设置对应位置的元素
* @param index 角标
* @param obj 待插入的元素
* @return
*/
@Override
public boolean set(int index, Object obj) {
if(index<0||index>this.size()-1)
{
throw new IndexOutOfBoundsException();
//return false;
}
setArray[index] = obj;
return true;
}
/**
* 从集合中查找元素
* @param obj 待查找的元素
* @return 返回该元素的角标 如果没找到返回-1
*/
@Override
public int indexOf(Object obj) {
for(int i=0;i<length;i++)
{
if(obj.equals(setArray[i]))
{
return i;
}
}
return -1;
}
/**
* 返回集合的长度
*/
@Override
public int size() {
return this.length;
}
/**
* 判断该集合是否为空
*/
@Override
public boolean isEmpty() {
return this.length==0;
}
/**
* 两个集合的并集
* @param set 待合并的集合
* @return 两个集合的并集
*/
@Override
public Set union(Set set) {
//把参数转换为顺序集合类
SequenceSet bSet = (SequenceSet)set;
SequenceSet tempSet = new SequenceSet(length+bSet.size());
//将当前集合中的全部元素复制到新的数组中
for(int i=0;i<length;i++){
tempSet.add(get(i));
}
tempSet.length = this.length;
//在临时集合中一次插入待合并集合的元素
for(int i=0;i<bSet.size();i++)
{
Object x = bSet.get(i);
if(!contains(x))//如果未重复才插入
{
tempSet.setArray[tempSet.length++]=x;
}
}
return tempSet;
}
/**
* 求两个集合的交集
* @param 待求交集的集合
*/
@Override
public Set intersection(Set set) {
//把参数转换为顺序集合类
SequenceSet bSet = (SequenceSet)set;
SequenceSet tempSet = new SequenceSet(length);
for(int i=0;i<length;i++)
{
Object obj = get(i);//获取当前循环出的元素
if(bSet.contains(obj))
{
tempSet.add(obj);
}
}
return tempSet;
}
/**
* 清空所有元素
*/
@Override
public void clear() {
length =0;
setArray = null;
}
/**
* 显示数据
*/
@Override
public String toString() {
StringBuffer sb = new StringBuffer();
sb.append("{");
for(int i=0;i<length;i++)
{
sb.append(setArray[i]);
if(i != length-1)
{
sb.append(",");
}
}
sb.append("}");
return sb.toString();
}
}
链式结构实现集合：
package com.chujianyun.agorithm.book.impl;
import com.chujianyun.agorithm.book.interf.Set;
import com.chujianyun.agorithm.entity.Node;
//链表方式的集合
public class LinkedSet implements Set
{
private Node head = null;//头指针
private int length = 0;//链表长度（集合长度）
public LinkedSet()
{
//创建一个由head指向的一个附加头结点 该节点next为空 表示初始化为一个空链表
head = new Node(null);
length = 0;
}
/**
* 把obj插入到集合单链表的末尾
* @param obj 待插入的节点
* @return 返回是否插入成功
*/
@Override
public boolean add(Object obj) {
Node tempNode = head;
//如果已经存在则返回false
while(tempNode.getNext()!=null)
{
if(tempNode.getNext().getElement().equals(obj))
{
return false;
}else
{
tempNode = tempNode.getNext();
}
}
//如果不存在插入新节点
Node newNode = new Node(obj,null);
tempNode.setNext(newNode);
length++;//个数加1
return true;
}
/**
* 移除指定元素
* @param obj 待移除的元素
* @return 返回是否成功
*/
@Override
public boolean remove(Object obj) {
Node tempNode = head;
//循环查找该节点
while(tempNode.getNext()!=null)
{
if(tempNode.getNext().getElement().equals(obj))
{
//找到 欲删除的节点
tempNode.setNext(tempNode.getNext().getNext());
length--;
return true;
}else
{
tempNode = tempNode.getNext();
}
}
return false;
}
/**
* 判断是否包含某个元素
* @param obj 欲判断的元素
* @return 是否包含某元素
*/
@Override
public boolean contains(Object obj) {
Node tempNode = head;
while(tempNode.getNext()!=null)
{
if(tempNode.getNext().getElement().equals(obj))
{
return true;
}else
{
tempNode = tempNode.getNext();
}
}
return false;
}
/**
* 获取某个位置的元素（起始角标为0）
* @param index 位置
* @return 该位置的元素
*/
@Override
public Object get(int index) {
if(index<0||index>length-1)
{
throw new IndexOutOfBoundsException();
}
int current =0;
Node tempNode = head;
while(tempNode.getNext()!=null)
{
if(current == index)
{
return tempNode.getElement();
}else
{
current++;
tempNode = tempNode.getNext();
}
}
return -1;
}
/**
* 在指定位置添加元素
* @param index 角标
* @param obj 欲添加的元素
* @return 是否成功
*/
@Override
public boolean set(int index, Object obj) {
if(index<0||index>length-1)
{
throw new IndexOutOfBoundsException();
}
Node tempNode = head;
int current =0;
while(tempNode.getNext()!=null)
{
if(current == index)
{
tempNode.getNext().setElement(obj);
return true;
}else
{
tempNode = tempNode.getNext();
}
current++;
}
length++;
return false;
}
/**
* 在某个位置插入元素
* @param index 角标
* @param obj 欲插入的元素
* @return
*/
public boolean add(int index,Object obj)
{
if(index<0||index>length-1)
{
throw new IndexOutOfBoundsException();
}
Node tempNode = head;
int current =0;
while(tempNode.getNext()!=null)
{
if(current == index)
{
Node newNode = new Node(obj,tempNode.getNext());
tempNode.setNext(newNode);
length++;
return true;
}else
{
tempNode = tempNode.getNext();
}
current++;
}
return false;
}
@Override
public int indexOf(Object obj) {
Node tempNode = head;
int current =0;
while(tempNode.getNext()!=null)
{
if(tempNode.getNext().equals(obj))
{
return current;
}else
{
tempNode = tempNode.getNext();
}
current++;
}
return -1;
}
/**
* 链表的长度
*/
@Override
public int size() {
return length;
}
//链表是否为空
@Override
public boolean isEmpty() {
return length==0;
}
/**
* 两个链表集合求并集
* @param 待合并的集合
* @return 返回合并后的集合
*/
@Override
public Set union(Set set) {
//初始化一个 链表类型的集合 用来存放合并后的链表
LinkedSet tempLinkedSet = new LinkedSet();
Node tempNode = head;//指向 当前链表的头结点
//指向 合并后的链表类型的集合的头指针域
Node tempLinkedSetPointer = tempLinkedSet.getHead();
//先将本集合 写入合并后的集合里
//循环当前集合
while(tempNode.getNext()!=null)
{
//将新节点放入新链表末尾
tempLinkedSetPointer.setNext(new Node(tempNode.getNext().getElement(),null));
//将指针指向新节点
tempLinkedSetPointer = tempLinkedSetPointer.getNext();
//将指针移向下一个节点
tempNode = tempNode.getNext();
}
//置新链表长度
tempLinkedSet.setLength(length);
//将带合并的链表写入临时链表后面
LinkedSet dLinkedSet = (LinkedSet)set;
tempNode = dLinkedSet.getHead();
while(tempNode.getNext() != null)
{
//注意需去重复
Object obj = tempNode.getNext().getElement();
if(!this.contains(obj))
{
//插入到并集链表结尾
tempLinkedSetPointer.setNext(new Node(obj,null));
//指向新链表的结尾
tempLinkedSetPointer=tempLinkedSetPointer.getNext();
//新链表长度+1
tempLinkedSet.setLength(tempLinkedSet.getLength()+1);
}
tempNode = tempNode.getNext();
}
return tempLinkedSet;
}
/**
* 请当前链表和传入链表集合的交集
* @param 待交集的集合
* @return 交集
*/
@Override
public Set intersection(Set set) {
LinkedSet dLinkedSet = (LinkedSet) set;//将欲合并的集合强转为链表类型的集合
LinkedSet tempLinkedSet = new LinkedSet();//新集合用来存放交集
Node tempLinkedSetPointer = tempLinkedSet.getHead();
Node linkedSetPointer = head;//定义“指针” 指向 当前集合的“头指针”
//循环当前链表集合
while(linkedSetPointer.getNext() != null){
//判断待交集的集合内是否包含 当前节点
if(dLinkedSet.contains(linkedSetPointer.getNext().getElement())) {
//为 当前 新结合 添加新节点
tempLinkedSetPointer.setNext(new Node(linkedSetPointer.getNext().getElement(),null));
//新集合转到下一个节点
tempLinkedSetPointer = tempLinkedSetPointer.getNext();
//置新节点的长度
tempLinkedSet.setLength(tempLinkedSet.getLength()+1);
}
//当前集合移至下一个节点
linkedSetPointer = linkedSetPointer.getNext();
}
return tempLinkedSet;
}
/**
* 清空链表
*/
@Override
public void clear() {
length = 0;
head.setNext(null);
}
public Node getHead() {
return head;
}
public void setHead(Node head) {
this.head = head;
}
public int getLength() {
return length;
}
public void setLength(int length) {
this.length = length;
}
@Override
public String toString()
{
StringBuffer sb = new StringBuffer();
Node pointer = head;
while(pointer.getNext()!=null)
{
sb.append(pointer.getNext().getElement().toString()+" ");
pointer = pointer.getNext();
}
return sb.toString();
}
}
原文链接：https://blog.csdn.net/w605283073/article/details/50072353
本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。
还没有人抢沙发呢~