数据结构上机_实验报告_栈的表示与实现及栈的应用.doc

实验：栈的表示与实现及栈的应用

【实验目的】
掌握栈的顺序存储结构及其基本操作的实现。
掌握栈后进先出的特点，并利用其特性在解决实际问题中的应用。
掌握用递归算法来解决一些问题。
【实验内容】
编写程序，对于输入的任意一个非负十进制整数，输出与其等值的八进制数。
编写递归程序，实现N！的求解。
编写递归程序，实现以下函数的求解。

编写程序，实现Hanoi塔问题。
【实验步骤】
1.打开VC++。
2.建立工程：点File->New，选Project标签，在列表中选Win32ConsoleApplication，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。
3.创建源文件或头文件：点File->New，选File标签，在列表里选C++SourceFile。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。
4．写好代码
5．编译－＞链接－＞调试
#include"stdio.h"
#include"malloc.h"
#defineOK1
#defineERROR0
#defineOVERFLOW-2
typedefintStatus;
typedefintSElemType;

#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10

typedefstruct
{
SElemType*base;
SElemType*top;
intstacksize;
}SqStack;

StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base)return(OVERFLOW);S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
returnOK;
}

StatusPush(SqStack&S,SElemTypee){
if(S.top-S.base>=S.stacksize)
{S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base)return(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
returnOK;
}

StatusPop(SqStack&S,SElemType&e)
{
if(S.top==S.base)
returnERROR;
e=*--S.top;
returnOK;
}

StatusStackEmpty(SqStackS)
{
if(S.top==S.base)
returnOK;
else
returnERROR;
}

voidconversion(){
SqStackS;
inte,N;
InitStack(S);
printf("请输入转换的数据:");
scanf("%d",&N);
while(N){
Push(S,N%8);
N=N/8;
}
printf("转换后的数据:");
while(!StackEmpty(S)){
Pop(S,e);
printf("%d",e);
}
}

#include"stdio.h"
intfib(intn){

if(n>1)
returnfib(n-1)+fib(n-2);
else
returnn;
}
voidmain(){
intn;
printf("请输入递归的数据:");
scanf("%d",&n);
printf("fib(%d)=%d\n",n,fib(n));
}
#include"stdio.h"
voidmove(charx,intn,charz){

printf("对%d号盘从%c号柱移动到%c号柱:\n",n,x,z);
}

voidhanoi(intn,charx,chary,charz){
if(n==1)
move(x,1,z);
else
{
hanoi(n-1,x,z,y);
move(x,n,z);
hanoi(n-1,y,x,z);
}
}
voidmain(){
intn;
printf("请输入圆盘的个数:");
scanf("%d",&n);
hanoi(n,'x','y','z');
}

【实验心得】
：涌过这次上机实验，我认识到了
在写主函数时，如