一方向チェーンテーブル反転(図解を含む)

8214 ワード

前言
前回は一方向チェーンテーブルの原理「Java実現一方向チェーンテーブル機能」について説明しましたが、今日はチェーンテーブルの反転を実現するための拡張を行います.次は直接コードをつけます.
チェーンテーブルの初期化
public class LinkedArray<T extends Number>{

    //      
    private Entry head;

    //     
    static final class Entry<T>{
        //            
        Entry next;
        T t;
        public Entry(T t) {
            // TODO Auto-generated constructor stub
            this.t = t;
        }
    }
}

ノードの追加
 public void add(T t) { 
    //          
    Entry entry = new Entry(t);
    //      ,  head  
    if(head == null) {
        head = entry;
    }else {
        //    ,    ,  head       entry
        entry.next = head;
        head = entry;
    }
}

追加されたプロシージャは、コードコメントと次の画像を組み合わせています.
チェーンテーブル反転
public void reverse() {
    ///  current    head       。
    Entry current = head.next;

    //  head.next  current,(   head      ,  next  )
    head.next = null;   
    while(current != null) {
        //  currentNext    currentNext       。
        Entry currentNext = current.next;
        //current.next          
        current.next = head;
        //  head current  ,   head       
        head = current; 
        current = currentNext;
    }       
}

反転のプロセスは、コードコメントと次の画像を組み合わせます.
チェーンテーブル全体の挿入および反転は実現されますが、チェーンテーブル内の要素の順序は挿入の順序であり、要素の実際の数値の大きさに従ってソートされていないことに注意してください.次の拡張インプリメンテーション挿入はソートされます.
ナチュラルシーケンス挿入
本論文では,Numberタイプの順序配列のみについて論じる

public void addByOrder(T t) {   
    //          
    Entry entry = new Entry(t);
    //      ,  head  
    if(head == null) {
        head = entry;
    }else {
        // head  ,      ,
        //current     ,previous current      
        Entry current = head;
        Entry previous = head;

        //      ,    current    (       )
        //           current 
        while(current != null && t.doubleValue()>current.t.doubleValue()) {
            //    
            previous = current;
            current = current.next;
        }

        //      head    ,
        //         head (  current == previous,current       )
        if(current == previous) {
            entry.next = head;
            head = entry;
        }else {
            //       , previous current     
            previous.next = entry;
            entry.next = current;
        }   
    }
}

追加されたプロシージャは、コードコメントと次の画像を組み合わせています.
実行結果
メイン関数はランダムに10個の数字を入力し、ソートとソートしない場合をテストします.
public static void main(String[] args) {
        // TODO Auto-generated method stub  
         add();
         System.out.println("-------------   -----------");
         addByOrder();
    }

    private static void add() {
        LinkedArray list = new LinkedArray<>();
        list.add(3);
        list.add(4);
        list.add(8);
        list.add(6);
        list.add(9);
        list.add(2);
        list.add(1);
        list.add(5);
        list.add(0);
        list.add(7);

        System.out.println(list.findAll());
        list.reverse();
        System.out.println(list.findAll());
    }

    private static void addByOrder() {
        LinkedArray list = new LinkedArray<>();
        list.addByOrder(3);
        list.addByOrder(4);
        list.addByOrder(8);
        list.addByOrder(6);
        list.addByOrder(9);
        list.addByOrder(2);
        list.addByOrder(1);
        list.addByOrder(5);
        list.addByOrder(0);
        list.addByOrder(7);

        System.out.println(list.findAll());
        list.reverse();
        System.out.println(list.findAll());
    }

実行結果
総計
ノードの挿入,ノードの順次挿入,反転の機能について述べた.チェーンテーブルはポインタの移動を重点的に理解する必要があります.その他のワンウェイチェーンテーブル機能については、「Javaワンウェイチェーンテーブル機能の実装」を参照してください.
ワンウェイチェーンテーブルの機能実装はここで終わります.
作者のレベルが限られているため、もし間違いがあれば皆さんの指摘を歓迎します.
Demoコードのダウンロード