数据结构的javascript实现

红太狼 2021-03-27 11:50 510阅读 0赞

## 栈 ##

> 栈（stack）又名堆栈，是一种遵循后进先出（LIFO）原则的有序集合。新添加或待删除的元素都保存在栈的末尾，称作栈顶，另一端称作栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。

## 队列 ##

## 单链表 ##

## 双向链表 ##

// 结点类
    function Node(element) {
        this.element = element;
        this.next = null;
        this.previous = null;
    }
    // 方法类
    function LList() {
        this.head = new Node("head");
        this.find = find;  // 查找给定数据
        this.insert = insert;  // 在指定结点后面插入一个结点
        this.display = display;  // 展示链表
        this.remove = remove;  // 移除一个结点
        this.findLast = findLast;  // 找到最后一个结点
        this.dispReverse = dispReverse;  // 反序展示双向链表
    }
    
    // 反序展示链表
    function dispReverse() {
        var currNode = this.head;
        currNode = this.findLast();
        while (!(currNode.previous == null)) {
            print(currNode.element);
            currNode = currNode.previous;
        }
    }
    
    // 找到最后一个结点
    function findLast() {
        var currNode = this.head;
        while (!(currNode.next == null)) {
            currNode = currNode.next;
        }
        return currNode;
    }
    
    // 移除一个结点
    function remove(item) {
        var currNode = this.find(item);
        if (!(currNode.next == null)) {
            currNode.previous.next = currNode.next;
            currNode.next.previous = currNode.previous;
            currNode.next = null;
            currNode.previous = null;
        }
    }
    
    // 展示链表
    function display() {
        var currNode = this.head;
        while (!(currNode.next == null)) {
            print(currNode.next.element);
            currNode = currNode.next;
        }
    }
    
    // 找到指定结点
    function find(item) {
        var currNode = this.head;
        while (currNode.element != item) {
            currNode = currNode.next;
        }
        return currNode;
    }
    
    // 把新结点插入到指定结点后面
    function insert(newElement, item) {
        var newNode = new Node(newElement);
        var current = this.find(item);
        newNode.next = current.next;
        newNode.previous = current;
        current.next = newNode;
    }
    
    var cities = new LList();
    cities.insert("Conway", "head");
    cities.insert("Russellville", "Conway");
    cities.insert("Carlisle", "Russellville");
    cities.insert("Alma", "Carlisle");
    cities.display();
    print('\n');
    cities.remove("Carlisle");
    cities.display();
    print('\n');
    cities.dispReverse();

打印结果：  
![1017946-20170408180800160-1147411479.png][]

## 二叉树(暂未调试) ##

// *模拟输出
    function print(x) {
        console.log(x);
    }
    
    
    function Node(data, left, right) {
        this.data = data;
        this.left = left;
        this.right = right;
        this.show = show;
    }
    
    function show() {
        return this.data;
    }
    
    function BST() {
        this.root = null;
        this.insert = insert;
        this.inOrder = inOrder;
    }
    
    function insert(data) {
        var n = new Node(data, null, null);
        if (this.root == null) {
            this.root = n;
        } else {
            var current = this.root;
            var parent;
            while (true) {
                parent = current;
                if (data < current.data) {
                    current = current.left;
                    if (current == null) {
                        parent.left = n;
                        break;
                    }
                } else {
                    current = current.right;
                    if (current == null) {
                        parent.right = n;
                        break;
                    }
                }
            }
        }
    }
    
    function inOrder(node) {
        if (!(node == null)) {
            inOrder(node.left);
            putstr(node.show() + " ");
            inOrder(node.right);
        }
    }
    
    
    function preOrder(node) {
        if (!(node == null)) {
            putstr(node.show() + " ");
            preOrder(node.left);
            preOrder(node.right);
        }
    }
    
    
    function postOrder(node) {
        if (!(node == null)) {
            postOrder(node.left);
            postOrder(node.right);
            putstr(node.show() + " ");
        }
    }
    
    
    function getMin() {
        var current = this.root;
        while (!(current.left == null)) {
            current = current.left;
        }
        return current.data;
    }
    
    function getMax() {
        var current = this.root;
        while (!(current.right == null)) {
            current = current.right;
        }
        return current.data;
    }
    
    function find(data) {
        var current = this.root;
        while (current != null) {
            if (current.data == data) {
                return current;
            } else if (data < current.data) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return null;
    }
    
    function remove(data) {
        root = removeNode(this.root, data);
    }
    
    function removeNode(node, data) {
        if (node == null) {
            return null;
        }
        if (data == node.data) {
            // 没有子节点的节点
            if (node.left == null && node.right == null) {
                return null;
            }
            // 没有左子节点的节点
            if (node.left == null) {
                return node.right;
            }
            // 没有右子节点的节点
            if (node.right == null) {
                return node.left;
            }
            // 有两个子节点的节点
            var tempNode = getSmallest(node.right);
            node.data = tempNode.data;
            node.right = removeNode(node.right, tempNode.data);
            return node;
        } else if (data < node.data) {
            node.left = removeNode(node.left, data);
            return node;
        } else {
            node.right = removeNode(node.right, data);
            return node;
        }
    }

[1017946-20170408180800160-1147411479.png]: /images/20210327/1616845811763.png