课 程 实 验 报 告
专 业 年 级 2012级软件工程 课 程 名 称 数据结构C语言描述 指 导 教 师 申红婷 学 生 姓 名 王晓霞
学 号 202
实 验 日 期 2012.11.7 实 验 地 点 A3笃行楼A栋306 实 验 成 绩
教务处制 2013年10月07日
实验项目 名称 一．目的： 栈和队列实验 １．使学生对栈和队列的顺序存储结构和链式结构、基本操作和应用，能通过实验达到掌握和应用的目的。 ２．要求学生对栈和队列的顺序存储结构和链式结构的基本操作均作验证性实验，实验 对栈和列的应用各作一个设计性实验，并写出实验报告。 目的及要求 二．要求： 实验前认真预习实验内容，实验时自觉遵守课堂纪律，严格按操作规程操作，既要独立操作又要与其他同学配合，在实验过程中必须按照实验内容认真做完实验，并认真填写相关实验报告。 实验 内容 栈和队列的顺序存储结构和链式结构、基本操作和应用。 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 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+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(\ else{ printf(\ return ERROR; } printf(\ while(scanf(\ Push(S,e); return OK; }/*CreateStack*/ void PrintStack(SqStack *S){ ElemType e; while(Pop(S,&e)) printf(\}/*Pop_and_Print*/ int main() { SqStack ss; printf(\ CreateStack(&ss); printf(\PrintStack(&ss); printf(\ 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(\ scanf(\while(n) { m++; Push(S,n%2); n=n/2; } while(k #include #include #define M 20 #define elemtype char typedef struct { elemtype stack[M]; int top; }
