站内搜索

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

教学目的： 掌握栈的存储表示方式和栈基本操作的实现方法

教学重点： 栈的基本操作实现方法，栈的应用

教学难点： 栈的存储表示

实验内容：

一、栈的实现

实现栈的顺序存储。

栈实现示例

#include<stdio.h>#include<malloc.h>#include<conio.h>#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 10typedef 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;};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);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(SqStack));  (*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.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=(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 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.top);}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;  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 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,StackPrintElem);  getch();  printf("/n/n/nWelcom to visit http://zmofun.topcool.net/n/n");}

 

二、栈的应用

１、利用栈实现数制转换 ２、利用栈实现单行编辑

以上任选一题。

数制转换示例

#include<stdio.h>#include<malloc.h>#include<conio.h>typedef int SElemType;#include "stack.h"Status 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(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 result is:        "); while(!StackEmpty(*S)){   Pop(S,&e);   printf("%d",e); }}main(){  printf("/n/n/n/n");  conversion();  getch();  printf("/n/nWelcome to visit http://zmofun.yeah.net !");}
单行编辑示例
#include<string.h>#include<stdio.h>#include<malloc.h>#include<conio.h>#define EOFILE '`'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,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_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 '*':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;  InitStack(&OPTR);  Push(OPTR,'#');  InitStack(&OPND);  c=getchar();  while(c!='#'||GetTop(*OPTR)!='#')    {      if(!In(c,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);  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=EvaluateExpression();  printf("/nThis expression's result is:   ");  printf("%d/n/n/n/n",i-'0');  printf("/n/nWelcome to visit http://zmofun.yeah.net !");}
 

 

这里是实现栈的头文件

 

#include "simuc.h"#define OVERFLOW -1#define STACK_INIT_SIZE 100#define 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 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)->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.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++;    }}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.top>S.base)     visit(--S.top);}

  • 上一篇：数据结构教程 第十八课 数组的顺序表示与实现
  • 下一篇：数据结构教程 第十六课 串操作应用举例