实验二 实现顺序栈或循环队列的储存.doc

实验二 实现顺序栈或循环队列的储存 实验环境 Visual Stdio C++6.0 二、实验目的 熟练掌握队列和栈的基本操作，并在此基础上进行适当的拓展。 需求分析 本实验主要利用链式队列的储存模式，来模拟实现生活中的离散事件发生情况。该程序是利用C++的面向对象的方法来进行处理，对过程进行了封装和集成，便于操作与实现。 当用户发现刚刚键入得一个字符是错误的时，可以补进一个退格符“#”，以表示一个字符无效；如果发现当前键入的行内差错较多或难以补救，则可以键入一个退行符“@”，以表示当前行中的字符均无效。 程序执行的命令包括： 1、初始化栈 2、进栈 3、出栈 4、清空栈 5、释放栈 6、判断空栈 7、输出栈 8、结束 四、详细设计 1、定义头文件 #include stdlib.h #include stdio.h #include malloc.h #include string.h #include conio.h #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 2、元素类型、节点类型和指针类型 struct SqStack { char *base; char *top; int stacksize; }; 3、初始化栈 void InitStack(SqStack S) { S.base=(char*)malloc(STACK_INIT_SIZE *sizeof(char)); if (!S.base) exit(1); S.top=S.base; S.stacksize=STACK_INIT_SIZE; } 进栈 void push(SqStack S,char e) { if(S.top-S.base=S.stacksize) { S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char)); if (!S.base) exit(1); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; } 出栈 char pop(SqStack S,char e) { if (S.top==S.base) return false; e=*--S.top; return e; } 清空栈 void ClearStack(SqStack S) { S.top=S.base; } 释放栈 void DestroyStack(SqStack S) { free(S.base); S.top=S.base; } 判断空栈 bool StackEmpty(SqStack S) { if (S.top==S.base) return true; return false; } 9、输出栈 void PrintStack(SqStack S) { char e; while (!StackEmpty(S)) { pop(S,e); printf(%d,e); } 主函数模板 void main() { char ch,e; printf(请输入字符\n); printf(输入#前一个字符无效\n); printf(输入@清空@之前的栈\n); SqStack S,D; InitStack(S); InitStack(D); ch=getchar(); while (ch!=EOF) { while(ch!=EOFch!=\n) { switch(ch) { case#:pop(S,e);break; case@:ClearStack(S);break; default:push(S,ch);break; } ch=getchar(); } while (!StackEmpty(S)) { e=pop(S,e); push (D,e); } while (!StackEmpty(D)) { e=pop(D,e); printf(%c,e); } ClearStack(S); if(ch!=EOF) ch=getchar(); } DestroyStack(S); } 调试分析 这个程序是行编译器，运用了栈。用