柚子快報(bào)激活碼778899分享：學(xué)習(xí) 數(shù)據(jù)結(jié)構(gòu)---順序表

http://yzkb.51969.com/

文章目錄

線性表順序表的使用及其內(nèi)部方法ArrayList 的擴(kuò)容機(jī)制順序表的幾種遍歷方式順序表的優(yōu)缺點(diǎn)順序表的模擬實(shí)現(xiàn)楊輝三角撲克牌算法

線性表

??線性表（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ǔ)

順序表的使用及其內(nèi)部方法

??順序表是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲(chǔ)。在數(shù)組上完成數(shù)據(jù)的增刪查改。ArrayList底層是一段連續(xù)的空間，并且可以動(dòng)態(tài)擴(kuò)容，是一個(gè)動(dòng)態(tài)類型的順序表

ArrayList的使用 ArrayList 的構(gòu)造方法如下： 示例代碼如下：

public static void main(String[] args) {

// ArrayList創(chuàng)建，推薦寫法

List list1 = new ArrayList<>();

// 構(gòu)造一個(gè)具有10個(gè)容量的列表

List list2 = new ArrayList<>(10);

list2.add(1);

list2.add(2);

list2.add(3);

// list2.add("hello"); // 編譯失敗，List已經(jīng)限定了，list2中只能存儲(chǔ)整形元素

// list3構(gòu)造好之后，與list中的元素一致

ArrayList list3 = new ArrayList<>(list2);

// 避免省略類型，否則：任意類型的元素都可以存放，使用時(shí)將是一場(chǎng)災(zāi)難

List list4 = new ArrayList();

list4.add("111");

list4.add(100);

}

ArrayList 中的方法

ArrayList 的擴(kuò)容機(jī)制

ArrayList是一個(gè)動(dòng)態(tài)類型的順序表，即：在插入元素的過程中會(huì)自動(dòng)擴(kuò)容。

【總結(jié)】

默認(rèn)容量為10檢測(cè)是否真正需要擴(kuò)容，如果是調(diào)用grow準(zhǔn)備擴(kuò)容預(yù)估需要擴(kuò)容的大小

初步預(yù)估按照1.5倍大小擴(kuò)容如果用戶所需大小超過預(yù)估1.5倍大小，則按照用戶所需大小擴(kuò)容真正擴(kuò)容之前檢測(cè)是否能擴(kuò)容成功，防止太大導(dǎo)致擴(kuò)容失敗

使用copyOf進(jìn)行擴(kuò)容

順序表的幾種遍歷方式

public static void main(String[] args) {

ArrayList list = new ArrayList<>();

list.add(1);

list.add(2);

list.add(3);

System.out.println(list);

System.out.println("=========for循環(huán)遍歷=========");

for (int i = 0; i < list.size(); i++) {

System.out.print(list.get(i) +" ");

}

System.out.println();

System.out.println("=========foreach循環(huán)遍歷=========");

for(Integer x : list) {

System.out.print(x +" ");

}

System.out.println();

System.out.println("=========迭代器遍歷1=========");

Iterator it = list.iterator();

while(it.hasNext()) {

System.out.print(it.next() +" ");

}

System.out.println();

System.out.println("=========迭代器遍歷2=========");

ListIterator tmpList = list.listIterator();

while(tmpList.hasNext()) {

System.out.print(tmpList.next() +" ");

}

System.out.println();

System.out.println("=========迭代器遍歷3=========");

ListIterator tmpList2 = list.listIterator(list.size());

while(tmpList2.hasPrevious()) {

System.out.print(tmpList2.previous() +" ");

}

System.out.println();

}

順序表的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

內(nèi)存連續(xù)—>物理上和邏輯上根據(jù)下標(biāo)查找元素，時(shí)間復(fù)雜度為O(1)

缺點(diǎn)：

插入數(shù)據(jù)和刪除數(shù)據(jù)不合適，因?yàn)槊看味家苿?dòng)元素時(shí)間復(fù)雜度會(huì)達(dá)到O(N)

順序表的模擬實(shí)現(xiàn)

??順序表的底層使用數(shù)組實(shí)現(xiàn)的，所以這里模擬實(shí)現(xiàn)順序表也使用數(shù)組來實(shí)現(xiàn)。 在實(shí)現(xiàn)之前，先看看ArrayList中的常用方法，后續(xù)要模擬實(shí)現(xiàn)這些方法，如下：

