数据结构编程-汉诺塔.doc

数据结构课程

Project 3
汉诺塔

Type：Individual
Programmer:
Tester:
Report Writer:
Date of completion:2010/11/10

第一章: 绪论
问题背景描述
汉诺塔游戏是这样的：有三个桩（桩1，桩2和桩3）和N个半径不同的盘子。初始所有的盘子按半径从小到大堆叠在桩1上，半径最小的盘子在最上面。规则：每次只可以移动一个桩上最顶端的盘子到另一个桩上，而且不可以把大盘子堆在小盘子上。问题是要把所有盘子移动到桩3上。
每次用两个整数a (1 <= a <= 3) 和 b (1 <= b <= 3)表示一次移动，表示移动桩a最顶端的盘子到桩b上。如果桩a上至少有一个盘子，而且桩a顶端的盘子可以在不违反规则的情况下移动到桩b上，那么这次移动才是一个有效的移动。
基本要求：
输入：
每次输入包含几个测试样例。
输入的第一行包含一个整数T (1 <= T <= 55)，表示测试样例的个数。后面紧跟T个测试样例。
每个测试样例第一行有两个整数，n (1 <= n <= 10) 和 m (1 <= m <= 12000)，表示有n个盘子，m次移动。后面m行表示具体的移动步骤。
输出：
对每个测试样例，输出一行表示该测试样例最后的移动结果。
（1） 如果所有的盘子移动到桩3之前，第p次（从1开始记）移动是无效的移动，输出-p，忽略后面的移动步骤。
（2） 如果经过p次移动后，所有的盘子都已经移动到桩3，则输出p，并忽略后面的移动步骤。
（3） 其他情况输出0

int main(void)
主函数，打开输入输出文件，将各测试样例送入func( )执行

void func(int n,int m)
操作函数，处理一个测试样例
构造一个三元堆栈数组表示三个桩
将n个盘子从大到小放入桩1
依次进行m次移动，被移栈弹出的盘子压入目的栈
有效或无效移动判断，输出结果
销毁堆栈

void destroy()
关闭输入输出文件
第二章: 算法详述
FILE *fp_in 输入文件指针
FILE *fp_out 输出文件指针
定义堆栈
typedef struct {
int *base; 栈底指针
int *top; 栈顶指针
int stacksize; 栈所占的存储空间大小
}stack；
stack stake[3]; 一个三元栈顶数组，表示三个桩
int T 测试样例的个数
int n 每个测试样例的盘子数
int m 每个测试样例移动的次数
int from 被移桩号
int to 目的桩号
int plate 被移盘子号（从小到大依次为1到n）
int topplate 目的桩原来的顶层盘号
int law 移动合法性判断

int main(void){
for i:=1 to T do
begin
{
输入m,n
送入func( )执行
}
}

void func(int n,int m){
为三个桩构造三个空栈
for j:=n to 1 do
begin
{
stake[0]=push(stake[0],j);
}
for k:=1 to m do
begin
{
fscanf(fp_in, "%d%d",&from,&to)
plate:=getplate(stake[from-1]) 得到移出的盘子号
if(被移桩无盘子) then
fprintf(fp_out, "-%d\n",k)
跳出循环，忽略以后步骤
stake[from-1]:=pop(stake[from-1]) 该桩弹出顶端的盘子
topplate:=getplate(stake[to-1]) 得到目的桩原来的顶层盘子号 stake[to-1]=:push(stake[to-1],plate) 将盘子移入该桩
if(被移动盘子比原来桩顶盘子大) then
fprintf(fp_out, "-%d\n",k)
跳出循环，忽略以后步骤
else if(桩3的盘子数为n) then
fprintf(fp_out, "%d\n",k)
跳出循环，忽略以后步骤
}
if(k<=m) then
for(i=k+1;i<=m;i++){
fscanf(fp_in, "%d%d",&from,&to);
}以免影响后面的读入
else if(桩3的盘子数不为n且每次移动合法) then
fprintf(fp_out, "%d\n",0)
销毁三个堆栈
}

第三章: 测试结果

输入
In_1
In_2
In_3
In_4
3
2 3
1 2
1 3
2 3
2 3
1 2
1 3
3 2
2 3
1 3
1 2
3 2
2
2 4
1 2
1 3
2 3
3 1
2 3
1 2
1 3
3 2

3
2 3
1 2
1 3
2 3
2 4
1 2
1 3
3 2
2 3
2 3
1 3
1 2
3 2
2
2 4
1 3
1 2
3 2
1 2
2 3
1 2
1 3
2 3

