《湘潭大学 数据结构实验3 实验报告 源代码 栈和队列.docx》由会员分享，可在线阅读，更多相关《湘潭大学 数据结构实验3 实验报告 源代码 栈和队列.docx（8页珍藏版）》请在三一办公上搜索。
1、湘潭大学 数据结构实验3 实验报告 源代码 栈和队列 “数据结构和算法II”课程实验报告 实验名称：栈和队列的综合应用 班级 姓名 学号 实验日期： 实验机时：2 学时 实验成绩： - 一.实验目的： 1. 熟悉栈的定义和基本操作 2. 熟悉队列的定义和基本操作 3. 掌握递归和非递归算法的实现技术和实际应用 4. 加深对栈结构的理解，培养解决实际问题的编程能力。 二.实验内容： 基本实验内容： 实现Hanoi 塔的问题； 完成迷宫问题或马踏棋盘问题求解。 三.程序及注释： 1. Hanoi塔问题： typedef int ElementType;#ifndef _Stack_h #defin
2、e _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
3、#define Error( Str ) FatalError( Str ) #define FatalError( Str ) fprintf( stderr, %sn, Str ), exit( 1 ) #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 Nod
4、e ) ); 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 ); else while( !IsEmpty( S ) ) Pop( S ); Void DisposeStack( Stack S )/销毁栈 MakeEmpty( S ); free( S ); void Push( ElementType X, S
5、tack 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 FirstCel
6、l = 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(%2d:将原盘 %d 从 %c 移动到 %cn,+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利
7、用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(%d,&n); for(i=n;i0;i-) Push(i,x); hanoi(n,x,y,z); p
8、rintf(移动完成！); 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 ); vo
9、id 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, %sn, Str ), exit( 1 ) #include struct Node/定义栈的结构 ElementType Element; PtrToNode N
10、ext; 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 ); else
11、 while( !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;
12、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 qipan99=0; qipanab=1; int i,m,n,s
13、tep103=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 c65=0;/用于储存棋子在每个位置时所选择的路径编号 for(i=1;i0&m0&n9)|(qipanmn!=0)/当所选路径不合法时，选择下一条路径 ci+;/路径编号递增 m=a+stepci1; n=b+stepci2; if(ci=9)/如果当前位置的棋子8个路径均不可用，则将当前位置编号置0，从栈x、y中pop
14、出上一步棋子的位置，并设置为当前位置 qipanab=0; Pop(x); a=e; Pop(y); b=e; break; if(ci=9)/若当前棋子无路可走，将路径编号置0后，将位置编号回溯 ci=0; i=i-2; continue; qipanmn=i+1;/若路径可用，将移动后的位置输入栈内，并将当前位置设置为移动后的位置 Push(m,x); Push(n,y); a=m;b=n; int p,q; for(p=1;p9;p+)/输出解决方案 for(q=1;q9;q+) printf(%3d,qipanpq); printf(n); int main/主函数 int a,b;
15、Stack x=CreateStack; Stack y=CreateStack; printf(请输入马的初始位置，以空格隔开，其中x、y均为18区间内的整数n); scanf(%d%d,&a,&b); solve(a,b,x,y); DisposeStack(x); DisposeStack(y); 四.运行结果： 1.hanoi塔问题： 2.马踏棋盘： 五.实验心得： 在本课程设计中，我明白了理论与实际应用相结合的重要性，并提高了自己组织数据及编写大型程序的能力。培养了基本的、良好的程序设计技能以及合作能力。这次课程设计同样提高了我的综合运用所学知识的能力。并对VC有了更深入的了解。数据结构是一门实践性很强的课程，上机实习是对学生全面综合素质进行训练的一种最基本的方法，是与课堂听讲、自学和练习相辅相成的、必不可少的一个教学环节。上机实习一方面能使书本上的知识变“活”，起到深化理解和灵活掌握教学内容的目的;另一方面，上机实习是对学生软件设计的综合能力的训练，包括问题分析，总体结构设计，程序设计基本技能和技巧的训练。此外，还有更重要的一点是：机器是比任何教师更严厉的检查者。因此，在“数据结构”的学习过程中，必须严格按照老师的要求，主动地、积极地、认真地做好每一个实验，以不断提高自己的编程能力与专业素质。总的来说，这次课程设计让我获益匪浅，对数据结构也有了进一步的理解和认识。
