课程试验报告+2

1、课程实验报告专 业 年 级 2012 级软件工程课 程 名 称 数据结构 C 语言描述指 导教 师申红婷学 生姓 名王晓霞学号20122205041002实 验日 期2012.11.7实 验 地 点 A3 笃行楼 A 栋 306 实验成绩教务处制2013 年 10 月 07 日专业 word 可编辑实验项目栈和队列实验名称目的： 使学生对栈和队列的顺序存储结构和链式结构、 基本操作和应用 ， 能通过实验达到掌握和应用的目的 。实验 要求学生对栈和队列的顺序存储结构和链式结构的基本操作均作验证性实验，对栈和列的应用各作一个设计性实验 ， 并写出实验报告 。目的及要求二要求：实验前认真预习实验内容

2、 ，实验时自觉遵守课堂纪律 ， 严格按操作规程操作 ， 既，并要独立操作又要与其他同学配合 ， 在实验过程中必须按照实验内容认真做完实验实验认真填写相关实验报告 。栈和队列的顺序存储结构和链式结构 、 基本操作和应用 。内容1、阅读下面程序 ，将函数 Push 和函数 Pop 补充完整 。要求输入元素序列 1 2 3 4 5 e， 运行结果如下所示 。实验步骤#include#include#define ERROR 0专业 word 可编辑#define OK 1#define STACK_INT_SIZE 10 /* 存储空间初始分配量 */#define STACKINCREMENT 5

3、/* 存储空间分配增量 */typedef 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

4、(SqStack *S); /* 出栈并输出栈中元素 */int 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;专业 word 可编辑/*InitStack*/int Push(SqStack *S,ElemType e)if (S-top-S-base=S-stacksize)S-base=(ElemType*)realloc( S

5、-base,(S-stacksize+STACKINCREMENT)*sizeof(Ele mType) );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;elsereturn 0;/*Pop*/专业 word 可编辑int CreateStack(SqStack *S)int e;if(InitStack(S)printf(Init Succe

6、ss!n);elseprintf(Init Fail!n);return ERROR;printf(input data:(T erminated by inputing a character)n);while(scanf(%d,&e)Push(S,e);return OK;/*CreateStack*/void PrintStack(SqStack *S)ElemType e;while(Pop(S,&e)printf(%3d,e);/*Pop_and_Print*/int main()SqStack ss;printf(n1-createStackn);专业 word 可编辑Create

7、Stack(&ss);printf(n2-Pop&Printn);PrintStack(&ss);printf(n);return 0;算法分析 ： 输入元素序列 1 2 3 4 5 ， 为什么输出序列为 5 4 3 2 1 ？体现了栈的什 么特性 ？程序运行结果如下图所示 ：因为当 main 函数调用 PrintStack(&ss) 时， 程序转到函数体中 ，而在该函数体内 ， 又调用了 int Pop(SqStack *S,ElemType *e) ，此函数的功能是栈 S 的栈顶元素退栈并返 回其值 。所以输入元素序列 1 2 3 4 5 ，输出序列为 5 4 3 2 1 。而这则体现了栈

8、是只允 许在表的一端进行操作的线性表并且具有先进后出的特性 。2、在第 1 题的程序中 ， 编写一个十进制转换为二进制的数制转换算法函数( 要求利用栈来实现 )， 并验证其正确性 。实现代码void conveshen(SqStack *S)ElemType n,h;专业 word 可编辑int m=0,k=0;InitStack(S); printf(Input elementn); scanf(%d,&n);while(n) m+;Push(S,n%2); n=n/2;while(km)k+;Pop(S,&h);printf(%d,h);int main()SqStack S; conve

9、shen(&S); printf(n);return 0;专业 word 可编辑验证3、阅读并运行程序 ，并分析程序功能#include#include#include#define M 20#define elemtype chartypedef structelemtype stackM;int top;stacknode;void init(stacknode *st);void push(stacknode *st,elemtype x);void pop(stacknode *st);专业 word 可编辑void init(stacknode *st) st-top=0;void

10、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;专业 word 可编辑stacknode *sp;printf(create a empty stack!n); sp=malloc(sizeof(stacknode

11、); 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运行结果 ：专业 word 可编辑输入 ： a-(c-d)*6-(s/3-x)/2 运行结果 ：程序的基本功能判断所输入多项式的左右括号是否配对实验环境实验结果与分析(一)运行环境说明PC 计算机 ，Windows 2000( 或 Windows XP) 及以上版本 ，C(二)基础数据设置及说明计算机 ， Windows 2000( 或 Windows XP) 及以上版本 ，C 均能正常运行通过这次实验 ， 我已经基本掌握了本章的学习要点和实验的基本要求以及目的。第一个程序填空题使我学会了栈和队列的结构定义， 逻辑特性及其基本操作的使用 。而第二个程序分析则使我明白了栈和队列的顺序存储表示和链式存储表示， 这使得我懂得了该在什么情况下分别实用两种存储表示并用程序代码实现它们相应的操作 。 虽 然我最终顺利完成了实验 ，但是在实验过程中我也遇到了许多问题 ，比如说 ，不清楚 栈和队列的结构定义以至于在后续过程中无法使用站和队列 ，造成了极大的麻烦 ， 还 有在实现某些操作时 ，无法用程序代码