“数据结构和算法II”课程实验报告实验名称：栈和队列的综合应用班级姓名学号实验日期：实验机时：2 学时实验成绩：-------------------------------------------------------------------------------一.实验目的：1.熟悉栈的定义和基本操作2.熟悉队列的定义和基本操作3.掌握递归和非递归算法的实现技术和实际应用4.加深对栈结构的理解，培养解决实际问题的编程能力。

二.实验内容：（1）基本实验内容：实现Hanoi 塔的问题；完成迷宫问题或马踏棋盘问题求解。

三.程序及注释：1.Hanoi塔问题：typedef int ElementType;#ifndef _Stack_h#define _Stack_hstruct 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 <stdio.h>#include <stdlib.h>#define Error( Str ) FatalError( Str )#define FatalError( Str ) fprintf( stderr, "%s\n", Str ), exit( 1 ) #include <stdlib.h>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( "Out of space!!!" );S->Next = NULL;MakeEmpty( S );return S;}void MakeEmpty( Stack S )//将栈置空{if( S == NULL )Error( "Must use CreateStack first" );elsewhile( !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( "Out of space!!!" );else{TmpCell->Element = X;TmpCell->Next = S->Next;S->Next = TmpCell;}}Void Pop( Stack S )//推出栈顶元素{PtrToNode FirstCell;if( IsEmpty( S ) )Error( "Empty stack" );else{FirstCell = S->Next;S->Next = S->Next->Next;free( FirstCell );}}void Move(Stack x,int n,Stack z)//将第编号为n的圆盘从x移动到z{Pop(x);Push(n,z);printf("%2d:将原盘 %d 从 %c 移动到 %c\n",++c,n,x->bianhao,z->bianhao);} 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移动到yMove(x,n,z);//将编号为n的圆盘从x移动到zhanoi(n-1,y,x,z);}}// 将编号为1到n-1的圆盘从y利用x移动到zint 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("%d",&n);for(i=n;i>0;i--)Push(i,x);hanoi(n,x,y,z);printf("移动完成！！！");DisposeStack(x);//销毁栈xDisposeStack(y);//销毁栈yDisposeStack(z);//销毁栈z}2.马踏棋盘typedef int ElementType;#ifndef _Stack_h#define _Stack_hstruct 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 );#include <stdio.h>#include <stdlib.h>#define Error( Str ) FatalError( Str )#define FatalError( Str ) fprintf( stderr, "%s\n", Str ), exit( 1 ) #include <stdlib.h>struct Node//定义栈的结构{ElementType Element;PtrToNode Next;};int IsEmpty( Stack S )//判断栈是否为空{return S->Next == NULL;}Stack CreateStack()//创建一个栈{Stack S;S = malloc( sizeof( struct Node ) );if( S == NULL )FatalError( "Out of space!!!" );S->Next = NULL;MakeEmpty( S );return S;}void MakeEmpty( Stack S )//将栈制空{if( S == NULL )Error( "Must use CreateStack first" );elsewhile( !IsEmpty( S ) )Pop( S );}void DisposeStack( Stack S )//销毁栈{MakeEmpty( S );free( S );}void Push( ElementType X, Stack S )//向栈内输入一个值{PtrToNode TmpCell;TmpCell = malloc( sizeof( struct Node ) );if( TmpCell == NULL )FatalError( "Out of space!!!" );else{TmpCell->Element = X;TmpCell->Next = S->Next;S->Next = TmpCell;}}int e;//用来暂时储存从栈里pop出的元素void Pop( Stack S )//输出栈顶的元素{PtrToNode FirstCell;if( IsEmpty( S ) )Error( "Empty stack" );else{e=S->Next->Element;FirstCell = S->Next;S->Next = S->Next->Next;free( FirstCell );}}void solve(int a,int b,Stack x,Stack y)//棋盘问题函数{int qipan[9][9]={0};qipan[a][b]=1;int i,m,n,step[10][3]={{0,0,0},{1,1,2},{2,1,-2},{3,-1,2},{4,-1,-2},{5,2,1},{6,2,-1},{7,-2,1},{8,-2,-1},{9,0,0}}; //定义棋子行走规则Push(a,x);//向栈x输入起始位置x的值Push(b,y);//向栈y输入起始位置y的值int c[65]={0};//用于储存棋子在每个位置时所选择的路径编号for(i=1;i<3;i++){c[i]++;if(c[i]==9)//如果当前位置的棋子8个路径均不可用，则将当前位置编号置0，从栈x、y中pop出上一步棋子的位置，并设置为当前位置{c[i]=0;i=i-2;qipan[a][b]=0;Pop(x);a=e;Pop(y);b=e;continue;}m=a+step[c[i]][1];n=b+step[c[i]][2];while((!(m>0&&m<9&&n>0&&n<9))||(qipan[m][n]!=0))//当所选路径不合法时，选择下一条路径{c[i]++;//路径编号递增m=a+step[c[i]][1];n=b+step[c[i]][2];if(c[i]==9)//如果当前位置的棋子8个路径均不可用，则将当前位置编号置0，从栈x、y中pop出上一步棋子的位置，并设置为当前位置{qipan[a][b]=0;Pop(x);a=e;Pop(y);b=e;break;}}if(c[i]==9)//若当前棋子无路可走，将路径编号置0后，将位置编号回溯{c[i]=0;i=i-2;continue;}qipan[m][n]=i+1;//若路径可用，将移动后的位置输入栈内，并将当前位置设置为移动后的位置Push(m,x);Push(n,y);a=m;b=n;}int p,q;for(p=1;p<9;p++)//输出解决方案{for(q=1;q<9;q++)printf("%3d",qipan[p][q]);printf("\n");}}int main()//主函数{int a,b;Stack x=CreateStack();Stack y=CreateStack();printf("请输入马的初始位置（x,y），以空格隔开，其中x、y均为1~8区间内的整数\n");scanf("%d%d",&a,&b);solve(a,b,x,y);DisposeStack(x);DisposeStack(y);｝四.运行结果：1.hanoi塔问题：2.马踏棋盘：五.实验心得：在本课程设计中，我明白了理论与实际应用相结合的重要性，并提高了自己组织数据及编写大型程序的能力。