java数据结构线性表——顺序表的设计思想及实现

线性表抽象数据类型概述

---

• 什么是抽象数据类型
  这里引用一段相关描述：

  我们都知道java在默认情况下，所有的基本数据类型(int,float,boolean等)都支持基本运算，如加减法，这是因为系统已帮我们实现了这些基本数据类型的的基本运算。而对于自定义的数据类型(如类)也需要定义相应的运算，但在实际使用这些自定义的数据类型的运算时需要自己实现相关的运算，也就是说用户自定义的数据类型的运算需要我们自己利用系统提供的基本运算来定义和实现。这些自定义了数据结构(如自定义类)和包含相关运算组合实现的数据类型就称其为抽象数据类型(ADT,Abstract Data Type),因此一个ADT会包含数据声明和运算声明。常用的ADT包含链表、栈、队列、优先队列、二叉树、散列表、图等，所以接下来我们要分析的顺序表和链表也属于ADT范畴.

---

• Java数据结构中对线性表的定义:

 线性表是由n(n>=0)个类型相同的数据元素a0,a1,…,an-1组成的有限的序列，在数学中记作(a0,a1,…,an-1)，其中ai的数据类型可以是基本数据类型(int,float等)、字符或类。n代表线性表的元素个数，也称其为长度(Length)。若n=0，则为空表；若n > 0，则ai(0 < i < n-1)有且仅有一个前驱(Predecessor)元素ai-1和一个后继(Successor)元素ai+1，a0没有前驱元素，ai没有后继元素。

以上，便是关于线性表抽象数据类型的概述。

---

线性表的顺序存储设计和实现（顺序表）

• 顺序储存结构的设计原理

  顺序存储结构底层是利用数组来实现的，而数组可以存储具有相同数据类型的元素集合，如int，float或者自定义类型等，当我们创建一个数组时，计算机操作系统会为该数组分配一块连续的内存块，这也就意味着数组中的每个存储单元的地址都是连续的，因此只要知道了数组的起始内存地址就可以通过简单的乘法和加法计算出数组中第n-1个存储单元的内存地址.

 通过上图可以发现为了访问一个数组元素，该元素的内存地址需要计算其距离数组基地址的偏移量，即用一个乘法计算偏移量然后加上基地址，就可以获得数组中某个元素的内存地址。其中c代表的是元素数据类型的存储空间大小，而序号则为数组的下标索引。整个过程需要一次乘法和一次加法运算，因为这两个操作的执行时间是常数时间，所以我们可以认为数组访问操作能再常数时间内完成，即时间复杂度为O(1)，这种存取任何一个元素的时间复杂度为O(1)的数据结构称之为随机存取结构。

及a1=a0+c,a2=a1+c,a3=a2+cc代表每个数组元素所占存储空间的大小。因为顺序表是一段连续不断的空间里储存的，所以我们只需要用前一个数组元素的存储位置加上其所占的存储空间大小，就可以得出当前数组元素的存储位置，只需要进行简单的加法和乘法运算就可以实现对顺序表中的元素进行基本的插入，删除，查找操作了。

这里引用一下顺序表的定义：

 线性表的顺序存储结构称之为顺序表(Sequential List),它使用一维数组依次存放从a0到an-1的数据元素(a0,a1,…,an-1)，将ai(0< i <> n-1)存放在数组的第i个元素，使得ai与其前驱ai-1及后继ai+1的存储位置相邻，因此数据元素在内存的物理存储次序反映了线性表数据元素之间的逻辑次序。

---

• 顺序储存结构的实现

  下面我们分析一下顺序表的实现，前面说了线性表的抽象数据类型的性质，所以我们这里首先要创建一个顺序表接口类用来声明顺序表的各种操作方法。
  关于接口这里引用Java数据结构中的一段描述：

  java语言的接口是一组抽象方法，常量和内嵌型的集合。接口是多继承的，一个接口可以继承多个父接口，接口是一种数据类型，采用抽象的形式来约定，因此接口只有被类实现之后才有意义。
  一个接口可被多个类实现，接口提供方法声明与方法实现是相分离的机制。使实现接口的多个类表现出共同的行为能力，接口声明的抽象方法在实现接口的多个类中表现出多态性。

  ---

  • 声明接口类

    
  /**
   * 首先声明一个顺序表的接口类<List>,并实现该接口。
   * 泛型参数T表示数据源数的数据类型
   * 定义线性表ADT的基本操作
   * 
   * @author MaYaP
   *
   */
  public interface List<T> {
  
  	boolean isEmpty();  //判断集合是否为空
  	
  	int length();  //返回线性表的元素个数(长度)
  	
  	T get(int i); // 返回第i个元素
  	
      void set(int i, T x);  //设置第i个元素的值为x
  	
  	int insert(int i, T x); //插入x作为第i个元素
  	
  	void append(T x); //在线性表最后插入x元素
  	
  	T remove (int i); //删除第i个元素并返回被删除的对象
  	
  	void removeAll(); //删除线性表内所有元素
  	
  	T search(T key);  //查找，返回首次出现的关键字为key元素,按内容查找
  	
  	boolean contain(T x); //判断集合是否包含元素x,及元素x是否属于集合
  	
  	void showListInfo();  //显示表长和表内的所有元素
  
  		
  }

