クラシックケース-回文シーケンスJava String(Char)ストレージ実装シングルチェーンテーブルストレージ実装


一連の数字や文字列が返信されるかどうかを判断することは、プログラミングの基本的な問題です.ここでは、データ構造に関する最近の知識に基づいて、java言語で2つの古典的なケースを実現します.
1.Stringにより文字列を格納し、返信文字列であるか否かを判定する.
この解決は比較的簡単で,iとjはそれぞれStringの前後から遍歴して比較して回文文字列であるか否かを得る.
import java.util.Scanner;

/**
 *   String         
 * @author xjh 2018.10.08
 *
 */
public class ToString {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		String s=sc.nextLine();
		for(int i=0,j=s.length()-1;i

2.単一チェーンテーブルを用いて文字列を格納し、単一チェーンテーブルの性質を用いて返信チェーンテーブルであるか否かを得る方法
これはとても面白いテーマで、単鎖表の応用を学ぶdemoでもあります.単一チェーンテーブルは線形テーブルの典型であることを知っています.論理的に隣接するデータ構造は、物理的に不連続なメモリアドレスで格納できます.削除要素を挿入する時間は複雑ですが、配列のようにランダムアクセスをサポートすることはできません.
回文シーケンスという問題に戻ると,単一チェーンテーブルの特殊な性質のため,データアクセスは単一チェーンテーブルのヘッダノードからのみ,チェーンテーブルノードのnextポインタに沿って逐次下遍歴できる.そこでここでは,クイックインスローインの2つのポインタを巧みに利用し,headノードから遍歴し,ポインタn 1を1回,ポインタn 2を1回2回行う.n 2が指す次が空の場合、n 1は現在チェーンテーブルの中間ノードを指す.その後,後半のノードは逆順に復元され,前後半のノードが比較して回文の有無が得られる.
import java.util.Scanner;

/**
 *              ,       
 * @author xjh 2018.10.08
 *
 */
class Node{	//     
	  char data;
	  Node next;
	 public Node(char t){
		 this.data=t;
	 }	
	 
}
public class ToSingleLinkedList {
	
	public static boolean IsHuiwen(Node head){
		Node n1=head;
		Node n2=head;
//		System.out.println(n2.next.next.data);
		while(n2.next!=null&&n2.next.next!=null){	
//                while           n2.next!=null        ,   n2             n2.next.next
			//     n2  2  n1  1 
			n1=n1.next;
			n2=n2.next.next;
		}//     n2       ,n1        
		
		n2=n1.next;
		Node pre=n1;
		Node next=null;
		while(n2!=null){
			//          
			next=n2.next;
			n2.next=pre;
			pre=n2;
			n2=next;
		}
		
		n1.next=null;
		n2=pre;
		n1=head;
		while(n1.next!=null&&n2.next!=null){
			//                 
			if(n1.data!=n2.data)
				return false;
			n1=n1.next;
			n2=n2.next;
		}
		return true;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in=new Scanner(System.in);
		String tmp=in.nextLine();
		char[] s=tmp.toCharArray();
		
		Node[] node=new Node[s.length];
		for(int i=0;i