湘潭大学数据结构实验3实验报告源代码栈和队列剖析

“数据结构和算法II”课程实验报告

实验名称：栈和队列的综合应用

班级 姓名 学号 实验日期： 实验机时：2 学时 实验成绩：

-------------------------------------------------------------------------------

一.实验目的：

1. 熟悉栈的定义和基本操作 2. 熟悉队列的定义和基本操作

3. 掌握递归和非递归算法的实现技术和实际应用 4. 加深对栈结构的理解，培养解决实际问题的编程能力。 二.实验内容： （1）基本实验内容： 实现Hanoi 塔的问题；

完成迷宫问题或马踏棋盘问题求解。 三.程序及注释： 1. Hanoi塔问题：

typedef int ElementType;#ifndef _Stack_h #define _Stack_h struct Node;

typedef struct Node *PtrToNode; typedef PtrToNode Stack; int IsEmpty( Stack S ); Stack CreateStack( void ); void DisposeStack( Stack S ); void MakeEmpty( Stack S );

void Push( ElementType X, Stack S ); ElementType Top( Stack S ); void Pop( Stack S ); #endif

#include

#include

#define Error( Str ) FatalError( Str )

#define FatalError( Str ) fprintf( stderr, \#include struct Node//定义栈的结构 {ElementType Element; PtrToNode Next; char bianhao;};

int IsEmpty( Stack S )//判断栈是否为空 {return S->Next == NULL;} Stack CreateStack()//创建一个空栈 {Stack S;

S = malloc( sizeof( struct Node ) ); if( S == NULL )

FatalError( \ S->Next = NULL; MakeEmpty( S ); return S;}

void MakeEmpty( Stack S )//将栈置空 {if( S == NULL )

Error( \ else

while( !IsEmpty( S ) ) Pop( S );}

Void DisposeStack( Stack S )//销毁栈 {MakeEmpty( S ); free( S );}

void Push( ElementType X, Stack S )//向栈S中插入元素n {PtrToNode TmpCell;

TmpCell = malloc( sizeof( struct Node ) ); if( TmpCell == NULL )

FatalError( \ else

{TmpCell->Element = X; TmpCell->Next = S->Next; S->Next = TmpCell;}}

Void Pop( Stack S )//推出栈顶元素 {PtrToNode FirstCell; if( IsEmpty( S ) ) Error( \ else

{FirstCell = S->Next; S->Next = S->Next->Next; free( FirstCell );}}

int c=0;

void Move(Stack x,int n,Stack z)//将第编号为n的圆盘从x移动到z {Pop(x); Push(n,z);

printf(\将原盘 %d 从 %c 移动到 %c\\n\void hanoi(int n,Stack x,Stack y,Stack z)//汉诺塔问题解决函数 {if (n==1) Move(x,1,z); else

{hanoi(n-1,x,z,y);//将编号为1到n-1的圆盘从x利用z移动到y Move(x,n,z);//将编号为n的圆盘从x移动到z

hanoi(n-1,y,x,z);}}// 将编号为1到n-1的圆盘从y利用x移动到z int main() {int n,i;

Stack x=CreateStack();

x->bianhao='x';//对栈x进行编号 Stack y=CreateStack();

y->bianhao='y';//对栈y进行编号 Stack z=CreateStack();

z->bianhao='z';//对栈z进行编号 printf(\请输入Hanoi塔的高度\\n\scanf(\for(i=n;i>0;i--) Push(i,x); hanoi(n,x,y,z); printf(\移动完成！！！\DisposeStack(x);//销毁栈x DisposeStack(y);//销毁栈y DisposeStack(z);//销毁栈z}

2. 马踏棋盘

typedef int ElementType; #ifndef _Stack_h #define _Stack_h struct Node;

typedef struct Node *PtrToNode; typedef PtrToNode Stack; int IsEmpty( Stack S ); Stack CreateStack( void ); void DisposeStack( Stack S ); void MakeEmpty( Stack S );

void Push( ElementType X, Stack S ); ElementType Top( Stack S ); void Pop( Stack S );