顺序线性表的代码实现方法
2019/7/10 22:48:23
本文主要是介绍顺序线性表的代码实现方法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
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
以上这篇顺序线性表的代码实现方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持找一找教程网。
这篇关于顺序线性表的代码实现方法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升