顺序表的描述
程序员文章站
2022-03-15 10:10:03
...
顺序表,就是顺序存储的线性表,顺序存储是用一组地址连续的存储单元依次存放线性表中各个元素的存储结构,具有便于随机存取的优点,缺点是插入删除操作比较麻烦,在进行插入删除的同时,会引起大量数据的移动,而且需要预先分配空间,会造成空间的浪费。下面先用一个接口表明顺序表需要实现的基本操作。
public interface IList {
public void clear();//将表中的元素置空
public boolean isEmpty();//判断是否为空表
public int length();//求线性表元素的个数
public Object get(int i) throws Exception;//返回下标为i的元素
public void insert(int i,Object x) throws Exception;//在i位置插入元素x
public void remove(int i) throws Exception;//删除i位置的元素
public int indexOf(Object x) throws Exception;//求数据为x的下标
public void display();//输出数据元素
}
接下来对顺序表类进行描述,实现IList接口
public class SqList implements IList {
private Object[] listElem;//线性表存储空间
private int curLen;//线性表当前长度
public SqList(int maxSize) {
curLen = 0;
listElem = new Object[maxSize];
}
//置空
public void clear() {
curLen = 0;
}
//判断线性表数据元素是否为空,是返回true
public boolean isEmpty() {
return curLen == 0;
}
//求线性表元素个数
public int length() {
return curLen;
}
//读取线性表的第i个元素的值,取值范围为0<=i<=curLen-1
public Object get(int i) throws Exception {
if(i < 0 || i > curLen-1) {
throw new Exception("第"+i+"个元素不存在");
}
return listElem[i];
}
//在线性表的第i个元素之前插入x
public void insert(int i, Object x) throws Exception {
if(i == listElem.length) {
throw new Exception("线性表已满");
}
if(i < 0 || i > listElem.length) {
throw new Exception("插入位置不合法");
}
for(int j = curLen; j > i ;j--) {
listElem[j] = listElem[j - 1];
}
listElem[i] = x;
curLen++;
}
//删除线性表下标为i的元素
public void remove(int i) throws Exception {
if(i < 0 || i > listElem.length) {
throw new Exception("删除位置不合法");
}
for(int j = i; j < curLen-1; j++) {
listElem[j] = listElem[j+1];
}
curLen--;
}
//返回线性表中首次出现x的位置,没有则返回-1
public int indexOf(Object x) {
for(int i = 0; i < curLen; i++) {
if (listElem[i] != x) {
continue;
}
return i;
}
return -1;
}
//输出线性表的元素
public void display() {
for(int i = 0; i < curLen; i++) {
System.out.print(listElem[i]+" ");
}
System.out.println();
}
}
下面说一下顺序表的插入和删除操作。
插入:在i位置插入一个数据,基本思路是将i+1后面的数据都后移一位,再将i的值赋给它。需要注意的是要先判断线性表是否还有空间,还有就是判断插入的位置是否在线性表元素长度之中,即(i>=0&&i<=length())。
删除:删除位置为i的数据,基本思路是将i+1后面的数据都进行左移一位,需要注意的点就是需要判断删除的数据的下标是否在线性表元素长度之中,即(i>=0&&i<length())。
注意:这里面有两个长度,一个是初始化时分配给线性表的长度,另一个·是线性表元素的个数,上面插入删除说的长度就是线性表元素的个数。