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ù)的，線性表在物理上存儲(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ù)的增刪查改。
而順序表一般可以分為兩類：靜態(tài)順序表、動(dòng)態(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();
}獲取順序表的有效長(zhǎng)度
有效長(zhǎng)度就是已經(jīng)用過的元素，返回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.開始挪數(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è)元素對(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ù)組沒有負(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;//說明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)用我們上邊寫的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("沒有你要?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)中是引用類型，則要將其置為空
}清空順序表
清空順序表，只需要把有效長(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ò)容也是問題，增容一般是呈2倍的增長(zhǎng)，勢(shì)必會(huì)有一定的空間浪費(fèi)。例如當(dāng)前容量為100，滿了以后增容到200，我們?cè)倮^續(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ù)長(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.開始挪數(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è)元素對(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ù)組沒有負(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("沒有你要?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)中是引用類型，則要將其置為空
}
// 清空順序表
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)文章
這篇文章主要介紹了java格式化時(shí)間示例,需要的朋友可以參考下2014-04-04
本篇文章將為大家詳細(xì)介紹一下springmvc的異常處理機(jī)制，用到了ControllerAdvice和ExceptionHandler注解，感興趣的小伙伴可以了解一下2022-07-07
Spring實(shí)戰(zhàn)之@Autowire注解用法詳解
這篇文章主要介紹了Spring實(shí)戰(zhàn)之@Autowire注解用法,結(jié)合實(shí)例形式詳細(xì)分析了Spring @Autowire注解具體實(shí)現(xiàn)步驟與相關(guān)使用技巧,需要的朋友可以參考下2019-12-12
Spring的請(qǐng)求映射handlerMapping以及原理詳解
這篇文章主要介紹了Spring的請(qǐng)求映射handlerMapping以及原理詳解,我們每次發(fā)請(qǐng)求,它到底是怎么找到我們哪個(gè)方法來去處理這個(gè)請(qǐng)求,因?yàn)槲覀冎浪械恼?qǐng)求過來都會(huì)來到DispatcherServlet,springboot底層還是使用的是springMVC,需要的朋友可以參考下2023-08-08
SpringBoot異步實(shí)現(xiàn)的8種方式
異步執(zhí)行對(duì)于開發(fā)者來說并不陌生,在實(shí)際的開發(fā)過程中,很多場(chǎng)景多會(huì)使用到異步,本文主要介紹了SpringBoot異步實(shí)現(xiàn)的8種方式,具有一定的參考價(jià)值,感興趣的可以了解一下2023-09-09
這篇文章主要介紹了spring緩存代碼詳解，分享了相關(guān)代碼示例，小編覺得還是挺不錯(cuò)的，具有一定借鑒價(jià)值，需要的朋友可以參考下2018-02-02
Spring Boot實(shí)戰(zhàn)之發(fā)送郵件示例代碼
本篇文章主要介紹了Spring Boot實(shí)戰(zhàn)之發(fā)送郵件示例代碼，具有一定的參考價(jià)值，有興趣的可以了解一下。2017-03-03
這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)小球碰撞功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-01-01
這篇文章主要介紹了java實(shí)現(xiàn)的圖片裁剪功能,涉及java針對(duì)圖片的讀取、轉(zhuǎn)換、保存等相關(guān)操作技巧,需要的朋友可以參考下2017-10-10
這篇文章主要介紹了Java編程中常用的基本描述符與運(yùn)算符整理,包括運(yùn)算符優(yōu)先級(jí)等平時(shí)經(jīng)常查看反復(fù)記憶的知識(shí)點(diǎn),需要的朋友可以參考下2016-02-02