溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
一、線性表
原理：零個或多個同類數據元素的有限序列
原理圖：
特點 ：
1、有序性
2、有限性
3、同類型元素
4、第一個元素無前驅，最后一個元素無后繼，中間的元素有一個前驅并且有一個后繼
線性表是一種邏輯上的數據結構，在物理上一般有兩種實現 順序實現和鏈表實現
二、基于數組的 線性表順序實現
原理 ： 用一段地址連續的存儲單元依次存儲線性表數據元素。
原理圖：
算法原理：
1、初始化一個定長的數組空間 elementData[] , size 存儲長度 存儲元素
2、通過索引來快速存取元素
3、通過數組復制實現元素的插入和刪除
總結：
1、無需為表示表中元素之間的邏輯關系增加額外的存儲空間
2、可以快速存取表中任一位置元素
3、插入和刪除需要進行數組復制（即大量元素的移動）
4、線性表長度變化較大時，需要頻繁擴容，并造成存儲空間碎片
實現代碼：
接口定義：
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);
/**
* 獲取元素第一次出現的位置
* @param e
* @return
*/
int indexOf(E e);
/**
* 判斷 lineList是否包含指定元素
* @param e
* @return
*/
boolean contains(E e);
/**
* 設置指定位置數據，如數據已存在 則覆蓋原數據
* @param index
* @param e
* @return
*/
E set(int index, E e);
/**
* 移除指定位置元素
* @param index
* @return
*/
E remove(int index);
/**
* 在lineList結尾插入元素
* @param e
* @return
*/
E add(E e);
/**
* 在index后面插入元素
* @param index
* @param e
* @return
*/
E add(int index, E e);
/**
* 返回lineList長度
* @return
*/
int size();
}
算法實現：
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;
}
/**
* 擴容
*/
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;
}
}
/**
* 校驗列表索引越界
* @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;
}
}
以上這篇淺談線性表的原理及簡單實現方法就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
