1、 课 程 实 验 报 告专 业 年 级 2012 级软件工程 课 程 名 称 数据结构 C 语言描述 指 导 教 师 申红婷 学 生 姓 名 王晓霞 学 号 20122205041002 实 验 日 期 2012.11.7 实 验 地 点 A3 笃行楼 A 栋 306 实 验 成 绩 教务处制2013 年 10 月 07 日实验项目名称 栈和队列实验实验目的及要求一目的：使学生对栈和队列的顺序存储结构和链式结构、基本操作和应用，能通过实验达到掌握和应用的目的。要求学生对栈和队列的顺序存储结构和链式结构的基本操作均作验证性实验，对栈和列的应用各作一个设计性实验，并写出实验报告。二要求：实验前认真
2、预习实验内容，实验时自觉遵守课堂纪律，严格按操作规程操作，既要独立操作又要与其他同学配合，在实验过程中必须按照实验内容认真做完实验，并认真填写相关实验报告。实验内容 栈和队列的顺序存储结构和链式结构、基本操作和应用。实验步骤1、阅读下面程序，将函数 Push 和函数 Pop 补充完整。要求输入元素序列 1 2 3 4 5 e，运行结果如下所示。#include#include#define ERROR 0#define OK 1#define STACK_INT_SIZE 10 /*存储空间初始分配量*/#define STACKINCREMENT 5 /*存储空间分配增量*/typedef
3、int ElemType; /*定义元素的类型*/typedef structElemType *base;ElemType *top;int stacksize; /*当前已分配的存储空间*/SqStack;int InitStack(SqStack *S); /*构造空栈*/int push(SqStack *S,ElemType e); /*入栈*/int Pop(SqStack *S,ElemType *e); /*出栈*/int CreateStack(SqStack *S); /*创建栈*/void PrintStack(SqStack *S); /*出栈并输出栈中元素*/int
4、InitStack(SqStack *S)S-base=(ElemType *)malloc(STACK_INT_SIZE*sizeof(ElemType);if(!S-base) return ERROR;S-top=S-base;S-stacksize=STACK_INT_SIZE;return OK;/*InitStack*/int Push(SqStack *S,ElemType e)if (S-top-S-base=S-stacksize) S-base=(ElemType*)realloc( S-base,(S-stacksize+STACKINCREMENT)*sizeof(El
5、emType) ); S-top=S-base+S-stacksize; S-stacksize+=STACKINCREMENT; *S-top+=e; return 1;/*Push*/int Pop(SqStack *S,ElemType *e)if (S-top!=S-base) *e=*-S-top; return 1; else return 0;/*Pop*/int CreateStack(SqStack *S)int e;if(InitStack(S)printf(“Init Success!n“);elseprintf(“Init Fail!n“);return ERROR;p
6、rintf(“input data:(Terminated by inputing a character)n“);while(scanf(“%d“,return OK;/*CreateStack*/void PrintStack(SqStack *S)ElemType e;while(Pop(S,/*Pop_and_Print*/int main()SqStack ss;printf(“n1-createStackn“);CreateStack(printf(“n2-PopPrintStack(printf(“n“); return 0; 算法分析：输入元素序列 1 2 3 4 5，为什么输
7、出序列为 5 4 3 2 1？体现了栈的什么特性？程序运行结果如下图所示：因为当 main 函数调用 PrintStack( int m=0,k=0; InitStack(S); printf(“Input elementn“); scanf(“%d“, while(n) m+; Push(S,n%2); n=n/2; while(k#include#include#define M 20#define elemtype chartypedef structelemtype stackM;int top;stacknode;void init(stacknode *st);void push(
8、stacknode *st,elemtype x);void pop(stacknode *st);void init(stacknode *st)st-top=0;void push(stacknode *st,elemtype x)if(st-top=M)printf(“the stack is overflow!n“);elsest-top=st-top+1;st-stackst-top=x;void pop(stacknode *st)if(st-top0) st-top-;else printf(“Stack is Empty!n”);int main()char sM;int i;
9、stacknode *sp;printf(“create a empty stack!n“);sp=malloc(sizeof(stacknode);init(sp);printf(“input a expression:n“);gets(s);for(i=0;itop=0)printf(“(match)!n“);elseprintf(“(not match)!n“);return 0;输入：2+(c-d)*6-(f-7)*a)/6运行结果：输入：a-(c-d)*6-(s/3-x)/2运行结果：程序的基本功能：判断所输入多项式的左右括号是否配对。实验环境（一）运行环境说明PC 计算机，Wind
10、ows 2000(或 Windows XP) 及以上版本，C（二）基础数据设置及说明计算机，Windows 2000(或 Windows XP) 及以上版本，C 均能正常运行。实验结果与分析通过这次实验，我已经基本掌握了本章的学习要点和实验的基本要求以及目的。第一个程序填空题使我学会了栈和队列的结构定义，逻辑特性及其基本操作的使用。而第二个程序分析则使我明白了栈和队列的顺序存储表示和链式存储表示，这使得我懂得了该在什么情况下分别实用两种存储表示并用程序代码实现它们相应的操作。虽然我最终顺利完成了实验，但是在实验过程中我也遇到了许多问题，比如说，不清楚栈和队列的结构定义以至于在后续过程中无法使用站和队列，造成了极大的麻烦，还有在实现某些操作时，无法用程序代码将其顺利运行。然而遇到问题我并没有退缩，我努力去图书馆查阅资料并且请教老师同学，最终将这些问题各个击破。与此同时，我也取得了极大的进步。总而言之，这次有关栈和队列的实验使我受益匪浅，弄明白了许多曾经模糊的知识点，也学会了许多以前并不知道的知识。教师评语注：可根据实际情况加页
