数据结构实验4栈的操作.docVIP

《数据结构》实验报告 实验序号：4　　　　　　　　　　 实验项目名称：栈的操作 学　　号 流浪 姓　　名 专业、班 实验地点 指导教师 实验时间 一、实验目的及要求 1. 熟悉栈的基本概念； 2. 掌握栈的顺序存储结构； 3．掌握栈的应用。 二、实验设备（环境）及要求 微型计算机； windows 操作系统； Microsoft Visual Studio 6.0集成开发环境。 三、实验内容与步骤 1.假设1,2,3,4顺序进入一个空栈中，请列出所有可能的出栈序列。 （1）：1 2 3 4 （2）：1 2 4 3 （3）：1 3 2 4 （4）：1 3 4 2 （5）：1 4 3 2 （6）：2 1 3 4 （7）：2 1 4 3 （8）：2 3 4 1 （9）：2 4 3 1 （10）：3 4 2 1 （11）：3 2 1 4 （12）：3 2 4 1 （13）：4 3 2 1 2.栈的顺序表表示和实现的如下： #include stdlib.h #include stdio.h #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define ERROR 1 #define OK 0 #define OVERFLOW 1 typedef int SElemType; typedef int Status; typedef struct{ SElemType *base; SElemType *top; int stacksize; } SqStack; Status InitStack(SqStack S) { S.base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; } Status Push(SqStack S, SElemType e) { if(S.top - S.base = S.stacksize) { S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *S.top++ = e; return OK; } Status Pop(SqStack S, SElemType e) { if(S.top == S.base) return ERROR; e = *--S.top; return OK; } void main() { int i; SElemType j = 0; SqStack S; InitStack(S); //初始化栈 printf(元素入栈); for(i=0 ; i10; i++) { printf( %d ,j); Push(S,j); //元素入栈 j++; } printf(\n元素出栈); for(i=0 ; i10; i++) { Pop(S,j); //元素出栈 printf( %d ,j); } } 改写以上程序，实现功能如下： 改写Push和Pop函数，使得以上两个函数可以一次性将i个元素（参数为数组）入栈和出栈。 以下题目为选做题： 3.C/C++的库函数中已经实现了栈，实例如下： #includestack //引入栈 using namespace std; int main() { int a; stackints; //定义整型栈s scanf(%d,a); s.push(a); //入栈 printf(%d\n,s.top()); //取得栈顶元素输出 s.pop(); //出栈 return 0; } 请根据以上程序，设计算法如下（任选一题）： 判别一个算术表达式中的圆括号配对是否正确。 2．判别一个算术表达式中的圆括号和方括号配对是否正确。 四、实验结果与数据处理 详细记录程序在调过程中出现的问题及解决方法。记录程序执行的结果对上机结果进行分析，上机的心得体会。