文档章节

Java数据结构(二):线性表之顺序表

凌枫yong
 凌枫yong
发布于 2016/07/17 13:43
字数 731
阅读 6
收藏 0

顺序表采用数组实现,并且通过继承AbstractList类,下图为顺序表的存储结构图:
该图为顺序表的存储结构
具体代码如下:

package datastructure.linear.sequence;

import datastructure.exception.StructureException;
import datastructure.linear.AbstractList;

public class SequenceList<T> extends AbstractList<T>{

    /** * 该顺序表的默认容量为10 */
    private final static int defaultCapacity = 10;
    /** * 实现顺序表的数组 */
    private Object[] arrs;

    /** * 实例化顺序表,使用默认的容量大小,为10 */
    public SequenceList() {
        this(defaultCapacity);
    }

    /** * 实例化顺序表, 指定顺序表的容量 * @param capacity */
    public SequenceList(int capacity) {
        arrs = new Object[capacity];
        size = 0;
    }

    @Override
    public void insert(int index, T t) throws StructureException {
        if(arrs.length <= size) {
            throw new StructureException("顺序表的容量已满");
        }
        if(index < 0 || index > size) {
            throw new StructureException("参数异常!不能小于0或者大于当前长度");
        }
        // 插入前先后移之后的元素
        for(int i = size ; i > index ; i--) {
            arrs[i] = arrs[i-1];
        }
        arrs[index] = t;
        size ++;
    }

    @Override
    public void delete(int index)  throws StructureException{
        if(isEmpty()) {
            throw new StructureException("该顺序表为空!不存在任何元素");
        }
        if(index < 0 || index >size - 1) {
            throw new StructureException("参数异常!不能小于0或者大于顺序表的容量");
        }
        for(int i = index+1 ; i < size ; i++ ) {
            arrs[i-1] = arrs[i];
        }
        arrs[size -1] = null;
        size--;
    }

    @SuppressWarnings("unchecked")
    @Override
    public T get(int index) throws StructureException {
        if(isEmpty()) {
            throw new StructureException("该顺序表为空!不存在任何元素");
        }
        if(index < 0 || index >arrs.length) {
            throw new StructureException("参数异常!不能小于0或者大于顺序表的容量");
        }
        return (T) arrs[index];
    }

}

顺序表上的插入和删除是顺序表中时间复杂度最高的成员函数。在顺序表中插入一个数据元素时,算法中时间复杂度最高的部分是循环移动数据元素。循环移动数据元素的效率与插入数据元素的位置pos有关,最坏情况是pos=0,需移动size个数据元素;最好情况是pos=size,需移动0个元素。

顺序表的时间复杂度:顺序表中的其余操作都是与数据元素个数n无关,因此,在顺序表中插入和删除一个数据元素的时间复杂度为O(n),其余操作的时间复杂度为O(1).

顺序表的主要优点:算法简单,空间单元利用效率高;主要缺点是需要预先确定数据元素的最大个数,并且插入和删除操作时需要移动较多的数据元素。

测试类:代码如下:
package datastructure.linear.sequence;

import static org.junit.Assert.fail;

import org.junit.Test;

import datastructure.exception.StructureException;
import datastructure.linear.List;

public class SequenceListTest {

    @Test
    public void testSequenceList() throws StructureException {
        List<String> list = new SequenceList<String>();
        list.insert(0, "asdas");
        list.insert(1, "sdf");
        list.insert(1, "a");
        int index = 0;
        while(index < 10) {
            if(list.get(index) != null) {
                System.out.println(index + "----" + list.get(index));
            }
            index ++;
        }
        System.out.println(list.size());
    }

    @Test
    public void testSequenceListInt() throws StructureException {
        List<Integer> list = new SequenceList<Integer>();
        for(int i = 0 ; i < 10 ; i ++) {
            list.insert(i, i+1);
        }
        list.delete(4);
        for(int i = 0 ; i < list.size() ; i++) {
            System.out.print(list.get(i) + " ");
        }
    }

