计算机科学与工程学院
《算法与数据结构》试验报告[二]
专业班级10级计算机工程02 试验地点计算机大楼计工教研室学生学号1005080222 指导教师蔡琼
学生姓名肖宇博试验时间2012-4-14
试验项目算法与数据结构
试验类别基础性（）设计性（）综合性（√）其它（）
试验目的及要求（1）掌握栈的特点及其存储方法；（2）掌握栈的常见算法以及程序实现；（3）了解递归的工作过程。
成
绩评定表
类别评分标准分值得分合计
上机表现积极出勤、遵守纪律
主动完成设计任务
30分
程序与报告程序代码规范、功能正确
报告详实完整、体现收获
70分
备注：
评阅教师：
日期：年月日
试 验 内 容
一、实验目的和要求
1、实验目的：
（1）掌握栈的特点及其存储方法；
（2）掌握栈的常见算法以及程序实现； （3）了解递归的工作过程。
2、实验内容
Hanoi 塔问题。（要求4个盘子移动，输出中间结果）
3、实验要求：
要求实现4个盘子的移动，用递归和栈实现。
二、设计分析
三个盘子Hanoi 求解示意图如下：
三个盘子汉诺塔算法的运行轨迹：
B A
B C A B C
A C A
B C
(a
(b)
(c (d)
⑸
⑼ ⑶
Hanio(3,A,B,C) Hanio(3,A,B,C) Hanio(2,A,C,B)
Hanio(2,A,C,B) Hanio(1,A,B,C) Hanio(1,A,B,C) Move (A,C) Move (A,B) Hanio(1,C,A,B)
Hanio(1,C,A,B) Move (C,B)
Move (A,B)
Hanio(2,B,A,C)
Hanio(2,B,A,C) Hanio(1,B,C,A)
Hanio(1,B,C,A) Move (B,C) Hanio(1,A,B,C)
Hanio(1,A,B,C) Move (A,C)
Move (B,A)
递归第一层 递归第二层 递归第三层 ⑴ ⑵
⑷
⑹
⑺ ⑻
⑽ ⑾
⑿
⒀
⒁
三、源代码
#include
#include
#define maxsize 20
typedef int datatype; //数据结构的类型
typedef struct
{
int top;
datatype data[maxsize];
char flat;
}sqstack; //栈的定义
void inisqstack(sqstack *&s,char ch) //初始化函数！{
s=(sqstack *)malloc(sizeof(sqstack));
s->top=-1;
s->flat=ch;
}
void push(sqstack *&s,datatype e) //进栈函数
{
s->top++;
s->data[s->top]=e;
}
void pop(sqstack *&s,datatype &e) //出栈函数
{
e=s->data[s->top];
s->top--;
}
void Dispstack(sqstack *s) //显示函数
{
for(int i=s->top;i>=0;i--)
{
printf("%d\t",s->data[i]);
}
printf("\n");
}
void Hanio(int n,sqstack *A,sqstack *B,sqstack *C) //汉诺塔主程序
{
int e1;
if(n==1)
{
printf("把%c的%d号盘移到
到%c\n",A->flat,A->data[A->top],C->flat);
pop(A,e1);
push(C,e1);
printf("-----%c还剩下-------------",A->flat);
if(A->top==-1)
{
printf("0");
printf("\n");
}
else
Dispstack(A);
printf("-----%c还剩下-------------",B->flat);
if(B->top==-1)
{
printf("0");
printf("\n");
}
else
Dispstack(B);
printf("-----%c还剩下-------------",C->flat);
if(C->top==-1)
{
printf("0");
printf("\n");
}
else
Dispstack(C);
}
else
{
Hanio(n-1,A,C,B);
pop(A,e1);
push(C,e1);
printf("把%c的%d号盘移到
到%c\n",A->flat,e1,C->flat);
Hanio(n-1,B,A,C);
