重启数据结构与算法1

[Ray-56]

重启数据结构与算法1

重启数据结构与算法，一些代码案例使用 Deno 与 TypeScript 实现

1. 重启数据结构与算法1

线性数据结构

元素之间一对一的线性关系

• 顺序表
• 链表 不一定连续，存数据元素以及相邻元素的地址信息

常见有：数组、队列、栈、链表

非线性数据结构

常见有：二维数组、多维数组、广义表，树结构、图结构

---

稀疏数组

当一个数组中大部分为0，或者为同一个值，可以使用稀疏数组来保存

处理方法：

• 记录几行几列，有多少个不同的值
• 不同值元素的行列及值记录在小规模数组中，缩小程序规模

实践案例

简易五子棋：

// 稀疏数组 五子棋
// 因为有读取和写入 所以运行时需要加入 --allow-write --allow-read
const dataFileName = 'sparsearray.data';
type SparseArrayType = number[][];
class SparseArray {
    /**
     * 原始二维数组 11 * 11
     * 0: 没有棋子
     * 1: 黑子
     * 2: 蓝子
     */
    private chessArr1: SparseArrayType;
    constructor() {
        this.chessArr1 = [];
        for (let i = 0; i < 11; i++) {
            this.chessArr1[i] = new Array(11).fill(0);
        }
        this.chessArr1[1][2] = 1;
        this.chessArr1[2][4] = 2;
        // 输出 二维数组
        console.table(this.chessArr1);
    }
    /** 读取本地文件 */
    public ready() {
        const decoder = new TextDecoder("utf-8");
        const data = Deno.readFileSync(dataFileName);
        console.log('读取到的内容: ');
        console.table(JSON.parse(decoder.decode(data)));
    }
    /** 保存本地文件 */
    public save(arr: SparseArrayType) {
        const encoder = new TextEncoder();
        const data = encoder.encode(JSON.stringify(arr));
        Deno.writeFileSync(dataFileName, data);
    }
    /** 二维转稀疏 */
    toSparseArray(): SparseArrayType {
        // 1 找到非 0 的个数
        let sum = 0;
        for (let i = 0; i < 11; i++) {
            for (let j = 0; j < 11; j++) {
                if (this.chessArr1[i][j] !== 0) {
                    sum++;
                }
            }
        }
        console.log(`sum -> ${sum}`);
        // 2.1 创建对应数组
        let intSparseArray: number[][] = [[11, 11, sum]];
        // 2.2 遍历将非 0 存入
        let count = 0; // 稀疏数组下标
        for (let i = 0; i < 11; i++) {
            for (let j = 0; j < 11; j++) {
                if (this.chessArr1[i][j] !== 0) {
                    intSparseArray[++count] = [i, j, this.chessArr1[i][j]];
                }
            }
        }
        console.table('得到的稀疏数组为：');
        console.table(intSparseArray);
        return intSparseArray;
    }
    /** 稀疏数组恢复为二维数组 */
    recover(sp: SparseArrayType): SparseArrayType {
        let chessArr2: SparseArrayType = [];
        // 1. 创建二维数组
        let [rowCount, columnCount, valueCount] = sp[0]; // 第0行的 第一个为行数量， 第二个为列数量，第三个为非空值的数量
        for (let i = 0; i < columnCount; i++) {
            chessArr2[i] = new Array(rowCount).fill(0);
        }
        // 2. 读取稀疏数组后几行数据赋值给新创建的二维数组
        for (let i = 1; i < sp.length; i++) {
            const [rowIndex, columnIndex, value] = sp[i];
            chessArr2[rowIndex][columnIndex] = value
        }
        console.table('恢复后的稀疏数组为：');
        console.table(chessArr2);
        return chessArr2;
    }
}
export default SparseArray;

队列

队列是一个有序列表，可以用数组或者链表来表示，遵循先进先出的原则。常见场景：银行排队办业务，先排队的先办业务。

数组模拟

// 数组模拟队列
class QueueArray {
    public queue: number[];
    private front: number;
    private rear: number;
    private maxSize: number;
    constructor(maxSize: number) {
        this.queue = [];
        this.front = -1;
        this.rear = -1;
        this.maxSize = maxSize;
    }
    public isFull() {
        return this.rear === this.maxSize - 1;
    }
    public isEmpty() {
        return this.front === this.rear;
    }
    public add(value: number) {
        if (this.isFull()) {
            console.log('队列已满');
            return;
        }
        this.queue[++this.rear] = value;
    }
    public pop(): number | undefined {
        if (this.isEmpty()) {
            console.log('队列为空');
            return;
        }
        return this.queue[++this.front];
    }
    public show() {
        if (this.isEmpty()) {
            console.log('队列为空');
            return;
        }
        console.log(this.queue.slice(this.front + 1, this.rear + 1).join(','));
    }
}

export default QueueArray;

问题以及优化：

• 目前数组使用一次就不能用，没有达到复用
• 将这个数组使用算法，改进成一个 环形队列 取模：%

import { readLines } from "https://deno.land/std/io/mod.ts";

