线性表的顺序实现_JAVA_编程开发_程序员俱乐部

? ? ? ?数据结构和算法是程序的灵魂，基本的数据结构分为：线性结构、树、图。线性结构又分为顺序实现的线性结构和链式实现的线性结构。顺序实现的线性结构是一种随机存取结构，适合遍历，寻找元素；而不适合插入和caozuo.html" target="_blank">删除操作。其get()、set()的时间复杂度为O(1)，而插入和删除的时间复杂度为O(N)。使用java语言实现顺序存储的线性结构代码如下：

class="java">线性表的抽象数据类型

package dataStructtion.linear;
/**
 * 线性表的抽象数据类型
 * @author xiucai
 * @param <T>
 */
public interface LList<T> {
	/**
	 * 判断是否为空
	 * @return
	 */
	public boolean isEmpty();
	/**
	 * 返回线性表长度
	 * @return
	 */
	public int length();
	/**
	 * 返回下标为i的元素(i>=0)
	 * @param i
	 * @return
	 */
	public T get(int i);
	/**
	 * 设置下标为i的元素值为t
	 * @param i
	 * @param t
	 */
	public void set(int i,T t);
	/**
	 * 在下标为i的位置插入元素t
	 * @param i
	 * @param t
	 */
	public void insert(int i,T t);
	/**
	 * 在线性表末尾追加元素t
	 * @param t
	 */
	public void append(T t);
	/**
	 * 移除下标为i的元素
	 * @param i
	 * @return
	 */
	public T remove(int i);
	/**
	 * 移除线性表所有元素
	 */
	public void removeAll();
	/**
	 * 查找，返回首次出现的关键字为key的元素
	 * @param t
	 * @return
	 */
	public T search(T t);
	/**
	 * 判断线性表是否包含元素t
	 * @param t
	 * @return
	 */
	public boolean contain(T t);
}




顺序存储的线性表的实现：

package dataStructtion.linear;
/**
 * 线性表的顺序表示和实现
 * @author xiucai
 * @param <T>
 */
public class SeqList<T> implements LList<T>{
	private Object[] element;//对象数组
	private int len;//顺序表长度，记录元素个数
	/**
	 * 构造方法，初始化为size长度
	 * @param size
	 */
	public SeqList(int size){
		this.element=new Object[size];
		this.len=0;
	}
	/**
	 * 默认构造长度为64的数组
	 */
	public SeqList(){
		this(64);
	}
	/**
	 * 重写toString方法，用于输出
	 */
	@Override
	public String toString(){
		String string="";
		if(this.len==0)
			return string;
		for(int i=0;i<this.len;i++)
			string+=element[i].toString()+" ";
		return string;
		
	}
	/**
	 * 重写equals方法，用于比较
	 */
	@Override
	public boolean equals(Object obj) {
		// TODO Auto-generated method stub
		boolean flag=true;
		if(this==obj)
			return flag;
		if(obj instanceof SeqList){
			SeqList<T> t=(SeqList<T>)obj;
			if(this.len==t.len){
				for(int i=0;i<this.len;i++){
					if(this.element[i]!=t.element[i]){
						flag=false;
					}
				}
			}else
				return false;
		}else 
			return false;
		return flag;
		
	}
	/**
	 * 判断线性表是否为空
	 */
	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return this.len==0;
	}
	/**
	 * 线性表的长度
	 */
	@Override
	public int length() {
		// TODO Auto-generated method stub
		return this.len;
	}
	/**
	 * 获取下标为i的元素
	 */
	@Override
	public T get(int i) {
		// TODO Auto-generated method stub
		if(i>=0&&i<this.len)
			return (T)element[i];
		else throw new IndexOutOfBoundsException(i+",下标越界");
	}
	/**
	 * 设置小标为i的元素为t
	 */
	@Override
	public void set(int i, T t) {
		// TODO Auto-generated method stub
		if(t==null) return;
		if(i>=0&&i<this.len)
			this.element[i]=t;
		else throw new IndexOutOfBoundsException(i+",下标越界");
	}
	/**
	 * 在下标为i的位置设置元素t，其他元素依次后移
	 */
	@Override
	public void insert(int i, T t) {
		// TODO Auto-generated method stub
		if(t==null) return ;
		if(this.len==element.length){
			Object[] temp=this.element;
			this.element=new Object[temp.length*2];
			for(int j=0;j<temp.length;j++){
				element[i]=temp[i];
			}
		}
		i=i<0?0:i>this.len?len:i;
		for(int j=this.len-1;j>=i;j--)
			this.element[j+1]=this.element[j];
		this.element[i]=t;
		this.len++;
	}
	/**
	 * 线性表末尾追加元素t
	 */
	@Override
	public void append(T t) {
		// TODO Auto-generated method stub
		insert(this.len, t);
	}
	/**
	 * 移除下表为i的元素，剩下元素依次前移
	 */
	@Override
	public T remove(int i) {
		// TODO Auto-generated method stub
		if(i<0||i>this.len-1)
			return null;
		T t=(T)this.element[i];
		for(int j=i;j<this.len;j++)
			this.element[j]=this.element[j+1];
		this.element[this.len-1]=null;
		this.len--;
		return t;
	}
	/**
	 * 清空线性表
	 */
	@Override
	public void removeAll() {
		// TODO Auto-generated method stub
		for(int i=0;i<this.len;i++)
			this.element[i]=null;
		this.len=0;
	}
	/**
	 * 搜索key为t的元素
	 */
	@Override
	public T search(T t) {
		// TODO Auto-generated method stub
		if(t==null)
			return null;
		for(int i=0;i<this.len;i++){
			if(element[i].equals(t))
				return (T)element[i];
		}
		return null;
	}
	/**
	 * 判断线性表是否包含元素t
	 */
	@Override
	public boolean contain(T t) {
		// TODO Auto-generated method stub
		return this.search(t)!=null;
	}

}





测试类：

package dataStructtion.linear;
/**
 * 此类进行测试
 * @author xiucai
 *
 */
public class SeqTest {
	public static void main(String[] args) {
		SeqList<String> seqList=new SeqList<String>();
		System.out.println(seqList.isEmpty());
		System.out.println(seqList.length());
		seqList.insert(0, "aaa");
		System.out.println(seqList);
		seqList.insert(1,"bbb");
		System.out.println(seqList);
		seqList.insert(0,"ccc");
		System.out.println(seqList);
		System.out.println(seqList.length());
//		System.out.println(seqList.get(4));
		seqList.set(0, "ddd");
		System.out.println(seqList);
		seqList.remove(0);
		System.out.println(seqList);
		seqList.append("ccc");
		System.out.println(seqList);
		System.out.println(seqList.contain("aaa"));
		System.out.println(seqList.search("bbb"));
		seqList.removeAll();
		System.out.println(seqList);
	}
}

?

?

• SeqList.zip (2.3 KB)
• 下载次数: 0