単一チェーンテーブル、双方向リストのアルゴリズムについて

3218 ワード

まずデータ定義の構造を与える
シングルチェーンテーブル
/**
 *   
 */

public class LinkTable {
  public LinkTable next;
  public String name;

  public void setName(String name) {
    this.name = name;
  }

  public LinkTable(String name) {
    this.name = name;
  }
}

1.単一チェーンテーブルの逆順序反転
package zong.xiao.mi.demosource.java;

/**
 * Created by mi on 2017/3/9.
 */

public class        {

  public static void main(String[] a) {
    LinkTable linkTable = LinkTableReverse2(getLinkTable());
    print(linkTable);

  }

  public static LinkTable getLinkTable() {
    LinkTable A = new LinkTable("A");
    LinkTable B = new LinkTable("B");
    LinkTable C = new LinkTable("C");
    LinkTable D = new LinkTable("D");
    LinkTable E = new LinkTable("E");
    A.next = B;
    B.next = C;
    C.next = D;
    D.next = E;
    return A;
  }

  /**     (  )
   *    
   * 1. root next   
      2. root.next   
      3.   newRoot   
      4.  root  head
   * @param root
   */
  public static void LinkTableReverse(LinkTable root) {
    print(root);
    LinkTable newRoot = null;
    while (root != null) {
      LinkTable next = root.next;
      root.next = newRoot;
      newRoot = root;
      root = next;
    }
    print(newRoot);
  }

  /**
   *                          ,
   *  root.next.next=root    root.nex=null;
   * 
   * @param root
   * @return
   */
  public static LinkTable LinkTableReverse2(LinkTable root) {
    LinkTable newRoot = null;

    if (root == null || root.next == null) {
      return root;
    }
    newRoot = LinkTableReverse2(root.next);
    root.next.next = root;
    root.next = null;
    return newRoot;

  }

シングルチェーンテーブル隣接ノード反転A-B-C-D出力B-A-D-C
/**
   *          
   *   A-B-C-D-E  B-A-D-C-E
   * 
   * @param root
   * @return
   */
  public static LinkTable borderReverse(LinkTable root) {

    if (root == null || root.next == null) return root;
    LinkTable curr = root;
    LinkTable next;
    LinkTable pre = null;
    while (curr != null && curr.next != null) {

      if (pre != null) {
        pre.next = curr.next;
      } else {
        root = curr.next;
      }
      pre = curr;
      next = curr.next.next;
      curr.next.next = curr;
      curr.next = next;
      curr = curr.next;
    }
    return root;

  }
  public static void print(LinkTable root) {
    while (root != null) {
      System.out.print(root.name);
      System.out.print("--");
      root = root.next;
    }
    System.out.println();
  }
}


にほうこうチェーンテーブル
public class Node {

  public Node pre;
  public Node next;
  public int data;

  public Node(Node pre, Node next, int data) {
    this.pre = pre;
    this.next = next;
    this.data = data;
  }

  public static void printNode(Node node) {
    Node n = node;
    while (n != null) {
      System.out.println(n.data);
      n = n.next;
    }

  }
}

双方向チェーンテーブルの反転
 public Node reverse(Node node) {
    Node n = node, pre = null;
    while (n != null) {
      Node next = n.next;
      n.next = pre;
      n.pre = next;
      pre = n;
      n = next;
    }
    return pre;
  }