js書き込みデータ構造(1)一方向チェーン表

4174 ワード

最近見た本の名前は「Javascritデータ構造とアルゴリズムを勉強する」です.
むずむずしているのを見て、Linked List類の定義を出して、自分でインターフェースの方法を実現しました.
この文章はデータ構造の第一編です.
一方向チェーンの実現
自分は簡単なテストです.間違いがあったら指摘してください.
以下は本から与えられた構造関数の定義です.

function LinkedList() {
    var Node = function(element){ 
      this.element = element;
      this.next = null;
    };
    var length = 0; 
    var head = null; //             。
    this.append = function(element){};
    this.insert = function(position, element){};
    this.removeAt = function(position){};
    this.remove = function(element){};
    this.indexOf = function(element){};
    this.isEmpty = function() {};
    this.size = function() {};
    this.toString = function(){};
    this.print = function(){};
}

インターフェースの説明:
  • apped(element):リストの最後に新しいエントリを追加します.
  • insert(position,element):リストの特定の位置に新しいエントリを挿入する
  • Remove(element):リストから一つを削除します.
  • indexOf:リスト内の要素のインデックスを返します.この要素がリストにない場合は-1
  • に戻ります.
  • removeAt(position):リストの特定の位置から一つを削除します.
  • isEmpty()もしチェーンテーブルに要素が含まれていないなら、trueに戻ります.チェーン長が0より大きいなら、false
  • に戻ります.
  • size():チェーンテーブルに含まれる要素の個数を返します.配列のlength属性と類似しています.
  • toStering():リスト項目にNodeクラスが使われているので、JavaScriptオブジェクトのデフォルトを引き継ぐ
  • を書き換える必要があります.
    Stringメソッドでは、要素の値だけを出力させます.
    function LinkedList() {
        var Node = function(element){ 
          this.element = element;
          this.next = null;
        };
        var length = 0; 
        var head = null; //             。
        this.append = function(element){
            var node = new Node(element);
            if( head == null ){
                head = node;
                length++;
            }else{
                var e = head ;
                for( var i = 0 ; i < length-1; i++ ){
                    e = e.next;
                }
                e.next = node;
                length++;
            }
        };
        this.insert = function(position, element){  
            //position start at 0,not 1;
            var node = new Node(element);
            var e = head ;
            if( position == 0 ){
                node.next = e;
                head = node;
                length++;
                return;
            }
            else if( position <= length  ){  
                for( var i = 0 ; i < position - 1 ; i++ ){
                    e = head.next;
                }
                node.next = e.next;
                e.next = node;
                length++;
                return;
            }
            else if( position > length ){
                console.log("          ,    ");
                return false;
            }
        };
        this.removeAt = function(position){
            if( position < 0 || position >= length ){
                console.log("position     ,       。");
                return false;
            }
            else if( position == 0 ){
                head = head.next;
                length--;
            }else{
                var e = head;
                for( var i = 0 ; i < position - 1 ; i++ ){
                    e = e.next;
                }
                e.next = e.next.next;
            }
        };
        this.remove = function(element){
            //      
          var e = head;
          var j = 0;
          var index = this.indexOf(element);
          this.removeAt(index);
        };
        this.indexOf = function(element){
            var e = head;
            for( var i = 0 ; i < length; i++ ){
                if( e.element == element ){
                    return i;
                }
                e = e.next;
            }
        };
        this.isEmpty = function() {
            if( length > 0 ){
                return false;
            }else{
                return true;
            }
        };
        this.size = function() {
            return length;
        };
        this.toString = function(){
            var e = head;
            while(true){
                console.log(e.element);
                e = e.next;
                if( e == null ){
                    break;
                }
            }
        };
        this.print = function(position){   //        
            var e = head;
            if( position < 0 || position > length){
                console.log("position     ,       。");
                return false;
            }
            for( var i = 0 ; i < length ; i++){
                if( i == position){
                    return e.element;
                }
            }
            e = e.next;
        };
    }