侧边栏壁纸
博主头像
千异博主等级

学无止境,学以致用,志存高远!

  • 累计撰写 29 篇文章
  • 累计创建 26 个标签
  • 累计收到 0 条评论

数据结构和算法——稀疏数组、队列、链表

千异
2022-04-20 / 0 评论 / 0 点赞 / 524 阅读 / 5,833 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-04-20,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

数据结构

数据结构分为线性结构和非线性结构。

线性结构

  1. 顺序存储
    顺序存储的线性表称为顺序表,顺序表中的存储元素是连续的。

  2. 链式存储
    链式存储的线性表称为链表,存储元素不一定是连续的,元素节点中存放是数据元素以及相邻元素的地址信息。

常见的线性结构有:数组,队列,链表和栈。

稀疏数组

当一个数组大部分元素是0时,可以使用稀疏数组压缩数据。
一个二维数组:
image.png
压缩为系数数组后:
image.png

import java.util.Arrays;

public class ArrayUtil {
    public static void main(String[] args) {
        /**
         * 原始二维数组定义
         * 11行11列的棋盘,1表示白子,2表示黑子,0表示无子
         */
        int[][] chessArr1 = new int[11][11];
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;
        chessArr1[4][5] = 2;
        printArray(chessArr1);
        int sum = 0;
        for (int[] ints : chessArr1) {
            for (int anInt : ints) {
                sum = anInt == 0 ? sum : sum + 1;
            }
        }
        /**
         * 压缩为稀疏数组
         */
        int[][] sparseArr = new int[sum + 1][3];
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;
        int x = 1;
        for (int i = 0; i < chessArr1.length; i++) {
            for (int j = 0; j < chessArr1[i].length; j++) {
                if (chessArr1[i][j] != 0) {
                    sparseArr[x][0] = i;
                    sparseArr[x][1] = j;
                    sparseArr[x][2] = chessArr1[i][j];
                    x++;
                }
            }
        }
        printArray(sparseArr);
        /**
         * 稀疏数组恢复为原始数组
         */
        int[][] chessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
        for (int i = 1; i < sparseArr.length; i++) {
            chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        printArray(chessArr2);
    }

    public static void printArray(int[][] array) {
        for (int[] row : array) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
    }
}

### 队列
先入先出
```JAVA
import java.util.Scanner;

public class ArrayQueue {
    private int maxSixe;
    private int front;//队列头
    private int rear;//队列尾
    private int[] arr;//存储数据,模拟队列

    public ArrayQueue(int arrMaxSize) {
        maxSixe = arrMaxSize;
        arr = new int[arrMaxSize];
        front = -1;
        rear = -1;
    }

    /**
     * 判断队列已满
     *
     * @return
     */
    public boolean isFull() {
        return rear == maxSixe - 1;
    }

    /**
     * 判断队列是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return rear == front;
    }

    public void addQueue(int n) {
        if (isFull()) {
            System.out.println("队列已满,不能加入数据");
            return;
        }
        rear++;
        arr[rear] = n;
    }

    public int getQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        front++;
        return arr[front];
    }

    /**
     * 显示队列数据
     */
    public void list() {
        if (isEmpty()) {
            System.out.println("队列为空");
            return;
        }
        for (int i = front + 1; i <= rear; i++) {
            System.out.printf("arr[%d]=%d\n", i, arr[i]);
        }
    }

    /**
     * 闲时是队列的头数据
     *
     * @return
     */
    public int headQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        return arr[front + 1];

    }

    public static void main(String[] args) {
        ArrayQueue arrayQueue = new ArrayQueue(5);
        Scanner scanner = new Scanner(System.in);
        flag:
        while (true) {
            System.out.println("l: 显示队列");
            System.out.println("e:退出程序");
            System.out.println("a:添加数据");
            System.out.println("g:取出数据");
            System.out.println("h:查看队列头的数据");
            char key = scanner.next().charAt(0);
            switch (key) {
                case 'l':
                    arrayQueue.list();
                    break;
                case 'e':
                    scanner.close();
                    break flag;
                case 'a':
                    System.out.println("请输入一个数字");
                    int value = scanner.nextInt();
                    arrayQueue.addQueue(value);
                    break;
                case 'g':
                    try {
                        System.out.println("取出的数据是:" + arrayQueue.getQueue());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        System.out.println("队列头的数据是:" + arrayQueue.headQueue());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出");
    }
}

环形队列

import java.util.Scanner;

public class CircleArrayQueue {
    private int maxSixe;
    private int front;//队列的第一个元素,初始值为0
    private int rear;//队列最后一个元素的后一个位置
    private int[] arr;//存储数据,模拟队列

    public CircleArrayQueue(int arrMaxSize) {
        maxSixe = arrMaxSize;
        arr = new int[arrMaxSize];
    }

    /**
     * 判断队列已满
     * (rear + 1) % maxSixe == front
     *
     * @return
     */
    public boolean isFull() {
        return (rear + 1) % maxSixe == front;
    }

    /**
     * 判断队列是否为空
     * rear == front
     *
     * @return
     */
    public boolean isEmpty() {
        return rear == front;
    }

    public void addQueue(int n) {
        if (isFull()) {
            System.out.println("队列已满,不能加入数据");
            return;
        }
        arr[rear] = n;
        rear = (rear + 1) % maxSixe;
    }

    public int getQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        int value = arr[front];
        front = (front + 1) % maxSixe;
        return value;
    }

    /**
     * 显示队列数据
     */
    public void list() {
        if (isEmpty()) {
            System.out.println("队列为空");
            return;
        }
        for (int i = front; i <= front + size(); i++) {
            System.out.printf("arr[%d]=%d\n", i % maxSixe, arr[i % maxSixe]);
        }
    }

    /**
     * 元素个数
     *
     * @return
     */
    public int size() {
        return (rear + maxSixe - front) % maxSixe;
    }

    /**
     * 闲时是队列的头数据
     *
     * @return
     */
    public int headQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        return arr[front];

    }

    public static void main(String[] args) {
        CircleArrayQueue queue = new CircleArrayQueue(4); //说明设置4, 其队列的有效数据最大是3
        Scanner scanner = new Scanner(System.in);
        flag:
        while (true) {
            System.out.println("l: 显示队列");
            System.out.println("e:退出程序");
            System.out.println("a:添加数据");
            System.out.println("g:取出数据");
            System.out.println("h:查看队列头的数据");
            char key = scanner.next().charAt(0);
            switch (key) {
                case 'l':
                    queue.list();
                    break;
                case 'e':
                    scanner.close();
                    break flag;
                case 'a':
                    System.out.println("请输入一个数字");
                    int value = scanner.nextInt();
                    queue.addQueue(value);
                    break;
                case 'g':
                    try {
                        System.out.println("取出的数据是:" + queue.getQueue());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        System.out.println("队列头的数据是:" + queue.headQueue());
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出");
    }
}

链表示范代码:

public class LinkedList {
    /**
     * 先初始化一个头结点,头结点不要动,不存放数据
     */
    private HeroNode head = new HeroNode(0, null, null);

    public void add(HeroNode node) {
        HeroNode tmp = head;
        while (tmp.next != null) {
            tmp = tmp.next;
        }
        tmp.next = node;
    }

    public void list() {
        if (head.next == null) {
            System.out.println("链表为空");
        }
        HeroNode tmp = head;
        while (tmp.next != null) {
            System.out.println(tmp);
            tmp = tmp.next;
        }
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.add(new HeroNode(1, "宋江", "及时雨"));
        list.add(new HeroNode(2, "卢俊义", "玉麒麟"));
        list.add(new HeroNode(3, "吴用", "智多星"));
        list.list();
    }
}

class HeroNode {
    public int no;
    public String name;
    public String nickName;
    public HeroNode next;

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                ", next=" + next +
                '}';
    }
}

非线性结构

非线性结构包括:二维数组,多维数组,广义表,树结构,图结构

0
博主关闭了所有页面的评论