선형 테이블의 원리와 간단한 구현 방법에 대한 상세한 분석

아래 편집기에서는 선형 테이블의 원리와 간단한 구현 방법에 대해 간략하게 설명합니다. 편집자님이 꽤 좋다고 생각하셔서 지금 공유하고 모두에게 참고용으로 드리도록 하겠습니다. 와서 편집기로 살펴보세요

1. 선형 테이블

원리: 0개 이상의 유사한 데이터 요소의 유한 시퀀스

원리:

특징:

1 . 질서

2. 유한성

3. 동일한 유형의 요소

4. 첫 번째 요소에는 선행 요소가 없고, 마지막 요소에는 후행 요소가 없으며, 중간 요소에는 선행 요소와 후속 요소가 있습니다.

선형 테이블입니다. 논리적 데이터 구조에는 일반적으로 순차 구현과 연결 목록 구현의 두 가지가 있습니다. 2. 배열 기반 선형 테이블 순차 구현 원리: 선형 테이블 데이터 요소를 연속적으로 저장하는 저장 장치를 사용합니다.

원리 다이어그램:

알고리즘 원리:

1. 요소를 저장할 크기 저장 길이인 요소 데이터를 초기화합니다.

2. 배열을 통해 빠르게 요소에 액세스합니다. 요소 삽입 및 삭제를 구현합니다

요약:

1. 테이블의 요소 간의 논리적 관계를 표현하기 위해 추가 저장 공간을 추가할 필요가 없습니다.

2. table

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

}

위 내용은 선형 테이블의 원리와 간단한 구현 방법에 대한 상세한 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!