Detaillierte Analyse der Prinzipien und einfachen Implementierungsmethoden linearer Tabellen

Der folgende Editor bietet Ihnen eine kurze Diskussion über die Prinzipien und einfachen Implementierungsmethoden linearer Tabellen. Der Herausgeber findet es ziemlich gut, deshalb teile ich es jetzt mit Ihnen und gebe es als Referenz. Kommen Sie und schauen Sie sich den Editor an

1. Lineare Tabelle

Prinzip: eine endliche Folge von null oder mehr ähnlichen Datenelementen

Schema:

Eigenschaften:

1. Ordnung

2. Endlichkeit

3. Elemente desselben Typs

4. Das erste Element hat keinen Vorgänger, das letzte Element hat keinen Nachfolger und das mittlere Element hat einen Vorgänger und einen Nachfolger

Lineare Tabelle ist eine logische Datenstruktur. Es gibt im Allgemeinen zwei physische Implementierungen: sequentielle Implementierung und verknüpfte Listenimplementierung

2. Array-basierte lineare Tabellenreihenfolge Implementierungsprinzip von

: Verwenden Sie eine Speichereinheit mit einer kontinuierlichen Adresse, um lineare Tabellendatenelemente der Reihe nach zu speichern.

Prinzipdiagramm:

Algorithmusprinzip:

1. Initialisieren Sie ein Array mit fester Länge, RaumelementData[] und Speicherlänge Elemente

2. Schneller Zugriff auf Elemente über Indizes

3. Einfügen und Löschen von Elementen durch Array-Kopie

Zusammenfassung:

1. Es ist nicht erforderlich, zusätzlichen Speicherplatz hinzuzufügen, um die logische Beziehung zwischen Elementen in der Tabelle auszudrücken

2. Auf Elemente an jeder Position in der Tabelle kann schnell zugegriffen werden

3. Das Einfügen und Löschen erfordert das Kopieren des Arrays (d. h. das Verschieben einer großen Anzahl von Elementen)

4. Wenn sich die Länge der linearen Tabelle stark ändert, ist eine häufige Erweiterung erforderlich, was zu einer Fragmentierung des Speicherplatzes führt

Implementierungscode:

Schnittstellendefinition:

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();



}

Algorithmusimplementierung:

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;
 }

}

Das obige ist der detaillierte Inhalt vonDetaillierte Analyse der Prinzipien und einfachen Implementierungsmethoden linearer Tabellen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!