利用栈简单实现回文串判断
题目:编程实现程序,相关功能包括:输入一串字符,使用单链表进行存储,然后设计算法通过数据结构栈来帮助判断上述已知单链表中字符序列是否为回文,如果是,则输出“此链表中的字符序列构成回文”,否则输出“此链表中的字符序列不构成回文”。
注:回文模式即字符序列为中心对称,如 abccba 和 abcdcba 都是回文。
思路:利用单链表与栈的特点,实现回文串的判断.
// 创建字符节点 public class Node { char data; Node next; public Node() { } public Node(char t){ this.data=t; } @Override public String toString() { return "Node{" + "data=" + data + }; } }
// 创建一个简单栈 public class Stack { Node base; Node top; public void push(Node node) { Node temp = new Node(); temp.data = node.data; temp.next = top; top = temp; } public boolean isEmpty() { return base == top; } public Node peek() { return top; } public Node pop() { if (this.isEmpty()) { System.out.println("退栈失败,栈为空!"); return null; } Node temp = new Node(); temp = top; top = top.next; return temp; } }
public class InputString { static { System.out.println("请输入字符串"); } static Scanner scanner = new Scanner(System.in); static String in = scanner.nextLine(); static char[] chars = in.toCharArray(); static Node head = null; static Stack stack = new Stack(); // 将字符串先用单链表存储 public static void toLinkedList() { Node temp = null; for (int i = 0; i < chars.length; i++) { Node node = new Node(chars[i]); if (i == 0) { head = node; temp = head; } else { temp.next = node; temp = node; } } } // 再将字符串使用栈存储 public static void toLinkedStack() { for (char aChar : chars) { stack.push(new Node(aChar)); } } // 将单链表与栈遍历一半的字符长度,进行匹配. public static boolean judgeHuiWen() { InputString.toLinkedList(); InputString.toLinkedStack(); Node headTemp = head; for (int i = 0; i < ((chars.length) / 2); i++) { if (headTemp.data == stack.top.data) { headTemp = headTemp.next; stack.pop(); } else { return false; } } return true; } public static void isHuiWen() { if (InputString.judgeHuiWen()) { System.out.println("输入的是回文"); } else { System.out.println("输入不是回文"); } } }
public class TestHuiWen { public static void main(String[] args) { InputString.isHuiWen(); } }
没有特别幸运,那么请先特别努力,别因为懒惰而失败,还矫情地将原因归于自己倒霉。