javascriptに基づくデータ構造の実現(一)
12530 ワード
データ構造データ構造は、プログラマーとして知らなければならない基礎知識であり、教養の一つでもあります.次に、いくつかの簡単な基礎のデータ構造を大紹介します. スタックスタック:このようなデータ構造は、必ずその特徴が必要です.後進が先に出ると、食べて吐き出すように、上品ではないというたとえですが、とてもイメージがあります. 続いて、jsでみんなのために実現して、配列を利用して実現して、理解しやすくて、時間の複雑さはo(1)で、空間の複雑さはo(n)です. 上のコードは私がみんなのためにスタック/スタック/スタック長とスタックトップの要素を実現しました.コードを使ってみんなのために一回実現しました.みんなも時間があれば、コードを絞ります. キュー列:先进先出、次も行列を利用して実现します. 時間の複雑さはo(1)であり、空間の複雑さはo(n) である.次は優先列を紹介します.列に並ぶ時は優先権があります.割り込むことができます. 優先キュー 空間複雑度はo(n)であり、時間複雑度o(n) である.上記の2つのデータ構造について理解しました.フロントエンドの多くの原理についても、ぱっと明るくなります.ブラウザの原理の中のイベント循環メカニズムやゴミ回収中のスタックメモリやメモリ回収メカニズムなどがあります.
チェーン?メーター 特徴:メモリ不連続性は、配列が連続するメモリと比較しても良い. はこのような特性のために、チェーンテーブルの表が長くて、解を求める必要があります.チェーンテーブルは現在のノードと次のポインタnextがあります.nextポインタは次のノードを指します.次は次のノードを指します.最後のノードのnextがnull です.上に記載されているのは一方向チェーンであり、それ以外にも双方向チェーンと循環チェーンテーブルがあります.双方向リンク表は、必ず一方向チェーンテーブルが一つ多くなったpre針で、チェーンテーブルが二つのチェーンテーブルをそれぞれnextとpreからリンクした を意味しています.循環チェーンテーブルは、エンドノードのnextポインタをヘッドノードheadに向けて、循環チェーン と呼ばれる大きなループを形成する.コードが実現され、一方向チェーンの例: 上のチェーンテーブルは、チェーンテーブルの追加ノード、挿入ノード、クエリノード、削除ノードなどを実現しています.このようなデータ構造に詳しい後、reactとvueの原理をより明確に認識することができます. 木ツリー、二叉樹、バランス二叉樹、二叉は木を捜索して、積み上げて、もとの場所で積み上げることと、赤い黒い木、本文は二叉で木を捜索することを例にして、コードを行って を実現します.二叉はツリーの特性を検索します.ルートノードは左右の2つのサブツリーに分けられます.左のサブツリーは親ノードより小さいです.右のサブツリーは親ノードより大きいです.まとめて、左小右大. 部分実装:ツリー構造:左右の子樹が完成した は、ツリープラスリーフノードである: により、ジグザグの木を構成する構造 .は、ツリーの中の順序を実現し、先の順序および後の順序が を巡回する.総括:二叉検索ツリーは成功しました.ツリーというデータ構造も比較的頻繁なデータ構造を使っています.特に下のフレームの開発に応用します. 集合するには重複要素がなく、順序概念がないデジタルデータ構造 がある.続いて、みんなのために簡単に集合方法を実現します. 交差点: 差セット を統合する .サブセット まとめ:この上で、私はスタック、キュー、ツリー、優先列、集合及び辞書といういくつかの簡単なデータ構造を実現しました.これからはヒープを実現し、元の場所にヒープを建設し、リスト及び図のデータ構造を実現します.
参考文献 Javascriptに基づくデータ構造とアルゴリズム
function Stack() {
var items = [];
//
this.push = function(value) {
items.push(value);
};
//
this.pop = function() {
return items.pop();
};
//
this.peek = function() {
return items[items.length - 1];
};
this.isEmpty = function() {
return items.length === 0;
};
this.size = function() {
return items.length;
};
this.clear = function() {
items = [];
};
this.print = function() {
console.log(items.toString());
};
}
function Queue() {
var items = [];
//
this.enQueue = function(value) {
items.push(value);
};
//
this.outQueue = function() {
return items.shift();
};
this.front = function() {
return items[0];
};
this.isEmpty = function() {
return items.length === 0;
};
this.clear = function() {
items = [];
};
this.size = function() {
return items.length;
};
this.print = function() {
console.log(items);
};
}
function PriorityQueue() {
var items = [];
function QueueElement(value, priority) {
this.value = value;
this.priority = priority;
}
this.enQueue = function(value, priority) {
var queueElement = new QueueElement(value, priority);
if (this.isEmpty()) {
items.push(queueElement);
} else {
var isAdd = false;
for (var i = 0; i < this.size(); i++) {
if (items[i].priority > queueElement.priority) {
items.splice(i, 0, queueElement);
isAdd = true;
break;
}
}
if (!isAdd) {
items.push(queueElement);
}
}
};
this.outQueue = function() {
return items.shift();
};
this.front = function() {
return items[0];
};
this.isEmpty = function() {
return items.length === 0;
};
this.clear = function() {
items = [];
};
this.size = function() {
return items.length;
};
this.print = function() {
console.log(items);
};
}
チェーン?メーター
function CreateList() {
this.headNode = null;
this.nodeLength = 0;
//
this.createNode = function (value) {
this.data = value;
this.nextNode = null;
};
}
CreateList.prototype.ListLength = function () {
let headNode = this.headNode;
let count = 0;
if (headNode) {
count = count + 1;
}
while (headNode.nextNode) {
count++;
headNode = headNode.nextNode;
}
return count;
};
//
CreateList.prototype.appendNode = function (value) {
// console.log(this);
const node = new this.createNode(value);
let current = null;
if (!this.headNode) {
this.headNode = node;
} else {
current = this.headNode;
while (current.nextNode) {
current = current.nextNode;
}
current.nextNode = node;
}
this.nodeLength++;
};
//
CreateList.prototype.insertNode = function (value, location) {
if (location >= 0 && location <= this.nodeLength) {
let node = new this.createNode(value);
let current = this.headNode;
let count = 0;
let pre;
if (location == 0) {
node.nextNode = current;
this.headNode = node;
} else {
while (count < location) {
pre = current;
current = current.nextNode;
count++;
}
node.nextNode = current;
pre.nextNode = node;
}
this.nodeLength++;
return true;
} else {
return false;
}
};
//
CreateList.prototype.deleteLocationNode = function (location) {
if (location >= 0 && location < this.nodeLength) {
let current = this.headNode;
let count = 0;
let pre, next;
if (location === 0) {
current = this.headNode.nextNode;
this.headNode = current;
} else {
while (count < location) {
pre = current;
current = current.nextNode;
next = current.nextNode;
count++;
}
pre.nextNode = next;
}
this.nodeLength--;
return true;
} else {
console.warn(' ');
return false;
}
};
//
CreateList.prototype.isNode = function (element) {
let current = this.headNode;
let indexFlag = false;
if (current.data === element) {
return true;
}
while (current.nextNode) {
current = current.nextNode;
if (current.data === element) {
indexFlag = true;
break;
}
}
return indexFlag;
};
//
CreateList.prototype.indexOf = function (element) {
const isElement = this.isNode(element);
if (isElement) {
let count = 0;
let current = this.headNode;
if (current.data === element) {
return count;
}
while (current.nextNode) {
count++;
current = current.nextNode;
if (current.data === element) {
break;
}
}
return count;
} else {
return -1;
}
};
//
CreateList.prototype.deleteElementNode = function (element) {
//
const isElement = this.isNode(element);
if (isElement) {
let current = this.headNode;
let pre;
let count = 0;
if (current.data === element) {
this.headNode = current.nextNode;
}
pre = current;
current = current.nextNode;
while (current) {
if (current.data === element) {
pre.nextNode = current.nextNode;
current = current.nextNode;
this.nodeLength--;
count++;
} else {
pre = current;
current = current.nextNode;
}
}
return count;
} else {
console.warn(' ');
return false;
}
};
//
CreateList.prototype.toString = function () {
let data = this.headNode.data;
let current = this.headNode.nextNode;
while (current) {
data += `,${current.data}`;
current = current.nextNode;
}
return data;
};
function BinarySearchTree() {
var Node = function(key) {
this.key = key;
this.left = null;
this.right = null;
};
var root = null;
}
var insertNode = function(node, newNode) {
//
if (newNode.key < node.key) {
if (node.left === null) {
node.left = newNode;
} else {
insertNode(node.left, newNode);
}
} else {
if (node.right === null) {
node.right = newNode;
} else {
insertNode(node.right, newNode);
}
}
};
this.insert = function(key) {
var node = new Node(key);
if (root === null) {
root = node;
} else {
insertNode(root, node);
}
};
var tree = new BinarySearchTree();
tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
var inOrderTraverseNode = function(node, callback) {
//
if (node !== null) {
inOrderTraverseNode(node.left, callback);
callback(node, callback);
inOrderTraverseNode(node.right, callback);
}
};
this.inOrderTraverse = function(callback) {
//
inOrderTraverseNode(root, callback);
};
//
var preOrderTraverseNode = function(node, callback) {
if (node !== null) {
callback(node, callback);
preOrderTraverseNode(node.left, callback);
preOrderTraverseNode(node.right, callback);
}
};
this.preOrderTraverse = function(callback) {
//
preOrderTraverseNode(root, callback);
};
//
var postOrderTraverseNode = function(node, callback) {
if (node !== null) {
postOrderTraverseNode(node.left, callback);
postOrderTraverseNode(node.right, callback);
callback(node, callback);
}
};
//
this.postOrderTraverse = function(callback) {
postOrderTraverseNode(root, callback);
};
function Set() {
var items = {};
//
this.has = function(value) {
return value in items;
};
//
this.add = function(value) {
if (!this.has(value)) {
items[value] = value;
return true;
}
return false;
};
//
this.remove = function(value) {
if (this.has(value)) {
delete items[value];
return true;
}
return false;
};
this.clear = function() {
items = {};
};
this.size = function() {
return Object.keys(items).length;
};
this.values = function() {
return Object.keys(items);
};
}
this.intersection = function(otherSet) {
var intersectionSet = new Set();
var values = this.values();
for (var i = 0; i < values.length; i++) {
if (otherSet.has(values[i])) {
intersectionSet.add(values[i]);
}
}
return intersectionSet;
};
this.difference = function(otherSet) {
var differenceSet = new Set();
values = this.values();
for (var i = 0; i < values.length; i++) {
if (!otherSet.has(values[i])) {
differenceSet.add(values[i]);
}
}
return differenceSet;
};
this.union = function(otherSet) {
var unionSet = new Set();
var values = this.values();
for (var i = 0; i < values.length; i++) {
unionSet.add(values[i]);
}
values = otherSet.values();
for (var i = 0; i < values.length; i++) {
unionSet.add(values[i]);
}
return unionSet;
};
this.subSet = function(otherSet) {
if (this.size() > otherSet.size()) {
return false;
} else {
var value = this.values();
for (var i = 0; i < values.length; i++) {
if (!otherSet.has(values[i])) {
return false;
}
}
return true;
}
};
function Dictionary() {
var items = {};
this.has = function(value) {
return value in items;
};
this.set = function(key, value) {
items[key] = value;
};
this.remove = function(key) {
if (this.has(key)) {
delete items[key];
}
};
this.get = function(key) {
return this.has(key) ? items[key] : undefined;
};
this.values = function() {
var values = [];
for (var i in items) {
if (this.has(i)) {
values.push(items[i]);
}
}
return values;
};
this.getItems = function() {
return items;
};
this.clear = function() {
items = {};
};
this.size = function() {
return Object.keys(items).length;
};
this.keys = function() {
return Object.keys(items);
};
}
参考文献