标签归档:

汉诺塔C语言算法演示

汉诺塔简介:

有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:

  1. 每次只能移动一个圆盘;
  2. 大盘不能叠在小盘上面。

提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆,但都必须遵循上述两条规则。

汉诺塔移动分析:

定义汉诺塔移动函数:

void hanoi(int n, char from, char buffer, char to);

1) 参数 n 表示要移动的盘子数

2) 参数 from 表示盘子所在的柱子

3) 参数 buffer 表示盘子移动过程中借助的柱子

4) 产生 to表示盘子最终要移到的柱子

初始状态:

将A柱子的N个圆盘移至C柱子上, 其中可以借助B柱子

汉诺塔移动初始状态

汉诺塔移动初始状态
移动n-1个盘子

汉诺塔的3个中间状态:

以下内容需要理解函数调用, 栈的知识

栈的知识: 先进后出, 后进先出

1): 汉诺塔移动n-1个盘子从A借助C移到B

hanoi-1

汉诺塔移动n-1个盘子从A借助C到B

移动代码: hanoi(n-1, from, to, buffer);

为何可以移动n-1个盘子, 这是初学者最难理解的部分. 要想理解, 必须理解栈的知识, 递归是一种反向思维.

2): 汉诺塔移动盘子n从A到C

汉诺塔移动盘子n从A到C

汉诺塔移动盘子n从A到C

移动代码: printf(“%d A->C\n”, n);

3): 汉诺塔移动n-1个盘子从B借助A移到B

汉诺塔移动n-1个盘子从B借助A移至C

汉诺塔移动n-1个盘子从B借助A移至C

移动代码: hanoi(n-1, buffer, from, to);

这是移动n-1个盘子的情况, 这和初始状态时一样的, 区别在于位于不同的柱子.

移动n-2个盘子并重复1-3步骤

接下来是移动n-2个盘子的情况. 因为 盘子n和n-1已经不要移动了(从递归的思想来看)

直到剩下一个盘子

这是就需要移动最后一个盘子到C, 实际的运算过程中程序会不断压栈(从n, n-1, 直到1), 然后执行此步操作, 注意之后的每一步都是每次移动一个盘子(之前只是压栈操作, 不要移动操作), 然后释放内存, 执行盘子2的操作, 直到最后移动盘子n-1, n的操作
继续阅读

栈的算法演示(C语言)

栈的算法演示

/*
	Name:		栈的算法演示
	Author:		lnesuper
	Date:		2014-10-11 00:05:17 
	Version:	V0.1 
	Discretion:	使用单向链表演示栈的操作 
*/

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <stdbool.h>

//链表数据类型 
typedef struct Node {			
	int data;
	struct Node * pNext;
} NODE, *PNODE;

//链表栈数据类型 
typedef struct Stack {		
	PNODE pTop;
	PNODE pBottom;
} STACK, *PSTACK; 

//函数原型 
void init(PSTACK pS);				//栈的初始化 
void push(PSTACK pS, int val);		//压栈 
void traverse(PSTACK pS);			//遍历 
bool pop(PSTACK pS, int * pVal);	//出栈	
bool empty(PSTACK pS);				//判断栈是否为空	
void clear(PSTACK pS);				//清空栈 

int main(void)
{
	STACK S;
	init(&S);
	push(&S, 1);
	push(&S, 2);
	push(&S, 3);
	push(&S, 4);
	push(&S, 5);
	push(&S, 6);
	traverse(&S);

	int val;
	if (pop(&S, &val))
	{
		printf("出栈成功, 出栈的元素是%d\n", val); 
	}
	else
	{
		printf("出栈失败\n");
	}

	traverse(&S);
	clear(&S);
	traverse(&S);
	
	return 0;
}

void init(PSTACK pS)
{
	PNODE pHead = (PNODE)malloc(sizeof(NODE));
	if (NULL == pHead)
	{
		printf("分配内存失败. \n");
		exit(-1); 
	}
	else
	{
		pS->pTop = pHead;
		pS->pBottom = pHead;
		pHead->pNext = NULL; 
	}
	
	return;
}

void push(PSTACK pS, int val)
{
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	if(NULL == pNew)
	{
		printf("压栈失败. \n");
		exit(-1);
	}
	else
	{
		pNew->data = val;
		pNew->pNext = pS->pTop;
		pS->pTop = pNew;
	}
	
	return; 
}

void traverse(PSTACK pS)
{
	PNODE p = pS->pTop, q = NULL;
	
	if (empty(pS))
		printf("空栈, 无法遍历\n");
	else
	{
		while(pS->pBottom != q)
		{
			printf("%d ", p->data);
			q = p->pNext;
			p = q;
		}
		printf("\n");
	}

	return;
}

bool pop(PSTACK pS, int * pVal)
{
	bool ret = false;
	if(empty(pS))
	{
		ret = false;
	}
	else
	{
		PNODE r = pS->pTop;
		*pVal = r->data;
		pS->pTop = r->pNext;
		free(r);
		r = NULL; 
		
		ret = true;	
	}
	
	return ret;
}

bool empty(PSTACK pS)
{
	if (pS->pBottom == pS->pTop)
		return true;
	else
		return false;	
}

void clear(PSTACK pS)
{
	if (!empty(pS))
	{
		PNODE p = pS->pTop;
		PNODE q = NULL;
		while (pS->pBottom != p)
		{
			q = p->pNext;
			free(p);
			p = q;
		}
		pS->pTop = pS->pBottom; 
	}
	pS->pTop = pS->pBottom;
	
	return;
}

/*	
	Result(Dev-C++ 5.7.1):
	=========================
	6 5 4 3 2 1
	出栈成功, 出栈的元素是6
	5 4 3 2 1
	空栈, 无法遍历
	=========================
*/

源代码:

http://pan.baidu.com/s/1bn91dk7