栈的基本操作.doc

_数 据 结 构 实 验 报 告2011年5月18日1. 项目组成2. 程序结构图 mainGetTopStackEmptyNizhiPopPushStackLengthInitStack3. 算法及其功能函数InitStack(SqStack *S) /*创建栈*/GetTop(SqStack *S,SElemType e) /*取栈顶元素并用e返回*/Push(SqStack *S,SElemType e) /*插入e为栈顶元素*/Pop(SqStack *S,SElemType *e) /*删除栈顶元素并用e返回*/StackEmpty(SqStack S) /*判断栈是否为空*/StackLength(SqStack S) /*求栈的长度*/Nizhi(SqStack S) /*将栈中元素逆置*/4. 源代码#include #include #define OK 1#define OVERFLOW -2typedef int Status;typedef int SElemType;#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10typedef structSElemType *base;SElemType *top;int stacksize;SqStack;Status InitStack(SqStack *S)int i,n;SElemType e;S-base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S-base) exit (OVERFLOW);S-top=S-base;S-stacksize=STACK_INIT_SIZE;printf(请输入栈内的数据个数:);scanf(%d,&n);if(n=S-stacksize)S-base=(SElemType *)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S-base) exit(OVERFLOW); for(i=0;itop)=e;S-top=S-top+1;return OK;Status Init(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 GetTop(SqStack *S,SElemType e) if(S-top=S-base) return 0;e=*(S-top-1);return e;Status Push(SqStack *S,SElemType e)if(S-top-S-base=S-stacksize)S-base=(SElemType *)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S-base)exit (OVERFLOW);S-top=S-base+S-stacksize;S-stacksize+=STACKINCREMENT;printf(请输入要插入的栈顶元素:);scanf(%d,&e);*S-top+=e;return OK;void PushSq(SqStack *S,SElemType e)if(S-top-S-base=S-stacksize)S-base=(SElemType *)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S-base)exit (OVERFLOW);S-top=S-base+S-stacksize;S-stacksize+=STACKINCREMENT;*S-top+=e;Status Pop(SqStack *S,SElemType *e)if(S-top=S-base) return 0;*e=*-S-top;return *e;Status StackEmpty(SqStack S)if(S.base=S.top)return 1; else return 0;Status StackLength(SqStack S) int i=0; while(S.topS.base) S.base+; i+; return i;Status Nizhi(SqStack S)SqStack A,B;SElemType e;if (Init(&A)=OVERFLOW) printf(构造失败，退出程序！n);if (Init(&B)=OVERFLOW) printf(构造失败，退出程序！n);while(!StackEmpty(S) Pop(&S,&e); PushSq(&A,e);while(!StackEmpty(A) Pop(&A,&e); PushSq(&B,e);printf(逆置后n);while(!StackEmpty(B) Pop(&B,&e);printf(%dn,e); PushSq(&S,e);return OK;void main() SqStack S,M; SElemType e; int select,N,xuanze,X; do printf(1：构造栈Sn); printf(2：判断栈S是否为空n ); printf(3：用e返回S的栈顶元素n); printf(4：插入元素e为新的栈顶元素n); printf(5：删除S的栈顶元素,并用e返回其值n); printf(6：返回栈S的元素个数n); printf(7: 逆置栈Sn); printf(8: 数值转换进制n); printf(0：结束n); scanf(%d,&select); switch (select) case 1: if (InitStack(&S)=OVERFLOW) printf(构造失败，退出程序！n);else printf(构造成功！n);break;case 2:if(StackEmpty(S)=1) printf(栈为空n);else printf(栈非空n);break;case 3:if(StackEmpty(S)=1) printf(错误!此表为空表!n);break;e=GetTop(&S,e);printf(e=%dn,e);break;case 4: if(StackEmpty(S)=1) printf(错误!此表为空表!n);break;if(Push(&S,e)=OVERFLOW) printf(插入元素e失败n);else printf(插入元素e成功！n);break;case 5:if(StackEmpty(S)=1) printf(错误!此表为空表!n);break;e=Pop(&S,&e);printf(e=%dn,e);break;case 6:printf(栈的长度为%dn,StackLength(S);break;case 7:if(StackEmpty(S)=1) printf(错误!此表为空表!n);break;if(Nizhi(S)=1) printf(逆置成功n);else printf(逆置失败n);break;case 8: Init(&M); printf(请输入任意非负十进制整数:nN=);scanf(%d,&N);printf(请选择将该整数转换成:n); do printf(1：2进制n); printf(2：8进制n ); printf(3：12进制n); printf(4：16进制n); printf(5：任意进制n); scanf(%d,&xuanze); switch (xuanze) case 1:X=2;break; case 2:X=8;break; case 3:X=12;break; case 4:X=16;break; case 5:printf(转换成X进制,X=); scanf(%d,&X);break; case 0:break;default:printf(输入选择出错！n); while (!xuanze); printf(转制后n);while(N)PushSq(&M,N%X);N