线性表的顺序存储结构（java版）

在说线性表的顺序存储结构之前，首先要讲一下必要的定义。

线性表的定义 ：零个或多个数据元素的有限序列

线性表的顺序存储结构 ：用一段地址连续的存储单元依次存储线性表的数据元素。

 

在了解这两个必要的定义之后，我们就来看一下他的代码实现吧，在本文中，由于我个人比较熟悉Java，所以就用Java来进行代码实现了，当然，如果条件允许的话，还是比较建议读者通过C或者C++来进行代码实现。

 

第一步：我们先定义一个接口，代码如下

package com.stucture.sqlList;

/**
 * 线性表顺序存储结构的接口
 * 指的是用一段地址连续的存储单元一次存储线性表的数据元素
 * @ClassName: ISeqList 
 * @author 小学徒
 * @date 2013-2-27
 */
public interface ISeqList<T> {
	
	/**
	 * 获得元素
	 * @param i 需要获得的第i个元素
	 * @return 
	 */
	public T getElem(int i);
	

	/**
	 * 插入元素
	 * @param i 元素的插入位置
	 * @param t 需要插入的元素
	 * @return  是否成功插入
	 */
	public boolean insertElem(int i, T t);
	
	/**
	 * 删除元素
	 * @param i 需要删除元素的位置
	 * @return
	 */
	public T deleteElem(int i);
}

 

第二步，实现该接口中必要的方法，代码如下：

package com.stucture.sqlList;

/**
 * 线性表顺序存储结构
 * 指的是用一段地址连续的存储单元一次存储线性表的数据元素
 * @ClassName: SeqList 
 * @author 小学徒
 * @date 2013-2-27
 */
public class SeqList<T> implements ISeqList<T> {
	public static final int MAXSIZE = 20;	//存储空间的初始化配量
	
	private T[] data;	//数组存储数据元素
	private int length;	//线性表当前长度		
	
	public SeqList() {
		data = (T[]) new Object[MAXSIZE];
	}
	
	// 获得元素
	public T getElem(int i) {
		if(i < 0 || i >MAXSIZE) {
			return null;
		}
		T t = data[i - 1];
		return t;
	}

	// 插入元素
	public boolean insertElem(int i, T t) {
		if(length == MAXSIZE) {	//线性表已经满了
			System.out.println("该线性表已经满了");
			return false;
		}
		
		if(i < 1 || i > MAXSIZE) {	//插入位置不在范围内
			System.out.println("该位置不合法");
			return false;
		}
		
		if(i < length) {	//插入位置不在表尾
			
			for(int j = length; j >= i; j--) {	//将要插入位置后数据元素向后移动一位
				data[j] = data[j - 1];
			}
		}
		data[i - 1] = t;	//插入新元素
		length++;	//线性表长度增加
		return true;
	}
	
	//删除元素
	public T deleteElem(int i) {
		
		if(length == 0) {	//"线性表为空"
			System.out.println("线性表为空");
			return null; 
		}

		if(i < 1 || i > length) {	//删除位置不在范围内
			System.out.println("该位置不合法");
			return null;
		}
		T t = data[i -1];
		for(int j = (i - 1); j <= (length - 1); j++) {
			data[j] = data[j+1];
		}
		length--;//线性表长度减少
		return t;
		
	}
	
	public T[] getData() {
		return data;
	}

	public void setData(T[] data) {
		this.data = data;
	}

	public int getLength() {
		return length;
	}

	public void setLength(int length) {
		if(length < 0 || length > MAXSIZE) {	//删除位置不在范围内
			System.out.println("长度不合法");
		}
		this.length = length;
	}
	
}

 

第三步，既然我们已经通过Java代码实现了线性表的顺序存储结构，我们下面就写一个比较完善的代码测试，在下面的代码中，我是通过随机数来生成一些必要的数据来测试的，只要多运行几遍，还是能够测试比较完善的，不过封装的可能有点不太好，如果读者看了以后有什么更好的建议，还希望能够指出，谢谢，好啦，废话不多说，继续上代码：

package com.stucture.sqlList;

import java.util.Random;

public class SeqListTest {
	final int MAX = 25;
	Random r = new Random();
	SeqList<Integer> seqList;
	
	public SeqListTest() {
		initSeqList();
	}
	
	//创建一个线性表顺序存储结构
	public void initSeqList() {

		seqList = new SeqList<Integer>();
//		int length = (int) Math.random();	//只能产生0.0 - 1.0之间的double随机数
		int length = Math.abs(r.nextInt(MAX));	//使用Random随机产生一个25左右的值,使用Math.abs()函数来取绝对值	
		System.out.println("产生的数组长度为 ：" + length);
		
		if(length > SeqList.MAXSIZE) {
			System.out.println("该长度不合法");
		}
		
		for (int i = 1; i <= length; i++) {	//为生成的数组赋值，同时也测试了插入值的方法
			int j =r.nextInt(MAX);
			System.out.print(j + " ");
			
			if(!seqList.insertElem(i, j)) {
				System.exit(0);	
			}
		}
		System.out.println("\n原始数组是 ：");
		display(seqList);
	}
	
	//测试删除方法
	public void deleteElem() {
		int i = r.nextInt(MAX);
		System.out.println("\n\n删除的位置是：" + i);
		Integer deleteNumber = seqList.deleteElem(i);
		
		if( deleteNumber == null) {
			System.exit(0);
		} else {
			System.out.println("删除的元素是 ： " + deleteNumber);
			System.out.println("删除元素后数组是 ：");
			display(seqList);
		}
	}
	
	//测试随机插入方法
	public void insertByRandom() {
		int i = r.nextInt(MAX);
		System.out.println("\n\n随机插入位置是 ：" + i);
		int elem = r.nextInt(MAX);
		System.out.println("随机插入数据是 ：" + elem);
		seqList.insertElem(i, elem);
		System.out.println("随机插入数据后数组是 ：");
		display(seqList);
	}
	
	//数据展示
	public  void display(SeqList seqList) {
		for (int i = 1; i < seqList.getData().length; i++) {
			
			if(seqList.getElem(i) != null) {
				System.out.print(seqList.getElem(i) + " ");
			}
			
		}
		System.out.println("数组的长度为 ：" + seqList.getLength());
	}
	
	//获取元素
	public void getElem() {
		int i = r.nextInt(MAX);
		System.out.println("\n获取位置为 ：" + i);
		System.out.println("获取到的元素为 : " + seqList.getElem(i));
		
		
	}
	
	public static void main(String[] args) {
		SeqListTest s = new SeqListTest();
		s.insertByRandom();
		s.deleteElem();
		s.getElem();
	}
}

 下面个钟情况的运行结果我就不完全列出啦，我只列出其中一个测试结果，剩下的大家自己实践啦，毕竟实践是认知的源泉嘛。

产生的数组长度为 ：15
9 8 22 23 18 0 6 0 19 1 7 24 11 10 18 
原始数组是 ：
9 8 22 23 18 0 6 0 19 1 7 24 11 10 18 数组的长度为 ：15


随机插入位置是 ：21
随机插入数据是 ：5
该位置不合法
随机插入数据后数组是 ：
9 8 22 23 18 0 6 0 19 1 7 24 11 10 18 数组的长度为 ：15


删除的位置是：1
删除的元素是 ： 9
删除元素后数组是 ：
8 22 23 18 0 6 0 19 1 7 24 11 10 18 数组的长度为 ：14

获取位置为 ：7
获取到的元素为 : 0

 

评论

1 楼 听听米 2016-07-12  

在删除的时候最后一个元素并没有移除掉