数据结构那些事(二)线性表及其连续存储的实现
数据结构那些事(二)线性表及其连续存储的实现
零下三度 发表于4年前
数据结构那些事(二)线性表及其连续存储的实现
  • 发表于 4年前
  • 阅读 172
  • 收藏 9
  • 点赞 0
  • 评论 0

腾讯云 新注册用户 域名抢购1元起>>>   

摘要: 1.线性表的基本概念 2.线性表连续存储的实现

   一、基本概念

   首先,还是来回顾线性结构的基本概念。

  • 线性结构:在这些数据元素中有一个可以被称为“第一个”(元素01)的数据元素;还有一个可以被称为“最后一个”(元素04)的数据元素;除第一个元素以外每个数据元素有且仅有一个直接前驱元素,除最后一个元素以外每个数据元素有且仅有一个直接后续元素。这种数据结构的特点是数据元素之间是11 的联系,即线性关系。

  • 二元组表示:一种数据结构的二元组表示为 linearity = (K,R),其中
    K = {01, 02, 03, 04, 05}
    R = {<02,04>, <03,05>, <05,02>, <01,03>} 

    接下来我必须强调的一点,我们研究的线性表是类型相同有限序列

  二、线性表和数组的区别

    还有一点,线性表和数组要区别一下,具体区别如下:

  1. 从概念上区别:线性表是抽象数据结构,数组是一种具体的数据类型。

  2. 从逻辑关系上区别:线性表描述的是元素和元素之间一对一的关系,而数组是下表索引和数组元素的一一对应的关系。

  3. 从物理存储上区别:线性表相邻的元素存储在内存中可以是连续的,也可以是不连续的;而数组中相邻的元素存储在连续的内存空间中。

  三、线性表抽象数据类型(ADT List)

   抽象数据类型是描述啥东西,有啥关系,干啥。关于啥东西。

  啥东西:数据元素在Java里面就是对象,什么对象呢?为了兼容所有对象,可以使用Object,在这里,我使用泛型占位符E表示对象的类型。

  啥关系:数据元素的逻辑关系是线性表

  干啥:线性表可以完成对其中的元素访问、增加、删除等操作,还应该能够判断是否是空的,此额外还应该判断是否包含某个元素。

  好的,说了再多也不如用代码来的那么明了。

ackage com.util.linear;
/***
 * <p>List是线性表的抽象定义ADT。<br/>
 * List 定义了一个线性表对象所拥有的行为准则,List支持范型,能够在编译器期确定容器中元素的类型。
 * </P>
 * @author huangqian(huangqian866@163.com)
 */
public interface List<E> {
	/***
	 * 返回线性表中元素的个数
	 * @return
	 */
	public int getSize();
	/***
	 * 如果线性表为空返回true,如果线性表非空返回false
	 * @return
	 */
	public boolean isEmpty();
	/***
	 * 判断线性表中是否包含元素e。如果包含元素e,返回true,否则返回false
	 * @param e
	 * @return
	 */
	public boolean containes( E e);
	/***
	 * <p>获取元素e在线性表中索引,<br/>
	 * 如果线性表中不存在e,则返回-1,<br/>
	 * 否则返回e所在位置的索引
	 * </p>
	 * @param e
	 * @return 如果线性表中不存在e,则返回-1,<br/>
	 * 否则返回e所在位置的索引
	 */
	public int indexOf(E e);
	/***
	 * 在指定的位置(index)处插入元素e
	 * @param index
	 * @param e
	 */
	public void insert(int index,E e)throws OutOfBoundaryException;
	
	/***
	 * 将元素e插入到e1前面
	 * @param e1 参考元素
	 * @param e 插入的元素
	 * @return
	 */
	public boolean insertBefore(E e1,E e );
	/***
	 * 将元素e插入到e1后面
	 * @param e1 参考元素
	 * @param e 插入的元素
	 * @return
	 */
	public boolean insertAfter(E e1, E e);
	
	/***
	 * 删除线性表中索引为index的元素,并将其返回
	 * @param index
	 * @return 返回下表索引为index的元素
	 * @throws OutOfBoundaryException
	 */
	public  E remove(int index) throws OutOfBoundaryException;
	/***
	 * 从集合中删除元素e
	 * @param e
	 * @return 如果成功删除则返回true,否则返回false。
	 */
	public boolean remove(E e);
	/***
	 * 用元素e替换线性表中索引位置index处的元素,并将替换的元素返回。
	 * @param index 目标索引
	 * @param e 新元素
	 * @return 如果成功替换,将被替换的元素返回。
	 * @throws OutOfBoundaryException 索引越界异常
	 */
	public E replace(int index,E e)throws OutOfBoundaryException;
	/***
	 * 获取位置为index处的元素
	 * @param index 目标元素的位置
	 * @return 如果index未超出线性表索引范围,则返回index处的元素。
	 * @throws OutOfBoundaryException 索引位置越界异常
	 */
	public E get(int index) throws OutOfBoundaryException;
	

}

 

 四、线性表的顺序存储的实现

   线性表的顺序存储是用一组连续的存储单元存储数据元素,假如每个元素占k个存储单元,那么

    location(a(n+1)) = location(a(n)) + k

  因此:

    location(a(n)) = location(a(0)) + n*k

   因为数组的物理内存单元是连续的,在这里我可以借助数组,去实现线性表的顺序存储。

