线性表相关介绍:
线性表是一种最常用,最简单的线性结构。线性表的主要操作特定是,可以在任意位置上插入一个数据元素和删除一个数据元素。线性表可以用顺序存储结构和链式存储结构实现。用顺序存储结构实现的线性表称为顺序表,用链式存储结构实现的线性表称为链表。链表主要有单链表、循环单链表和循环双链表三种。
线性表的定义
如果一个数据元素序列满足:
1、除第一个和最后一个数据元素外,每个数据元素只有一个前驱数据元素和一个后继数据元素。
2、第一个数据元素没有前驱数据元素。
3、最后一个数据元素没有后继元素。
则称这样的数据结构为线性结构。
线性表是一种可以在任意位置进行插入和删除数据元素操作的、由n(n>=0)个相同类型的数据元素a1,a2,a3,a4组成的线性结构。
线性表的抽象数据类型
1、数据集合:线性表的数据元素集合可以表示为序列a1,a2,a3,a4,每个数据元素的数据类型可以是任意的类类型。
2、操作集合:1、求当前数据元素的个数。
2、插入指定位置数据元素
3、删除指定位置数据元素
4、取出指定位置的数据元素
5、判断线性表是否为空
实例代码:
顺序存储结构-----线性表接口代码:
package com.algorithm;
//创建顺序存储---线性表(接口)
public interface Linear {
//统计线性表大小
public int size();
//判断线性表是否为空
public boolean isEmpty();
//线性表--取数据
public Object getData(int position);
//线性表---删数据
public boolean delete(int position);
//线性表---存数据
public boolean insert(int position,Object object);
}
顺序存储结构----线性表实例类代码:
package com.algorithm;
public class LinearExample implements Linear {
//相关属性和相关的构造函数
//默认线性表大小--20
final int defaultSize=20;
//线性表默认存储的最大值
int maxSize;
//线性表大小
int size;
//线性表的数组存储对象
Object[] listarray;
//相关构造方法
public LinearExample() {
initiate(defaultSize);
}
public LinearExample(int sz){
initiate(sz);
}
//线性表初始化方法
public void initiate(int length){
maxSize=length;
size=0;
listarray=new Object[length];
}
@Override
public boolean delete(int position) {
// TODO Auto-generated method stub
boolean target=false;
//判断是否position是否为合法值
if(position<0||position>size-1){
return target;
}else if(size==0){
return target;
}else{
Object object=listarray[position];
//线性表---数据前移
for(int i=position;i<size-1;i++){
listarray[i]=listarray[i+1];
}
target=true;
size--;
return target;
}
}
@Override
public Object getData(int position) {
// TODO Auto-generated method stub
Object object=null;
if(position<0||position>listarray.length-1){
//返回错误信代码
object="404";
}else{
//判读存储的数据是否为空
object=listarray[position];
}
return object;
}
@Override
public boolean insert(int position, Object object) {
// TODO Auto-generated method stub
boolean target=false;
if(size==maxSize){
return target;
}else if(position<0||position>size){
return target;
}else{
target=true;
//线性表---数据后退
for(int i=size;i>position;i--){
listarray[i]=listarray[i-1];
}
//线性表--数据存储
listarray[position]=object;
//大小添加
size++;
return target;
}
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
boolean target=false;
if(listarray.length>0){
target=true;
return target;
}
return target;
}
@Override
public int size() {
// TODO Auto-generated method stub
return listarray.length;
}
}
代码实例调用:
public class ArrayTest {
public static void main(String[] args){
//顺序存储--线性表
LinearExample exaple=new LinearExample(10);
//线性表数据插入
exaple.insert(0, "1");
exaple.insert(1, "2");
exaple.insert(2, "3");
exaple.insert(3, "4");
exaple.insert(4, "5");
exaple.insert(5, "6");
exaple.insert(6, "7");
exaple.insert(7, "8");
exaple.insert(8, "9");
exaple.insert(9, "10");
//输出线性表存储
for(int i=0;i<exaple.size();i++){
System.out.println("i 的值为:"+exaple.getData(i));
}
//线性表大小
int size=exaple.size();
System.out.println("线性表的大小为:"+size);
//删除指定位置的数据
boolean delete=exaple.delete(1);
System.out.println("线性表删除是否成功:"+delete);
//输出删除后线性表存储
for(int i=0;i<exaple.size()-1;i++){
System.out.println("i 的值为:"+exaple.getData(i));
}
//插入指定位置的值
exaple.insert(2, "hello,world");
//输出插入后线性表存储
for(int i=0;i<exaple.size();i++){
System.out.println("i 的值为:"+exaple.getData(i));
}
}
}
相关结果展示: