JavaScriptデータ構造とアルゴリズムの要約2——非線形構造(集合、辞書、散布リスト)

記事の目次

非線形構造

セット

辞書とハッシュリスト

辞書です.

ハッシュリスト

非線形構造
集合する
ES 6は、新しいデータ構造Setを提供する.配列に似ていますが、メンバーの値は全部唯一で、重複した値はありません.
Set自体はSetデータ構造を生成するためのコンストラクターである.
Setクラスを使う:

//Set          （     iterable          ）    ，     。
let set = new Set([1, 2, 3, 4, 4]);

Set.prototype.add:値を追加して、Set構造自体に戻ります.

Set.prototype.delete:ある値を削除し、ブール値を返します.削除が成功したかどうかを表します.

Set.prototype.has:この値がSetのメンバーかどうかを示すブール値を返します.

Set.prototype.clear():全メンバーをクリアし、戻り値がない.

集合は、無秩序で唯一の(つまり重複できない)項目のセットから構成される.
集合する

        //  
        function Set() {
     
            this.dataStore = [];
            this.add = add;// 
            this.remove = remove;// 
            this.size = size;//            
            this.union = union;//  
            this.intersect = intersect;//  
            this.subset = subset;//  
            this.difference = difference;//  
            this.show = show;//      
            this.contains = contains;//             
        }
        //              ，  ，   add()            ，             。   indexOf()                 。    ，                ；      ，      -1。             ，add()                   true；  ，   false。
        function add(data) {
     
            if (this.dataStore.indexOf(data) < 0) {
     
                this.dataStore.push(data); return true;
            } else {
     
                return false;
            }
        }
        function remove(data) {
     
            var pos = this.dataStore.indexOf(data);
            if (pos > -1) {
     
                this.dataStore.splice(pos, 1);
                return true;
            } else {
     
                return false;
            }
        }
        function size() {
      return this.dataStore.length }
        function contains(data) {
     
            if (this.dataStore.indexOf(data) > -1) {
     
                return true;
            } else {
     
                return false;
            }
        }
        function union(set) {
     
            var tempSet = new Set();
            for (let i = 0; i < this.dataStore.length; ++i) {
     
                tempSet.add(this.dataStore[i]);
            }
            for (let i = 0; i < set.dataStore.length; ++i) {
     
                if (!tempSet.contains(set.dataStore[i])) {
     
                    tempSet.dataStore.push(set.dataStore[i]);
                }
            }
            return tempSet;
        }
        function intersect(set) {
     
            var tempSet = new Set();
            for (let i = 0; i < this.dataStore.length; ++i) {
     
                if (set.contains(this.dataStore[i])) {
     
                    tempSet.add(this.dataStore[i]);
                }
            }
            return tempSet;
        }
        function subset(set) {
     
            if (this.size() > set.size()) {
     
                return false;
            } else {
     
                for (let i = 0; i < this.dataStore.length; ++i) {
     
                    if (!set.contains(this.dataStore[i])) {
     
                        return false;
                    }
                }
            }
            return true;
        }
        function difference(set) {
     
            var tempSet = new Set();
            for (let i = 0; i < this.dataStore.length; ++i) {
     
                if (!set.contains(this.dataStore[i])) {
     
                    tempSet.add(this.dataStore[i]);
                }
            }
            return tempSet;
        }
        function show() {
      return this.dataStore; }

        var setA = new Set();
        setA.add(1);
        setA.add(2);
        setA.add(3);
        setA.add(4);
        setA.add(5);
        setA.add(6);
        document.write("setA：", setA.show(), "
");
        if (setA.add(3)) {
     
            document.write("Add success 
");
        } else {
     
            document.write("Add faild,can't add 3 
");
        }
        let re1 = 6;
        if (setA.remove(re1)) {
     
            document.write(" removed ", re1, " 
");
        }
        else {
     
            document.write("no ", re1, " 
");
        }
        let re2 = 7;
        if (setA.remove(re2)) {
     
            document.write(" removed ", re2, " 
");
        }
        else {
     
            document.write("no ", re2, " 
");
        }
        var setB = new Set();
        setB.add(1);
        setB.add(3);
        setB.add(5);
        setB.add(7);
        document.write("setB：", setB.show(), "
");
        
        var AB = setA.union(setB);
        document.write("union:", AB.show(), "
");
        var AB = setA.intersect(setB);
        document.write("intersect:", AB.show(), "
");

        if (setA.subset(setB)) {
     
            document.write("setA is a subset of setB.
");
        }
        else {
     
            document.write("setA is not a subset of setB.
");
        }
        var diff = setA.difference(setB);
        document.write("complementary set:",diff.show());

辞書とフリーリスト
ES 6は、Mapデータ構造を提供する.オブジェクトに似ていて、キーパッドのペアの集合でもありますが、キーの範囲は文字列に限られず、各種の値(オブジェクトを含む)はキーとして使用できます.つまり、Object構造は「文字列ー値」の対応を提供し、Map構造は「値ー値」の対応を提供し、より完璧なHash構造の実現である.もしあなたが「キーペア」のデータ構造が必要ならば、MapはObjectよりもっと適しています.
mapクラスを使う:

		const map = new Map([
		  ['name', '  '],
		  ['title', 'Author']
		]);

		let obj = {
     "a":1, "b":2};
		let map = new Map(Object.entries(obj));

size属性は、Map構造のメンバー総数

に戻る.

set方法では、現在のMapオブジェクトを返すため、チェーン式の書き方を採用することができる

.

get方法は、keyに対応するキーの値を読み取り、keyが見つからなければundefined

に戻る.

has方法は、現在のMapオブジェクトの中にあるキーが

であるかどうかを示すブール値を返します.

delete方法は、あるキーを削除して、trueに戻ります.削除に失敗した場合、false

に戻ります.

clear方法は、全メンバーをクリアし、戻り値

がない.
字典
辞書には、キーと値のペアが記憶されていますが、キー名は特定の要素を問い合わせるためのものです.

        function Dictionary() {
     
            this.add = add;
            this.datastore = new Array();
            this.find = find;
            this.remove = remove;
            this.showAll = showAll;
            this.count = 0;
            this.clear=clear;
        }

        //add()，      ：   。          。
        function add(key, value) {
     
            this.datastore[key] = value;
            this.count++;
        }

        //find(),      ，        。 
        function find(key) {
     
            return this.datastore[key];
        }

        //delete    Object      ，           。               。
        function remove(key) {
     
            delete this.datastore[key];
            this.count--;
        }

        function showAll() {
     
            for (let key in this.datastore) {
     
                document.write(key,":", this.datastore[key], " ");
            }

        }

        function clear() {
     
            for (let key in this.datastore) {
     
                delete this.datastore[key];
            }
            this.count=0;
        }
        var dictA = new Dictionary();
        dictA.add("Mike", "1");
        dictA.add("David", "3");
        dictA.add("Jack", "5");
        document.write("David's extension: ", dictA.find("David"), "
");
        document.write("Number: ", dictA.count, "
");
        dictA.showAll();
        document.write("
");
        dictA.remove("David");
        document.write("Number: ", dictA.count, "
");
        dictA.showAll();
        document.write("
");
        dictA.clear();
        document.write("Number: ", dictA.count, "
");

フリーリスト
ハッシュアルゴリズムの役割は、できるだけ速くデータ構造にある値を見つけることである.
ハッシュ関数の選択は、キーのデータタイプに依存します.キーが整数である場合、一番簡単なハッシュ関数は配列の長さでキーの残りを取ります.
衝突を避けるためには、まず、ハッシュリストにデータを格納するための配列のサイズが素数であることを確認する必要があります.この点は重要です.これはハッシュ値を計算する時に使う剰余計算と関係があります.配列の長さは100以上であるべきで、これはデータを分散リストにおいてより均一に分布させるためである.

        function HashTable() {
     
            this.table = new Array(137);
            this.simpleHash = simpleHash;
            this.hornerHash = hornerHash;
            this.showDistro = showDistro;
            this.put = put;
            //this.get = get; 
        }

        function hornerHash(string) {
     
            const H = 37;
            var total = 0;
            for (var i = 0; i < string.length; ++i) {
     
                total += H * total + string.charCodeAt(i);
            }
            total = total % this.table.length;
            if (total < 0) {
     
                total += this.table.length - 1;
            }
            return parseInt(total);
        }

        function simpleHash(data) {
     
            var total = 0;
            for (var i = 0; i < data.length; ++i) {
     
                total += data.charCodeAt(i);
            }
            print("Hash value: " + data + " -> " + total);
            return total % this.table.length;
        }
        function put(data) {
     
            var pos = this.hornerHash(data);
            this.table[pos] = data;
        }

        function showDistro() {
     
            var n = 0;
            for (var i = 0; i < this.table.length; ++i) {
     
                if (this.table[i] != undefined) {
     
                    document.write(i ,": " ,this.table[i],"
");
                }
            }
        }


        var someNames = ["David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
        var hTable = new HashTable();
        for (var i = 0; i < someNames.length; ++i) {
     
            hTable.put(someNames[i]);
        }
        hTable.showDistro();

ハッシュ関数が複数の入力に対して同じ出力を生成すると衝突が発生する.
衝突が起こると、私たちは依然としてキーをハッシュアルゴリズムによって生成されたインデックス位置に格納することを望んでいるが、実際には、複数のデータを1つの配列要素に格納することは不可能である.チェーンオンとは、ハッシュを実現するための下の配列の中で、各配列要素はまた別の配列のような新しいデータ構造であり、複数のキーを格納することができます.この技術を使うと、2つのキーがハッシュした後の値が同じでも、同じ位置に保存されます.ただし、それらは第2の配列の中の位置が違っています.
第二の処理衝突の方法は線形検出法である.線形探知法はより一般化されたハッシュ技術に従属する.衝突が発生した場合、線形検出法は、発散リストの次の位置が空かどうかを調べます.空の場合は、データをその場所に保存します.空でない場合は、次の位置を確認し続けます.空の位置が見つかるまで.この技術は、各ハッシュテーブルには多くの空きセルがあり、それらを使ってデータを格納することができるという事実に基づいている.