数据结构教程第十七课实验三栈的表示与实现及栈的应用

《数据结构教程第十七课实验三栈的表示与实现及栈的应用》由会员分享，可在线阅读，更多相关《数据结构教程第十七课实验三栈的表示与实现及栈的应用（11页珍藏版）》请在装配图网上搜索。

1、►  数据结构教程 第十七课 实验三：栈的表示与实现及栈的应用 数据结构教程 第十七课 实验三：栈的表示与实现及栈的应用 教学目的： 掌握栈的存储表示方式和栈基本操作的实现方法 教学重点： 栈的基本操作实现方法，栈的应用 教学难点： 栈的存储表示 实验内容： 一、栈的实现 实现栈的顺序存储。 栈实现示例 #include #include #include #define ERROR 0 #define TRUE 1 #define FALSE 0 #define OK 1 #define EQUAL

2、1 #define OVERFLOW -1 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef int Status ; struct STU{ char name[20]; char stuno[10]; int age; int score; }; typedef struct STU SElemType; struct STACK { SElemType *base; SElemType *top; int stacksize; }; t

3、ypedef 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 S); Status GetTop(SqStack S,SElemType *e); Status Push(SqStack *S,SElemType e);

4、 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)->base)exit(OVERFLOW); (*S)->top=(*S)->base

5、; (*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(

6、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-

7、>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(SqSta

8、ck *S,SElemType *e) { if(S->top==S->base) return ERROR; *e=*--S->top; return OK; } Status StackPrintElem(SElemType * e) { printf("%s %s %d %d\n",e->name,e->stuno,e->age,e->score); } Status StackTraverse(SqStack S,Status (*visit)()) { while(S.top!=S.base) visit(--S.to

9、p); } main() { SElemType e; SqStack *Sa; clrscr(); printf("\n\n-------------------SqStack Demo is running...----------------\n\n"); printf("First is Push function.\n"); InitStack(&Sa); strcpy(e.name,"stu1"); strcpy(e.stuno,"100001"); e.age=80; e.score=1000;

10、 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(" N

11、ow Stack has another element.\n"); StackTraverse(*Sa,StackPrintElem); printf(" Now Pop Stack,the top elem put into variable e.\n"); Pop(Sa,&e); printf("%s\n%s\n%d\n%d\n",e.name,e.stuno,e.age,e.score); printf(" Let's see the left of Stack's elem:\n"); StackTraverse(*Sa,Stack

12、PrintElem); getch(); printf("\n\n\nWelcom to visit \n\n"); } 二、栈的应用 １、利用栈实现数制转换 ２、利用栈实现单行编辑 以上任选一题。 数制转换示例 #include #include #include typedef int SElemType; #include "stack.h" Status visit(SElemType * e) { printf(" %d ", *e); } void conve

13、rsion() { pSqStack S; SElemType e; int n; InitStack(&S); printf("Input a number to convert to OCT:\n"); scanf("%d",&n); if(n<0) { printf("\nThe number must be over 0."); return; } if(!n) Push(S,0); while(n){ Push(S,n%8); n=n/8; } printf("the

14、 result is: "); while(!StackEmpty(*S)){ Pop(S,&e); printf("%d",e); } } main() { printf("\n\n\n\n"); conversion(); getch(); printf("\n\nWelcome to visit !"); } 单行编辑示例 #include #include #include #include #define EOFILE

15、 '`' typedef char SElemType; #include "stack.h" Status visit(SElemType * e) { printf("%c", *e); } char OP[10]={'+','-','*','/','(',')','#'}; int precede[7][7]={ 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,

16、1,1,0,1,1, 2,2,2,2,2,0,3}; int In(char c,char *op) { int i=0; while(i<7) if(c==op[i++]) return 1; return 0; } char Precede(char op,char c) { int pos_op; int pos_c; int i; for(i=0;i<7;i++) { if(op==OP[i]) pos_op=i; if(c==OP[i]) pos

17、_c=i; } switch(precede[pos_op][pos_c]) { case 1: return '>'; 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 '*':retur

18、n (a-'0')*(b-'0')+'0'; case '/':return (a-'0')/(b-'0')+'0'; } } char EvaluateExpression() { SqStack *OPND,*OPTR; char c,x,theta; char a,b; InitStack(&OPTR); Push(OPTR,'#'); InitStack(&OPND); c=getchar(); while(c!='#'||GetTop(*OPTR)!='#') { if(!In(c,

19、OP)) {Push(OPND,c);c=getchar();} else switch(Precede(GetTop(*OPTR),c)) { case '<': Push(OPTR,c); c=getchar(); break; case '=': Pop(OPTR,&x); c=getchar(); break; case '>': Pop(OPTR,&theta); Pop(OPND,&b);

20、 Pop(OPND,&a); Push(OPND,Operate(a,theta,b)); break; } } c=GetTop(*OPND); DestroyStack(OPTR); DestroyStack(OPND); return c; } main() { char i; printf("\n\n\n\nOnly within 0..9 evaluation,input a expression end with symbol #:\n"); i=EvaluateExpress

21、ion(); printf("\nThis expression's result is: "); printf("%d\n\n\n\n",i-'0'); printf("\n\nWelcome to visit !"); } 这里是实现栈的头文件   #include "simuc.h" #define OVERFLOW -1 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef int Status; struct STACK { SElemType *b

22、ase; 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 S); SElemType GetTop(SqStack S

23、); 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)->base)

24、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

25、 return FALSE; } int StackLength(SqStack S) { int i; SElemType *p; 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

26、->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.top>S.base) visit(--S.top); }