Machine World | Math World

记录实验过程

【数据结构】回文判断程序的C语言实现

【背景】

回文是指正读反读均相同的字符序列,如“abba”和"abdba"均是回文,但"good"不是回文。试写一个算法判定给定字符序列是否回文。

【源码运行环境】

操作系统:Windows 10

编译环境:Dev C++(基于C99标准)

【思路】

1、利用栈的后进先出特性。

2、让字符串一半进栈。

3、将字符串后半部分与栈中元素出栈顺序依次对比。

3.1 对比出两字符不同,直接返回FALSE。

4、返回TURE。

【源码实现】

#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;
}

【总结】

在现实需求模型应用中,栈占着自己的一席之地。

【参考文献】

  • 《数据结构习题解析与实验指导》.李冬梅,张琪.人民邮电出版社

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注