[数据结构JAVA版]集合
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 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;ithis.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 链式结构实现集合：
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();
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2015/11/27 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
