实验四 栈的设计及应用.doc

实验四 栈的设计及应用 一．实验目的 1．掌握栈的逻辑结构。 2．掌握顺序栈、链栈的设计过程。 3．使用设计的栈实现进制转换。 二、实验内容 1．设计顺序栈：设计头文件SqStack.h，其内容如下： #define MaxLen 20 #include stdlib.h typedef struct { Selemtype data[MaxLen]; int top; }SqStack; //初始化栈 void InitStack(SqStack S) { //栈中数据元素个数为0 S.top=0; } //判栈空 int StackEmpty(SqStack S) { //栈中元素个数为0，则为空 if(S.top==0) return 1; else return 0; } //判栈满 int StackFull(SqStack S) { //栈中元素个数为MaxLen if(S.topMaxLen) return 1; else return 0; } void push(SqStack S,Selemtype e) { if(StackFull(S)) { coutStack is full,the program break!; exit(-1); } //将元素e插入到栈顶 S.data[S.top]=e; //栈中元素个数增加1 S.top++; } void pop(SqStack S,Selemtype e) { if(StackEmpty(S)) { coutStack is empty!; exit(-1); } //将栈顶元素通过形参e返回 e=S.data[S.top-1]; //栈中元素个数减少1 S.top--; } void Gettop(SqStack S,Selemtype e) { if(StackEmpty(S)) { coutStack is empty!; exit(-1); } //将栈顶元素通过形参e返回 e=S.data[S.top-1]; } 2．利用顺序栈实现将一个十进制数转换成2、8、16进制：设计测试文件test.cpp，其内容如下： #include iostream.h typedef int Selemtype; #include SqStack.h void main() { SqStack s; InitStack(s); int m; coutplease input a number:; cinm; while(m) { push(s,m%2); m=m/2; } while(!StackEmpty(s)) Selemtype e; pop(s,e); coute; } coutendl; } 3．设计链式栈：设计头文件LinkStack.h，其内容如下： #include stdio.h #include stdlib.h typedef struct snode { Selemtype data; snode *next; }SNode,*LinkStack; void InitStack(LinkStack S) { S=NULL; } int StackEmpty(LinkStack S) { return S==NULL; } void push(LinkStack S,Selemtype e) { SNode *p; p=new SNode; p-data=e; p-next=S; S=p; } void pop(LinkStack S,Selemtype e) { if(StackEmpty(S)) { coutStack is empty!; exit(-1); } e=S-data; SNode *p=S; S=S-next; delete p; } void Gettop(LinkStack S,Selemtype e) { if(StackEmpty(S)) { coutStack is empty!; exit(-1); } e=S-data; } 三．分析 3