期望输出
3
-3
0
3
-3
3
-3
0
-4
3
实际输出
3
-3
0
3
-3
3
-3
0
-4
3
测试结果
pass
pass
pass
pass
补充说明：1.in_1使用老师所给的参考输入，初步测试程序是否正确。
2.in_2所有盘子移动到桩3后面步骤忽略。
3.in_3有非法移动忽略后继步骤。
4.in_4被移桩无盘子的一种无效情况。
第四章: 分析与调试
程序中所用算法的时间与空间复杂度分析
本算法的时间复杂的要视测试样例的情况而定，平均为O(T*m);
空间复杂度使用了一个三元堆栈数组，每个堆栈动态分配10个顺序的存储空间（存放int型数据），相对链栈在盘子较少时存储空间会有所浪费
程序调试中遇到的问题与收获
1. 通过这个汉诺塔移动步骤测试熟悉了堆栈这种数据结构的定义和使用。
2. 可能对于输出要求中第三种情况“其他情况输出0”的理解有一定偏差，我把从空桩移出盘子的情况定义为无效移动，而不是其他情况，其他情况仅包括所有部都合法但所有移动都执行后未能实现将所有盘子移到桩3
3. 刚开始对算法的设计上有些问题，无效移动同样没有完成任务，不加变量law的判断，将既输出-p，又输出0，显然不对。
4. 在三个堆栈的定义方面刚开始没用数组，而用了switch语句，比较繁琐。
代码有待提高的地方。
1. 在堆栈操作函数定义部分，对于如空栈的弹出，超存储空间的压入等特殊情况的处理较粗糙，认为输入的数据足够正常。
2. 算法上对于不合法的输入数据（如实际输入的测试样例数不等于T等）无法修正，执行后将出错。

附件: 源代码(C)
#include<stdio.h>
#include<stdlib.h>

#define STACKSIZE 10 /*动态分配堆栈存储量*/

FILE *fp_in = NULL; /*输入文件指针*/
FILE *fp_out = NULL; /*输出文件指针*/

typedef struct {
int *base;
int *top;
int stacksize;
}stack; /*定义堆栈*/

stack initstack(stack stake){
stake.base=((int*)malloc(STACKSIZE*sizeof(int)));
if(!stake.base) exit(0);
stake.top=stake.base;
stake.stacksize=STACKSIZE;
return stake;
} /*堆栈初始化*/

stack push(stack stake,int plate){
*stake.top++=plate;
return stake;
} /*将plate压入堆栈*/

stack pop(stack stake){
if(stake.top!=stake.base) --stake.top;
return stake;
} /*将栈顶元素弹出*/

int getplate(stack stake){
if(stake.top==stake.base) return 0;
else return *(stake.top-1);
} /*若栈不空则返回栈顶元素，否则返回0*/
void destroysk(stack stake){
free(stake.base);
} /*销毁栈*/

void func(int n,int m){ /*操作函数，处理一个测试样例*/
int j=n,k=1,i,from,to,plate,topplate,law=1;
stack stake[3]; /*定义一个栈顶数组*/
for(i=0;i<3;i++){
stake[i]=initstack(stake[i]);
} /*为三个桩构造三个空栈*/

for(j=n;j>=1;j--){ /*将n个盘子从大到小放入桩1*/
stake[0]=push(stake[0],j);
}
for(k=1;k<=m;k++){ /*依次进行m次移动*/
fscanf(fp_in, "%d%d",&from,&to);
plate=getplate(stake[from-1]); /*移出的盘子号*/
stake[from-1]=pop(stake[from-1]); /*该桩弹出顶端的盘子*/
if(plate==0){
fprintf(fp_out, "-%d\n",k);
break; /*如果待移的桩无盘子，无效移动，输出-k*/
}

topplate=getplate(stake[to-1]); /*目的桩原来的顶层盘子号*/
if(plate>=topplate&&topplate!=0){
fprintf(fp_out, "-%d\n",k);
law=0;
break; /*如果被移盘子号比目的桩原顶层盘大，无效移动，输出-k*/
}
stake[to-1]=push(stake[to-1],plate); /*将盘子移入该桩*/
if((stake[2].top-stake[2].base)==n){
fprintf(fp_out, "%d\n",k);
break; /*成功将桩1所有盘子移到桩3，输出k*/
}

}
if(k<=m){ /*如果某部移动无效或已成功，忽略后面步骤*/
for(i=k+1;i<=m;i++){
fscanf(fp_in, "%d%d",&from,&to);
}
}
else if((stake[2].top-stake[2].base)!=n&&law) /*其他情况，输出0*/
fprintf(fp_out, "%d\n",0);
for(i=0;i<3;i++){
destroysk(stake[i]); /*销毁三个堆栈*/
}

}

void destroy() /*关闭输入输出文件*/
{
fclose(fp_in);
fclose(fp_out);
}

int main(void) /*主函数*/
{
int T,i=1,n,m;
fp_in = fopen("p3_in.txt", "r"); /*打开输入文件*/
if(fp_in == NULL)
{
exit(0);
}
fp_out = fopen("p3_out.txt", "w"); /*打开输出文件*/
if(fp_out == NULL)
{
exit(0);
}
fscanf(fp_in, "%d", &T); /*输入测试样例个数*/

for(i=1;i<=T;i++){ /*实现所有测试样例的操作*/
fscanf(fp_in, "%d%d", &n,&m);
func(n,m);
}
destroy();
return 0;
}