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