第 1 页 共 17 页南京信息工程大学 实验（实习）报告实验（实习）名称 栈和队列 日期 2017.11.8 得分 指导老师 崔萌萌 系 计算机系 专业 软件工程 年级 2016 班次 (1) 姓名 学号 一、实验目的1、学习栈的顺序存储和实现，会进行栈的基本操作2、掌握递归3、学习队列的顺序存储、链式存储，会进行队列的基本操作4、掌握循环队列的表示和基本操作二、实验内容1、用栈解决以下问题：（1）对于输入的任意一个非负十进制数，显示输出与其等值的八进制数，写出程序。（2）表达式求值，写出程序。2、用递归写出以下程序：（1）求 n！。（2）汉诺塔程序，并截图显示 3、4、5 个盘子的移动步骤,写出移动 6 个盘子的移动次数。第 2 页 共 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(“%d“,printf(“请输入目标进制： “);第 3 页 共 17 页scanf(“%d“,printf(“转换为%d 进制： “,radix);while(n) s.push(n%radix);n /= radix;while(!s.empty() /非空printf(“%d“,s.top();s.pop();printf(“n“);return 0;运行结果如下：2.2 求表达式的值代码如下：#include #include #include #include #define true 1 #define false 0 #define OPSETSIZE 8 typedef int Status;第 4 页 共 17 页unsigned char Prior88 = /运算符优先级表/ + - * / ( ) # /*+*/ , , /*#*/ , ; typedef struct StackChar /StackChar 类型的结点 SCchar c; struct StackChar *next; SC;typedef struct StackFloat /StackFloat 类型的结点 SF float f; struct StackFloat *next; SF;SC* Push(SC* s,char c) /SC 类型的指针 Push，返回 pSC* p = (SC* )malloc(sizeof(SC); p-c = c; p-next = s; return p; SF* Push(SF* s,float f) /SF 类型的指针 Push，返回 p第 5 页 共 17 页SF* p = (SF* )malloc(sizeof(SF); p-f = f; p-next = s; return p; SC* Pop(SC* s) /SC 类型的指针 PopSC* q = s; s = s-next; free(q); return s; SF* Pop(SF* s) /SF 类型的指针 PopSF* q = s; s = s-next; free(q); return s; float Operate(float a,unsigned char theta, float b) /计算函数Operateswitch(theta) case +: return a+b; case -: return a-b; case *: return a*b; case /: return a/b; 第 6 页 共 17 页case : return pow(a,b); default : return 0; char OPSETOPSETSIZE = +,-,*,/,(,),#,; Status In(char Test,char *TestOp)int Find = false; for (int i=0; ic != #) if (!In(*c, OPSET) Dr0 = *c; strcat(TempData,Dr); /字符串连接函数 c+; if (In(*c, OPSET) Data = atof(TempData); /字符串转换函数(double) OPND = Push(OPND, Data); strcpy(TempData,“0“); else /不是运算符则进栈 switch (precede(OPTR-c, *c) case : /退栈并将运算结果入栈 theta = OPTR-c; OPTR = Pop(OPTR); b = OPND-f; OPND = Pop(OPND); a = OPND-f; OPND = Pop(OPND); OPND = Push(OPND, Operate(a, theta, b); break; 第 8 页 共 17 页 return OPND-f; int main() char s128;printf(“请输入表达式: n“); scanf(“%s“,s);printf(“该表达式的值为: n“); printf(“%s = “,s);printf(“%gn“,EvaluateExpression(s); / %g return 0;运行结果如下：2.递归的使用2.1 求 n！：代码如下：#include int Fact(int n) if(0 = n) return 1;第 9 页 共 17 页else return n*Fact(n-1);int main() int n;scanf(“%d“,printf(“%d 的阶乘为：“,n); printf(“%d“,Fact(n);return 0;运行结果如下：2.2 哈诺塔：代码如下：#include int Hanoi(int n,char a,char b,char c)if(1 = n) printf(“%c-%d-%c “,a,1,c);elseHanoi(n-1,a,c,b);printf(“%c-%d-%c “,a,n,c);Hanoi(n-1,b,a,c);return 0;第 10 页 共 17 页int main()int n;char a=A,b=B,c=C;printf(“请输入汉诺塔的层数: “);scanf(“%d“,Hanoi(n,a,b,c);printf(“n“);return 0;运行结果如下：n=3 时n=4 时n=5 时n=6 时由 3,4,5 可推知 n 层哈诺塔需要移动 次；12n第 11 页 共 17 页n=6 时,需要移动 63 次。3. 队列的出队和入队 代码如下：#include #include #include #define OK 1 #define ERROR 0 #define OVERFLOW -1typedef char ElemType; /default ElemType = char typedef int Status; /Return Value /*队列节点的申明*/ typedef struct node ElemType data; struct node *next; QNode,*QuePtr; /*链式队列*/ typedef struct QuePtr front; /队头指针 QuePtr rear; /队尾指针，指向队尾元素的下一位 LinkQueue; Status InitQueue(LinkQueue *q) /初始化队列 q-front = q-rear = (QuePtr)malloc(sizeof(QNode); q-front-next = NULL; return OK; Status EnQueue(LinkQueue *q,ElemType e) /将元素 e 入队列 QuePtr temp = (QuePtr)malloc(sizeof(QNode); /创建新结点 if(!temp) return OVERFLOW;第 12 页 共 17 页temp-data = e; /初始化新结点的数据为 e temp-next = NULL; /队列只能从队尾插入所以下一个结点初始化为 NULL q-rear-next = temp; q-rear = temp; /将指向队尾的指针指向新结点 return OK; Status CreateQueue(LinkQueue *q /*,char a*/) /创建队列 InitQueue(q);int k;printf(“请输入队列元素个数：“);scanf(“%d“,printf(“请输入队列元素: n“);for(int i=0;ifront = q-rear) return ERROR; QuePtr temp = q-front-next; /初始化 temp 为要出队的结点的指针 if(q-front-next = q-rear) q-rear = q-front; *e = temp-data; /将出队的数据元素存入*e q-front-next = temp-next; /下一个结点成为队头 free(temp); /删除要出队的结点 return OK； 第 13 页 共 17 页bool IsEmpty(LinkQueue *q) /判断队列是否为空 if(q-front = q-rear) return true; return false; int GetQueueLength(LinkQueue *q) /返回队列的长度 QuePtr temp = q-front; int i = 0; while(temp != q-rear) +i; temp = temp-next; return i; Status Print(LinkQueue *q) /打印队列的元素 if(q-front = q-rear) return ERROR; QuePtr temp = q-front-next; while(temp != q-rear) printf(“%c “,temp-data); temp = temp-next; printf(“%c“,temp