《資料結構-第一章》之順序表

前言

在你立足處深挖下去,就會有泉水湧出!别管蒙昧者們叫嚷:“下邊永遠是地獄!”

部落格首頁：KC老衲愛尼姑的部落格首頁

部落客的github，平常所寫代碼皆在于此

刷題求職神器

共勉：talk is cheap, show me the code

作者是爪哇島的新手，水準很有限，如果發現錯誤，一定要及時告知作者哦！感謝感謝！

文章目錄

線性表

線性表定義如下
順序表

常用方法

列印順序表
添加元素
在指定位置插入元素
判定是否包含某個元素
查找某個元素對應的位置(頭到尾)
查找某個元素對應的位置(尾–>頭)
獲得pos位置的值
設定pos位置的值
删除第一次出現的關鍵字
擷取順序表的長度

順序表所有的源代碼

線性表

線性表是一種線性結構。線性結構的特點是資料元素之間是一種線性關系，資料元素“一個接一個的排列”。在一個線性表中資料元素的類型是相同的，或者說線性表是由同一類型的資料元素構成的線性結構。線性表的邏輯上是連續的,實體上不一定連續的，比如數組它在邏輯上和實體上都是連續的,但是連結清單在邏輯上是連續的在實體上是不連續的。常見的線性表有數組,棧,隊列,連結清單。

數組在記憶體的存儲

連結清單在記憶體的存儲

線性表定義如下

線性表是具有相同資料類型的n（n≥0）個類型相同的資料元素組成的有限序列。至于每個資料元素的具體含義，在不同的情況下各不相同，它可以是一個數或一個符号，也可以是一頁書，甚至其他更複雜的資訊。線性表通常記為：（a1，…，ai－1，，ai，ai＋1，，…，an），其中n為表長，n＝0時稱為空表。表中相鄰元素之間存在着順序關系，ai－1領先于ai，ai領先于ai＋1，稱ai－1是ai的直接前驅元素，ai＋1是ai的直接後繼元素。當i＝1，2，…，n－1時，ai有且僅有一個直接後繼；當i＝2，3，…，n時，ai有且僅有一個直接前驅ai－1；當i＝1，2，…，n－1時，有且僅有一個直接後繼ai＋1，而a1是表中第一個元素，它沒有前驅，an是最後一個元素，無後繼。

前驅:線性表中除了第一個元素以外都有前驅

後繼:線性表中除了最後一個元素以外都有後繼

順序表

順序表是用一段實體位址連續的存儲單元依次存儲元素的線性結構。一般情況下采用數組存儲,在數組上完成資料的增删查改。像Java中的ArrayList就是順序表,底層是一個Object數組。接下來就使用數組來實作一個簡單的順序表。

接口實作

public class SeqList {
// 列印順序表
public void display() { }
// 新增元素,預設在數組最後新增
public void add(int data) { }
// 在 pos 位置新增元素
public void add(int pos, int data) { }
// 判定是否包含某個元素
public boolean contains(int toFind) { return true; }
// 查找某個元素對應的位置
public int indexOf(int toFind) { return -1; }
// 擷取 pos 位置的元素
public int get(int pos) { return -1; }
// 給 pos 位置的元素設為 value
public void set(int pos, int value) { }
//删除第一次出現的關鍵字key
public void remove(int toRemove) { }
// 擷取順序表長度
public int size() { return 0; }
// 清空順序表
public void clear() { }
}

屬性

private static final int capacity = 3;//初始化數組的容量
    private int elem[];//存儲元素的數組
    private int userSized;//記錄順序表中元素的個數

構造方法

使用無參構造在建立順序表的時候,為其配置設定預設的容量

public MyArrayList() {
        this.size = 0;
        elementData = new int[CAPACITY];
    }

常用方法

列印順序表

周遊數組即可

/**
     * 列印順序表中的資料
     */
    public void display() {
        for (int i = 0; i < this.userSized; i++) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }

添加元素

預設在數組末尾添加元素

/**
     * 新增元素,預設在數組末尾添加元素
     *
     * @param element
     */
    public void add(int element) {
        if (isFull()) {//對數組進行判斷是否已經滿了,滿了則2倍擴容
            this.elementData = Arrays.copyOf(this.elementData, this.elementData.length * 2);
        }
        this.elementData[this.size++] = element;
    }

