文档章节

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

零下三度
 零下三度
发布于 2014/06/07 13:07
字数 2036
阅读 177
收藏 9
点赞 0
评论 0

   一、基本概念

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

  • 线性结构:在这些数据元素中有一个可以被称为“第一个”(元素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
朝阳
程序员
JAVA数据结构--------线性表

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

Winnie007 ⋅ 2015/08/02 ⋅ 0

数据结构/算法——线性表*

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

cjun1990 ⋅ 2015/09/24 ⋅ 0

栈-顺序栈(顺序表示和实现)

从数据结构看,栈也是线性表,其特殊性在于栈的基本操作是线性表操作的子集。 抽象数据类型栈的定义: 栈(stack),是限定在表尾进行插入或删除操作的线性表,因此对栈来说表尾有其特殊的含...

秋风醉了 ⋅ 2014/05/18 ⋅ 0

数据结构1 线性结构

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

zhixin9001 ⋅ 02/07 ⋅ 0

数据结构课程主页-2016级

  新学期,再度起程!   翻转的数据结构课程再度迎来新的一批同学。   前两年,资源建设基本完备,课堂方案逐渐完善,同学们对新型的学习方式设计给予了肯定(参见2014级问卷调查和201...

sxhelijian ⋅ 2017/08/30 ⋅ 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

线性表

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

DWade_Coding ⋅ 2017/11/08 ⋅ 0

数据结构与算法概论

数据结构与算法概论 一、基本概念 数据:描述客观事物的数、字符以及能输入计算机中并被计算机处理的符号集合 数据元素:是数据的基本单位。有时一个数据元素可由若干个数据项(也称为字段、...

JS_HCX ⋅ 02/26 ⋅ 0

【C语言基础】关于数据结构顺序表动态内存开辟的介绍

数据结构中,线性表的顺序存储结构就是,把线性表中的所有元素按照其逻辑顺序依次存储在计算机存储器中指定存储位置开始的一块连续的存储空间中。 因此,线性表的顺序存储结构是利用数组来实...

qregi ⋅ 2017/12/13 ⋅ 0

线性表(知识笔记)

什么是线性表 线性表描述的是数据的逻辑结构。其描述的逻辑为: 数据是线性的,一对一的,头结点无前驱,可以有且只能有一个后继,尾结点有且只有一个前驱,无后继,其余结点有且只有一个前驱...

光哥很霸气 ⋅ 2017/02/23 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

常见数据结构(二)-树(二叉树,红黑树,B树)

本文介绍数据结构中几种常见的树:二分查找树,2-3树,红黑树,B树 写在前面 本文所有图片均截图自coursera上普林斯顿的课程《Algorithms, Part I》中的Slides 相关命题的证明可参考《算法(第...

浮躁的码农 ⋅ 12分钟前 ⋅ 0

android -------- 混淆打包报错 (warning - InnerClass ...)

最近做Android混淆打包遇到一些问题,Android Sdutio 3.1 版本打包的 错误如下: Android studio warning - InnerClass annotations are missing corresponding EnclosingMember annotation......

切切歆语 ⋅ 27分钟前 ⋅ 0

eclipse酷炫大法之设置主题、皮肤

eclipse酷炫大法 目前两款不错的eclipse 1.系统设置 Window->Preferences->General->Appearance 2.Eclipse Marketplace下载【推荐】 Help->Eclipse Marketplace->搜索‘theme’进行安装 比如......

anlve ⋅ 36分钟前 ⋅ 0

vim编辑模式、vim命令模式、vim实践

vim编辑模式 编辑模式用来输入或修改文本内容,编辑模式除了Esc外其他键几乎都是输入 如何进入编辑模式 一般模式输入以下按键,均可进入编辑模式,左下角提示 insert(中文为插入) 字样 i ...

蛋黄Yolks ⋅ 40分钟前 ⋅ 0

大数据入门基础:SSH介绍

什么是ssh 简单说,SSH是一种网络协议,用于计算机之间的加密登录。 如果一个用户从本地计算机,使用SSH协议登录另一台远程计算机,我们就可以认为,这种登录是安全的,即使被中途截获,密码...

董黎明 ⋅ 59分钟前 ⋅ 0

web3j教程

web3j是一个轻量级、高度模块化、响应式、类型安全的Java和Android类库提供丰富API,用于处理以太坊智能合约及与以太坊网络上的客户端(节点)进行集成。 汇智网最新发布的web3j教程,详细讲解...

汇智网教程 ⋅ 今天 ⋅ 0

谷歌:安全问题机制并不如你想象中安全

腾讯科技讯 5月25日,如今的你或许已经对许多网站所使用的“安全问题机制”习以为常了,但你真的认为包括“你第一个宠物的名字是什么?”这些问题能够保障你的帐户安全吗? 根据谷歌(微博)安...

问题终结者 ⋅ 今天 ⋅ 0

聊聊spring cloud gateway的RedisRateLimiter

序 本文主要研究下spring cloud gateway的RedisRateLimiter GatewayRedisAutoConfiguration spring-cloud-gateway-core-2.0.0.RELEASE-sources.jar!/org/springframework/cloud/gateway/con......

go4it ⋅ 今天 ⋅ 0

169. Majority Element - LeetCode

Question 169. Majority Element Solution 思路:构造一个map存储每个数字出现的次数,然后遍历map返回出现次数大于数组一半的数字. 还有一种思路是:对这个数组排序,次数超过n/2的元素必然在中...

yysue ⋅ 今天 ⋅ 0

NFS

14.1 NFS介绍 NFS是Network File System的缩写 NFS最早由Sun公司开发,分2,3,4三个版本,2和3由Sun起草开发,4.0开始Netapp公司参与并主导开发,最新为4.1版本 NFS数据传输基于RPC协议,RPC...

派派菠菜 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部