下面小编就为大家带来一篇浅谈线性表的原理及简单实现方法。小编觉得挺不错的，现在就分享给大家，也给大家做个参考。一起跟随小编过来看看吧
一、线性表
原理：零个或多个同类数据元素的有限序列
原理图：
特点 ：
1、有序性
2、有限性
3、同类型元素
4、第一个元素无前驱，最后一个元素无后继，中间的元素有一个前驱并且有一个后继
线性表是一种逻辑上的数据结构，在物理上一般有两种实现 顺序实现和链表实现
二、基于数组的 线性表顺序实现
原理 ： 用一段地址连续的存储单元依次存储线性表数据元素。
原理图：
算法原理：
1、初始化一个定长的数组空间 elementdata[] , size 存储长度 存储元素
2、通过索引来快速存取元素
3、通过数组复制实现元素的插入和删除
总结：
1、无需为表示表中元素之间的逻辑关系增加额外的存储空间
2、可以快速存取表中任一位置元素
3、插入和删除需要进行数组复制（即大量元素的移动）
4、线性表长度变化较大时，需要频繁扩容，并造成存储空间碎片
实现代码：
接口定义：
package online.jfree.base;
/**
* author : guo lixiao
* date : 2017-6-14 11:46
*/
public interface linelist <e>{
/**
* linelist 是否为空
* @return
*/
boolean isempty();
/**
* 清空 linelist
*/
void clear();
/**
* 获取指定位置元素
* @param index
* @return
*/
e get(int index);
/**
* 获取元素第一次出现的位置
* @param e
* @return
*/
int indexof(e e);
/**
* 判断 linelist是否包含指定元素
* @param e
* @return
*/
boolean contains(e e);
/**
* 设置指定位置数据，如数据已存在 则覆盖原数据
* @param index
* @param e
* @return
*/
e set(int index, e e);
/**
* 移除指定位置元素
* @param index
* @return
*/
e remove(int index);
/**
* 在linelist结尾插入元素
* @param e
* @return
*/
e add(e e);
/**
* 在index后面插入元素
* @param index
* @param e
* @return
*/
e add(int index, e e);
/**
* 返回linelist长度
* @return
*/
int size();
}
算法实现：
package online.jfree.base;
/**
* author : guo lixiao
* date : 2017-6-15 13:44
*/
public class orderedlinelist<e> implements linelist<e> {
private static final int init_capacity = 10;
private transient e[] elementdata;
private transient int elementlength;
private int size;
public orderedlinelist() {
this(0);
}
public orderedlinelist(int initcapacity) {
init(initcapacity);
}
private void init(int initcapacity) {
if (initcapacity >= 0) {
this.elementdata = (e[]) new object[initcapacity];
this.elementlength = initcapacity;
} else {
throw new illegalargumentexception("illegal capacity: " +
initcapacity);
}
this.size = 0;
}
/**
* 扩容
*/
private void dilatation() {
int oldcapacity = this.elementlength;
int newcapacity = oldcapacity;
if (oldcapacity <= this.size) {
newcapacity = oldcapacity + init_capacity;
}else if(oldcapacity - init_capacity > this.size){
newcapacity = oldcapacity - init_capacity;
}
if (oldcapacity != newcapacity){
e[] newelementdata = (e[]) new object[newcapacity];
system.arraycopy(elementdata, 0, newelementdata, 0, oldcapacity);
this.elementlength = newcapacity;
this.elementdata = newelementdata;
}
}
/**
* 校验列表索引越界
* @param index
*/
private void checkcapacity(int index){
if (index > this.size - 1 || index < 0)
throw new indexoutofboundsexception(new stringbuffer("[index : ").append(index).append("] , [size : ").append(size).append("] ").tostring());
}
@override
public boolean isempty() {
return this.size == 0;
}
@override
public void clear() {
this.init(0);
}
@override
public e get(int index) {
this.checkcapacity(index);
return this.elementdata[index];
}
@override
public int indexof(e e) {
for (int i = 0; i < this.size; i++){
if (e == null && elementdata[i] == null || e.equals(elementdata[i])){
return i;
}
}
return -1;
}
@override
public boolean contains(e e) {
return this.indexof(e) > 0;
}
@override
public e set(int index, e e) {
this.checkcapacity(index);
this.dilatation();
e oldelement = this.elementdata[index];
this.elementdata[index] = e;
return oldelement;
}
@override
public e remove(int index) {
this.dilatation();
e e = elementdata[index];
if (index == size - 1) elementdata[index] = null;
else {
int length = size - index - 1;
system.arraycopy(elementdata, index + 1, elementdata, index, length);
}
size --;
return e;
}
@override
public e add(e e) {
return this.add(size, e);
}
@override
public e add(int index, e e) {
this.dilatation();
if (index == size) elementdata[index] = e;
else {
index++;
int lastlength = size - index;
e[] lastelementdata = (e[]) new object[lastlength];
system.arraycopy(elementdata, index, lastelementdata, 0, lastlength);
elementdata[index] = e;
system.arraycopy(lastelementdata, 0, elementdata, index + 1, lastlength);
}
size ++ ;
return e;
}
@override
public int size() {
return this.size;
}
}
以上就是详细解析线性表的原理及简单实现方法的详细内容。