回文判断。称正读与反读都相同的字符序列为回文序列

骑猪看日落 2022-05-24 09:49 136阅读 0赞

试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如“序列1&序列2”模式的字符序列。其中序列1和序列2都不含字符“&”，且序列2是序列1的逆序列。例如，"a+b&b+a"是属该模式的字符序列，而"1+3&3-1"则不是。

通过栈与队列相关内容的学习，我们知道，栈是"先进后出"的线性表，而队列是"先进先出"的线性表。可以通过构造栈与队列来实现在这一算法。将要判断的字符序列依次压栈和入队。然后依次出栈和出队，通过比较出栈的字符序列与出队的字符序列是否相同来判断读入的字符序列是否为回文序列。如果全部相同则是回文序列，否则不是回文序列。

使用**链式栈**和**链式队列**来实现这一算法。

/*检测是否为回文序列*/
    int Check(char *str,LinkStack LS, LinkQueue* LQ)
    {
    	DataType data;
    	DataType elem;
    	int i = 0;
    	/*从键盘依次输入字符以‘@’作为结束标志，将其依次压栈，入队，*/
    	scanf("%c", &str[i]);
        do
    	{
            PushStack(LS, str[i]);    /*将字符序列中的字符依次入栈*/
    		EnterQueue(LQ, str[i]);   /*将字符序列中的字符依次入队*/
    		i++;
    		scanf("%c", &str[i]);
    	} while (str[i] != '@');
    	/*当栈不为空时循环弹栈和出队，如果遇到出栈的元素data与出队的元素不同
    	则不是回文序列,如果站为空，依然没要遇到出队与出栈元素不同则为回文序列*/
    	while (!IsEmpty(LS))
    	{
    		PopStack(LS, &data);     /*将字符序列中的字符依次出栈*/
    		DeleteQueue(LQ, &elem);  /*将字符序列中的字符依次出队*/
    		if (data != elem)
    		{
    			printf("不是回文字符序列!\n");
    			return 0;
    		}
    	}
    	printf("是回文字符序列！\n");
    }

**\*\*源程序\*\***

