课 程 实 验 报 告
专 业 年 级 2012级软件工程 课 程 名 称 数据结构C语言描述 指 导 教 师 申红婷 学 生 姓 名 王晓霞
学 号 20122205041002 实 验 日 期 2012.11.7 实 验 地 点 A3笃行楼A栋306 实 验 成 绩
教务处制 2013年10月07日
文档
实验项目 名称 一．目的： 栈和队列实验 １．使学生对栈和队列的顺序存储结构和链式结构、基本操作和应用，能通过实验达到掌握和应用的目的。 ２．要求学生对栈和队列的顺序存储结构和链式结构的基本操作均作验证性实验，实验 对栈和列的应用各作一个设计性实验，并写出实验报告。 目的及要求 二．要求： 实验前认真预习实验内容，实验时自觉遵守课堂纪律，严格按操作规程操作，既要独立操作又要与其他同学配合，在实验过程中必须按照实验内容认真做完实验，并认真填写相关实验报告。 实验 内容 栈和队列的顺序存储结构和链式结构、基本操作和应用。 1、阅读下面程序，将函数Push和函数Pop补充完整。要求输入元素序列1 2 3 4 5 e，运行结果如下所示。 实验步骤 #include 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+STACKINCREMENT)*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; } else return 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\ 文档 Push(S,e); return OK; }/*CreateStack*/ void PrintStack(SqStack *S){ ElemType e; while(Pop(S,&e)) printf(\"%3d\}/*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\while(n) { m++; Push(S,n%2); n=n/2; } while(k 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 文档 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均能正常运行。 通过这次实验，我已经基本掌握了本章的学习要点和实验的基本要求以及目的。第一个程序填空题使我学会了栈和队列的结构定义，逻辑特性及其基本操作的使用。而第二个程序分析则使我明白了栈和队列的顺序存储表示和链式存储表示，这使得我懂得了该在什么情况下分别实用两种存储表示并用程序代码实现它们相应的操作。虽然我最终 顺利完成了实验，但是在实验过程中我也遇到了许多问题，比如说，不清楚栈和队列的 实验结果与 结构定义以至于在后续过程中无法使用站和队列，造成了极大的麻烦，还有在实现某些分析 操作时，无法用程序代码将其顺利运行。然而遇到问题我并没有退缩，我努力去图书馆查阅资料并且请教老师同学，最终将这些问题各个击破。与此同时，我也取得了极大的进步。总而言之，这次有关栈和队列的实验使我受益匪浅，弄明白了许多曾经模糊的知识点，也学会了许多以前并不知道的知识。 文档 教师评语 注：可根据实际情况加页 文档 因篇幅问题不能全部显示，请点此查看更多更全内容