其次，在声明好了接口类后，我们需要对其中声明的方法进行实现，所以接下来我们需要声明一个实现接口方法的类。用来实现接口类中的各种方法。

---

• 声明一个实现接口类方法的类SeqList。及实现接口类各种方法的代码。

    /**
   * 声明一个实现接口类方法的类SeqList。及实现接口类各种方法的代码。
   * @author MaYaP
   *
   * @param <T>
   */
  
  public class SeqList<T> implements List<T> {
  	
  	protected Object[] element;  //对象数组存储顺序表的数据类型，保护成员
  	protected int n; //顺序表的元素个数
  	/**
  	 * 构建容量为length的空表
  	 * @param length
  	 */
  	public SeqList(int length) {
  		this.element = new Object[length]; // 申请数组的存储空间，元素为null,若数组长度小于0，则抛出负数组异常。
  		this.n=0; 
  	}
  	
  	/**
  	 *创建默认容量的空表。
  	 */
  	public SeqList(){
  		this(64);  //调用本类已声明的指定参数列表的构建方法
  		
  	}
  	
  	
  	/**
  	 * 判断顺序表是否为空，若为空则返回ture
  	 */
  	@Override
  	public boolean isEmpty() {
  		// TODO Auto-generated method stub
  		return this.n==0; //双等于判断，单等于是赋值。
  	}
  
  	/**
  	 * 返回顺序表元素个数，长度。
  	 */
  	@Override
  	public int length() {
  		// TODO Auto-generated method stub
  		return this.n;
  	}
  /**
  	 * 按序号查找，返回第i个元素，0<i<n.若i越界，则返回null
  	 */
  	@Override
  	public T get(int i) {
  		if(i>=0 && i<this.n)
  		{
  			int p=i;
  			//return (T)this.element[i];	
  		    System.out.println("position="+p+",is:"+this.element[i]);//返回第i个元素
  		}
  		
  		    return null;	
  		// TODO Auto-generated method stub
  		
  	}
  
  	/**
  	 * 设置第i个元素为x，0<i<n,若i越界，则抛出序号越界异常，若i=null，则抛出空对象异常。
  	 */
  	@Override
  	public void set(int i, T x) {
  		// TODO Auto-generated method stub
  		if(x==null)
  			throw new NullPointerException("x==null");//抛出空对象异常
  		if(i>=0 && i<n)
  			this.element[i]=x;
  		else throw new java.lang.IndexOutOfBoundsException(i+"");//抛出序号越界异常
  			
  	}
  	
  /**
   * 插入x做为第i个元素，x!=null，返回x序号，若x==null,则抛出空对象异常 
   * 对序号i采取容错措施，若i<0,则在表头插入x，若i>n,则在表尾插入x。
   */
  	
  	@Override
  	public int insert(int i, T x) {
  		// TODO Auto-generated method stub
  		if(x==null)  
  			throw new NullPointerException("x==null"); // 抛出空对象异常
  		if(i<0) i=0;  //插入在表头
  		if(i>this.n) i=this.n;  //插入在最后
  		Object[] source=this.element; // 数组引用赋值，source也引用element
  		if(this.n==element.length)  // 如果数组满了，则扩充顺序表的数据容量
  		{
  			this.element=new Object[source.length*2];  //重新申请一个容量更大的数组
  			for(int j=0;j<i;j++)  //复制当前数组前i-1个元素
  				this.element[j]=source[j]; 
  		}
  		for(int j=this.n-1;j>=i;j--)  //从i开始至表尾的元素向后移动
  			this.element[j]=source[j];
  		this.element[i]=x;  
  		this.n++;  
  		
  		System.out.println("insert a new node:"+this.element[i].toString()+",in position="+i);	//输出插入元素信息
  		
  		
  	return i++;  //返回x序号
  	
  	
  	
  	}
  
  	
  	/**
  	 * 在线性表尾插入x
  	 */
  	
  	@Override
  	public void append(T x) {
  		// TODO Auto-generated method stub
  		
  	}
  /**
   * 删除第i个元素，0=<i<0,返回被删除元素，若i越界，则返回 null
   */
  	@Override
  	public T remove(int i) {
  		// TODO Auto-generated method stub
  		if(this.n==0 || i<0 || i>this.n )  {
  			// throw new IndexOutOfBoundsException(i + ""); // 抛出序号越界异常
  			return null;
  		}
  		
  			T old = (T)this.element[i];  //old 中存储被删除元素
  			
  			System.out.println("node:"+this.element[i].toString()+",is Delete from the SeqList");//输出删除信息
  			
  			for (int j=i;j<this.n-1;j++)
  			{
  				this.element[j]=this.element[j+1];  //元素前移一个位置 
  			}
  				
  			this.element[this.n-1]=null; //设置数组元素对象为空，释放原引用实例
  			this.n--;
  			return old;  //返回old局部变量引用的对象，传递对象引用
  		
  		
  	}
  /**
   * 删除所有元素
   */
  	@Override
  	public void removeAll() {
  		// TODO Auto-generated method stub
  		this.n=0;  //设置长度为0，未释放数组空间 
  	}
  	
  /**
   * 判断集合是否包含元素x，即元素x是否属于集合
   */
  	@Override
  	public boolean contain(T x) {
  		// TODO Auto-generated method stub
  		return false;
  	}
  /**
   * 显示表长和表内所有数据元素
   */
  	@Override
  	public void showListInfo() {
  		// TODO Auto-generated method stub
  		
  		
  		
  		//int i=this.length(); 
  		/**
  		 * 使用for循环遍历顺序表，输出表内全部内容
  		 */
  		
  		
  		/*for(int i=0;i<this.length();i++)	
  		{			
  			int p=i; //重新定义一个整型变量p来记录元素下标，以便输出
  			
  	   	System.out.println("insert a new node:"+this.element[i]+",in position="+p);	
  	   	//输出顺序表内所有插入的元素及其对应的下标序号。
  		}*/
         
  	
  		
  			
  		
  		System.out.println("seqlist len="+this.length());//输出顺序表的长度length().
  		/**
  		 * 通过for循环，以（，，，，）的形式输出所有顺序表内的元素。
  		 */
  		System.out.print("The seqlist is:(");//打印括号
  		
  		/**
  		 * for循环，遍历整个顺序表，并输出其中元素。
  		 */
  		
  		
  		for(int i=0;i<this.length();i++){
  			System.out.print(this.element[i]+",");
  		}
  		
  		System.out.println(")");//输出反括号
  		
  		
  	}
  /*
   * 按内容查找
   */
  	@Override
  	public T search(T key) {
  		// TODO Auto-generated method stub
  		return null;
  	}
  
  
  }

