本文共 7319 字，大约阅读时间需要 24 分钟。
东北林业大学
目录
实验二
| 实验名称：栈、队列 | |
| 实验室名称：905 | 实验台号：18 |
| 学生姓名：** | 专业班级：2016级计算机科学与技术四班 |
| 指导教师：王阿川(教授) | 实验日期： 2018-04-25 |
一、实验目的
1．掌握栈、队列的思想及其存储实现。
2．掌握栈、队列的常见算法的程序实现。
二、实验仪器及环境：
PC计算机；windows 10操作系统、codeblocks17.12;
三、实验内容及结果（按照具体实验题目，按照如下格式书写）
1. 采用链式存储实现栈的初始化、入栈、出栈操作。
存储结构：
typedef int Status;
typedef int SElemType;
typedef struct SNode{
SElemTypedata;
structSNode *next;
}SNode,*LinkStack;
程序：
#includeusing namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef int SElemType;typedef struct SNode{ SElemTypedata; structSNode *next;}SNode,*LinkStack;//链栈的初始化Status InitStack (LinkStack &S){ S=NULL; return OK;}// 链栈的入栈Status Push(LinkStack &S , SElemType e){ SNode*p = new SNode; if(!p) { returnOVERFLOW; } p->data= e; p->next= S; S= p; returnOK;}//链栈的出栈Status Pop (LinkStack &S,SElemType &e){ SNode*p; if(!S) returnERROR; e= S->data; p= S; S= S->next; deletep; returnOK;}int main(){ LinkStacks; SElemTypee; cout<<"进栈元素依次为："<
2.采用链式存储实现栈的初始化、入栈、出栈操作。
存储结构：
typedefint Status;
typedefint SElemType;
typedefstruct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
程序；
#include#include usingnamespace std;#defineOK 1#defineERROR 0#defineOVERFLOW -2#defineMAXSIZE 100typedefint Status;typedefint SElemType;typedefstruct{ SElemType *base; SElemType *top; int stacksize;}SqStack;//顺序栈的初始化StatusInitStack(SqStack &S){ S.base = new SElemType[MAXSIZE]; if(!S.base) exit (OVERFLOW); S.top = S.base; S.stacksize = MAXSIZE; return OK;}//顺序栈的入栈StatusPush(SqStack &S,SElemType &e){ if(S.top-S.base==S.stacksize) return ERROR; *(S.top++) = e; //元素e压入栈顶，栈顶指针加1 return OK;}//顺序栈的出栈StatusPop(SqStack &S,SElemType &e){ if(S.base == S.top) return ERROR; e = *(--S.top); //栈顶指针减1，将栈顶元素赋给e return OK;}intmain(){ SqStack s; SElemType e; SElemType t; cout<<"进栈元素依次为："<
3.采用链式存储实现队列的初始化、入队、出队操作。
存储结构：
typedefint QElemType;
typedefint Status;
typedefstruct QNode{
QElemType data;
QNode *next;
}QNode,*QueuePtr;
typedefstruct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
程序：
#includeusingnamespace std;#defineOK 1#defineERROR 0#defineOVERFLOW -2typedefint QElemType;typedefint Status;typedefstruct QNode{ QElemType data; QNode *next;}QNode,*QueuePtr;typedefstruct{ QueuePtr front; QueuePtr rear;}LinkQueue; //链队的初始化StatusInitQueue(LinkQueue &Q){ Q.front = new QNode; if(Q.front == NULL) { return OVERFLOW; } Q.front->next = NULL; Q.rear = Q.front; return OK;}//链队的入队StatusEnQueue(LinkQueue &Q,QElemType e){ QNode *p = new QNode; if(p == NULL) { return OVERFLOW; } p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; // 修改队尾指针 return OK;}//链队的出队StatusDeQueue(LinkQueue &Q,QElemType &e){ if(Q.front == Q.rear) { return ERROR; } QNode *p = Q.front->next; e = p->data; Q.front->next = p->next; if(Q.rear == p) { Q.rear = Q.front; } delete p; return OK;}intmain(){ LinkQueue Q; QElemType e; cout<<"进链队的元素依次为："<
4．采用顺序存储实现循环队列的初始化、入队、出队操作。
存储结构：
typedef int QElemType;
typedef int Status;
typedef struct{
QElemType *base;
int front; //头指针
int rear; //尾指针
}SqQueue;
程序：
#includeusing namespace std;#define MAXQSIZE 100#define OK 1#define ERROR 0#define OVERFLOW -2typedef int QElemType;typedef int Status;typedef struct{ QElemType *base; int front; //头指针 int rear; //尾指针}SqQueue;//循环队列的初始化Status InitQueue(SqQueue &Q){ Q.base = newQElemType[MAXQSIZE]; if(!Q.base) { return OVERFLOW; } Q.front = Q.rear=0; return OK;}//循环队列的入队Status EnQueue(SqQueue &Q,QElemType e){ if((Q.rear+1)%MAXQSIZE ==Q.front) { return ERROR;//队列满 } Q.base[Q.rear] = e; Q.rear =(Q.rear+1)%MAXQSIZE; return OK;}//循环队列的出队Status DeQueue(SqQueue &Q,QElemType &e){ if(Q.rear == Q.front) { return ERROR; } e = Q.base[Q.front]; Q.front =(Q.front+1)%MAXQSIZE; return OK;}int main(){ SqQueue Q; QElemType e; cout<<"进循环队列的元素依次为："<
*5．综合训练:1)利用栈实现表达式求值算法。
程序：
/***链栈实现表达式求值***/#includeusing namespace std;const char oper[7] = {'+','-','*','/','(',')','#'};#define OK 1#define ERROR 0#define OVERFLOW -2typedef char SElemType;typedef int Status;typedef struct SNode{ int data; struct SNode *next;}SNode,*LinkStack;Status InitStack(LinkStack &S){ S = NULL; return OK;}bool StackEmpty(LinkStack S){ if(!S) return true; return false;}Status Push(LinkStack &S,SElemType e){ SNode *p = new SNode; if(!p) { return OVERFLOW; } p->data = e; p->next = S; S = p; return OK;}Status Pop(LinkStack &S,SElemType &e){ SNode *p; if(!S) return ERROR; e = S->data; p = S; S = S->next; delete p; return OK;}Status GetTop(LinkStack &S,SElemType &e){ if(!S) return ERROR; e = S->data; return OK;}bool In(char ch){//判断ch是否为运算符 for(int i = 0;i < 7;i ++) { if(ch == oper[i]) { return true; } } return false;}char Precede(char theta1,char theta2){//判断运算符优先级 if((theta1 == '('&&theta2 == ')')||(theta1 == '#'&&theta2 == '#')) { return '='; } else if(theta1 == '('||theta1 == '#'||theta2 == '(' ||(theta1 == '+'||theta1 == '-')&&(theta2 == '*'||theta2 == '/')) { return '<'; } else return '>';}char Operate(char first,char theta,char second){//计算两数运算结果 switch(theta) { case '+': return (first - '0')+(second - '0')+ 48; case '-': return (first - '0')-(second - '0')+ 48; case '*': return (first - '0')*(second - '0')+ 48; case '/': return (first - '0')/(second - '0')+ 48; } return 0;}// 表达式求值char EvaluateExpression(){ // 算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和操作数栈， // OP 为运算符集合 LinkStack OPTR,OPND; char ch,theta,a,b,x,top; InitStack ( OPTR); Push (OPTR,'#'); InitStack ( OPND); ch = getchar(); while (ch != '#' || (GetTop(OPTR,top) ,top!= '#') ) { if (!In(ch)) { Push(OPND, ch); ch = getchar(); } // ch不是运算符则进栈 else switch (GetTop(OPTR, top),Precede(top,ch)) { //比较OPTR的栈顶元素和ch的优先权 case '<': //当前字符ch压入OPTR栈，读入下一字符ch Push(OPTR, ch); ch = getchar(); break; case '>': //弹出OPTR栈顶的运算符进行相应运算，并将运算结果入栈 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b)); break; case '=': //脱括号并接收下一字符 Pop(OPTR, x); ch = getchar(); break; } // switch } // while GetTop(OPND,ch); return ch;} // EvaluateExpressionint main(){ cout<<"请输入要计算的表达式（操作数和结果都在0-9的范围内，以#结束）："<
四、实验心得体会：（包括遇到的问题及解决办法）
（1）从数据结构的定义看，栈和队列也是一种线性表。其与线性表的不同之处在于栈和队列的相关运算具有特殊性，只是线性表相关运算的一个子集。一般线性表的上的插入、删除运算不受限制，而栈和队列上的插入、删除运算受某种特殊限制。因此。栈和队列也称为操作受限的线性表。
（2）栈在计算机中的地位很重要，例如表达式求值，函数调用时都需要用到栈的结构。
算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。
（3）我感觉，最重要的还是把基础掌握，掌握了基础，很多问题就不是问题，只要按部就班就可以了。这次试验，我感觉自己还有很多比较薄弱的地方，我感到自己对于指针的理解还不是很透彻，对于指针的运用也不是十分的熟练，因此，在后的学习中，我会更加重视这方面的学习，力争掌握这门学科。
五、指导教师意见及成绩
签名:
年 月 日
发表评论
最新留言
关于作者
