資訊專欄INFORMATION COLUMN
摘要：數(shù)據(jù)結(jié)構(gòu)前言隨著的興起將推向的一個前所未有的高度作為為建立高性能的服務(wù)端而創(chuàng)建的運(yùn)行平臺隨著時間的推移和生態(tài)鏈的完善已經(jīng)不再局部于服務(wù)端包括前端后端桌面正如在年提出的任何可以使用來編寫的應(yīng)用，最終會由編寫雖然人們大多或多或少對筆者的文章有點
數(shù)據(jù)結(jié)構(gòu) 前言
隨著node的興起, 將javascript推向的一個前所未有的高度, node作為為建立高性能的服務(wù)端而創(chuàng)建的js運(yùn)行平臺隨著時間的推移和生態(tài)鏈的完善已經(jīng)不再局部于服務(wù)端,包括前端,后端,桌面......二維數(shù)組
正如Jeff Atwood在2007年提出的：任何可以使用JavaScript來編寫的應(yīng)用，最終會由JavaScript編寫, 雖然人們大多或多或少對筆者的文章有點斷章取義, 但無可變非的是javascript正在大行其道 ^_^,
但正如偉大的js之父親布蘭登.艾奇--(每每想起他和 冰與火之歌中史塔克家族什么關(guān)系 哈哈)所說js是C語言和Self語言一夜情的產(chǎn)物, 他的生命力與發(fā)展遠(yuǎn)遠(yuǎn)超出作者的預(yù)期, 間接導(dǎo)致設(shè)計之初并沒有過多的考慮對數(shù)據(jù)結(jié)構(gòu)的支持,
但es規(guī)范制定者似乎已經(jīng)察覺到了這一點, 于是最es6標(biāo)準(zhǔn)增加了set集合和map集合,有興趣的可以查閱最新的es標(biāo)準(zhǔn),這里推薦阮一峰的es6入門 筆者認(rèn)為是一部不錯的教材(^_^筆者可不是做廣告),有興趣的可以查閱,下面給出連接es6 阮一峰http://es6.ruanyifeng.com
Array.matrix = function(numrows, numcols, initial) {
let arr = [];
for (let i = 0; i < numrows; ++i) {
let columns = [];
for (let j = 0; j < numcols; ++j) {
columns[j] = initial;
}
arr[i] = columns;
}
return arr;
}
棧
let Stack = (function(){
function Stack() {
this.dataStore = [];
this.top = 0;
}
Stack.prototype.push = function(element) {
this.dataStore[this.top++] = element;
}
Stack.prototype.peek = function() {
return this.dataStore[this.top-1];
}
Stack.prototype.pop = function() {
return this.dataStore[--this.top];
}
Stack.prototype.clear = function() {
this.top = 0;
}
Stack.prototype.length = function() {
return this.top;
}
return Stack;
})();
隊列
let Queue = (function () {
function Queue() {
this.dataStore = [];
}
Queue.prototype.enqueue = function(element) {
this.dataStore.push(element);
}
Queue.prototype.dequeue = function() {
return this.dataStore.shift();
}
Queue.prototype.front = function() {
return this.dataStore[0];
}
Queue.prototype.back = function() {
return this.dataStore[this.dataStore.length-1];
}
Queue.prototype.toString = function() {
var retStr = "";
for (var i = 0; i < this.dataStore.length; ++i) {
retStr += this.dataStore[i] + "
";
}
return retStr;
}
Queue.prototype.empty = function() {
if (this.dataStore.length == 0) {
return true;
} else {
return false;
}
}
return Queue;
})()
優(yōu)先隊列
let PriQueue = (function() {
function Ele(value, code) {
this.value = value;
this.code = code;
}
function PriQueue() {
this.dataStore = [];
}
PriQueue.prototype.enqueue = function(element) {
this.dataStore.push(element);
}
PriQueue.prototype.dequeue = function() {
var priority = this.dataStore[0].code;
for (var i = 1; i < this.dataStore.length; ++i) {
if (this.dataStore[i].code < priority) {
priority = i;
}
}
return this.dataStore.splice(priority,1);
}
PriQueue.prototype.front = function() {
return this.dataStore[0];
}
PriQueue.prototype.back = function() {
return this.dataStore[this.dataStore.length-1];
}
PriQueue.prototype.toString = function() {
var retStr = "";
for (var i = 0; i < this.dataStore.length; ++i) {
retStr += this.dataStore[i].name + " code: " + this.dataStore[i].code + "
";
}
return retStr;
}
PriQueue.prototype.empty = function() {
if (this.dataStore.length == 0) {
return true;
} else {
return false;
}
}
return PriQueue;
})()
單向鏈表
let LList = (function() {
function Node(element) {
this.element = element;
this.next = null;
}
function LList() {
this.head = new Node("head");
this.foot = new Node("foot");
this.head.next = this.foot;
}
LList.prototype.remove = function(item) {
var prevNode = this.findPrevious(item);
if (!(prevNode.next == null)) {
prevNode.next = prevNode.next.next;
}
}
LList.prototype.findPrevious = function(item) {
var currNode = this.head;
while ((currNode.next !== null) && (currNode.next.element != item)) {
currNode = currNode.next;
if (currNode.next === null) {
currNode =null;
break;
}
}
return currNode;
}
LList.prototype.display = function() {
var currNode = this.head;
console.log(currNode.element);
while (!(currNode.next == null)) {
currNode = currNode.next;
console.log(currNode.element);
}
}
LList.prototype.find = function(item) {
var currNode = this.head;
while (currNode.element != item) {
currNode = currNode.next;
if (currNode === null) {
break;
}
}
return currNode;
}
LList.prototype.insert = function(newElement, item) {
var newNode = new Node(newElement);
var current = this.find(item);
newNode.next = current.next;
current.next = newNode;
}
return LList;
})()
雙向鏈表
let DLList = (function () {
function Node(element) {
this.element = element;
this.next = null;
this.previous = null;
}
function DLList() {
this.head = new Node("head");
this.foot = new Node("foot");
this.head.next = this.foot;
this.foot.previous = this.head;
}
DLList.prototype.find = function(item) {
var currNode = this.head;
while (currNode.element != item) {
currNode = currNode.next;
if (currNode === null) {
break;
}
}
return currNode;
}
DLList.prototype.insert = function(newElement, item) {
var newNode = new Node(newElement);
var current = this.find(item);
newNode.next = current.next;
newNode.previous = current;
current.next.previous = newNode;
current.next = newNode;
}
DLList.prototype.remove = function(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;
}
}
DLList.prototype.display = function() {
var currNode = this.head;
console.log(currNode.element);
while (currNode.next !== null) {
currNode = currNode.next;
console.log(currNode.element);
}
}
return DLList;
})()
樹
let BST = (function () {
let Node = (function () {
function Node(data, left, right) {
this.data = data;
this.left = left;
this.right = right;
}
Node.prototype.show = function () {
return this.data;
}
return Node;
})()
function BST() {
this.root = null;
}
BST.prototype.insert = function(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;
}
}
}
}
}
BST.prototype.inOrder = function(node) {
if (!(node === null)) {
this.inOrder(node.left);
console.log(node.show() + " ");
this.inOrder(node.right);
}
}
BST.prototype.preOrder = function(node) {
if (!(node === null)) {
console.log(node.show() + " ");
this.preOrder(node.left);
this.preOrder(node.right);
}
}
BST.prototype.postOrder = function(node) {
if (!(node === null)) {
this.postOrder(node.left);
this.postOrder(node.right);
console.log(node.show() + " ");
}
}
BST.prototype.getMin = function() {
var current = this.root;
while (!(current.left == null)) {
current = current.left;
}
return current.data;
}
BST.prototype.getMax = function() {
var current = this.root;
while (!(current.right == null)) {
current = current.right;
}
return current.data;
}
BST.prototype.find = function(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;
}
BST.prototype.remove = function(data) {
root = this.removeNode(this.root, data);
}
BST.prototype.removeNode = function(node, data) {
if (node == null) {
return null;
}
if (data == node.data) {
// 沒有子節(jié)點的節(jié)點
if (node.left == null && node.right == null) {
return null;
}
// 沒有左子節(jié)點的節(jié)點
if (node.left == null) {
return node.right;
}
// 沒有右子節(jié)點的節(jié)點
if (node.right == null) {
return node.left;
}
// 有兩個子節(jié)點的節(jié)點
var tempNode = this.getSmallest(node.right);
node.data = tempNode.data;
node.right = this.removeNode(node.right, tempNode.data);
return node;
}
else if (data < node.data) {
node.left = this.removeNode(node.left, data);
return node;
}
else {
node.right = this.removeNode(node.right, data);
return node;
}
}
BST.prototype.getSmallest = function(node) {
if (node.left == null) {
return node;
} else {
return this.getSmallest(node.left);
}
}
return BST;
})()
圖
let Graph = (function() {
function Graph(v) {
this.vertices = v;
this.vertexList = [];
this.edges = 0;
this.adj = [];
for (var i = 0; i < this.vertices; ++i) {
this.adj[i] = [];
// this.adj[i].push("");
}
this.marked = [];
for (var i = 0; i < this.vertices; ++i) {
this.marked[i] = false;
}
this.edgeTo = [];
}
Graph.prototype.addEdge = function (v, w) {
this.adj[v].push(w);
this.adj[w].push(v);
this.edges++;
}
Graph.prototype.showGraph = function() {
for (var i = 0; i < this.vertices; ++i) {
let st = i + " -> " ;
for (var j = 0; j < this.vertices; ++j ) {
if (this.adj[i][j] != undefined) {
st += this.adj[i][j] + " ";
}
}
console.log(st);
}
}
Graph.prototype.dfs = function(v) {
this.marked[v] = true;
if (this.adj[v] != undefined) {
console.log("Visited vertex: " + v);
}
for (const w of this.adj[v]) {
if (!this.marked[w]) {
this.dfs(w);
}
}
}
Graph.prototype.bfs = function(s) {
var queue = [];
this.marked[s] = true;
queue.push(s); // 添加到隊尾
while (queue.length > 0) {
var v = queue.shift(); // 從隊首移除
if (v !== undefined) {
console.log("Visisted vertex: " + v);
}
for (var w of this.adj[v]) {
if (!this.marked[w]) {
this.edgeTo[w] = v;
this.marked[w] = true;
queue.push(w);
}
}
}
console.log(this.edgeTo);
}
Graph.prototype.hasPathTo = function(s, v) {
this.bfs(s)
return this.marked[v];
}
Graph.prototype.pathTo = function(s, v) {
var source = s;
if (!this.hasPathTo(s, v)) {
return undefined;
}
var path = [];
for (var i = v; i != source; i = this.edgeTo[i]) {
path.unshift(i);
}
path.unshift(source);
return path;
}
Graph.prototype.topSort = function() {
var stack = [];
var visited = [];
for (var i = 0; i < this.vertices; i++) {
visited[i] = false;
}
for (var i = 0; i < this.vertices; i++) {
if (visited[i] == false) {
this.topSortHelper(i, visited, stack);
}
}
for (var i = 0; i < stack.length; i++) {
if (stack[i] != undefined && stack[i] != false) {
console.log(this.vertexList[stack[i]]);
}
}
}
Graph.prototype.topSortHelper = function(v, visited, stack) {
visited[v] = true;
for (var w in this.adj[v]) {
if (!visited[w]) {
this.topSortHelper(visited[w], visited, stack);
}
}
stack.push(v);
}
return Graph;
})()
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/107123.html
摘要：滿二叉樹除葉子節(jié)點以為的每個節(jié)點都有兩個孩子。完全二叉樹可以看成是可以有若干額外向左靠的葉子節(jié)點的完美二叉樹。 以下是在編程面試中排名前10的算法相關(guān)的概念，我會通過一些簡單的例子來闡述這些概念。由于完全掌握這些概念需要更多的努力，因此這份列表只是作為一個介紹。本文將從Java的角度看問題，包含下面的這些概念： 字符串 鏈表 樹 圖 排序 遞歸 vs. 迭代 動態(tài)規(guī)劃 位操作 概率...
摘要：是棧，它繼承于。滿二叉樹除了葉結(jié)點外每一個結(jié)點都有左右子葉且葉子結(jié)點都處在最底層的二叉樹。沒有鍵值相等的節(jié)點。這是數(shù)據(jù)庫選用樹的最主要原因。 在我們學(xué)習(xí)Java的時候，很多人會面臨我不知道繼續(xù)學(xué)什么或者面試會問什么的尷尬情況（我本人之前就很迷茫）。所以，我決定通過這個開源平臺來幫助一些有需要的人，通過下面的內(nèi)容，你會掌握系統(tǒng)的Java學(xué)習(xí)以及面試的相關(guān)知識。本來是想通過Gitbook的...
摘要：數(shù)據(jù)結(jié)構(gòu)程序數(shù)據(jù)結(jié)構(gòu)算法數(shù)據(jù)結(jié)構(gòu)基本概念數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的關(guān)系的數(shù)據(jù)元素集合的表示。這兩部分信息組成數(shù)據(jù)元素的存儲映象，稱為結(jié)點。 本文涉及更多的是概念，代碼部分請參考之前寫過的 2 篇博客 基于 Javascript 的排序算法 基于 javascript 的基本數(shù)據(jù)結(jié)構(gòu)和查找算法 本文主要是基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)和算法概念，可能部分地方會涉及更高級的算法和算法，具體內(nèi)容以...
摘要：為檢查長度為的列表，二分查找需要執(zhí)行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關(guān)于二叉樹，戳這里數(shù)據(jù)結(jié)構(gòu)與算法二叉樹算法常見練習(xí)在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。 常見數(shù)據(jù)結(jié)構(gòu) 簡單數(shù)據(jù)結(jié)構(gòu)（必須理解和掌握） 有序數(shù)據(jù)結(jié)構(gòu)：棧、隊列、鏈表。有序數(shù)據(jù)結(jié)構(gòu)省空間（儲存空間?。?無序數(shù)據(jù)結(jié)構(gòu)：集合、字典、散列表，無序...
閱讀 2787·2021-11-19 11:30
閱讀 3069·2021-11-15 11:39
閱讀 1793·2021-08-03 14:03
閱讀 1999·2019-08-30 14:18
閱讀 2055·2019-08-30 11:16
閱讀 2169·2019-08-29 17:23
閱讀 2611·2019-08-28 18:06
閱讀 2545·2019-08-26 12:22
