数据结构实验报告1_crystal_node的博客-爱代码爱编程

问题描述：设计算法，判断输入序列12......n的任一排列p1p2…pn是否是栈的正确输出序列。

1.问题分析

栈是一种后进先出的线性表，判断p1p2...pn是否为正确的输出序列，只需看p1p2...pn是否满足后进先出的顺序

2.解题思路及实现过程

建立两个数组in和out存储入栈序列和出栈序列，定义栈s（使用前应先实现栈的基本操作），遍历入栈序列in，将数字压入栈s中，压入数字前应先判断栈顶元素ch是否与当前out数组元素相同，若相同则弹出栈顶元素，out下标后移，继续判断栈顶元素是否与当前out数组元素相同，仍相等则重复以上操作直至不相等，若不相等，则将in数组下标后移。直至in数组遍历完毕。

此时若out数组遍历完成，则out数组中的序列是一种可能的出栈序列，否则不是。

3.解决过程中的bug及解决方法

bug:

Error:expected';',','or')'before'&'token

解决方法：将源代码存为.cpp文件而不是.c文件（据说将&改为*也可行但是我改了之后出现了新bug）

4.实验总结

本次实验帮助我更好的理解了栈后进先出的特点，学会了判断栈输出序列是否合法的算法

5.附录-源代码

#include <stdio.h>  
#include <stdlib.h>
#define ERROR 0
#define OK 1
#define MAX_SIZE 10000
/**********实现栈的基本操作**********/ 
typedef struct NODE{
	int arr[MAX_SIZE];
	int top;
}Node;
void InitStack(Node &s){
	s.top=0;
} 
int Push(Node &s,int c){
	if(s.top==MAX_SIZE) return ERROR;
	s.arr[s.top++]=c;
	return OK;
}
int Pop(Node &s,int &e){
	if(s.top==0) return ERROR;
	e=s.arr[--s.top];
	return OK;
}
int GetTop(Node &s,int &e){
	if(s.top==0) return ERROR;
	e=s.arr[s.top-1];
	return OK;
}
int StackEmpty(Node &s){
	return s.top==0;
}
/**********************************/ 
int Test(int *in,int *out){
	Node s;
	int ch;//栈顶元素 
	InitStack(s);
	while(*in!=0){
		Push(s,*in);//将in中元素压入栈中 
		GetTop(s,ch);//取栈顶元素 
		while(ch==*out){//栈顶元素ch与当前out数组元素相同，弹出栈顶元素，out下标后移 
			Pop(s,ch);
			out++;
			GetTop(s,ch);
		}
		in++;
	}
	if(*out!=0) return 0;//若out数组遍历完成，则out数组中的序列是一种可能的出栈序列，否则不是
	return 1;
}
/******************************/
int main(){
	int in[10000],out[10000];//入栈序列和出栈序列 
	int n,flag;
	printf("输入入栈元素个数:");
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		in[i]=i+1;
	}
	printf("输入出栈序列:");
	for(int i=0;i<n;i++){
		scanf("%d",&out[i]);
	}
	flag=Test(in,out);
	if(flag) printf("TRUE");
	else printf("FALSE");
	return 0; 
}