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
You can’t perform that action at this time.