Java數(shù)據(jù)結(jié)構(gòu)之順序表篇
一.線性表
線性表（ linear list ） 是 n 個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見(jiàn) 的線性表：順序表、鏈表、棧、隊(duì)列、字符串... 線性表在邏輯上是線性結(jié)構(gòu)，也就說(shuō)是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲(chǔ) 時(shí)，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲(chǔ)。
二.順序表
1.概念及結(jié)構(gòu)
順序表是用一段 物理地址連續(xù) 的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲(chǔ)。在數(shù)組上完成數(shù)據(jù)的增刪查改。
而順序表一般可以分為兩類(lèi)：靜態(tài)順序表、動(dòng)態(tài)順序表
2.順序表的實(shí)現(xiàn)
首先我們將順序表的成員屬性以及構(gòu)造函數(shù)寫(xiě)好，接下來(lái)實(shí)現(xiàn)具體接口
public class MyArrayList {
public int[] elem;
public int usedSize;//有效的數(shù)據(jù)個(gè)數(shù)，默認(rèn)值為0
public MyArrayList() {//初始化一個(gè)數(shù)組，容量為5
this.elem = new int[5];
}
}打印順序表
只需要遍歷完數(shù)組，然后將其打印出來(lái)即可
具體的代碼實(shí)現(xiàn)：
// 打印順序表
public void display() {
for (int i = 0; i <this.usedSize ; i++) {
System.out.print(elem[i]+" ");
}
System.out.println();
}獲取順序表的有效長(zhǎng)度
有效長(zhǎng)度就是已經(jīng)用過(guò)的元素，返回usedSize即可
具體的代碼實(shí)現(xiàn)：
// 獲取順序表的有效數(shù)據(jù)長(zhǎng)度
public int size() {
return usedSize;
}在pos位置新增元素
具體的操作分為四步：
1、判斷pos位置是否合法，即pos既不能小于0，也不能大于有效數(shù)據(jù)個(gè)數(shù)
2、判斷順序表是否已滿，如果滿了，需要Arrays.CopyOf()進(jìn)行擴(kuò)容
3、將pos后的元素依次后移，即 elem[i+1]=elem[i]
4、將目標(biāo)元素data放入pos下標(biāo)對(duì)應(yīng)位置，即elem[pos]=data
具體的代碼實(shí)現(xiàn)：
// 在 pos 位置新增元素
public void add(int pos, int data) {
//1.判斷pos位置是否合法
if (pos<0 || pos>usedSize){
System.out.println("pos位置不合法");
return;
}
//2.判斷usedSize是否已滿
if (isFull()){
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
//3.開(kāi)始挪數(shù)據(jù),并且給pos位置賦值
for (int i = usedSize-1; i >= pos ; i--) {
elem[i+1]=elem[i];//把i下標(biāo)的值給i+1
}
this.elem[pos]=data;
this.usedSize++;//說(shuō)明存放成功
}
public boolean isFull(){
return this.usedSize == this.elem.length;
}判斷是否包含某個(gè)元素
只需要傳入需要查找的元素toFind，然后遍歷查找即可
具體的代碼實(shí)現(xiàn)：
// 判定是否包含某個(gè)元素
public boolean contains(int toFind) {
for (int i = 0; i <this.usedSize ; i++) {
if (this.elem[i]==toFind)
return true;
}
return false;
}查找某個(gè)元素對(duì)應(yīng)的位置
跟上一個(gè)操作一樣，使用遍歷查找到元素后，返回其下標(biāo)即可
具體的代碼實(shí)現(xiàn)：
// 查找某個(gè)元素對(duì)應(yīng)的位置
public int search(int toFind) {
for (int i = 0; i < this.usedSize; i++) {
if (this.elem[i]==toFind)
return i;//找到了返回i下標(biāo)
}
return -1; //找不到返回-1，因?yàn)閿?shù)組沒(méi)有負(fù)數(shù)下標(biāo)
}獲取/查找pos位置的元素
凡是傳入pos位置，我們都需要判斷pos是否合法，也要查看順序表是否為空，如果合法且不為空直接返回該下標(biāo)對(duì)應(yīng)的元素即可
具體的代碼實(shí)現(xiàn)：
// 獲取 pos 位置的元素
public int getPos(int pos) {
if (pos<0 || pos>this.usedSize){
System.out.println("pos位置不合法");
return -1;//說(shuō)明pos位置不合法
}
if(isEmpty()){
System.out.println("順序表為空");
return -1;
}
return this.elem[pos];//返回pos位置的值
}
public boolean isEmpty(){
return this.usedSize==0;
}給pos位置的元素設(shè)為value
依然先判斷pos位置是否合法，再判斷順序表是否為空，如果合法且不為空，則將value賦值給pos下標(biāo)對(duì)應(yīng)的元素
具體的代碼實(shí)現(xiàn)：
// 給 pos 位置的元素設(shè)為/更新為 value
public void setPos(int pos, int value) {
//還是要先判斷pos位置的合法性
if (pos<0 || pos>usedSize){
System.out.println("pos位置不合法");
return;
}
if(isEmpty()){
System.out.println("順序表為空");
return ;
}
this.elem[pos] = value;//將pos位置的元素更新為value
}刪除第一次出現(xiàn)的關(guān)鍵字key
具體步驟如下：
1、判斷順序表是否為空(除了增加元素是判斷順序表是否已滿，其他的都是判斷是否為空)
2、調(diào)用我們上邊寫(xiě)的search函數(shù)，看是否存在該元素
3、如果存在，則從該元素起，將后面的元素往前挪，將要?jiǎng)h除的元素覆蓋
具體的代碼實(shí)現(xiàn)如下：
//刪除第一次出現(xiàn)的關(guān)鍵字key
public void remove(int toRemove) {
if (isEmpty()){
System.out.println("順序表為空");
return;
}
int index = search(toRemove);
if (index==-1) {
System.out.println("沒(méi)有你要?jiǎng)h除的數(shù)字");
return;
}
for (int i = index; i < usedSize-1; i++) {
this.elem[i]=this.elem[i+1];
}
this.usedSize--;
//this.elem[usedSize]=null; 如果數(shù)組當(dāng)中是引用類(lèi)型，則要將其置為空
}清空順序表
清空順序表，只需要把有效長(zhǎng)度置于0即可
具體的代碼實(shí)現(xiàn)：
// 清空順序表
public void clear() {
this.usedSize = 0;
}3.順序表的優(yōu)、缺點(diǎn)
優(yōu)點(diǎn)：由于順序表是物理和邏輯上都連續(xù)的，可以快速查找到當(dāng)前數(shù)據(jù)，時(shí)間復(fù)雜度為O(1)
缺點(diǎn)：
1、刪除和插入數(shù)據(jù)的時(shí)候，都需要移動(dòng)數(shù)據(jù)，時(shí)間復(fù)雜度為O(N)
2、擴(kuò)容也是問(wèn)題，增容一般是呈2倍的增長(zhǎng)，勢(shì)必會(huì)有一定的空間浪費(fèi)。例如當(dāng)前容量為100，滿了以后增容到200，我們?cè)倮^續(xù)插入5個(gè)數(shù)據(jù)，無(wú)后續(xù)數(shù)據(jù)插入，那么就浪費(fèi)了95個(gè)數(shù)據(jù)空間
那么順序表的缺點(diǎn)怎么才能解決呢？鏈表很好的解決了順序表的缺點(diǎn)，隨用隨取，需要空間的時(shí)候就new一個(gè)結(jié)點(diǎn)。需要注意的是，鏈表是物理上不連續(xù)，而邏輯上連續(xù)。
三.順序表的實(shí)現(xiàn)代碼匯總
public class MyArrayList {
public int[] elem;
public int usedSize;
public MyArrayList() {
this.elem = new int[5];
}
// 打印順序表
public void display() {
for (int i = 0; i <this.usedSize ; i++) {
System.out.print(elem[i]+" ");
}
System.out.println();
}
// 獲取順序表的有效數(shù)據(jù)長(zhǎng)度
public int size() {
return usedSize;
}
// 在 pos 位置新增元素
public void add(int pos, int data) {
//1.判斷pos位置是否合法
if (pos<0 || pos>usedSize){
System.out.println("pos位置不合法");
return;
}
//2.判斷usedSize是否已滿
if (isFull()){
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
//3.開(kāi)始挪數(shù)據(jù),并且給pos位置賦值
for (int i = usedSize-1; i >= pos ; i--) {
elem[i+1]=elem[i];//把i下標(biāo)的值給i+1
}
this.elem[pos]=data;
this.usedSize++;//說(shuō)明存放成功
}
public boolean isFull(){
return this.usedSize == this.elem.length;
}
// 判定是否包含某個(gè)元素
public boolean contains(int toFind) {
for (int i = 0; i <this.usedSize ; i++) {
if (this.elem[i]==toFind)
return true;
}
return false;
}
// 查找某個(gè)元素對(duì)應(yīng)的位置
public int search(int toFind) {
for (int i = 0; i < this.usedSize; i++) {
if (this.elem[i]==toFind)
return i;//找到了返回i下標(biāo)
}
return -1; //找不到返回-1，因?yàn)閿?shù)組沒(méi)有負(fù)數(shù)下標(biāo)
}
// 獲取 pos 位置的元素
public int getPos(int pos) {
if (pos<0 || pos>this.usedSize){
System.out.println("pos位置不合法");
return -1;//說(shuō)明pos位置不合法
}
if(isEmpty()){
System.out.println("順序表為空");
return -1;
}
return this.elem[pos];//返回pos位置的值
}
public boolean isEmpty(){
return this.usedSize==0;
}
// 給 pos 位置的元素設(shè)為/更新為 value
public void setPos(int pos, int value) {
//還是要先判斷pos位置的合法性
if (pos<0 || pos>usedSize){
System.out.println("pos位置不合法");
return;
}
if(isEmpty()){
System.out.println("順序表為空");
return ;
}
this.elem[pos] = value;//將pos位置的元素更新為value
}
//刪除第一次出現(xiàn)的關(guān)鍵字key
public void remove(int toRemove) {
if (isEmpty()){
System.out.println("順序表為空");
return;
}
int index = search(toRemove);
if (index==-1) {
System.out.println("沒(méi)有你要?jiǎng)h除的數(shù)字");
return;
}
for (int i = index; i < usedSize-1; i++) {
this.elem[i]=this.elem[i+1];
}
this.usedSize--;
//this.elem[usedSize]=null; 如果數(shù)組當(dāng)中是引用類(lèi)型，則要將其置為空
}
// 清空順序表
public void clear() {
this.usedSize = 0;
}
}到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之順序表篇的文章就介紹到這了,更多相關(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)順序表從零基礎(chǔ)到精通進(jìn)階
- Java?精煉解讀數(shù)據(jù)結(jié)構(gòu)的順序表如何操作
- Java實(shí)現(xiàn)順序表和鏈表結(jié)構(gòu)
- Java實(shí)現(xiàn)順序表的操作
- Java中ArrayList與順序表的概念與使用實(shí)例
- Java線性表的順序表示及實(shí)現(xiàn)
相關(guān)文章
本文介紹了對(duì)象存儲(chǔ)、服務(wù)器磁盤(pán)和分布式文件系統(tǒng)的基本概念和區(qū)別,重點(diǎn)講解了MinIO的安裝、配置和基本操作,以及如何在SpringBoot項(xiàng)目中集成MinIO,感興趣的朋友一起看看吧2025-02-02
Java 同步鎖(synchronized)詳解及實(shí)例
這篇文章主要介紹了Java 同步鎖(synchronized)詳解及實(shí)例的相關(guān)資料,需要的朋友可以參考下2017-03-03
使用@RequiredArgsConstructor注解來(lái)取代繁瑣的@Autowrired
有了@RequiredArgsConstructor注解，我們就可以減少@Autowired的書(shū)寫(xiě)，本文主要介紹了使用@RequiredArgsConstructor注解來(lái)取代繁瑣的@Autowrired，感興趣的可以了解一下2022-04-04
這篇文章主要介紹了struts2過(guò)濾器和攔截器的區(qū)別,簡(jiǎn)單分析了struts2框架中過(guò)濾器和攔截器的概念與相關(guān)使用區(qū)別,需要的朋友可以參考下2016-04-04
equals是在object類(lèi)中的方法,在object中equals是用來(lái)看看兩個(gè)參數(shù)是否引用的是同一個(gè)對(duì)象,下面這篇文章主要給大家介紹了關(guān)于Java中equals方法使用及重寫(xiě)練習(xí)的相關(guān)資料,需要的朋友可以參考下2023-05-05
Java基礎(chǔ)第二篇方法與數(shù)據(jù)成員
在上一篇文章中介紹了Java基礎(chǔ) 從HelloWorld到面向?qū)ο?，我們初步了解了?duì)象(object)。對(duì)象中的數(shù)據(jù)成員表示對(duì)象的狀態(tài)。對(duì)象可以執(zhí)行方法，表示特定的動(dòng)作。這篇文章我們進(jìn)一步深入到對(duì)象。了解Java中方法與數(shù)據(jù)成員的一些細(xì)節(jié)。2021-09-09
Java object類(lèi)及正則表達(dá)式原理解析
這篇文章主要介紹了Java object類(lèi)及正則表達(dá)式原理解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-07-07
這篇文章主要介紹了我對(duì)@RestController注解的理解,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-03-03
本文是小編給大家?guī)Я说腟pringmvc restful配置遇到的小小坑，小編給大家?guī)?lái)了問(wèn)題原因及解決辦法，非常不錯(cuò)，具有參考借鑒價(jià)值，感興趣的朋友一起看下吧2016-07-07
在程序的世界里面,比較也是必不可少的,通過(guò)比較可以確定對(duì)象的相對(duì)順序、相等性以及其他比較條件,下面我們就來(lái)深入了解一下java中常見(jiàn)的五種比較方法吧2023-12-12