搜尋
首頁Javajava教程淺析線性表的原理及簡單實現

淺析線性表的原理及簡單實現

Jun 26, 2017 am 11:38 AM
原理實現簡單線性

一、線性表格

原理:零個或多個同類資料元素的有限序列

原理圖:

特點: 

1、有序性

2、有限性

#3、同類型元素

4、第一個元素無前驅,最後一個元素無後繼,中間的元素有一個前驅並且有一個後繼

線性表是一種邏輯上的資料結構,在物理上一般有兩種實作順序實作和鍊錶實作 

 

二、基於陣列的線性表格順序實作

原理: 用一段位址連續的儲存單元依序儲存線性表格資料元素。

原理圖:

演算法原理:

1、初始化一個定長的陣列空間elementData[] , size 儲存長度存儲元素

2、透過索引來快速存取元素

3、透過陣列複製實作元素的插入與刪除

總結:

1、無須為表示表中元素之間的邏輯關係增加額外的儲存空間

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

3、插入和刪除需要進行陣列複製(即大量元素的移動)

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 }</e>
View Code
演算法實作:

  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){ 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; 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 }</e></e>
View Code
 

#

以上是淺析線性表的原理及簡單實現的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
JVM如何在不同平台上管理垃圾收集?JVM如何在不同平台上管理垃圾收集?Apr 28, 2025 am 12:23 AM

JVMmanagesgarbagecollectionacrossplatformseffectivelybyusingagenerationalapproachandadaptingtoOSandhardwaredifferences.ItemploysvariouscollectorslikeSerial,Parallel,CMS,andG1,eachsuitedfordifferentscenarios.Performancecanbetunedwithflagslike-XX:NewRa

為什麼Java代碼可以在不同的操作系統上運行,而無需修改?為什麼Java代碼可以在不同的操作系統上運行,而無需修改?Apr 28, 2025 am 12:14 AM

Java代碼可以在不同操作系統上無需修改即可運行,這是因為Java的“一次編寫,到處運行”哲學,由Java虛擬機(JVM)實現。 JVM作為編譯後的Java字節碼與操作系統之間的中介,將字節碼翻譯成特定機器指令,確保程序在任何安裝了JVM的平台上都能獨立運行。

描述編譯和執行Java程序的過程,突出平台獨立性。描述編譯和執行Java程序的過程,突出平台獨立性。Apr 28, 2025 am 12:08 AM

Java程序的編譯和執行通過字節碼和JVM實現平台獨立性。 1)編寫Java源碼並編譯成字節碼。 2)使用JVM在任何平台上執行字節碼,確保代碼的跨平台運行。

基礎硬件架構如何影響Java的性能?基礎硬件架構如何影響Java的性能?Apr 28, 2025 am 12:05 AM

Java性能与硬件架构密切相关,理解这种关系可以显著提升编程能力。1)JVM通过JIT编译将Java字节码转换为机器指令,受CPU架构影响。2)内存管理和垃圾回收受RAM和内存总线速度影响。3)缓存和分支预测优化Java代码执行。4)多线程和并行处理在多核系统上提升性能。

解釋為什麼本地庫可以破壞Java的平台獨立性。解釋為什麼本地庫可以破壞Java的平台獨立性。Apr 28, 2025 am 12:02 AM

使用原生庫會破壞Java的平台獨立性,因為這些庫需要為每個操作系統單獨編譯。 1)原生庫通過JNI與Java交互,提供Java無法直接實現的功能。 2)使用原生庫增加了項目複雜性,需要為不同平台管理庫文件。 3)雖然原生庫能提高性能,但應謹慎使用並進行跨平台測試。

JVM如何處理操作系統API的差異?JVM如何處理操作系統API的差異?Apr 27, 2025 am 12:18 AM

JVM通過JavaNativeInterface(JNI)和Java標準庫處理操作系統API差異:1.JNI允許Java代碼調用本地代碼,直接與操作系統API交互。 2.Java標準庫提供統一API,內部映射到不同操作系統API,確保代碼跨平台運行。

Java 9影響平台獨立性中引入的模塊化如何?Java 9影響平台獨立性中引入的模塊化如何?Apr 27, 2025 am 12:15 AM

modularitydoesnotdirectlyaffectJava'splatformindependence.Java'splatformindependenceismaintainedbytheJVM,butmodularityinfluencesapplicationstructureandmanagement,indirectlyimpactingplatformindependence.1)Deploymentanddistributionbecomemoreefficientwi

什麼是字節碼,它與Java的平台獨立性有何關係?什麼是字節碼,它與Java的平台獨立性有何關係?Apr 27, 2025 am 12:06 AM

BytecodeinJavaistheintermediaterepresentationthatenablesplatformindependence.1)Javacodeiscompiledintobytecodestoredin.classfiles.2)TheJVMinterpretsorcompilesthisbytecodeintomachinecodeatruntime,allowingthesamebytecodetorunonanydevicewithaJVM,thusfulf

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

DVWA

DVWA

Damn Vulnerable Web App (DVWA) 是一個PHP/MySQL的Web應用程序,非常容易受到攻擊。它的主要目標是成為安全專業人員在合法環境中測試自己的技能和工具的輔助工具,幫助Web開發人員更好地理解保護網路應用程式的過程,並幫助教師/學生在課堂環境中教授/學習Web應用程式安全性。 DVWA的目標是透過簡單直接的介面練習一些最常見的Web漏洞,難度各不相同。請注意,該軟體中

Dreamweaver Mac版

Dreamweaver Mac版

視覺化網頁開發工具

SecLists

SecLists

SecLists是最終安全測試人員的伙伴。它是一個包含各種類型清單的集合,這些清單在安全評估過程中經常使用,而且都在一個地方。 SecLists透過方便地提供安全測試人員可能需要的所有列表,幫助提高安全測試的效率和生產力。清單類型包括使用者名稱、密碼、URL、模糊測試有效載荷、敏感資料模式、Web shell等等。測試人員只需將此儲存庫拉到新的測試機上,他就可以存取所需的每種類型的清單。

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)