public class IList {

// 新增元素,默認(rèn)在數(shù)組最后新增

public void add(int data) { }

// 在 pos 位置新增元素

public void add(int pos, int data) { }

// 判定是否包含某個(gè)元素

public boolean contains(int toFind) { return true; }

// 查找某個(gè)元素對(duì)應(yīng)的位置

public int indexOf(int toFind) { return -1; }

// 獲取 pos 位置的元素

public int get(int pos) { return -1; }

// 給 pos 位置的元素設(shè)為 value

public void set(int pos, int value) { }

//刪除第一次出現(xiàn)的關(guān)鍵字key

public void remove(int toRemove) { }

// 獲取順序表長度

public int size() { return 0; }

// 清空順序表

public void clear() { }

// 打印順序表，注意：該方法并不是順序表中的方法，為了方便看測(cè)試結(jié)果給出的

public void display() { }

}

【思路】：把這些ArrayList中的方法放入一個(gè)接口中（當(dāng)然這些方法放入接口中暫時(shí)沒有具體實(shí)現(xiàn)，為抽象方法），讓模擬實(shí)現(xiàn)的MyArrayList 類實(shí)現(xiàn)這個(gè)接口，然后在MyArrayList 類中把這些方法全部重寫并實(shí)現(xiàn)。

創(chuàng)建一個(gè) IList 接口，接口中包含各種關(guān)于ArrayList的抽象方法,代碼示例如下：

public interface IList {

// 新增元素,默認(rèn)在數(shù)組最后新增

void add(int data);

// 在 pos 位置新增元素

void add(int pos, int data);

// 判定是否包含某個(gè)元素

boolean contains(int toFind);

// 查找某個(gè)元素對(duì)應(yīng)的位置

int indexOf(int toFind) ;//

// 獲取 pos 位置的元素

int get(int pos);

// 給 pos 位置的元素設(shè)為 value

void set(int pos, int value);

//刪除第一次出現(xiàn)的關(guān)鍵字key

void remove(int toRemove);

// 獲取順序表長度

int size();

// 清空順序表

void clear();

// 打印順序表，注意：該方法并不是順序表中的方法，為了方便看測(cè)試結(jié)果給出的

void display();

//判斷數(shù)組是否為空

boolean isEmpty();

//刪除所有數(shù)據(jù)為toRemove的元素

void removeAll(int toRemove);

}

創(chuàng)建MyArrayList 類 使其實(shí)現(xiàn) IList 接口，在類中重寫接口中的方法

import java.util.Arrays;

public class MyArrayList implements IList{

public int[] elem;

public int usedSize;

public MyArrayList() {

this.elem = new int[10];

}

//判斷數(shù)組是否滿了

public boolean isFull() {

return elem.length == usedSize;

}

//數(shù)組滿了，進(jìn)行擴(kuò)容

private void grow() {

elem = Arrays.copyOf(elem,2*elem.length);

}

/**

* 對(duì)數(shù)組的 最后一個(gè)位置 新增data

* @param data

*/

@Override

public void add(int data) {

if(isFull()) {

grow();

}

elem[usedSize] = data;

usedSize++;

}

/**

* 在pos位置 新增 元素data

* @param pos

* @param data

*/

@Override

public void add(int pos, int data) {

if(isFull()) {

grow();

}

if(pos < 0 || pos > usedSize) {

throw new PosOutOfException("pos位置不合法");

}

for (int i = usedSize-1; i >= pos; i--) {

elem[i+1] = elem[i];

}

elem[pos] = data;

usedSize++;

}

/**

* 查找一個(gè)數(shù)據(jù)，返回true或false

* @param toFind

* @return

*/

@Override

public boolean contains(int toFind) {

if(isEmpty()) {

return false;

}

for (int i = 0; i < usedSize; i++) {

if(elem[i] == toFind) {

return true;

}

}

return false;

}

/**

* 查找一個(gè)數(shù)據(jù)，返回其下標(biāo)

* @param toFind

* @return

*/

@Override

public int indexOf(int toFind) {

for (int i = 0; i < usedSize; i++) {

if(elem[i] == toFind) {

return i;

}

}

return -1;

}

/**

* 查找下標(biāo)為pos的元素，返回其數(shù)值

* @param pos

* @return

*/

@Override

public int get(int pos) {

if(isEmpty()) {

throw new EmptyArrayListException("順序表為空");

}

if(pos < 0 || pos >= usedSize) {

throw new RuntimeException("pos位置不合法");

}

return elem[pos];

}

/**

* pos位置 設(shè)置成 value

* @param pos

* @param value

*/

@Override

public void set(int pos, int value) {

if(pos < 0 || pos >= usedSize) {

throw new PosOutOfException("pos位置不合法");

}

elem[pos] = value;

}

/**

* 刪除數(shù)組中的一個(gè)元素 toMove

* @param toRemove

*/

@Override

public void remove(int toRemove) {

int index = indexOf(toRemove);

if(index == -1) {

return;

}

for (int i = index; i < usedSize-1; i++) {

elem[i] = elem[i+1];

}

usedSize--;

}

@Override

public int size() {

return usedSize;

}

@Override

public void clear() {

usedSize = 0;

}

@Override

public void display() {

for (int i = 0; i < usedSize; i++) {

System.out.print(elem[i] +" ");

}

System.out.println();

}

@Override

public boolean isEmpty() {

if(usedSize == 0) {

return true;

}

return false;

}

@Override

public void removeAll(int toRemove) {

while(contains(toRemove)) {

int index = indexOf(toRemove);

for (int i = index; i < usedSize-1; i++) {

elem[i] = elem[i+1];

}

usedSize--;

}

}

}

