データ構造とアルゴリズムのJavaScript記述——チェーンテーブル

データ構造とアルゴリズムのJavaScript記述——チェーンテーブル

： 《 JavaScript 》 。
JavaScriptの配列の主な問題:オブジェクトとして実装され、他の言語に比べて効率が低い.配列が実際の使用中に遅い場合は、チェーンテーブルで置き換えることが考えられます.データへのランダムアクセスに加えて、チェーンテーブルは、1次元配列を使用できる場合にほとんど使用できます.ランダムアクセスが必要な場合、配列は依然としてより良い選択です.

1、オブジェクトベースのチェーンテーブルを定義する

チェーンテーブルは、ノードのセットからなる集合である.各ノードは、オブジェクトの参照でその後続を指します.別のノードへの参照を

と呼ぶ.
1.1ノードクラス

function Node(element){
    this.element=element;
    this.next=null;
}

1.2 LinkListクラス

function LList(){
    this.head=new Node("head");
    this.find=find;
    this.insert=insert;
    this.remove=remove;
    this.display=display;
}

1.3ノードの検索

function find(item){
    var currNode=this.head;
    while(currNode.element!=item){
        currNode=currNode.next;
    }
    return currNode;
}

1.4新規ノードの挿入

function insert(newElement,item){
    var newNode=new Node(newElement);
    var current=this.find(item);//   item        
    newNode.next=current.next;//    next      next
    current.next=newNode;//    next     
}

1.5チェーンテーブルの要素を表示する

function display(){
    var currNode=this.head;//head     
    while(!(currNode.next==null)){
        print(currNode.next.element);
        currNode=currNode.next;
    }
}

1.6チェーンテーブルからノードを削除

ノードを削除するには、削除するノードの前のノードを見つけてから、前のノードのnext属性を削除するノードの次のノードに指さす必要があります.

function findPrevious(item){
    var currNode=this.head;
    while((currNode.next!=null)&&(currNode.next. element!=item)){
        currNode=currNode.next;
    }
    return currNode;//        
}

function remove(item){
    var prevNode=this.findPrevious(item);
    if(!(prevNode.next==null)){
        prevNode.next=prevNode.next.next;
    }
}

1、双方向チェーンテーブル

//  
function Node(element){
    this.element=element;
    this.next=null;
    this.previous=null;
}
//  
function insert(newElement,item){
    var newNode=new Node(newElement);
    var current=this.find(item);
    newNode.next=current.next;
    newNode.previous=current;
    current.next=newNode;
}
//  
function remove(item){
    var currNode=this.find(item);
    if(!(currNode.next==null)){
        currNode.previous.next=currNode.next;
        currNode.next.privious=currNode.previous;
        currNode.next==null;
        currNode.previous=null;
    }
}
//           （       ）
function findLast(){
    var currNode=this.head;
    while(!(currNode.next==null)){
        currNode=currNode.next;
    }
    return currNode;
}
//    
function dispReverse(){
    var currNode=this.findLast();
    while(!(currNode.previous==null)){
        print(currNode.element);
        currNode=currNode.previous;
    }
}
//    n   
function advance(n){

}
//    n   
function back(n){

}
//      
function show(node){

}

1、循環チェーンテーブル

後からチェーンテーブルを巡回したいが、双方向チェーンテーブルを作成するために追加の代価を払う必要がない場合は、ループチェーンテーブルを使用する必要があります.

1.1コンストラクタ

function LList(){
    this.head=new Node("head");
    this.length=0;//       
    this.head.next=this.head;//      
    this.find=find;
    this.insert=insert;
    this.display=display;
    this.findPrevious=findPrevious;
    this.remove=remove;
}

function display(){
    var currNode=this.head;
    while(!(currNode.next==null)&&!(currNode.next.element=="head")){
        print(currNode.next.element);
        currNode=currNode.next;
    }
}