在指定位置插入元素

在數組中插入一個元素,并不是使用數組直接通路該位置然後進行修改這個位置的值,這不是插入而是修改。在順序表中定義一個size屬性,記錄數組中元素的個數,假設現在數組中有8個元素,那麼size指向的位置是在數組中元素的後一個位置,我們可以将從指定插入位置到size-1位置的元素都往後挪一個位置出來,然後再将要插入的元素插入即可。

假設數組長度為11,在數組的索引2處插入一個99，插入過程如下圖。

/**
     * 在指定位置插入元素
     *
     * @param index
     * @param element
     */
    public void add(int index, int element) {
        if (isFull()) {//判斷是否已滿
            this.elementData = Arrays.copyOf(this.elementData, this.elementData.length * 2);
        }
        //判斷index合法
        if (index < 0 || index > this.size) {
            return;
        }
        //從要插入元素的位置開始将元素都後移
        for (int i = this.size-1; i >= index; i--) {
            this.elementData[i + 1] = this.elementData[i];
        }
        //插入元素
        this.elementData[index] = element;
        this.size++;
    }

判定是否包含某個元素

直接周遊數組找到目标值

/**
     * 判斷數組中是否包含該元素
     * @param toFind
     * @return
     */
    public boolean contains(int toFind) {
        if (isEmpty()){
            return true;
        }
        for (int i=0;i<this.size;i++) {
            if (this.elementData[i]==toFind) {
                return true;
            }
        }
        return false;
    }

查找某個元素對應的位置(頭到尾)

