广 州 商 学 院
2019学年—2020学年第1学期 数据结构实验任务书二
专业名称： 软件技术 实验学时： 2
课程名称：数据结构 任课教师：
实验题目：堆栈的应用
实验环境： Dev C++
实验目的：
1、掌握堆栈的定义；
2、掌握堆栈的基本操作，如初始化、入栈、出栈等。
实验内容：
(1) n阶Hanoi问题递归算法的实现；
(2) n阶Hanoi问题非递归算法的实现；
(3) 比较Hanoi问题递归算法和非递归算法的区别；
(4) 理解和调试算法3.22表达式求值。
实验提示：
1、n阶Hanoi递归算法(算法3.10)
00 void Hannoi(int n,char A,char B,char C)
01 {
02 if(n==1)
03 Move(1,A,C); /* 将1号盘从A杆移到C杆 */
04 else
05 {
06 Hannoi(n-1,A,C,B); /* 将A杆上n-1个盘借助C杆移动到B杆 */
07 Move(n,A,C); /* 将n号盘从A杆移到C杆 */
08 Hannoi(n-1,B,A,C); /* 将B杆上n-1个盘借助A杆移动到C杆 */
09 }
10 }
根据上面算法编写程序并上机调试。
2、n阶Hanoi非递归算法
# include <stdio.h>
struct stack /* 栈结构定义 */
{int n; /* 层数 */
char x,y,z; /* x:原点； y:中间点； z：目标点；*/
}sta[200]; /* 定义数组栈sta */
voidHanniota(intn,charfr,charto,char by)
/* n：层数；fr：原点；to：目标点；by：中间点 */
{int top=-1; /* 初始化栈top=-1 */
int n1,a,b,c; /* n1：层数；a：原点，b：中间点；c：目标点 */
top=top+1;
sta[top].n=n;
sta[top].x=fr;
sta[top].y=by;
sta[top].z=to;
while(top>-1)
{
n1=sta[top].n;
a=sta[top].x;
b=sta[top].y;
c=sta[top].z;
top--;
if(n1>1)
{top++; /* 压栈Hannoi(n1-1,b,c,a) */
sta[top].n=n1-1;
sta[top].x=b;
sta[top].y=a;
sta[top].z=c;
top++; /* 压栈Move(a,c) */
sta[top].n=1;
sta[top].x=a;
sta[top].z=c;
top++; /* 压栈Hannoi(n1-1,a,b,c) */
sta[top].n=n1-1;
sta[top].x=a;
sta[top].y=c;
sta[top].z=b;
}
else
printf("move %c --> %c\n",a,c); /* 一个盘子时直接移动 */
}
}
main()
{
Hanniota(4,'A','B','C'); /* 假设初始时4个盘子 */
}
3、/*表达式求值P79算法3.22*/
实验要求：
(1) 程序要添加适当的注释，程序的书写要采用缩进格式。
(2) 程序要具有一定的健壮性，即当输入数据非法时，程序也能适当地做出反应。
(3) 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。
(4) 根据实验报告模板详细书写实验报告。
(5) 通过学习通的作业模块上传实验报告。实验报告命名为学号-姓名-S2，如20180001-封清扬-S2。
