数据结构栈和队列实验报告 - 图文

南京信息工程大学 实验（实习）报告

实验（实习）名称 栈和队列 日期 2017.11.8 得分 指导老师 崔萌萌 系 计算机系 专业 软件工程 年级 2016 班次 (1) 姓名 学号

一、实验目的

1、学习栈的顺序存储和实现，会进行栈的基本操作 2、掌握递归

3、学习队列的顺序存储、链式存储，会进行队列的基本操作 4、掌握循环队列的表示和基本操作

二、实验内容

1、用栈解决以下问题：

（1）对于输入的任意一个非负十进制数，显示输出与其等值的八进制数，写出程序。 （2）表达式求值，写出程序。

2、用递归写出以下程序： （1）求n！。

（2）汉诺塔程序，并截图显示3、4、5个盘子的移动步骤,写出移动6个盘子的移动次数。

第 1 页 共 17 页

3、编程实现：（1）创建队列，将asdfghjkl依次入队。（2）将队列asdfghjkl依次出队。 4、编程实现创建一个最多6个元素的循环队列、将ABCDEF依次入队，判断循环队列是否队满。

三、实验步骤

1.栈的使用

1.1 用栈实现进制的转换： 代码如下：

#include

#include using namespace std;

int main() {

stack s; //栈s; int n,radix;

printf(\请输入要转换的十进制非负整数： \ scanf(\

printf(\请输入目标进制： \ scanf(\

第 2 页 共 17 页

printf(\转换为%d进制： \

while(n) {

s.push(n%radix); n /= radix;

}

while(!s.empty()) { //非空

printf(\ s.pop();

}

printf(\ return 0; }

运行结果如下：

2.2 求表达式的值 代码如下：

#include

#include #include #include

#define true 1 #define false 0 #define OPSETSIZE 8

typedef int Status;

第 3 页 共 17 页

unsigned char Prior[8][8] = { //运算符优先级表 // '+' '-' '*' '/' '(' ')' '#' '^' /*'+'*/ '>','>','<','<','<','>','>','<', /*'-'*/ '>','>','<','<','<','>','>','<', /*'*'*/ '>','>','>','>','<','>','>','<', /*'/'*/ '>','>','>','>','<','>','>','<', /*'('*/ '<','<','<','<','<','=',' ','<', /*')'*/ '>','>','>','>',' ','>','>','>', /*'#'*/ '<','<','<','<','<',' ','=','<', /*'^'*/ '>','>','>','>','<','>','>','>'

};

typedef struct StackChar { //StackChar类型的结点SC char c;

struct StackChar *next;

}SC;

typedef struct StackFloat { //StackFloat类型的结点SF float f;

struct StackFloat *next;

}SF;

SC* Push(SC* s,char c) //SC类型的指针Push，返回p {

SC* p = (SC* )malloc(sizeof(SC)); p->c = c; p->next = s; return p;

}

SF* Push(SF* s,float f) //SF类型的指针Push，返回p {

第 4 页 共 17 页