測(cè)試類Test

public static void main1(String[] args) {

MyArrayList myArrayList = new MyArrayList();

myArrayList.add(1);

myArrayList.add(2);

myArrayList.add(3);

myArrayList.add(1,19);

myArrayList.display();

myArrayList.set(0,100);

myArrayList.display();

boolean ret = myArrayList.contains(100);

System.out.println(ret);

myArrayList.set(1,33);

myArrayList.display();

myArrayList.add(0,1);

myArrayList.add(1,2);

myArrayList.add(2,1);

myArrayList.add(3,4);

myArrayList.add(4,1);

myArrayList.display();

myArrayList.removeAll(1);

myArrayList.display();

}

楊輝三角

OJ鏈接—> 楊輝三角

題目描述：給定一個(gè)非負(fù)整數(shù) numRows，生成「楊輝三角」的前 numRows 行。 示例： 輸入: numRows = 5 輸出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] 要求：返回值用 List > 接收

??思路：要求每行數(shù)值都放入一個(gè)List< Integer > 中，所以遍歷每行，每遍歷一行，就創(chuàng)建一個(gè) List< Integer > ，然后把每行的數(shù)值add進(jìn)順序表，完成每行 List< Integer > 的元素填充，最后再把本行的 List< Integer > 作為元素放入 List > 中。 ??那么問題是 如何得到每行的數(shù)字，將其放入順序表中？—>觀察楊輝三角，每行的第一個(gè)元素和最后一個(gè)元素都為 1 ，中間的元素：如果中間某一個(gè)元素是 i 行 j 列，那么 這個(gè)元素值就等于上一行 本列和前一列 的兩值之和： [i] [j] = [i-1] [j] + [i-1] [j-1]，但是這不是數(shù)組不能使用下標(biāo)直接賦值，所以可以使用順序表的 get(int Index) 和 set(int Index) 方法，分別拿到上一行，取出上一行的 j下標(biāo) 和 j-1 下標(biāo)的元素，兩值相加賦值給 本行的順序表list。

完整代碼如下：

class Solution {

public List> generate(int numRows) {

List> lists = new ArrayList<>();

//第一行

List list1 = new ArrayList<>();

list1.add(1);

lists.add(list1);

for(int i = 1; i < numRows; i++) {

List list = new ArrayList<>();

//第一個(gè)元素

list.add(1);

//中間元素

List prevRow = lists.get(i-1);//拿到上一行

for(int j = 1; j < i; j++) {

list.add(prevRow.get(j) + prevRow.get(j-1));

}

//最后一個(gè)元素

list.add(1);

lists.add(list);

}

return lists;

}

}

撲克牌算法

