线性表——顺序表
线性表——顺序表
线性表
线性表:n(n>=0)个数据元素组成的一个有限序列,可以在任意位置进行插入和删除操作的线性数据结构。
从数据在物理内存存储形式上线性表可分为:顺序表和链表
从上图可以看出:
线性表中数据与数据之间存在一对一的关系,即除第一个元素和最后一个元素外,没给元素都有唯一的直接前驱和唯一的直接后继,第一个元素没有前驱,最后一个元素没有后继。
顺序表
顺序表:用一段地址连续的存储单元依次存储数据元素的线性结构。(地址连续的空间,一般情况下采用数组)
Java内存中,栈内存和堆内存占了很大一部分空间位置:栈内存的存储是连续的,堆内存的存储是离散的。
下面我们将完成基于静态数组的顺序表(默认数组元素为整型元素)的以下基本操作:
1、置空表
2、判断线性表是否为空
3、求取线性表的长度
4、任意位置插入元素
5、获取指定位置的元素
6、删除并返回指定位置的元素
7、返回指定元素首次出现的位置,如不含该元素返回-1
8、输出该顺序表
顺序表的实现
Step1:设计线性表整型数据类型的java接口
package Struct;
//线性表的接口 public interface LinearList { //置空表 public void clear(); //判断线性表是否为空 public boolean isEmpty(); //求取线性表的长度 public int size(); //任意index位置插入整型元素odj public void insert(int index,int obj) throws Exception; //获取第index位置的元素 public int get(int index) throws Exception; //删除并返回第index个元素 public void delete(int index) throws Exception; //返回指定元素首次出现的位置,如不含该元素返回-1 public int indexOf(int obj); //输出该线性表 public void display(); } |
然后让子类实现该接口即可。
Step2:设计顺序表类
package Struct;
public class ArrayList1 implements LinearList { //线性表存储空间(整型数组) private int[] listArray; //当前长度 private int size; //顺序表构造函数,构造一个存储容量为maxSize的线性表 public ArrayList1(int maxSize){ //将顺序表当前长度置为0 size = 0; //为顺序表分配maxSize个存储单元 listArray= new int[maxSize]; } //将一个已经存在的线性表置为空表 public void clear(){ size = 0;//将顺序表的当前长度置为0 } //判断顺序表是否为空 public boolean isEmpty() { return size==0;//若size=0则该表为空表,返回true } //求取线性表的长度 public int size() { return size;//当前长度即为该线性表的长度 } //获取表中第index个元素 public int get(int index) throws Exception { if(index <0||index>size-1){ //输如的index值不在该顺序表的范围内,抛出异常 throw new Exception("第"+"【"+index+"】"+"个元素不存在"); }else{ //返回该元素 return listArray[index]; } } //任意位置插入元素obj public void insert(int index,int obj)throws Exception{ if(size == listArray.length){ //size达到设定该顺序表的最大长度,则表满,抛出异常 throw new Exception("顺序表已经满了"); } if(index < 0||index > size){ //要插入的元素不在该顺序表的范围内,抛出异常 throw new Exception("输入参数异常"); } //移动元素 else{ for(int i = size-1;i>index;i--){ listArray[i+1]=listArray[i]; } //不论当前顺序表size是否为0,此语句都可执行 listArray[index] = obj; //改变顺序表的长度 size++; } } //删除指定位置的元素 public void delete(int index) throws Exception{ if(isEmpty()){ //判断是空表的情况 throw new Exception("无法对空顺序表进行删除此操作"); } if(index < 0 || index > size-1){ //判断输入参数的合法性 throw new Exception("输入参数错误"); }else{ for(int j = index;j<size;j++){ listArray[j] = listArray[j+1]; } } //改变数组的大小 size--; } //获取第一次出现指定元素的下标 public int indexOf(int obj) { int k = 0; //while循环判断每个元素是否与指定的元素相等 while(k<size&&!(listArray[k]==(obj))){ k++; } if(k<size){ return k; }else{ return -1; } } //顺序表的输出 public void display(){ System.out.print("顺序表序列为:"); for(int x =0;x<size;x++){ System.out.print(listArray[x]+" "); } System.out.println(); } } |
Step3:测试类
package Struct;
public class Test { public static void main(String[] args) throws Exception{ ArrayList1 list = new ArrayList1(10); list.insert(0, 3); list.insert(1, 2); list.insert(2, 3); list.insert(3, 2); list.insert(4, 3); list.insert(5, 2); list.display(); int i = list.get(1); System.out.println("要获取的指定元素为:"+i); list.delete(1); list.delete(4); list.display(); int j = list.indexOf(2); System.out.println("指定元素2第一次出现的下标为:"+j); int k = list.size(); System.out.println("list的长度为:"+k); list.clear(); int m = list.size(); System.out.println("清空后list的长度为:"+m); } }
|
运行结果如下图: