编程技术中如何实现顺序线性表

小编给大家分享一下编程技术中如何实现顺序线性表，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！

1、采用一个数组实现一个顺序线性表中添加元素、删除元素等基本操作

package com.ietree.basic.datastructure.Sequence;

import java.util.Arrays;

/**
 * 顺序线性表
 * 
 * @param <T>
 * @author Dylan
 */
public class SequenceList<T> {

 private final int DEFAULT_SIZE = 16;
 // 保存数组的长度
 private int capacity;
 // 定义一个数组用于保存顺序线性表的元素
 private Object[] elementData;
 // 保存顺序表中元素的当前个数
 private int size = 0;
 
 // 以默认数组长度创建顺序线性表
 public SequenceList() {
  capacity = DEFAULT_SIZE;
  elementData = new Object[capacity];
 }
 
 // 以一个初始化元素创建顺序线性表
 public SequenceList(T element) {
  this();
  elementData[0] = element;
  size++;
 }
 
 /**
  * 以指定长度的数组来创建顺序线性表
  * @param element 指定顺序线性表中第一个元素
  * @param initSize 指定顺序线性表底层数组的长度
  */
 public SequenceList(T element, int initSize) {
  capacity = 1;
  // 把capacity设为大于initSize的最小的2的n次方
  while (capacity < initSize) {
   capacity <<= 1;
  }
  elementData = new Object[capacity];
  elementData[0] = element;
  size++;
 }
 
 // 获取顺序线性表的大小
 public int length() {
  return size;
 }
 
 // 获取顺序线性表中索引为i处的元素
 public T get(int i) {
  if (i < 0 || i > size - 1) {
   throw new IndexOutOfBoundsException("线性表索引越界");
  }
  return (T) elementData[i];
 }
 
 // 查找顺序线性表中指定元素的索引
 public int locate(T element) {
  for (int i = 0; i < size; i++) {
   if (elementData[i].equals(element)) {
    return i;
   }
  }
  return -1;
 }
 
 // 向顺序线性表的指定位置插入一个元素
 public void insert(T element, int index) {
  if (index < 0 || index > size) {
   throw new IndexOutOfBoundsException("线性表索引越界");
  }
  ensureCapacity(size + 1);
  // 将指定索引处之后的所有元素向后移动一格
  System.arraycopy(elementData, index, elementData, index + 1, size - index);
  elementData[index] = element;
  size++;
 }
 
 // 在插入元素之前需要确保顺序线性表的长度大于插入之后顺序线性表的长度
 private void ensureCapacity(int minCapacity) {
  
  // 如果数组的原有长度小于目前所需的长度
  if (minCapacity > capacity) {
   // 不断地将capacity * 2，直到capacity大于minCapacity
   while (capacity < minCapacity) {
    capacity <<= 1;
   }
   elementData = Arrays.copyOf(elementData, capacity);
  }
 }
 
 // 在线性顺序表的开始处添加一个元素
 public void add(T element) {
  insert(element, size);
 }
 
 // 删除顺序线性表中指定索引处的元素
 public T delete(int index) {
  if (index < 0 || index > size - 1) {
   throw new IndexOutOfBoundsException("线性表索引越界");
  }
  T oldValue = (T) elementData[index];
  int numMoved = size - index - 1;
  if (numMoved > 0) {
   System.arraycopy(elementData, index + 1, elementData, index, numMoved);
  }
  // 清空最后一个元素
  elementData[--size] = null;
  return oldValue;
 }
 
 // 删除顺序线性表中最后一个元素
 public T remove() {
  return delete(size - 1);
 }
 
 // 判断顺序线性表是否为空表
 public boolean empty() {
  return size == 0;
 }
 
 // 清空线性表
 public void clear() {
  Arrays.fill(elementData, null);
  size = 0;
 }

 public String toString() {
  if (size == 0) {
   return "[]";
  } else {
   StringBuilder sb = new StringBuilder("[");
   for (int i = 0; i < size; i++) {
    sb.append(elementData[i].toString() + ",");
   }
   int len = sb.length();
   return sb.delete(len - 2, len).append("]").toString();
  }
 }

}

测试模拟线性表的基本操作：

package com.ietree.basic.datastructure.Sequence;

/**
 * 测试类
 * 
 * @author Dylan
 */
public class SequenceListTest {
 
 public static void main(String[] args) {
  SequenceList<String> list = new SequenceList<String>();
  list.add("aaa");
  list.add("bbb");
  list.add("ccc");
  list.add("ddd");
  list.insert("eee", 1);
  System.out.println(list);
  list.delete(2);
  System.out.println(list);
  System.out.println("ccc在顺序线性表中的位置：" + list.locate("ccc"));
 }
}

程序输出：

[aaa,eee,bbb,ccc,dd]
[aaa,eee,ccc,dd]

ccc在顺序线性表中的位置：2

以上是“编程技术中如何实现顺序线性表”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注亿速云行业资讯频道！