實(shí)現(xiàn)效果：能夠完成創(chuàng)建撲克牌、洗牌、發(fā)牌操作 思路： 完成洗牌和發(fā)牌操作，需要先拿到一副撲克牌，所以先創(chuàng)建一副撲克牌(共52張牌，沒有大小王) 一副撲克牌由 13張紅桃?、13張黑桃?、13張方片?、13張梅花? 組成。 創(chuàng)建 Card類，內(nèi)部定義變量 suit 花色、rank 數(shù)字，重寫toString方法，便于觀察每張牌的信息 創(chuàng)建 Game類，內(nèi)部實(shí)現(xiàn) 創(chuàng)建一副牌、洗牌、發(fā)牌操作. Card類的代碼示例如下：

public class Card {

public String suit;//花色--紅桃、黑桃、方塊、梅花

public int rank;//數(shù)字

public Card(String suit, int rank) {

this.suit = suit;

this.rank = rank;

}

@Override

public String toString() {

// return "Card{" +

// "suit='" + suit + '\'' +

// ", rank=" + rank +

// '}';

return "{ "+suit+rank+" }";

}

}

1.創(chuàng)建一副牌，使用順序表作為容器，將每一張牌放入這個(gè)容器中 如何把每一張牌放入順序表中？–> 四種不同花色分別有13張牌，所以使用兩個(gè) for 循環(huán)，將卡牌放入順序表 內(nèi)部循環(huán)13次，把放入同一花色的13張牌放入順序表，外部循環(huán)4次，每次都是不同的花色。代碼示例如下：

import java.util.ArrayList;

import java.util.List;

import java.util.Random;

public class Game {

public String[] suits = {"?","?","?","?"};

public List cardsList = new ArrayList<>();//作為撲克牌的容器

//創(chuàng)建一副撲克牌

public List createCards() {

for (int i = 0; i < suits.length; i++) {

for (int j = 1; j <= 13 ; j++) {

Card card = new Card(suits[i],j);

cardsList.add(card);

}

}

return cardsList;

}

2.洗牌操作，現(xiàn)實(shí)中洗牌是將任意不同的卡牌交換位置，轉(zhuǎn)換為代碼層面，可以把任意不同下標(biāo)的卡牌進(jìn)行交換，for(i)循環(huán)遍歷順序表，每次生成一個(gè)i下標(biāo)后面的隨機(jī)數(shù)（i+1，51），但是這樣生成隨機(jī)數(shù)的實(shí)現(xiàn)比較麻煩，因此可以從最后面即下標(biāo)為 51 的位置向前遍歷順序表，每次生成 [0,i) 的隨機(jī)數(shù)，然后交換下標(biāo)為i 和 下標(biāo)為randIndex的元素。 代碼示例如下：

//洗牌操作

public void shuffle(List cardsList) {

Random random = new Random();

for (int i = 51; i > 0; i--) {

int randIndex = random.nextInt(i);//生成 [0,i-1] 區(qū)間的隨機(jī)數(shù)

//i下標(biāo)位置 與 randIndex下標(biāo)位置元素進(jìn)行交換

swap(i,randIndex);

}

}

//i下標(biāo)位置 與 randIndex下標(biāo)位置元素進(jìn)行交換

private void swap(int i,int randIndex) {

Card tmp = cardsList.get(i);

cardsList.set(i,cardsList.get(randIndex));

cardsList.set(randIndex,tmp);

}

3.發(fā)牌操作 要求：三人依次取牌，每人每次取牌一張，進(jìn)行五次輪回取牌，最終每人手中有五張牌 三個(gè)人取出的牌，也需要一個(gè)容器容納撲克牌，可以為每個(gè)人創(chuàng)建一個(gè)順序表容納取出的撲克牌 三人依次取牌，每次一張，進(jìn)行五次輪回，就可以使用兩個(gè)for循環(huán)，完成取牌和牌進(jìn)入入順序表的操作 每次取牌都要把取出的這張牌從順序表中刪除，避免其他人重復(fù)取這張牌（現(xiàn)實(shí)中也是如此，取出一張牌，那么這張牌就不會(huì)存在于 待取的那攤撲克牌中，誰取的這張牌，這張牌就在誰手上），轉(zhuǎn)換為代碼層面，就是調(diào)用 cardsList.remove(0)方法。將cardsList.remove(0)方法的返回值 傳給 每個(gè)人的手中

【注意】這里cardsList.remove(0)方法中的參數(shù)一直都是0，因?yàn)槊看稳∨贫际亲钌厦娴呐?，而順序表刪除已取出的牌之后，第二張牌又會(huì)稱為新的下標(biāo)為 0 的新的元素。 代碼示例如下：

