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ǔ)單元中
順序表可以分為以下兩類(lèi)：
- 靜態(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ì)前面寫(xiě)的三個(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)文章
本篇文章主要介紹了詳解springmvc 參數(shù)綁定，詳細(xì)的介紹了springmvc各種參數(shù)綁定的情況，具有一定的參考價(jià)值，有興趣的可以了解一下。2017-03-03
Java中靜態(tài)代碼塊、構(gòu)造代碼塊、構(gòu)造函數(shù)和普通代碼塊的區(qū)別
在Java中，靜態(tài)代碼塊、構(gòu)造代碼塊、構(gòu)造函數(shù)、普通代碼塊的執(zhí)行順序是一個(gè)筆試的考點(diǎn)，通過(guò)這篇文章希望大家能徹底了解它們之間的執(zhí)行順序,需要的朋友可以參考下2023-05-05
這篇文章主要介紹了Spring Boot使用Maven自定義打包方式,本文通過(guò)多種方式給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-12-12
本文先從HashMap的遍歷方法講起，然后再?gòu)男阅?、原理以及安全性等方面，?lái)分析HashMap各種遍歷方式的優(yōu)勢(shì)與不足2021-06-06
Java+Selenium調(diào)用JavaScript的方法詳解
這篇文章主要為大家講解了java在利用Selenium操作瀏覽器網(wǎng)站時(shí)候，有時(shí)會(huì)需要用的JavaScript的地方，代碼該如何實(shí)現(xiàn)呢？快跟隨小編一起學(xué)習(xí)一下吧2023-01-01
Java?數(shù)據(jù)結(jié)構(gòu)與算法系列精講之漢諾塔
漢諾塔是源于印度一個(gè)古老傳說(shuō)的益智玩具。大梵天創(chuàng)造世界時(shí)做了三根石柱，在一根柱子上從下往上按大小順序摞著64片黃金圓盤(pán)。大梵天命令婆羅門(mén)把圓盤(pán)從下面開(kāi)始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤(pán)上不能放大圓盤(pán)，三根柱子之間一次只能移動(dòng)一個(gè)圓盤(pán)2022-02-02
Springboot集成定時(shí)器和多線程異步處理操作
這篇文章主要介紹了Springboot集成定時(shí)器和多線程異步處理操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-09-09
使用Java實(shí)現(xiàn)PDF文字識(shí)別的方法詳解
在現(xiàn)代信息化的社會(huì)中,PDF文件已經(jīng)成為一種非常常見(jiàn)的文檔格式,本文將詳細(xì)介紹如何使用Java實(shí)現(xiàn)PDF文字識(shí)別,包括所需的工具、庫(kù)、代碼實(shí)現(xiàn)以及實(shí)際應(yīng)用中的注意事項(xiàng),需要的朋友可以參考下2025-02-02
JPA?使用criteria簡(jiǎn)單查詢工具類(lèi)方式
這篇文章主要介紹了JPA?使用criteria簡(jiǎn)單查詢工具類(lèi)方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-12-12
Java構(gòu)造器與傳值學(xué)習(xí)總結(jié)
這篇文章主要為大家詳細(xì)介紹了Java構(gòu)造器與傳值學(xué)習(xí)總結(jié)，文中示例介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-01-01