Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
第4回Javascript勉強会@未来会議室(プログラミング超入門) http://otona.connpass.com/event/44234/

第4回Javascript勉強会@未来会議室(プログラミング超入門)

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);
	}
}

キュー(Queue)

  • 例: スーパーの行列
  • 最初に並んだ人が最初に処理される
  • First in First out

キーボードの動作(a, b, cのキーを連続で叩くと順番に処理される)(非同期に動作する)

スタック(Stack)

  • せんべいの缶
  • 最初に入った人が最後にでる
  • First in Last out

undo(やり直し)で使われる

次回

オブジェクト

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment