Java數據結構之順序表篇
更新時間：2022年01月19日 16:51:36 作者：ViolentAsteroid
順序表，全名順序存儲結構，是線性表的一種。線性表用于存儲邏輯關系為“一對一”的數據，順序表自然也不例外，不僅如此，順序表對數據物理存儲結構也有要求。順序表存儲數據時，會提前申請一整塊足夠大小的物理空間，然后將數據依次存儲起來，存儲時數據元素間不留縫隙
一.線性表
線性表（ linear list ） 是 n 個具有相同特性的數據元素的有限序列。 線性表是一種在實際中廣泛使用的數據結構，常見 的線性表：順序表、鏈表、棧、隊列、字符串... 線性表在邏輯上是線性結構，也就說是連續(xù)的一條直線。但是在物理結構上并不一定是連續(xù)的，線性表在物理上存儲 時，通常以數組和鏈式結構的形式存儲。
二.順序表
1.概念及結構
順序表是用一段 物理地址連續(xù) 的存儲單元依次存儲數據元素的線性結構，一般情況下采用數組存儲。在數組上完成數據的增刪查改。
而順序表一般可以分為兩類：靜態(tài)順序表、動態(tài)順序表
2.順序表的實現
首先我們將順序表的成員屬性以及構造函數寫好，接下來實現具體接口
public class MyArrayList {
public int[] elem;
public int usedSize;//有效的數據個數，默認值為0
public MyArrayList() {//初始化一個數組，容量為5
this.elem = new int[5];
}
}打印順序表
只需要遍歷完數組，然后將其打印出來即可
具體的代碼實現：
// 打印順序表
public void display() {
for (int i = 0; i <this.usedSize ; i++) {
System.out.print(elem[i]+" ");
}
System.out.println();
}獲取順序表的有效長度
有效長度就是已經用過的元素，返回usedSize即可
具體的代碼實現：
// 獲取順序表的有效數據長度
public int size() {
return usedSize;
}在pos位置新增元素
具體的操作分為四步：
1、判斷pos位置是否合法，即pos既不能小于0，也不能大于有效數據個數
2、判斷順序表是否已滿，如果滿了，需要Arrays.CopyOf()進行擴容
3、將pos后的元素依次后移，即 elem[i+1]=elem[i]
4、將目標元素data放入pos下標對應位置，即elem[pos]=data
具體的代碼實現：
// 在 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.開始挪數據,并且給pos位置賦值
for (int i = usedSize-1; i >= pos ; i--) {
elem[i+1]=elem[i];//把i下標的值給i+1
}
this.elem[pos]=data;
this.usedSize++;//說明存放成功
}
public boolean isFull(){
return this.usedSize == this.elem.length;
}判斷是否包含某個元素
只需要傳入需要查找的元素toFind，然后遍歷查找即可
具體的代碼實現：
// 判定是否包含某個元素
public boolean contains(int toFind) {
for (int i = 0; i <this.usedSize ; i++) {
if (this.elem[i]==toFind)
return true;
}
return false;
}查找某個元素對應的位置
跟上一個操作一樣，使用遍歷查找到元素后，返回其下標即可
具體的代碼實現：
// 查找某個元素對應的位置
public int search(int toFind) {
for (int i = 0; i < this.usedSize; i++) {
if (this.elem[i]==toFind)
return i;//找到了返回i下標
}
return -1; //找不到返回-1，因為數組沒有負數下標
}獲取/查找pos位置的元素
凡是傳入pos位置，我們都需要判斷pos是否合法，也要查看順序表是否為空，如果合法且不為空直接返回該下標對應的元素即可
具體的代碼實現：
// 獲取 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位置的元素設為value
依然先判斷pos位置是否合法，再判斷順序表是否為空，如果合法且不為空，則將value賦值給pos下標對應的元素
具體的代碼實現：
// 給 pos 位置的元素設為/更新為 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
}刪除第一次出現的關鍵字key
具體步驟如下：
1、判斷順序表是否為空(除了增加元素是判斷順序表是否已滿，其他的都是判斷是否為空)
2、調用我們上邊寫的search函數，看是否存在該元素
3、如果存在，則從該元素起，將后面的元素往前挪，將要刪除的元素覆蓋
具體的代碼實現如下：
//刪除第一次出現的關鍵字key
public void remove(int toRemove) {
if (isEmpty()){
System.out.println("順序表為空");
return;
}
int index = search(toRemove);
if (index==-1) {
System.out.println("沒有你要刪除的數字");
return;
}
for (int i = index; i < usedSize-1; i++) {
this.elem[i]=this.elem[i+1];
}
this.usedSize--;
//this.elem[usedSize]=null; 如果數組當中是引用類型，則要將其置為空
}清空順序表
清空順序表，只需要把有效長度置于0即可
具體的代碼實現：
// 清空順序表
public void clear() {
this.usedSize = 0;
}3.順序表的優(yōu)、缺點
優(yōu)點：由于順序表是物理和邏輯上都連續(xù)的，可以快速查找到當前數據，時間復雜度為O(1)
缺點：
1、刪除和插入數據的時候，都需要移動數據，時間復雜度為O(N)
2、擴容也是問題，增容一般是呈2倍的增長，勢必會有一定的空間浪費。例如當前容量為100，滿了以后增容到200，我們再繼續(xù)插入5個數據，無后續(xù)數據插入，那么就浪費了95個數據空間
那么順序表的缺點怎么才能解決呢？鏈表很好的解決了順序表的缺點，隨用隨取，需要空間的時候就new一個結點。需要注意的是，鏈表是物理上不連續(xù)，而邏輯上連續(xù)。
三.順序表的實現代碼匯總
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();
}
// 獲取順序表的有效數據長度
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.開始挪數據,并且給pos位置賦值
for (int i = usedSize-1; i >= pos ; i--) {
elem[i+1]=elem[i];//把i下標的值給i+1
}
this.elem[pos]=data;
this.usedSize++;//說明存放成功
}
public boolean isFull(){
return this.usedSize == this.elem.length;
}
// 判定是否包含某個元素
public boolean contains(int toFind) {
for (int i = 0; i <this.usedSize ; i++) {
if (this.elem[i]==toFind)
return true;
}
return false;
}
// 查找某個元素對應的位置
public int search(int toFind) {
for (int i = 0; i < this.usedSize; i++) {
if (this.elem[i]==toFind)
return i;//找到了返回i下標
}
return -1; //找不到返回-1，因為數組沒有負數下標
}
// 獲取 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 位置的元素設為/更新為 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
}
//刪除第一次出現的關鍵字key
public void remove(int toRemove) {
if (isEmpty()){
System.out.println("順序表為空");
return;
}
int index = search(toRemove);
if (index==-1) {
System.out.println("沒有你要刪除的數字");
return;
}
for (int i = index; i < usedSize-1; i++) {
this.elem[i]=this.elem[i+1];
}
this.usedSize--;
//this.elem[usedSize]=null; 如果數組當中是引用類型，則要將其置為空
}
// 清空順序表
public void clear() {
this.usedSize = 0;
}
}到此這篇關于Java數據結構之順序表篇的文章就介紹到這了,更多相關Java 順序表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了java格式化時間示例,需要的朋友可以參考下2014-04-04
本篇文章將為大家詳細介紹一下springmvc的異常處理機制，用到了ControllerAdvice和ExceptionHandler注解，感興趣的小伙伴可以了解一下2022-07-07
Spring實戰(zhàn)之@Autowire注解用法詳解
這篇文章主要介紹了Spring實戰(zhàn)之@Autowire注解用法,結合實例形式詳細分析了Spring @Autowire注解具體實現步驟與相關使用技巧,需要的朋友可以參考下2019-12-12
Spring的請求映射handlerMapping以及原理詳解
這篇文章主要介紹了Spring的請求映射handlerMapping以及原理詳解,我們每次發(fā)請求,它到底是怎么找到我們哪個方法來去處理這個請求,因為我們知道所有的請求過來都會來到DispatcherServlet,springboot底層還是使用的是springMVC,需要的朋友可以參考下2023-08-08
異步執(zhí)行對于開發(fā)者來說并不陌生,在實際的開發(fā)過程中,很多場景多會使用到異步,本文主要介紹了SpringBoot異步實現的8種方式,具有一定的參考價值,感興趣的可以了解一下2023-09-09
這篇文章主要介紹了spring緩存代碼詳解，分享了相關代碼示例，小編覺得還是挺不錯的，具有一定借鑒價值，需要的朋友可以參考下2018-02-02
Spring Boot實戰(zhàn)之發(fā)送郵件示例代碼
本篇文章主要介紹了Spring Boot實戰(zhàn)之發(fā)送郵件示例代碼，具有一定的參考價值，有興趣的可以了解一下。2017-03-03
這篇文章主要為大家詳細介紹了java實現小球碰撞功能，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-01-01
這篇文章主要介紹了java實現的圖片裁剪功能,涉及java針對圖片的讀取、轉換、保存等相關操作技巧,需要的朋友可以參考下2017-10-10
這篇文章主要介紹了Java編程中常用的基本描述符與運算符整理,包括運算符優(yōu)先級等平時經常查看反復記憶的知識點,需要的朋友可以參考下2016-02-02