【算法】回文数的判断--栈的使用

悠悠 2022-06-14 09:24 181阅读 0赞

“回文”是指正读反读都能读通的句子，它是古今中外都有的一种修辞方式和文字游戏，如“我为人人，人人为我”等。在数学中也有这样一类数字有这样的特征，成为回文数（palindrome number）。

设n是一任意[自然数][Link 1]。若将n的各位数字反向排列所得自然数n1与n相等，则称n为一回文数。例如，若n=1234321，则称n为一回文数；但若n=1234567，则n不是回文数。

“ xyzyx”是一个回文字符串，所谓回文字符串就是指正读反读均相同的字符序列，如“席主席”、“记书记”、“ aha”和“ ahaha”均是回文，但“ ahah”不是回文。通过栈这个数据结构我们将很容易判断一个字符串是否为回文。

代码实现：

#define _CRT_SECURE_NO_DEPRECATE
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    void Palindrome(char * arr1, char *arr2)
    {
    	int i, len, mid, next, top;
    	printf("请输入：\n");
    	gets(arr1);
    	len = strlen(arr1);
    	mid = len / 2 - 1;
    
    	top = 0;
    	for (i = 0; i <= mid; i++)
    	{
    		arr2[++top] = arr1[i];
    	}
    
    	if (len%2 == 0)
    	{
    		next = mid + 1;
    	}
    	else
    	{
    		next = mid + 2;
    	}
    	for (i = next; i <= len - 1; i++)
    	{
    		if (arr1[i] != arr2[top])
    		{
    			break;
    		}
    		top--;
    	}
    
    	if (top == 0)
    	{
    		printf("%s是回文数！\n",arr1);
    	}
    	else
    	{
    		printf("%s不是回文数\n", arr1);
    	}
    }
    
    int main()
    {
    	char arr1[101];
    	char arr2[101];
    	Palindrome(arr1, arr2);
    	system("pause");
    	return 0;
    }

运行结果：  
![Center][]

![Center 1][]

![Center 2][]

![Center 3][]

[Link 1]: http://baike.sogou.com/lemma/ShowInnerLink.htm?lemmaId=213727&ss_c=ssc.citiao.link
[Center]: /images/20220614/575d368ac1034b22871cadd2f4b2d884.png
[Center 1]: /images/20220614/1913c25e897245c796100fb69a58794e.png
[Center 2]: /images/20220614/9acbcc8e177e4d7db09b4c527545e595.png
[Center 3]: /images/20220614/5bb00d271bab48e9a634eafd00ea973d.png