汉洛塔的实现-数据结构

数据结构实验报告数据结构实验报告 姓名 否姓名 否 学号 学号 2010468302 班级 计科班级 计科 1001 题目 汉洛塔的实现题目 汉洛塔的实现 完成日期 完成日期 2012 04 24 成绩 成绩 一 需求分析一 需求分析 1 需求分析 本次试验是分别用栈和递归实现汉罗塔的实际问题 通过与 c 语言中的递归调用函数实 现了塔间的转移 通过栈的存放实现了塔的从小到大的堆放 主要是函数的递归和栈的建 立及出栈和入栈的实现 除此之外我还用另一种方法实现了汉罗塔 与栈实现汉罗塔做对 比可以很清楚地看到栈的优点和缺点 2 程序执行命令包括 1 栈的建立 2 出栈返回一个整数 3 进栈 4 删除栈的元素 3 测试数据 栈实现 请输入塔的层数 1 请输入塔的层数 2 请输入塔的层数 3 请输入塔的层数 4 普通实现 请输入塔的层数 1 请输入塔的层数 2 请输入塔的层数 3 请输入塔的层数 4 二二 概要设计 概要设计 1 顺序存储结构的抽象数据类型定义为 ADT hanoi 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 1 2 n 基本操作 void initstack sqstack int base int top int stacksize sqstack void initstack sqstack s top s base s stacksize stack init size void push sqstack if s base printf overflow n exit 1 s top s base s stacksize s stacksize stackincrement s top e void pop sqstack else e s top s top s top 1 int gottop sqstack else e s top 1 return e void move sqstack e gottop a m m 是编号 printf d e push c e printf d n m pop a e printf c c n a elem c elem void hanoi int n sqstack x sqstack y sqstack z if n 1 move x 1 z intf c c n x elem z elem else hanoi n 1 x z y move x n y ntf c c n x elem y elem hanoi n 1 y x z int main int n char x a y b z c sqstack a b c initstack a initstack b initstack c printf 请输入塔的层数 scanf d for int i 0 i n i push a n i a elem b elem c elem hanoi n a b c for int j 0 i c n a b else hanoi n 1 a c b printf c c n a b hanoi n 1 c b a int main void int n printf 请输入塔的层数 scanf d printf the steps for d disk are n n hanoi n a b c return 0 函数的调用关系图反映了程序的层次结构 main hanoi n 1 x z y 递归函数 move x n y push s e pop s e gottop s m 四四 调试分析 调试分析 1 递归过程中出现很多问题 有事很难理解 2 move