欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

线性表的Java实现--顺序存储

程序员文章站 2022-07-10 21:02:09
...

线性表的Java实现--顺序存储

 线性表(Linear List)是由n(n≥0)个数据元素(结点)a[0],a[1],a[2]…,a[n-1]组成的有限序列

 

其中:

  • 数据元素的个数n定义为表的长度 = "list".length() ("list".length() = 0(表里没有一个元素)时称为空表)
  • 将非空的线性表(n>=0)记作:(a[0],a[1],a[2],…,a[n-1])
  • 数据元素a[i](0≤i≤n-1)只是个抽象符号,其具体含义在不同情况下可以不同

        一个数据元素可以由若干个数据项组成。数据元素称为记录,含有大量记录的线性表又称为文件。这种结构具有下列特点:

线性结构的基本特征为:
1.集合中必存在唯一的一个“第一元素”;
2.集合中必存在唯一的一个 “最后元素” ;
3.除最后一个元素之外,均有 唯一的后继(后件);
4.除第一个元素之外,均有 唯一的前驱(前件)。

 简单结束线性表的基础知识后,下面分别实现顺序存储的线性表和链式存储的线性表。

 

下面的程序分别实现了顺序存储线性表的初始化、获取线性表长度、获取指定索引处元素、根据值查找、插入、删除、清空等操作。

 

顺序存储插入操作:

 


线性表的Java实现--顺序存储
            
    
    博客分类: 数据结构与算法分析 Java线性表
 

顺序存储删除操作:

 
线性表的Java实现--顺序存储
            
    
    博客分类: 数据结构与算法分析 Java线性表
 

顺序存储的Java实现

package com.liuhao.algorithm;

import java.util.Arrays;

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 indexOf(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++;

	}
	
	//在线性表的末端添加一个元素
	public void add(T element){
		insert(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 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 isEmpty(){
		return size == 0;
	}
	
	//清空线性表
	public void clear(){
		//将所有元素置为null
		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.liuhao.test;

import org.junit.Test;

import com.liuhao.algorithm.SequenceList;

public class SequeceListTest {

	@Test
	public void test() {
		SequenceList<String> sList = new SequenceList<String>();
		
		//添加元素
		sList.add("我");
		sList.add("is");
		sList.add("hehe");
		System.out.println(sList);
		
		//指定位置插入
		sList.insert("xxx", 3);
		System.out.println(sList);
		
		//指定位置删除
		sList.delete(2);
		System.out.println(sList);
		
		//获取元素位置
		System.out.println("“我”在其中的位置:" + sList.indexOf("我"));
		
		//清空
		sList.clear();
		System.out.println(sList);
	}

}

 

 

代码获取地址:https://github.com/liuhao123/JavaMore.git

  • 线性表的Java实现--顺序存储
            
    
    博客分类: 数据结构与算法分析 Java线性表
  • 大小: 18.7 KB
  • 线性表的Java实现--顺序存储
            
    
    博客分类: 数据结构与算法分析 Java线性表
  • 大小: 17.4 KB
相关标签: Java 线性表