Java數(shù)據(jù)結(jié)構(gòu)之順序表篇
一.線性表
線性表（ linear list ） 是 n 個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見 的線性表：順序表、鏈表、棧、隊(duì)列、字符串... 線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲 時(shí)，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲。
二.順序表
1.概念及結(jié)構(gòu)
順序表是用一段 物理地址連續(xù) 的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲。在數(shù)組上完成數(shù)據(jù)的增刪查改。
而順序表一般可以分為兩類：靜態(tài)順序表、動態(tài)順序表
2.順序表的實(shí)現(xiàn)
首先我們將順序表的成員屬性以及構(gòu)造函數(shù)寫好，接下來實(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ù)組，然后將其打印出來即可
具體的代碼實(shí)現(xiàn)：
// 打印順序表
public void display() {
for (int i = 0; i <this.usedSize ; i++) {
System.out.print(elem[i]+" ");
}
System.out.println();
}獲取順序表的有效長度
有效長度就是已經(jīng)用過的元素，返回usedSize即可
具體的代碼實(shí)現(xiàn)：
// 獲取順序表的有效數(shù)據(jù)長度
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)對應(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.開始挪數(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++;//說明存放成功
}
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è)元素對應(yīng)的位置
跟上一個(gè)操作一樣，使用遍歷查找到元素后，返回其下標(biāo)即可
具體的代碼實(shí)現(xiàn)：
// 查找某個(gè)元素對應(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ù)組沒有負(fù)數(shù)下標(biāo)
}獲取/查找pos位置的元素
凡是傳入pos位置，我們都需要判斷pos是否合法，也要查看順序表是否為空，如果合法且不為空直接返回該下標(biāo)對應(yīng)的元素即可
具體的代碼實(shí)現(xiàn)：
// 獲取 pos 位置的元素
public int getPos(int pos) {
if (pos<0 || pos>this.usedSize){
System.out.println("pos位置不合法");
return -1;//說明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)對應(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)用我們上邊寫的search函數(shù)，看是否存在該元素
3、如果存在，則從該元素起，將后面的元素往前挪，將要刪除的元素覆蓋
具體的代碼實(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("沒有你要刪除的數(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)中是引用類型，則要將其置為空
}清空順序表
清空順序表，只需要把有效長度置于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í)候，都需要移動數(shù)據(jù)，時(shí)間復(fù)雜度為O(N)
2、擴(kuò)容也是問題，增容一般是呈2倍的增長，勢必會有一定的空間浪費(fèi)。例如當(dāng)前容量為100，滿了以后增容到200，我們再繼續(xù)插入5個(gè)數(shù)據(jù)，無后續(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ù)長度
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.開始挪數(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++;//說明存放成功
}
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è)元素對應(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ù)組沒有負(fù)數(shù)下標(biāo)
}
// 獲取 pos 位置的元素
public int getPos(int pos) {
if (pos<0 || pos>this.usedSize){
System.out.println("pos位置不合法");
return -1;//說明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("沒有你要刪除的數(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)中是引用類型，則要將其置為空
}
// 清空順序表
public void clear() {
this.usedSize = 0;
}
}到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之順序表篇的文章就介紹到這了,更多相關(guān)Java 順序表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- Java實(shí)現(xiàn)線性表的鏈?zhǔn)酱鎯?/a>
- java實(shí)現(xiàn)線性表及其算法
- java 線性表接口的實(shí)例詳解
- java線性表的存儲結(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)文章
本文介紹了對象存儲、服務(wù)器磁盤和分布式文件系統(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注解來取代繁瑣的@Autowrired
有了@RequiredArgsConstructor注解，我們就可以減少@Autowired的書寫，本文主要介紹了使用@RequiredArgsConstructor注解來取代繁瑣的@Autowrired，感興趣的可以了解一下2022-04-04
這篇文章主要介紹了struts2過濾器和攔截器的區(qū)別,簡單分析了struts2框架中過濾器和攔截器的概念與相關(guān)使用區(qū)別,需要的朋友可以參考下2016-04-04
equals是在object類中的方法,在object中equals是用來看看兩個(gè)參數(shù)是否引用的是同一個(gè)對象,下面這篇文章主要給大家介紹了關(guān)于Java中equals方法使用及重寫練習(xí)的相關(guān)資料,需要的朋友可以參考下2023-05-05
Java基礎(chǔ)第二篇方法與數(shù)據(jù)成員
在上一篇文章中介紹了Java基礎(chǔ) 從HelloWorld到面向?qū)ο?，我們初步了解了對?object)。對象中的數(shù)據(jù)成員表示對象的狀態(tài)。對象可以執(zhí)行方法，表示特定的動作。這篇文章我們進(jìn)一步深入到對象。了解Java中方法與數(shù)據(jù)成員的一些細(xì)節(jié)。2021-09-09
這篇文章主要介紹了Java object類及正則表達(dá)式原理解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-07-07
這篇文章主要介紹了我對@RestController注解的理解,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-03-03
本文是小編給大家?guī)Я说腟pringmvc restful配置遇到的小小坑，小編給大家?guī)砹藛栴}原因及解決辦法，非常不錯，具有參考借鑒價(jià)值，感興趣的朋友一起看下吧2016-07-07
在程序的世界里面,比較也是必不可少的,通過比較可以確定對象的相對順序、相等性以及其他比較條件,下面我們就來深入了解一下java中常見的五種比較方法吧2023-12-12