数据结构题集-第三章-栈和队列-识别特定回文序列

说明

• 本文参照严蔚敏《数据结构(C语言版)题集》一书中包含的问答题和算法设计题目，提供解答和算法的解决方案。
• 请读者在自己已经解决了某个题目或进行了充分的思考之后，再参考本解答，以保证复习效果。
• 由于作者水平所限，本解答中一定存在不少这样或者那样的错误和不足，希望读者们在阅读中多动脑、勤思考，争取发现和纠正这些错误，写出更好的算法来。

3.17 试写一算法

识别依次读入的一个以@为结束符的字符序列是否为形如’序列₁&序列₂‘模式的字符序列。
其中序列₁和序列₂中都不含字符’&'，
且序列₂是序列₁的逆序列。
例如，'a+b&b+a’是属于该模式的字符序列，而’1+3&3-1’则不是。

解：
在写算法之前，应先分析清楚不符合给定模式的几种情况。
注意题中给出的条件：模式串中应含字符’&‘，则不含字符’&'的字符序列与模式串也不匹配。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define STACK_SIZE 22
#define HALF_SIZE 10
#define MAX_TEST_LENGTH 23
#define MAX_TEST_ELEM 100

typedef char ElemType;

ElemType space[STACK_SIZE];

typedef struct{
	int top;
} Stack;

void init_stack(Stack *ps){
	ps->top=0;
}

void push(Stack *ps,ElemType e){
	if(ps->top>=STACK_SIZE) return;
	space[ps->top++]=e;
}

void pop(Stack *ps,ElemType *pe){
	if(ps->top<=0) return;
	*pe=space[--ps->top];
}

void print_space(Stack s){
	int i;
	for(i=0;i<STACK_SIZE;i++){
		if(i==s.top)
			printf("[");
		printf("%c",space[i]);
		if(i==s.top)
			printf("]");
	}
	printf("\n");
}

int stack_empty(Stack s){
	return !s.top;
}

int is_reverse(Stack *ps,ElemType *str){
	//判断输入的字符串中'&'前和'&'后部分是否为逆串,是则返回1,否则返回0
	ElemType ch;
	int i=0;
	while(str[i]!='&'){
		if(str[i]=='@') return 0;
		push(ps,str[i++]);
	}
	while(str[++i]!='@'){
		if(stack_empty(*ps)) return 0;
		pop(ps,&ch);
		if(ch!=str[i]) return 0;
	}
	if(i>1&&!stack_empty(*ps)) return 0;
	return 1;
}

void rand_test_reverse(){
	int i,c;
	Stack s;
	time_t t;
	ElemType ch;
	ElemType str[MAX_TEST_LENGTH];
	init_stack(&s);
	srand((unsigned)time(&t));
	
	i=0;
	c=rand()%(HALF_SIZE+1);
	for(i=0;i<c;i++){
		do{
			ch=(ElemType)((rand()%MAX_TEST_ELEM)+25);
		}while(ch=='&'||ch=='@');
		str[i]=ch;
		str[2*c-i]=ch;
	}
	str[i]='&';
	str[2*c+1]='@';
	str[2*c+2]='\0';
	
	printf("%s\n",str);
	if(is_reverse(&s,str))
		printf("The same as reversed string split by & and end by @.\n");
}

int main(){
	rand_test_reverse();
	return 0;
}

这里测试只给出了随机符合序列的例子。