선형 테이블의 원리와 간단한 구현에 대한 간략한 분석-java지도 시간-php.cn

선형 테이블의 원리와 간단한 구현에 대한 간략한 분석

巴扎黑

풀어 주다： 2017-06-26 11:38:01

원래의

2090명이 탐색했습니다.

1. 선형 테이블

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

원리:

특징:

1. 유한성

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

선형 테이블은 논리적 데이터 구조이며 일반적으로 두 가지 물리적 구현이 있습니다. 순차 구현과 연결 목록 구현

2. 배열 기반 선형 테이블 순차 구현

원리: 연속된 주소를 갖는 저장 장치를 사용하여 선형 테이블 데이터 요소를 순차적으로 저장합니다.

원리 다이어그램:

알고리즘 원리:

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

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

요약:

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

2. 테이블의 모든 위치에 있는 요소에 빠르게 액세스할 수 있습니다. . 삽입 및 삭제에는 배열 복사가 필요합니다(즉, 많은 수의 요소 이동)

4. 선형 테이블 길이가 크게 변경되면 잦은 확장이 필요하고 저장 공간 조각화가 발생합니다

구현 코드:

인터페이스 정의:

 1 package online.jfree.base; 2  3 /** 4  * author : Guo LiXiao 5  * date : 2017-6-14  11:46 6  */ 7  8 public interface LineList <E>{ 9 10     /**11      * lineList 是否为空12      * @return13      */14     boolean isEmpty();15 16     /**17      * 清空 lineList18      */19     void clear();20 21     /**22      * 获取指定位置元素23      * @param index24      * @return25      */26     E get(int index);27 28     /**29      * 获取元素第一次出现的位置30      * @param e31      * @return32      */33     int indexOf(E e);34 35     /**36      * 判断 lineList是否包含指定元素37      * @param e38      * @return39      */40     boolean contains(E e);41 42     /**43      * 设置指定位置数据，如数据已存在 则覆盖原数据44      * @param index45      * @param e46      * @return47      */48     E set(int index, E e);49 50     /**51      * 移除指定位置元素52      * @param index53      * @return54      */55     E remove(int index);56 57     /**58      * 在lineList结尾插入元素59      * @param e60      * @return61      */62     E add(E e);63 64     /**65      * 在index后面插入元素66      * @param index67      * @param e68      * @return69      */70     E add(int index, E e);71 72     /**73      * 返回lineList长度74      * @return75      */76     int size();77 78 79 80 }

로그인 후 복사

코드 보기

알고리즘 구현:

  1 package online.jfree.base;  2   3 /**  4  * author : Guo LiXiao  5  * date : 2017-6-15  13:44  6  */  7   8 public class OrderedLineList<E> implements LineList<E> {  9  10     private static final int INIT_CAPACITY = 10; 11  12     private transient E[] elementData; 13  14     private transient int elementLength; 15  16     private int size; 17  18     public OrderedLineList() { 19         this(0); 20     } 21  22     public OrderedLineList(int initCapacity) { 23         init(initCapacity); 24     } 25  26     private void init(int initCapacity) { 27         if (initCapacity >= 0) { 28             this.elementData = (E[]) new Object[initCapacity]; 29             this.elementLength = initCapacity; 30         } else { 31             throw new IllegalArgumentException("Illegal Capacity: " + 32                     initCapacity); 33         } 34         this.size = 0; 35     } 36  37     /** 38      * 扩容 39      */ 40     private void dilatation() { 41         int oldCapacity = this.elementLength; 42         int newCapacity = oldCapacity; 43         if (oldCapacity <= this.size) { 44             newCapacity = oldCapacity + INIT_CAPACITY; 45         }else if(oldCapacity - INIT_CAPACITY > this.size){ 46             newCapacity = oldCapacity - INIT_CAPACITY; 47         } 48         if (oldCapacity != newCapacity){ 49             E[] newElementData = (E[]) new Object[newCapacity]; 50             System.arraycopy(elementData, 0, newElementData, 0, oldCapacity); 51             this.elementLength = newCapacity; 52             this.elementData = newElementData; 53         } 54     } 55  56     /** 57      * 校验列表索引越界 58      * @param index 59      */ 60     private void checkCapacity(int index){ 61         if (index > this.size - 1 || index < 0) 62             throw new IndexOutOfBoundsException(new StringBuffer("[index : ").append(index).append("] , [size : ").append(size).append("] ").toString()); 63     } 64  65     @Override 66     public boolean isEmpty() { 67         return this.size == 0; 68     } 69  70     @Override 71     public void clear() { 72         this.init(0); 73     } 74  75     @Override 76     public E get(int index) { 77         this.checkCapacity(index); 78         return this.elementData[index]; 79     } 80  81     @Override 82     public int indexOf(E e) { 83         for (int i = 0; i < this.size; i++){ 84             if (e == null && elementData[i] == null || e.equals(elementData[i])){ 85                 return i; 86             } 87         } 88         return -1; 89     } 90  91     @Override 92     public boolean contains(E e) { 93         return this.indexOf(e) > 0; 94     } 95  96     @Override 97     public E set(int index, E e) { 98         this.checkCapacity(index); 99         this.dilatation();100         E oldElement = this.elementData[index];101         this.elementData[index] = e;102         return oldElement;103     }104 105     @Override106     public E remove(int index) {107         this.dilatation();108         E e = elementData[index];109         if (index == size - 1) elementData[index] = null;110         else {111             int length = size - index - 1;112             System.arraycopy(elementData, index + 1, elementData, index, length);113         }114         size --;115         return e;116     }117 118     @Override119     public E add(E e) {120         return this.add(size, e);121     }122 123     @Override124     public E add(int index, E e) {125         this.dilatation();126         if (index == size) elementData[index] = e;127         else {128             index++;129             int lastLength = size - index;130             E[] lastElementData = (E[]) new Object[lastLength];131             System.arraycopy(elementData, index, lastElementData, 0, lastLength);132             elementData[index] = e;133             System.arraycopy(lastElementData, 0, elementData, index + 1, lastLength);134         }135         size ++ ;136         return e;137     }138 139     @Override140     public int size() {141         return this.size;142     }143 144 }

로그인 후 복사

코드 보기