Java数据结构（一）

Java数据结构（一）

——线性表

线性表（亦作顺序表）是最基本、最简单、也是最常用的一种数据结构。线性表的主要特点是，可以在任意位置插入一个数据元素或删除一个数据元素。线性表可以用顺序存储结构或链式存储结构实现，使用顺序存储结构实现的线性表称为顺序表，而使用链式存储结构实现的称为链表，链表主要有单链表，循环单链表，双向链表等。在本篇博客中主要介绍实现的是顺序表与单链表两种。

?

?

顺序表

package pzw.List;

/**
 * 利用线性表接口实现顺序表类
 * @author PZW
 *
 */
public class SeqList implements List{
	//设置默认构造的顺序表长度
	final int defaultSize = 10;
	
	int maxSize;
	int size;
	Object[] listArray;
	//无参构造函数
	public SeqList(){
		initiate(defaultSize);
	}
	//构造函数
	public SeqList(int size){
		initiate(size);
	}
	//初始化顺序表
	private void initiate(int sz){
		maxSize = sz;
		size = 0;
		listArray = new Object[sz];
	}
	
	public void insert(int i, Object elm) throws Exception {
		if(size == maxSize){
			throw new Exception("顺序表已满无法插入");
		}
		if(i < 0||i > size){
			throw new Exception("输入的插入位置错误");
		}
		for(int j = size;j > i;j--){
			listArray[j] = listArray[j-1];
		}
		listArray[i] = elm;
		size++;
	}
	
	public void append(Object elm) throws Exception{
		insert(size,elm);
	}

	@Override
	public Object delete(int i) throws Exception {
		if(size == 0){
			throw new Exception("顺序表已空无法删除");
		}
		if(i < 0||i > size){
			throw new Exception("输入的删除位置错误");
		}
		Object elm = listArray[i];
		for(int j = i;j < size -1;j++){
			listArray[j] = listArray[j+1];
		}
		size--;
		return elm;
	}


	public Object getData(int i) throws Exception {
		if(i < 0||i > size){
			throw new Exception("参数错误");
		}
		return listArray[i];
	}
	
	public void print(){
		for(int i = 0;i < size;i++){
			System.out.print(listArray[i]+"  ");
		}
		System.out.println();
	}

	@Override
	public int size() {
		// TODO Auto-generated method stub
		return size;
	}

	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return size == 0;
	}
	
	/**
	 * 
	 * @param sl
	 * @param elm
	 * @return
	 * @throws Exception
	 */
	public int MoreDataDelete(SeqList sl,Object elm) throws Exception{
		int i,j;
		int tag = 0;
		for(i = 0;i < sl.size;i++){
			if(elm.equals(sl.getData(i))){
				sl.delete(i);
				i--;
				tag = 1;
			}
		}
		return tag;
	}

}

? ? ? ? 顺序表的主要优点是：支持随机读取，以及内存空间利用效率高；

? ? ? ? 顺序表的主要缺点是：需要预先给出数组的最大数据元素个数，但数组的最大数据元素个数很难准确给出。另外，插入和删除操作每次都必须要遍历数组，即使是在平均情况下，插入和删除操作的时间代价也是O（n）。

单链表

package pzw.list;

/**
 *自定义链表一共由两个类组成
 *链表类的方法、属性
 * @author pzw
 *
 */
public class JList {
	
	//定义一个头指针
	private JListNode head = null;
	
	//创建一个新的节点
	JListNode flag=new JListNode();
	
	//记录链表中元素的个数
	private int nCount = 0;
	
	//插入方法（默认插在最后）
	public void add(JListNode node){
		add(node,nCount);
		
	}
	
	//插入方法(从nPos位置插入)
	public void add(JListNode node,int nPos){
		//判断位置是否输入正确
		if(nPos<0||nPos>nCount){
			System.out.println("插入的位置错误");
			return;
		}
		
		//如果链表为空,将头节点指向node
		if(nCount==0){
			head=node;
			nCount++;
			return;
			
		}
		
		//其他情况
		//创建一个新的节点来指向head
		flag=head;
		
		//找到要插入的点的上一个节点
		for(int i=0;i<nPos-1;i++){
			//将flag指向flag的下一个节点
			flag=flag.Next;
		}
		
		//将插入的元素与其他元素链接起来
		node.Next=flag.Next;
		flag.Next=node;
		
		nCount++;
		
	}
	
	//删除一个元素（链表默认从头删除）
	public JListNode delete(){
		return delete(0);
	}
	
	//删除一个元素（将元素从指定的nPos位置删除）
	public JListNode delete(int nPos){
		//如果链表为空
		if(nCount==0){
			System.out.println("该链表为空");
			return null;
		}
		
		
		//如果链表中只有一个元素
		if(nCount==1){
			flag=head;
			head=null;
			nCount=0;
			return flag;
		}
		
		//判断输入的位置是否正确
		if(nPos<0||nPos>nCount-1){
			System.out.println("删除的位置错误");
			return null;
		}
		
		//如果nPos为零
		if(nPos==0){
			flag=head;
			head=head.Next;
			flag.Next=null;
			nCount--;
			return flag;
		}
		
		//其他情况
		flag=head;
		//找到要删除位置的元素的前一个
		for(int i=0;i<nPos-1;i++){
			flag=flag.Next;
		}
		
		//记录flag的下一个节点
		JListNode temp=flag.Next;
		flag.Next=temp.Next;
		temp.Next=null;
		nCount--;
		
		return temp;
	}
	
	//删除链表中所有元素
	public void remove(){
		for(int i=0;i<nCount-1;i++){
			this.delete();
		}
	}
	
	//得到指定位置nPos的元素的值(返回一个节点)
	public JListNode get(int nPos){
		flag=head;
		//找到要输出的那个节点
		for(int i=0;i<nPos;i++){
			flag=flag.Next;
		}
		
		//使用temp复制flag节点，但让temp的Next指向空
		JListNode temp=new JListNode();
		//temp=flag;
		temp.nValue=flag.nValue;
		temp.Next=null;
		
		return temp;
	}
	
	//获取链表中一共有多少个元素
	public int size(){
		return nCount;
	}
	
}

? ? ? ?单链表的主要优点是不需要预先给出数据元素的最大个数。另外单链表插入和删除工作时不需要移动数据元素。

? ? ? ?单链表的主要缺点是每个节点中要有一个指针，因此单链表的空间利用率低于顺序表，另外，单链表不支持随机读取，单链表的读取必须从头结点开始遍历，因此单链表读取数据的时间代价是O（n）。