??前面的話??
本篇文章帶大家認識資料結構與演算法基礎，順序表（動態），所謂的順序表本質就是陣列，它的特點是物理結構與邏輯結構都是連續的，最大的優點就是能夠隨機訪問，最大的缺點是空間有限，就算擴容，也有可能存在大量的記憶體浪費，描述代碼：Java，
📒博客主頁：未見花聞的博客主頁
🎉歡迎關注🔎點贊👍收藏??留言📝
📌本文由未見花聞原創，CSDN首發！
📆首發時間：🌴2021年11月10日🌴
??堅持和努力一定能換來詩與遠方！
💭參考書籍：📚《趣學資料結構》，📚《資料結構(C語言版)》，📚《趣學演算法》
💬參考在線編程網站：🌐牛客網🌐力扣
博主的碼云gitee，平常博主寫的程式代碼都在里面，
博主的github，平常博主寫的程式代碼都在里面，
🙏作者水平很有限，如果發現錯誤，一定要及時告知作者哦！感謝感謝！
📌導航小助手📌
- 🍓1.順序表基本理論
- 🍇1.1線性表
- 🍇1.2順序表
- 🍅1.2.1概念與特點
- 🍅1.2.2順序表實作介面
- 🍓2.動態順序表實踐
- 🍇2.1動態順序表基本結構
- 🍇2.2初始化
- 🍇2.3順序插入資料
- 🍇2.4指定位置插入資料
- 🍇2.5列印順序表
- 🍇2.6判斷順序表中是否包含某資料
- 🍅2.6.1判定是否包含某個元素
- 🍅2.6.2查找某個元素對應的位置
- 🍇2.7指定位置的值
- 🍅2.7.1獲取指定位置元素
- 🍅2.7.2修改指定位置元素
- 🍇2.8洗掉第一次出現的指定資料
- 🍇2.9獲取有效元素個數
- 🍇2.10洗掉整個順序表
- 🍓3.源代碼
- 🍇3.1動態順序表實作代碼
- 🍇3.2測驗專用代碼
- 🍇3.3專案檔案
🍓1.順序表基本理論
🍇1.1線性表
線性表（linear list）是n個具有相同特性的資料元素的有限序列， 線性表是一種在實際中廣泛使用的資料結構，常見的線性表：順序表、鏈表、堆疊、佇列、字串…
線性表在邏輯上是線性結構，也就說是連續的一條直線，但是在物理結構上并不一定是連續的，線性表在物理上存盤時，通常以陣列和鏈式結構的形式存盤，
本篇文章介紹的是最簡單的資料結構——順序表，
🍇1.2順序表
🍅1.2.1概念與特點
順序表是用一段物理地址連續的存盤單元依次存盤資料元素的線性結構，一般情況下采用陣列存盤，在陣列上完成資料的增刪查改，
順序表一般可以分為：
- 靜態順序表：使用定長陣列存盤，
- 動態順序表：使用動態開辟的陣列存盤，
靜態順序表適用于確定知道需要存多少資料的場景.
靜態順序表的定長陣列導致N定大了，空間開多了浪費，開少了不夠用.
相比之下動態順序表更靈活, 根據需要動態的分配空間大小.
靜態順序表：
class StaticSeq {
public int Maxsize;
int[] elem = new int[Maxsize];//資料域
public int size;//有效元素個數
public StaticSeq(int capacity) {
this.Maxsize = capacity;//構造方法，用來確定靜態順序表的容量
}
}
動態順序表：
class DynamicSeq {
public int[] elem;//資料域參考
public int size;//有效元素個數
}
本篇文章將介紹動態順序表增刪查改的實作，靜態順序表不多贅述！
🍅1.2.2順序表實作介面
//初始化順序表
public void initSeqList(){
}
// 列印順序表
public void display() {
}
// 在 pos 位置新增元素
public void add(int pos, int data) {
}
public boolean isFull() {
}
public boolean isEmpty() {
}
// 判定是否包含某個元素
public boolean contains(int toFind) {
}
// 查找某個元素對應的位置
public int search(int toFind) {
}
//順序插入元素
public void seqAdd(int value) {
}
// 獲取 pos 位置的元素
public int getPos(int pos) {
}
// 給 pos 位置的元素設為 value
public void setPos(int pos, int value) {
}
//洗掉第一次出現的關鍵字key
public void remove(int toRemove) {
}
// 獲取順序表長度
public int size() {
}
// 清空順序表
public void clear() {
}
🍓2.動態順序表實踐
🍇2.1動態順序表基本結構
class DynamicSeq {
public int[] elem;//資料域參考
public int size;//有效元素個數
}
🍇2.2初始化
順序表的本質是陣列，要使用順序表必須有一段初始的空間，我初始化順序表時，為順序表開辟了10個資料空間，
//初始化順序表
public void initSeqList(){
this.elem = new int[10];
}
每次使用新的順序表還需要自己構造物件呼叫初始化方法，太麻煩了，我們讓順序表在執行構造方法階段就完成順序表的初始化，
public class SeqList {
public int[] elem;
public int size;
public SeqList() {
this.initSeqList();
}
}
🍇2.3順序插入資料
在最后一個有效元素后插入一個資料，當然，在此之前需要判斷順序表有沒有滿，如果滿了需要先擴容再插入，判斷順序表滿沒滿很簡單，就看他的有效元素個數是否與陣列長度相等，如果相等就代表順序表滿了，
//判斷順序表是否滿
public boolean isFull() {
return this.size == this.elem.length;
}
//順序插入元素
public void seqAdd(int value) {
if (this.elem == null) {
this.initSeqList();
}
if (this.isFull()) {
this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);//擴容
}
this.elem[this.size] = value;
this.size++;
}
🍇2.4指定位置插入資料
這個與順序插入很相似，只不過多了一個條件：在指定位置插入，那怎么解決這個問題？你不能直接接訪問這個位置然后修改這個位置元素的值，這是修改，不是插入，由于順序表的“指標”是指向最后一個元素的后一個空間，所以我們需要先將指定位置的資料以及后面的資料先全部往后移動一個位置，然后再將指定位置的值改為目標資料，假設需要在順序表下標為3的位置插入一個數字22，
// 在 pos 位置新增元素
public void add(int pos, int data) {
if (this.elem == null) {
this.initSeqList();
}
if (pos < 0 || pos > this.size) {
System.out.println("插入位置非法！");
return;
}
if (isFull()) {
this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
}
for (int i = size - 1; i >= pos; i--) {
this.elem[i+1] = this.elem[i];
}
this.elem[pos] = data;
this.size++;
}
🍇2.5列印順序表
遍歷大法就能搞定！
// 列印順序表
public void display() {
for (int i = 0; i < this.size; i++) {
System.out.print(this.elem[i] + " ");
}
System.out.println();
}
🍇2.6判斷順序表中是否包含某資料
遍歷順序表，找到就回傳，
🍅2.6.1判定是否包含某個元素
// 判定是否包含某個元素
public boolean contains(int toFind) {
for (int j : this.elem) {
if (j == toFind) {
return true;
}
}
return false;//回圈走完，表示沒找到
}
🍅2.6.2查找某個元素對應的位置
// 查找某個元素對應的位置
public int search(int toFind) {
for (int i = 0; i < this.size; i++) {
if (this.elem[i] == toFind) {
return i;
}
}
return -1;//回圈走完，表示沒找到
}
🍇2.7指定位置的值
先判斷位置是否合理，再直接訪問回傳，
🍅2.7.1獲取指定位置元素
// 獲取 pos 位置的元素
public int getPos(int pos) {
if (pos < 0 || pos >= this.size) {
System.out.println("位置非法！");
return -1;
}
return this.elem[pos];
}
🍅2.7.2修改指定位置元素
// 給 pos 位置的元素修改為 value
public void setPos(int pos, int value) {
if (pos < 0 || pos >= this.size) {
System.out.println("修改位置非法！");
return;
}
this.elem[pos] = value;
}
🍇2.8洗掉第一次出現的指定資料
首先判斷順序表是否為空，為空直接回傳，如果順序表不為空再遍歷找到元素并洗掉，
//洗掉第一次出現的關鍵字key
public void remove(int toRemove) {
if (isEmpty()) {
System.out.println("順序表為空！");
return;
}
for (int i = 0; i < this.size; i++) {
if (this.elem[i] == toRemove) {
for (int j = i; j < this.size - 1; j++) {
this.elem[j] = this.elem[j+1];
}
this.size--;
return;
}
}
System.out.println("未找到！");
}
🍇2.9獲取有效元素個數
訪問size的值即可，
// 獲取順序表長度
public int size() {
return this.size;
}
🍇2.10洗掉整個順序表
這個要注意一件事，如果順序表的資料是參考型別的，需要先將所有元素的值全部置位null再將size置為0，當然，如果是基本資料，直接將size置為0即可，
// 清空順序表
public void clear() {
this.size = 0;
}
🍓3.源代碼
🍇3.1動態順序表實作代碼
import java.util.Arrays;
class StaticSeq {
public int Maxsize;
int[] elem = new int[Maxsize];//資料域
public int size;//有效元素個數
public StaticSeq(int capacity) {
this.Maxsize = capacity;//構造方法，用來確定靜態順序表的容量
}
}
class DynamicSeq {
public int[] elem;//資料域參考
public int size;//有效元素個數
}
public class SeqList {
public int[] elem;
public int size;
public SeqList() {
this.initSeqList();
}
//初始化順序表
public void initSeqList(){
this.elem = new int[10];
}
// 列印順序表
public void display() {
for (int i = 0; i < this.size; i++) {
System.out.print(this.elem[i] + " ");
}
System.out.println();
}
// 在 pos 位置新增元素
public void add(int pos, int data) {
if (this.elem == null) {
this.initSeqList();
}
if (pos < 0 || pos > this.size) {
System.out.println("插入位置非法！");
return;
}
if (isFull()) {
this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
}
for (int i = size - 1; i >= pos; i--) {
this.elem[i+1] = this.elem[i];
}
this.elem[pos] = data;
this.size++;
}
public boolean isFull() {
return this.size == this.elem.length;
}
public boolean isEmpty() {
return this.size == 0;
}
// 判定是否包含某個元素
public boolean contains(int toFind) {
for (int j : this.elem) {
if (j == toFind) {
return true;
}
}
return false;
}
// 查找某個元素對應的位置
public int search(int toFind) {
for (int i = 0; i < this.size; i++) {
if (this.elem[i] == toFind) {
return i;
}
}
return -1;
}
//順序插入元素
public void seqAdd(int value) {
if (this.elem == null) {
this.initSeqList();
}
if (this.isFull()) {
this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
}
this.elem[this.size] = value;
this.size++;
}
// 獲取 pos 位置的元素
public int getPos(int pos) {
if (pos < 0 || pos >= this.size) {
System.out.println("位置非法！");
return -1;
}
return this.elem[pos];
}
// 給 pos 位置的元素設為 value
public void setPos(int pos, int value) {
if (pos < 0 || pos >= this.size) {
System.out.println("修改位置非法！");
return;
}
this.elem[pos] = value;
}
//洗掉第一次出現的關鍵字key
public void remove(int toRemove) {
if (isEmpty()) {
System.out.println("順序表為空！");
return;
}
for (int i = 0; i < this.size; i++) {
if (this.elem[i] == toRemove) {
for (int j = i; j < this.size - 1; j++) {
this.elem[j] = this.elem[j+1];
}
this.size--;
return;
}
}
System.out.println("未找到！");
}
// 獲取順序表長度
public int size() {
return this.size;
}
// 清空順序表
public void clear() {
this.size = 0;
}
}
🍇3.2測驗專用代碼
public class Test {
public static void main(String[] args) {
SeqList sl = new SeqList();
for (int i = 0; i < 12; i++) {
sl.seqAdd(i+1);
}
sl.display();
System.out.println("------------");
sl.add(2,99);
sl.add(13,99);
sl.add(0,99);
sl.display();
System.out.println("------------");
System.out.println(sl.contains(78));
System.out.println(sl.contains(2));
System.out.println("------------");
System.out.println(sl.search(78));
System.out.println(sl.search(5));
System.out.println("------------");
System.out.println(sl.getPos(98));
System.out.println(sl.getPos(5));
System.out.println("------------");
sl.setPos(45, 88);
sl.display();
sl.setPos(1, 88);
sl.display();
System.out.println("------------");
sl.remove(99);
sl.display();
sl.remove(99);
sl.display();
sl.remove(99);
sl.display();
sl.remove(122);
sl.display();
System.out.println("------------");
System.out.println(sl.size);
System.out.println("------------");
sl.clear();
sl.display();
}
}
🍇3.3專案檔案
博主的gitee，平常博主寫的程式代碼都在里面，
博主的github，平常博主寫的程式代碼都在里面，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/355315.html
標籤：java