数据结构的javascript实现 红太狼 2021-03-27 11:50 444阅读 0赞 ## 栈 ## > 栈(stack)又名堆栈,是一种遵循后进先出(LIFO)原则的有序集合。新添加或待删除的元素都保存在栈的末尾,称作栈顶,另一端称作栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。 function Stack() { var data = []; // 入栈:放在数组末尾 this.push = function(ele) { data.push(ele); }; // 出栈:弹出栈顶元素(数组末尾的元素) this.pop = function() { return data.pop(); }; // 查看栈顶元素 this.peek = function() { return data[data.length - 1]; } // 判断栈空:返回布尔 this.isAmpty = function() { return data.length === 0 }; // 清空栈 this.clear = function() { data = []; }; // 返回栈的长度 this.size = function() { return data.length; }; // 以字符串显示栈中所有内容 this.print = function() { console.log(data.toString()); }; } var s = new Stack; s.push("a"); s.push("b"); s.push("c"); s.push("d"); s.push("e"); s.print(); // a,b,c,d,e ## 队列 ## function print(x) { console.log(x); } // function Queue() { this.data = []; // 队列用数组实现 this.enqueue = enqueue; // 入队 this.dequeue = dequeue; // 出队 this.front = front; // 求队头元素 this.back = back; // 求队尾元素 this.toString = toString; this.empty = empty; // 判断队空 } // 入队 function enqueue(ele) { this.data.push(ele); } // 出队 function dequeue() { return this.data.shift(); } // 求队头元素 function front() { return this.data[0]; } // 求队尾元素 function back() { return this.data[this.data.length - 1]; } function toString() { var retStr = ""; for (var i = 0; i < this.data.length; ++i) { retStr += this.data[i] + "\n"; } return retStr; } // 判断队空 function empty() { if (this.data.length == 0) { return true; } else { return false; } } // 测试程序 var q = new Queue(); q.enqueue("Meredith"); q.enqueue("Cynthia"); q.enqueue("Jennifer"); print(q.toString()); // Meredith // Cynthia // Jennifer q.dequeue(); print(q.toString()); // Cynthia // Jennifer print("Front of queue: " + q.front()); // Front of queue: Cynthia print("Back of queue: " + q.back()); // Back of queue: Jennifer ## 单链表 ## function print(x) { console.log(x); } // // 结点类 function Node(element) { this.element = element; this.next = null; } // 方法类 function LList() { this.head = new Node("head"); this.find = find; this.insert = insert; this.display = display; this.findPrevious = findPrevious; this.remove = remove; } // 移除一个结点 function remove(item) { var prevNode = this.findPrevious(item); if (!(prevNode.next == null)) { prevNode.next = prevNode.next.next; } } // 找到当前结点的前一个结点 function findPrevious(item) { var currNode = this.head; while (!(currNode.next == null) && (currNode.next.element != item)) { currNode = currNode.next; } return currNode; } // 展示所有结点 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; } // 在item后面插入newEle function insert(newElement, item) { var newNode = new Node(newElement); var current = this.find(item); newNode.next = current.next; 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(); // Conway // Russellville // Carlisle // Alma print('\n') cities.remove("Carlisle"); cities.display(); // Conway // Russellville // Alma ## 双向链表 ## // 结点类 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
还没有评论,来说两句吧...