栈的实现与应用.doc

实验题目 栈的实现与应用 实验时间 一、实验目的、意义（1）理解栈的特点，掌握栈的定义和基本操作。（2）掌握进栈、出栈、清空栈运算的实现方法。（3）熟练掌握顺序栈的操作及应用。二、实验内容及要求1.定义顺序栈，完成栈的基本操作：建空栈、入栈、出栈、取栈顶元素（参见教材45页）。2. 调用栈的基本操作，将输入的十进制数转换成十六进制数。3. 调用栈的基本操作，实现行编辑程序，假设“#”为退格符，“”为退行符。三、实验结果及分析（所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果采用截图方式给出。） 四、程序清单(包含注释) #include #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; typedef int SElemType; #define STACK_INIT_SIZE 10 #define STACK_INCREMENT 2 struct SqStack SElemType *base; SElemType *top; int stacksize; ; void 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; void DestroyStack(SqStack &S) free(S.base); S.top=S.base=NULL; S.stacksize=0; void ClearStack(SqStack &S) S.top=S.base; Status StackEmpty(SqStack S) if(S.top=S.base) return TRUE; else return FALSE; int StackLength(SqStack S) return S.top-S.base; Status GetTop(SqStack S,SElemType &e) if(S.topS.base) e=*(S.top-1); return OK; else return ERROR; Status Push(SqStack &S,SElemType e) if(S.top-S.base=S.stacksize) S.base=(SElemType*)realloc(S.base, (S.stacksize+STACK_INCREMENT)* sizeof(SElemType); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACK_INCREMENT; *(S.top)+=e; return OK; Status Pop(SqStack &S,SElemType &e) if(S.top=S.base) return ERROR; e=*-S.top; return OK; void StackTraverse(SqStack S,void(*visit)(SElemType &) while(S.topS.base) visit(*S.base+); printf(n); void conversion(int n,int m) SqStack sl; int x; InitStack(sl); while(n) Push(sl,n%m);n=n/m; while(!StackEmpty(sl) Pop(sl,x); if(x=9) printf(%d,x); else printf(%c,x+55); printf(n); void main() int a; int n,m; while(1) printf(1.数制转换n); printf(2.退出n); printf(请选择:); scanf(%d,&a); getchar(); switch(a) case 1: printf(请输入要转换的十进制数(n),及要转换成几进制(m)nn,mn); scanf(%d,%d,&n,&m); conversion(n,m); break; case 2: return; #include #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; typedef char SElemType; #define STACK_INIT_SIZE 10 #define STACK_INCREMENT 2 struct SqStack SElemType *base; SElemType *top; int stacksize; ; void 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; void DestroyStack(SqStack &S) free(S.base); S.top=S.base=NULL; S.stacksize=0; void ClearStack(SqStack &S) S.top=S.base; Status StackEmpty(SqStack S) if(S.top=S.base) return TRUE; else return FALSE; int StackLength(SqStack S) return S.top-S.base; Status GetTop(SqStack S,SElemType &e) if(S.topS.base) e=*(S.top-1); return OK; else return ERROR; Status Push(SqStack &S,SElemType e) if(S.top-S.base=S.stacksize) S.base=(SElemType*)realloc(S.base, (S.stacksize+STACK_INCREMENT)* sizeof(SElemType); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACK_INCREMENT; *(S.top)+=e; return OK; Status Pop(SqStack &S,SElemType &e) if(S.top=S.base) return ERROR; e=*-S.top; return OK; void StackTraverse(SqStack S,void(*visit)(SElemType &) while(S.topS.base) visit(*S.base+); printf(n); FILE *fp;void copy(SElemType &c) fputc(c,fp); void LineEdit() SqStack s; char ch; InitStack(s); printf(请输入一个文本文件，Z(Ctrl+Z)结束输入：n); ch=getchar(); while(ch!=EOF) while(ch!=EOF&ch!=n) switch(ch) case #:if(!StackEmpty(s) Pop(s,ch); break; case :ClearStack(s); break; default :Push(s,ch); ch=getchar(); StackTraverse(s,copy); fputc(n,fp); ClearStack(s); if(ch!=EOF) ch=getchar(); DestroyStack(s); void main() int a; while(1) pr