数据结构-顺序表

独断万古他化

发布于 2026-01-15 13:06:44

1270

文章被收录于专栏：Java 攻略Java 攻略

1. 线性表

线性表是n个具有相同特性的数据元素的有限序列。常见的线性表有：顺序表、链表、栈、队列… 线性表在逻辑结构上是线性结构的，也可以说是一条直线。但是在实际物理结构上不一定连续，线性表在物理上存储通常是以数组和链式结构的形式存储。

2. 顺序表的自我实现

我们首先来自己写一个顺序表及它的一些功能。给出一个接口，其中包括要具体实现的功能：

public interface IList {
    // 新增元素,默认在数组最后新增
    void add(int data);
    // 在 pos 位置新增元素
    void add(int pos, int data);
    // 判定是否包含某个元素
    boolean contains(int toFind);
    // 查找某个元素对应的位置
    int indexOf(int toFind);
    // 获取 pos 位置的元素
    int get(int pos);
    // 给 pos 位置的元素设为 value
    void set(int pos, int value);
    //删除第一次出现的关键字key
    void remove(int toRemove);
    // 获取顺序表长度
    int size();
    // 清空顺序表
    void clear();
    // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
    void display();
}

创建一个Arraylist类来实现这个接口，并逐个实现这些顺序表功能。首先我们需要定义一个数组elem，因为顺序表底层也就是数组实现的。然后定义一个usedSize存放数组的长度。

private int[] elem;
private int usedSize;//数组长度
private static final int DEFAULT_SIZE = 10;//定义初始数组容量
//初始化顺序表长度
public Arraylist() {
    this.elem = new int[DEFAULT_SIZE];
}

1.先从简单的开始：遍历打印整个顺序表，就是for循环打印

public void display() {
    for (int i = 0; i < usedSize; i++) {
        System.out.print(this.elem[i] + " ");
    }
    System.out.println();
}

2.获取顺序表长度，直接返回存放数组长度变量usedSize即可

public int size() {
    return this.usedSize;
}

3.判断是否包含某个数据

	public boolean contains(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind){
                return true;
            }
        }
        return false;
    }

4.add添加数据方法，默认在顺序表尾部插入数据因为尾插时的下标正好是usedSize，因此直接在usedSize下标插入即可。

需要注意的是，当usedSize = 数组的初始容量，也就是顺序表满时，是无法插入数据的，因此我们需要先进行判断顺序表是否满，此判断可以写成一个方法，方便后续其他操作的判断调用。
当判断数组满了时，需要进行扩容操作，也可写成一个方法。

	public void add(int data) {
        if(isFull()){
            grow();
        }
        
        this.elem[usedSize] = data;
        usedSize++;
    }

    private boolean isFull(){
        if(this.usedSize == this.elem.length){
            return true;
        }

        return false;
    }
    
    private void grow(){
        this.elem = Arrays.copyOf(this.elem,this.elem.length*2);
    }

5.在指定下标pos插入数据（1）首先判断pos位置是否合法（判断：pos < 0 || pos > usedSize）（2）判断是否满，满了则扩容（3）判断pos是否为usedSize，如果是，那么就是尾插（4）从pos位置开始，后面的数据都向后移动一位。（5）将插入的数据存放到下标pos位置且usedSize加1.

	public void add(int pos, int data) {
        if(isFull()){
            grow();
        }

        String msg = "传入的pos位置不合理";
        checkPosInAdd(pos,msg);

		if(pos == this.usedSize){
            this.elem[pos] = data;
            usedSize++;
            return;
        }

        for (int i = this.usedSize; i > pos; i--) {
            this.elem[i] = this.elem[i-1];
        }
        this.elem[pos] = data;
        this.usedSize++;

    }

    private void checkPosInAdd(int pos,String message){
        if(pos < 0 || pos > this.usedSize){
            throw new PosIllegalityException(message);
        }
    }

判断pos位置是否合理的方法我使用了异常来处理

6.查找某个元素对应的位置遍历查找即可：找不到则返回-1

	public int indexOf(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind){
                return i;
            }
        }
        return -1；
    }