//發(fā)牌，三個(gè)人輪流取牌，一次取一張，最終每個(gè)人五張牌

public List> play(List cardsList) {

List> cardLists = new ArrayList<>();

List hand0 = new ArrayList<>();

List hand1 = new ArrayList<>();

List hand2 = new ArrayList<>();

cardLists.add(hand0);

cardLists.add(hand1);

cardLists.add(hand2);

for (int i = 0; i < 5; i++) {

for (int j = 0; j < 3; j++) {

Card card = cardsList.remove(0);

cardLists.get(j).add(card);

}

}

return cardLists;

}

Test測(cè)試類，代碼示例如下：

import java.util.List;

public class Test {

public static void main(String[] args) {

Game game = new Game();

List cardsList = game.createCards();

System.out.println("初始牌："+cardsList);

game.shuffle(cardsList);

System.out.println("洗過后的牌："+cardsList);

System.out.println("發(fā)牌后，每人手中的牌："+game.play(cardsList));

}

}

運(yùn)行結(jié)果：

“C:\Program Files\Java\jdk-17\bin\java.exe” “-javaagent:D:\softstall\idea\IntelliJ IDEA Community Edition 2021.3.3\lib\idea_rt.jar=63623:D:\softstall\idea\IntelliJ IDEA Community Edition 2021.3.3\bin” -Dfile.encoding=UTF-8 -classpath D:\javacode\J20241025_CardGame\out\production\J20241025_CardGame Test 初始牌：[{ ?1 }, { ?2 }, { ?3 }, { ?4 }, { ?5 }, { ?6 }, { ?7 }, { ?8 }, { ?9 }, { ?10 }, { ?11 }, { ?12 }, { ?13 }, { ?1 }, { ?2 }, { ?3 }, { ?4 }, { ?5 }, { ?6 }, { ?7 }, { ?8 }, { ?9 }, { ?10 }, { ?11 }, { ?12 }, { ?13 }, { ?1 }, { ?2 }, { ?3 }, { ?4 }, { ?5 }, { ?6 }, { ?7 }, { ?8 }, { ?9 }, { ?10 }, { ?11 }, { ?12 }, { ?13 }, { ?1 }, { ?2 }, { ?3 }, { ?4 }, { ?5 }, { ?6 }, { ?7 }, { ?8 }, { ?9 }, { ?10 }, { ?11 }, { ?12 }, { ?13 }] 洗過后的牌：[{ ?13 }, { ?13 }, { ?5 }, { ?10 }, { ?13 }, { ?12 }, { ?4 }, { ?6 }, { ?5 }, { ?3 }, { ?1 }, { ?12 }, { ?11 }, { ?2 }, { ?7 }, { ?5 }, { ?9 }, { ?11 }, { ?2 }, { ?2 }, { ?7 }, { ?5 }, { ?12 }, { ?7 }, { ?11 }, { ?11 }, { ?1 }, { ?8 }, { ?10 }, { ?8 }, { ?8 }, { ?3 }, { ?4 }, { ?10 }, { ?4 }, { ?2 }, { ?1 }, { ?9 }, { ?3 }, { ?6 }, { ?6 }, { ?7 }, { ?12 }, { ?8 }, { ?4 }, { ?10 }, { ?13 }, { ?9 }, { ?1 }, { ?9 }, { ?6 }, { ?3 }] 發(fā)牌后，每人手中的牌：[[{ ?13 }, { ?10 }, { ?4 }, { ?3 }, { ?11 }], [{ ?13 }, { ?13 }, { ?6 }, { ?1 }, { ?2 }], [{ ?5 }, { ?12 }, { ?5 }, { ?12 }, { ?7 }]]

柚子快報(bào)激活碼778899分享：學(xué)習(xí) 數(shù)據(jù)結(jié)構(gòu)---順序表

http://yzkb.51969.com/

好文鏈接