线性结构与顺序表功能实现

一、线性表

线性表也叫线性储存结构，是基本最常用的一种数据结构。由n个具有相同特性的数据元素组成的序列；数据依次储存到物理空间， 就称为顺序表 ，数据分散存放到物理空间，就称为链表

线性表相关术语：

• 线性表中的每个个体被称为数据元素
• 具有一对一逻辑关系的数据
• 某个元素左边的相邻元素称为前驱元素 ，右边的相邻元素称为后继元素

线性表的特征：

• 数据元素之间具有一对一的逻辑关系
• 第一个元素没有前驱元素，称为头元素
• 最后一个元素没有后继元素，称为尾元素
• 除了头元素跟尾元素，其他的元素只存在一个前驱或者后继节点

 二、顺序表

顺序表是用一段物理地址连续的储存单元进行储存元素的线性结构，通常是以数组进行储存。通过数据元素物理储存的相邻关系来反映数据元素之间逻辑上的相邻关系。

Java中的ArrayList类被认为是顺序表的一种实现，它实现了增加元素、删除元素、修改元素值、查找元的功能，我们也可以自己实现一个顺序表。

顺序表的实现一般包含了如下几个方法：

判断顺序表是否为空表：public boolean isEmpty()

判断顺序表是否满：public boolean ifFull()

向顺序表中添加元素：public void addNum(int ele)

删除指定位置的元素：public void delNum(int ele)

在指定的位置添加元素：public void insertNum(int i,int number)

修改数据：public void changeData(int index,int number)

获取顺序表的长度：public int getLength()

获取对应位置的元素：public int getNum(int flag)

遍历输出顺序表：public void showNum()

其中，判断顺序表是否为空表、满表是完成其他方法的前提。

我们首先定义好属性跟构造函数：

class SequenceList {//顺序表元素存放的数组private int[] list;//顺序表的有效元素个数private int num;public SequenceList(int size) {list = new int[size];num = 0;}
}

顺序表的判空实现：

public boolean isEmpty(){return num==0;
}

顺序表的判满实现：

public boolean isFull(){return num==list.length;
}

顺序表添加元素：

public void addNum(int ele){if(isFull()){throw new RuntimeException("顺序表已满 无法插入");}list[num++]=ele;}

顺序表指定位置插入元素：

public void insertNum(int i,int number){if(i<0||i>num){throw new RuntimeException("参数不合法");}if(isFull()){throw new RuntimeException("顺序表已满 无法插入");}//把i的位置腾出来 i位置的元素全部向后移动一位for(int index=num;index>i;index--){list[index]=list[index-1];}list[i]=number;num++;}

 顺序表的遍历：

public void showNum(){for(int i=0;i<num;i++){System.out.println(list[i]);}}

 顺序表删除指定位置的元素：

public void delNum(int ele){if(ele<0||ele>num){throw new RuntimeException("参数不合法");}for(int index=ele+1;index<num;index++){list[index-1]=list[index];}num--;}

顺序表修改元素：

 public void changeData(int index,int number){list[index]=number;}

 顺序表获取有效元素个数：

public int getLength(){return num;}

顺序表获取对应位置元素：

public int getNum(int index){return list[index];}

在之前的操作中，我们实现了isFull()判满的操作，当有效元素个数等于数组长度的时候，就无法插入了。这样设计一个顺序表的话明显是不合理的，需要增加扩容功能。

顺序表扩容：

public void reList(int size){//保存之前的顺序表int[] temp = list;//创建新的顺序表list = new int[size];//拷贝for(int i=0;i<temp.length;i++){list[i]=temp[i];}}

 之前的顺序表添加元素、顺序表指定位置插入元素方法也都需要修改一下。

if(isFull()){//throw new RuntimeException("顺序表已满 无法插入");reList(list.length*2);}

到这里我们的顺序表就完成啦，不过有个问题，就是这个顺序表只能存放int类型的数据，我们可以使用泛型让顺序表适应多种类型数据。

首先要改的地方是

class SequenceList<T> {//顺序表元素存放的数组private T[] list;//顺序表的有效元素个数private int num;public SequenceList(int size) {//list = new int[size];list = (T[])new Object[size];num = 0;}
}

后面就是要把各个int换成T就🆗啦。