1、数据结构 实验二 查找与排序 实验二 栈、队列的实现及应用 实验课程名：高级语言程序设计 专业班级： 11计科一班 学 号： 姓 名： 实验时间： 12.11 实验地点： 教师： 一、实验目的和要求1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。2、掌握栈和队列的特点，即先进后出与先进先出的原则。3、掌握栈和队列的基本操作实现方法。二、实验的内容和步骤（一）1、实现栈的顺序存储和链式存储代码：# define STACK_INIT_SIZE 100# define STACKINCREMENT 10# define MAXQSIZE 100# define OK 1#
2、define ERROR 0#include stdio.h#include iostream.h#include malloc.h#include stdlib.htypedef int SElemType;typedef struct /define structure SqStack() SElemType *base; SElemType *top; int stacksize;SqStack;int InitStack(SqStack &S) /InitStack() sub-function S.base=(SElemType *)malloc(STACK_INIT_SIZE*si
3、zeof(SElemType); if(!S.base) coutendlS.stacksize) S.base=(SElemType *)realloc(S.base,(S.stacksize+ STACKINCREMENT*sizeof(SElemType); if(!S.base) coutendlOverflow!; return (ERROR); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return (OK); /Push() endint Pop(SqStack &S,SElemType &
4、e) /Pop() sub-function if(S.top=S.base) coutendlj; for(n=0;n0;n-) Pop(S,e); printf(%d ,e); printf(n);运行结果（二）1、利用栈实现数制转换代码：#include#include#include# include# define STACK_INIT_SIZE 100# define STACKINCREMENT 10# define MAXQSIZE 100# define OK 1# define ERROR 0typedef int SElemType;typedef struct SEle
5、mType *base; SElemType *top; int stacksize;SqStack;int InitStack(SqStack &S) S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S.base) coutendlAllocate 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) co
6、utendlS.stacksize) S.base=(SElemType *)realloc(S.base,(S.stacksize+ STACKINCREMENT*sizeof(SElemType); if(!S.base) coutendlOverflow!; return 0; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return 1; int Pop(SqStack &S,SElemType &e) if(S.top=S.base) coutendlIts a empty SqStack!; r
7、eturn 0; e=*-S.top; return 1;void Conversion() SqStack S; SElemType N,e; InitStack(S); printf(请输入想转数据：); scanf(%d,&N); while(N) Push(S,N%8); N=N/8; printf(所给数据进制转换后为：); while(!StackEmpty(S) Pop(S,e); printf(%d,e); coutendl;void main() Conversion(); 3、运行结果（三）1、利用栈实现表达式求值2、源代码#include#include#define S
8、TACK_INIT_SIZE 100#define STACKINCREMENT 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
9、=STACK_INIT_SIZE; int GetTop (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;
10、S.stacksize+=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=; break;case*: case/: if(a1=*|a1=/|a1=) r=; else r=; break;case(:if(a1=) cout括号匹配错误!end
11、l; exit(-1); else r=; break;case): if(a1=() r=; else if(a1=#) couterror!没有左括号; break;case#: switch(a1) case#: r=; break; case(:couterror!没有右括号; break;return r;char In(char d)switch(d)case+:case-:case*:case/:case(:case):case#:return true;default:return false;SElemType Operate( SElemType a, SElemType
12、theta, SElemType b )char n=char(theta);switch(n) case+:return a+b;case-:return a-b;case*:return a*b; default:if(b!=0) return a/b;elsecouterror!除数不能为零endl; exit(-1);SElemType EvaluateExpression() SqStack OPTR,OPND;char c;char Data11;SElemType a,b,d,e;InitStack(OPTR);InitStack(OPND);Push(OPTR,#);c=get
13、char();GetTop(OPTR,e);while(c!=#|e!=#)if(In(c) switch(Precede(e,c) case: Pop(OPTR,e); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,e,b); break; else if(c=0&c=0&c=9|c=.) Datai=c;i+; c=getchar(); Datai=0; d=atof(Data); Push(OPND,d);else couterror!输入错误!endl; exit(-1);GetTop(OPTR,e);GetTop(OPND,e);retu
14、rn e;int main()SElemType result;cout请输入要计算的表达式，并以#号结束endl;result=EvaluateExpression();cout结果为:resultnext=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(s
15、izeof(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,QElemType &e) if(Q.front=Q.rear) printf(If it was deleted, its empty !); return (ERROR); QNode *p; p=Q.front-ne
16、xt; e=p-data; Q.front-next=p-next; free(p); return (OK); int QueueTraverse(LinkQueue Q,void(*vi)(QElemType)QueuePtr p; p=Q.front-next; while(p) vi(p-data);p=p-next; printf(n);return OK;void visit(QElemType i)printf(%d,i);void main()int i,j;int e; QElemType d; LinkQueue q; i=InitQueue(q); if(i)for(j=1;je; EnQueue(q,e); QueueTraverse(q,visit); DeQueue(q,d); printf(删除了队头元素%dn,d); DestroyQueue(q); printf(销毁队列后，q.front=%u q.rear=%un,q.front, q.rear);运行结果三、结论（写本次实验的收获）了解栈和队列的顺序存储结构和链式存储，例如：先进后出与先进先出的原则，掌握栈和队列的基本操作方法，以及数值转换，删除队列元素的方法。
