数据结构（java语言描述）-- 表的简单数组实现

约定不等于承诺〃 2022-08-12 20:28 169阅读 0赞

首先说一下什么是线性表：

线性表：

零个或多个数据元素的有限序列。

他是有限的，元素个数是有限个数的。

他是一个序列，元素之家是有顺序的，如有多个元素，则第一个元素无先驱，最后一个元素无后继，其他每个元素都有

有且仅有一个先驱和后继。

线性表的顺序存储结构：

![Center][]

线性表的顺序存储结构的优缺点：

优点：

*  无须为表示表中元素之间的逻辑关系而增加额外的存储空间。
 *  可以快速地存取表中任一位置的元素。

缺点：

*  插入和删除操作需移动大量元素。
 *  当线性表长度变化较大时，难以确定存储空间的容量。
 *  造成存储空间的“碎片”。

下面给出线性表的简单数组实现的例子：

package com.cly.sjjg;
    /**
     * 表的简单数组实现、遍历、查找、插入、删除
     * @author lenovo
     *
     */
    public class TestArray {

<span style="white-space:pre">	</span>//测试代码
    	public static void main(String[] args) {		
    		int[] arr = new int[]{34, 12, 52, 16, 12};		//创建并初始化数组
    		TestArray ta = new TestArray();	
    		ta.printList(arr);
    		ta.find(arr, 52);
    		ta.findKth(arr, 2);
    		/*
    		 * 测试删除时以下两行必须撤销注释，测试插入时必须注释最后一行。
    		 */
    		/*ta.insert(arr, 11, 2);										
    		ta.remove(arr, 52);*/
    	}
    
    	public  void printList(int[] arr) {	
    		System.out.println("遍历出数组：");
    		for (int i=0; i<arr.length; i++) {
    			System.out.print(arr[i]+"\t");										
    		}
    		System.out.println();
    	}
    	
    	/**
    	 * 
    	 * @param arr
    	 * @param findValue 返回指定值在数组中的位置
    	 */
    	public   int find(int[] arr, int findValue) {
    		int index=0;
    		for (int i=0; i<arr.length; i++) {		
    		 if (arr[i] == findValue) {
    				index = i;
    				System.out.println("值"+findValue+"在数组中的位置为：\n"+index);
    				break;
    			}
    		}		
    		return index;	
    	}
    	
    	/**
    	 * 
    	 * @param arr
    	 * @param positionValue 返回在数组中指定位置的值
    	 */
    	public  int findKth(int[] arr, int positionValue) {
    		int posValue = 0;
    		for (int i=0; i<arr.length; i++) {			
    			if (i == positionValue) {
    				posValue = arr[i];				
    				System.out.println("数组下标为"+positionValue+"的值是：\n"+arr[i]);
    				break;
    			}
    		}
    		return posValue;		
    	}
    	
    	/**
    	 * 
    	 * @param arr
    	 * @param x 要插入的值
    	 * @param positionValue 插入指定位置的值
    	 */
    	 int x = 0;
    	 int positionValue = 0;
    	public   int[] insert(int[] arr, int x, int positionValue) {
    				this.x = x;
    				this.positionValue = positionValue;
    				if (positionValue > arr.length && positionValue < 0) {
    					System.exit(-1);
    				}
    				int[] newArr = new int[arr.length+1];				
    				newArr[positionValue] = x;
    				System.arraycopy(arr, 0, newArr, 0, positionValue);
    				System.arraycopy(arr, positionValue, newArr, positionValue+1, newArr.length-positionValue -1);
    				//arr = newArr;
    				//测试删除时必须注释，测试插入时必须撤销注释。								
    				System.out.println("将"+x+"值插入数组中位置为"+positionValue+"后的新数组为：");	
    				printList(newArr);		
    				return newArr;
    	}
    
    	/**
    	 * 
    	 * @param deleteValue 删除指定数组中的位置的值
    	 */
    	public void remove(int[] arr, int deleteValue) {
    		int[] a = insert(arr, x, positionValue) ;
    		int[] newa = new int[a.length-1];		
    		for (int i=0; i<a.length; i++) {			
    			if (a[i]==deleteValue) {
    				System.arraycopy(a, 0, newa, 0, i);			//先将i之前数组元素复制到新数组newa						
    				System.arraycopy(a, i+1, newa, i, newa.length-i);	//再将i之后数组元素复制到新数组newa
    			}			
    		}
    		//a = newa;
    		System.out.println("删除数组中值为"+deleteValue+"后的新数组为：");
    		printList(newa);		
    	}
    	
    }<span style="font-size:18px;">
    </span>

测试结果：

![Image 1][]

![Center 1][]

至于插入和删除大家可以自行测试下。

如果哪里有问题，请留言，一起学习交流(●'◡'●)

[Center]: /images/20220810/fdff810e5ede4f8ba01bb80eced6df56.png
[Image 1]: 
[Center 1]: /images/20220810/0b821bb45dfb459d8b6d0a3e39f78cf0.png