实验（实训）报告
项目名称 实验3 栈和队列
所属课程名称 数据结构
项目类型 验 证 性
实验(实训)日期 2013.10.
班 级
学 号
姓 名
指导教师 朱 凌
浙江财经学院教务处制
一、实验（实训）概述：
【实验目的】
1. 掌握栈的两种存储实现方法：顺序栈和链式栈；掌握STL栈的使用方法，能用栈求解问题。
2. 掌握队列的两种存储实现方法：顺序队列和链式队列；掌握STL队列的使用方法，能用队列求解问题。
【实验要求】
1. 新建文件夹，并命名为“学号姓名实验1 数据结构概论”，如“0901042001** ×××实验1 数据结构概论”（**和×××部分用自己的学号和姓名替换），该文件夹用于存放实验程序和实验报告。实验报告完成后，请将该文件夹压缩后提交，压缩前请删除各程序的debug目录。
2. 认真记录实验过程及结果，认真回答实验报告中的问题。
3. 及时提交实验报告。
【实施环境】（使用的材料、设备、软件）
Visual C++ 6.0
注意：所有回答的内容用红色字体标明！！！
二、实验（实训）内容：
实验任务一 栈
第1题回答以下问题
(1) 在日常生活中，除课件中提到的例子（超市存放购物车的轨道、折反型的火车站）外，还有哪些事物“处理数据”的方式是按照栈的方式进行的。
回答：
(2) 请根据你的理解，回答在什么情况下可以用栈来存储数据？
回答：
(3) 栈具有后进先出（LIFO）的特性，是因为它使用的存储结构具有这样的特性吗？还是因为其他原因？原因又是什么？
回答：
第2题栈的应用－计算表达式的值
(1) 请将下列中缀表达式转换成等值的后缀表达式。
(2+3)×(19-7) + (6 – 9) – 66/3
75 – 23 + (19 – 11)/(5 – 1) – 15
回答：
(2) 求解(1)中得到的后缀表达式，要求将求解过程列出来。
回答：
第3题顺序栈
请写出顺序栈的实现的主要代码，分别粘贴在下方。
回答：
第4题链式栈
请写出链式栈的实现的主要代码，分别粘贴在下方。
回答：
第5题掌握STL栈stack的使用。
(1) 请写出阶乘函数的递归实现。（主要代码粘贴在下方）
回答：
(2) 请写出阶乘函数的迭代实现。（主要代码粘贴在下方）
回答：
(2) 请写出阶乘函数的非递归实现，要求使用STL栈stack，及其成员函数（主要代码粘贴在下方）
回答：
第6题掌握STL栈stack的使用。
请编写一个程序，测试STL栈stack的使用，要求用到stack的成员函数。
编写一个代码段，弹出栈中所有结点，用STL中的栈实现。
stack<int> S;//假设栈里已经有结点了
请将代码粘贴在下方。
回答：
实验任务二队列
第1题回答以下问题
(1) 请根据你的理解，回答在什么情况下可以用队列来存储数据？
回答：
(2) 本章介绍了四种线性表，分别是顺序表、单链表、栈和队列，请总结这四种线性表的特点（包括优缺点、适用范围）。
回答：
第2题顺序队列
请写出顺序队列的实现的主要代码，分别粘贴在下方。
回答：
第3题链式队列
请写出链式队列的实现的主要代码，分别粘贴在下方。
回答：
第4题掌握STL队列queue的使用。
请用STL的优先级队列模拟Windows操作系统的消息队列。每个消息用一个字符串表示，为“Keyboard”、“Mouse”、“Timer”，分别表示键盘(注意有不同的键盘消息，所以不同的Keyboard消息优先级允许不一样)、鼠标和定时器消息。每个消息有自己的优先级，用整数表示，该值越大表示优先级越高。
输入描述：首先是一个整数n，表示要处理消息的数目，接下来有2n行，每行可能为一个消息（格式为“消息名称优先级”），也可能为“Process”，后者表示处理一个消息(总是处理当前优先级高的消息)。输入数据保证不会出现“在要处理消息时，优先级队列为空”的情形，也能保证在同一时刻，优先级队列中不存在两个优先级相同的消息。
输出描述：输出依次处理的每个消息，格式如样例输出所示。
样例输入/输出如下。
请将代码粘贴在下方。
回答：
第二篇：《数据结构》实验二 栈和队列
《数据结构》实验指导及报告书
2014 / 2015 学年 第 1学期
姓 名：
学 号：
班 级：
指导教师：徐江
计算机科学与工程学院
20##
实验二 栈和队列
一、实验目的
1、掌握栈的结构特性及其入栈，出栈操作；
2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。
二、实验内容和要求
1、阅读下面程序，将函数Push和函数Pop补充完整。要求输入元素序列1 2 3 4 5 e，运行结果如下所示。
#include<stdio.h>
#include<malloc.h>
#define ERROR 0
#define OK 1
#define STACK_INT_SIZE 10 /*存储空间初始分配量*/
#define STACKINCREMENT 5 /*存储空间分配增量*/
typedef int ElemType; /*定义元素的类型*/
typedef struct{
ElemType *base;
ElemType *top;
int stacksize; /*当前已分配的存储空间*/
}SqStack;
int InitStack(SqStack *S); /*构造空栈*/
int push(SqStack *S,ElemType *e); /*入栈*/
int Pop(SqStack *S,ElemType *e); /*出栈*/
int CreateStack(SqStack *S); /*创建栈*/
void PrintStack(SqStack *S); /*出栈并输出栈中元素*/
int InitStack(SqStack *S){
S->base=(ElemType *)malloc(STACK_INT_SIZE *sizeof(ElemType));
if(!S->base) return ERROR;
S->top=S->base;
S->stacksize=STACK_INT_SIZE;
return OK;
}/*InitStack*/
int Push(SqStack *S,ElemType e){
}/*Push*/
int Pop(SqStack *S,ElemType *e){
}/*Pop*/
int CreateStack(SqStack *S){
int e;
if(InitStack(S))
printf("Init Success!\n");
else{
printf("Init Fail!\n");
return ERROR;
}
printf("input data:(Terminated by inputing a character)\n");
while(scanf("%d",&e))
Push(S,e);
return OK;
}/*CreateStack*/
void PrintStack(SqStack *S){
ElemType e;
while(Pop(S,&e))
printf("%3d",e);
}/*Pop_and_Print*/
int main(){
SqStack ss;
printf("\n1-createStack\n");
CreateStack(&ss);
printf("\n2-Pop&Print\n");
PrintStack(&ss);
return 0;
}
l 算法分析：输入元素序列1 2 3 4 5，为什么输出序列为5 4 3 2 1？体现了栈的什么特性？
#include<stdio.h>
#include<malloc.h>
#define ERROR 0
#define OK 1
#define STACK_INT_SIZE 10 /*存储空间初始分配量*/
#define STACKINCREMENT 5 /*存储空间分配增量*/
typedef int ElemType; /*定义元素的类型*/
typedef struct{
ElemType *base;
ElemType *top;
int stacksize; /*当前已分配的存储空间*/
}SqStack;
int InitStack(SqStack *S); /*构造空栈*/
int Push(SqStack *S,ElemType *e); /*入栈*/
int Pop(SqStack *S,ElemType *e); /*出栈*/
int CreateStack(SqStack *S); /*创建栈*/
void PrintStack(SqStack *S); /*出栈并输出栈中元素*/
int InitStack(SqStack *S){
S->base=(ElemType *)malloc(STACK_INT_SIZE *sizeof(ElemType));
if(!S->base) return ERROR;
S->top=S->base;
S->stacksize=STACK_INT_SIZE;
return OK;
}/*InitStack*/
int Push(SqStack *S,ElemType e){
if(S->top-S->base>=S->stacksize)
{
S->base=(ElemType*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S->base) return ERROR;
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*S->top++=e;
return OK;
}/*Push*/
int Pop(SqStack *S,ElemType *e){
if(S->top=S->base)return ERROR;
e= --S->top;
return OK;
}/*Pop*/
int CreateStack(SqStack *S){
int e;
if(InitStack(S))
printf("Init Success!\n");
else{
printf("Init Fail!\n");
return ERROR;
}
printf("input data:(Terminated by inputing a character)\n");
while(scanf("%d",&e))
Push(S,e);
return OK;
}/*CreateStack*/
void PrintStack(SqStack *S){
ElemType e;
while(Pop(S,&e))
printf("%3d",e);
}/*Pop_and_Print*/
int main(){
SqStack ss;
printf("\n1-createStack\n");
CreateStack(&ss);
printf("\n2-Pop&Print\n");
Pop(&ss, &e);
PrintStack(&ss);
return 0;
}
2、在第1题的程序中，编写一个十进制转换为二进制的数制转换算法函数（要求利用栈来实现），并验证其正确性。
l 实现代码
#include<stdio.h>
#include<malloc.h>
#define ERROR 0
#define OK 1
#define STACK_INIT_SIZE 10 /*存ä?储ä¡é空?间?初?始º?分¤?配?量¢?*/
#define STACKINCREMENT 5 /*存ä?储ä¡é空?间?分¤?配?增?量¢?*/
typedef int SElemType; /*定¡§义°?元a素?的Ì?类¤¨¤型¨ª*/
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
int InitStack(SqStack &S);
int CreateStack(SqStack *S);
int GetTop(SqStack S,SElemType &e);
int Push(SqStack &S,SElemType e);
int Pop(SqStack &S,SElemType &e);
void conversion();
void main()
{
int e;
SqStack S;
CreateStack(S);
GetTop( S, e);
Push( S, e);
conversion();
}
int InitStack(SqStack &S)
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if(!S.base)return ERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
}
int CreateStack(SqStack &S)
{
int e;
if(InitStack(S))
printf("Init Success!\n");
else{
printf("Init Fail!\n");
return ERROR;
}
printf("input data:(Terminated by inputing a character)\n");
while(scanf("%d",&e))
Push(S,e);
return OK;
}
int GetTop(SqStack S,SElemType &e)
{
if(S.top==S.base) return ERROR;
e=*(S.top-1);
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));
if(!S.base)return ERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
}
int Pop(SqStack &S,SElemType &e)
{
if(S.top==S.base)return ERROR;
e= *--S.top;
return OK;
}
void conversion()
{
int n,e;
SqStack S;
printf("input data:\n");
scanf("%d",n);
while(n)
{
Push(S,n);
n=n/2;
}
Pop(S,e);
printf("%d",e);
}
3、阅读并运行程序，并分析程序功能。
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define M 20
#define elemtype char
typedef struct
{
elemtype stack[M];
int top;
}
stacknode;
void init(stacknode *st);
void push(stacknode *st,elemtype x);
void pop(stacknode *st);
void init(stacknode *st)
{
st->top=0;
}
void push(stacknode *st,elemtype x)
{
if(st->top==M)
printf("the stack is overflow!\n");
else
{
st->top=st->top+1;
st->stack[st->top]=x;
}
}
void pop(stacknode *st)
{
st->top=st->top-1;
}
int main()
{
char s[M];
int i;
printf("create a empty stack!\n");
stacknode *sp;
sp=malloc(sizeof(stacknode));
init(sp);
printf("input a expression:\n");
gets(s);
for(i=0;i<strlen(s);i++)
{
if(s[i]=='(')
push(sp,s[i]);
if(s[i]==')')
pop(sp);
}
if(sp->top==0)
printf("'('match')'!\n");
else
printf("'('not match')'!\n");
return 0;
}
l 输入：2+((c-d)*6-(f-7)*a)/6
l 运行结果：
l 输入：a-((c-d)*6-(s/3-x)/2
l 运行结果：
l 程序的基本功能：
以下为选做实验：
4、设计算法，将一个表达式转换为后缀表达式，并按照后缀表达式进行计算，得出表达式得结果。
l 实现代码
5、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点（不设队头指针），试编写相应的置空队列、入队列、出队列的算法。
实现代码：
三、实验小结
四、教师评语