课程实验报告记录+2————————————————————————————————作者：————————————————————————————————日期：课程实验报告专业年级2012级软件工程课程名称数据结构C语言描述指导教师申红婷学生姓名王晓霞学号20122205041002 实验日期2012.11.7实验地点A3笃行楼A栋306 实验成绩教务处制2013年10月07日实验项目名称栈和队列实验实验目的及要求一．目的：１．使学生对栈和队列的顺序存储结构和链式结构、基本操作和应用，能通过实验达到掌握和应用的目的。

２．要求学生对栈和队列的顺序存储结构和链式结构的基本操作均作验证性实验，对栈和列的应用各作一个设计性实验，并写出实验报告。

二．要求：实验前认真预习实验内容，实验时自觉遵守课堂纪律，严格按操作规程操作，既要独立操作又要与其他同学配合，在实验过程中必须按照实验内容认真做完实验，并认真填写相关实验报告。

实验内容栈和队列的顺序存储结构和链式结构、基本操作和应用。

实验步骤1、阅读下面程序，将函数Push和函数Pop补充完整。

要求输入元素序列1 2 3 4 5e，运行结果如下所示。

#include<stdio.h>#include<malloc.h>#define ERROR 0#define OK 1#define STACK_INT_SIZE 10 /*存储空间初始分配量*/#define STACKINCREMENT 5 /*存储空间分配增量*/typedef int ElemType; /*定义元素的类型*/typedef struct{ElemType *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 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+STACKINCREME NT)*sizeof(ElemType) );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*/int CreateStack(SqStack *S){int e;if(InitStack(S))printf("Init Success!\n");else{printf("Init Fail!\n");return ERROR;}printf("input data:(Terminated 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-createStack\n");CreateStack(&ss);printf("\n2-Pop&Print\n");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。

而这则体现了栈是只允许在表的一端进行操作的线性表并且具有先进后出的特性。

2、在第1题的程序中，编写一个十进制转换为二进制的数制转换算法函数（要求利用栈来实现），并验证其正确性。

●实现代码void conveshen(SqStack *S){ElemType n,h;int m=0,k=0;InitStack(S);printf("Input element\n"); scanf("%d",&n);while(n){ m++;Push(S,n%2);n=n/2;}while(k<m){k++;Pop(S,&h);printf("%d",h);}}int main(){SqStack S;conveshen(&S);printf("\n");return 0;}验证3、阅读并运行程序，并分析程序功能。

#include<stdio.h>#include<malloc.h>#include<string.h>#define M 20#define elemtype char typedef struct{elemtype stack[M];int top;}stacknode;void init(stacknode *st);void push(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"); else{st->top=st->top+1;st->stack[st->top]=x;}}void pop(stacknode *st){if(st->top>0) st->top--;else printf(“Stack is Empty!\n”);}int main(){char s[M];int i;stacknode *sp;printf("create a empty stack!\n");sp=malloc(sizeof(stacknode));init(sp);printf("input a expression:\n");gets(s);for(i=0;i<strlen(s);i++){if(s[i]=='(')push(sp,s[i]);if(s[i]==')')pop(sp);}if(sp->top==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计算机，Windows 2000(或Windows XP) 及以上版本，C（二）基础数据设置及说明计算机，Windows 2000(或Windows XP) 及以上版本，C均能正常运行。

实验结果与分析通过这次实验，我已经基本掌握了本章的学习要点和实验的基本要求以及目的。

第一个程序填空题使我学会了栈和队列的结构定义，逻辑特性及其基本操作的使用。

而第二个程序分析则使我明白了栈和队列的顺序存储表示和链式存储表示，这使得我懂得了该在什么情况下分别实用两种存储表示并用程序代码实现它们相应的操作。

虽然我最终顺利完成了实验，但是在实验过程中我也遇到了许多问题，比如说，不清楚栈和队列的结构定义以至于在后续过程中无法使用站和队列，造成了极大的麻烦，还有在实现某些操作时，无法用程序代码将其顺利运行。

然而遇到问题我并没有退缩，我努力去图书馆查阅资料并且请教老师同学，最终将这些问题各个击破。

与此同时，我也取得了极大的进步。

总而言之，这次有关栈和队列的实验使我受益匪浅，弄明白了许多曾经模糊的知识点，也学会了许多以前并不知道的知识。

教师评语注：可根据实际情况加页。