湖北理工黄石理工数据结构实验 实验三栈队列的实现及应用二

1、验证性实验三 栈、队列的实现及应用实验课程名：数据结构专业班级： 09计科一班 学号： * 姓名： * 实验时间： 2010.11.25 实验地点： k4-206 指导教师： 祁文青 一、实验目的和要求1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。2、掌握栈和队列的特点，即先进后出与先进先出的原则。3、掌握栈和队列的基本操作实现方法。二、实验内容任务1:实现栈的顺序存储和链式存储#include "stdio.h"#include "stdlib.h"#include "malloc.h"#include &

2、quot;iostream.h"# define STACK_INIT_SIZE 100# define STACKINCREMENT 10# define MAXQSIZE 100# define OK 1# define ERROR 0typedef int SElemType;typedef struct SElemType *base; SElemType *top; int stacksize;SqStack;int InitStack(SqStack &S) S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SEl

3、emType); if(!S.base) cout<<endl<<"Allocate space failure !" return (ERROR); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return (OK);int Push(SqStack &S,SElemType e) if(S.top-S.base>S.stacksize)S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT*sizeof(SElemType)

4、;if(!S.base) cout<<endl<<"Overflow!"return (ERROR); elseS.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT;*S.top+=e; return (OK);int Pop(SqStack &S,SElemType &e) if(S.top=S.base) cout<<endl<<"It's a empty SqStack!" return (ERROR); e=*-S.top

5、; return (OK);void main()SqStack S;SElemType e;InitStack(S); int j,n;cin >>j;for(n=0;n<j;n+)scanf("%d",&e);Push(S,e);for(n=j;n>0;n-) Pop(S,e);printf("%d ",e);printf("n");实验结果:任务2、利用栈实现数制转换#include<stdio.h>#include<stdlib.h>#include<malloc.

6、h># include<iostream.h># define STACK_INIT_SIZE 100# define STACKINCREMENT 10# define MAXQSIZE 100# define OK 1# define ERROR 0typedef int SElemType;typedef struct SElemType *base; SElemType *top; int stacksize;SqStack;int InitStack(SqStack &S) S.base=(SElemType *)malloc(STACK_INIT_SIZE

7、*sizeof(SElemType); if(!S.base) cout<<endl<<"Allocate space failure !" return 0; S.top=S.base; S.stacksize=STACK_INIT_SIZE;return 1;int GetTop(SqStack S,SElemType &e) if(S.top=S.base) cout<<endl<<"It's a empty SqStack !" return 0; e=*(S.top-1);retu

8、rn 1; int StackEmpty(SqStack S)if(S.top=S.base) return 1; else return 0;int 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) cout<<endl<<"Overflow!" return 0; S.top=S.

9、base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return 1; int Pop(SqStack &S,SElemType &e) if(S.top=S.base) cout<<endl<<"It's a empty SqStack!" return 0; e=*-S.top; return 1;void Conversion() SqStack S; SElemType N,e; InitStack(S); printf("请输入想转数据：&qu

10、ot;);scanf("%d",&N);while(N) Push(S,N%8); N=N/8; printf("所给数据进制转换后为：");while(!StackEmpty(S) Pop(S,e); printf("%d",e);cout<<endl;void main() Conversion(); 实验结果:任务3: 利用栈实现表达式求值#include<iostream>#include<stdlib.h>#define STACK_INIT_SIZE 100#define STA

11、CKINCREMENT 100using namespace std;typedef double SElemType;typedef struct SqStack SElemType *base;SElemType *top;int stacksize;SqStack;void InitStack (SqStack &S)S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base) exit (-1); S.top=S.base;S.stacksize=STACK_INIT_SIZE; int Get

12、Top (SqStack S,SElemType &e) if(S.top=S.base)return false;e=*(S.top-1);return true;int 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(-1); S.top=S.base+S.stacksize; S.stacksize+=

13、STACKINCREMENT;*S.top+=e;return true;int Pop(SqStack &S,SElemType &e)if(S.top=S.base)return false;e=*-S.top; return true ;char Precede(char a1 ,char a2) char r;switch(a2)case'+': case'-': if(a1='('|a1='#') r='<' else r='>' break;case'

14、*': case'/': if(a1='*'|a1='/'|a1=')') r='>' else r='<' break;case'(':if(a1=')') cout<<"括号匹配错误!"<<endl; exit(-1); else r='<' break;case')': if(a1='(') r='=' else if(a1=&#

15、39;#') cout<<"error!没有左括号"<<endl; exit (-1); else r='>' break;case'#': switch(a1) case'#': r='=' break; case'(':cout<<"error!没有右括号"<<endl; exit(-1); default: r='>' break;return r;char In(char d)swit

16、ch(d)case'+':case'-':case'*':case'/':case'(':case')':case'#':return true;default:return false;SElemType Operate( SElemType a, SElemType theta, SElemType b )char n=char(theta);switch(n) case'+':return a+b;case'-':return a-b;case&

17、#39;*':return a*b; default:if(b!=0) return a/b;elsecout<<"error!除数不能为零"<<endl; exit(-1);SElemType EvaluateExpression() SqStack OPTR,OPND;char c;char Data11;SElemType a,b,d,e;InitStack(OPTR);InitStack(OPND);Push(OPTR,'#');c=getchar();GetTop(OPTR,e);while(c!='#

18、9;|e!='#')if(In(c) switch(Precede(e,c) case'<': Push(OPTR,c); c=getchar(); break; case'=': Pop(OPTR,e); c=getchar(); break; case'>': Pop(OPTR,e); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,e,b); break; else if(c>='0'&&c<='9'|c=&#

19、39;.') int i=0; while(c>='0'&&c<='9'|c='.') Datai=c;i+; c=getchar(); Datai='0' d=atof(Data); Push(OPND,d);else cout<<"error!输入错误!"<<endl; exit(-1);GetTop(OPTR,e);GetTop(OPND,e);return e;int main()SElemType result;cout<<&qu

20、ot;请输入要计算的表达式，并以#号结束"<<endl;result=EvaluateExpression();cout<<"结果为:"<<result<<endl;return 0;实验结果:任务4: 实现循环队列的存储和链队列的基本操作#include "stdio.h"#include "stdlib.h"#include "malloc.h"# include "iostream.h"#define MAXQSIZE 5#defi

21、ne Overflow #define OK 1#define ERROR 0typedef int QElemType;typedef struct QNode QElemType data; struct QNode *next;QNode,*QueuePtr;typedef struct LinkQueue QueuePtr front; QueuePtr rear;LinkQueue;int InitQueue(LinkQueue &Q) Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); if(!Q.front) printf(&qu

22、ot;Overflow !"); return (ERROR); Q.front->next=NULL; return (OK);int DestroyQueue(LinkQueue &Q) while(Q.front) Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear; return (OK); int EnQueue(LinkQueue &Q,QElemType e) QNode *p;p=(QueuePtr)malloc(sizeof(QNode); if(!p)printf("Overflow !"); return (ERROR); p->data=e;p->next=NULL; if(Q.front=NULL) Q.front=Q.rear=p;return (OK); Q.rear->next=p; Q.rear=p; return (OK); int DeQueue(LinkQueue &Q,QEl