package com.util.linear;


/****
 * 现行表顺序存储的实现
 * @author huangqian
 *
 * @param <E>
 */
public class ArrayList<E> implements List<E> {
   //顺训表种元素的个数
	private int size;
	private Object [] elements ;
	private  int capacity;
	
	

	public ArrayList() {
		 //capacity默认值为8
		this(8);
	}
	
	public ArrayList(int initCapacity){
		this.capacity = initCapacity;
		elements = new Object[initCapacity];
	}

	@Override
	public int getSize() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return size==0 || elements.length ==0;
	}

	/***
	 * 如果包含对应的元素,返回true,否则返回false
	 */
	@Override
	public boolean containes(E e) {
		return indexOf(e) >-1;
	}

	/***
	 * 查询到了返回对应的索引值,否则返回-1
	 */
	@Override
	public int indexOf(E e) {
		if(e ==null){
			for(int i=0;i<elements.length;i++){
				if(elements[i]==null){
					return i;
				}
			}
		}else{
			for(int i=0;i<elements.length;i++){
				if(e.equals(elements[i])){
					return i;
				}
			}
		}
		return -1;
	}

	@Override
	public void insert(int index, E e) throws OutOfBoundaryException {
          if(index >size){
        	  throw new OutOfBoundaryException("插入的索引超过了数组的范围");
          }
          //空间不足,需要重新开辟空间
          if(size == elements.length){
        	  //倍增能够提高效率
        	  extendSpace(elements.length*2);
          }
		for (int i = size; i > index; i--) {
			elements[i] = elements[i - 1];
		}
		elements[index] = e;
		size++;
	}
	/***
	 * 扩展存储空间
	 * @param newLen
	 */
	private void extendSpace(int newLen){
		   Object[] tmp = elements;
		   elements = new Object[newLen];
		   for(int i=0;i<tmp.length;i++){
			   elements[i] = tmp[i];
		   }
		   tmp = null;
	}
	/***
	 * 如果实际内存利用不超过当前空间得一半,并且当前存储空间的长度为capacity的2倍以上,则回收一半的存储空间。否则,不会回收存储空间
	 */
	private void free(){
		if(size * 2 < elements.length&& capacity * 2 < elements.length){
			Object[] tmp = elements;
			int newLen;
			newLen = elements.length % 2 == 0 ? elements.length % 2  : (elements.length % 2) +1;
			elements = new Object[newLen];
			for(int i = 0; i < size ; i++){
				elements[i] = tmp[i];
			}
			tmp = null;
		}
	}

	/***
	 * 在e1后面插入元素e.如果找到了e1,并且插入元素e返回true,否则返回false
	 */
	@Override
	public boolean insertBefore(E e1, E e) {
		int index = indexOf(e1);
		if(index == -1){
			return false;
		}else{
			insert(index+1,e);
			return true;
		}
	}

	@Override
	public boolean insertAfter(E e1, E e) {
		int index = indexOf(e1);
		if(index < 0){
			return false;
		}else {
			insert(index,e);
			return true;
		}
	}

	@Override
	public E remove(int index) throws OutOfBoundaryException {
	     if(index < 0 || index >= size){
	    	 throw new OutOfBoundaryException("指定的下表索引越界");
	     }
	     E returnObj = (E)elements[index];
	     for(int i=index;i < size-1;i++){
	    	 elements[i] = elements[i+1];
	     }
	     size--;
	     //检查是否回收空间
	     free();
		return returnObj;
	}

	@Override
	public boolean remove(E e) {
		int index = indexOf(e);
		if(index < 0){
			return false;
		}else{
			remove(index);
			return true;
		}
	}

	@Override
	public E replace(int index, E e) throws OutOfBoundaryException {
		if(index < 0 || index >= size){
			 throw new OutOfBoundaryException("指定的下标索引越界");
		}
		@SuppressWarnings("unchecked")
		E rst =(E)elements[index];
		elements[index] = e;
		return rst;
	}

	@SuppressWarnings("unchecked")
	@Override
	public E get(int index) throws OutOfBoundaryException {
		if(index < 0 || index >= size){
			throw new OutOfBoundaryException("指定的下标索引越界");
		}
		return ((E)elements[index]);
	}

}

在线性表的操作中肯定会遇到内存不足,需要扩展内存空间的。我依然还记得大学学习C语言的时候,每次定义一个宏INC_SIZE。每次存储空间不足的时候,就增加INC_SIZE。如果每次我们增加的空间都是一个固定值,会有一个问题,比如我的INC_SIZE是100,我突然需要插入1000元素,这个时候就做10次内存空间的重新开辟的工作,换句话说,我需要插入n个元素,我花在开辟空间的时间是n/INC_SIZE,我再次花销的时间复杂度为o(n)。比较友好一点的做法是倍增,时间复杂度变为了log2(n)。

   还有一点,当我们的线性表的存储空间使用不到一半的时候,应该考虑回收空间。我的代码代码里面free在下一次GC之前,我实际上是增加了内存。


共有 人打赏支持
粉丝 9
博文 11
码字总数 13153
×
零下三度
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: