http://otona.connpass.com/event/44234/
コンピュータで表現される何らかの情報
具体的な例
- 数字
- 文字
名前: 佐藤
年齢: 30
性別: 男性
構造化されたデータ プログラムでは構造化されたデータを頻繁に扱う
// 構造化されていないデータ
var a = 3;
配列 ar [1|2|3|4|5]
配列に順番にアクセスすることを走査と呼ぶ
var ar = [];
ar[0] = 1;
ar[1] = 2;
console.log(ar); //=> [1, 2]
javascript標準で提供しているデータ構造
連想配列（れんそうはいれつ） 呼び方がいくつかある
- マップ
- ディクショナリ (辞書)
- ハッシュテーブル
| key | value |
|---|---|
| apple | りんご |
| pen | ペン |
| pineapple | パイナップル |
var map = {};
map['apple'] = 'りんご';
map['pen'] = 'ぺん';
map['pineapple'] = 'パイナップル';
map['PPAP'] = '古坂大魔王;
console.log(map);
配列のように連続した値を持って順序があるものをリストという
リスト: データの順番を持った集合
数学的な集合は重複を持たない 近いものをセットと呼ぶ
[0, 1, 2, 3, 4]
1を消した場合どうなるか？
3回の移動が必要
[0, , 2, 3, 4]
[0, 2, , 3, 4]
[0, 2, 3, , 4]
[0, 3, 3, 4]
1000個、10000個の要素があった場合…？
LinkedList (リンクドリスト)
1を削除した場合指定先を書き換えるだけで良い
→ → → → →
0 1 2 3 4
→ → → →
0 2 3 4
リンクドリストを作ってみる
var Node = function (value) {
this.value = value;
this.next = null;
}
var n1 = new Node(10);
console.log(n1);
| Node |
|---|
| value |
| next |
↓
| n1 |
|---|
| 10 |
| null |
var Node = function (value) {
this.value = value;
this.next = null;
}
var n1 = new Node(10);
console.log(n1);
var n2 = new Node(20);
console.log(n2);
| n1 | n2 |
|---|---|
| 10 | 20 |
| null | null |
var Node = function (value) {
this.value = value;
this.next = null;
}
var n1 = new Node(10);
var n2 = new Node(20);
// リストの紐付け
n1.next = n2;
| n1 | n2 |
|---|---|
| 10 | 20 |
| n2 | null |
var Node = function (value) {
this.value = value;
this.next = null;
}
var n1 = new Node(10);
var n2 = new Node(20);
var n3 = new Node(30);
var n4 = new Node(40);
var n5 = new Node(50);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
console.log(n1);
論理的な構造と具体的な構造
プログラムの場合、論理的な構造を扱う
var Node = function (value) {
this.value = value;
this.next = null;
}
var n1 = new Node(10);
var n2 = new Node(20);
var n3 = new Node(30);
var n4 = new Node(40);
var n5 = new Node(50);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
printList(n1);
function printList(topNode) {
// 次のノードがなくなるまでループ
while(node.next !== null) {
console.log(node.value);
node = node.next;
}
// 最後の一個を出力
console.log(node.value);
}
// console.log(n1);
削除を作る
var Node = function (value) {
this.value = value;
this.next = null;
}
var n1 = new Node(10);
var n2 = new Node(20);
var n3 = new Node(30);
var n4 = new Node(40);
var n5 = new Node(50);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
printList(n1);
removeNode(n1, 3);
console.log('-----');
printList(n1);
function printList(topNode) {
var node = topNode;
// 次のノードがなくなるまでループ
while(node.next !== null) {
console.log(node.value);
node = node.next;
}
// 最後の一個を出力
console.log(node.value);
}
/** 0番目は削除できません */
function removeNode(topNode, num) {
if (num === 0) {
console.log('You are not allowed to delete first node.');
return;
}
var idx = 0; // ループインデックス
var node = topNode;
var prev = null; // 1個前のNodeを保持する
while(true) {
if (idx === num) {
// 前の要素と次の要素をつなぎ合わせる
prev.next = node.next;
}
if (node.next === null) {
break;
}
idx++;
prev = node;
node = node.next;
}
}
ルート（根）から2個に別れるノード構造 ノードの先端を葉と呼ぶ
var TNode = function (value) {
this.value = null;
this.left = null;
this.right = null;
}
var tn1 = new TNode();
var tn2 = new TNode();
var tn3 = new TNode();
var tn4 = new TNode();
var tn5 = new TNode();
var tn6 = new TNode();
tn3.value = 10;
tn5.value = 20;
tn6.value = 30;
tn1.left = tn2;
tn2.left = tn3;
tn1.right = tn4;
tn4.left = tn5;
tn4.right = tn6;
print(tn1, 0);
function print(topNode, depth) {
if (topNode.left !== null) {
print(topNode.left, depth+1);
}
if (topNode.right !== null) {
print(topNode.right, depth+1);
}
if (topNode.value !== null) {
var spacer ="";
for (var i=0; i<depth; i++) {
spacer += "+";
}
console.log(spacer + topNode.value);
}
}
- 例: スーパーの行列
- 最初に並んだ人が最初に処理される
- First in First out
キーボードの動作（a, b, cのキーを連続で叩くと順番に処理される）(非同期に動作する）
- せんべいの缶
- 最初に入った人が最後にでる
- First in Last out
undo（やり直し）で使われる