数据结构篇(2) ts实现单循环链表

JS的class可以通过extends关键字实现类似其他语言的继承效果，比起使用一个extends关键字，在es5中实现继承要复杂一些，可以通过修改原型链的方法实现继承，让一个原型对象等于另一个类型的实例等等，虽然也能够实现，但是不够直观。

constructor()方法中的super()表示调用父类的构造函数，在这里就是调用SIngleList类里面的构造函数。

接下来就可以使用SingleList类中已经实现的函数了，但是由于单向循环链表的某些操作还是不同于单链表的，所以对SingleList类中的一些方法，需要在CirSingleList类中重写。

//继承单链表的属性和方法，有一些方法需要重写

class CirListNode extends ListNode {

    constructor() {

        super()

    }

    // 在单循环链表中寻找最后一个节点

    /** 使用count进行计数，如果与当前链表的长度相同就返回子节点，这样就可以避免陷入无限循环*/

    findLast(): NodeItem {

        let count = 0;

        let currNode = this.head;

        while (currNode.next) {

            currNode = currNode.next;

            count++;

            if (count === this.size) {

                return currNode;

            }

        }

        return this.head;

    }

    // 在单循环链表中寻找数据

    /** 如果对应元素不存在会导致无限循环，

    所以需要重写搜索函数,如果当前节点等于最后一个子节点就结束循环返回null*/

    find(item: any): NodeItem {

        let lastNode = this.findLast();

        let currNode = this.head;

        while (currNode.data != item) {

            if (currNode == lastNode) {

                currNode = null;

                break;

            }

            currNode = currNode.next;

        }

        return currNode;

    }

    // 在数据为item的节点后面插入数据为element元素的节点

    /**

     *  1. 插入的是头节点位置，如果当前链表为空，则将新节点插入到head节点后面，并指向自己，形成循环

     *  2，插入的是头节点位置，当前链表不为空，则将新节点指向头节点的下一个节点，然后再将头节点指向新节点，再将尾节点指向新节点，形成一个新的循环

     *  3, 插入的是中间位置，就正常插入即可

    */

    insert(item: any, element: any): void {

        let newNode = new NodeItem(element);

        let itemNode = this.find(item);

        let lastNode = this.findLast();

        // 插入的位置处于头结点之后，第一个节点之前

        if (item === 'head') {

            if (this.size === 0) {

                this.head.next = newNode;

                newNode.next = newNode;

            } else {

                newNode.next = this.head.next;

                this.head.next = newNode;

                lastNode.next = newNode;

            }

            this.size++;

            return;

        }

        // 处于链表中后位置时

        newNode.next = itemNode.next;

        itemNode.next = newNode;

        this.size++;

    }

    /**

     * 1. 当前删除的节点是第一个节点时，如果此时单向循环链表只有一个节点，直接将此单向链表置空即可

     * 2. 当前删除的节点是第一个节点时， 且此时单向循环链表不仅只有一个节点时，此时将头节点的next指针指向要删除节点的下一个节点，并将最后一个节点指向要删除节点的下一个节点

     * 3.  除了前面的两种情况之外，只要将删除节点的前一个节点next指针指向要删除节点的后一个系欸但即可

    */

    remove(item: any): void {

        let lastNode = this.findLast();

        let itemNode = this.find(item);

        let preCurNode = this.head;

        while (preCurNode.next !== itemNode) {

            preCurNode = preCurNode.next;

        }

        if (itemNode === this.head.next) {

            if (this.size === 1) {

                this.head.next = null;

            } else {

                this.head.next = itemNode.next;

                lastNode.next = itemNode.next;

            }

        } else {

            preCurNode.next = itemNode.next;

        }

        this.size--;

    }

    /**

     * 根据count计数来输出链表内容,防止陷入无限循环

     */

    display(): void {

        let count = 0;

        let currNode = this.head;

        let str = '';

        while (count !== this.size) {

            currNode = currNode.next;

            str += currNode.data + '=>';

            count++;

        }

        console.log(str)

    }

    /**

     * 在尾部插入数据

     * 用写好的findLast()方法，找到最后一个节点，然后将最后一个节点next指针指向新的节点，再将新的节点指向此链表的第一个节点即可。

     */

    append(element: any): void {

        let lastNode = this.findLast();

        let newNode = new NodeItem(element);

        lastNode.next = newNode;

        newNode.next = this.head.next;

        this.size++;

    }

}

// n个人围成一圈，杀死第m个人，直到剩下s个人为止

// 输出存活的人的序号

let myList = new CirListNode();

function killPerson(n: any, m: any, s: any) {

    for (let i = 1; i <= n; i++) {

        myList.append(i);

    }

    let currNode = undefined;

    let toKill = null;

    while(myList.size>s) {

        toKill = myList.advance(m, currNode);  // 从currNode开始，前进m个节点

        currNode = toKill;  // 保存要删除的节点作为下一次循环的参数

        myList.remove(toKill.data);  // 删除第m个节点

    }

    myList.display();

}

killPerson(41, 3, 2);  // head->16->31

// killPerson(5, 4, 1);  // head->1

巴特西

数据结构篇(2) ts实现单循环链表

最新文章

热门文章