文档介绍：数据结构
实验报告
实验题目: 栈序列匹配
班级:信息与计算科学111
姓名: 程倩
学号: 11102105
完成日期:
一、需求分析(说明实验的任务,包括输入、输出、功能、测试数据等)
对于给出的入栈序列和出栈序列,判断这两个序列是否相容。即能否利用栈操作将入栈序列转换为出栈序列。
入栈序列和出栈序列均为不含空格的字符型数据,由键盘输入,其长度不超过10个字符。若入栈序列和出栈序列相容(即能利用栈操作将入栈序列转换为出栈序列),则输出yes,否则输出no。并在判断栈序列的匹配过程中,输出入栈、出栈的过程和栈中的元素。
输入数据的第一行为一个正整数T, 表示测试数据的组数。然后是T组测试数据。每组测试数据的输入是在同一行中用一个空格分隔的两个字符串(其长度均不超过10),依次表示入栈序列和出栈序列。
输出格式为每入栈(或)出栈一次输出一行:push(或pop):c stack:栈顶到栈底的序列,其中c为入栈(或)出栈的字符,最后一行个根据入栈序列和出栈序列是否匹配输出yes或no,匹配则输出yes,否则输出no。
二、概要设计(数据类型的定义、算法思想、主程序和子程序(或功能)模块的说明及各程序模块之间的层次(调用)关系)
算法思路:设置链式栈或顺序栈s,作为入栈序列的栈空间,设置栈顶指针(或下标)。对入栈序列从第一个元素开始考虑入栈,在依次扫描出栈序列元素的过程中进行如下的处理:若栈空且入栈序列有未入栈的元素,则当前入栈序列中的元素入栈,并输出相应的信息;若栈不空且栈顶的元素为出栈序列的当前元素,则栈顶元素出栈,并输出相应的信息,否则,若入栈序列有未入栈的元素,则当前入栈序列中的元素入栈,并输出相应的信息;否则可以确定输入的入栈序列和出栈序列不相容(即不匹配)。
1、栈的抽象数据类型定义
struct stacknode //链式栈s中的结点结构
{
……
};
typedef struct stacknode stacknode,*linkstack;
int push(linkstack *top,char e) 入栈顺序
{
……
}
int pop(linkstack *top, char *e) 出栈顺序
{
……
}
2、判断入栈序列和出栈序列是否匹配
int judge(char a[],char b[])
{
linkstack p=NULL;
……
}
3、列出入栈出栈的顺序
void list(linkstack s)
{
……
}
4、主程序的处理流程
int main() //主函数
{
输入入栈顺序和出栈顺序;
判断入栈和出栈序列是否相容
输出结果
}
三、详细设计(实现概要设计中定义的数据类型,对主程序和其他模块写出算法,说明子模块的调用关系)
struct stacknode //链式栈s中的结点结构
{
char data;
struct stacknode *next;
};
typedef struct stacknode stacknode,*linkstack;
void list(linkstack s);