#include <stdio.h>
    #include <stdlib.h>
    #include <Windows.h>
    #include <assert.h>
    
    #define MaxSize 50      //字符数组的最大长度
    
    typedef char DataType;
    
    /*使用LinkQueueNode定义队列中的结点，使用LStackNode定义链式栈中的节点，
    由于在链式栈的初始化中要改变栈顶指针top的指向，所以需要传二级指针，定义
    一个指针类型LinkStack，使用LinkStack定义指针类型变量，使用LinkStack*定
    义二级指针变量*/
    typedef struct Node
    {
    	DataType _data;              /*结点的数据域*/
    	struct Node* _next;          /*结点的指针域*/
    }LinkQueueNode,LStackNode, *LinkStack;
    
    typedef struct
    {
    	LinkQueueNode* front;      /*队头指针*/
    	LinkQueueNode* rear;       /*队尾指针*/
    }LinkQueue;
    
    /* ********************链栈的相关操作函数************************* */
    
    /*链栈的初始化*/
    
    void InitStack(LinkStack* top)
    {
    	//为头结点开辟一个存储空间
    	*top = (LinkStack*)malloc(sizeof(LStackNode));
    	assert(*top);
    	(*top)->_next = NULL; //将链栈的头结点指针域置为空
    }
    
    /*判断链栈是否为空*/
    int IsEmpty(LinkStack top)
    {
    	if (top->_next == NULL)
    	{
    		return 1;
    	}
    	return 0;
    }
    
    /*进栈操作*/
    
    void PushStack(LinkStack top, DataType data)
    {
    	LStackNode*  pNewNode;
    	pNewNode = (LStackNode*)(malloc(sizeof(LStackNode)));
    	assert(pNewNode);
    	pNewNode->_data = data;
    	pNewNode->_next = top->_next;
    	top->_next = pNewNode;
    }
    
    /*出栈操作*/
    
    int PopStack(LinkStack top, DataType* data)
    {
    	LStackNode* pDel;
    	pDel = top->_next;
    	if (pDel == NULL)
    	{
    		printf("栈为空！\n");
    		return 0;
    	}
    	else
    	{
    		*data = pDel->_data;
    		top->_next = pDel->_next;
    		free(pDel);   //释放p指向的结点
    		return *data;
    	}
    }
    
    /*销毁链栈*/
    void DestoryStack(LinkStack top)
    {
    	LStackNode *p;
    	LStackNode *q;
    	p = top;
    	while (!p)
    	{
    		q = p;          /*q为要释放的结点*/
    		p = p->_next;   /*p指向下一次要释放的结点*/
    		free(q);        /*释放q指向的结点空间*/
    	}
    
    }
    	
    /* ********************链式队列的相关操作函数************************* */
    
    /*初始化队列*/
    void InitLinkQueue(LinkQueue* LQ)
    {
    	//创建一个头结点
    	LinkQueueNode* pHead = (LinkQueueNode*)malloc(sizeof(LinkQueueNode));
    	assert(pHead);
    	LQ->front = LQ->rear = pHead; //队头和队尾指向头结点
    	LQ->front->_next = NULL;
    }
    
    /*入队操作*/
    void EnterQueue(LinkQueue* LQ, DataType data)
    {
    	//创建一个新结点
    	LinkQueueNode* pNewNode = (LinkQueueNode*)malloc(sizeof(LinkQueueNode));
    	assert(pNewNode);
    	pNewNode->_data = data;  //将数据元素赋值给结点的数据域
    	pNewNode->_next = NULL;  //将结点的指针域置空
    	LQ->rear->_next = pNewNode;   //将原来队列的队尾指针指向新结点
    	LQ->rear = pNewNode;      //将队尾指针指向新结点
    }
    
    /*出队操作*/
    
    int DeleteQueue(LinkQueue* LQ, DataType* data)
    {
    	if (LQ->front->_next == NULL)
    	{
    		printf("队列为空！\n");
    		return;
    	}
    	/*pDel指向队头元素，由于队头指针front指向头结点，所以pDel指向头结点的下一个结点*/
    	LinkQueueNode* pDel = LQ->front->_next;
    	*data = pDel->_data;   /*将要出队的元素赋给data*/
    	LQ->front->_next = pDel->_next;  /*使指向头结点的指针指向pDel的下一个结点*/
    	/*如果队列中只有一个元素,将队列置空*/
    	if (LQ->rear = pDel)
    	{
    		LQ->rear = LQ->front;
    	}
    	free(pDel);   /*释放pDel指向的空间*/
    	return *data;
    }
    
    /*销毁链队列*/
    void DestryQueue(LinkQueue* LQ)
    {
    	while (LQ->front != NULL)
    	{
    		LQ->rear = LQ->front->_next;  /*队尾指针指向队头指针的下一个结点*/
    		free(LQ->front);              /*释放队头指针指向的结点*/
    		LQ->front = LQ->rear;         /*队头指针指向队尾指针*/
    	}
    }
    
    ///
    
    /*检测是否为回文序列*/
    int Check(char *str,LinkStack LS, LinkQueue* LQ)
    {
    	DataType data;
    	DataType elem;
    	int i = 0;
    	/*从键盘依次输入字符以‘@’作为结束标志，将其依次压栈，入队，*/
    	printf("请输入字符序列,以@结束:");
    	
    	scanf("%c", &str[i]);
        do
    	{
            PushStack(LS, str[i]);    /*将字符序列中的字符依次入栈*/
    		EnterQueue(LQ, str[i]);   /*将字符序列中的字符依次入队*/
    		i++;
    		scanf("%c", &str[i]);
    	} while (str[i] != '@');
    	/*当栈不为空时循环弹栈和出队，如果遇到出栈的元素data与出队的元素不同
    	则不是回文序列,如果站为空，依然没要遇到出队与出栈元素不同则为回文序列*/
    	while (!IsEmpty(LS))
    	{
    		PopStack(LS, &data);     /*将字符序列中的字符依次出栈*/
    		DeleteQueue(LQ, &elem);  /*将字符序列中的字符依次出队*/
    		if (data != elem)
    		{
    			printf("不是回文字符序列!\n");
    			return 0;
    		}
    	}
    	printf("是回文字符序列！\n");
    }
    
    
    
    int main()
    {
    	LinkStack LS;
    	LinkQueue LQ;
    	char str[MaxSize];
    
    	InitStack(&LS);
    	InitLinkQueue(&LQ);
    	Check(str, LS, &LQ);
    	DestoryStack(LS);
    
    	system("pause");
    	return 0;
    }

**测试结果：**

输入：1+2+3&3-2+1@      输出：不是回文字符序列!
    
    输入：1+2+3&3+2+1@      输出: 是回文字符序列！
    
    输入：a+b&b+a@          输出: 是回文字符序列！
    
    输入：1234554321@       输出：是回文字符序列！
    
    输入：123aba321@        输出：是回文字符序列！
    
    输入：aba@11134         输出：是回文字符序列！
    
    输入：123a321b111@      输出：不是回文字符序列!