文档章节

数据结构那些事(二)线性表及其连续存储的实现

零下三度
 零下三度
发布于 2014/06/07 13:07
字数 2036
阅读 184
收藏 9

   一、基本概念

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

  • 线性结构:在这些数据元素中有一个可以被称为“第一个”(元素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之前,我实际上是增加了内存。


© 著作权归作者所有

共有 人打赏支持
零下三度
粉丝 8
博文 11
码字总数 13153
作品 0
朝阳
程序员
数据结构/算法——线性表*

线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。线性表的逻辑结构简单,...

cjun1990
2015/09/24
73
0
数据结构1 线性结构

数据结构是指数据元素的结合及元素间的相互关系和构造方法。元素之间的相互关系是数据的逻辑结构,元素关系的存储形式成为存储结构。数据结构按照逻辑关系的不同分为线性结构和非线性结构两大...

zhixin9001
02/07
0
0
JAVA数据结构--------线性表

一、线性表定义: 线性表是由n(n>=0)个类型相同的数据元素组成的有限序列,第一个元素无前驱元素,最后一个无后继元素,其他元素有且仅有一个前驱和一个后继。 线性表接口LList的定义: pack...

Winnie007
2015/08/02
0
0
线性表Linear List-线性表的顺序表示和实现

线性表Linear List 线性表:线性表(Linear List)是由n(n≥0)个数据元素(结点)a[0],a[1],a[2]…,a[n-1]组成的有限序列 其中: 数据元素的个数n定义为表的长度 = "list".length() ("...

秋风醉了
2014/05/04
0
0
线性表

1、线性表的定义 线性表(List):零个或多个数据元素的有限序列 第一个元素无前驱,最后一个元素无后继,其他元素都有且只有一个前驱和后继。然后,线性表强调是有限的, 线性表元素的个数n...

DWade_Coding
2017/11/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

HashTable

Hashtable 是一个散列表,它存储的内容是键值对(key-value)映射 Hashtable 继承于Dictionary,实现了Map、Cloneable、java.io.Serializable接口 Hashtable 的函数都是同步的,这意味着它是线...

职业搬砖20年
5分钟前
0
0
Linux系统状态查看命令1

10月23日任务 10.1 使用w查看系统负载 10.2 vmstat命令 10.3 top命令 10.4 sar命令 10.5 nload命令 查看系统负载 w命令 # 第一行:当前系统时间,系统启动时间,登录的用户,系统负载:1分钟...

robertt15
21分钟前
0
0
缓存那些事

前言 一般而言,现在互联网应用(网站或App)的整体流程,可以概括如图1所示,用户请求从界面(浏览器或App界面)到网络转发、应用服务再到存储(数据库或文件系统),然后返回到界面呈现内容...

Skqing
30分钟前
0
0
nginx开启stub_status模块配置方法

nginx开启stub_status模块配置方法 2017年12月13日 15:57:29 ly_dengle 阅读数:3765 标签: stub_statusnginxnginx开启stub_status模块 更多 个人分类: 软件工具php 版权声明:本文为博主原...

linjin200
36分钟前
3
0
挑逗 Java 程序员的那些 Scala 绝技

有个问题一直困扰着 Scala 社区,为什么一些 Java 开发者将 Scala 捧到了天上,认为它是来自上帝之吻的完美语言;而另外一些 Java 开发者却对它望而却步,认为它过于复杂而难以理解。同样是 ...

joymufeng
39分钟前
94
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部