クラシックケース-回文シーケンスJava String(Char)ストレージ実装シングルチェーンテーブルストレージ実装
2391 ワード
一連の数字や文字列が返信されるかどうかを判断することは、プログラミングの基本的な問題です.ここでは、データ構造に関する最近の知識に基づいて、java言語で2つの古典的なケースを実現します.
1.Stringにより文字列を格納し、返信文字列であるか否かを判定する.
この解決は比較的簡単で,iとjはそれぞれStringの前後から遍歴して比較して回文文字列であるか否かを得る.
2.単一チェーンテーブルを用いて文字列を格納し、単一チェーンテーブルの性質を用いて返信チェーンテーブルであるか否かを得る方法
これはとても面白いテーマで、単鎖表の応用を学ぶdemoでもあります.単一チェーンテーブルは線形テーブルの典型であることを知っています.論理的に隣接するデータ構造は、物理的に不連続なメモリアドレスで格納できます.削除要素を挿入する時間は複雑ですが、配列のようにランダムアクセスをサポートすることはできません.
回文シーケンスという問題に戻ると,単一チェーンテーブルの特殊な性質のため,データアクセスは単一チェーンテーブルのヘッダノードからのみ,チェーンテーブルノードのnextポインタに沿って逐次下遍歴できる.そこでここでは,クイックインスローインの2つのポインタを巧みに利用し,headノードから遍歴し,ポインタn 1を1回,ポインタn 2を1回2回行う.n 2が指す次が空の場合、n 1は現在チェーンテーブルの中間ノードを指す.その後,後半のノードは逆順に復元され,前後半のノードが比較して回文の有無が得られる.
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