其中，关于顺序表的插入，删除，查找，就不在做详细描述了，代码注释都比较详细。

---

当然，在声明了实现接口的类并且实现了其中的构造方法后。我们需要创建main主函数类来测试实现一下我们的顺序表的构造是否成功。

---

• 声明main主函数类测试实现接口和接口实现类

    /*
   * 声明main主函数类测试实现<List>接口和接口实现类<SeqList>
   */
  public class Main {
  	
  	public static void main(String args[]){
  		//创建顺序表
  		SeqList<Integer> list1 =new SeqList<Integer>();//空表
  		
  		//建表，插入新的数据元素
  		System.out.println("建表操作：");
  		list1.insert(1, 1);  //相当于执行了四次插入操作
  		list1.insert(2, 2);
  		list1.insert(3, 3);
  		list1.insert(4, 4);
  		list1.showListInfo(); //调用方法，显示表的长度和表内所有的内容
  		
  		//查找操作
  		System.out.println("查找操作：");
  		list1.get(3);
  		
  		//插入操作
  		System.out.println("插入操作：");
  		list1.insert(4, 100);
  		list1.showListInfo();
  		
  		//删除操作
  		System.out.println("删除操作：");
  		list1.remove(3);
  		list1.showListInfo();
  	}
  
  }

这是一个主函数类，用来测试顺序表的各种操作的实现。

---

• 参考:

  java数据结构与算法之顺序表与链表深入分析

  ---

  更新时间：
  2018.4.29