快捷導(dǎo)航

淺談線性表的原理及簡(jiǎn)單實(shí)現(xiàn)方法

更新時(shí)間：2017年06月18日 08:53:16 投稿：jingxian

下面小編就為大家?guī)?lái)一篇淺談線性表的原理及簡(jiǎn)單實(shí)現(xiàn)方法。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧

一、線性表

原理：零個(gè)或多個(gè)同類(lèi)數(shù)據(jù)元素的有限序列

原理圖：

特點(diǎn) ：

1、有序性

2、有限性

3、同類(lèi)型元素

4、第一個(gè)元素?zé)o前驅(qū)，最后一個(gè)元素?zé)o后繼，中間的元素有一個(gè)前驅(qū)并且有一個(gè)后繼

線性表是一種邏輯上的數(shù)據(jù)結(jié)構(gòu)，在物理上一般有兩種實(shí)現(xiàn) 順序?qū)崿F(xiàn)和鏈表實(shí)現(xiàn)

二、基于數(shù)組的線性表順序?qū)崿F(xiàn)

原理：用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表數(shù)據(jù)元素。

原理圖：

算法原理：

1、初始化一個(gè)定長(zhǎng)的數(shù)組空間 elementData[] , size 存儲(chǔ)長(zhǎng)度存儲(chǔ)元素

2、通過(guò)索引來(lái)快速存取元素

3、通過(guò)數(shù)組復(fù)制實(shí)現(xiàn)元素的插入和刪除

總結(jié)：

1、無(wú)需為表示表中元素之間的邏輯關(guān)系增加額外的存儲(chǔ)空間

2、可以快速存取表中任一位置元素

3、插入和刪除需要進(jìn)行數(shù)組復(fù)制（即大量元素的移動(dòng)）

4、線性表長(zhǎng)度變化較大時(shí)，需要頻繁擴(kuò)容，并造成存儲(chǔ)空間碎片

實(shí)現(xiàn)代碼：

接口定義：

package online.jfree.base;

/**
 * author : Guo LiXiao
 * date : 2017-6-14 11:46
 */

public interface LineList <E>{

 /**
  * lineList 是否為空
  * @return
  */
 boolean isEmpty();

 /**
  * 清空 lineList
  */
 void clear();

 /**
  * 獲取指定位置元素
  * @param index
  * @return
  */
 E get(int index);

 /**
  * 獲取元素第一次出現(xiàn)的位置
  * @param e
  * @return
  */
 int indexOf(E e);

 /**
  * 判斷 lineList是否包含指定元素
  * @param e
  * @return
  */
 boolean contains(E e);

 /**
  * 設(shè)置指定位置數(shù)據(jù)，如數(shù)據(jù)已存在 則覆蓋原數(shù)據(jù)
  * @param index
  * @param e
  * @return
  */
 E set(int index, E e);

 /**
  * 移除指定位置元素
  * @param index
  * @return
  */
 E remove(int index);

 /**
  * 在lineList結(jié)尾插入元素
  * @param e
  * @return
  */
 E add(E e);

 /**
  * 在index后面插入元素
  * @param index
  * @param e
  * @return
  */
 E add(int index, E e);

 /**
  * 返回lineList長(zhǎng)度
  * @return
  */
 int size();



}

算法實(shí)現(xiàn)：

package online.jfree.base;

/**
 * author : Guo LiXiao
 * date : 2017-6-15 13:44
 */

public class OrderedLineList<E> implements LineList<E> {

 private static final int INIT_CAPACITY = 10;

 private transient E[] elementData;

 private transient int elementLength;

 private int size;

 public OrderedLineList() {
  this(0);
 }

 public OrderedLineList(int initCapacity) {
  init(initCapacity);
 }

 private void init(int initCapacity) {
  if (initCapacity >= 0) {
   this.elementData = (E[]) new Object[initCapacity];
   this.elementLength = initCapacity;
  } else {
   throw new IllegalArgumentException("Illegal Capacity: " +
     initCapacity);
  }
  this.size = 0;
 }

 /**
  * 擴(kuò)容
  */
 private void dilatation() {
  int oldCapacity = this.elementLength;
  int newCapacity = oldCapacity;
  if (oldCapacity <= this.size) {
   newCapacity = oldCapacity + INIT_CAPACITY;
  }else if(oldCapacity - INIT_CAPACITY > this.size){
   newCapacity = oldCapacity - INIT_CAPACITY;
  }
  if (oldCapacity != newCapacity){
   E[] newElementData = (E[]) new Object[newCapacity];
   System.arraycopy(elementData, 0, newElementData, 0, oldCapacity);
   this.elementLength = newCapacity;
   this.elementData = newElementData;
  }
 }

 /**
  * 校驗(yàn)列表索引越界
  * @param index
  */
 private void checkCapacity(int index){
  if (index > this.size - 1 || index < 0)
   throw new IndexOutOfBoundsException(new StringBuffer("[index : ").append(index).append("] , [size : ").append(size).append("] ").toString());
 }

 @Override
 public boolean isEmpty() {
  return this.size == 0;
 }

 @Override
 public void clear() {
  this.init(0);
 }

 @Override
 public E get(int index) {
  this.checkCapacity(index);
  return this.elementData[index];
 }

 @Override
 public int indexOf(E e) {
  for (int i = 0; i < this.size; i++){
   if (e == null && elementData[i] == null || e.equals(elementData[i])){
    return i;
   }
  }
  return -1;
 }

 @Override
 public boolean contains(E e) {
  return this.indexOf(e) > 0;
 }

 @Override
 public E set(int index, E e) {
  this.checkCapacity(index);
  this.dilatation();
  E oldElement = this.elementData[index];
  this.elementData[index] = e;
  return oldElement;
 }

 @Override
 public E remove(int index) {
  this.dilatation();
  E e = elementData[index];
  if (index == size - 1) elementData[index] = null;
  else {
   int length = size - index - 1;
   System.arraycopy(elementData, index + 1, elementData, index, length);
  }
  size --;
  return e;
 }

 @Override
 public E add(E e) {
  return this.add(size, e);
 }

 @Override
 public E add(int index, E e) {
  this.dilatation();
  if (index == size) elementData[index] = e;
  else {
   index++;
   int lastLength = size - index;
   E[] lastElementData = (E[]) new Object[lastLength];
   System.arraycopy(elementData, index, lastElementData, 0, lastLength);
   elementData[index] = e;
   System.arraycopy(lastElementData, 0, elementData, index + 1, lastLength);
  }
  size ++ ;
  return e;
 }

 @Override
 public int size() {
  return this.size;
 }

}

以上這篇淺談線性表的原理及簡(jiǎn)單實(shí)現(xiàn)方法就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: