数据结构教程第十七课实验三栈的表示与实现及栈的应用
《数据结构教程第十七课实验三栈的表示与实现及栈的应用》由会员分享,可在线阅读,更多相关《数据结构教程第十七课实验三栈的表示与实现及栈的应用(11页珍藏版)》请在装配图网上搜索。
1、数据结构教程第十七课实验三:栈的表示与实现及栈的应用数据结构教程第十七课实验三:栈的表示与实现及栈的应用教学目的: 掌握栈的存储表示方式和栈基本操作的实现方法教学重点: 栈的基本操作实现方法,栈的应用教学难点: 栈的存储表示实验内容:一、栈的实现实现栈的顺序存储。栈实现示例#include#include#include#define ERROR 0#define TRUE 1#define FALSE 0#define OK 1#define EQUAL 1#define OVERFLOW -1#define STACK_INIT_SIZE 100#define STACKINCREMENT
2、 10typedef int Status ;struct STU char name20; char stuno10; int age; int score;typedef struct STU SElemType;struct STACK SElemType *base; SElemType *top; int stacksize;typedef struct STACK SqStack;typedef struct STACK *pSqstack;Status InitStack(SqStack *S);Status DestroyStack(SqStack *S);Status Cle
3、arStack(SqStack *S);Status StackEmpty(SqStack S);int StackLength(SqStack S);Status GetTop(SqStack S,SElemType *e);Status Push(SqStack *S,SElemType e);Status Pop(SqStack *S,SElemType *e);Status StackTraverse(SqStack S,Status (*visit)();Status InitStack(SqStack *S) (*S)=(SqStack *) malloc(sizeof(SqSta
4、ck); (*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 DestroyStack(SqStack *S) free(S-base); free(S);Status ClearStack(SqStack *S) S-top=S-base;Status StackEmpty(SqStack S) if(S.top=S.
5、base) return TRUE; else return FALSE;int StackLength(SqStack S) int i; SElemType *p; i=0; p=S.top; while(p!=S.base) p+; i+; Status GetTop(SqStack S,SElemType *e) if(S.top=S.base) return ERROR; *e=*(S.top-1); return OK;Status Push(SqStack *S,SElemType e) /* if(S-top - S-base=S-stacksize) S-base=(SEle
6、mType *) 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; return OK;Status Pop(SqStack *S,SElemType *e) if(S-top=S-base) return ERROR; *e=*-S-top; return OK;Status StackPrintElem(SE
7、lemType * e) printf(%s %s %d %dn,e-name,e-stuno,e-age,e-score);Status StackTraverse(SqStack S,Status (*visit)() while(S.top!=S.base) visit(-S.top);main() SElemType e; SqStack *Sa; clrscr(); printf(nn-SqStack Demo is running.-nn); printf(First is Push function.n); InitStack(&Sa); strcpy(e.name,stu1);
8、 strcpy(e.stuno,100001); e.age=80; e.score=1000; printf( Now Stack is Empty.n); StackTraverse(*Sa,StackPrintElem); Push(Sa,e); printf( Now Stack has one element.n); StackTraverse(*Sa,StackPrintElem); strcpy(e.name,stu3); strcpy(e.stuno,100002); e.age=80; e.score=1000; Push(Sa,e); printf( Now Stack h
9、as another element.n); StackTraverse(*Sa,StackPrintElem); printf( Now Pop Stack,the top elem put into variable e.n); Pop(Sa,&e); printf(%sn%sn%dn%dn,e.name,e.stuno,e.age,e.score); printf( Lets see the left of Stacks elem:n); StackTraverse(*Sa,StackPrintElem); getch(); printf(nnnWelcom to visit nn);二
10、、栈的应用、利用栈实现数制转换 、利用栈实现单行编辑以上任选一题。数制转换示例#include#include#includetypedef int SElemType;#include stack.hStatus visit(SElemType * e) printf( %d , *e);void conversion() pSqStack S; SElemType e; int n; InitStack(&S); printf(Input a number to convert to OCT:n); scanf(%d,&n); if(n0) printf(nThe number must
11、be over 0.); return; if(!n) Push(S,0); while(n) Push(S,n%8); n=n/8; printf(the result is: ); while(!StackEmpty(*S) Pop(S,&e); printf(%d,e); main() printf(nnnn); conversion(); getch(); printf(nnWelcome to visit !);单行编辑示例#include#include#include#include#define EOFILE typedef char SElemType;#include st
12、ack.hStatus visit(SElemType * e) printf(%c, *e);char OP10=+,-,*,/,(,),#;int precede77= 1,1,2,2,2,1,1, 1,1,2,2,2,1,1, 1,1,1,1,2,1,1, 1,1,1,1,2,1,1, 2,2,2,2,2,3,0, 1,1,1,1,0,1,1, 2,2,2,2,2,0,3;int In(char c,char *op) int i=0; while(i7) if(c=opi+) return 1; return 0;char Precede(char op,char c) int pos
13、_op; int pos_c; int i; for(i=0;i; case 2: return ; case 3: return =; char Operate(int a,char theta,int b) switch(theta) case +:return a+b-0; case -:return a-b+0; case *:return (a-0)*(b-0)+0; case /:return (a-0)/(b-0)+0; char EvaluateExpression() SqStack *OPND,*OPTR; char c,x,theta; char a,b; InitSta
14、ck(&OPTR); Push(OPTR,#); InitStack(&OPND); c=getchar(); while(c!=#|GetTop(*OPTR)!=#) if(!In(c,OP)Push(OPND,c);c=getchar(); elseswitch(Precede(GetTop(*OPTR),c) case : Pop(OPTR,&theta); Pop(OPND,&b); Pop(OPND,&a); Push(OPND,Operate(a,theta,b); break; c=GetTop(*OPND); DestroyStack(OPTR); DestroyStack(O
15、PND); return c;main() char i; printf(nnnnOnly within 0.9 evaluation,input a expression end with symbol #:n); i=EvaluateExpression(); printf(nThis expressions result is: ); printf(%dnnnn,i-0); printf(nnWelcome to visit !);这里是实现栈的头文件#include simuc.h#define OVERFLOW -1#define STACK_INIT_SIZE 100#define
16、 STACKINCREMENT 10typedef int Status;struct STACK SElemType *base; SElemType *top; int stacksize;typedef struct STACK SqStack;typedef struct STACK *pSqStack;Status InitStack(SqStack *S);Status DestroyStack(SqStack *S);Status ClearStack(SqStack *S);Status StackEmpty(SqStack S);int StackLength(SqStack
17、 S);SElemType GetTop(SqStack S);Status Push(SqStack *S,SElemType e);Status Pop(SqStack *S,SElemType *e);Status StackTraverse(SqStack S,Status (*visit)();Status InitStack(SqStack *S) (*S)=(SqStack *)malloc(sizeof(SqStack); (*S)-base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType); if(!(*S)-bas
18、e)exit(OVERFLOW); (*S)-top=(*S)-base; (*S)-stacksize=STACK_INIT_SIZE; return OK;Status DestroyStack(SqStack *S) free(S-base); free(S);Status 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) int i; SElemType *p
19、; i=0; p=S.top; while(p!=S.base) p+; i+; SElemType GetTop(SqStack S) if(S.top=S.base) return ERROR; return *(S.top-1);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; */ *(S-top+)=e; return OK;Status Pop(SqStack *S,SElemType *e) if(S-top=S-base) return ERROR; *e=*(-(S-top); return OK;Status StackTraverse(SqStack S,Status (*visit)() while(S.topS.base) visit(-S.top);
- 温馨提示:
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。