7.取出pos位置的元素（1）判断顺序表是否为空，为空就取不到元素了（2）判断pos位置是否合理

	public int get(int pos) {
        if(isEmpty()){
            throw new EmptyListException("顺序表为空...");
        }

        String message = "传入的pos位置不合理...";
        checkPos(pos,message);
        
        return this.elem[pos];
    }

	//与添加时判断条件不一致，需另写判断pos方法
    private void checkPos(int pos,String message){
        if(pos < 0 || pos >= usedSize){
            throw new PosIllegalityException(message);
        }
    }

	//判断空
    private boolean isEmpty(){
        if(this.usedSize == 0){
            return true;
        }
        return false;
    }

8.将pos位置的数据更改为传入的value数据（1）判断是否为空，为空不能更改（2）判断pos位置是否合理

	public void set(int pos, int value) {
        if(isEmpty()){
            throw new EmptyListException("顺序表为空...");
        }
        
        String message = "pos位置不合理";
        checkPos(pos,message);

        this.elem[pos] = value;
    }

9.删除第一次出现的某个元素（1）判断是否为空（2）找到该元素下标，若找到下标为-1，直接return即可（3）进行删除，将此位置后的元素都向前移动一位，将其覆盖掉

	public void remove(int toRemove) {

        if(isEmpty()){
            throw new EmptyListException("顺序表为空，无法删除...");
        }
        
        int index = indexOf(toRemove);

        if(index == -1){
            System.out.println("没有该数据...");
            return;
        }

        for (int i = index; i < this.usedSize-1; i++) {
            this.elem[i] = this.elem[i+1];
        }
        usedSize--;
    }

10.删除顺序表所有数据遍历将所有元素置为0

	public void clear() {
        for (int i = 0; i < this.usedSize; i++) {
            this.elem[i] = 0;
        }
        
        this.usedSize = 0;
    }

至此所有的顺序表常用操作我们已经自己实现了一遍。总代码如下，可以进行测试类调用了。

import java.util.Arrays;

public class Arraylist implements IList{

    private int[] elem;
    private int usedSize;

    private static final int DEFAULT_SIZE = 10;

    public Arraylist() {
        this.elem = new int[DEFAULT_SIZE];
    }



    /**
     * 新增元素,默认在数组最后新增
     * @param data
     */
    @Override
    public void add(int data) {
        if(isFull()){
            grow();
        }

        this.elem[usedSize] = data;
        usedSize++;
    }

    /**
     * 判断顺序表是否为空
     * @return
     */
    private boolean isFull(){
        if(this.usedSize == this.elem.length){
            return true;
        }

        return false;
    }

    /**
     * 顺序表扩容
     */
    private void grow(){
        this.elem = Arrays.copyOf(this.elem,this.elem.length*2);
    }

    /**
     * 在 pos 位置新增元素
     * @param pos
     * @param data
     */
    @Override
    public void add(int pos, int data) {
        if(isFull()){
            grow();
        }

        String msg = "传入的pos位置不合理";
        checkPosInAdd(pos,msg);

        if(pos == this.usedSize){
            this.elem[pos] = data;
            usedSize++;
            return;
        }

        for (int i = this.usedSize; i > pos; i--) {
            this.elem[i] = this.elem[i-1];
        }
        this.elem[pos] = data;
        this.usedSize++;

    }

    /**
     * 判断要插入数据的pos位置是否合理
     * @param message
     */
    private void checkPosInAdd(int pos,String message){
        if(pos < 0 || pos > this.usedSize){
            throw new PosIllegalityException(message);
        }
    }

