文档库

最新最全的文档下载
当前位置:文档库 > 超详细 课程设计 汉诺塔问题

超详细 课程设计 汉诺塔问题

江西理工大学应用科学学院

数据结构课程设计报告

汉诺塔问题

题目:________________________________________________

计算机科学与技术111班

班级:__________________________________________________

*************

姓名:__________________________________________________

******************

学号:__________________________________________________

2013/6/27

完成日期:_______________________________________________

目录

一、课程设计概述: (1)

二、课程设计目的 (1)

三、问题描述 (1)

四、需求分析 (1)

五、概要设计 (1)

六、详细设计 (1)

七、存储结构 (4)

八、调试分析 (4)

九、运行结果界面以及析 (6)

十、流程图 (9)

十一、设计心得 (9)

十二、参考文献 (10)

一、课程设计概述:

本次课程设计内容主要包括进栈出栈和初始化栈与递归函数的自我调用。

使用语言:C

编译环境:Microsoft visual c++ 6.0

二、课程设计目的

课程设计是课程教学必不可缺的一个重要环节,它可加深学生对课程所学内容的进一步的理解与巩固,是将计算机课程与实际问题相联接的关键步骤。通过课程设计,能够提高学生分析问题、解决问题,从而运用所学知识解决实际问题的能力,因而必须给予足够的重视。

三、问题描述:

汉诺塔问题

有A,B,C,三根柱子,开始时A柱子有1~n个圆环,它们是按照从小到大的顺序放在A柱子上,将A柱子上所有圆环通过B柱子,移动到C柱子上,要求小圆环只能在大圆环的上面,实现移动的步骤:

四、需求分析

1、通过键盘输入圆盘的个数。

2、任何时刻都不能将一个较大的圆盘压在较小的圆盘上面。

3、运用所了解的知识,对InitStack、Push、Pop、Hanoi中各个函数进行实现,构建相应的函数。Main函数实现函数的调用,Move函数实现输出,Hanoi函数调用Move函数实现移动和最终输出。

4、界面布局美观。

五、概要设计

void Move(SqStack &a,SqStack &b);

/*汉诺塔的移动步骤*/

int Hanoi(int n,SqStack &a,SqStack &b,SqStack &c);

/*汉诺塔的操作*/

void InitStack(SqStack &s);

/*初始化栈,构建栈*/

int Push(SqStack &s,int e);

/*进栈*/

int Pop(SqStack &s,int e);

/*出栈*/

六、详细设计

#include

#include

#define MaxSize 30

typedef struct

{

int data[MaxSize];

char name;

int top;

}*SqStack,Han;

void Move(SqStack &a,SqStack &b); /*汉诺塔的移动步骤*/

int Hanoi(int n,SqStack &a,SqStack &b,SqStack &c);/*汉诺塔的操作*/

void InitStack(SqStack &s); /*初始化栈*/

int Push(SqStack &s,int e); /*进栈*/

int Pop(SqStack &s,int e); /*出栈*/

void main()

{

printf("*****************************************************************\n");

printf("** 有三根柱子A,B,C,开始时A柱子有1~n个圆环,它们**\n");

printf("** 是按照从小到大的顺序放在A柱子上,将A柱子上所有圆**\n");

printf("** 环通过B柱子,移动到C柱子上,要求小圆环只能在大圆**\n");

printf("** 环的上面,则移动实现的步骤如下: **\n");

printf("*****************************************************************\n");

int n,i;

SqStack a,b,c;

InitStack(a);

InitStack(b);

InitStack(c);

a->name ='A';

b->name ='B';

c->name ='C';

printf("请输入汉诺塔塔中圆环的个数n:");

scanf("%d",&n);

for(int t=n;t>0;t--)

Push(a,t); //进栈的调用

i=Hanoi(n,a,b,c); //移动操作的调用且返回移动的总次数free(a);

free(b);

free(c);

printf("总共需要移动的次数为:%d次\n",i);

}

void InitStack(SqStack &s) /*初始化栈的实现,构建栈*/

{

s=(SqStack )malloc(sizeof(Han));

s->top =-1;

}

int Push(SqStack &s,int e) /*进栈的实现*/

{

if(s->top ==MaxSize-1)

return 0;

s->top ++;

s->data [s->top ]=e;

return 1;

}

int Pop(SqStack &s,int e) /*出栈的实现*/

{

if(s->top ==-1)

return 0;

e= s->data [s->top ];

s->top --;

return e;

}

int Hanoi(int n,SqStack &a,SqStack &b,SqStack &c)/*圆环操作的实现*/ {

static int i=0;

if(n==1)

{

Move(a,c);

i++;

}

else

{

Hanoi(n-1,a,c,b);/*递归调用*/

Move(a,c);

i++;

Hanoi(n-1,b,a,c);

}

return i;

}

void Move(SqStack &a,SqStack &b)/*圆环移动步骤的现实*/

{

int i,j;

j=Pop(a,i);

printf("\t\t\t %d 环-->%c 柱子\n",j,b->name );

Push(b,j);

}

七、存储结构

栈的存储结构,每进入一层递归,就产生一个新的工作记录压人栈顶,每退出一层递归,就从栈顶弹出一个工作记录。

typedef struct

{

int data[MaxSize];

char name;

int top;

}*SqStack,Han;

八、调试分析

程序调试

1、使用Microsoft visual c++ 6.0

编辑软件进行源程序的编写。

2、使用Microsoft visual c++ 6.0

软件进行编译,步骤:单击“组建”选择“编译”

3、使用Microsoft visual c++ 6.0

运行程序并调试,步骤:单击“组建”选择“执行”

超详细 课程设计 汉诺塔问题

超详细 课程设计 汉诺塔问题

超详细 课程设计 汉诺塔问题

九、运行结果界面以及分析

超详细 课程设计 汉诺塔问题

当n=2时,输出运行结果界面

超详细 课程设计 汉诺塔问题

当n=3时,输出运行结果界面

超详细 课程设计 汉诺塔问题

当n=4时,输出运行结果界面

超详细 课程设计 汉诺塔问题

十、流程图

开始

输入圆环个数

判断盘数是

否为1

盘子数大于1,继续进行

递归过程

输出移动步骤

执行移位操作

执行移位操作

输出移动步骤

结束

十一、设计心得

通过这次课程设计,我们理解了我们一直没有深入理解的知识,大学学习,从C语言到面向对象的程序化设计,再到数据结构,研究算法的特性,程序设计的趣味性一直存在,在学习数据结构的过程中也学到了许多计算机应用基础知识,对计算机的机体也有了一个大体的了解。

通过我们小组两人的努力所实现的要求,虽然不是很复杂的程序,但是在实际操作过程中却还是犯了不少错误,还和小组成员起了一点小矛盾,但在解决问题的过程中获得的一丝收获,使我们很有成就感。虽然理论考试成绩很不理想,但在具体操作中,还是对这学期所学的数据结构的理论知识得到了巩固,尤其是对汉诺塔的栈与递归调用,达到课程设计的基本目的。

通过实际操作,学会分析问题,解决问题,是我们一直以来的要求,理论结合实践才是成功。

十二、参考文献

严蔚敏. 《数据结构(C语言版)》. 清华大学出版社.