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

《实验3-栈的链式存储及应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验三栈的链式存储及应用一、实习目的1.理解栈的概念和特点。2.掌握栈这种数据结构特性及其主要存储结构。3.在现实生活中灵活运用栈这种数据结构。二、实验内容完成下面内容1、链栈的存储和基本操作：初始化、出栈、入栈、取栈顶元素、输出栈中元素2、假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个判别表达式中括号是否正确配对的函数，并设计一个测试主函数。算法思想：算术表达式中右括号和左括号匹配的次序正好符合后到的括号要最先被匹配的“后进先出”堆栈操作特点，因此可以借助一个堆栈来进行判断。括号匹配共

2、有四种情况：（1）左右括号配对次序不正确；（2）右括号多于左括号；（3）左括号多于右括号；（4）左右括号匹配正确。要求：实验后用专用实验纸书写报告。报告中要说明实验题目，内容；分析实验过程，总结实验结果。三、设计指导1、链栈1）结点的定义#include#include#includetypedefintDataType;typedefstructnode{DataTypedata;structnode*next;}StackNode,*LinkStac

3、k;2)部分函数//堆栈初始化LinkStackInitStack(){returnNULL;}Page6of6//入栈LinkStackPushStack(LinkStackL,intx){//请大家在自己完成}//出栈LinkStackPopStack(LinkStackL,inte){//请大家在自己完成}//显示栈中元素voidVisitStack(LinkStackL){//请大家在自己完成}//取栈顶元素intStackTop(LinkStackL,inte){//请大家在自己完成}voidmain

4、(){inti,e;LinkStackL;L=InitStack();//构造空栈while(1){printf("************************堆栈************************");printf("1入栈2出栈3显示栈中元素4取栈顶元素0返回");printf("****************************************************");scanf("%d",&i);switch(i){case1:printf("入栈元素的值

5、为：");scanf("%d",&e);L=PushStack(L,e);break;case2:L=PopStack(L,e);break;case3:printf("栈中元素自栈顶至栈底为:");VisitStack(L);break;case4:printf("栈顶元素为:%-6d",StackTop(L,e));Page6of6break;case0:exit(0);default:printf("输入错误，请重新选择!");}}}2、括号匹配问题算法思想：算术表达式中右括号和左括号匹配的次

6、序正好符合后到的括号要最先被匹配的“后进先出”堆栈操作特点，因此可以借助一个堆栈来进行判断。括号匹配共有四种情况：（1）左右括号配对次序不正确；（2）右括号多于左括号；（3）左括号多于右括号；（4）左右括号匹配正确。#include#include#include#defineMaxStackSize100typedefcharDataType;typedefstruct{DataTypestack[MaxStackSize];inttop;}SeqSt

7、ack;//1）初始化StackInitiate(S)voidStackInitiate(SeqStack*S){S->top=0;}//（2）非空否StackNotEmpty(S)intStackNotEmpty(SeqStackS){if(S.top<=0)return0;elsereturn1;}//（3）入栈StackPush(S,x)intStackPush(SeqStack*S,DataTypex){if(S->top>=MaxStackSize)Page6of6{printf("堆栈已满无法插入!

8、");return0;}else{S->stack[S->top]=x;S->top++;return1;}}//（4）出栈StackPop(S,d)intStackPop(SeqStack*S,DataType*d){if(S->top<=0){printf("堆栈已空无数据元素出栈!");return0;}else{S->top--;*d=S->stack[S->top];