    /**
     * 判断顺序表中有没有toFind这个数据
     * @param toFind
     * @return
     */
    @Override
    public boolean contains(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind){
                return true;
            }
        }
        return false;
    }

    /**
     *查找某个元素对应的位置
     * @param toFind
     * @return
     */
    @Override
    public int indexOf(int toFind) {
        for (int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind){
                return i;
            }
        }
        return -1;
    }

    /**
     * 取出pos位置的数据
     * @param pos
     * @return
     */
    @Override
    public int get(int pos) {
        if(isEmpty()){
            throw new EmptyListException("顺序表为空...");
        }

        String message = "传入的pos位置不合理...";
        checkPos(pos,message);

        return this.elem[pos];
    }

    private void checkPos(int pos,String message){
        if(pos < 0 || pos >= usedSize){
            throw new PosIllegalityException(message);
        }
    }

    private boolean isEmpty(){
        if(this.usedSize == 0){
            return true;
        }
        return false;
    }

    /**
     * 将pos位置的数据更改为value
     * @param pos
     * @param value
     */
    @Override
    public void set(int pos, int value) {
        if(isEmpty()){
            throw new EmptyListException("顺序表为空...");
        }

        String message = "pos位置不合理";
        checkPos(pos,message);

        this.elem[pos] = value;
    }

    /**
     * 删除第一次遇到的数据
     * @param toRemove
     */
    @Override
    public void remove(int toRemove) {

        if(isEmpty()){
            throw new EmptyListException("顺序表为空，无法删除...");
        }

        int index = indexOf(toRemove);

        if(index == -1){
            System.out.println("没有该数据...");
            return;
        }

        for (int i = index; i < this.usedSize-1; i++) {
            this.elem[i] = this.elem[i+1];
        }
        usedSize--;
    }

    /**
     * 得到顺序表长度
     * @return
     */
    @Override
    public int size() {
        return this.usedSize;
    }

    /**
     * 删除顺序表所有数据
     */
    @Override
    public void clear() {
        for (int i = 0; i < this.usedSize; i++) {
            this.elem[i] = 0;
        }

        this.usedSize = 0;
    }

    /**
     * 遍历顺序表
     */
    @Override
    public void display() {
        for (int i = 0; i < usedSize; i++) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }
}

3. ArrayList的使用

自我实现顺序表只是为了能更好的理解顺序表。在java中已经为我们写好了顺序表的包装类，我们可以直接拿来使用。 ArrayList 是以泛型方式实现的，使用时必须要先实例化，因为是泛型，所以可以限制数据类型。

在集合框架中，ArrayList是⼀个普通的类，实现了List接口，具体框架图如下：

3.1 ArrayList的构造

ArrayList有三种构造方法

空参构造

ArrayList<Integer> list = new ArrayList<>();

利用其他Collection构造

ArrayList<Integer> list1 = new ArrayList<>();
ArrayList<Integer> list2 = new ArrayList<>(list1);

指定顺序表初始容量构造

ArrayList<Integer> list = new ArrayList<>(10);

此时指定顺序表的初始容量为10.

3.2 ArrayList的常见操作

方法	解释
boolean add(E e)	尾插 e
void add(int index, E element)	将 e 插入到 index 位置
boolean addAll(Collection<? Extends E> c)	尾插 c 中的元素
E remove(index)	删除 index 位置元素
boolean remove(Object o)	删除遇到的第一个 o
E get(int index)	获取下标 index 位置元素
E set(int index, E element)	将下标 index 位置元素设置为 element
void clear()	清空
boolean contains(Object o)	判断 o 是否在线性表中
int indexOf(Object o)	返回第一个 o 所在下标
int lastIndexOf(Object o)	返回最后一个 o 的下标
List<E> subList(int fromIndex, int toIndex)	截取部分 list

我们可以直接调用这些方法来对顺序表进行操作

3.3 ArrayList的遍历

for循环进行遍历

	ArrayList<Integer> list = new ArrayList<>();

    list.add(12);
    list.add(23);
    list.add(34);
    list.add(45);

    for (int i = 0; i < list.size(); i++) {
        System.out.print(list.get(i) + " ");
    }
    System.out.println();

foreach进行遍历

	for(Integer x : list){
        System.out.print(x + " ");
    }
    System.out.println();

使用迭代器进行遍历使用Iterator迭代器遍历

		Iterator<Integer> iterator = list.iterator();

        while (iterator.hasNext()){
            //iterator.hasNext() ： 如果有下一个，打印下一个
            //iterator.next() : 访问下一个，并且向下走一步
            System.out.print(iterator.next() + " ");
        }
        System.out.println();

