`
chemingliang
  • 浏览: 134108 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

数据结构：栈应用_求解汉诺塔(Hanoi)1

数据结构CC++C# 
阅读更多

/************************************************************************/

/* 数据结构：栈应用：汉诺塔(Hanoi)问题                                                           */

/* 挑灯看剑-shuchangs@126.com 2010-10                                                                   */

/* 云歌国际（Cloud Singers International） www.cocoral.com                              */

/************************************************************************/

#include <stdio.h>

#include <malloc.h>

#include "core.h"

/************************************************************************/

/* 以下是栈基本操作                                                                                      */

/************************************************************************/

//结点数据结构

typedef struct NODE

{

       int data;

       struct NODE* next;

       struct NODE* prior;

}Node, * NodePointer;

 

//栈元数据结构

typedef struct STACK

{

       int len;

       struct NODE* top;

       struct NODE* base;

}Stack, * StackPointer;

 

void main_HANOI()

{

       //*************函数原型******************

       Status StackIn(StackPointer SP, int e);

       void autoStack(StackPointer SP, int n);

       void StackPrint(Stack S, char tag);

       Status StackOut(StackPointer SP, NodePointer NP);

       void Hanoi();

       //*************函数原型******************

       Stack S = { 0, NULL, NULL };

       Node N = { 0, NULL, NULL};

       int i = 0;

       //autoStack(&S, 4);

       //StackPrint(S, 't');

       Hanoi();

}

//进栈操作，结点作为栈顶元素入栈

Status StackIn(StackPointer SP, int e)

{

       static Status StackIsEmpty(Stack S);//函数原型

       Status status = ERROR;

       NodePointer p = NULL;//遍历指针，非游离指针

       NodePointer NP = (NodePointer) malloc(sizeof(Node));

       NP->data = e;

       //进行预处理

       if (!StackIsEmpty(*SP))

       {

              //将结点追加为栈顶元素

              p = SP->top; //p指向栈顶

              p->next = NP;

 

              NP->prior = p;

              NP->next = NULL;

 

              SP->top = NP;

              SP->len += 1; //长度加1

              //puts("进栈成功！");

              status = OK;

       }

       else

       {

              SP->base = SP->top = NP;

              NP->next = NP->prior = NULL;

              SP->len = 1; //长度为1

              //puts("进栈成功！");

              status = OK;

       }

       return status;

}

 

//自动化栈，初始化汉诺塔（Hanio）

void autoStack(StackPointer SP, int n)

{

       COUNT i;

       for (i = n; i >= 1; i--)

       {

              if (StackIn(SP, i))

              {}

              else

              {

                     break;

              }

       }

}

 

static Status StackIsEmpty(Stack S)

{

       if (S.len == 0 || S.base == NULL || S.top == NULL)

              return TRUE;

       else

              return FALSE;

}

 

//出栈操作，并用结点返回该值

Status StackOut(StackPointer SP, NodePointer NP)

{

       Status status = ERROR;

       NodePointer p = SP->top; //p指向栈顶

       if (!StackIsEmpty(*SP))

       {

              if (SP->len == 1)

              {

                     SP->base = SP->top = NULL;

                     SP->len = 0; //长度为0

 

                     NP->data = p->data;

                     NP->next = p->next;

                     NP->prior = p->prior;

                     //puts("出栈成功！");

                     status = OK;

              }

              else

              {

                     p->prior->next = NULL;

                     SP->top = p->prior;

                     SP->len -= 1; //长度减1

                     NP->data = p->data;

                     NP->next = p->next;

                     NP->prior = p->prior;

                     //puts("出栈成功！");

                     status = OK;

              }

       }

       else

       {

              //puts("出栈失败！栈为空！");

              status = ERROR;

       }

       free(p); //p为游离结点，最后释放p内存

       return status;

}

 

//栈打印操作，tag参数IN SET{'B','T'}

void StackPrint(Stack S, char tag)

{

       static Status StackIsEmpty(Stack S);//函数原型

       NodePointer p = NULL;

       COUNT i = 1;

       COUNT n = S.len;

       printf("栈长度：%d\n", n);

       if (!StackIsEmpty(S)) //如果线性链表非空

       {

              switch (tag)

              {

              case 'B':

                     p = S.base;

                     puts("打印结点信息（栈底到栈顶）：");

                     for (i = 1; i <= n; i++)

                     {

                            printf("Node[%d] = %d\n", i, p->data);

                            p = p->next;

                     }

                     break;

              case 'b':

                     p = S.base;

                     puts("打印结点信息（栈底到栈顶）：");

                     for (i = 1; i <= n; i++)

                     {

                            printf("Node[%d] = %d\n", i, p->data);

                            p = p->next;

                     }

                     break;

              case 'T':

                     p = S.top;

                     puts("打印结点信息（栈顶到栈底）：");

                     for (i = n; i >= 1; i--)

                     {

                            printf("Node[%d] = %d\n", i, p->data);

                            p = p->prior;

                     }

                     break;

              case 't':

                     p = S.top;

                     puts("打印结点信息（栈顶到栈底）：");

                     for (i = n; i >= 1; i--)

                     {

                            printf("Node[%d] = %d\n", i, p->data);

                            p = p->prior;

                     }

                     break;

              default:

                     puts("打印失败！");

                     break;

              }

       }

       else //如果栈为空

       {

              puts("打印失败！栈为空！");

       }

       free(p);//p为游离结点，最后释放p内存

}

/************************************************************************/

/* 以下为汉诺塔（Hanoi）求解                                                                        */

/************************************************************************/

void Hanoi()

{

       void recursion(int n, StackPointer from, StackPointer tmp,

              StackPointer to, int* stn);

 

       Stack A = { 0, NULL, NULL }; //起始栈

       Stack B = { 0, NULL, NULL }; //临时栈

       Stack C = { 0, NULL, NULL }; //目的栈

 

       int n = 4;

       int cnt = 0; //统计搬运次数

 

       //初始化A，生成4阶Hanoi

       autoStack(&A, n);

 

       puts("--------------------------------");

       puts("汉诺塔：搬运前 A塔 盘子情况：");

       StackPrint(A, 't');

       puts("\nB塔 盘子情况：");

       StackPrint(B, 't');

       puts("\nC塔 盘子情况：");

       StackPrint(C, 't');

       puts("--------------------------------");

 

       recursion(n, &A, &B, &C, &cnt); //递归调用

 

       puts("--------------------------------");

       puts("汉诺塔：搬运后 A塔 盘子情况：");

       StackPrint(A, 't');

       puts("\nB塔 盘子情况：");

       StackPrint(B, 't');

       puts("\nC塔 盘子情况：");

       StackPrint(C, 't');

       puts("--------------------------------");

       printf("搬运次数合计：%d\n", cnt);

}

 

//参见版面《数据结构：栈应用_求解汉诺塔(Hanoi)2》

0
顶
0
踩
分享到：
| 写给程序员
评论
1 楼 deepfuture 2010-10-16  
不错，用栈来实现递归，速度和效率较高，建议部分栈操作这块用内联汇编，这样更好
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    汉诺塔 Hanoi

    汉诺塔（Hanoi）问题，也称为艾斯特拉达问题或移塔问题，是一个经典的递归算法问题，源于19世纪由法国数学家艾德蒙·朗利所提出。问题的目标是将一个堆栈中的所有盘子，通过三个柱子在有限步骤内从初始柱子A移动到...

    汉诺塔c++实现源码

    在给定的C++代码片段中，我们看到的是通过栈数据结构来模拟和解决汉诺塔问题的一种方法。下面，我们将深入探讨汉诺塔问题本身、如何用栈来模拟汉诺塔的过程以及代码中所涉及的关键概念。 ### 汉诺塔问题概述 汉诺...

    汉诺塔经典问题递归实现—程序源代码

    汉诺塔（Hanoi Tower）问题是一个经典的递归问题，它由三个柱子及不同大小的圆盘组成。游戏的目标是将所有圆盘从一个柱子移动到另一个柱子上，并遵循以下规则： 1. **每次只能移动一个圆盘**。 2. **大盘子不能放在...

    Java语言编写的Hanoi图形演示程序（汉诺塔）

    汉诺塔（Hanoi）问题是一个经典的递归问题，它涉及到三个柱子和一堆不同大小的盘子。目标是将所有盘子从一个柱子移动到另一个柱子，每次只能移动一个盘子，并且任何时候大盘子都不能位于小盘子之上。Java语言可以很...

    汉诺塔问题算法以及实现

    汉诺塔问题是一个经典的递归算法案例，它不仅在计算机科学领域有着广泛的应用，同时也被用来教授递归思想的基础知识。这个问题最早由法国数学家Édouard Lucas于1883年提出，并以其发明者的名字命名。汉诺塔问题涉及...

    汉诺塔应用

    递归是一种强大的工具，广泛应用于数据结构（如树和图的遍历）、搜索算法（如深度优先搜索）以及其他许多复杂问题的求解。通过理解和实践汉诺塔问题，C语言学习者能够更好地掌握递归这一核心概念，为后续的编程学习...

    汉诺塔递归与非递归两种算法的代码与结果对比

    非递归算法通常需要额外的数据结构来跟踪当前的状态，例如盘子的位置和待移动的盘子。非递归算法的代码可能更复杂，但执行效率通常更高，因为它避免了递归带来的栈空间消耗。 "非递归解决汉诺塔，每一步都有确切解....

    汉诺塔vc++ 面向对象编程课程作业

    汉诺塔（Towers of Hanoi）问题来自一个古老的传说：在世界刚被创建的时候有一座钻石宝塔，其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔。从世界创始之日起，婆罗门...

    汉诺塔的c语言实现代码

    理解并掌握汉诺塔的递归实现，对于深入学习算法和数据结构具有重要意义。 此外，汉诺塔问题还可以用非递归方式解决，例如利用栈或迭代的方法，这同样值得探索和学习。对于初学者而言，通过汉诺塔问题的学习，可以更...

    java汉诺塔源码

    汉诺塔是一个经典的递归问题，源于...递归是计算机科学中的重要概念，广泛应用于数据结构（如树和图的遍历）、算法（如排序和搜索）以及各种复杂问题的求解。理解并能熟练运用递归，对提升Java程序员的能力至关重要。

    Manual /windows下的数据结构描述

    - **递归算法演示**：包括汉诺塔（Hanoi）、皇后问题（Queen）、迷宫问题（Maze）和背包问题（Knap）的解决算法。 - **模拟银行**：BankSimulation 展示了队列在银行服务中的应用。 - **表达式求值**：Exp_...

    Java汉诺塔

    此外，汉诺塔问题还可以帮助我们理解栈的数据结构，因为递归本质上就是栈的运用，每次函数调用都会将相关信息压入栈中，待调用返回时弹出。递归算法的效率主要取决于递归深度，因此在实际问题中，如果圆盘数量巨大，...

    Java 汉诺塔代码

    理解递归是学习计算机科学和编程的重要部分，因为它在许多领域，如数据结构（如树和图的遍历）、算法（如排序和搜索）以及问题求解策略中都扮演着关键角色。通过练习和应用递归，你可以提高自己的编程能力和问题解决...

    hdu 汉诺塔

    - **2184**, **2175**, **2511**, **2587**, **1007**, **4033**, **2899**, **1062**, **1173**: 其他编号也可能涉及汉诺塔问题的不同方面，如特定数据结构的应用、算法优化技巧等。 通过对汉诺塔问题及其变种的...

    16470257490438c语言实现的汉诺塔演示程序.zip

    递归算法不仅在汉诺塔问题中应用广泛，还在数据结构（如树和图）、搜索算法（如深度优先搜索）和其他许多计算问题中发挥着重要作用。了解并掌握递归思想是每个程序员必备的技能之一，而C语言提供了一个简洁的平台来...

    C和C++实现的汉诺塔

    在C和C++中实现汉诺塔可以帮助我们理解递归算法和数据结构的应用。本项目包含不同方法实现的汉诺塔，既有递归版本，也有非递归版本，为学习者提供了丰富的学习资源。 首先，我们要理解汉诺塔问题的基本规则：有三根...

    汉诺塔问题的非递归算法分析

    Hanoi(汉诺)塔问题作为一个古典的数学问题,一直以来都是数据结构中递归算法的经典案例, 几乎没有介绍过其他的方法来解决此问题。文章分析讨论了一种非递归算法。

    c语言实现的汉诺塔演示程序.zip

    在编写汉诺塔程序时，我们将用到基本的数据类型（如int、void等）、控制结构（如if语句、while循环、for循环）和函数定义。 汉诺塔问题通常采用递归方法解决。递归是函数调用自身的一种方式，通过不断缩小问题规模...

    汉诺塔模拟实现

    汉诺塔是一个经典的递归问题，它源自印度的一个古老传说，涉及三个...递归是计算机科学中一种强大的工具，广泛应用于数据结构（如树和图的遍历）、搜索算法、动态规划等问题中。熟练掌握递归对于提升编程能力至关重要。

Magicbox
Global site tag (gtag.js) - Google Analytics