算法实验题3.8 单柱 Hanoi塔问题 问题描述：
在一个塔座上有一叠大小不等的共n 个圆盘。各圆盘从小到大编号为 1，2，……，n。
时，这些圆盘自下而上散乱地叠在一起。现要求按照以下翻转规则，经若干次翻转，将
上的这一叠圆盘排好序，即按自底向上，从大到小的顺序叠置。
翻转规则：每次可以将最顶上的若干圆盘翻转，即按其相反的次序叠置。
例如，在下面的3个圆盘叠置状态中，中间状态是在左边状态中第3 个圆盘以上所有圆
转后得到的，相应翻转记为flip(3)；右边状态是将中间状态中第1个圆盘以上所有圆
转得到的，相应翻转记为flip(1)。
8 7 2
4 6 5
6 4 8
7 8 4
5 5 6
2 2 7
实验任务：
对于给定的大小不等的n个圆盘的初始状态，用最少的翻转次数将 n 个圆盘排序。 数据输入：
由文件input.txt给出输入数据。第 1 行是给定的圆盘自顶向下的初始状态。 结果输出:
将排序所需的翻转运算依次输出到文件 output.txt。输出翻转运算 flip(i)时，只要输出数
即可，相邻数字用空格分隔。
输入文件示例 输出文件示例
input.txt output.txt
5 1 2 3 4 1 2
>> 本文固定链接: http://www.vcgood.com/archives/2195
>> 转载请注明: zhitian516 2008年03月12日 于 C语言帝国 发表
下面是我写的程序，有高手可以帮我调试一下吗？
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef struct snode *slink;
typedef struct snode{int element;slink next;} StackNode;
slink NewStackNode()
{
slink p;
if((p=malloc(sizeof(StackNode)))==0)
Error(“Exhausted memory.”);
else return p;
}
typedef struct Istack *Stack;
typedef struct Istack
{
slink top;
}Lstack;
Stack StackInit()
{
Stack S=malloc(sizeof*S);
S->top=0;
return S;
}
int StackEmpty(Stack S)
{
return S->top==0;
}
int StackMellFull()
{
slink p;
if((p=malloc(sizeof(StackNode)))==0)
return 1;
else {
free(p);
return 0;
}
int StackFull(Stack S)
{
return StackMemFull();
}
void Push(int x,Stack S)
{
slink p;
if(StackFull(S))
Error(“Stack is full”);
p=NewStackNode()
p->element=x;
p->next=S->top;
S->top=p;
}
int Pop(Stack S)
{slink p;int x;
if(StackEmpty(S))Error(“Stack is empty”);
x=S->top->element;
p=S->top;
S->top=p->next;
free(p);
return x;
}
void main()
{
freopen(“input.txt”,”r”,stdin);
freopen(“output.txt”,”w”,stdout);
void flip(int x,int a[],int n);
Stack S;
S=StackInit();
int i=0,j,m,t=0,c;
while(scanf(“%d”,&m),m!=’\0′)
{
Push(m,Stack S);
i++;
}
c=n=i;
int * a =new int [n];
for(i=0;i<n;i++)
a[i]=Pop(S);
for(c;c>=0;c–)
{
i=0;j=i+1;
while(i<n-1)
{
for(j;j<n;)
{
if(a[i]<a[j])
{i=j;
j++;
}
else j++;
}
}
if(i==0)
flip(t+1,a,n);
if(i==n-1);
else
{
printf(“%d “,i);
flip(t+1,a,i);
flip(t+1,a,n);
}
}
}
void flip(int x,int a[],int n)
{
int p,q,r;
q=x;
r=n;
while(x<=(r+q)/2)
{
p=a[x-1];
a[x-1]=a[n-1];
a[n-1]=p;
x++;
n–;
}
}
帮帮忙啊，用C写出来都
行，