使用list的迭代器：ListIterator 并且可以从指定下标位置开始打印

		ListIterator<Integer> it = list.listIterator(2);
        while (it.hasNext()){
            System.out.print(it.next() + " ");
       }
        System.out.println();

list的迭代器还可以从末尾向头逆序打印，这是Iterator迭代器做不到的

		ListIterator<Integer> it1 = list.listIterator(list.size());
        while (it1.hasPrevious()){
            System.out.print(it1.previous() + " ");
        }
        System.out.println();

当然，也可以直接sout进行输出list。 ArrayList最常用的遍历方式是：for+下标循环以及foreach

4. ArrayList的具体使用

4.1 杨辉三角

杨辉三角就是每一行的首位和末位都为1，中间的值分别为其上一行对应的值与其前一位值的和。我们进行调整之后可变为这个样子

我们此时给一个非负整数N代表要输出的行数。同时输出杨辉三角的前N行。思路：将每一行都定义为一个List顺序表，那么整个杨辉三角就是List类型的顺序表，可类似于一个二维数组首先我们将第一行单独处理，单独添加第一行；然后从第二行开始，将首位和末位单独处理此时每行中间的元素都为其上一行对应位置与该位置前一位的和。整理完思路，我们逐渐完成代码

	public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();

        //第0行
        List<Integer> tmp = new ArrayList<>();
        tmp.add(1);
        ret.add(tmp);

        //第1行开始
        for(int i = 1; i < numRows; i++){
            List<Integer> tmpRow = new ArrayList<>();

            //0位置
            tmpRow.add(1);

            //中间位置
            List<Integer> preRow = ret.get(i - 1);
            for(int j = 1; j < i; j++){
                int x = preRow.get(j) + preRow.get(j - 1);
                tmpRow.add(x);
            }

            //尾位置
            tmpRow.add(1);

            ret.add(tmpRow);
        }

        return ret;
    }

示例传入4时，通过遍历打印得到了杨辉三角的前4行：

4.2 简单的洗牌算法

首先定义一个牌类，具有属性花色和牌值

public class Card {
    public int rank;
    public String suit;

    public Card(int rank,String suit){
        this.rank = rank;
        this.suit = suit;
    }

    @Override
    public String toString() {
        return String.format("[%s,%d]",suit,rank);
    }
}

将Card类型作为List的泛型参数，那么顺序表中每一个元素就是一张牌。通过四个花色以及1-13的数值大小控制循环添加52张牌，此时就得到了除大小王的一副牌。

public class CardDemo {
    public static final String[] SUITS = {"♠", "♥", "♣", "♦"};

    //得到一副扑克牌
    public static List<Card> buyCards(){
        List<Card> cardList = new ArrayList<>();

        for(int i = 0; i < SUITS.length; i++){
            for (int j = 1; j <= 13; j++) {
                Card card = new Card(j,SUITS[i]);
                cardList.add(card);
            }
        }

        return cardList;
    }

    public static void main(String[] args) {
        List<Card> cardList = buyCards();
        int count = 0;
        for (int i = 0; i < cardList.size(); i++) {
            System.out.print(cardList.get(i));
            count++;
            if(count == 13){
                System.out.println();
                count = 0;
            }
        }

    }
}

通过main方法中的打印：可以看到确实得到了一副牌

那么怎么进行洗牌呢，可以通过Random随机数进行，可以通过循环从1-52的随机下标得到的牌与第 i 张牌进行交换，那么就得到了一副乱序牌。

	public static void shuffle(List<Card> cardList) {
        for (int i = cardList.size()-1; i > 0 ; i--) {
            Random random = new Random();
            int index = random.nextInt(i);
            swap(cardList,i,index);
        }
    }

    private static void swap(List<Card> cardList,int x,int y) {
        Card tmp = cardList.get(y);
        cardList.set(y,cardList.get(x));
        cardList.set(x,tmp);
    }

此时调用shuffle再次进行打印后得到：