【背景】
回文是指正读反读均相同的字符序列，如“abba”和"abdba"均是回文，但"good"不是回文。试写一个算法判定给定字符序列是否回文。
【源码运行环境】
操作系统：Windows 10
编译环境：Dev C++(基于C99标准）
【思路】
1、利用栈的后进先出特性。
2、让字符串一半进栈。
3、将字符串后半部分与栈中元素出栈顺序依次对比。
3.1 对比出两字符不同，直接返回FALSE。
4、返回TURE。
【源码实现】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 | #include <stdio.h>#define SIZE 20 /** 结构体：stack* 作用： 定义一个栈，并封装相应的操作* Author: WellLee* Last Modified: 2018-12-13 13:02:20 */ typedef struct stack{ char *elems; int top; int size;}Stack;/**方法名：InitStack*作用：初始化栈 *参数：栈指针 s ; *返回值：void*Author: WellLee*Last Modified: 2018-12-13 13:03:33*/ void InitStack(Stack *s){ //s = (Stack *)malloc(sizeof(Stack)); s->elems = (char *)malloc(SIZE * sizeof(char)); s->size = SIZE; s->top = -1;}/**方法名：Push*作用：元素入栈 *参数：栈指针 s ，字符元素 e ; *返回值：void*Author: WellLee*Last Modified: 2018-12-13 13:03:33*/ void Push(Stack *s, char e){ if(s->top+1 == s->size) { printf("栈满\n"); return ; } s->elems[++s->top] = e;}/**方法名：Pop*作用：元素出栈 *参数：栈指针 s , 字符元素指针 e; *返回值：void*Author: WellLee*Last Modified: 2018-12-13 13:03:33*/ void Pop(Stack *s, char *e){ if(s->top == -1) { printf("栈空\n"); return ; } *e = s->elems[s->top--];}/**方法名：PopAll*作用：栈中所有元素出栈并输出 *参数：栈指针 s*返回值：void*Author: WellLee*Last Modified: 2018-12-13 13:03:33*/ void PopAll(Stack *s){ char e; while(s->top != -1) { Pop(s, &e); printf("%c ",e); } printf("\n");}/**方法名：isPalindrome*作用：判断字符串是否为回文 *参数：栈指针 s , 字符元素指针 e; *返回值：0（FALSE） 1(TRUE) *Author: WellLee*Last Modified: 2018-12-13 13:03:33*/ int isPalindrome(char strings[],int length){ Stack s; InitStack(&s); int mid; mid = length / 2; int i; char e; for(i = 0; i < mid; i++) { Push(&s, strings[i]); // 字符串前半部分压栈操作 } if(length % 2 != 0) { i = mid + 1; // 判断字符串长度是否为奇数，奇数跳过最中间的字符，直接从mid+1开始对比 } else { i = mid; } for(; i < length; i++) { Pop(&s, &e); if(strings[i] != e) { return 0; } } return 1;}int main(){ char strings[] = {'a','b','c','c','b','a','e'}; int i = isPalindrome(strings,7); printf("%d \n", i); return 0;} |
【总结】
在现实需求模型应用中，栈占着自己的一席之地。
【参考文献】
-
《数据结构习题解析与实验指导》.李冬梅,张琪.人民邮电出版社