实验3-栈的链式存储及应用.doc

实验三 栈的链式存储及应用一、实习目的1. 理解栈的概念和特点。2. 掌握栈这种数据结构特性及其主要存储结构。3. 在现实生活中灵活运用栈这种数据结构。 二、实验内容 完成下面内容1、 链栈的存储和基本操作：初始化、出栈、入栈、取栈顶元素、输出栈中元素2、假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个判别表达式中括号是否正确配对的函数，并设计一个测试主函数。算法思想： 算术表达式中右括号和左括号匹配的次序正好符合后到的括号要最先被匹配的“后进先出”堆栈操作特点，因此可以借助一个堆栈来进行判断。括号匹配共有四种情况：（1）左右括号配对次序不正确；（2）右括号多于左括号；（3）左括号多于右括号； （4）左右括号匹配正确。 要求：实验后用专用实验纸书写报告。报告中要说明实验题目，内容；分析实验过程，总结实验结果。三、 设计指导1、链栈1）结点的定义#include#include#includetypedef int DataType;typedef struct nodeDataType data;struct node *next;StackNode,*LinkStack;2) 部分函数/堆栈初始化LinkStack InitStack()return NULL;/入栈LinkStack PushStack(LinkStack L,int x)/请大家在自己完成/出栈LinkStack PopStack(LinkStack L,int e)/请大家在自己完成/显示栈中元素void VisitStack(LinkStack L)/请大家在自己完成/取栈顶元素int StackTop(LinkStack L,int e)/请大家在自己完成void main() int i,e; LinkStack L; L=InitStack(); /构造空栈 while(1) printf(*堆栈*n); printf(1 入栈 2 出栈 3 显示栈中元素 4 取栈顶元素 0 返回n); printf(*n); scanf(%d,&i); switch(i) case 1: printf(入栈元素的值为：); scanf(%d,&e);L=PushStack(L,e);break; case 2: L=PopStack(L,e);break;case 3: printf(栈中元素自栈顶至栈底为:n); VisitStack(L) ; break;case 4: printf(栈顶元素为:%-6dn,StackTop(L,e);break;case 0: exit(0);default: printf(输入错误，请重新选择!n); 2、括号匹配问题算法思想： 算术表达式中右括号和左括号匹配的次序正好符合后到的括号要最先被匹配的“后进先出”堆栈操作特点，因此可以借助一个堆栈来进行判断。括号匹配共有四种情况：（1）左右括号配对次序不正确；（2）右括号多于左括号；（3）左括号多于右括号； （4）左右括号匹配正确。 #include#include#include#define MaxStackSize 100typedef char DataType;typedef struct DataType stackMaxStackSize; int top; SeqStack;/1）初始化StackInitiate(S)void StackInitiate(SeqStack *S) S-top = 0;/（2）非空否StackNotEmpty(S)int StackNotEmpty(SeqStack S) if(S.top top = MaxStackSize) printf(堆栈已满无法插入! n); return 0; else S-stackS-top = x; S-top +; return 1; /（4）出栈StackPop(S, d)int StackPop(SeqStack *S, DataType *d) if(S-top top -;*d = S-stackS-top; return 1; /（5）取栈顶数据元素StackTop(SeqStack S, DataType *d)int StackTop(SeqStack S, DataType *d) if(S.top = 0) printf(堆栈已空! n); return 0; else *d = S.stackS.top - 1; return 1; void ExpIsCorrect(char exp, int n) SeqStack myStack; int i; char c; StackInitiate(&myStack); for(i = 0; i n; i+) if(expi = () | (expi = ) | (expi = )StackPush(&myStack, expi); else if(expi = )&StackNotEmpty(myStack)& StackTop(myStack,&c) & c = () StackPop(&myStack, &c); else if(expi = ) & StackNotEmpty(myStack)& StackTop(myStack, &c) & c != () printf(左右括号配对次序不正确！n); return; else if(expi = & StackNotEmpty(myStack)& StackTop(myStack, &c) & c = )StackPop(&myStack, &c); else if(expi = & StackNotEmpty(myStack)& StackTop(myStack, &c) & c != ) printf(左右括号配对次序不正确！n);return;else if(expi = & StackNotEmpty(myStack)& StackTop(myStack, &c) & c = )StackPop(&myStack, &c); else if(expi = & StackNotEmpty(myStack)& StackTop(myStack, &c) & c != ) printf(左右括号配对次序不正确！n); return;else if(expi = ) | (expi = ) | (expi = )& !StackNotEmpty(myStack) printf(右括号多于左括号！n); return; if(StackNotEmpty(myStack) printf(左括号多于右括号！n);else printf(左右括号匹配正确！n); void main(void) Se