    @Test
    public void testInsert() {
        fail("尚未实现");
    }

    @Test
    public void testDelete() {
        fail("尚未实现");
    }

    @Test
    public void testGet() {
        fail("尚未实现");
    }

    @Test
    public void testSize() {
        fail("尚未实现");
    }

    @Test
    public void testIsEmpty() {
        fail("尚未实现");
    }

}

本文转载自:http://blog.csdn.net/u011990285/article/details/46710223

凌枫yong
粉丝 1
博文 65
码字总数 0
作品 0
南昌
私信 提问
数据结构(java版)学习笔记(一)——线性表

一、线性表的定义 线性表是n(n>=0)个具有相同特性的数据元素的有限序列。 线性表是最简单、最常用的一种数据结构 线性表属于线性结构的一种 如果一个数据元素序列满足: (1)除第一个和最...

Stars-one
2018/07/29
0
0
Java实现栈Stack_栈内部使用数组存储结构

Java实现栈Stack_栈内部使用数组存储结构 抽象数据类型栈的定义: 栈(stack),是限定在表尾进行插入或删除操作的线性表,因此对栈来说表尾有其特殊的含义,称为栈顶,相应的,表头端称为栈...

秋风醉了
2014/09/14
0
0
数据结构——Java实现顺序表

一、分析   什么是顺序表?顺序表是指用一组地址连续的存储单元依次存储各个元素,使得在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中的线性表。一个标准的顺序表需要实现以下基本...

牛cattle
04/19
0
0
第一阶段:Java内功秘籍-线性表

前言 为什么要学习数据结构与算法,如果你学会了做安卓,javaweb,前端等,都是你的武功秘籍,但是如果你的内功不够好,再厉害的功夫也是白费。 数据结构和算法:什么是数据结构,什么是数据...

达叔小生
2018/08/06
0
0
java数组、集合和数据结构知识*

一、数据结构知识。数据结构分为逻辑结构和物理结构,下面是百度百科的数据结构知识。 数据的逻辑结构:指反映数据元素之间的逻辑关系的数据结构,其中的逻辑关系是指数据元素之间的前后件关...

cjun1990
2015/06/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

干货 | 解读MySQL 8.0新特性:Skip Scan Range

MySQL从8.0.13版本开始支持一种新的range scan方式,称为Loose Skip Scan。该特性由Facebook贡献。我们知道在之前的版本中,如果要使用到索引进行扫描,条件必须满足索引前缀列,比如索引idx...

迷你芊宝宝
23分钟前
1
0
观点 | 云原生时代来袭 下一代云数据库技术将走向何方?

全面云化的时代已经到来,面对一系列的新技术和挑战,数据库市场将面临怎样的变革?作为云服务提供商,如何帮助更多的企业级用户把握“云”潮,提供最高效、最具价值的数据库解决方案? 日前...

zhaowei121
32分钟前
1
0
ReentrantLock是如何基于AQS实现的

ReentrantLock是一个可重入的互斥锁,基于AQS实现,它具有与使用 synchronized 方法和语句相同的一些基本行为和语义,但功能更强大。 lock和unlock ReentrantLock 中进行同步操作都是从lock方...

java菜分享
33分钟前
0
0
比特币钱包开发【C#】

在这个教程中,我们将使用C#来开发一个比特币钱包,我们使用NBitcoin这个库。教程中的代码实现了比特币的存储、接收和支付功能,可以很容易地移植到其他应用中。 如果要快速掌握在C#程序中N...

汇智网教程
33分钟前
1
0
centos7.4编译安装nginx

1、安装准备环境 yum install gcc gcc-c++ automake pcre pcre-devel zlip zlib-devel openssl openssl-devel pcre* 下载pcre wget https://jaist.dl.sourceforge.net/project/pcre/pcre/8.......

Marhal
35分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部