Java數(shù)據(jù)結(jié)構(gòu)順序表從零基礎(chǔ)到精通進(jìn)階
一、什么是線性表
線性表是最基本、最簡(jiǎn)單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表*（linear list）*是數(shù)據(jù)結(jié)構(gòu)的一種，一個(gè)線性表是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。常見(jiàn)的線性表有順序表，鏈表，棧，隊(duì)列，字符串等
注意：這里說(shuō)的線性表都指的是邏輯結(jié)構(gòu)，也就是他們的邏輯結(jié)構(gòu)是線性的，但物理結(jié)構(gòu)卻不一定是線性的。
在數(shù)據(jù)結(jié)構(gòu)邏輯層次上細(xì)分，線性表可分為一般線性表和受限線性表。一般線性表也就是我們通常所說(shuō)的“線性表”，可以自由的刪除或添加結(jié)點(diǎn)。受限線性表主要包括棧和隊(duì)列，受限表示對(duì)結(jié)點(diǎn)的操作受限制
二、順序表
順序表是在計(jì)算機(jī)內(nèi)存中以數(shù)組的形式保存的線性表，線性表的順序存儲(chǔ)是指用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的各個(gè)元素、使得線性表中在邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素存儲(chǔ)在相鄰的物理存儲(chǔ)單元中
順序表可以分為以下兩類：
- 靜態(tài)順序表：通過(guò)定長(zhǎng)數(shù)組實(shí)現(xiàn)
- 動(dòng)態(tài)順序表：數(shù)組長(zhǎng)度可動(dòng)態(tài)增長(zhǎng)
靜態(tài)順序表比較死板，如果數(shù)組長(zhǎng)度太小，擔(dān)心后面數(shù)據(jù)存不下，太大，又會(huì)有空間浪費(fèi).
所以我們一般都用動(dòng)態(tài)增長(zhǎng)的順序表，按需所取.
三、手撕順序表
在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的過(guò)程中，我們不僅要學(xué)會(huì)如何用數(shù)據(jù)結(jié)構(gòu)，懂得它的理論部分，更要親自動(dòng)手去實(shí)踐，將數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)一遍，這樣的話理解會(huì)更深刻
順序表中我們?nèi)绻皇菃渭兡靡粋€(gè)數(shù)組去用的話就會(huì)出現(xiàn)：順序表中到底有多少有效數(shù)據(jù)，滿了還是沒(méi)滿等問(wèn)題，所以我們?cè)趯?shí)現(xiàn)順序表的時(shí)候都還會(huì)再加一個(gè)size(有效數(shù)據(jù)個(gè)數(shù))屬性（順序表的容量可以通過(guò)data.length獲得）
屬性定義
public class MyArrayList {
public int[] data; // 存儲(chǔ)數(shù)據(jù)
public int size; // 有效數(shù)據(jù)個(gè)數(shù)
}
構(gòu)造方法
public MyArrayList() {
this.data = new int[10]; // 后面不夠再增容
this.size = 0; // 初始無(wú)有效數(shù)據(jù)，size 為0
}
接口實(shí)現(xiàn)
對(duì)于順序表我們一般都會(huì)有以下接口需要去實(shí)現(xiàn)：
// 打印順序表 public void display(); // 在 pos 位置增加元素 public void add(int pos, int num); // 判斷順序表中是否包含某個(gè)元素 public boolean contains(int num); // 查找某個(gè)元素所在位置 public int search(int key); // 獲取 pos 位置的元素 public int getPos(int pos); // 將 pos 位置的元素值設(shè)為 value public void setPos(int pos, int value); //刪除第一次出現(xiàn)的關(guān)鍵字key public void remove(int key); // 獲取順序表長(zhǎng)度 public int size(); // 清空順序表 public void clear();
在實(shí)現(xiàn)這些接口的過(guò)程中，凡是涉及到數(shù)組下標(biāo)的，我們都要進(jìn)行下標(biāo)合法性的檢驗(yàn)，并且要注意用size，還是data.length
確保順序表空間
在對(duì)順序表增加元素的時(shí)候，我們一定要確保順序表有足夠的空間去增加元素，否則就會(huì)導(dǎo)致數(shù)組下標(biāo)越界等情況發(fā)生
private void ensureCapacity() {
if (this.size == this.data.length) {
// 說(shuō)明滿了，該擴(kuò)容了
this.data = Arrays.copyOf(this.data, 2 * this.data.length);
}
}
增加元素
往順序表中增加元素的時(shí)候要注意可以在size位置去加元素（相當(dāng)于尾插），同時(shí)也要確保順序表有空間足夠插入，在移動(dòng)元素的時(shí)候要注意邊界情況（下標(biāo)越界，移動(dòng)元素過(guò)多等），也別忘了size++
public void add(int pos, int num) {
if (pos < 0 || pos > this.size) { // 檢驗(yàn)下表合法性
throw new RuntimeException("ArrayIndexOutOfBoundsException : " + pos);
}
ensureCapacity();
for (int i = this.size; i > pos; i--) {
this.data[i] = this.data[i - 1];
}
this.data[pos] = num;
this.size++;
}
打印順序表
注意這里只打印有效數(shù)據(jù)
public String printMyArrayList() {
String str = "[";
for (int i = 0; i < this.size - 1; i++) { // for循環(huán)中的右邊界應(yīng)該用size而不用data.length
str += this.data[i] + ", ";
}
str += this.data[this.size - 1];
str += "]";
return str;
}
測(cè)試
對(duì)前面寫的三個(gè)接口做測(cè)試
public class UseArrayList {
public static void main(String[] args) {
MyArrayList myArrayList = new MyArrayList();
myArrayList.add(0, 0);
myArrayList.add(1, 1);
myArrayList.add(2, 2);
myArrayList.add(3, 3);
myArrayList.add(4, 2);
myArrayList.add(0, 100); // 頭插
myArrayList.add(2, 666); // 中間插
System.out.println(myArrayList.printMyArrayList());
}
}
運(yùn)行結(jié)果：
判斷順序表中是否包含某個(gè)元素
public boolean contains(int num) {
for (int i = 0; i < this.size; i++) {
if (this.data[i] == num) {
return true;
}
}
return false;
}
測(cè)試：
public class UseArrayList {
public static void main(String[] args) {
MyArrayList myArrayList = new MyArrayList();
myArrayList.add(0, 0);
myArrayList.add(1, 1);
myArrayList.add(2, 2);
myArrayList.add(3, 3);
System.out.println(myArrayList.contains(3));
System.out.println(myArrayList.contains(2));
System.out.println(myArrayList.contains(0));
System.out.println(myArrayList.contains(666));
}
}
運(yùn)行結(jié)果：
查找元素
查找順序表中某個(gè)元素的位置（返回下標(biāo)）
public int search(int key) {
for (int i = 0; i < this.size; i++) {
if (this.data[i] == key) {
return i;
}
}
return -1; // 不存在這個(gè)元素，返回-1
}
測(cè)試：
public class UseArrayList {
public static void main(String[] args) {
MyArrayList myArrayList = new MyArrayList();
myArrayList.add(0, 0);
myArrayList.add(1, 1);
myArrayList.add(2, 2);
myArrayList.add(3, 3);
System.out.println(myArrayList.search(0));
System.out.println(myArrayList.search(3));
System.out.println(myArrayList.search(666));
}
}
獲取 pos 位置的元素
注意：size位置為無(wú)效元素
public int getPos(int pos) {
if (pos < 0 || pos >= this.size) {
throw new RuntimeException("ArrayIndexOfBoundsException : " + pos);
}
return this.data[pos];
}
測(cè)試：
public class UseArrayList {
public static void main(String[] args) {
MyArrayList myArrayList = new MyArrayList();
myArrayList.add(0, 0);
myArrayList.add(1, 1);
myArrayList.add(2, 2);
myArrayList.add(3, 3);
System.out.println(myArrayList.getPos(0));
System.out.println(myArrayList.getPos(3));
System.out.println(myArrayList.getPos(1));
System.out.println(myArrayList.getPos(6));
}
}
將 pos 位置的元素值設(shè)為 value
這里不涉及元素的移動(dòng)
public void setPos(int pos, int value) {
if (pos < 0 || pos >= this.size) { // size位置為無(wú)效元素
throw new RuntimeException("ArrayIndexOfBoundsException : " + pos);
}
this.data[pos] = value;
}
測(cè)試：
public class UseArrayList {
public static void main(String[] args) {
MyArrayList myArrayList = new MyArrayList();
myArrayList.add(0, 0);
myArrayList.add(1, 1);
myArrayList.add(2, 2);
myArrayList.add(3, 3);
myArrayList.setPos(0, 666);
myArrayList.setPos(3, 777);
System.out.println(myArrayList.printMyArrayList());
}
}
刪除第一次出現(xiàn)的關(guān)鍵字key
注意在刪除的時(shí)候的數(shù)組邊界以及改變size
public void remove(int key) {
int pos = search(key);
if (pos == -1) {
return; // 若是這個(gè)數(shù)字不存在，則返回
}
for (int i = pos; i < this.size - 1; i++) {
this.data[i] = this.data[i + 1]; // 從后往前挪，直接將要?jiǎng)h除的數(shù)字覆蓋掉
}
this.size--;
}
獲取順序表長(zhǎng)度
public int size() {
return this.size;
}
清空順序表
public void clear() {
this.size = 0;
}
刪除所有的key
如果我們想要?jiǎng)h除順序表中所有的key，如何做？
法一：我們可以將第一次出現(xiàn)的key刪除完之后再繼續(xù)搜索若有，則刪除，沒(méi)有則刪除完畢
public void removeAll(int key) {
for (int i = 0; i < this.size; i++) {
if (this.search(key) != -1) {
remove(key);
} else {
return;
}
}
}
法二：我們可以轉(zhuǎn)變以下思路，不直接刪除key，而是重新創(chuàng)建一個(gè)數(shù)組，將源數(shù)組中不是key的值復(fù)制到新數(shù)組，再讓原數(shù)組的引用指向新數(shù)組，間接完成刪除操作
public void removeAllPlus(int key) {
int[] newData = new int[this.data.length]; // 新數(shù)組長(zhǎng)度應(yīng)該和源數(shù)組長(zhǎng)度相同
int j = 0;
for (int i = 0; i < this.size; i++) {
if (this.data[i] != key) {
newData[j] = this.data[i];
j++;
}
}
this.data = newData;
this.size = j;
}
注意：在元素復(fù)制完之后要改變?cè)磾?shù)組的引用，并改變順序表的size
法三：我們既然可以通過(guò)復(fù)制的方式實(shí)現(xiàn)間接刪除操作，那么我們可以想著將原數(shù)組就當(dāng)成目標(biāo)數(shù)組，即兩個(gè)指針，一個(gè)數(shù)組
public void removeAllPlusPlus(int key) {
int dest = 0;
for (int src = 0; src < this.size; src++) {
if (this.data[src] != key) {
this.data[dest] = this.data[src];
dest++;
}
}
this.size = dest;
}
到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)順序表從零基礎(chǔ)到精通進(jìn)階的文章就介紹到這了,更多相關(guān)Java 順序表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- Java實(shí)現(xiàn)線性表的鏈?zhǔn)酱鎯?chǔ)
- java實(shí)現(xiàn)線性表及其算法
- java 線性表接口的實(shí)例詳解
- java線性表的存儲(chǔ)結(jié)構(gòu)及其代碼實(shí)現(xiàn)
- Java?精煉解讀數(shù)據(jù)結(jié)構(gòu)的順序表如何操作
- Java實(shí)現(xiàn)順序表和鏈表結(jié)構(gòu)
- Java實(shí)現(xiàn)順序表的操作
- Java數(shù)據(jù)結(jié)構(gòu)之順序表篇
- Java中ArrayList與順序表的概念與使用實(shí)例
- Java線性表的順序表示及實(shí)現(xiàn)
相關(guān)文章
使用RestTemplate 調(diào)用遠(yuǎn)程接口上傳文件方式
這篇文章主要介紹了使用RestTemplate 調(diào)用遠(yuǎn)程接口上傳文件方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-09-09
Java微信公眾平臺(tái)開(kāi)發(fā)（9） 關(guān)鍵字回復(fù)以及客服接口實(shí)現(xiàn)
這篇文章主要為大家詳細(xì)介紹了Java微信公眾平臺(tái)開(kāi)發(fā)第九步，關(guān)鍵字回復(fù)以及客服接口實(shí)現(xiàn)，以及遇到該公眾號(hào)暫時(shí)無(wú)法提供服務(wù)的解決方案，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-04-04
Spring?Boot在Web應(yīng)用中基于JdbcRealm安全驗(yàn)證過(guò)程
這篇文章主要為大家介紹了Spring?Boot在Web應(yīng)用中基于JdbcRealm安全驗(yàn)證過(guò)程詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪<BR>2023-02-02
Java實(shí)現(xiàn)Socket的TCP傳輸實(shí)例
這篇文章主要介紹了Java實(shí)現(xiàn)Socket的TCP傳輸,實(shí)例分析了java通過(guò)socket實(shí)現(xiàn)TCP傳輸?shù)南嚓P(guān)技巧,需要的朋友可以參考下2015-05-05
WebSocket實(shí)現(xiàn)Web聊天室功能
這篇文章主要為大家詳細(xì)介紹了WebSocket實(shí)現(xiàn)Web聊天室功能，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-08-08
泛型是一種把類型明確的工作推遲到創(chuàng)建對(duì)象或者調(diào)用方法的時(shí)候才去明確的特殊的類型,參數(shù)化類型,把類型當(dāng)作參數(shù)一樣的傳遞,本文給大家介紹Java 泛型(Generic)概述及使用,感興趣的朋友跟隨小編一起看看吧2023-10-10
Spring項(xiàng)目里將SQL語(yǔ)句寫在.sql文件中的方法
這篇文章主要介紹了Spring項(xiàng)目里如何將SQL語(yǔ)句寫在.sql文件中的方法，文中給出了詳細(xì)的介紹和示例代碼，相信對(duì)大家的學(xué)習(xí)或者工作具有一定的參考借鑒價(jià)值，有需要的朋友們下面來(lái)一起看看吧。2017-01-01
ReentrantLock和Synchronized都是Java開(kāi)發(fā)中最常用的鎖，與Synchronized這種JVM內(nèi)置鎖不同的是，ReentrantLock提供了更豐富的語(yǔ)義。本文就來(lái)深入剖析一下ReentrantLock源碼，需要的可以參考一下2022-11-11
java字符串相加時(shí)的內(nèi)存表現(xiàn)和原理分析
這篇文章主要介紹了java字符串相加時(shí)的內(nèi)存表現(xiàn)和原理分析,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-07-07
Spring Boot 2.4 對(duì)多環(huán)境配置的支持更改示例代碼
這篇文章主要介紹了Spring Boot 2.4 對(duì)多環(huán)境配置的支持更改,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-12-12