数据结构栈、队列实验试验报告3教程.doc

实验报告（3） 实验名称栈、队列实验同组人姓名ＸＸ实验性质基本操作 □验证性 ■ 综合性 □设计性实验日期2011.04.20实验成绩教师评价： 实验预习□ 实验操作□ 实验结果□ 实验报告□ 其它□ 教师签名：1.目的要求： 掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们。 本实验训练的要点是“栈”和“队列”的观点； 2.实验内容： 利用栈，实现任一个表达式中的语法检查（如括号的匹配）。 编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）； 三、主要设备及软件 PC机1台, VC 6.0 平台实验流程、操作步骤或核心代码、算法片段 括号匹配 Status InitStack(SqStack S) {S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } Status POp(SqStack S,SElemType e) {if(S.top==S.base) return ERROR; e=*--S.top; return OK; } Status Push(SqStack S,SElemType e) {if(S.top-S.base=S.stacksize) {S.base=(SElemType*)realloc(S.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT;} *S.top++=e; return OK; } Status StackEmpty(SqStack S) {if(S.top==S.base) return OK; else return ERROR; } gets(ch); while(ch[i]!=\0flag) { switch(ch[i]) {case( : case[ : case{ : Push(S,ch[i]);break; case) : if(POp(S,e)==ERROR||e!=() flag=ERROR;break; case] : if(POp(S,e)==ERROR||e!=[) flag=ERROR;break; case} : if(POp(S,e)==ERROR||e!={) flag=ERROR;break;} ++i; } if(flagch[i]==\0StackEmpty(S)) printf(括号匹配成功\n); else printf(匹配失败\n); 进制转换的关键代码 void main(){ SqStack S; SElemType e,n; printf( 将一个十进制数转换成十六进制数\n); if(InitStack(S)==OVERFLOW) printf(分配失败，退出程序\n); else printf(输入一个十进制的数字n\n); scanf(%d,n); while(n) {Push(S,n%16); n=n/16; } while(!StackEmpty(S)) {POp(S,e); if(e10) printf(%d,e); else printf(%c,65+e-10); }printf(\n\n);} 循环队列的关键代码 Status InitQueue(SqQueue Q) { Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType)); if (!Q.base) exit(OVERFLOW); Q.front=Q.rear=0; return OK; } Status QueueLength(SqQueue Q) { return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; } Status EnQueue(SqQueu