Java实现线性表的顺序存储

Java实现线性表的顺序存储

本文实例为大家分享了java实现线性表的顺序存储，供大家参考，具体内容如下

顺序表：用一组地址连续的存储单元依次存储各个元素，使得在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中的线性表

package algorithm.datastructure.seqlist;

/*顺序表

*

* 用一组地址连续的存储单元依次存储各个元素，使得在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中的线性表

*

*/

public class SeqList {

private int length;//顺序表长度

private int[] list;//数组，连续的存储空间

//初始化，构造一个空的线性表

public SeqList(int listLength) {

list = new int[listLength];

}

//销毁表

public void destroyList() {

list = null;

this.length = 0;

}

//将线性表置为空表

public void clearList() {

for (int i = 0; i < getLength(); i++) {

list[i] = 0;

}

}

//判断线性表是否未空表

public Boolean isEmpty() {

return getLength() == 0;

}

//获取线性表元素个数

public int getLength() {

return length;

}

//根据下标获取线性表元素

public int getElem(int i) {

if (i < 0 || i >= getLength()) {

try {

throw new Exception("线性表下标越界");

} catch (Exception e) {

e.printStackTrace();

}

}

return list[i];

}

//返回某元素(第一个)的前驱

public Integer priorElem(int element) {

for (int i = 0; i < getLength(); i++) {

if (element == list[i]) {

if (i == 0) {

return null;

} else {

return list[i - 1];

}

}

}

return null;

}

//获取某元素(第一个)的后继

public Integer nextElem(int element) {

for (int i = 0; i < getLength(); i++) {

if (element == list[i]) {

if (i == getLength() - 1) {

return null;

} else {

return list[i + 1];

}

}

}

return null;

}

//扩容，这里设置容量变为原来两倍

public void ensureCapacity(int capacity) {

if (capacity >= list.length) {//扩容

int tempList[] = new int[list.length * 2];

for (int i = 0; i < list.length; i++) {

tempList[i] = list[i];

}

list = tempList;

}

}

//在指定位置插入元素

public Boolean insertElement(int index, int element) {

if (index < 0 || index >= list.length) {

try {

throw new Exception("下标错误");

} catch (Exception e) {

e.printStackTrace();

}

}

if (index == getLength()) {

return insertTailElement(emhWGMFlement);

}

for (int i = 0; i < getLength(); i++) {

if (i == index) {

ensureCapacity(getLength() + 1);

//index位置后面的元素后移

for (int j = getLength() - 1; j >= index; j--) {

list[j + 1] = list[j];

}

list[index] = element;

length++;

}

}

return true;

}

//尾部插入元素

public Boolean insertTailElement(int element) {

ensureCapacity(length + 1);

list[++length] = element;

return true;

}

//删除尾部元素

public int deleteTailElement() {

if (getLength() == 0) {

try {

throw new Exception("下标错误");

} catch (Exception e) {

e.printStackTrace();

}

}

int tailElement = list[getLength() - 1];

list[getLength() - 1] = 0;

length--;

return tailElement;

}

//删除元素

public int deleteElement(int index) {

if (index < 0 || index >= list.length) {

try {

throw new Exception("下标错误");

} catch (Exception e) {

e.printStackTrace();

}

}

if (index == getLength()) {

return deleteTailElement();

}

for (int i = 0; i < getLength(); i++) {

if (i == index) {

int tailElement = list[index];

//index位置后面的元素前移

for (int j = index; j < getLength() - 1; j++) {

list[j] = list[j + 1];

}

list[getLength() - 1] = 0;

length--;

return tailElement;

}

}

return 0;

}

//遍历顺序表

public void traverseList() {

for (int i = 0; i < getLength(); i++) {

System.out.println(list[i]);

}

}

public static void main(String[] args) {

//测试

SeqList seqList = new SeqList(2);

System.out.println(seqList.insertTailElement(1));

System.out.println(seqList.insertTailElement(2));

System.out.println(seqList.insertTailElement(3));

System.out.println(seqList.insertTailElement(4));

System.out.println(seqList.getElem(0));

System.out.println(seqList.getElem(1));

System.out.println(seqList.getElem(2));

System.out.println(seqList.getElem(3));

System.out.println(seqList.insertElement(0, 4));

System.out.println(seqList.getElem(0));

System.out.println(seqList.getElem(1));

System.out.println(seqList.getElem(2));

System.out.println(seqList.getElem(3));

System.out.println(seqList.getElem(4));

System.out.println(seqList.priorElem(3));

System.out.println(seqList.priorElem(4));

System.out.println(seqList.nextElem(4));

System.out.println(seqList.nextElem(3));

// System.out.println(seqList.deleteTailElement());

// System.out.println(seqList.deleteTailElement());

// System.out.println(seqList.deleteTailElement());

// System.out.println(seqList.deleteTailElement());

// System.out.println(seqList.deleteTailElement());

// System.out.println(seqList.deleteTailElement());

System.out.println(seqList.deleteElement(0));

System.out.println(seqList.deleteElement(1));

seqList.traverseList();

}

}

以上就是用Java简单实现的顺序表，在Java中，如果要实现功能更复杂，性能更高的顺序表，可参考ArrayList源码。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。