// 环形队列
class CircleArrayQueue {
    private maxSize: number;
    private queue: number[];
    private front: number;
    private rear: number;
    constructor(maxSize: number) {
        this.maxSize = maxSize;
        this.queue = [];
        this.front = 0;
        this.rear = 0;
    }
    private isFull() {
        return (this.rear + 1) % this.maxSize === this.front;
    }
    private isEmpty() {
        return this.front === this.rear;
    }
    public add(value: number) {
        if (this.isFull()) {
            console.log('队列已满');
            return;
        }
        this.queue[this.rear++] = value;
    }
    public pop() {
        if (this.isEmpty()) {
            console.log('队列为空');
            return;
        }
        const ret = this.queue[this.front];
        this.front++;
        return ret;
    }
    public show() {
        if (this.isEmpty()) {
            console.log('队列为空');
            return;
        }
        const printList = [];
        let count = 0;
        for (let i = this.front; i < this.front + this.size() - 1; i++) {
            printList[count++] = this.queue[i];
        }
        console.table(printList);
    }
    /** 有效数据个数 */
    private size() {
        return this.rear - this.front + 1;
    }
}

const commandDict = {
    a: 'add -入队',
    p: 'pop -出队',
    s: 'show -显示队列',
    '-h': 'help -显示帮助',
}
window.onload = async function main() {
    console.table(commandDict);
    const q = new CircleArrayQueue(4); // 提前规定，4 是给 rear 空出一个位置
    for await (const line of readLines(Deno.stdin)) {
        switch (line) {
            case '-h':
                console.table(commandDict);
                break
            case 'a':
				console.log('请输入一个数字:');
                const ret = await readLines(Deno.stdin).next();
                const value = Number(ret.value.trim());
				if (typeof value !== 'number' || isNaN(value)) {
					console.log('输入内容不为数字！');
					break;
				}
				q.add(value);
				break;
			case 'p':
				const valuePop = q.pop();
				console.log(`${valuePop}，出队`);
				break;
			case 's':
				q.show();
				break;
        }
    }
}

链表

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。

实践案例

使用单向链表做一个水浒英雄榜，实现了增删改查，以及按序号加入：

class HeroNode {
    public no: number;
    public name: string;
    public nickName: string;
    public next: HeroNode | null;
    constructor(no: number, name: string, nickName: string) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
        this.next = null;
    }

    public show() {
        console.log(`no = ${this.no}; name = ${this.name}; nickName = ${this.nickName}`);
    }
}

class SingleLinkedList {
    private head: HeroNode;
    constructor() {
        this.head = new HeroNode(0, '', '');
    }
    /** 加入到最后 */
    public add(node: HeroNode) {
        let temp = this.head;
        while (temp.next) {
            temp = temp.next;
        }
        temp.next = node;
    }
    /**
     * 按照编号加入
     * 1. 已存在就提示
     * */
    public addByOrder(heroNode: HeroNode) {
        let temp: HeroNode | null = this.head;
        let flag = false; // 是否存在

        // 找到要插入的上一个位置
        while (temp.next !== null) {
            if (temp.next.no === heroNode.no) {
                flag = true;
                break;
            }
            if (temp.next.no > heroNode.no) {
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            console.log(`编号：${heroNode.no}，已存在`)
            return;
        }
        heroNode.next = temp.next;
        temp.next = heroNode;
    }
    /** 修改 */
    public update(newHeroNode: HeroNode) {
        let temp = this.head;
        let flag = false; // 是否存在
        while (temp.next !== null) {
            if (temp.no === newHeroNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
            return;
        }
        console.log('要修改的英雄不存在');
    }
    /** 删除 */
    public del(no: number) {
        let temp = this.head;
        let flag = false; // 是否存在

        // 找上一个
        while (temp.next) {
            if (temp.next.no === no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag && temp.next !== null) {
            temp.next = temp.next.next;
            return;
        }
        console.log('要删除的英雄不存在');
    }
    /** 展示链表中的内容 */
    public show() {
        let temp = this.head;
        while (temp.next) {
            temp = temp.next;
            temp.show();
        }
    }
}

window.onload = function main() {
    const hero1 = new HeroNode(1, '宋江', '及时雨');
    const hero2 = new HeroNode(2, '卢俊义', '玉麒麟');
    const hero3 = new HeroNode(3, '吴用', '智多星');
    const hero4 = new HeroNode(4, '公孙胜', '入云龙');
    const singleLinkedList = new SingleLinkedList();
    // singleLinkedList.add(hero1);
    // singleLinkedList.add(hero2);
    // singleLinkedList.add(hero3);
    // singleLinkedList.add(hero4);
    singleLinkedList.addByOrder(hero2);
    singleLinkedList.addByOrder(hero1);
    singleLinkedList.addByOrder(hero4);
    singleLinkedList.addByOrder(hero3);
    singleLinkedList.del(5);
    singleLinkedList.show();
}

下期预告

下期针对单向链表做几个面试题：

• 求单链表中节点个数

• 查找单链表中的倒数第k个节点

• 单链表反转

• 从尾到头打印单链表

  反向遍历

  Stack栈

• 合并有序单链表，合并后依然有序