/**
     * 查找某個元素對應的位置(從頭到尾)
     * @param toFind
     * @return
     */
    public int indexOf(int toFind) {
        for (int i = 0; i < this.size; i++) {
            if (this.elementData[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

查找某個元素對應的位置(尾–>頭)

/**
     * 查找某個元素對應的位置(從尾都頭)
     * @param toFind
     * @return
     */
    public int lastIndexOf(int toFind) {
        for (int i=this.size-1;i>=0;i--) {
            if (this.elementData[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

獲得pos位置的值

首先進進判空,在判斷pos是否合法,最後直接通路。

/**
     *  pos 位置的元素
     * @param pos
     * @return
     */
    public int get(int pos) {
        if (isEmpty()) {
            throw new RuntimeException("MyArrayList為空");
        }
        if (pos < 0 || pos > this.size) {
            throw new RuntimeException("pos位置不合法");
        }
        return this.elementData[pos];
    }

設定pos位置的值

首先進進判空,在判斷pos是否合法,最後直接修改。

/**
     * 給 pos 位置的元素設為 value
     * @param pos
     * @param value
     */
    public void set(int pos, int value) {
        if (pos < 0 || pos > this.size) {
            throw new RuntimeException("pos不合法");
        }
        this.elementData[pos] = value;
    }

删除第一次出現的關鍵字

先找到要删除的位置,然後判斷該位置是否合法,然後該位置後面的元素都往前移動一個位置,就可以完成删除。

/**
     * 删除第一次出現的關鍵字key
     * @param key
     */
    public void remove(int key) {
        int index = searchIndex(key);
        if (index<0||index>this.size) {
            throw new RuntimeException("index不合法");
        }
        for (int i=index; i<this.size-1; i++) {
            this.elementData[i] = this.elementData[i+1];
        }
        this.size--;
    }

擷取順序表的長度

直接傳回size即可

/**
     * 傳回數組的長度
     *
     * @return
     */
    public int size() {
        return this.size;
    }

清空順序表

注意:如果是基本類型,直接将size置空,如果是引用類型要将所有元素置為null,再将size置為0。

/**
     * 清空數組
     */
    public void clear(){
        this.size = 0;
    }

順序表所有的源代碼

package com.kc.demo;

import java.util.Arrays;

public class MyArrayList {
    private static int[] elementData;
    private static final int CAPACITY = 5;//初始化數組的容量
    private int size;

    public MyArrayList() {
        this.size = 0;
        elementData = new int[CAPACITY];
    }

    /**
     * 周遊數組
     */
    public void display() {
        for (int i = 0; i < this.size; i++) {
            System.out.print(this.elementData[i] + " ");
        }
        System.out.println();
    }

    /**
     * 新增元素,預設在數組末尾添加元素
     *
     * @param element
     */
    public void add(int element) {
        if (isFull()) {
            this.elementData = Arrays.copyOf(this.elementData, this.elementData.length * 2);
        }
        this.elementData[this.size++] = element;
    }

    /**
     * 在指定位置插入元素
     *
     * @param index
     * @param element
     */
    public void add(int index, int element) {
        if (isFull()) {
            this.elementData = Arrays.copyOf(this.elementData, this.elementData.length * 2);
        }
        //判斷index合法
        if (index < 0 || index > this.size) {
            return;
        }
        for (int i = this.size-1; i >= index; i--) {
            this.elementData[i + 1] = this.elementData[i];
        }
        this.elementData[index] = element;
        this.size++;
    }

    /**
     * 删除第一次出現的關鍵字key
     * @param key
     */
    public void remove(int key) {
        int index = searchIndex(key);
        if (index<0||index>this.size) {
            throw new RuntimeException("index不合法");
        }
        for (int i=index; i<this.size-1; i++) {
            this.elementData[i] = this.elementData[i+1];
        }
        this.size--;
    }

    /**
     * 查找該元素數組中第一次出現的位置
     * @param key
     * @return
     */
    private int searchIndex(int key){
      for (int i=0;i<this.size;i++) {
          if (this.elementData[i]==key) {
              return i;
          }
      }
      return -1;
    }

    /**
     * 判斷數組中是否包含該元素
     * @param toFind
     * @return
     */
    public boolean contains(int toFind) {
        if (isEmpty()){
            return true;
        }
        for (int i=0;i<this.size;i++) {
            if (this.elementData[i]==toFind) {
                return true;
            }
        }
        return false;
    }

    /**
     * 判斷數組是否已經滿了
     * @return
     */
    private boolean isFull() {
        if (this.size == CAPACITY) {
            return true;
        }
        return false;
    }

    /**
     * 查找某個元素對應的位置(從頭到尾)
     * @param toFind
     * @return
     */
    public int indexOf(int toFind) {
        for (int i = 0; i < this.size; i++) {
            if (this.elementData[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 查找某個元素對應的位置(從尾都頭)
     * @param toFind
     * @return
     */
    public int lastIndexOf(int toFind) {
        for (int i=this.size-1;i>=0;i--) {
            if (this.elementData[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 給 pos 位置的元素設為 value
     * @param pos
     * @param value
     */
    public void set(int pos, int value) {
        if (pos < 0 || pos > this.size) {
            throw new RuntimeException("pos不合法");
        }
        this.elementData[pos] = value;
    }

    /**
     *  pos 位置的元素
     * @param pos
     * @return
     */
    public int get(int pos) {
        if (isEmpty()) {
            throw new RuntimeException("MyArrayList為空");
        }
        if (pos < 0 || pos > this.size) {
            throw new RuntimeException("pos位置不合法");
        }
        return this.elementData[pos];
    }

    /**
     * 判斷數組是否為空
     * @return
     */
    private boolean isEmpty() {
        return this.size == 0;
    }

    /**
     * 傳回數組的長度
     *
     * @return
     */
    public int size() {
        return this.size;
    }

    /**
     * 清空數組
     */
    public void clear(){
        this.size = 0;
    }
}

《資料結構-第一章》之順序表

文章目錄

線性表

線性表定義如下

順序表

常用方法

列印順序表

添加元素

在指定位置插入元素

判定是否包含某個元素

查找某個元素對應的位置(頭到尾)

查找某個元素對應的位置(尾–>頭)

獲得pos位置的值

設定pos位置的值

删除第一次出現的關鍵字

擷取順序表的長度

順序表所有的源代碼

繼續閱讀

nginx location中斜線的位置的重要性

資料結構與算法（27）——排序（二）

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

Linux裝置模型（中）之上層容器

scala (3) Function 和 Method