黑马程序员技术交流社区

标题: 探讨回文的多种解法 [打印本页]
作者: 欧玉斌    时间: 2012-10-28 00:12
标题: 探讨回文的多种解法
本帖最后由 幻想领域 于 2012-10-28 00:18 编辑

上半年参加c语言比赛，接触了一些的常见算法，其中比较常见的就是求回文了。
回文：称正读和反读都相同的字符序列为“回文”，如“abba”、“abccba”、12321、123321是“回文”，“abcde”和“ababab”则不是“回文”。
一般可以用栈、队列等方式来解决(关于栈、队列的区别，大家也可以讨论一下，最好能简洁生动)。
下面我想出的几种算法，大家看看还没有其他更好的办法么？
（大半夜发贴不容易，版主记得加分哈，发帖除了为了挣积分，也是为五期交流区挣人气，大家积极发帖答题，别让五期人气低）
这是c语言的解法，主要是将数组元素反序输出：
  1. #include<stdio.h>
  2. #include<string.h>

  4. int main(void)
  5. {
  6. char str[100];
  7. int i, len;
  8. printf("please input string");
  9. gets(str);
  10. len = strlen(str);
  11. for (i = 0; i < len / 2; i++)
  12. {
  13. if (str[i] != str[len-1-i])
  14. {
  15. break;
  16. }
  17. }
  18. if (i == len / 2)
  19. {
  20. printf("%s is huiwen\n", str);
  21. }
  22. else
  23. {
  24. printf("%s not is huiwen\n", str);
  25. }

  27. getchar();
  28. }
复制代码
下面是C#的第一种解法，将原数组逆向存放到另一数组，然后进行对比：
  1. // --------------- 算法一：根据数组元素----------------------------
  2. Console.WriteLine("算法1：请输入一个字符串！");
  3. string str1 = Console.ReadLine();
  4. StringBuilder a = new StringBuilder();//声明一个可变的字符，用于逆向存放sString里的元素
  5. //逆向存放sString里的元素
  6. for (int i = str1.Length - 1; i >= 0; i--)
  7. {
  8. a.Append(str1[i]);//循环附加
  9. }

  11. if (str1.Equals(a.ToString()))//Equals用于判定两对象是否具有相同值
  12. Console.WriteLine("是回文");
  13. else
  14. Console.WriteLine("不是回文");
复制代码
这是c#的第二种算法：
  1. // ------------------算法二:利用栈先进后出，队列先进先出的特点----------------
  2. //abba
  3. Console.WriteLine("算法2：请输入一个字符串！");
  4. //调用.net里面自带的Queue,Stack,并初始化
  5. Queue<char> queue = new Queue<char>();
  6. Stack<char> stack = new Stack<char>();
  7. string str2 = Console.ReadLine(); //获取输入字符
  8. for (int i = 0; i < str2.Length; ++i) //放入栈和队列
  9. {
  10. queue.Enqueue(str2[i]);
  11. stack.Push(str2[i]);
  12. }

  14. IsHuiWen(queue, stack);
复制代码
IsHuiWen的方法是我自己写的：
  1. //检验函数，只需要检验1/2的位置，因为只需要检测前半部分和后半部分是否相同。
  2. static void IsHuiWen(Queue<char> queue, Stack<char> stack)
  3. {//aabb /abbaa
  4. //abcd
  5. // abbba
  6. int i = 0, total = 0;
  7. bool isHuiWen = true;
  8. //确定所要取出的字数,分奇数偶数两种情况
  9. if (queue.Count % 2 == 0)
  10. total = queue.Count / 2;
  11. else
  12. total = queue.Count / 2 + 1;
  13. //通过循环比对出栈元素和出队元素是否相同
  14. while (queue.Count != 0 && stack.Count != 0)
  15. {
  16. if (queue.Dequeue() != stack.Pop()) //不相等
  17. {
  18. isHuiWen = false;
  19. break;
  20. }
  21. else if (i == total) //检查到一半时，跳出循环
  22. break;
  23. ++i;
  24. }

  26. if (!isHuiWen)
  27. Console.WriteLine("这不是回文");
  28. else
  29. Console.WriteLine("这是回文");
  30. }
复制代码
C#第三种解法：
  1. //--------------------------算法三：-----------

  3. Console.WriteLine("算法3：请输入一个字符串！");
  4. string str3 = Console.ReadLine();
  5. string s=null;
  6. //将str3压入栈中
  7. for (int i = 0; i < str3.Length; ++i)
  8. {
  9. stack.Push(str3[i]);
  10. }
  11. //循环将栈元素放入s中
  12. while (stack.Count>0)
  13. {
  14. s +=stack.Pop().ToString();
  15. }

  17. if (str3!= s)
  18. {
  19. Console.WriteLine("这不是回文");
  20. }
  21. else{ Console.WriteLine("这是回文");}
  22. Console.ReadLine();
复制代码
希望大家能贴出更多回文解法。





作者: 杨深    时间: 2012-10-28 02:58
栈（stack）是一种特殊的线性表。如洗碗，在通常情况下，最先冼净的碗总是放在最底下，后冼净的碗总是摞在最顶上。而在使用时，却是从顶上拿取，也就是说，后冼的先取用，后摞上的先取用。好比我们把冼净的碗“摞上”称为进栈，把“取用碗”称为出栈，那么，上例的特点是：后进栈的先出栈。然而，摞起来的碗实际上是一个表，只不过“进栈”和“出栈”，或者说，元素的插入和删除是在表的一端进行而已。
队列(Queue)也是线性表的一种特殊情况，但它与栈不同，其所有的插入均限定在表的一端进行，而所有

的删除则限定在表的另一端进行。允许插入的一端称队尾(Rear)，允许删除的一端称队头(Front)。队列

的结构特点是先进队的元素先出队。假设有队列Q=（a1, a2，a3，…，an），则队列Q中的元素是按a1,

a2，a3，…，an的次序进队，而第一个出队的应该是a1，第二个出队的应该是 a2，只有在ai-1出队以后

，ai才可以出队（1≤i≤n）。因此，通常又把队列叫做先进先出（FIFI—First In First Out）表。再

一句话总结：
栈（数据结构）：后进先出
队列：先进先出
作者: 许庭洲    时间: 2012-10-28 08:05
三个C#判断回文方法值得学习ing!



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2