文档章节

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

零下三度
 零下三度
发布于 2014/06/07 13:07
字数 2036
阅读 190
收藏 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
Java中数组、集合、链表、队列的数据结构和优缺点和他们之间的区别

Java中数组、集合、链表、队列的数据结构和优缺点和他们之间的区别 集合与数组的区别 个人分类: Java基础 相同点:数组和集合类同是容器。 不同点 :1.数组的长度是固定的,集合的长度是可变...

DemonsI
11/29
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

没有更多内容

加载失败,请刷新页面

加载更多

计算机系统要素 C5

本章值得一提的是组织计算机的结构。Hack 的指令和数据是分开存储的,因此它的 CPU 有两个 input: IN inM[16], // M value input (M = contents of RAM[A]) instruction[16],...

lionets
19分钟前
0
0
SpringSecurity404需要注意的地方

在使用@RequestMapping的时候路径的值如果写为("auth"),虽然用的时候前面加不加"/"没有区别,但是在配置了SpringSecurity的http.authorizeRequests().antMatchers()时就必须要注意了! 🌰1...

百萬馬力
23分钟前
0
0
10分钟读懂阿里巴巴高级专家在Flutter Live2018的分享

作者:闲鱼技术-宗心 12月4日,google flutter团队宣布第一个flutter正式版本发布。次日,Flutter Live Beijing 会议上,google flutter团队邀请了在这一技术方案中重要的合作伙伴闲鱼团队分...

阿里云官方博客
23分钟前
2
0
RxJava window操作符

原文:https://github.com/Froussios/Intro-To-RxJava/blob/master/Part%204%20-%20Concurrency/3.%20Sequences%20of%20coincidence.md Sequences of coincidence Rx试图避免管道(pipeline)外......

woshixin
30分钟前
1
0
05.Beetl标签函数以及定界符、占位符介绍---《Beetl视频课程》

本期视频实现了博客的详情页面; 内容简介:使用了标签函数layout完成详情功能 一起学beetl目录:https://my.oschina.net/u/1590490?tab=newest&catalogId=6214598 作者:GK #标签函数 layo...

Gavin-King
31分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部