重启数据结构与算法3

[Ray-56]

重启数据结构与算法3

重启数据结构与算法，一些代码案例使用 Deno 与 TypeScript 实现，相关代码都在这里

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

双向链表

双向链表，又称为双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

单向链表的缺点：

• 查找只能一个方向
• 不能自我删除，需要辅助节点temp(待删除节点的前一个)

实例

将水浒英雄榜改为双向链表

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

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

class DoubleLinkedList {
    private head: HeroNode;
    constructor() {
        this.head = new HeroNode(-1, '', '');
    }
    /** 获取头节点 */
    public getHead() {
        return this.head;
    }
    /** 展示环形链表 */
    public show() {
        let temp = this.head;

        while (temp.next) {
            temp = temp.next;
            temp.show();
        }
    }
    /** 默认添加到最后 */
    public add(node: HeroNode) {
        let temp = this.head;

        while (temp.next) {
            temp = temp.next;
        }
        node.prev = temp;
        temp.next = node;
    }
    /** 按序号添加 */
    public addByOrder(node: HeroNode) {
        if (!this.head.next) {
            this.head.next = node;
            node.prev = this.head;
            return;
        }
        let temp = this.head;
        let flag = false;
        while (temp.next) {
            if (temp.no === node.no) {
                flag = true;
                break;
            }
            if (temp.no > node.no) {
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            console.log(`英雄${node.no}已存在!`);
            return;
        }

        node.next = temp;
        node.prev = temp.prev;
        temp.prev!.next = node;
        temp.prev = node;
    }
    /** 修改 */
    public update(node: HeroNode) {
        let temp = this.head;
        let flag = false;
        while (temp.next) {
            temp = temp.next;
            if (temp.no === node.no) {
                flag = true;
                break;
            }
        }

        if (flag) {
            temp.name = node.name;
            temp.nickName = node.nickName;
            return;
        }
        console.log('要修改的英雄未找到')
    }
    /** 删除 */
    public del(no: number) {
        let temp = this.head;
        let flag = false;
        while (temp.next) {
            temp = temp.next;
            if (temp.no === no) {
                flag = true;
                break;
            }
        }
        if (flag) {
            temp.prev!.next = temp.next;
            if (temp.next !== null) {
                temp.next!.prev = temp.prev;
            }
            return;
        }
        console.log('未找到要删除的');
    }
}

单向环形链表

循环链表是一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。

约瑟夫问题

约瑟夫问题，或称“约瑟夫环”，又名“丢手绢问题”。是一个非常典型的单向循环链表的实例。

问题描述：

现有T个人围成一桌坐下，编号从1到T，从编号为S的人开始报数。
报数也从1开始，报到M的人离席，从离席者的下一位在座成员开始，继续从1开始报数。
复现这个过程（各成员的离席次序），或者求最后一个在座的成员编号。

代码实现：

class Boy {
    private _no: number;
    private _next: Boy | null = null;
    constructor(no: number) {
        this._no = no;
    }
    get no(): number {
        return this._no;
    }

    get next(): Boy | null {
        return this._next;
    }
    set next(newNext: Boy | null) {
        this._next = newNext;
    }
}

class CircleSingleLinkedList {
    private first: Boy | null = null;

    public addBoys(num: number) {
        if (num < 1) throw new Error('num 不能小于 1');
        let curBoy: Boy;
        for (let i = 1; i <= num; i++) {
            const boy = new Boy(i);
            if (i === 1) {
                this.first = boy;
                this.first.next = this.first; // 构成环
                curBoy = this.first;
            } else {
                curBoy!.next = boy;
                boy.next = this.first; // 构成环
                curBoy = boy;
            }
        }
    }
    public showBoy() {
        if (this.first === null) {
            console.log('没有小孩');
            return;
        }
        let curBoy = this.first;
        while (curBoy.next !== this.first) {
            console.log(curBoy.no);
            curBoy = curBoy.next as Boy;
        }
        console.log(curBoy.no);
    }
    /**
     * 小孩出圈
     * @param startNo - 第S个小孩还是报数
     * @param countNum - 数多少下
     * @param nums - 最初有多少个小孩
     */
    public countBoy(startNo: number, countNum: number, nums: number) {
        if (this.first === null || startNo < 1 || startNo > nums) {
            console.log('参数有误');
            return;
        }
        let helper = this.first;
        // helper 指向最后一个节点
        while (helper.next !== this.first) {
            helper = helper.next as Boy;
        }

        // 移动到开始的位置
        for (let i = 1; i < startNo; i++) {
            this.first = this.first!.next;
            helper = helper.next as Boy;
        }

        // 只有一个节点了
        while (helper !== this.first) {

            // 数次数后出圈
            for (let j = 1; j < countNum; j++) {
                this.first = this.first!.next;
                helper = helper.next as Boy;
            }
            console.log(`要出圈的小孩${this.first!.no}`);

            // 出圈
            this.first = this.first!.next;
            helper.next = this.first;
        }
        console.log(`最后留在圈中的小孩${this.first!.no}`);
    }
}

window.onload = () => {
    const circleSingleLinkedList = new CircleSingleLinkedList();
    circleSingleLinkedList.addBoys(5);
    // circleSingleLinkedList.showBoy();

    circleSingleLinkedList.countBoy(1, 2, 5); // 2 4 1 5 // 3
}

下期预告

• 栈
• 前中后缀表达式与计算器的实现